This is something I was talking about with a coworker today, and I couldn’t quickly find a friendly writeup of it online, so I decided to write my own. (Yes, we do have a lot of people who enjoy conversations like this at foursquare, which is one of the many reasons that it’s such a great place to work. And we are hiring engineers! Feel free to get in touch with me if you’re interested, or just check our website!)<\/p>\n
Anyway – what we were discussing was something called partial evaluation<\/em> (PE). The idea of PE is almost like an eager form of currying. Basically, you have a two parameter function, f(x, y). You know that you’re going to invoke it a bunch of times with the same value of x, but different values of y. So what you want to do is create a new function, fx<\/sub>(y), which evaluates as much as possible<\/em> of f using the known parameter.<\/p>\n It’s often clearer to see it in programmatic form. Since these days, I pretty much live Scala, I’ll use Scala syntax. We can abstractly represent a program as an object which can be run with a list of arguments, and which returns some value as its result.<\/p>\n If that’s a program, then a partial evaluator would be:<\/p>\n What it does is take and program and a partial input, and returns a new<\/em> program, which is the original program, specialized for the partial inputs supplied to the partial evaluator. So, for example, imagine that you have a program like:<\/p>\n This is obviously a stupid program, but it’s good for an example, because it’s so simple. If we’re going to run Here’s where the interesting part comes, where it’s really different from This can be a really useful thing to do. It can turn in to a huge<\/em> But the cool thing that we were talking about is going a bit meta. Suppose that you run a partial evaluator on a programming language interpreter?<\/p>\n We can run our partial evaluator to generate a version of the interpreter that’s specialized for the code that the interpreter is supposed to execute:<\/p>\n So the partial evaluator took a program written in M, and transformed it into a program written in L!<\/p>\n We can go a step further – and generate an M to L compiler. How? By running the partial evaluator on itself<\/em>. That is, run the partial We can go yet another<\/em> step, and turn the partial evaluator into a\ntrait Program {\n def run(inputs: List[String]): String\n}\n<\/pre>\n\nobject PartialEvaluator {\n def specialize(prog: Program, knownInputs: List[String]): Program = {\n ...\n }\n}\n<\/pre>\n\nobject Silly extends Program {\n def run(inputs: List[String]): String = {\n val x: Int = augmentString(inputs[0]).toInt\n val y: Int = augmentString(inputs[0]).toInt\n if (x % 2 == 0) {\n\t (y * y).toString\n } else {\n\t ((y+1)*(y+1)).toString\n }\n }\n}\n<\/pre>\nSilly<\/code> a bunch of times with 1<\/code> as the first parameter, but with different second parameters, then we could generate a specialized version of Silly<\/code>:<\/p>\n\n val sillySpecialOne = PartialEvaluator.specialize(Silly, List(\"1\"))\n<\/pre>\n
\ncurrying. A partial evaluator evaluates<\/em> everything that it
\npossibly can, given the inputs that it’s supplied. So the value produced by the specializer would be:<\/p>\n\nobject Silly_1 extends Program {\n def run(inputs: List[String]): String = {\n val y: Int = augmentString(inputs[0]).toInt\n ((y+1)*(y+1)).toString\n }\n}\n<\/pre>\n
\noptimization. (Which is, of course, why people are interested in it.) In compiler terms, it’s sort of like an uber-advanced form of constant propagation. <\/p>\n\nobject MyInterpreter extends Program {\n def run(inputs: List[String]): String = {\n val code = inputs[0]\n val inputsToCode = inputs.tail\n interpretProgram(code, inputsToCode)\n }\n\n def interpretProgram(code: String, inputs: List[String]): String = {\n ...\n }\n}\n<\/pre>\n\n
\n written in M that we want to interpret:
\n PartialEvaluator.specialize(M_Interpreter, M_Code)<\/code>.\n\t<\/li>\n
\nevaluator like this: PartialEvaluator.specialize(PartialEvaluator, M_Interpreter)<\/code>. The result is a program which takes an M program as
\ninput, and generates an L program: that is, it’s an M to L compiler!<\/p>\n
\n\tcompiler generator: PartialEvaluator(PartialEvaluator,
\n\t\t List(source(PartialEvalutor)))<\/code>. What we get is a program which takes an interpreter written in L, and generates a compiler from it. <\/p>\n