The Magic of Partial Evaluation

Hacker News by 14 min read 509x views
The Magic of Partial Evaluation

Share Post

There are certain ideas in application that are merely beautiful. It doesn't matter if they have any applicable use. It doesn't matter that you volition never convince your coworkers to regard them. There is fair item captivating concerning the way several computational systems work.

For me, the most beautiful pieces of application are those that disclose item concerning the nature of programming languages. Programming languages are my obsession. I have never met a issue that couldn't be solved by introducing yet another programming language. Solving a issue at the programming tongue flat is concerning solving the meta problem. Instead of trying to resolve a particular problem, we obtain a stage rear and ask how we can resolve a entire category of problems at once.

So whenever I discover item that makes me rethink the nature of programming languages, I commencement 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 volition instruct 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 quarry for a while. But this entire item came up whenever James Long announced he had revived Meta's partial evaluator for JavaScript called prepack. When I archetypal heard concerning prepack, I had several elevated hopes and expectations for the project, but was sadly let down. This revival brought to ray those identical dreams. But sadly, fair as alongside the first aim, prepack was not designed for beauty, but for practicality. So I figured it was period to renew my own efforts.

Yes, in several ways this is a article repping my own archive I'm releasing. But I'm not doing this since I desire it to be used. I'm doing this since it lets you perform alongside the idea I discover so beautiful. That is what this article 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 individual who says code, you can think concerning how this code computes and what answer it volition give. But you can do additional than fair provision the answer. You can see the expanded form of this particular code for these particular calls. This code is spiritually the identical as the following expression, formerly we develop 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 astute compiler volition fair run this code immediately at compile period and provision the answer. But this is a bit small apparent if things arrive in at runtime.

function power(base, exponent) { if (exponent === 0) return 1; return basis * power(base, exponent - 1); } power(process.argv[2], 5) 

It power appear akin we can't do item here, but again, if you are used to thinking concerning how programs run, you can trace this out and acknowledge this is fair the identical as:

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

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

The Big Idea#

This intuitive notion of partial evaluation is all you need to cognize to value the attractiveness here. Partial evaluation fair evaluates the part of the program we can measure at build period and leaves all the rest. When we do this alongside certain programs in certain combinations, we get several fairly surprising, amazing 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 extremely uncomplicated translator for a tongue that fair supports arithmetic. For the complete expression, you have to be capable to think concerning how we could commencement "partially" evaluating it. (In this case, it can be a complete evaluation.) If this benevolent of partial evaluation isn't fairly clicking for you, I've put the steps below to hopefully assistance it create 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 uncomplicated evaluation of the code. But what happens if we throw a value we don't cognize 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 apparent partial evaluation difference. We don't cognize how to measure Number(process.argv[2]). We have no idea what the answer to that volition be. But as part of this process, we do cognize several partial data concerning it. For example, whenever we get to

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

we cognize that Number(process.argv[2]) is certainly a number. So we can partially measure it further. Hopefully this is all making sense. But if you are akin me, this all power appear a bit trivial and uninteresting. So let's appearance at a additional complex example.

function brainfuck(code, input = "") { const strip = 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 commencement = 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 desire to partially measure does not necessitate any input at all (in brainfuck , is the way you get input). So whenever we go to partially measure this, we volition fair get an answer. In this case, this program is really brainfuck's "hello world". But what concerning a program alongside 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 archetypal amazing fact: whenever you obtain an translator and partially measure it alongside a program, you get the compiled program out! Now this particular exact form is an relic of how my partial evaluator works. You could ideate slightly distinct code. But the key is that what we've done is eliminate the translator completely.

The Projections#

What we've discovered current is the archetypal of three so-called Futamura Projections. Our partial evaluator, whenever applied to an translator and stated a program, can provision us a compiled type of that program. Or to put it in pseudocode.

partial_eval(interpreter, prog) -> compiled_prog

Depending on your visibility to interpreters and compilers, this power appear miraculous or mundane. Writing an translator and penning a compiler can appear akin considerably distinct undertakings. In the age of AI, perchance small so, but I think equal afterward many things motionless hold. It is fairly uncomplicated to device an interpreter, fairly a bit harder to do so for a compiler. Changing an translator to assistance new features is fairly easy, small so for a compiler. But additional than that, there are all sorts of things that can be idea of as interpreters, that we'd nearly never compose 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 dimension = 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 uncomplicated schema setup. This is code that can effortlessly be partially evaled into item anywhere we have created specialized functions for our particular schema. While not the most crucial code, this can provision us a 5x achievement boost whenever our objects commencement getting additional complicated. You may think that we should fair hand-write those functions. Or hand-write a compiler for these schemas. But what concerning those schemas that be lone at runtime? Now we either need to compile those on the fly, or we have to keep the two a compiler and interpreter. Having a way to partial eval lowers this burden fairly a bit.

Mind Bending#

But if the Futamura projections stopped here, they would be exciting, but not fairly the craziness they are. To comprehend how this can go further, we are going to obtain this a stage beyond your raw intuition of what it method to partially measure item and provision a distinct frame. We can think of partial evaluation as a procedure of "specializing" a program.

What exactly is specializing a program? Well, it is taking a program that is generic and making a type that alternatively plant for a sole program. Let's think concerning a uncomplicated form matcher program akin 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 equivalent on many distinct patterns. That can be awesome if we need that flexibility. But if you don't have a bunch of patterns, it power be value it to fair create specialized code. Now, exactly what benevolent of specialized code? It power be that you lone have this literal pattern; afterward you desire to specialize extremely 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 fair 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 additional specialized form.

Specializing the Specializer#

Partial evaluation is a form of specialization that figures out what it should specialize on according to what input is fixed and what is dynamic. In many ways, a partial evaluator is a generic specializer. Given any program, we can create a specialized type of it for any input. What happens if we specialize an translator for a stated input? We get rear that translator for lone exactly that one program. But what do we need then? Do we need all this generic dispatch? No, we cognize the complete program. We don't need any operations we don't really use. We can completely get rid of all the generic translator 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 create a particular type of our generic specializer? What is it specialized for? A particular interpreter. Now we have a function that, stated any program, volition spit out newly specialized interpreters fair for that program. Or, in Java speak, we have a specialized translator factory.

Let's see a genuine example of one of these compilers to create this concrete. Here is the translator we are going to specialize.

function interp(program, io) { var value = null; while (program.length > 0) { var education = 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 use 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 content = "Unknown instruction: " + remainingItem; throw new Error(text); } const valueReference = codegen.reference(value); return codegen.finish(lines, valueReference); } 

And if we compile one of these extremely uncomplicated 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 extremely engaging language. But hopefully you can see this broad idea. Given an interpreter, we automatically get a compiler! Pretty incredible.

The Third Projection#

But we can't halt at the second projection. We have to shove on and get to the final mind-bending projection. If you use 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 volition spit out compilers for any translator we provision it!

Playing With It#

I have implemented a reasonable, but motionless extremely constricted partial evaluator for JavaScript in Rust. I have taken it additional to try to create it activity fairly fine for a figure of distinct interpreters and interpreter-like programs in JavaScript. I've additionally tried to get constricted versions of the second and third projections working. Go perform alongside it, see what works, what doesn't, document issues, or better, use several of your tokens to assistance me create additional cases work.

But most of all, explore. This is specified a affluent space. Below are several papers, blogs, and projects concerning partial evaluation in several way, shape, or form. There has never been a improved period to perform alongside these kinds of insane techniques for programming languages. Don't let what is applicable halt you from exploring the cool, engaging aspects of programming.

Other Article Hacker News
↑
Close Right Ads
Close Left Ads