A Lisp Interpreter Implemented in Conway's Game of Life (2021)

Posted by pabs3 2 days ago

Comments

Comment by Xmd5a 2 days ago

https://www.cambridge.org/core/books/abs/algorithmic-informa...

I - Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP

Gregory. J. Chaitin

> And in Chapter 4 we present a register machine interpreter for this LISP, and then compile it into a diophantine equation.

Comment by qubex 18 hours ago

Being somebody whose absolute favourite book is The Computational Beauty of Nature by Gary William Flake (1998), this is the kind of stuff I come here for. So much more interesting than shop talk about the framework of the week, blockchain hype segueing into AI frenzy, and making fun of people who get stuck in VIM (I once got stuck in nano when for some reason the Control key became unmapped for unknown reasons eventually solved by spawning a new shell, killing the killalling the process, and resetting the terminal, so yeah — I might be an old hand but making fun of people is so not funny).

I’m glad the real hacker ethos of making stuff arbitrarily convoluted by mixing and matching various computational-equivalent substrates results is some truly bizarre results. An instant classic of the genre.

Comment by forgotpwd16 1 day ago

Since although details given, it isn't explicitly stated, ELVM is an infrastructure with an 8cc front-end, a simple IR, and multiple target back-ends which, alongside others, include QFTASM, that article is about, brainfuck, and lambda / binary lambda calculus. Essentially you can write code in C and have it compiled to bunch of weird targets.

Mentioning the last one (same model, different encoding basically) because that guy (@woodrush*) also made a Lisp to λ-calculus expressions compiler which then used to make a Lisp interpreter expressed in λ-calculus (which can evaluate aforementioned compiler and also has an a λ-calculus interpreter implementation available**) and a VM for a Lisp/ELVM-like assembly. The λ ELVM backend was made possible integrating this VM in ELVM. And, of course using his own contributed backend, had an 8cc-based C compiler expressed in λ-calculus.

*If want a drink game to get drunk asap, "take a shot for every λ" in @woodrush Lambda projects is a strong option.

**For extra inception points, can use it to run 2012 Tromp's λ self-interpreter.

Comment by anthk 1 day ago

Which is basically this but in Scheme:

https://t3x.org/clc/code.html

Comment by forgotpwd16 1 day ago

Τhat's the reverse, λ->VM/C (also very interesting). Theoretically should be possible to use this code to run @woodrush's λ expressions (the Lisp interpreter, ELVM vCPU, and C compiler).

Comment by dang 2 days ago

Related. Others?

A Lisp interpreter implemented in Conway's Game of Life (2021) - https://news.ycombinator.com/item?id=34266240 - Jan 2023 (25 comments)

A Lisp Interpreter Implemented in Conway's Game of Life - https://news.ycombinator.com/item?id=29661616 - Dec 2021 (85 comments)

Comment by anthk 1 day ago

I'd love a Lisp written for a 16 bit SUBLEQ interpreter. There's OFC EForth, but we have no Lisp.

https://github.com/howerj/subleq

Same, but with instruction multiplexing.

https://github.com/howerj/muxleq