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