CSSE 304 Day 25 Add letrec to the interpreted language
Reminder: Submit your interesting test cases to the interpreter-project folder on Piazza.
A little more CPS
• From the Day 24 slides and handout.
1
Add letrec to the interpreted language
• Limited version of letrec
– One that’s like the way letrec SHOULD always be used.
– (letrec ([var
– could be parsed into
[letrec-exp
(proc-names (list-of symbol?))
(idss (list-of (list-of symbol?)))
(bodiess (list-of (list-of expression?)))
(letrec-bodies (list-of expression?)]
This is one possible way of parsing it. 0thers are also acceptable.
Example of a [letrec-exp
(proc-names (list-of symbol?))
parsed letrec expression
This is one possible way of parsing it. 0thers are also acceptable.
Parsed form of the blue code:
(letrec-exp
(odd? even?)
(idss (list-of (list-of symbol?)))
(bodiess (list-of (list-of expression?)))
(letrec-bodies (list-of expression?))]
(define odd?
(letrec ([odd? (lambda (n)
(if (zero? n)
#f
(even? (- n 1))))]
[even? (lambda (m)
(lambda (x)
(odd? x))))
(if (zero? m)
#t
(odd? (- m 1))))])
((n) (m))
(((if-exp (app-exp (var-exp zero?) (var-exp n)) …))
((if-exp (app-exp (var-exp zero?) (var-exp m)) …)))
((lambda-exp (x) ((app-exp (var-exp odd?) (var-exp x))))))
2
letrec Evaluation
• Closures are created and added to the
letrec environment
• bodies of the letrec are evaluated in
order
• When one of the letrec closures is applied
– new environment must extend the letrec environment
• If it were let instead of letrec,
– the new environment would extend the enclosing environment instead
How to evaluate letrec?
(define eval-exp (lambda (exp env)
(cases expression exp …
[letrec-exp
(proc-names idss bodiess letrec-bodies)
…
(eval-bodies letrec-bodies
(extend-env-recursively
proc-names idss bodiess env))]
So the question becomes: how do we
implement extend-env-recursively?
We saw when we drew environment and closure diagrams that we need a recursive environment here
3
Extend-env-recursively: Three possible approaches
0. Implement extend-env-recursively intermsofScheme’sletrec. Nope!
1. No mutation: A new kind of environment extension: recursively-extended-env-record
2. Mutation: A normal extended environment, then use vector-set! to fix things up.
Disclaimer
• The succeed and fail arguments to the
apply-env procedure
– Add to the usability
– but not to the initial understandability of the code when you see new environment approaches.
• So I won’t include them here.
• Easy to add back in, once you understand
each of these approaches to letrec implementation.
4
datatype for no-mutation approach
(define-datatype environment environment?
[empty-env-record]
[extended-env-record
(env environment?)]
[recursively-extended-env-record
(proc-names (list-of symbol?))
(idss (list-of (list-of symbol?)))
(bodiess (list-of (list-of expression?)))
(env environment?)])
had these two (vals(list-ofscheme-value?)) variants
(syms (list-of symbol?))
We already
Recursive extension without mutation
(define extend-env-recursively
(lambda (proc-names idss bodiess old-env)
(recursively-extended-env-record
proc-names idss bodiess old-env)))
5
(define apply-env
(lambda (env sym)
(cases environment env
[empty-env-record ()(apply-global-env sym)] [extended-env-record (syms vals env)
What is the disadvantage of this approach?
(let ((pos (list-find-position sym syms))) (if (number? pos)
(list-ref vals pos)
(apply-env env sym)))]
[recursively-extended-env-record
(procnames idss bodiess old-env)
(let ([pos (list-find-position sym procnames)])
(if (number? pos)
(closure (list-ref idss pos)
(list-ref bodiess pos)
env)
(apply-env old-env sym)))])))
Mutation solution: Uses the ribcage implementation of environments.
6
Mutation solution: Uses the ribcage
implementation of environments.
(define extend-env-recursively
(lambda (proc-names idss bodiess old-env)
(let ([len (length proc-names)])
(let ([vec (make-vector len)])
This let has two bodies
With this representation, we can use the original extended- env-record
(let ([env (extended-env-record
proc-names vec old-env)]) and apply-
(for-each
(lambda (pos ids bodies)
(vector-set! vec
pos
env; it does not need the additional case for recursive environments.
(iota len)
idss
bodiess)
env)))))
(closure ids bodies env)))
(iota 4)(0 1 2 3)
You can easily write the code…
7
Another Mutation solution: Expand the source code using syntax-expand.
(define odd?
(letrec ([o? (lambda (n)
(if (zero? n)
#f
(e? (- n 1))))]
[e? (lambda (m)
o?))
(if (zero? m)
#t
(o? (- m 1))))])
How can we expand this to an expression involving let and set! ?
Binding vs. Assignment
• A binding creates a new name and associated value.
– In Scheme, accomplished by define, let, letrec, or application of a closure
• An assignment changes the value of a variable an existing binding.
– set!, or top-level define of an already- defined variable.
8
Add set! to the interpreter
• r-values vs l-values – x = x + 1;
• We need a way of changing the value of a bound variable
• Why doesn’t the current setup support this? • How can we fix this?
9