Specialising a Lambda-Interpreter

In this exercise you will specialise an interpreter for the lambda-calculus, with the aim of achieving optimal specialisation. You will need to both annotate and modify the interpreter to achieve this. Take the following interpreter as your starting point:

module Lam where

data E = Con Int | Var String | Ap E E | Lam String E
data V = Num Int | Clos String E [(String,V)]

eval e env =
  case e of
    Con n -> Num n
    Var s -> look s env
    Ap e1 e2 -> apply (eval e1 env) (eval e2 env)
    Lam x e1 -> Clos x e1 env

apply f v =
  case f of
    Clos x e env -> eval e ((x,v):env)

look x env =
  case env of
    nv:env' ->
      case nv of
        (n,v) -> if x==n then v else look x env'

You may find it helpful to place the following initial call in a file:

eval (Lam "f" (Lam "x" (Ap (Var "f") (Ap (Var "f") (Var "x"))))) []

Check that you can specialise the interpreter to this term. Since nothing is annotated as static, you should see no useful specialisation at this stage.

Now improve the specialisation of the interpreter in the following stages. Each stage involves adding annotations to the interpreter, but some also require rewriting parts of it to make the interpreter `more specialisable'.

Make the expression argument of eval static.
Make the environment partially static, so that identifiers disappear from the residual program.
Unfold the calls of look.
Unfold calls of eval and apply.
Is specialisation now optimal? If not, can you modify the interpreter so that it becomes so? [Hint: the specialiser will actually accept ill-typed programs, if you omit the -btcheck flag.]

Last modified: Mon Sep 29 12:12:41 MET DST 1997