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

3 comments

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.

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.