Write your name in the top right-hand corner of this page. There are 90 points total. You have the entire class period for this exam. Show your work to receive partial credit. If you use any procedure that is not in standard Scheme, define it (in any blank space that seems large enough). Check your work carefully!
(let ((alpha 1)
(beta 1)
(n 0))
(let ((foo (delta (beta n)
(if (equal alpha 2)
n
(bar (* 2 alpha) (+ n 1))))))
(letrec ((bar (lambda (alpha n)
(if (equal beta 2)
n
(foo (* 2 beta) (+ n 10))))))
(cons (foo alpha n) (bar beta n)))))
Answer: (11 . 21)
(let ((x 1) (y 2))
(let ((set!x (lambda (val) (set! x val)))
(set!y (lambda (val) (set! y val))))
(let ((x 3))
(set!x 4)
(set! y 5)
(set!y 6)
(list x y))))
Answer: (3 6)
((lambda (x)
(* (let ((x 3))
(add1 x))
x))
2)
Answer: 8
((lambda (a d)
((lambda ()
((lambda (b c d)
((lambda (a c)
(d b c a))
d e))
a b d))))
a d)
Answer:
((lambda (a d)
((lambda ()
((lambda (b c d)
((lambda (a c)
((d : 1 2) (b : 1 0) (c : 0 1) (a : 0 0)))
(d : 0 2)
(e : free)))
(a : 1 0)
(b : free)
(d : 1 1)))))
(a : free)
(d : free))
let to an application of a lambda
procedure:
Now consider a new interpreter that expands(let ((var1 exp1) ... (varn expn)) body) ==> ((lambda (var1 ... varn) body) exp1 ... expn)
let
to an application of a delta procedure:
Invent a program that is as small as possible and gives a different answer for each of these expansions. Or argue that such a program can not be defined (i.e., both expansions are equivalent).(let ((var1 exp1) ... (varn expn)) body) ==> ((delta (var1 ... varn) body) exp1 ... expn)
Answer:
A lambdaprocedure gets its environment at
procedure creation time. A deltaprocedure
gets its environment at procedure call time. In a
let expression, the environment at procedure
creation is the same as the environment at procedure call,
making both expansions equivalent.
45 points. EOPL. Exercise 5.5.7.
The following interpreter creates cells for all variables, not
only for mutable variables. Modify the interpreter so that
the letmutable form is just the same as the
let form, except that it introduces mutable
bindings to the environment, whereas let (and
lambda) bindings remain immutable.
Variable assignment works only when the variable to be assigned to has a mutable binding. You should raise an error if the binding is immutable.
The initial environment should have only immutable bindings
(i.e. don't create cells for them). letmutable
should be a core form (i.e., you should include it in
eval-exp). Assume the expander has been modified
appropriately.
Answer: Changes are marked with strong.
(define make-closure
(lambda (formals body env)
(lambda args
(eval-exp body (extend-env formals
args ; was: (map expressed->denoted args)
env)))))
(define init-env
(extend-env
*prim-op-names*
*prim-op-procs* ; was: (map expressed->denoted *prim-op-procs*)
the-empty-env))
(define eval-exp
(lambda (exp env)
(if (variable? exp)
(let ([value (apply-env env exp)])
(if (denoted-value? value)
(denoted->expressed value)
value))
(record-case exp
(quote (datum) datum)
(lambda (formals body)
(make-closure formals body env))
(letmutable (decls body)
(let ([vars (map decl->var decls)]
[exps (map decl->exp decls)])
(eval-exp body
(extend-env vars
(map (lambda (exp) (expressed->denoted (eval-exp exp env)))
exps)
env))))
(if (test-exp then-exp else-exp)
(if (true-value? (eval-exp test-exp env))
(eval-exp then-exp env)
(eval-exp else-exp env)))
(set! (var exp)
(let ([binding (apply-env env var)])
(if (denoted-value? binding)
(denoted-set! binding (eval-exp exp env))
(error 'eval-exp "trying to change an immutable variable: ~s" var))))
(begin (exp1 exp2)
(eval-exp exp1 env)
(eval-exp exp2 env))
(else
(let ((proc (eval-exp (app->rator exp) env))
(args (eval-rands (app->rands exp) env)))
(apply-proc proc args)))))))