Laser Accent 1
CSSE 304 Days 28-29
Copyright By PowCoder代写 加微信 powcoder
Escape procedures
Intro to call/cc
call/cc examples
Good and bad code for letrec
Springer/Friedman excerpt to read
Something Very time 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.
Warm-up for call/cc
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
What we’ll do today and next time is loosely based the book Scheme and the Art of Programming by and .
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)
I plan to go slow. Please don't let anything go over your head today. We can revisit anything!
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 is a receiver
(we previously called it the consumer)
new receiver example
(call-with-output-file “myfile.ss”
(lambda (p) ; this is the “receiver”
(let f ([ls list-to-be-printed])
(if (not (null? ls))
(write (car ls) p)
(newline p)
(f (cdr ls)))))))
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.”
(define call-with-output-file
(lambda (filename proc)
(let ((p (open-output-file filename)))
(let ((v (proc p)))
(close-output-port p)
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)
We can say that escape-+ ignores the current continuation, or “escapes from” the current continuation.
Answers: 11, 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
We can say that escape-+ ignores the current continuation, or “escapes from” the current continuation.
Answers: 11, 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 +) creates a procedure that is equivalent to escape-+
(+ 3 ((escaper +) 4 5))
(+ ((escaper (lambda (x)
(- (* x 3) 7)))
4)
Answers: 9, 8
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 +) creates a procedure that is equivalent to escape-+
(+ 3 ((escaper +) 4 5)) 9
(+ ((escaper (lambda (x)
(- (* x 3) 7)))
4) 8
Answers: 9, 8
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)))
You can experiment with escaper
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:
Is escaper an escape procedure?
Answer: error
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
“call-with” procedures
(call-with-values producer consumer)
The receiver is the consumer.
It receives the values returned by a call to the producer.
(call-with-input-file filename proc)
The receiver is proc.
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
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
an escape procedure that embodies the execution context of the entire call/cc expression.
call/cc definition summary
(call/cc receiver) (receiver continuation),
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).
call/cc example
(call/cc receiver) (receiver continuation)
(+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
The receiver is
The context c is
The continuation is
(+ 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)
(set! xxx k)
2))) ; xxx is equivalent to?
(* 7 (xxx 4))
This last one depends on context and also is a little weirder in Racket scheme
(call/cc receiver) (receiver continuation)
(+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
Next day questions (use RSG):
What is a receiver?
Is call/cc a procedure, or syntax?
IS call/cc an escape procedure?
What does call/cc expect as its argument?
What is call/cc an abbreviation for?
What does the receiver receive?
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) take the photograph
(set! xxx k) save the photograph
2))) ; xxx is equivalent to?
(* 7 (xxx 4)) rub the photograph
d) (call/cc procedure?)
(call/cc receiver) (receiver continuation)
(+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
List-index
Standard approach:
(define (list-index item L)
[(null? L) -1]
[(eq? (car L) item) 0]
[else (+ 1 (list-index item
(cdr L)))]))
What is the problem with this?
One solution: accumulator approach
But “standard recursion” seems so much more natural!
Can use call/cc to escape with the -1 answer?
Still more call/cc examples
e) (define list-index
(lambda (sym L)
(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))
> (list-index ‘a ‘(b d c))
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. –
Computer Science is the only discipline in which we view adding a new wing to a building as being maintenance. –
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)))
(lambda (k) k)))
“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.
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com