CS 421 – Spring 2007Lecture Notes Set 33:CPSElsa L. Gunter1Transcribed by: Pooja MathurCorresponding to Slides: 26-CPS (slides 6-17)Made available: April 18, 2007Revision 1.01 Change Log1.0 Initial Release.2 CPS2.1 Terminology (slide 6)A function is said to be in direct style when it returns its result to whatever procedure called it. However, we aren’tgoing to use direct style. We are going to be using something else. Recall tail recursion, in CPS, instead of returningthe result from a recursive call, we are going to do a tail call to its continuation. So you will always be passing on ourresult, instead of passing it backwards.2.2 Simple example (slide 7)But if we continue to pass results forward, we will seemingly, never have an end of the chain. So we have to putsomething there to say we are done. So, our end of the chain in most cases will be the report function. And what itdoes is simply report back the result. That is, it prints out the integer that was calulated and then prints a new line.Other times we will use the identity function. So it will take what ever you gave it and then return it right back.But here, along with the report function, we will use the function plusk. Recall, when we were first learning OCamland we learned how to make a simple function that added two numbers. Now we are going to take that a step fartherand turn such a function into a continuation. So we are going to take three arguments and still do the addition. Thereare the two values to add a and b and then there is k which is what receieves the result of performing some operation.So what happens is a and b get added together and then the result is handed to k.# let plusk a b k = k (a + b)val plusk : int → int → (int → a) → a = <fun>So another way to think of this is that plusk doesn’t give back a result, but the function k is what returns the answer.You can see this by looking at the type of plusk. The first two ints belong to a and b and then we see that plusk alsotakes in a function that takes an int and returns a0a. That function is what goes into k. And that function returns thefinal result of that has type0a.Now, let’s try to use plusk. We send in the values 20 and 22 and the function report. The numbers get added, andthen they are sent to report. Report prints the 42 (like we told it to) and then we get a final type of type unit.# plusk 20 22 report;;42- : unit = ()1c 2007, Share and Enjoy12.3 Recursive example (slides 8-10)So for simple functions, you take in your argument, you do whatever computation you were supposed to do to it, butnow you take one more argument which is going to be the continuation. It will be the place the result needs to go. Inthe recursive case, part of the work goes into calling itself. So let’s use factorial as an example.In normal OCaml code, we have the recursive factorial function take in a single argument n. We have our basecase and recursive case and end up with a function that takes an int and returns an int. So when we apply factorial to5, we get 120 for our answer. Seems simple enough.# let rec factorial n =if n = 0 then 1 else n * factorial (n - 1);;val factorial : int → int = <fun># factorial 5;;- : int = 120But for CPS, you need to write a function that not only takes in another function that tells you what to do withyour result, but really what is going on here is that the recursion is doing some part of the computation and now thecontinuation has to tell the recursive calls how it should carry on. But usually, with recursive functions, you aren’tdone with your computation, so you have to build a new continuation in a sense, with these new values and move onfrom there.Now let’s take a look at the CPS version, piece by piece. So, like we did before, we add in the argument k in thefunction declaration.... ok simple enough, let’s move on. In the base case, we have if n = 0 then k 1. What does thismean? Well, when we get to the base case, we know we don’t want to be recursing anymore. We know we want tosend some value back to the previous calls, just like normal recursive. But now we aren’t going to only send back thevalue. We need to first give our base case to the continuation. So, since k is a function, will apply the function k tothe value 1. That returns some value and we move on. If this doesn’t make complete sense yet, let’s take a look at therecursive case and then hopefully we can connect the dots.In the recursive case we have that, like normal recursion, we are calling our recursive function factorialk with thereduced n as the first argument. Ok, so far so good. But what about k... instead of sending k or report we are writinga new function... What is this function doing? Well, it’s taking some argument m...and then multiplying what it tookin by n and sending that to the last k...# 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>To make more sense out of this, let’s look at a numerical example. We start off by making a call to factorialk.# factorialk 5 report;;Ok, looks good, what’s next? Well, next we need to we check cases and find that we are going to the recursive caseso we call...factorialk 4 (fun m → k (5 * m)) which then callsfactorialk 3 (fun m → k (4 * m)) which then callsfactorialk 2 (fun m → k (3 * m)) which then callsfactorialk 1 (fun m → k (2 * m)) which then callsfactorialk 0 (fun m → k (1 * m)) which then callsk 1...ok....what’s k at this point? Well, if we look at the call we just made, the function we sent in for k was (fun m →k (1 * m)). So we apply 1 to that function:(fun m → k (1 * m)) 1 ⇒ (k (1 * 1)) ⇒ k 1Now what’s k? Well, the call before last had k be (fun m → k (2 * m)). So we apply the 1 to that and get:(fun m → k (2 * m)) 1 ⇒ (k (2 * 1)) ⇒ k 2The value of k before that was (fun m → k (3 * m)). So apply 2 to it:(fun m → k (3 * m)) 2 ⇒ (k (3 * 2)) ⇒ k 6Next:(fun m → k (4 * m)) 6 ⇒ (k (4 * 6)) ⇒ k 24Then:2(fun m → k (5 * m)) 24 ⇒ (k (5 * 24)) ⇒ k 120Wait, there’s another k? But we just got the answer we wanted. However, …
View Full Document
Unlocking...