[HN Gopher] Desmos uses Pratt Parsers (2018)
___________________________________________________________________
Desmos uses Pratt Parsers (2018)
Author : vector_spaces
Score : 69 points
Date : 2023-06-08 17:46 UTC (5 hours ago)
(HTM) web link (engineering.desmos.com)
(TXT) w3m dump (engineering.desmos.com)
| IshKebab wrote:
| 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.
| awhitty wrote:
| 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!
| dheera wrote:
| 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.
| jansan wrote:
| 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.
| ReleaseCandidat wrote:
| 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
| xeonmc wrote:
| I always link this whenever the need arises to showcase desmos'
| general-purpose computation prowess:
| https://www.desmos.com/calculator/vjnhlumjiw
| kazinator wrote:
| > _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
| yakubin wrote:
| _> Shunting Yard in TXR Lisp [2015]_
|
| I think you skipped the 3rd prompt, which I suspect was
| _(pretty-truth-table '(not a))_.
| DonHopkins wrote:
| 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
| JadeNB wrote:
| > 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.
| diffxx wrote:
| 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.
___________________________________________________________________
(page generated 2023-06-08 23:00 UTC)