CSSE 304 Day 24 (E&C exam was Day 23)
More CPS procedures succeed and fail continuations (CPS Pitfalls)
Continue the live coding
Do the procedures that we did not do Day 22
(if there is time) Succeed and fail continuations:
List-prod-cps subst-leftmost-cps
1
Extra credit – up to 120 HW points
• Modifyyourinterpretersothatitcaninterpretitself.
• In rep mode, you can load the code and run it within
your interpreter.
• You may need to bypass define-datatype, or
implement a similar mechanism.
• Can your “second level” loaded interpreter load and
run another interpreter? How many levels can you
do?
• Demonstrate it to me no later than Wednesday of
exam week.
• You can do this with one or two other students.
– Can be people who are NOT on your interpreter team.
• Ifyouarethinkingofdoingthis,let’shavea conversation about it.
Continue with …
CONTINUATIONS AND CPS
2
Recap: Tail-form and CPS
• A continuation represents …
• Code is in tail-form if …
• CPS – continuation-passing style:
• When we get an answer without a recursive call, apply the current continuation to that answer.
• When we make a recursive call, construct correct continuation, use make-continuation.
• For now, continuations are represented as Scheme procedures (so the constructor is lambda).
• (define apply-k
(lambda (k v) (k v)))
• Later we will represent continuations as data structures.
Pass an explicit continuation to each recursive procedure call.
Succeed and fail continuations
(define prod-cps ; fill in the continuations at the end (lambda (L succeed fail)
(cond [(null? L) (apply-k succeed 1)]
[(zero? (car L)) (apply-k fail)]
[else (prod-cps (cdr L)
Code that uses prod-cps:
(define print-list-product
(lambda (list)
(prod-cps list
(make-k(lambda (prod)
(printf “The product is ~s~n” prod)))
(make-k (lambda ()
(printf “zero found, product is 0”)))))
3
Succeed and fail continuations
(define prod-cps ; fill in the continuations at the end (lambda (L succeed fail)
(cond [(null? L) (apply-k succeed 1)]
[(zero? (car L)) (apply-k fail)]
[else (prod-cps (cdr L)
Code that uses prod-cps:
(define print-list-product
(lambda (list)
(define apply-k
(lambda (k . vals)
(prod-cps list
(make-k(lambda (prod)
(apply k vals)))
(printf “The product is ~s~n” prod)))
(make-k (lambda ()
(printf “zero found, product is 0”)))))
Subst-leftmost with continuations
• Whatdoessubst-leftmostdo? • Why was it hard?
4
(define substitute-leftmost
(lambda (new old slist)
(subst-left-cps
new
old
slist
(lambda (v) v)
(lambda () slist) ; fail continuation
)))
(define subst-left-cps
(lambda (new old slist changed unchanged)
(let loop ([slist slist]
[changed changed]
[unchanged unchanged])
(cond
[(null? slist) (apply-k unchanged)]
; fill in the rest (next slide)
A solution with succeed and fail continuations may be better…
; succeed continuation
Green boxes:
changed
continuations
Red boxes:
unchanged
continuations
(make-k (lambda ()
(loop (cdr slist)
(make-k (lambda (substituted-cdr) (apply-k changed
(cons (car slist)
substituted-cdr))))
unchanged))))]))))
(define subst-left-cps ; changed and unchanged are continuations (lambda (new old slist changed unchanged)
(let loop ([slist slist] [changed changed] [unchanged unchanged])
(cond
[(null? slist) (apply-k unchanged)]
[(symbol? (car slist))
(define apply-k
(lambda (k . vals)
(if (eq? (car slist) old)
(apply-k changed (cons new (cdr slist)))
(loop (cdr slist)
(make-k (lambda (substituted-cdr) (apply-k changed
(apply k vals)))
(cons (car slist) substituted-cdr))))
unchanged))]
[else ; car is an s-list
(loop (car slist)
(make-k (lambda (substituted-car)
(apply-k changed (cons substituted-car (cdr slist)))))
5