[Haskell-cafe] Partial Evaluation

[Bryan O'Sullivan]

jim burton wrote:
> I am reading Hudak's paper Modular Domain Specific Languages and Tools 
> [1] and am confused by his use of the term `Partial Evaluation'. I 
> understand it to mean supplying some but not all arguments to a 
> function, e.g. (+3) but it seems to mean something else too.

That's partial application you're thinking of.  In the context of inline 
operators, this is referred to as a section.

Partial evaluation actually executes some of a partially applied 
function, generating a new function that is specialised to the given 
arguments.

Here's a silly, contrived example to illustrate the difference. 
Consider this function:

sumPlus :: Num a => [a] -> a -> a
sumPlus xs y = sum xs + y

Here's a partially applied version of the function:

sumPlus ([3,2] :: [Int])

Its type is

Int -> Int

If you partially evaluate this function, you're evaluating as much of 
the function as possible at "compile time" (usually in a separate 
partial evaluation tool that generates a whole new source file for the 
real compiler), and getting a new specialised function:

sumPlus32 :: Int -> Int
sumPlus32 y = 5 + y

You could expect a decent compiler to apply this kind of transformation 
under limited circumstances, but partial evaluation is much more 
ambitious.  The canonical example is partially evaluating a language 
interpreter by giving it a chunk of source as the input to specialise 
on.  This produces a new interpreter that is specialised to interpret 
exactly that source (aka the first Futamura projection), and which you 
might hope would do so more efficiently than the fully general interpreter.

	<b