How Desmos uses Pratt Parsers (2018) | Hacker News Reader

How Desmos uses Pratt Parsers (2018)

engineering.desmos.com

99 pointsvector_spaces19 comments

I once mentioned Desmos to a college friend who was teaching high school math. This was the first and one of the only times I’ve seen someone express true glee about a software product. They literally shouted, “I love Desmos!” at the dinner table. Kudos to the team for building a product that teachers love that much. Teachers need all the help they can get.

I’m so curious about how their graphing calculator and their geometric construction tools work. I’ve spent marginal amounts of time researching their stack, and it appears to be custom software. If anyone’s familiar with writing about how these systems are built (particularly the display side of things), I’d appreciate some links or titles!

Desmos is a true gem. It took me a while to understand how great the graphing calculator really is. There is also GeoGebra, which has similar functionality and I always thought it is just a rebranded Desmos, but they seem to exists independently.

GeoGebra is actually way older (about 10 years?) and has been a master thesis. I didn't know that it has been acquired by Byju's. https://en.wikipedia.org/wiki/GeoGebra

Sources, under the GPLv3 (code) or Creative Commons (documentation): https://github.com/orgs/geogebra/repositories?type=all

I was at school with the CTO of GeoGebra in the 80s. He released his first geometry app in the early 90s, but I don't know if the current product owes anything to his early software.

Not really, it was in (very bad) C++ and GeoGebra is in Java. A couple of good ideas made it across (and hopefully none of the mistakes :)

PS Hi!

I wrote FooPlot around the same time (2007). Ad revenue supplemented my PhD salary by quite a bit, though later on I couldn't keep up with Desmos as 1 person. The website's been down since AWS phased out EC2 classic instances and I was lazy to move it. But the code for the core library is still here, including the equation parsing which is quite similar to TFA. It's written in 2007-level JavaScript, so this could probably be a lot cleaner now.

https://github.com/dheera/fooplot

    git clone https://github.com/dheera/fooplot
    cd fooplot
    your-favorite-browser sample.html

It should support mouse panning and scroll wheel zooming.

I always link this whenever the need arises to showcase desmos’ general-purpose computation prowess: https://www.desmos.com/calculator/vjnhlumjiw

Vaughan Pratt (who directed the SUN workstation project at Stanford from 1980 to 1982) is the genius who designed the origin Sun Microsystems logo. It was originally square.

John Gage (who was on Richard Nixon's enemy list) is the good troublemaker who thought of turning it 45 degrees like a diamond. He was Sun's Science Officer.

https://www.famouslogos.org/logos/sun-microsystems-logo

https://www.enemieslist.info/list2.php

> Vaughan Pratt (who directed the SUN workstation project at Stanford from 1980 to 1982) is the genius who designed the origin Sun Microsystems logo. It was originally square.

> John Gage (who was on Richard Nixon's enemy list) is the good troublemaker who thought of turning it 45 degrees like a diamond. He was Sun's Science Officer.

Just to have it said, without taking anything away from the admiration of the logo, a square that is rotated 45 degrees is still a square.

Depends on the basis axes maybe

I'm quite aware of that and many other basic geometric definitions, which is exactly why I said "like a diamond" to be clear.

PostScript Sun Logo by Bill Meine:

https://donhopkins.com/home/archive/news-tape/pictures/sun-l...

PostScript Sun Logo by Craig Leres:

https://donhopkins.com/home/archive/news-tape/pictures/sun-l...

> I'm quite aware of that and many other basic geometric definitions, which is exactly why I said "like a diamond" to be clear.

Sure, I would have been very surprised at the thought that you weren't. I was just responding to the statement that the logo was "originally square", which seemed like an odd way to describe something that is still (more or less) square (except as the set-up for a Mitch Hedberg joke). But, of course, it is not wrong.

> PostScript Sun Logo by Bill Meine:

> PostScript Sun Logo by Craig Leres:

I don't have a native PS viewer, but, when I ran those through PS2PDF, both were in the same orientation, only one had solid black characters and one had white characters with black outlines. Is that a problem with my PDF distiller? (But now I see that those are not attributed to Pratt and Gage, as in your original post, so maybe you are just showing later variations on the theme.)

I had the misfortune to use a sun workstation circa 2004 in a grad student lab. It was so sluggish and unpleasant to use that I developed a negative association with the logo. But now you've gotten me to look at it with fresh eyes and I see how brilliant the logo was.

It all went downhill after SunOS 4.1.3.

Slowlaris: so bad I left the company.

> Because we rely on recursive function calls, it is possible that your parser may run out of space on the call stack for deeply nested expressions, like 1^1^1^1.... You could mitigate this by keeping track of the depth of the expression while parsing and throwing a custom “This expression is nested too deeply” error. Another strategy is to move the parsing stack into the heap, either by managing the parser state yourself or using something like trampolining.

That would be Dijkstra's "shunting yard" algorithm.

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

https://stackoverflow.com/a/13637731/1250772

Shunting Yard in TXR Lisp [2015]

https://stackoverflow.com/a/34377302/1250772

> Shunting Yard in TXR Lisp [2015]

I think you skipped the 3rd prompt, which I suspect was (pretty-truth-table '(not a)).

Thanks; I ran that input to be sure, and fixed it.

I recently had to write an expression parser. It turns out there are a few "different" algorithms that are common, but they're actually basically the same algorithm: Pratt parsers, precedence climbing, and the shunting yard algorithm (there may be others, I only started looking into this a week ago). They have small differences but the basic idea is the same.

I went with the shunting yard algorithm because it's not recursive so you don't need to worry about stack overflows. It's basically the iterative version of the other two.

Also note that most implementations of the shunting yard algorithm don't actually check that the expression is valid (e.g. they accept "1 2 +") but it's trivial to fix that with a state machine to check which tokens are acceptable.

This was also the first thing I've tried writing using Copilot and it was a huge time saver. Conservatively I'd say it halved the time it took me to write it. Ok admittedly it's probably a best case - there are a gazillion parser examples out there for it to learn from, but it was still great. I'm going to pay for a subscription.

Yup, they are all variations of the same idea. What makes the Pratt parser so much nicer is how naturally it fits with the rest of a recursive descent parser. The original paper is somewhat annoying to read due to very strange naming of things, but you can write a pratt parser in like 4 lines of code (not counting the mapping from operator to the next parser call), it's crazy simple.

Reply on news.ycombinator.com