Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 1 - Fall 1998 - Michael Elhadad
Problems for Tue 22/12/98
NOTE: The recommended platform to develop this assignment is SCM.
There is a nicer more user-friendly implementation as DrScheme, but it
requires more resources, and for this assignment, that does not seem
necessary.
To load the code supporting define-record and
variant-case in SCM, evaluate: (require 'struct).
In question 1, make sure you derive your function from the BNF
specification of lists, s-lists and binary-search-trees. That is, use the
BNF as a definition of the set of legal expressions that are lists, s-lists
and binary-search-trees respectively. Your code must be "syntax-directed"
in the sense that it can "walk down" any legal-expression of these types,
as defined by the following BNFs:
<list> ::= ({<expr>}*)
<s-list> ::= ({<s-expr>}*)
<s-expr> ::= <symbol> | <s-list>
<bin-search-tree> ::= () | (<number> <bin-search-tree> <bin-search-tree>)
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:
path,
car-cdr,
car-cdr2
(Exercise 2.2.9 - 1, 2, 3 p.55)
lexical-address
(Exercise 2.3.10 p.62 and 3.4.6 p.87)
un-lexical-address
(Exercise 2.3.13 p.63)
rename
(Exercise 2.3.14 p.65)
alpha-convert
(Exercise 2.3.15 p.65)
substitute
(Exercise 4.2.3 p.107)
beta-reduce
(Exercise 4.2.4 p.107)
eta-reduce
(Exercise 4.2.6 p.108)
depth-first-search
reduce-history
(Exercise 4.3.1 p.112)
reduce-once-leftmost
(Exercise 4.3.5 p.115)
path
(path n bin-search-tree)
where n is a number and bin-search-tree is a
binary search tree that contains the number n, returns a
list of Ls and Rs showing how to find the node containing n.
If n is found at the root, it returns the empty list.
> (path 17 '(14 (7 () (12 () ()))
(26 (20 (17 () ())
())
(31 () ()))))
(R L L)
car-cdr
(car-cdr s slst errvalue)
returns an expression that, when evaluated, produces the code for a
procedure that takes a list with the same structure a slst
and returns the value in the same position as the leftmost occurrence
of s in slst. If s does not
occur in slst, then errvalue is returned.
> (car-cdr 'a '(a b c) 'fail)
(lambda (slst) (car slst))
> (car-cdr 'c '(a b c) 'fail)
(lambda (slst) (car (cdr (cdr slst))))
> (car-cdr 'dog '(cat lion (fish dog) pig) 'fail)
(lambda (slst) (car (cdr (car (cdr (cdr slst))))))
> (car-cdr 'a '(b c) 'fail)
fail
car-cdr2
(car-cdr2 s slst errvalue)
like car-cdr but generates procedure compositions.
> (car-cdr 'a '(a b c) 'fail)
car
> (car-cdr 'c '(a b c) 'fail)
(compose car (compose cdr cdr))
> (car-cdr 'dog '(cat lion (fish dog) pig) 'fail)
(compose car (compose cdr (compose car (compose cdr cdr))))
> (car-cdr 'a '(b c) 'fail)
fail
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. (There is no
search here, you can assume e is a beta-redex.)
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-history
(reduce-history unparsed-exp n)
The function reduce-history takes an unparsed lambda calculus expression
unparsed-exp and a positive integer n, and returns a list of unparsed
expressions indicating a (perhaps incomplete) reduction history of exp.
The last element in the list is the answer, or the result of the nth
reduction if the answer cannot be obtained in n reductions. For example:
% (reduce-history '((lambda (x) (x ((lambda (x) y) z))) w) 5)
((w ((lambda (x) y) z))
(w y))
% (reduce-history '((lambda (x) (x x)) (lambda (x) (x x))) 3)
(((lambda (x) (x x)) (lambda (x) (x x)))
((lambda (x) (x x)) (lambda (x) (x x)))
((lambda (x) (x x)) (lambda (x) (x x))))
reduce-once-leftmost
(reduce-once-leftmost exp succeed fail)
Modify reduce-once-app to obtain a procedure reduce-once-leftmost that
implements one step of leftmost reduction.
Last modified Nov 18th, 1997
Michael Elhadad