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)
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.
Last modified Dec 13th, 1998
Michael Elhadad