Lambda calculus is a language of expressions described by the following grammar,
<E> ::= <N> | <V> | (lambda (<V>*) <E>) | (<E> <E>*)
where <N> stands for a numeric
constant, and <V> stands for a
variable name (a symbol). In other words, an expression
is one of the following: a number, a variable, an
application of an expression to several other
expressions, or a lambda expression. A lambda
expression introduces new variables that are visible in
its body. Here is a sample expression that we are going
to use as a test case throughout this assignment.
(lambda (car cdr null? cons)
(lambda (append)
(lambda (ls1 ls2)
((null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2))))))
To make our job easier when working with expressions,
let's devise a procedure that will convert expressions
from their representations as lists into corresponding
record representations. That will enable us to use variant-case
to dispatch control over different types of expressions.
We will use the following records:
(define-record num (val)) (define-record varref (var)) (define-record lambda (formals body)) (define-record app (operator operands))
Here, the record with tag num represents
a numeric constant, and val is the value of
the constant. The record with tag varref
represents a variable occurence, and var is
the variable name (a symbol.) The lambda
record represents a lambda expression where formals
is a list of parameters introduced by this lambda
expression, and body is the representation
of the expression that is the body of the lambda
expression. Finally, the app record
represents applications. Field operator
contains the representation of the operator of the
application, and operands is a list of
representations of operands of the application.
For instance, to make a representation for the the
expression (+ 1 2), the following command
has to be run.
(make-app (make-varref '+) (list (make-num 1) (make-num 2)))
To construct a record representation of the sample expression shown above, we can run the following set of commands
(make-lambda
'(car cdr null? cons)
(make-lambda
'(append)
(make-lambda
'(ls1 ls2)
(make-app
(make-app (make-varref 'null?) (list (make-varref 'ls1)))
(list (make-varref 'ls2)
(make-app
(make-varref 'cons)
(list (make-app
(make-varref 'car)
(list (make-varref 'ls1)))
(make-app
(make-varref 'append)
(list (make-app
(make-varref 'cdr)
(list (make-varref 'ls1)))
(make-varref 'ls2))))))))))
recordify that takes an
expression and parses it to produce a record
representation. It should call the system procedure error
if the input expression is not in the format defined by
the BNF grammar above. Here, we provide the skeleton of recordify;
your job is to fill in the ... blanks.
(define recordify
(lambda (exp)
(cond
((number? exp) (make-num exp))
((symbol? exp) (make-varref exp))
((atom? exp) (error 'recordify "illegal expression ~s" exp))
((eq? (car exp) 'lambda) ...)
(else ...))))
Here are some test cases:
> (recordify '(+ 1 2))
#3(app #2(varref +) (#2(num 1) #2(num 2)))
> (recordify '(lambda (car cdr null? cons)
(lambda (append)
(lambda (ls1 ls2)
((null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2)))))))
#3(lambda
(car cdr null? cons)
#3(lambda
(append)
#3(lambda
(ls1 ls2)
#3(app
#3(app #2(varref null?) (#2(varref ls1)))
(#2(varref ls2)
#3(app
#2(varref cons)
(#3(app #2(varref car) (#2(varref ls1)))
#3(app
#2(varref append)
(#3(app #2(varref cdr) (#2(varref ls1)))
#2(varref ls2))))))))))
listify that takes the
representation of an expression and converts it back to
its original form. Here is its skeleton:
(define listify
(lambda (exp)
(variant-case exp
(num (val) val)
(varref (var) var)
(lambda (formals body) ...)
(app (operator operands) ...)
(else (error 'listify "illegeal representation ~s" exp)))))
Here are some test cases:
> (listify #3(app #2(varref +) (#2(num 1) #2(num 2))))
(+ 1 2)
> (listify #3(lambda
(car cdr null? cons)
#3(lambda
(append)
#3(lambda
(ls1 ls2)
#3(app
#3(app #2(varref null?) (#2(varref ls1)))
(#2(varref ls2)
#3(app
#2(varref cons)
(#3(app #2(varref car) (#2(varref
ls1)))
#3(app
#2(varref append)
(#3(app #2(varref cdr)
(#2(varref ls1)))
#2(varref ls2)))))))))))
(lambda (car cdr null? cons)
(lambda (append)
(lambda (ls1 ls2)
((null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2))))))
Now, we will write a procedure that finds free variables in an expression. Free variables are defined inductively on the structure of expression E as follows.
E is a numeric constant, then E
has no free variables; E is a variable reference (E
= x), then E has exactly one
free variable: x; E is an application of the form (E1
E2 ... Ek) and V1, V2, ..., Vk
are lists of the free variables in E1, E2,
... Ek respectively, then the list of E's
free variables is obtained by appending V1,
V2, ..., Vk together. E is a lambda
expression of the form (lambda (v1 ... vk)
B) and V is a list of the
free variables in B, then the list
of E's free variables is obtained by
removing v1, ..., vk from V.
free-vars that takes a
record representation of an expression and returns a list
of the expression's free variables. (You may find
procedures append-all and remove-all
from Assignment 1 useful for this problem.) > (free-vars (recordify '(lambda (x) (x y)))) (y) > (free-vars (recordify '(x y (lambda (z w) (z (lambda (x y) (y w))))))) (x y) > (free-vars (recordify '(x y (lambda (z) (z (lambda (x y) x)))))) (x y) > (free-vars (recordify '(+ 1 2))) (+) > (free-vars (recordify '(lambda (append) (lambda (ls1 ls2) ((null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2))))))) (null? cons car cdr)
convert that takes a
record representation of an expression and returns an
expression that looks just like the original expression
except that all variable occurences are replaced by
lexical addresses of the variables, and lists of
parameters of lambda expressions are replaced by the
number of parameters. A lexical address is a list
containing the marker ":" and 2
integers, where the first integer tells how far from the
current lambda expression the the binder of the variable
is, and the second integer is the position of the
variable in the list of formal parameters of the
corresponding lambda expression. (See p.61 in the text
for the definition of lexical address.) For this
excercise, you might find it useful to use procedures get-depth
and get-offset from Assignment 1. The following fragment should provide a hint on how to write this procedure.
(define convert
(lambda (exp)
(convert-h exp '())))
(define convert-h
(lambda (exp env)
(variant-case exp
(num (val) val)
(varref (var) (list ': (get-depth var env) (get-offset var env)))
(lambda (formals body) ...)
(app (operator operands) ...)
(else (error 'convert "illegeal representation ~s" exp)))))
A test case:
> (convert (recordify '(lambda (+) (+ 1 2))))
(lambda 1 ((: 0 0) 1 2))
> (convert (recordify '(lambda (car cdr null? cons)
(lambda (append)
(lambda (ls1 ls2)
((null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2))))))))
(lambda 4
(lambda 1
(lambda 2
(((: 2 2) (: 0 0))
(: 0 1)
((: 2 3)
((: 2 0) (: 0 0))
((: 1 0) ((: 2 1) (: 0 0)) (: 0 1)))))))
A simple substitution is a pair of a variable v
and a closed expression E. (Recall that a
closed expression is an expression with no free
variables.) To apply a simple substitution to an
expression B is to replace all free
occurences of v in B by E.
subst that takes a
variable v, a closed expression in its
record representation E, and another
expession in its record representation B and
substitutes E for v in B.
> (listify
(subst
'x
(recordify '(lambda (xx) xx))
(recordify '(lambda (x) (lambda (y) (x y z))))))
(lambda (x) (lambda (y) (x y z)))
> (listify
(subst
'y
(recordify '(lambda (yy) yy))
(recordify '(lambda (x) (lambda (y) (x y z))))))
(lambda (x) (lambda (y) (x y z)))
> (listify
(subst
'z
(recordify '(lambda (zz) zz))
(recordify '(lambda (x) (lambda (y) (x y z))))))
(lambda (x) (lambda (y) (x y (lambda (zz) zz))))
Save the definitions of the procedures in a file. Include this file in an e-mail message addressed to c311@cs.indiana.edu with the subject line handin a2. The mail message should contain nothing but the file with the definitions. Make sure that the file is loadable in a Scheme session; otherwise, the grader will not be able to grade the homework.
In a few moments after the message is sent out, you will receive a confirmation of the attempt. It will tell you how many problems the automatic grader thinks you did correctly. The grader runs your definitions on several test cases (which are not necessarily the same as the test cases given in the assignment.) If any of the tests produce an incorrect result, the problem will get no credit.
You have only 5 attempts to submit an assignment, and assignments will not be accepted after the deadline. The submission graded the highest by the grader will be saved. The instructor will go over the saved homework manually. He may decrease or increase the points given by the automatic grader. Do NOT use the automatic grader to test your programs. Make sure you understand the problem and test the program yourself on the appropriate test cases before submitting the assignment.
If you encounter a grader malfunction, e-mail the AI.