[Haskell-cafe] Currying and Partial Evaluation

[Jules Bean]

Fernando Rodriguez wrote:
> 
> Hi,
> 
> Is currying in Haskell the same thing as Partial Evaluation 
> (http://en.wikipedia.org/wiki/Partial_evaluation)? Am I getting partial 
> evaluation for free just by using Haskell?
> Thanks!

I'm not sure you got a straight answer, although you provoked some 
discussion.

Currying is the transformation which takes a function which takes 
multiple parameters "all at once", into a function which takes one 
parameter, returning a function which takes one more parameter, 
returning....

I.e.:

uncurried function:

f :: (a,b,c,d) -> e

takes four parameters "all at once". In haskell it has to take them as a 
tuple.

The corresponding curried function:

f :: a -> b -> c -> d -> e

Takes one parameter (of type a), and returns a function of type (b -> c 
-> d ->e). This takes one parameter of type b, and returns a function of 
type (c -> d -> e). This takes one parameter of type c and returns a 
function of type (d -> e). This takes one parameter of type d and 
returns a result of type e.

So, in the end, both forms of f take four parameters and give a result 
of type e. The difference is that the curried form takes them "one at a 
time", and you can "stop partway" with only some of the parameters supplied.

This process of "stopping partway" is called "partial application" (not 
partial evaluation), and it's a useful technique when working with 
higher-order functions.

Convention in haskell, ML, and similar languages is to use the curried 
style predominantly. This is for a variety of reasons; the most 
practically oriented reason is simply that it makes partial application 
straightforward, which is a useful technique.

Now for the second half of your question!

Partial Evaluation is cool, but nobody has worked out a good way to get 
it for free. Some compilers do some kinds of partial evaluation. The 
"constant folding" that most C compilers do is a very simple case of 
partial evaluation.

In principle, languages like haskell give the compiler a lot more 
information to determine how much partial evaluation is feasible 
(especially that the compiler knows which functions are pure). It 
remains an interesting engineering problem working out which bits to do, 
though. GHC does not do very much partial evaluation, although some of 
its optimisations (SpecConstr and some RULES pragmas) are 
partial-evaluation in a sense.

Neil Mitchell's interesting (but as far as I know, work-in-progress) 
Supero project, http://www-users.cs.york.ac.uk/~ndm/supero/ , is a 
closely related notion of compilation.

Jules