Hacker News

The Magic of Partial Evaluation

There are certain ideas in software that are simply beautiful. It doesn't matter if they have any practical use. It doesn't matter that you will never convince your coworkers to consider them. There is just something captivating about the way some computational systems work.

For me, the most beautiful pieces of software are those that reveal something about the nature of programming languages. Programming languages are my obsession. I have never met a problem that couldn't be solved by introducing yet another programming language. Solving a problem at the programming language level is about solving the meta problem. Instead of trying to solve a particular problem, we take a step back and ask how we can solve a whole class of problems at once.

So when I find something that makes me rethink the nature of programming languages, I start rethinking computation as a whole. One of these incredibly beautiful but tricky concepts goes by the name partial evaluation. If you are fascinated by interpreters and compilers, partial evaluation will teach you how they are related, and how you can get a compiler for free.

Partial Evaluation Easy Mode

Partial evaluation has been a fascination of mine for a while. But this whole thing came up when James Long announced he had revived Meta's partial evaluator for JavaScript called prepack.

When I first heard about prepack, I had some high hopes and expectations for the project, but was sadly let down. This revival brought to light those same dreams. But sadly, just as with the original aim, prepack was not designed for beauty, but for practicality. So I figured it was time to renew my own efforts.

Yes, in some ways this is a post repping my own library I'm releasing. But I'm not doing this because I want it to be used. I'm doing this because it lets you play with the idea I find so beautiful. That is what this post is about.

Doing Partial Evaluation by Hand

Consider the following code:

function factorial(n) {
  if (n

Here we have a brainfuck interpreter. And the example program we want to partially evaluate does not require any input at all (in brainfuck , is the way you get input). So when we go to partially evaluate this, we will just get an answer. In this case, this program is actually brainfuck's "hello world".

But what about a program with input?

function main() {
  return brainfuck(",>++[>+++[>++++[ >>-]

Depending on your exposure to interpreters and compilers, this might seem miraculous or mundane. Writing an interpreter and writing a compiler can seem like significantly different undertakings. In the age of AI, perhaps less so, but I think even then many things still hold. It is quite easy to instrument an interpreter, quite a bit harder to do so for a compiler. Changing an interpreter to support new features is quite easy, less so for a compiler.

But more than that, there are all sorts of things that can be thought of as interpreters, that we'd almost never write a compiler for.

function validate(schema, value) {
  switch (schema.type) {
    case "string":
      return typeof value === "string" && (schema.minLength === undefined || value.length >= schema.minLength);
    case "number":
      return typeof value === "number" && Number.isFinite(value) && (schema.min === undefined || value >= schema.min);
    case "boolean":
      return typeof value === "boolean";
    case "array":
      if (!Array.isArray(value)) return false;
      const length = value.length;
      for (let i = 0; i Object.hasOwn(value, key) && validate(schema.properties[key], value[key]));
    default:
      throw new Error("Unknown schema type: " + schema.type);
  }
}

const userSchema = {
  type: "object",
  properties: {
    name: { type: "string", minLength: 1 },
    age: { type: "number", min: 0 },
    tags: { type: "array", items: { type: "string" } }
  }
};

function validateUser(value) {
  return validate(userSchema, value);
}

Consider this simple schema setup. This is code that can easily be partially evaled into something where we have created specialized functions for our particular schema. While not the most crucial code, this can give us a 5x performance boost when our objects start getting more complicated.

You may think that we should just hand-write those functions. Or hand-write a compiler for these schemas. But what about those schemas that exist only at runtime? Now we either need to compile those on the fly, or we have to keep both a compiler and interpreter. Having a way to partial eval lowers this burden quite a bit.

Mind Bending

But if the Futamura projections stopped here, they would be exciting, but not quite the craziness they are. To understand how this can go further, we are going to take this a step beyond your raw intuition of what it means to partially evaluate something and give a different frame.

We can think of partial evaluation as a process of "specializing" a program. What exactly is specializing a program? Well, it is taking a program that is generic and making a version that instead works for a single program.

Let's think about a simple pattern matcher program like an overly simplified regex.

function matches(pattern, text) {
  if (pattern.length === 0) {
    return text.length === 0;
  }
  const firstCharacterMatches = text.length > 0 && pattern[0] === text[0];
  const allowsRepetition = pattern[1] === "*";
  if (allowsRepetition) {
    const remainingPattern = pattern.slice(2);
    if (matches(remainingPattern, text)) {
      return true;
    }
    if (!firstCharacterMatches) {
      return false;
    }
    const remainingText = text.slice(1);
    return matches(pattern, remainingText);
  }
  if (!firstCharacterMatches) {
    return false;
  }
  const remainingPattern = pattern.slice(1);
  const remainingText = text.slice(1);
  return matches(remainingPattern, remainingText);
}

matches("a*b*c", "aaabbc");

This program is generic. It lets you match on many different patterns. That can be great if we need that flexibility. But if you don't have a bunch of patterns, it might be worth it to just make specialized code.

Now, exactly what kind of specialized code? It might be that you only have this literal pattern; then you want to specialize very particularly.

function matchesAStarBStarC(text) {
  let i = 0;
  while (text[i] === "a") i++;
  while (text[i] === "b") i++;
  return text[i] === "c" && i + 1 === text.length;
}

matchesAStarBStarC("aaabbc");

Or you just have * * * as a pattern.

function matchesXStarYStarZStar(x, y, z, text) {
  let i = 0;
  while (i

What if we make a special version of our generic specializer? What is it specialized for? A particular interpreter. Now we have a function that, given any program, will spit out newly specialized interpreters just for that program. Or, in Java speak, we have a specialized interpreter factory.

Let's see a real example of one of these compilers to make this concrete. Here is the interpreter we are going to specialize.

function interp(program, io) {
  var value = null;
  while (program.length > 0) {
    var instruction = program[0];
    if (instruction === "prompt") {
      value = io.prompt();
    } else if (instruction === "print") {
      io.print(value);
    } else {
      throw new Error("Unknown instruction: " + instruction);
    }
    program = program.slice(1);
  }
  return value;
}

When we apply our second projection, we get out the following compiler:

function compile(program) {
  const lines = codegen.buffer();
  const literalSource = codegen.literal(null).source;
  let remaining = program;
  let value = literalSource;
  while (remaining.length > 0) {
    const remainingItem = remaining[0];
    if (remainingItem === "prompt") {
      const ioReference = codegen.reference("io");
      const callSource = codegen.call(lines, ioReference, "prompt", []).source;
      remaining = remaining.slice(1);
      value = callSource;
      continue;
    }
    if (remainingItem === "print") {
      const ioReference2 = codegen.reference("io");
      const args = [codegen.reference(value)];
      codegen.call(lines, ioReference2, "print", args);
      remaining = remaining.slice(1);
      continue;
    }
    const text = "Unknown instruction: " + remainingItem;
    throw new Error(text);
  }
  const valueReference = codegen.reference(value);
  return codegen.finish(lines, valueReference);
}

And if we compile one of these very simple programs, we can see the output:

compile(["prompt", "print"])
// returns as a string
function run(io) {
  var v0 = io.prompt();
  var v1 = io.print(v0);
  return v0;
}

Now, of course, this is not a very interesting language. But hopefully you can see this general idea. Given an interpreter, we automatically derive a compiler! Pretty incredible.

The Third Projection

But we can't stop at the second projection. We have to push on and get to the final mind-bending projection. If you apply our specializer to itself as input, you get a compiler generator.

partial_eval(partial_eval, partial_eval) -> compiler_generator

So now we have a generic function that will spit out compilers for any interpreter we give it!

Playing With It

I have implemented a reasonable, but still very limited partial evaluator for JavaScript in Rust. I have taken it further to try to make it work quite well for a number of different interpreters and interpreter-like programs in JavaScript. I've also tried to get limited versions of the second and third projections working.

Go play with it, see what works, what doesn't, file issues, or better, use some of your tokens to help me make more cases work. But most of all, explore. This is such a rich space.

Below are some papers, blogs, and projects about partial evaluation in some way, shape, or form. There has never been a better time to play with these kinds of crazy techniques for programming languages. Don't let what is practical stop you from exploring the cool, interesting aspects of programming.

  • weval: the WebAssembly partial evaluator
  • Compilation of JavaScript to Wasm, Part 3: Partial Evaluation - Chris Fallin
  • A First Futamura Projection - Veit Heller
  • Partial Evaluation in Truffle - Graal documentation
  • Partial Evaluation of Computation Process-An Approach to a Compiler-Compiler - Yoshihiko Futamura (1971, original English translation)
  • Partial Evaluation and Automatic Program Generation - Neil D. Jones, Carsten K. Gomard, and Peter Sestoft
  • Tutorial on Online Partial Evaluation - William R. Cook and Ralf LΓ€mmel
Read on Hacker News ↗ ← Back to News

Comments

No comments yet. Start the discussion.