Laser Accent 1
CSSE 304 Days 29-31
Copyright By PowCoder代写 加微信 powcoder
Escape procedures
Intro to call/cc
call/cc examples
Good and bad code for letrec
Springer/Friedman excerpt to read
Warm-up for call/cc
Escape procedures
call/cc involves both receivers and escape
procedures, so we look at both of those first
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.
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)
Review of Continuations
This intro is loosely based on one from the book Scheme and the Art of Programming by and .
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!
An escape procedure
Suppose 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
Escape procedures
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
If you want to experiment with escaper, you can define it 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
Call/cc definition and exampleS
But first, an analogy!
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/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.
It 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))
d) (call/cc procedure?)
Spring 2016 day 30:
We will stop after example b so I can answer questions about the exam.
(call/cc receiver) (receiver continuation)
(+ 3 (call/cc (lambda (k) (* 2 (k 5)))))
Stop here for today. Let this sink in before we move on
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. –
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))
A puzzling call/cc example
g) (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