A Simple Partial Evaluator

The object of this exercise is to write a simple polyvariant partial evaluator, which although not self-applicable can be specialised by the Mini-Haskell partial evaluator to construct generating extensions.

I have designed a simple programming language for you to specialise, just powerful enough to express the power function! It is purposefully designed to make specialisation easy. Expressions in this language are represented by the type

data E = Con Int | Lift E |
         Prim String E E |
         If Bool E E E |
         Call Bool String [E] [E] | Var String

representing integer constants, a lift operator to convert static integers to dynamic ones, applications of binary operators (+, -, *, ==), conditional expressions, function calls, and local variables. Functions are defined at the top level of a program, which is just a list of definitions; local variables can refer only to function parameters. The only datatypes that programs in this language can manipulate are integers and strings. You need not therefore be concerned with partially static structures: every value is either completely static or dynamic. Conditional expressions and function calls carry (boolean) binding time annotations: if the boolean is True then the conditional should be simplified, or the function call unfolded. Notice that function calls carry two lists of parameters: the first is the list of static parameters, and the second is the list of dynamic ones.

A function definition is a nested tuple with the following structure:

(name,(sps,(dps,body)))

where

name is the name of the function being defined,
sps is a list of the names of the static formal parameters,
dps is a list of the names of the dynamic formal parameters,
body is the function body, an expression.

For example, the program defining the power function, with the first argument static, is:

test = [("power",
          (["n"],
	    (["x"],
	      (If True
	         (Prim "==" (Var "n") (Con 0))
		 (Con 1)
		 (Prim "*" (Var "x")
		   (Call False "power"
		     [Prim "-" (Var "n") (Con 1)]
		     [Var "x"]))))))]

This language has the property that we can determine from the context of an expression, in advance, whether its result should be static or dynamic. For example, the body of a specialised function should be dynamic, the argument of lift should be static, the branches of a conditional should have the same binding-time as the conditional itself. Thanks to this property, it isn't necessary to attach binding-time annotations to constants and applications of primitives: they are static in a static context, and dynamic in a dynamic one.

Because we always know whether an expression should be static or dynamic, we can define separate functions for specialising static and dynamic expressions. Begin by defining a function for evaluating static expressions:

eval prog expr env

should take a program (list of definitions), expression, and environment, and return a static value with the type

data V = Num Int | Bool Bool

You can simplify eval somewhat by assuming that the expression to be evaluated is a correct static expression:

Only static variables can occur, so the env parameter need only contain bindings for static variables,
Lift e cannot occur,
conditionals can only be annotated True (simplifiable),
function calls can only be annotated True (unfoldable),
function calls must have no dynamic parameters.

I suggest you use hugs to test your program.

Once eval is working, define a function to specialise dynamic expressions:

code prog expr senv denv

taking the program, expression to specialise, and two environments. Since we always know whether an occurrence of a variable should be static or dynamic, we can keep the bindings of static parameters and of dynamic parameters in two different environments. Whenever we reach a variable occurrence, we will know which environment it should be bound in.

The result of code should be a specialised expression of type E, but there is a complication. As we construct the specialised expression, we may encounter residual calls to other specialised functions. We need to determine which name should be used for that specialisation, and if it has not already been generated then we need to add it to a `pending list' of specialisations to be done in the future. A convenient way to express this `house-keeping' is via a monad, and I have defined one for you. Write code in terms of Haskell's do and return notation (do not use >>= explicitly), and when you encounter a residual call use the

name'<-specialise name args body

operation of the monad. Here:

name is the name of the function whose specialisation you are generating, for example "power".
args is a value which distinguishes different specialisations of the same function, for example a list of values of the static parameters.
name' is the generated name for the specialised function, for example "power_3". The same generated name is always returned for a particular name/args combination.
body is a monadic computation which constructs the specialised definition of name'. The first time a particular name/args combination appears, this computation is added to the pending list. Thus the specialised definition of name' will be constructed only once, no matter how many times that specialisation is referred to. Naturally, all calls of specialise with the same name and args ought to provide the same body also.

I am providing you with a module which defines this monad, and also a function run, which maps a monadic value into a pair of the value returned, and a list of specialised definitions. Each definition is represented by a pair of the generated name, and the value that the body parameter of specialise delivers. You can therefore test your specialiser by a call such as

run (code test (Call False "power" [Con 3] [Con 4]) [] [])

Once your specialiser is working, try to specialise it to test to construct a generating extension for the power function. As usual, the prog and expr arguments of code should be static, while the environment arguments should be partially static. A suitable initial call to specialise might be

code $test ($Call $False $"power" $[$Con $3] $[$Con $4]) $[] $[]

Observe how changes in the annotation of the definition of power are reflected in its generating extension.

Last modified: Tue Sep 23 19:34:32 MEST 1997