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

Syntactic Abstraction - Lambda Calculus

Problems for Tue 05/01/98



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 used in the reduce-once example. 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.
Last modified Dec 27th, 1998
Michael Elhadad