7 ms·

A Lisp interpreter written in Lisp (2017)

160 points by capableweb 5y ago

phoe-krk 5y ago
Also see Roots of Lisp[0] for an equivalent article, similarly ending with a working metacircular evaluator. [0] http://www.paulgraham.com/rootsoflisp.html http://www.paulgraham.com/rootsoflisp.html
peterkelly 5y ago
If you find this stuff interesting, I highly recommend "Structure and Interpretation of Computer Programs": https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html
- globular-toast 5y ago
  I highly recommend Lisp in Small Pieces [0]. There is a second edition, but it is only available in French [1]. [0] https://www.cambridge.org/core/books/lisp-in-small-pieces/66FD2BE3EDDDC68CA87D652C82CF849E https://www.cambridge.org/core/books/lisp-in-small-pieces/66... [1] https://www.paracamplus.com/spip/?page=livre&isbn=978-2-916466-03-3 https://www.paracamplus.com/spip/?page=livre&isbn=978-2-9164...
  - ilammy 5y ago
    Seconding Lisp in Small Pieces. I was so impressed with it during my student years that I even translated it into Russian. They don't lie about this “profound sense of enlightenment” once you finally get it.
  - pjmlp 5y ago
    I would also vouch for it.
  - nobleach 5y ago
    I haven't read that one. I've always recommended my devs read The Little Schemer if they ever need something to read on a plane ride. I always recommend reading it while NOT in front of a computer.
- urthor 5y ago
  I am a fan of composing programs personally, https://composingprograms.com/ https://composingprograms.com/ Very well written, concise, and helps with getting a novice programmer going with Python. Which is a huge selling point to practically minded new programmers because you can trick them into it with "this is the best way to learn Python read this." I haven't compared it to SICP though, which is much longer.
mojuba 5y ago
I'm just curious about something on the theoretical level. I think I can see the beauty of it, but if you take the two extremes: - a C++ compiler written in C++ in millions of lines of code - a Perl (PHP, ...) interpreter written in the same language in one line of code (along the lines of `eval $1`) Given the above the Lisp interpreter written in Lisp is somewhere in the middle and it doesn't really say much about the language. Just that you can use the built-in facilities of the language and write an interpreter that will implement those facilities using... themselves. In this regard, how is it fundamentally different from `eval $1`?
- p4bl0 5y ago
  `eval $1` uses the millions of line you were referring to in the first case. The few primitives necessary for a metacircular interpreter can be easily implemented from scratch (hence the name "primitives", which clearly does not apply to `eval`).
  - enriquto 5y ago
    the difference between "millions of lines" and "a few easily implemented primitives" is quantitative. Thus there is a continuum between the two extremes, which was the point of the OP.
  - mjw1007 5y ago
    Where does the garbage collector come from?
    - kaba0 5y ago
      It is going to be an interpreter, so the “host runtime” including the GC will be of the host LISP program.
      - mjw1007 5y ago
        It seems a bit of a stretch to describe that program as an implementation of a Lisp interpreter, then.
tromp 5y ago
I think this binary lambda calculus self-interpreter might be more beautiful: ┬─┬ ────────────────────────────────────────────────────┬─┬── └─┤ ────────────────────────────────────────────────────┼─┼─┬ │ ┬───────────────────────────────────────────────────┼─┼─┼ │ │ ──┬────────────────────────────────────────────── ├─┘ │ │ │ ┬─┼─────────────────────────────────────────────┬ │ │ │ │ ┼─┼─┬─────────────┬───────────────────┬─────────┼ │ │ │ │ ┼─┼─┼───┬─────────┼─┬───────────┬─────┼─┬───────┼ │ │ │ │ │ ┼─┼─┬─┼─────────┼─┼─────────┬─┼───┬─┼─┼─────┬─┼ │ │ │ │ │ │ │ ┼─┼─┬───────┼─┼─┬────── │ │ ┬─┼ ┼─┼─────┼─┼ │ │ │ │ │ │ │ │ │ ┼─────┬ │ ┼─┼───┬── │ │ ├─┘ │ ┼─┬───┼ │ │ │ │ │ │ │ │ │ │ ┼───┬─┼ │ │ ┼─┬─┼─┬ │ ├─┘ │ │ ┼─┬─┼ │ │ │ │ │ │ │ │ │ │ │ ┬─┼─┼ │ │ └─┤ ├─┘ └─┤ │ │ │ ├─┘ │ │ │ │ │ │ │ │ │ │ │ └─┤ │ │ │ ├─┘ │ │ │ ├─┘ │ │ │ │ │ │ │ │ │ │ │ ├─┘ │ ├───┘ │ │ ├─┘ │ │ │ │ │ │ │ │ │ │ ├───┘ ├─┘ │ └─┤ │ │ │ │ │ │ │ │ │ ├─┘ │ │ ├───────┘ │ │ │ │ │ │ │ └─┤ │ ├───────┘ │ │ │ │ │ │ │ ├─────────┘ │ │ │ │ │ │ │ ├───┘ │ │ │ │ │ │ └─┤ │ │ │ │ │ │ ├───────────────────────────┘ │ │ │ │ ├───┘ │ │ │ └─┤ │ │ │ └─────────────────────────────────────────────────┤ │ │ ├───┘ └─────────────────────────────────────────────────────┘ Or in non-graphical notation: (λ 11)(λ λ λ 1(λ λ λ λ 3(λ 5(3(λ 2(3(λ λ 3(λ 123)))(4(λ 4(λ 31(21)))))) (1(2(λ 12))(λ 4(λ 4(λ 2(14)))5))))(33)2)(λ 1((λ 11)(λ 11))) See https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html and https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html for details...
- Y_Y 5y ago
  I thought the same thing, and was going to link to that same article. The paper giving the BLC self-interpreter is one of my favourite ever. For anyone interested in the graphical representation of terms like this I recommend To Dissect a Mockingbird: https://dkeenan.com/Lambda/ https://dkeenan.com/Lambda/
- FullyFunctional 5y ago
bartq 5y ago
That's definitely the same idea: http://metaes.org/docs-metaes.html http://metaes.org/docs-metaes.html.
pjmlp 5y ago
For it to be really beautiful a compiler implementation would be needed as well.
- nic135792 5y ago
  How beautiful can a nonstop running live Lisp evolve to for the duration of an unsigned 64bit clock count attached to a nuclear or solar or geothermal power source and accreting new hardware like spacelab plus Nauka lab?
  - pjmlp 5y ago
    Don't know, you have to ask someone at JPL. I guess as beautiful as C++ and C code controlling the termodynamics of properllers in an hostile weather organism while looking for the presence of life.
flamboyant_ride 5y ago
I recently completed Programming languages - Part B, by Dan Grossman on coursera (https://www.coursera.org/learn/programming-languages-part-b https://www.coursera.org/learn/programming-languages-part-b). The homework in Racket was a very similar problem. Needless to say it was mindbending and to get the final interpreter work with all those expressions(nested) / lambdas was so satisfying!
DonHopkins 5y ago
Glenn Reid wrote a PostScript partial evaluator in PostScript that optimized other PostScript drawning programs, called "The Distillery". You would send still.ps to your PostScript printer, and then send another PostScript file that drew something to the printer. The first PostScript Distillery program would then partially evaluate the second PostScript drawing program, and send back a third PostScript program, an optimized drawing program, with all the loops and conditionals unrolled, calculations and transformations pre-computed, all in the same coordinate system. It was originally John Warnock's idea, that Glenn implemented. And it led to Adobe Acrobat's "Distiller". Acrobat is basically PostScript without the programming language. No, you could not make it optimize itself by sending it to a PostScript printer two times in a row. It was not magic: all it did was intercept and capture the side-effects of the PostScript drawing commands (fill, stroke, show), read out the path, and optimize it in a uniform coordinate system. Since it didn't do any drawing, so it would just output an empty program if run on itself. (Take that, halting problem!) https://donhopkins.com/home/archive/postscript/newerstill.ps.txt https://donhopkins.com/home/archive/postscript/newerstill.ps... >From: greid@adobe.com (Glenn Reid) Newsgroups: comp.lang.postscript Subject: release 10 of the Distillery Date: 10 Mar 89 10:21:52 GMT >Here is another release of the PostScript Language Distillery. I know it's not terribly long after the last release, but there are some significant enhancements, and I thought it would be worthwhile. >I finally took a closer look at user-defined fonts, which now seem to be working fairly well. In particular, it seems to handle the Macintosh screen bitmap fonts that get used if the native font is unavailable when the print file is genreated. The entire user-defined font is reverse-engineered to the output file as it stands, and is used exactly like the original file used it. I also fixed some rotate text bugs, rotated charpath, and a few other things. >I want to emphasize that probably the two best uses of this program, currently, are to do speed comparisons of various PostScript language drivers and to convert "non-conforming" files into "conforming" files. It is not particularly well suited to carefully hand-written programs, especially not those which use looping constructs. It works (usually), but it unrolls the loops and makes the files much bigger. It's also possible to simply write a metacircular PostScript evaluator in PostScript: https://donhopkins.com/home/archive/NeWS/ps.ps https://donhopkins.com/home/archive/NeWS/ps.ps https://donhopkins.medium.com/the-shape-of-psiber-space-october-1989-19e2dfa4d91e#c699 https://donhopkins.medium.com/the-shape-of-psiber-space-octo... >Printing Distilled PostScript >The data structure displays (including those of the Pseudo Scientific Visualizer, described below) can be printed on a PostScript printer by capturing the drawing commands in a file. >Glenn Reid’s “Distillery” program is a PostScript optimizer, that executes a page description, and (in most cases) produces another smaller, more efficient PostScript program, that prints the same image. [Reid, The Distillery] The trick is to redefine the path consuming operators, like fill, stroke, and show, so they write out the path in device space, and incremental changes to the graphics state. Even though the program that computes the display may be quite complicated, the distilled graphical output is very simple and low level, with all the loops unrolled. >The NeWS distillery uses the same basic technique as Glenn Reid’s Distillery, but it is much simpler, does not optimize as much, and is not as complete. >The Metacircular Postscript Interpreter >A program that interprets the language it is written in is said to be “metacircular”. [Abelson, Structure and Interpretation of Computer Programs] Since PostScript, like Scheme, is a simple yet powerful language, with procedures as first class data structures, implementing “ps.ps", a metacircular PostScript interpreter, turned out to be straightforward (or drawrofthgiarts, with respect to the syntax). A metacircular PostScript interpreter should be compatible with the "exec" operator (modulo bugs and limitations). Some of the key ideas came from Crispin Goswell's PostScript implementation. [Goswell, An Implementation of PostScript] >The metacircular interpreter can be used as a debugging tool, to trace and single step through the execution of PostScript instructions. It calls a trace function before each instruction, that you can redefine to trace the execution in any way. One useful trace function animates the graphical stack on the PSIBER Space Deck step by step. >The meta-execution stack is a PostScript array, into which the metacircular interpreter pushes continuations for control structures. (forall, loop, stopped, etc…) A continuation is represented as a dictionary in which the state needed by the control structure is stored (plus some other information to help with debugging). >It is written in such a way that it can interpret itself: It has its own meta-execution stack to store the program’s state, and it stashes its own state on the execution stack of the interpreter that’s interpreting it, so the meta-interpreter’s state does not get in the way of the program it’s interpreting. >It is possible to experiment with modifications and extensions to PostScript, by revectoring functions and operators, and modifying the metacircular interpreter. >The metacircular interpreter can serve as a basis for PostScript algorithm animation. One very simple animation is a two dimensional plot of the operand stack depth (x), against the execution stack depth (y), over time.
hazbo 5y ago
I can't recommend the talk Dr Byrd did on this enough: https://www.youtube.com/watch?v=OyfBQmvr2Hc https://www.youtube.com/watch?v=OyfBQmvr2Hc It's one of my favorite programs to play around with. I wrote about an Erlang implementation of this a short while back: https://thingstoreadabout.substack.com/p/lisp-in-seven-parts https://thingstoreadabout.substack.com/p/lisp-in-seven-parts
bane 5y ago
This is really cool! Is it the most beautiful program ever written? Not IMHO. I can't find it now, but there was a short live coding demo/presentation that essentially went from a blank file, to a stack-based language, to something like a webasm interpreter in like an hour with full explanations that made it all seem painfully obvious. It sent shivers up my spine and was absolutely amazing to watch.
- rashidujang 5y ago
  Would love to see this too!
- yesenadam 5y ago
  Sounds like this! Dave Beazley's A Talk Near the Future of Python (a.k.a., Dave live-codes a WebAssembly Interpreter) (2019) https://www.youtube.com/watch?v=r-A78RgMhZU https://www.youtube.com/watch?v=r-A78RgMhZU
  - bane 5y ago
    Oh man! Yup, that's exactly it! This was one of the most impressive and elegant demonstrations I've ever seen and I've been in computing since the 80s.
cgh 5y ago
Maybe not the most beautiful, but certainly among the most impressive: https://en.wikipedia.org/wiki/1K_ZX_Chess https://en.wikipedia.org/wiki/1K_ZX_Chess
temp0826 5y ago
when did "beautiful" become synonymous with "spilled coffee on my keyboard and it barfed out a bunch of parentheses"
- fishmaster 5y ago
  Never.

160 points by capableweb 5y ago

Also see Roots of Lisp[0] for an equivalent article, similarly ending with a working metacircular evaluator. [0] http://www.paulgraham.com/rootsoflisp.html http://www.paulgraham.com/rootsoflisp.html

peterkelly 5y ago

If you find this stuff interesting, I highly recommend "Structure and Interpretation of Computer Programs": https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html

globular-toast 5y ago
I highly recommend Lisp in Small Pieces [0]. There is a second edition, but it is only available in French [1]. [0] https://www.cambridge.org/core/books/lisp-in-small-pieces/66FD2BE3EDDDC68CA87D652C82CF849E https://www.cambridge.org/core/books/lisp-in-small-pieces/66... [1] https://www.paracamplus.com/spip/?page=livre&isbn=978-2-916466-03-3 https://www.paracamplus.com/spip/?page=livre&isbn=978-2-9164...
- ilammy 5y ago
  Seconding Lisp in Small Pieces. I was so impressed with it during my student years that I even translated it into Russian. They don't lie about this “profound sense of enlightenment” once you finally get it.
- pjmlp 5y ago
  I would also vouch for it.
- nobleach 5y ago
  I haven't read that one. I've always recommended my devs read The Little Schemer if they ever need something to read on a plane ride. I always recommend reading it while NOT in front of a computer.
urthor 5y ago
I am a fan of composing programs personally, https://composingprograms.com/ https://composingprograms.com/ Very well written, concise, and helps with getting a novice programmer going with Python. Which is a huge selling point to practically minded new programmers because you can trick them into it with "this is the best way to learn Python read this." I haven't compared it to SICP though, which is much longer.

mojuba 5y ago

I'm just curious about something on the theoretical level. I think I can see the beauty of it, but if you take the two extremes: - a C++ compiler written in C++ in millions of lines of code - a Perl (PHP, ...) interpreter written in the same language in one line of code (along the lines of `eval $1`) Given the above the Lisp interpreter written in Lisp is somewhere in the middle and it doesn't really say much about the language. Just that you can use the built-in facilities of the language and write an interpreter that will implement those facilities using... themselves. In this regard, how is it fundamentally different from `eval $1`?

p4bl0 5y ago
`eval $1` uses the millions of line you were referring to in the first case. The few primitives necessary for a metacircular interpreter can be easily implemented from scratch (hence the name "primitives", which clearly does not apply to `eval`).
- enriquto 5y ago
  the difference between "millions of lines" and "a few easily implemented primitives" is quantitative. Thus there is a continuum between the two extremes, which was the point of the OP.
- mjw1007 5y ago
  Where does the garbage collector come from?
  - kaba0 5y ago
    It is going to be an interpreter, so the “host runtime” including the GC will be of the host LISP program.
    - mjw1007 5y ago
      It seems a bit of a stretch to describe that program as an implementation of a Lisp interpreter, then.

tromp 5y ago

I think this binary lambda calculus self-interpreter might be more beautiful: ┬─┬ ────────────────────────────────────────────────────┬─┬── └─┤ ────────────────────────────────────────────────────┼─┼─┬ │ ┬───────────────────────────────────────────────────┼─┼─┼ │ │ ──┬────────────────────────────────────────────── ├─┘ │ │ │ ┬─┼─────────────────────────────────────────────┬ │ │ │ │ ┼─┼─┬─────────────┬───────────────────┬─────────┼ │ │ │ │ ┼─┼─┼───┬─────────┼─┬───────────┬─────┼─┬───────┼ │ │ │ │ │ ┼─┼─┬─┼─────────┼─┼─────────┬─┼───┬─┼─┼─────┬─┼ │ │ │ │ │ │ │ ┼─┼─┬───────┼─┼─┬────── │ │ ┬─┼ ┼─┼─────┼─┼ │ │ │ │ │ │ │ │ │ ┼─────┬ │ ┼─┼───┬── │ │ ├─┘ │ ┼─┬───┼ │ │ │ │ │ │ │ │ │ │ ┼───┬─┼ │ │ ┼─┬─┼─┬ │ ├─┘ │ │ ┼─┬─┼ │ │ │ │ │ │ │ │ │ │ │ ┬─┼─┼ │ │ └─┤ ├─┘ └─┤ │ │ │ ├─┘ │ │ │ │ │ │ │ │ │ │ │ └─┤ │ │ │ ├─┘ │ │ │ ├─┘ │ │ │ │ │ │ │ │ │ │ │ ├─┘ │ ├───┘ │ │ ├─┘ │ │ │ │ │ │ │ │ │ │ ├───┘ ├─┘ │ └─┤ │ │ │ │ │ │ │ │ │ ├─┘ │ │ ├───────┘ │ │ │ │ │ │ │ └─┤ │ ├───────┘ │ │ │ │ │ │ │ ├─────────┘ │ │ │ │ │ │ │ ├───┘ │ │ │ │ │ │ └─┤ │ │ │ │ │ │ ├───────────────────────────┘ │ │ │ │ ├───┘ │ │ │ └─┤ │ │ │ └─────────────────────────────────────────────────┤ │ │ ├───┘ └─────────────────────────────────────────────────────┘ Or in non-graphical notation: (λ 11)(λ λ λ 1(λ λ λ λ 3(λ 5(3(λ 2(3(λ λ 3(λ 123)))(4(λ 4(λ 31(21)))))) (1(2(λ 12))(λ 4(λ 4(λ 2(14)))5))))(33)2)(λ 1((λ 11)(λ 11))) See https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html and https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html for details...

Y_Y 5y ago
I thought the same thing, and was going to link to that same article. The paper giving the BLC self-interpreter is one of my favourite ever. For anyone interested in the graphical representation of terms like this I recommend To Dissect a Mockingbird: https://dkeenan.com/Lambda/ https://dkeenan.com/Lambda/
FullyFunctional 5y ago

bartq 5y ago

That's definitely the same idea: http://metaes.org/docs-metaes.html http://metaes.org/docs-metaes.html.

pjmlp 5y ago

For it to be really beautiful a compiler implementation would be needed as well.

nic135792 5y ago
How beautiful can a nonstop running live Lisp evolve to for the duration of an unsigned 64bit clock count attached to a nuclear or solar or geothermal power source and accreting new hardware like spacelab plus Nauka lab?
- pjmlp 5y ago
  Don't know, you have to ask someone at JPL. I guess as beautiful as C++ and C code controlling the termodynamics of properllers in an hostile weather organism while looking for the presence of life.

flamboyant_ride 5y ago

I recently completed Programming languages - Part B, by Dan Grossman on coursera (https://www.coursera.org/learn/programming-languages-part-b https://www.coursera.org/learn/programming-languages-part-b). The homework in Racket was a very similar problem. Needless to say it was mindbending and to get the final interpreter work with all those expressions(nested) / lambdas was so satisfying!

DonHopkins 5y ago

Glenn Reid wrote a PostScript partial evaluator in PostScript that optimized other PostScript drawning programs, called "The Distillery". You would send still.ps to your PostScript printer, and then send another PostScript file that drew something to the printer. The first PostScript Distillery program would then partially evaluate the second PostScript drawing program, and send back a third PostScript program, an optimized drawing program, with all the loops and conditionals unrolled, calculations and transformations pre-computed, all in the same coordinate system. It was originally John Warnock's idea, that Glenn implemented. And it led to Adobe Acrobat's "Distiller". Acrobat is basically PostScript without the programming language. No, you could not make it optimize itself by sending it to a PostScript printer two times in a row. It was not magic: all it did was intercept and capture the side-effects of the PostScript drawing commands (fill, stroke, show), read out the path, and optimize it in a uniform coordinate system. Since it didn't do any drawing, so it would just output an empty program if run on itself. (Take that, halting problem!) https://donhopkins.com/home/archive/postscript/newerstill.ps.txt https://donhopkins.com/home/archive/postscript/newerstill.ps... >From: greid@adobe.com (Glenn Reid) Newsgroups: comp.lang.postscript Subject: release 10 of the Distillery Date: 10 Mar 89 10:21:52 GMT >Here is another release of the PostScript Language Distillery. I know it's not terribly long after the last release, but there are some significant enhancements, and I thought it would be worthwhile. >I finally took a closer look at user-defined fonts, which now seem to be working fairly well. In particular, it seems to handle the Macintosh screen bitmap fonts that get used if the native font is unavailable when the print file is genreated. The entire user-defined font is reverse-engineered to the output file as it stands, and is used exactly like the original file used it. I also fixed some rotate text bugs, rotated charpath, and a few other things. >I want to emphasize that probably the two best uses of this program, currently, are to do speed comparisons of various PostScript language drivers and to convert "non-conforming" files into "conforming" files. It is not particularly well suited to carefully hand-written programs, especially not those which use looping constructs. It works (usually), but it unrolls the loops and makes the files much bigger. It's also possible to simply write a metacircular PostScript evaluator in PostScript: https://donhopkins.com/home/archive/NeWS/ps.ps https://donhopkins.com/home/archive/NeWS/ps.ps https://donhopkins.medium.com/the-shape-of-psiber-space-october-1989-19e2dfa4d91e#c699 https://donhopkins.medium.com/the-shape-of-psiber-space-octo... >Printing Distilled PostScript >The data structure displays (including those of the Pseudo Scientific Visualizer, described below) can be printed on a PostScript printer by capturing the drawing commands in a file. >Glenn Reid’s “Distillery” program is a PostScript optimizer, that executes a page description, and (in most cases) produces another smaller, more efficient PostScript program, that prints the same image. [Reid, The Distillery] The trick is to redefine the path consuming operators, like fill, stroke, and show, so they write out the path in device space, and incremental changes to the graphics state. Even though the program that computes the display may be quite complicated, the distilled graphical output is very simple and low level, with all the loops unrolled. >The NeWS distillery uses the same basic technique as Glenn Reid’s Distillery, but it is much simpler, does not optimize as much, and is not as complete. >The Metacircular Postscript Interpreter >A program that interprets the language it is written in is said to be “metacircular”. [Abelson, Structure and Interpretation of Computer Programs] Since PostScript, like Scheme, is a simple yet powerful language, with procedures as first class data structures, implementing “ps.ps", a metacircular PostScript interpreter, turned out to be straightforward (or drawrofthgiarts, with respect to the syntax). A metacircular PostScript interpreter should be compatible with the "exec" operator (modulo bugs and limitations). Some of the key ideas came from Crispin Goswell's PostScript implementation. [Goswell, An Implementation of PostScript] >The metacircular interpreter can be used as a debugging tool, to trace and single step through the execution of PostScript instructions. It calls a trace function before each instruction, that you can redefine to trace the execution in any way. One useful trace function animates the graphical stack on the PSIBER Space Deck step by step. >The meta-execution stack is a PostScript array, into which the metacircular interpreter pushes continuations for control structures. (forall, loop, stopped, etc…) A continuation is represented as a dictionary in which the state needed by the control structure is stored (plus some other information to help with debugging). >It is written in such a way that it can interpret itself: It has its own meta-execution stack to store the program’s state, and it stashes its own state on the execution stack of the interpreter that’s interpreting it, so the meta-interpreter’s state does not get in the way of the program it’s interpreting. >It is possible to experiment with modifications and extensions to PostScript, by revectoring functions and operators, and modifying the metacircular interpreter. >The metacircular interpreter can serve as a basis for PostScript algorithm animation. One very simple animation is a two dimensional plot of the operand stack depth (x), against the execution stack depth (y), over time.

hazbo 5y ago

I can't recommend the talk Dr Byrd did on this enough: https://www.youtube.com/watch?v=OyfBQmvr2Hc https://www.youtube.com/watch?v=OyfBQmvr2Hc It's one of my favorite programs to play around with. I wrote about an Erlang implementation of this a short while back: https://thingstoreadabout.substack.com/p/lisp-in-seven-parts https://thingstoreadabout.substack.com/p/lisp-in-seven-parts

bane 5y ago

This is really cool! Is it the most beautiful program ever written? Not IMHO. I can't find it now, but there was a short live coding demo/presentation that essentially went from a blank file, to a stack-based language, to something like a webasm interpreter in like an hour with full explanations that made it all seem painfully obvious. It sent shivers up my spine and was absolutely amazing to watch.

rashidujang 5y ago
Would love to see this too!
yesenadam 5y ago
Sounds like this! Dave Beazley's A Talk Near the Future of Python (a.k.a., Dave live-codes a WebAssembly Interpreter) (2019) https://www.youtube.com/watch?v=r-A78RgMhZU https://www.youtube.com/watch?v=r-A78RgMhZU
- bane 5y ago
  Oh man! Yup, that's exactly it! This was one of the most impressive and elegant demonstrations I've ever seen and I've been in computing since the 80s.

cgh 5y ago

Maybe not the most beautiful, but certainly among the most impressive: https://en.wikipedia.org/wiki/1K_ZX_Chess https://en.wikipedia.org/wiki/1K_ZX_Chess

temp0826 5y ago

when did "beautiful" become synonymous with "spilled coffee on my keyboard and it barfed out a bunch of parentheses"

fishmaster 5y ago
Never.