I compiled WebAssembly to lambda calculus! A journey into esoteric programming
summary
A compiler converts WebAssembly 1.0 (floats excluded) into pure lambda calculus, emitting lambda programs that interpret WASM semantics including numbers as bit lists, bytes big‑endian and u32 little‑endian, random access memory implemented as a sparse tree to cheaply represent 4 GB memory as sparse tree, structured control flow implemented as segments with a control‑flow stack for loops, and mutual recursion for functions. It compiles Rust/C/C++ to lambdas and runs examples: Mandelbrot renders in 4 minutes, tic‑tac‑toe AI takes about 12 minutes for first move. Source: GitHub.
AI-written summary · about
chapters (8)
- 0:00Project introduction
- 1:01Compile WebAssembly to lambda calculus
- 2:45Lambda calculus evaluation
- 4:30Data structures in lambda calculus
- 7:58Memory as tree structure
- 9:23WebAssembly control flow
- 11:30Compiler results and performance
- 13:17Demonstrations and thoughts
