OutlineContinuationsContinuation Passing StyleCPS by HandCS421 Lecture 21: Continuation Passing Style1Mark [email protected] of Illinois at Urbana-ChampaignJuly 27, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuationsContinuation Passing StyleCPS by HandMark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandQuestionCan we use functions to represent the control flow in a program?Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuationsYes,using the concept of a continuation.◮We will augment each procedure with an additi onal argument– a function to which it will pass the current computationalresult.◮The outer procedure “returns” no result – it will be kept inthe function argument◮This function argument, receiving the res ult, will be called thecontinuation.◮Note: We saw the use of continuations briefly in the lastlecture.Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformContinuation Passing StyleWriting procedures so that they take a continuation to which theypass on t he computation result, and which return no result, iscalled continuation passing style (CPS)Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformContinuation Passing StyleCPS provides a programming technique for all forms of “non-local”control flow:◮non-local jumps◮exceptions◮etcCPS turns all non-tail calls into t ail calls.◮Essentially a higher-order functional GOTOMark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformContinuation Passing Style◮CPS also acts as a compilation technique to implementnon-local control flow◮Especially useful in interpreters◮Also acts as a formalization of non-lo cal control flow indenotational semantics (again, mentioned i n last le cture)Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformCPS Terminology◮A function i s in direct style when it returns its result back tothe caller (this is a standard function)◮A tail call occurs when a function returns the result ofanother function call without any more computations (li ke intail recursion, but not restricted to just recursive calls)◮A function is in continuation passing style when it passes itsresult to another function instead of back to its caller –essentially, we pass the result forward, not backwardsMark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformExampleA simple reporting continuation:1 # let report x =2 (print_int x; print_newline( ) );;3 val report : int -> unit = <fun>And a function that use s it:1 # let plusk a b k = k (a + b)2 val plusk : int -> int -> (int -> ’a) -> ’a = <fun>3 # plusk 20 22 report;;4 425 - : unit = ()Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformRecursive FunctionsRecall our defi nition of factorial:1 # let rec factorial n =2 if n = 0 then 1 else n * factorial (n - 1);;3 val factorial : int -> int = <fun>4 # factorial 5;;5 - : int = 120Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformRecursive FunctionsNow for our version with continuations:1 # let rec factorialk n k =2 if n = 03 then k 14 else factorialk (n - 1) (fun m -> k (n * m));;5 val factorialk : int -> (int -> ’a) -> ’a = <fun>6 # factorialk 5 report;;7 1208 - : unit = ()◮Note that our factorial calculation i s now tail recursive◮To make it work, we had to◮take a recursive value, m◮build it to a final result, n * m◮then pass it to the final continuation, k (n * m)Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformAnother Example: Length, Take 11 # let rec lengthk list k =2 match list with3 | [ ] -> k 04 | x :: xs -> lengthk xs (fun r -> k (r + 1));;5 val lengthk : ’a list -> (int -> ’b) -> ’b = <fun>6 # lengthk [2;4;6;8] report;;7 48 - : unit = ()Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformAnother Example: Length, Take 21 # let rec lengthk list k =2 match list with3 | [ ] -> k 04 | x :: xs -> lengthk xs (fun r -> plusk r 1 k);;5 val lengthk : ’a list -> (int -> ’b) -> ’b = <fun>6 # lengthk [2;4;6;8] report;;7 48 - : unit = ()Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing StyleCPS by HandContinuation Passing StyleCPS TerminologyExamplesCPS and ExceptionsMore TerminologyPerforming the TransformExample: Exceptions1 # exception Zero;;2 exception Zero3 # let rec list_mult_aux list =4 match list with [ ] -> 15 | x :: xs -> if x = 0 then raise Zero6 else x * list_mult_aux xs;;7 val list_mult_aux : int list -> int = <fun>8 # let rec list_mult list =9 try list_mult_aux list with Zero -> 0;;10 val list_mult : int list -> int = <fun>11 # list_mult [3;4;2];;12 - : int = 2413 # list_mult [7;4;0];;14 - : int = 015 # list_mult_aux [7;4;0];;16 Exception: Zero.Mark Hills CS421 Lecture 21: Continuation Passing StyleOutlineContinuationsContinuation Passing
View Full Document
Unlocking...