CSSE 304 Day 26
Third letrec approach
About next week’s exam CPS wrap-up: tips and pitfalls
Intro: Add VHWto our interpreter
Add letrec to our interpreted language
1. No-mutation approach (uses recursively- extended-env-record, a new variant of the environment datatype)
2. Mutation approach (uses the ribcage-with- vectors approach, creates the recursive environment by calls to vector-set!)
3. Syntax-expand approach (also uses mutation, next slide)
1
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?))
Inyourinterpreter,expand a parsed letrec expression into a parsed let expression with additional bodies that are set! expressions
(if (zero? m)
#t
(o? (- m 1))))])
How can we expand this to an expressioninvolvingletandset!?
(Answer will be on the whiteboard)
Exam 2 format
• Exam 2 is Tuesday evening, week 8
• Three parts:
– E&C – already done (20 points)
– Written part (estimate: 40-50 points) Will include interpreter questions (how did you implement …?
how would you add …)
• Know your interpreter well.
– Comp. part, possibly including interpreter problem(s) (estimate: 30-40 points)
2
Potential Topics for Exam 2 • environments and closures diagrams (done last week)
• programming with lists (and nested lists)
• grammars (and code that follows the grammar)
• processing s-lists
• procedural abstraction (list‐recur, sn-list-recur, etc.)
• curried procedures, procedures that return procedures
• How mutation works (set!, set‐car!, set‐cdr!)
• persistent data (OO-approach, and memoization)
• case-lambda
• define‐syntax (and difference between syntactic extension & procedure definition)
• abstract data types: interface, representation & implementation
• Abstract data types, representation-independence, define‐datatype and cases
• free & bound variable occurrences, lexical address
• Parsing, working with parsed expressions
• Enhance interpreter (you need to bring your working interpreter code for comp part)
• Continuations, write code in CPS
• Multi-value returns (values, call‐with‐values, with‐values, mvlet)
• Show that you are a good programmer/problem solver.
If you have questions about old exam problems or solutions, ask them on Piazza so everyone can see the conversation.
One more thing …
• Onemorethingthatisnecessaryforsuccesson exam 2:
• You must be a good programmer/problem solver and be reasonably fast at it
• Should have been true before you got to this course
• Doing the HW should have enhanced your skills
• IMO:Astudentwhounderstandstheconcepts but cannot apply them to new situations is a C student.
• WhatkindsofexamgradesdoesaCstudentin this class have?
3
CPS tips
• The one thing to avoid:
– A call to a substantial procedure in a non-tail position.
• apply-k is a substantial procedure; make-k is not.
• Whenever you get an answer without doing a
substantial call, don’t forget to call apply-k.
• Ask “what happens next”, and put it on the outside of the remaining code, with later things “inside”, as part of the continuation.
• Ifyouthinkthecontinuationofarecursivecall should be (lambda(v) v), there’s a good chance that your code is not actually in tail form.
• Regardlessofwhattheserversays,nocreditif code is not in tail form
Some incorrect CPS code
All of this code was submitted by students in previous terms.
(define set?-cps
(lambda (ls k)
(cond
[(null? ls) (apply-k k #t)]
[(member?-cps (car ls)
(cdr ls)
(make-k (lambda (v) v)))
(apply-k k #f)]
[else (set?-cps (cdr ls) k)])))
Which call(s) to non-primitive procedures is/are not in tail-position?
4
Some incorrect CPS code
All of this code was submitted by students in previous terms.
(define andmap-cps
(lambda (pred?-cps ls k)
(cond
[(null? ls) (apply-k k #t)]
[(pred?-cps (car ls)
(make-k (lambda (v) v)))
(andmap-cps pred?-cps
(cdr ls) k)]
[else (apply-k k #f)])))
Which call(s) to non-primitive procedures is/are not in tail-position?
Some incorrect CPS code
(define identity (make-k (lambda (k) k))) (define matrix?-cps
(lambda (m k)
(if (list?-cps m identity)
(if (not (null? m))
(if (not (null? (car m)))
(if (andmap-cps list?-cps m identity) (if (andmap-cps
Which call(s) to non-primitive procedures is/are not in tail-position?
(make-cps
(lambda (L)
(= (length-cps L identity)
(length-cps (car m) identity))))
(cdr m)
identity)
(apply-k k #t)
(apply-k k #f))
(apply-k k #f))
(apply-k k #f))
(apply-k k #f))
(apply-k k #f))))
5
Some incorrect CPS code
Which call(s) to (if (not (list?-cps ls procedures
(define matrix?-cps
(lambda (ls k) non-primitive
(make-k (lambda (v) v)))) is/are not in tail-
(apply-k k #f)
(if (null? ls) position?
(apply-k k #f)
(if (null? (car ls))
(apply-k k #f)
(if (not (andmap-cps list?-cps ls
(apply-k k #f)
(if (not (andmap-cps
What is common to all of the non- tail recursion “CPS calls” in all of these examples?
(apply-k k #t))))))))
(make-k (lambda (v) v))))
(make-cps
(lambda (L)
(length-cps L
(lambda (v)
(= v (length-cps (car ls)
(make-k (lambda (v) v))))))))
(cdr ls)
(lambda (v) v)))
(apply-k k #f)
CPS and the future of 304
• Practice writing CPS code (A15)
• Add other features to interpreter (no CPS) (A16-17)
• (Inclassweeks7-8)Learnhowcall/ccworks.
• (In class week 8) Learn about data structures representation of continuations.
• Convert interpreter to CPS (A 18)
– Use the data-structures representation of continuations in your interpreter
• UseCPSinterpretertoaddcall/cctoour interpreted language. (A 18)
• Convert CPS code to imperative form, check code for tail form (A 19)
6
Another CPS example
• We will not do it in class • ItispartofHW15
• cps-list-recur (next slide)
cps-list-recur
• Not a cps procedure itself,
• butproducescpsprocedures • Arguments: A base-value
a cps-procedure
> (define +-cps ; you will generalize (lambda (a b k) ; this in make-cps (A15)
(apply-k k (+ a b))))
> (define list-sum-cps
(cps-list-recur 0 +-cps))
> (list-sum-cps ‘(1 2 3 4)
(make-k (lambda (v) (+ v 1000))))
1010
7
Add set! to the interpreted language
INTERPRETER NEXT STEP
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?
Add set! to the interpreter
• ADT approach: Add a new environment observer:
– (apply-env-ref env var) returns a reference to the variable in question. (so it is the reference constructor).
– (deref ref) gets the value stored in the location that is referenced by ref.
– (set-ref! ref value) sets the value stored there
– If we have apply-env-ref, then apply-env does not have
to be a basic operation of the environment datatype:
(define apply-env
(lambda (env var)
(deref (apply-env-ref env var))))
but it may be more efficient to implement apply-env directly (in a representation-dependent way).
This code is representation-indepedent
9
Implementing set!
• Once we have references, it is easy.
A new clause for eval-exp’s cases:
[set!-exp (id exp)
(set-ref!
(apply-env-ref env id)
(eval-exp exp env))]
All that is left to do is to implement references! (we’ll look at multiple approaches)
Implementing apply-env-ref, deref, set-ref!, extend-env
• Use a cell abstract data type.
(cell value) creates a cell containing the value. (cell-ref cell) gives us the value in the cell. (cell-set! cell value) replaces the value in the cell. (cell? obj) asks if an object is a cell.
Use these to implement references. Then
First step: In the extend-env implementation, replace vals with (map cell vals)
Second step: In the previous code, change the name of apply-env to apply-env-ref
Third step: Use the representation-independent implementation of apply-env from an earlier slide.
10
A summary of the ADTs that we have so far:
Environment
(empty-env)
(extend-env vars vals env)
(apply-env env id)
(apply-env-ref env id)*
Reference
(deref ref)
(set-ref! ref val)
Cell
(cell val)
(cell-ref cell)
(cell-set! cell val)
(cell? obj)
*This is the constructor for the reference type.
1. We use references to implement the new environment interface.
2. We use cells to implement references within an environment.
3. Now we need to implement cells. representation? code?
(cell value)
(cell? obj)
(cell-ref cell)
Implementing the cell ADT
• Usedefine-datatype.
• Use a pair for each cell.
• Use Chez Scheme box data type .
See the Chez Scheme Users Guide
A17a: You will add set! and top-level define
to your interpreter
Cell ADT
(cell-set! cell value)
Box implementation
(box value)
(box? obj)
(unbox cell)
(set-box! cell value)
11