Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 2 - Fall 1996 - Michael Elhadad
Problems for Sun 17/11/96
NOTE: To load the code supporting define-record and
variant-case in SCM, evaluate: (require 'struct).
Syntax of the Lambda Calculus
<exp> ::= <varref> varref (var)
| <number> lit (datum)
| (if <exp> <exp> <exp>) if (test-exp then-exp else-exp)
| (lambda ({<var>}*) <exp>) lambda (formals body)
| (<exp> {<exp>}*) app (rator rands)
From the textbook:
lexical-address
(lexical-address exp)
where pred is an unparsed lambda-calculus expression,
returns the lambda expression with all varrefs replaced by their lexical
address.
un-lexical-address
(un-lexical-address exp)
does the inverse of the previous exercise.
rename
(rename exp var1 var2)
returns exp[var1/var2] if var1 does not occur free in exp and #f otherwise.
alpha-convert
(alpha-convert e v)
takes a lambda expression e of the form (lambda (var) exp) and a variable
v and returns (lambda (v) exp[v/var]), or #f if v occurs free in exp.
substitute
(substitute e m x)
return e[m/x]. Use gensym when alpha-conversion is required.
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.
Last modified Nov 3rd, 1996
Michael Elhadad