Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 2 - Spring 2000 - Michael Elhadad

Lambda Calculus

Problems for 27 Mar 2000

  1. Gen-exp
  2. beta-reduce
  3. eta-reduce
  4. depth-first-search
  5. reduce-once-leftmost
  6. syntax-expand


Given the following BNF:
<exp> ::= <varref>
      |   (lambda (<var>) <exp>)
      |   (<exp> <exp>)
We define the function length inductively as follows:
length(<varref>) = 1
length((lambda (<var>) <body>)) = 1 + length(<body>)
length((<exp1> <exp2>)) = 1 + length(<exp1>) + length(<exp2>)
Define (gen-exp n) that returns all the expression such that (length <exp>) = n. For example:
(gen-exp 1) -> (v)
(gen-exp 2) -> ((lambda (v) v))
(gen-exp 3) -> ( (v v) (lambda (v)(lambda (v) v)) )
Define the function (gen-combinators n) that returns all the combinators of length n. A combinator is a lambda expression that contains no free variables. Bound variables can be called v1, v2... Use the function (make-var i) to generate the symbol vi.

Make sure that if two combinators are equivalent in terms of variable renaming then only one is returned by the function.


(beta-reduce exp) return the beta-reduction of parsed exp.


(eta-reduce exp) return the eta-reduction of a parsed exp.


(depth-first-search pred? binary-tree) Do a depth first search of the binary-tree and output the first item that satisfies pred? if found, #f otherwise. Use the success-failure continuation technique discussed on p.112. Describe first the BNF for your binary tree.


(reduce-once-leftmost exp) Modify the reduce-once code shown in class for applicative-order evaluation to obtain a procedure reduce-once-leftmost that implements one step of leftmost reduction. This strategy always reduces the first beta-redex whose left-parenthesis comes first. Note that leftmost order does reduce expressions in the body of lambda abstractions.


(syntax-expand syntax-tree) where syntax-tree is a parsed expression for the following BNF:
<exp>         ::= <varref>                  varref (var)
               |  <number>                  lit (datum)
               |  (if <exp> <exp> <exp>)    if (test-exp then-exp else-exp)
               |  (proc ({<var>}*) <exp>)   proc (formals body)
               |  (<exp> {<exp>}*)          app (rator rands)
               |  (:= <var> <exp>)          varassign (var exp)
               |  (begin {<exp>}+)          begin (exps)
               |  (let <decls> <exp>)       let (decls body)
               |  (letrec <decls> <exp>)    letrec (decls body)
<decls> ::= ({<decl>}*)
<decl>  ::= (<var> <exp>)                   decl (var exp)
This is a Lisp form of the syntax of the language studied in the text book. syntax-expand must return a new syntax tree, with every let and letrec records replaced by a semantically equivalent app record.
Last modified 14 Mar 2000
Michael Elhadad