MP 9 – CPS and a Lazy Intepreter forMicroMLCS 421 – Spring 2007Revision 1.1Assigned Wednesday, April 18, 2007Due Wednesday, April 25, 2007 at 23:59Extension two days (20% penalty)1 Change Log1.1 Changed “non-empty” to “empty” in Q7.1.0 Initial release2 OverviewThere are two problem sections in this MP: the first is on Continuation Passing Style (CPS) and the second asks youto write a CPS interpreter for MicroML that supports lazy evaluation based on an operational semantics for MicroML.The first part is required for the whole class; the second part is required for the graduate students and extra credit forthe undergraduate students.Upon completion of this MP (if you do both parts), you should have the following skills:• the ability to use CPS effectively,• the ability to implement a call-by-need language,• the ability to write a realistic interpreter for an ML-like language, and• the ability to laugh sincerely when someone makes a continuation passing style joke at a cocktail partyEnjoy!3 FilesThere are two graders, mp9graderA and mp9graderB. The first grader is for the first part of this assignment, and thesecond is for the second part of the assignment.The only files you should modify and submit are mp9A.ml and mp9B.ml.mp9graderA is fairly simple; it contains only the file mp9A-skeleton.ml, which you should rename to mp9A.ml.mp9graderB is a bit more complicated, but it is very similar to the grader for the last assignment; in particular,upon running make or gmake you will get three executables: mp9B, mp9BSol and grader.The file mp9common.cmo contains the datatype for expressions (input to your evalutor) and the datatypes forvalues (output of your evaluator). For this MP, mp9common.cmo also defines the thunk type, to be explainedbelow.You are also given files mp9lex.cmo, mp9yacc.cmo, etc...14 Continuation Passing StyleThese exercises are designed to give you a feel for continuation passing style before you build your interpreter.A function that is written in continuation passing style does not return once it has finished its computation. Instead,it calls another function (the continuation) with the result.Here is a small example:# let report x =print_string "Result: ";print_int x;print_newline()val report : int -> unit = <fun># let inck i k = k (i+1)val inck : int -> (int -> ’a) -> ’a = <fun>The inck function takes an integer and a continuation. After adding 1 to the integer, it passes the result to itscontinuation.# inck 3 report;;Result: 4- : unit = ()# inck 3 inck report;;Result: 5- : unit = ()In line 1, inck increments 3 to be 4, and then passes the 4 to report. In line 4, the first inck adds 1 to 3, andpasses the resulting 4 to the second inck, which then adds 1 to 4, and passes the resulting 5 to report.5 Part A - CPS Problems (required for all)You have been given a file called mp9A-skeleton.ml. You should write your solutions to the CPS problems inthat file.The following six problems demonstrate different techniques of CPS. None of the functions you write may directlyreturn a value; all must be written in CPS.Simple Continuations1. (5 pts) Write the functions subk, catk, doublek, plusk, multk, and isposk in CPS. subk subtracts oneinteger froma another; catk concatenates two strings; double k concatenates a string with itself, plusk adds twofloats, multk multiplies two floats, and is posk determines if an integer is greater than 0.# let subk n m k = ...;;val subk : int -> int -> (int -> ’a) -> ’a = <fun># let catk a b k = ...;;val catk : string -> string -> (string -> ’a) -> ’a = <fun># let doublek a k = ...;;val doublek : string -> (string -> ’a) -> ’a = <fun># let plusk x y k = ...;;val plusk : float -> float -> (float -> ’a) -> ’a = <fun># let multk x y k = ...;;val multk : float -> float -> (float -> ’a) -> ’a = <fun># let is_posk n k = ...;;2val is_posk : int -> (bool -> ’a) -> ’a = <fun># subk 10 5 report;;Result: 5- : unit = ()# catk "hi " "there" (fun x -> x);;- : string = "hi there"# doublek "pom " (fun x -> x);;- : string = "pom pom "# plusk 3.0 4.0(fun x -> multk x x(fun y -> (print_string "Result: ";print_float y; print_newline())));;Result: 49.- : unit = ()# is_pos 7 (fun b -> (report (if b then 3 else 4)));;Result: 3- : unit = ()Nesting Continuations One common technique used in CPS is that of nesting continuations. For example, considerthe following code:# let add3k a b c k =addk a b (fun ab -> addk ab c k);;val add3k : int -> int -> int -> (int -> ’a) -> ’a = <fun># add3k 1 2 3 report;;Result: 6- : unit = ()We needed to add three numbers together, but addk itself only adds two numbers. On line 2, we give the first callto addk a function that saves the sum of a and b in the variable ab. Then this function adds ab to c and passes itsresult to the continuation k.2. (5 pts) Using multk and plusk as helper functions, write a function abcdk, which takes four float argumentsa b c d and “returns” a ∗ (b + c) ∗ d. You may not use the normal*. operator or +. operators; you must insteaduse multk and plusk.# let abcdk a b c d k = ...val abcdk : float -> float -> float -> float -> (float -> ’a) -> ’a = <fun># abcdk 2.0 3.0 4.0 5.0 (fun y -> report (int_of_float y));;Result: 70- : unit = ()Recursion and Continuation How do we write recursive programs in CPS? Consider the following recursive func-tion:# let rec factorial n =if n = 0 then 1 else n*factorial (n - 1);;val factorial : int -> int = <fun># factorial 5;;- : int = 1203To put the function into CPS, we must make factorial take an additional argument, a continuation, to which theresult of the factorial function should be passed. When the recursive call is made to factorial, instead of it returning aresult to build the next higher factorial, it needs to take a continuation for building that next value from its result. Thusthe code becomes:# 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 = ()To make a recursive call, we must built an intermediate continuation to:• take the recursive value: m• build it to the final result: n*mAnd pass it to the final continuation: k (n*m). Notice that this is an extension of the ”nested continuation”method.3. (10 pts) Write gcdk m n k, the CPS version of:let rec gcd m n =let d1 = m - nin if d1 > 0 then gcd d1 nelse let d2 = n - m in if d2 > 0 then gcd m d2 else mYou should use subk for
View Full Document
Unlocking...