effective partial evaluator yet?

[Duncan Coutts]

On Thu, 2004-07-15 at 03:45, John Sharley wrote:
> Noting Hudak's remark in the conclusion of "Modular Domain Specific
> Languages and Tools"
> http://www.cs.chalmers.se/Cs/Grundutb/Kurser/afp/Papers/dsel-hudak.ps
> that Haskell lacked an effective partial evaluator, and remarks prior to but
> on the same page as the conclusion that such a thing is very important for
> DSELs, is there an effective partial evaluator for Haskell yet?

If there is, I'd be interested to hear as building an effective partial
evaluator for Haskell will hopefully form a major part of my PhD!!

> If not, what are the prospects (both theoretical and practical) for having
> an effective partial evaluator for Haskell and GHC in particular?

There are theoretical issues with types, multiple levels of encoding
(which leads to poor performance) and specialising programs that
manipulate higher order data.

My current prototype uses GHC and Template Haskell. It can only
specialise functions that manipulate first order values. It does work
for a number of simple examples eg Ackerman function (specialised on
first argument), matrix multiplication (specialising on fixed size
matrices), a simple language interpreter (specialised to a fixed input
program).

A very basic partial evaluator is surprisingly simple to implement but
it is rather hard to use since you have to explicitly annotate
everything with binding times (static/dynamic) and the error message
when you get it wrong are horrible.

My aim is to have a partial evaluator that works for full Haskell
(including higher-order values), including semi-automatic / user
assisted binding time inference. The plan is then to apply that to
active libraries like DSELs.

Duncan