Transcript Slides from class

CS 312 – Lecture 28
• Continuations
– Probably the most confusing thing you’ve
seen all semester…
• Course summary
– Life after CS 312
1
Continuations
• SML/NJ has ability to capture a control
context as a value: a continuation
• Continuation = “the rest of the program”
• Example: fn(z:bool) => if z then ~x else
if x<0 then ~x else x
x
fn(a: int)=>a
fn(a: int)=>~a
2
Continuations
• SML/NJ has ability to capture a control
context as a value: a continuation
• Continuation = “the rest of the program”
• Example: fn(z:bool) => if z then ~x else
x
if x<0 then ~x else x
• So we can rewrite the above code as
(fn(z:bool) => if z then ~x else x)
(x < 0)
3
Continuations in ML
• In CPS, functions don’t return – they just
pass their value to another function.
• Open SMLofNJ.Cont:
‘a cont is a continuation expecting a value of
type ‘a
throw: ‘a cont -> ‘a -> ‘b throws
control to continuation, never comes back
throw c v means: “You are c. Here is value v
for you, take it and take the control flow too;
I’ve done my job and I will disappear, so don’t
come back to me with your result.”
4
Continuations in ML
callcc : (‘a cont->`a)->`a
callcc f invokes f passing it the current
continuation
callcc f means: “I will now pass control to f, so
that f can perform some computation."
• throw = sending a value to a continuation
• callcc = sending a continuation to a function
When f is done, it will send something of type `a
to the continuation it received.
• directly, using a throw, or indirectly, with another callcc
So, the continuation must have type `a cont
and f will have type (`a cont -> `a). In the
end, it will be as though the callcc f had returned
`a.
5
Example
if (x < 0) then ~x else x
One way to write it in Continuation Passing Style:
let
fun f (x: int) (c: int cont): int = throw c (~x)
fun g (x: int) (c: int cont): int = throw c (x)
fun t (y: bool*int as (z, x)) (c: int cont): int =
if z then callcc (f x) else callcc (g x)
fun h (x: int) (c: int cont): int =
callcc ( t ((x<0), x))
in
callcc (h ~10 )
end
6
Handling errors
• Can be used in place of exceptions to send control to an
arbitrary place
let
fun g(n: real) (errors: int option cont) : int
option =
if n < 0.0 then throw errors NONE
else SOME(Real.trunc(Math.sqrt(n)))
fun f (x:int) (y:int) (errors: int option cont):
int option =
if y = 0 then throw errors NONE
else SOME(x div y+valOf(g 10.0 errors))
in
case callcc(f 13 3) of
NONE => "runtime error"
| SOME(z) => "Answer is "^Int.toString(z)
end
7
First-class continuations
• Can store continuations for future use!
let val cref: int cont option ref =
ref NONE
fun f(c: int cont): int =
(cref := SOME(c); 5)
in
callcc f;
case !cref of
NONE => "finished"
| SOME(co) => throw co 4
end
8
Continuations - summary
• Control context is encoded as a value and
passed around in the program
• Can be used to transfer control flow to
arbitrary points in the program
– related feature 1: gotos in low-level code
– related feature 2: setjmp/longjmp in C
– useful for exceptions
– useful in compilers and interpreters
• "You need to learn continuations about
three times before they really start making
sense."
9
What happened in CS 312?
• Design and specification of programs
– modules and interfaces
– documenting functions and ADTs
– programming in functional style
– testing
• Data structures and algorithms
– collections
– graphs
– showing correctness and complexity
• Programming languages
– Features and methodologies
– models of evaluation
– implementation
10
Life after SML
• 312 is not about SML or even about
functional programming
• Lessons apply to Java, C, C++, etc.
11
Design
• Break up your program into modules with
clearly defined interfaces (signatures)
• Use abstract data types (data abstractions)
• Good interfaces are narrow,
implementable, but adequate
• Avoid stateful abstractions, imperative
operations unless compelling justification
• Testing strategy and test cases: coverage
12
Specification
• Good specifications: clear, simple, concise,
accurate
• Think about your audience
• Avoid over-specification
• Abstraction barrier: user should not need
to know implementation/representation
• Convince someone that every spec is met
• Specify representation invariants and
abstraction functions
13
Data structures and algorithms
• Collections (ordered and unordered)
– Sets, maps
– Lists, arrays
– Hash tables
– Binary search trees (red-black, splay, B-trees)
– Priority queues/heaps
• Graphs
– BFS, DFS, Dijkstra
• CS 482 and 472
14
Data structures and algorithms
• String and regular-expression matching
– CS 381/481
• Mutable vs. immutable data structures
• Locality
– Everywhere (theoretical and applied courses)
15
Correctness and complexity
• Using specifications, invariants to reason
about correctness
• Constructing, solving recurrence relations
• Worst-case run time, average case run
time, amortized run time
• Proofs by induction
• CS 482
16
Programming languages
• Features
– Higher-order functions
– Explicit refs
– Recursive types and functions
– Lazy vs. eager evaluation
– Concurrency
• Evaluation models (semantics)
– Substitution
– Environments and closures
• Implementation
– Type checking and type inference
– Memory management, garbage collection
• CS 411, 412
17