DOC PREVIEW
U of I CS 421 - Lecture

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Programming Languages and Compilers (CS 421)ContinuationsContinuation Passing StyleSlide 4Slide 5TermsExampleRecursive FunctionsRecursion FunctionsSlide 10Nesting CPSExceptions - ExampleSlide 13ExceptionsImplementing ExceptionsSlide 16Slide 17TerminologySlide 19CPS TransformationSlide 21Slide 22Continuations ExampleA Small CalculatorContinuations Can Take Multiple ArgumentsComposing ContinationsSample RunExecution TraceSlide 29Slide 30Slide 31Slide 32Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter Continuations•Idea: Use functions to represent the control flow of a program•Method: Each procedure takes a function as an argument to which to pass its result; outer procedure “returns” no result•Function receiving the result called a continuationElsa L. Gunter Continuation Passing Style•Writing procedures so that they take a continuation to which to give (pass) the result, and return no result, is called continuation passing style (CPS)Elsa L. Gunter Continuation Passing Style•A programming technique for all forms of “non-local” control flow:–non-local jumps–exceptions–general conversion of non-tail calls to tail calls•Essentially it’s a higher-order function version of GOTOElsa L. Gunter Continuation Passing Style•A compilation technique to implement non-local control flow, especially useful in interpreters.•A formalization of non-local control flow in denotational semanticsElsa L. Gunter Terms•A function is in Direct Style when it returns its result back to the caller.•A Tail Call occurs when a function returns the result of another function call without any more computations (eg tail recursion)•A function is in Continuation Passing Style when it passes its result to another function.•Instead of returning the result to the caller, we pass it forward to another function.Elsa L. Gunter Example•Simple reporting continuation:# let report x = (print_int x; print_newline( ) );;val report : int -> unit = <fun>•Simple function using a continuation:# let plusk a b k = k (a + b)val plusk : int -> int -> (int -> ’a) -> ’a = <fun># plusk 20 22 report;;42- : unit = ()Elsa L. Gunter Recursive Functions•Recall:# let rec factorial n = if n = 0 then 1 else n * factorial (n - 1);; val factorial : int -> int = <fun># factorial 5;;- : int = 120Elsa L. Gunter Recursion Functions# let rec factorialk n k = if n = 0 then k 1 else factorialk (n - 1) (fun m -> k (n * m));;val factorialk : int -> (int -> 'a) -> 'a = <fun># factorialk 5 report;;120- : unit = ()Elsa L. Gunter Recursive Functions•Notice: factorialk is now tail recursive•To make recursive call, must built intermediate continuation to –take recursive value: m–build it to final result: n * m–And pass it to final continuation: k (n * m)Elsa L. Gunter Nesting CPS# let rec lengthk list k = match list with [ ] -> k 0 | x :: xs -> lengthk xs (fun r -> k (r + 1));;val lengthk : 'a list -> (int -> 'b) -> 'b = <fun># let rec lengthk list k = match list with [ ] -> k 0 | x :: xs -> lengthk xs (fun r -> plusk r 1 k);;val lengthk : 'a list -> (int -> 'b) -> 'b = <fun># lengthk [2;4;6;8] report;;4- : unit = ()Elsa L. Gunter Exceptions - Example# exception Zero;;exception Zero# let rec list_mult_aux list = match list with [ ] -> 1 | x :: xs -> if x = 0 then raise Zero else x * list_mult_aux xs;;val list_mult_aux : int list -> int = <fun>Elsa L. Gunter Exceptions - Example# let rec list_mult list = try list_mult_aux list with Zero -> 0;;val list_mult : int list -> int = <fun># list_mult [3;4;2];;- : int = 24# list_mult [7;4;0];;- : int = 0# list_mult_aux [7;4;0];;Exception: Zero.Elsa L. Gunter Exceptions•When an exception is raised–The current computation is aborted–Control is “thrown” back up the call stack until a matching handler is found–All the intermediate calls waiting for a return value are thrown awayElsa L. Gunter Implementing Exceptions# let multkp m n k = let r = m * n in (print_string "product result: "; print_int r; print_string "\n"; k r);;val multkp : int -> int -> (int -> 'a) -> 'a = <fun>Elsa L. Gunter Implementing Exceptions# let rec list_multk_aux list k kexcp = match list with [ ] -> k 1 | x :: xs -> if x = 0 then kexcp 0 else list_multk_aux xs (fun r -> multkp x r k) kexcp;;val list_multk_aux : int list -> (int -> 'a) -> (int -> 'a) -> 'a = <fun># let rec list_multk list k = list_multk_aux list k k;;val list_multk : int list -> (int -> 'a) -> 'a = <fun>Elsa L. Gunter Implementing Exceptions# list_multk [3;4;2] report;;product result: 2product result: 8product result: 2424- : unit = ()# list_multk [7;4;0] report;;0- : unit = ()Elsa L. Gunter Terminology•Tail Position: A subexpression s of expressions e, if it is evaluated, will be taken as the value of e–if (x>3) then x + 2 else x - 4–let x = 5 in x + 4•Tail Call: A function call that occurs in tail position–if (h x) then f x else (x + g x)Elsa L. Gunter Terminology•Available: A function call that can be executed by the current expression•The fastest way to be unavailable is to be guarded by an abstraction (anonymous function).–if (h x) then f x else (x + g x)–if (h x) then (fun x -> f x) else (x + g x)Elsa L. Gunter CPS TransformationStep 1: Add continuation argument to any function definition:let f arg = e  let f arg k = e•Idea: Every function takes an extra parameter saying where the result goesStep 2: A simple expression in tail position should be passed to a continuation instead of returned:return a  k a•Assuming a is a constant or variable.•“Simple” = “No available function calls.”Elsa L. Gunter CPS TransformationStep 3: Pass the current continuation to every function call in tail positionreturn f arg  f arg k•The function “isn’t going to return,” so we need to tell it where to put the result.Step 4: Each function call not in tail position needs to be built into a new continuation (containing the old continuation as appropriate)return op (f arg)  f arg (fun r -> k(op r))•op represents a primitive operationElsa L. Gunter ExampleBefore:let rec add_list lst =match lst with [ ] -> 0| 0 :: xs -> add_list xs| x :: xs -> (+) x (add_list xs);;After:let rec add_listk lst k = (* rule 1 *)match lst with| [ ] -> k 0 (* rule 2 *)| 0 ::


View Full Document

U of I CS 421 - Lecture

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?