Partially Evaluate an Interpreter and You Get a Compiler for Free

The Magic of Partial Evaluation

Jimmy Miller walks through partial evaluation: feed a program's known inputs into an interpreter at build time and strip away everything that can already be computed. Do it to a brainfuck interpreter with a fixed program and the interpreter vanishes, leaving compiled code behind — the first Futamura projection. He also shows how the same trick specializes schema validators, cutting runtime overhead, and argues the idea is worth admiring even when it never ships.

This is the first incredible fact: when you take an interpreter and partially evaluate it with a program, you get the compiled program out!
  1. TuringTest

    > For me, the most beautiful pieces of software are those that reveal something about the nature of programming languages.

    There are three moments that make the functional programmer evolve their understanding of how a programming language really works as a symbolic representation of human thought, beyond the metaphor taught in school of a computer program as a grinder that crunches input data and produces results.

    The first one is when you really understand recursion and how a function can be defined in terms of itself (with varying parameters for each call).

    The second is when you discover Prolog variable unification or Haskell lazy evaluation and how you can represent infinite data structures without having the program hang in an infinite loop.

    Third one is when you learn that the behavior of any imperative language (down to the working of the microprocessor data paths) can be fully represented in a pure functional rewrite language (without destructive assignment / cell state changes).

    Those insights make one realize that all programming paradigms have the nature of symbols processing in common and there's no "true description" of a program's runtime execution - the imperative, functional and logic views of the running program are all equivalent representations.

  2. artrax

    We build this as a c++ library, do to query-compilation for our stream processing engine.

    https://github.com/nebulastream/nautilus

    It allows us to implement operators or functions without having to write them in terms of LLVM IR DSL (or similar). Rather, you write your functions over a wrapper type (and returning one), for which there is an overload of anything which you can overload in c++.

    You can instantiate a wrapper from some c++ value, in which case the wrapper will just forward everything to this value, which was nice for debugging in the preagentic era.

    But, you can also instantiate such a wrapper as a tracer, and the result of the functions evaluation will be a trace.

    For controlflow, we record whenever a wrapper type is evaluated as a bool, first return true, and when we reach the end of one branch, throw an exception to get back to the beginning, and start all over again, but evaluate it to false.

    The resulting trace we can turn into LLVM IR and compile, or run for example in wasm

  3. apignotti

    We implemented a similar concept in our C++ -> JavaScript/WebAssembly compiler (Cheerp) several years ago. It was a nice challenge.

    https://labs.leaningtech.com/blog/reducing-webassembly-size-...

More from this day

2026-11-18