Blazing-Fast Lambda Calculus via Metaprogramming
Session Abstract
Interpreting lambda calculus is simple but slow. Using multi-stage metaprogramming, we built a JIT that compiles each program to native JVM code at load time, running 2–10x faster than existing interpreters – including heavily optimized Rust and Haskell implementations. The surprising part: staging resulted in remarkably little code.
Session Description
Many systems ship small programs in a tiny language based on lambda calculus – functions, function calls, a handful of built-in operations, and constants – and run them with an interpreter.
We replaced the interpreter with a JIT that translates each program into native JVM code as it loads: a lambda becomes a JVM lambda, an application becomes a real function call, and built-ins and constants map onto efficient runtime primitives.
What I find most compelling is how little code it took: multi-stage metaprogramming let us turn an interpreter into a compiler with surprisingly little code, which says a lot about how powerful the technique is.
I’ll walk through the staging approach, the benchmark results against existing interpreters, and the subtle pitfalls of JIT-compiling an untyped language while preserving exact evaluation semantics – a practical tour of runtime code generation and metaprogramming on the JVM.
