DOC PREVIEW
U of I CS 421 - Programming Languages and Compilers

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 andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterContinuations• Idea: Use functions to represent thecontrol flow of a program• Method: Each procedure takes afunction as an argument to which topass its result; outer procedure “returns”no result• Function receiving the result called acontinuationElsa L. GunterContinuation Passing Style• Writing procedures so that they take acontinuation to which to give (pass) theresult, and return no result, is calledcontinuation passing style (CPS)Elsa L. GunterContinuation Passing Style• A programming technique for allforms of “non-local” control flow:– non-local jumps– exceptions– general conversion of non-tail calls totail calls• Essentially it’s a higher-orderfunction version of GOTOElsa L. GunterContinuation Passing Style• A compilation technique toimplement non-local control flow,especially useful in interpreters.• A formalization of non-local controlflow in denotational semanticsElsa L. GunterTerms• A function is in Direct Style when itreturns its result back to the caller.• A Tail Call occurs when a functionreturns the result of another function callwithout any more computations (eg tailrecursion)• A function is in Continuation PassingStyle when it passes its result to anotherfunction.• Instead of returning the result to thecaller, we pass it forward to anotherfunction.Elsa L. GunterExample• 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. GunterRecursive 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. GunterRecursion 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. GunterRecursive Functions• Notice: factorialk is now tailrecursive• To make recursive call, must builtintermediate continuation to– take recursive value: m– build it to final result: n * m– And pass it to final continuation: k (n * m)Elsa L. GunterNesting 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. GunterExceptions - 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. GunterExceptions - 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. GunterExceptions• When an exception is raised– The current computation is aborted– Control is “thrown” back up the callstack until a matching handler isfound– All the intermediate calls waiting for areturn value are thrown awayElsa L. GunterImplementing 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. GunterImplementing 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) k0;;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. GunterImplementing 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. GunterTerminology• Tail Position: A subexpression s ofexpressions e, if it is evaluated, will betaken 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 intail position– if (h x) then f x else (x + g x)Elsa L. GunterTerminology• Available: A function call that can beexecuted by the current expression• The fastest way to be unavailable is tobe 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. GunterCPS TransformationStep 1: Add continuation argument to anyfunction definition:let f arg = e ⇒ let f arg k = e• Idea: Every function takes an extra parametersaying where the result goesStep 2: A simple expression in tail positionshould be passed to a continuation instead ofreturned:return a ⇒ k a• Assuming a is a constant or variable.• “Simple” = “No available function calls.”Elsa L. GunterCPS TransformationStep 3: Pass the current continuation to everyfunction call in tail positionreturn f arg ⇒ f arg k• The function “isn’t going to return,” so we needto tell it where to put the result.Step 4: Each function call not in tail positionneeds 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. GunterExampleBefore: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 :: xs -> add_listk xs k (* rule 3 *)| x :: xs -> add_listk xs (fun r -> k ((+) x r));; (* rule 4 *)Elsa L. GunterContinuations Examplelet add a b k = print_string "Add "; k (a + b);;let sub a b k = print_string "Sub "; k (a - b);;let report n = print_string "Answer is: "; print_int n; print_newline ();;let idk n k = k n;;type calc = Add of int | Sub of intElsa L.


View Full Document

U of I CS 421 - Programming Languages and Compilers

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 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 Programming Languages and Compilers
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 Programming Languages and Compilers 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 Programming Languages and Compilers 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?