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!!
Best wishes for a successful outcome for that work.
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.
Sounds great. Do you anticipate making using of John Hughes' work on partial evaluation using type inference http://www.cs.chalmers.se/~rjmh/TypedPE/revision.ps or is there something more recent and relevant to your endeavour?