Partial Evaluation (aka Specialization)
Posted: May 9, 2006 12:46 AM
Things are more interesting when only part of the input is known. A partial evaluator will accept a function and a constrained domain (D) and return an optimized version of the function that only accepts values in D.
For example, if you have:
multiply :: (int, int) -> int
multiply(x, y) = x * y
You could do:
multiply_2 :: int -> int
multiply_2 = specialize(multiply, x = 2)
A smart partial evaluator would convert the operation into a bit shift.
An impressive use of partial evaluation is to automatically convert an interpreter into a JIT compiler. An interpreter is essentially:
run :: (program, input_handle) -> output
If the entirety of "program" is known ahead of time, it can be specialized for a given program, yielding:
run_myprog :: input_handle -> output
run_myprog = specialize(run, program = myprog)
"Tempo" is a non-toy partial evaluator for C.