[Haskell-cafe] Partial Evaluation

Bryan O'Sullivan bos at serpentine.com
Wed Mar 21 15:08:39 EDT 2007

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 

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.


More information about the Haskell-Cafe mailing list