McMaster University
Programming Languages

CAS 706 — Fall 2010

Assignment 2

Implement interpreters for untyped λ-calculus in four different programming languages:

The following abstract grammar for untyped λ-expressions should be used:
var ::= letter ( letter | _ | digit | ' )*
term ::= var                                     -- Variable
       | term term                               -- Application
       | \ var -> term                           -- Abstraction

Implement at least two different reduction strategies (see also Wikipedia: Evaluation strategies).

For concrete syntax, follow the Haskell conventions: application is denoted by juxtapositions and associates to the left; the scope of abstraction extends as far as possible. You need to be able to generate this syntax from your implementation for output of reduction results.

For Haskell, parsing is not yet expected; you may instead rely on GHCi and provide the following interface to your implementation of the type Term of λ-expressions:

var    :: String         -> Term     -- Variable
(@@)   :: Term   -> Term -> Term     -- Application
lambda :: String -> Term -> Term     -- Abstraction
This will allow me to test your implementation in GHCi by typing, for example (assuming you provide a function normalise):
let x = var "x"
let y = var "y"
let delta = lambda "x" $ x @@ x
normalise $ lambda "x" (lambda "y" y) @@ (delta @@ delta)

Deliverables

Literature: Barendregt, Barendsen 2000: Introduction to Lambda Calculus