Jimmy Miller

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 <= 1) return 1;
  return n * factorial(n - 1);
}

factorial(5);

As a person who reads code, you can think about how this code computes and what answer it will give. But you can do more than just give the answer. You can see the expanded form of this particular code for these particular calls. This code is spiritually the same as the following expression, once we expand it out.

5 * (4 * (3 * (2 * 1)))

In this case, there is really nothing at all that this code needs to do at runtime. A sufficiently smart compiler will just run this code directly at compile time and give the answer. But this is a bit less clear if things come in at runtime.

function power(base, exponent) {
  if (exponent === 0) return 1;
  return base * power(base, exponent - 1);
}

power(process.argv[2], 5)

It might seem like we can't do anything here, but again, if you are used to thinking about how programs run, you can trace this out and realize this is just the same as:

process.argv[2] * (process.argv[2] * (process.argv[2] * (process.argv[2] * (process.argv[2] * 1))))

What we have done in both of these cases is called partial evaluation. In the first, it was a trivial case because everything was statically known. But in this latter case, we have reduced a program down into the essentials of its dynamic structure. There are no recursive function calls left. All of this has been expanded as far as it could till we get just the dynamic parts of the code remaining.

The Big Idea#

This intuitive notion of partial evaluation is all you need to know to appreciate the beauty here. Partial evaluation just evaluates the part of the program we can evaluate at build time and leaves all the rest. When we do this with certain programs in certain combinations, we get some quite surprising, incredible behavior.

function calculate(expr) {
  if (typeof expr === "number") return expr;
  switch (expr[0]) {
    case "+": return calculate(expr[1]) + calculate(expr[2]);
    case "-": return calculate(expr[1]) - calculate(expr[2]);
    case "*": return calculate(expr[1]) * calculate(expr[2]);
    case "/": return calculate(expr[1]) / calculate(expr[2]);
    default: throw new Error("Unknown operator");
  }
}

calculate(["+", 1, ["*", 2, 3]]);

Here we have a very simple interpreter for a language that just supports arithmetic. For the above expression, you should be able to think about how we could start "partially" evaluating it. (In this case, it can be a full evaluation.) If this kind of partial evaluation isn't quite clicking for you, I've put the steps below to hopefully help it make sense.

calculate(["+", 1, ["*", 2, 3]])
→ calculate(1) + calculate(["*", 2, 3])
→ 1 + calculate(["*", 2, 3])
→ 1 + (calculate(2) * calculate(3))
→ 1 + (2 * calculate(3))
→ 1 + (2 * 3)
→ 1 + 6
→ 7

This is a simple evaluation of the code. But what happens if we throw a value we don't know into the expression?

calculate(["+", Number(process.argv[2]), ["*", 2, 3]])
→ calculate(Number(process.argv[2])) + calculate(["*", 2, 3])
→ Number(process.argv[2]) + calculate(["*", 2, 3])
→ Number(process.argv[2]) + (calculate(2) * calculate(3))
→ Number(process.argv[2]) + (2 * calculate(3))
→ Number(process.argv[2]) + (2 * 3)
→ Number(process.argv[2]) + 6

Here we can see that clear partial evaluation difference. We don't know how to evaluate Number(process.argv[2]). We have no idea what the answer to that will be. But as part of this process, we do know some partial information about it. For example, when we get to

if (typeof expr === "number") return expr;

we know that Number(process.argv[2]) is indeed a number. So we can partially evaluate it further. Hopefully this is all making sense. But if you are like me, this all might seem a bit trivial and uninteresting. So let's look at a more complicated example.

function brainfuck(code, input = "") {
  const tape = new Uint8Array(30000);
  const jumps = {}, stack = [];
  let pointer = 0, inputPointer = 0, output = "";
  for (let i = 0; i < code.length; i++) {
    if (code[i] === "[") stack.push(i);
    if (code[i] === "]") {
      const start = stack.pop();
      jumps[start] = i;
      jumps[i] = start;
    }
  }
  for (let i = 0; i < code.length; i++) {
    switch (code[i]) {
      case ">": pointer++; break;
      case "<": pointer--; break;
      case "+": tape[pointer]++; break;
      case "-": tape[pointer]--; break;
      case ".": output += String.fromCharCode(tape[pointer]); break;
      case ",":
        tape[pointer] = inputPointer < input.length
          ? input.charCodeAt(inputPointer++)
          : 0;
        break;
      case "[": if (!tape[pointer]) i = jumps[i]; break;
      case "]": if (tape[pointer]) i = jumps[i]; break;
    }
  }
  return output;
}

brainfuck("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");

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(",>++[>+++[>++++[<<<+>>>-]<-]<-]<.", process.argv[2])
}

When we do our partial evaluation, we get the following:

function main(b) {
  let a;
  a: {
    a = process.argv[2];
    a = a === void 0 ? "" : a;
    if (0 < a.length) {
      a = a.charCodeAt(0);
      break a;
    }
    a = 0;
  }
  a = (a & 255) + 24 & 255;
  return String.fromCharCode(a);
}

What is this? A compiled brainfuck program! This is the first incredible fact: when you take an interpreter and partially evaluate it with a program, you get the compiled program out! Now this particular exact form is an artifact of how my partial evaluator works. You could imagine slightly different code. But the key is that what we've done is remove the interpreter completely.

The Projections#

What we've discovered here is the first of three so-called Futamura Projections. Our partial evaluator, when applied to an interpreter and given a program, can give us a compiled version of that program. Or to put it in pseudocode.

partial_eval(interpreter, prog) -> compiled_prog

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 < length; i++) {
        if (i in value && !validate(schema.items, value[i])) return false;
      }
      return true;
    case "object":
      return value !== null && typeof value === "object" &&
        !Array.isArray(value) &&
        Object.keys(schema.properties).every(key =>
          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 <x>*<y>*<z>* as a pattern.

function matchesXStarYStarZStar(x, y, z, text) {
  let i = 0;
  while (i < text.length && text[i] === x) i++;
  while (i < text.length && text[i] === y) i++;
  while (i < text.length && text[i] === z) i++;
  return i === text.length;
}

matchesXStarYStarZStar("a", "b", "c", "aaabbc");

For any bit of generic code, we can think of how to move our code to a more specialized form.

Specializing the Specializer#

Partial evaluation is a form of specialization that figures out what it should specialize on based on what input is static and what is dynamic. In many ways, a partial evaluator is a generic specializer. Given any program, we can make a specialized version of it for any input. What happens if we specialize an interpreter for a given input? We get back that interpreter for only exactly that one program. But what do we need then? Do we need all this generic dispatch? No, we know the full program. We don't need any operations we don't actually use. We can fully get rid of all the generic interpreter mechanism.

But if the specializer can specialize any program, can it specialize itself?

This leads us to the second Futamura projection. Put in our pseudo-code format, we get:

partial_eval(partial_eval, interpreter) -> compiler

Or, to put it in our specializer language, 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.