Advanced Methods in Programming Languages (201-2-4411-01)

## Lambda Calculus

### Problems for 27 Mar 2000

#### gen-exp

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

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

#### eta-reduce

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

#### depth-first-search

`(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

`(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-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.