CSSE 304 Days 27 and 29
Questions about Exam 2 expectations? Finish set! And define discussion Receivers
Escape procedures
Intro to call/cc call/cc examples
Can we do mutation in other ways?
2. Alternativeusingtheribcagewithvectors approach to environment implementation
– See the ribcage diagram on next slide.
– A reference is a datatype whose fields are a vector and
an index. I recommend that you investigate this one.
– deref is implemented using vector-ref
– set-ref! is implemented using vector-set!
3. A“normal”memorymodel…
– A single vector to contain all values – A reference is an index (an address) – Allocation and Garbage Collection?
1
Ribcage structure
Top‐level define
• Note that define and set! do different things
• dynamic global environment vs static local environments
• Should local environments extend the global environment?
– If you do it, be careful!
– Ifyoudoit,Idonotwanttohelpyouwith debugging that requires tracing!
2
Something Very New
• We finished the discussion of things you need as background for A17.
• You need to finish A16 and A17a before you’ll be ready to discuss details of A18.
• You also need to know about call/cc and a data‐ structures representation of continuations.
• We will work on those for the next 4 or 5 class meetings.
Receivers Escape procedures
call/cc involves both receivers and escape procedures, so we look at both of those first.
Before those, a quick review of continuations
WARM‐UP FOR CALL/CC
3
What we’ll do today and next time is loosely based the book Scheme and the Art of Programming by George Springer and Daniel Friedman.
Review of Continuations
• Consider the evaluation of the expression:
(let ([x (+ y 2)])
(if (< x 4) 5 (- x 6))
What is the continuation of
(+ y 2) ? 6 ?
(- x 6) ? (< x 4)
4
Receivers
• A receiver is an argument (which happens to also be a procedure) passed to a procedure, with the intention that the procedure will eventually pass values to that receiver.
• Example: The continuations that we pass to CPS procedures are receivers.
• Sometimes receivers are called "callbacks"
Old Receiver Example: call‐with‐values
• > (call-with-values
(lambda () (values 3 4))
list)
(3 4)
• list is a receiver
(we previously called it the consumer)
5
new receiver example
From TSPL: The following shows the use of call-with-output-file to write a list of objects (the value of list-to-be-printed), separated by newlines, to the file named by “myfile.ss.”
(call-with-output-file “myfile.ss” (lambda (p) ; this is the “receiver”
(let f ([ls list-to-be-printed])
(if (not (null? ls))
(begin
(write (car ls) p)
(newline p)
(define call-with-output-file (f (cdr ls))))))) (lambda (filename proc)
(let ((p (open-output-file filename)))
(let ((v (proc p)))
(close-output-port p)
v))))
The receiver expects to receive an output port as its argument
An escape procedure
• Pretend that we have a procedure escape-+ that adds its arguments and returns this sum as the final answer, no matter what the context.
(* (escape-+ 5 6) 3) (escape-+ (escape-+ 2 4) 5)
6
An escape procedure
• Pretend that we have a procedure escape-+ that adds its arguments and returns this sum as the final answer, no matter what the context.
(* (escape-+ 5 6) 3) 11 (escape-+ (escape-+ 2 4) 5)6
Escaper (a mostly fictitious procedure)
• More generally, suppose that we have a procedure escaper that takes a procedure as an argument and returns an equivalent escape procedure.
•(escaper+)createsaprocedurethatis equivalent to escape-+
• (+ 3 ((escaper +) 4 5)) • (+ ((escaper (lambda (x)
(- (* x 3) 7))) 4)
5)
7
Escaper (a mostly fictitious procedure)
• More generally, suppose that we have a procedure escaper that takes a procedure as an argument and returns an equivalent escape procedure.
•(escaper+)createsaprocedurethatis equivalent to escape-+
•(+ 3 ((escaper +) 4 5)) 9 • (+ ((escaper (lambda (x)
(- (* x 3) 7))) 4)5) 8
You can experiment with
escaper
• You can define escaper by loading escaper.ss in the following way:
escaper.ss is linked from the schedule page
sliderule 1:12pm > petite escaper.ss
Petite Chez Scheme Version 6.7
Copyright (c) 1985-2001 Cadence Research Systems > ((call/cc receiver-4))
“escaper is defined”
> (cdr ((escaper cdr) ‘(4 5 6)))
(5 6)
8
Escape Procedures
• Let p be a procedure. If an application of p abandons the current continuation and does something else instead, we call p an escape procedure.
• An example of a Scheme escape procedure that we have already used:
• Isescaperanescapeprocedure?
dining out example from Springer and Friedman, Part 5 intro
(define dine-out
(lambda (restaurant)
(enter restaurant)
(read-menu)
(let ([food-I-ordered
(order-some-food)])
(eat food-I-ordered)
(pay-for food-I-ordered restaurant)
(exit restaurant))))
Read excerpt from the book
9
“call‐with” procedures
• (call‐with‐values producer consumer)
– Thereceiveristheconsumer.
– It receives the values returned by a call to the producer.
• (call‐with‐input‐file filename proc)
– Thereceiverisproc.
– It receives the input port obtained by opening the input file whose name is filename.
• (call‐with‐current‐continuation receiver)
– The receiver receives the current continuation.
CALL/CC DEFINITION AND EXAMPLES
10
call/cc • call/cc is an abbreviation for
call-with-current-continuation .
• call/cc is a procedure that takes one argument; the argument is a
receiver.
• this receiver is a procedure that takes one argument; that
argument (in this case) is a continuation.
• A continuation is a procedure (that takes one argument); that continuation embodies the context of the application of call/cc. The continuation is an escape procedure.
• The application (call/cc receiver) has the same effect as (receiver continuation), where the continuation is
– anescapeprocedurethatembodiestheexecutioncontextoftheentire call/cc expression.
call/cc definition summary
• (call/ccreceiver)(receivercontinuation), • Hence the name:
call‐with‐current‐continuation.
• Rephrasing it: What is that continuation?
If c is a procedure that represents the execution context of this application of call/cc, then the continuation is equivalent to (escaper c).
11
call/cc example
• (call/cc receiver) (receiver continuation) • Consider
(+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
– The receiver is
– The context c is
– The continuation is
– Thus
(+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
is equivalent to
More call/cc examples
a) (+ 3 (call/cc (lambda (k) (* 2 5)))) b) (+ 3 (call/cc (lambda (k)
(k (* 2 5)))))
c) (define xxx #f)
(+ 5 (call/cc (lambda (k)
(* 7 (xxx 4))
(set! xxx k)
2))) ; xxx is equivalent to?
(call/cc receiver) (receiver continuation) (+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
12
More call/cc examples
a) (+ 3 (call/cc (lambda (k) (* 2 5)))) b) (+ 3 (call/cc (lambda (k)
(k (* 2 5)))))
(+ 5 (call/cc (lambda (k) take the photograph
(set!xxxk) savethephotograph 2))) ; xxx is equivalent to?
(* 7 (xxx 4)) rub the photograph d) (call/cc procedure?)
c) (define xxx #f)
(call/cc receiver) (receiver continuation) (+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
(define (list‐index item L)
(cond
[(null? L) ‐1]
[(eq? (car L) item) 0]
[else (+ 1 (list‐index item
List‐index
• Standard approach:
But “standard recursion” seems so much more natural!
What is the problem with this?
One solution: accumulator approach
(cdr L)))]))
Can use call/cc to escape with the -1 answer?
13
Still more call/cc examples
e) (define list-index (lambda (sym L)
(call/cc
(lambda (answer)
(let loop ([L L])
(cond [(null? L) (answer -1)]
[(eqv? sym (car L)) 0]
[else (+ 1
(loop (cdr L)))]))))))
> (list-index ‘a ‘(b a c)) 1
> (list-index ‘a ‘(b d c)) -1
f) ((car (call/cc list)) (list cdr 1 2 3))
Interlude: quotes
• Premature optimization is the root of all evil in programming. ‐ C.A.R. Hoare
Do you know what he is famous for?
• There is no code so big, twisted, or complex that
maintenance can’t make it worse. ‐ Gerald Weinberg
• Computer Science is the only discipline in which we view adding a new wing to a building as being maintenance. – Jim Horning
14
Two more call/cc examples
g) (let ([f 0] [i 0])
(call/cc (lambda (k) (set! f k))) (printf “~a~n” i)
(set! i (+ i 1))
(if (< i 10) (f "ignore")))
h) (define strange1 (lambda (x)
(display 1)
(call/cc x)
(display 2)))
(strange1
(call/cc
(lambda (k) k)))
i)
“mondo bizarro” example
(define strange2
(lambda (x)
(display 1)
(call/cc x)
(display 2)
(call/cc x)
(display 3)))
(strange2 (call/cc (lambda (k) k)))
We probably will not do this one in class; good practice for you.
15