The Mini-Haskell Partial Evaluator

I am providing you with a (toy) partial evaluator for a small subset of Haskell. If you are at Chalmers, you will find it in ~rjmh/NewPE/PE; make a directory for your exercises and insert a link to this program. This version is compiled for SPARC machines; if you are using a PC then copy all Haskell source files from that directory and compile them using

hbcmake PE

If you are elsewhere, you will need to download and compile the sources (30K). The binding-time checker (BT.hs) is quite a large module, and you will need to give hbc a larger heap in order to compile it: use hbc -H32M. (The partial evaluator is written in Haskell 1.3, and has been compiled with hbc. Much of it has also been tested under Hugs 1.3.)

The partial evaluator is best invoked by a command of the form

PE M <term

A Haskell module is read from M.hs, and specialised with respect to an initial call in the file term. The output of the partial evaluator is the specialised initial call, followed by the specialised module. Two flags are recognised:

-btcheck invokes a binding-time checker before specialisation. This is highly recommended!
-unfoldlets invokes a post-processor that unfolds trivial lets, that is, those that bind a variable to another variable. However, the `right' way to unfold lets, if that's what you want to do, is to annotate the source program that they are unfolded during partial evaluation. If you rely on the post-processor instead, then as soon as a non-trivial let appears in a residual program, it will not be unfolded.

Note that programs compiled by hbc interpret the first flags as flags to the run-time system; `user program' flags such as the two above must be preceded by an empty flag, for example:

PE - -btcheck M <term

The Haskell subset includes:

Integer, boolean, and string constants.
Pairs.
Lists (but not list comprehensions or arithmetic sequences; strings are not lists).
Primitive operations: || && == /= < <= >= > : ++ + = * div . (++ is restricted to String only; you will need to define append yourself to concatenate lists).
Conditional expressions.
Lambda expressions and applications.
Datatype definitions, constructors and case expressions. The patterns in a case must be simple, that is a constructor applied to variables. Pattern matching may only be used in a case expression. Pattern matching on lists and pairs is supported.
Do notation.
Definition by a single equation.
Imports.

Binding times are explicitly provided via annotations. In general, static operations are indicated by a '$':

$2, $True, $"x" are a static integer, boolean and string.
lift x converts a static integer or string x into a dynamic one.
x$+y and x$==$0 are static primitive operations.
(x$,y) is a static pair.
$[x,y,z] and x$:xs are static lists.
\$x $y -> x+y is a static lambda expression; f$@x is a static application.
$f is a static reference to a global name f (that will be unfolded by the specializer).
f $x $y z = e defines a function whose first two arguments are bound by static lambdas. Such a function must be unfolded at all call sites; a call might appear as $f $@x $@y z.
$C x y z is a static constructor application, and $case e of C x y z->e' is a corresponding static case expression. Here e must be static, so that the case can be simplified, but the branches of the case need not be.
$if x then y else z is a static conditional, which will be simplifed to one of the branches by the specialiser. Once again, the branches need not be static.
$import M is a static import declaration, which instructs the specialiser to read module M.hs and add the definitions it finds there to the code to be specialised.

The partial evaluator supports partially static structures, but note that dynamic functions, constructors and operators must have purely dynamic arguments and results.

If you just want to try the partial evaluator out, you can run it on our web server.

Last modified: Mon Sep 29 14:32:41 MET DST 1997