McMaster University
Programming Languages

CAS 706 — Fall 2010

Assignment 2

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

• Haskell
• Java or C++
• Python
• a language of your choice that is new to you.

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

let x = var "x"
let y = var "y"
let delta = lambda "x" $ x @@ x
normalise $ lambda "x" (lambda "y" y) @@ (delta @@ delta)

Deliverables

• For each programming language, produce a well-documented (preferably literate) program, and accompany this with compilation instructions if these are non-trivial, and with test cases, including both terminating and non-terminating derivations.

  Submit the program source electronically. and a printout of the documented program on paper (2-up is preferred for programs of more than 2 pages).

• Strive to write natural programs in each language, and document where different languages force/enable/invite you to do things differently.

Literature: Barendregt, Barendsen 2000: Introduction to Lambda Calculus