'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2004Lecture 16— Continuations and Related IdiomsDan Grossman CSE341 Spring 2004, Lecture 16 1'&$%Today• What are continuations?• What does let/cc mean?• How do continuations provide exception-like behavior?• Related idiom not using let/cc: iteratorsTime permitting: How “time travel” makes continuations so powerful(and easy to misuse).Dan Grossman CSE341 Spring 2004, Lecture 16 2'&$%Programs with holesConsider:(+ 3 (* 2 ))What does this “program with a hole” mean?“If you put a value v in the hole, the result is two times v plus 3.”That sounds like a function where the “function body” is the “re st ofcomputation”.A continuation is “the rest of computation”.A language with “first-class continuations” lets you “get atcontinuations”. Most let you treat them as functions (with weirdsemantics).Dan Grossman CSE341 Spring 2004, Lecture 16 3'&$%The let/cc primitive(let/cc k e)• Bind k to the current continuation (the rest of computation), a“function” that given a value (for a hole), completes computation.• Evaluate e to v and the result is v• But: Calling the continuation (e.g., (k 7)) means “forgeteverything else, the rest of computation is now the continuationwith 7 in the hole”.Examples:(+ 1 (let/cc k (+ 2 (if x 3 (k 4)))))((lambda (pr) (if (= (car pr) 0) 7 ((cdr pr) (cons 0 #f))))(let/cc k (cons 3 k)))Dan Grossman CSE341 Spring 2004, Lecture 16 4'&$%Connection with exceptionsInstead of building exceptions into our language, we can:• Pass in a continuation (or store it in a mutable global if you must)• Call the continuation to “forget what you are doing” and transfercontrol to an outer “rest of computation”Dan Grossman CSE341 Spring 2004, Lecture 16 5'&$%A lower-level viewContinuations really are defined in terms of “holes” and “rest ofcomputation”.But it’s often easier to reason in terms of a “call-stack”implementation.In this view:• let/cc wraps the current call-stack in a special function• Calling a continuation replaces the now-current call-stack with theone at the time of let/ccAnd that’s where “time travel” comes in: you can switch to acall-stack that without continuations would have not been needed anymore!Killer app: user-level non-preemptive threads!Dan Grossman CSE341 Spring 2004, Lecture 16 6'&$%Some perspectiveContinuations are perhaps too powerful and difficult to use well.Non-advanced programmers stay away from them.But it’s nice to think more generally about:• Languages with more powerful “control operators” than if andfunction application (languages used to not have exceptions either)• Programming styles (idioms) that exploit the idea of “rest ofcomputations”Example of the latter: iterator over treesDan Grossman CSE341 Spring 2004, Lecture 16
View Full Document
Unlocking...