Hi, Welcome to the second lecture about Continuation. The title of this lecture is Continuation Passing Style. The relevant part of the textbook is Chapter 15 continuations. As usual, the textbook will explain the concept very nicely in detail. As we explained at the end of previous lecture, this lecture, will implement an interpreter of the language called FAE using continuation passing style, in short, CPS. Without CPS, the usual style. The inter function takes an expression and on the environment and evaluates to a value, meaning that under an environment Sigma, we evaluate an expression e to a value. But using this new style called the continuation passing style, it's going to be different. The inter function will take an expression and an environment. In addition to them, it's going to take the third input called continuation, the work to do after evaluating this expression to a value. How is that? Let's see. The usual easy case is going to be what? A number. When we have a number n how do we evaluate it to a value? Just by constructing a value for number num v, num v n. When we have the value num v n, What's next? What are we going to do with the value number? Let's see one more time. We said that this inter function says after evaluating this expression number n under this environment e and get a value num v n. What the work to the next is k. What are we supposed to do is to evaluate this to a value num v and do k. How do we say do k? Can you guess it? Using this num v n we are going to do k by calling k. Are you with me? Remember, we said that this k is cont, it was a new type from value to value? Meaning that it's a function taking a value and producing another value. Using the value of this expression e num v n we're going to do k. We are going to call k using this value. So far so good this is the basic of continuous passing style. When you have an expression evaluates to a value, we get the value and call k with that. So far so good. If you understood this, the next one is going to be easy. How about an identifier? How do we get the value of an identifier? You know that right from this environment. Look up the environment. We get the value and when we have a value of this identifier, what's next? Do k by calling k. So far so good. Then what's the next easy case? Function expression. You see the pattern. Number, identifier, a function, they are basic primitive cases when we construct values. When we make values. In FAE, there are two kinds of values, num v and cloV. Number for the term v. Identifier gets the value from the environment function for cloV. Again, when we have a failure cloV, be, use the value to call k. So far so good. That's good because we are now done the easy part. What's the next when we have subsequent function calls of inter with num, ID and fun, we did not need to recursively call the inter function because they are just constructing values and call k. But with addition, subtraction and function call. We need to call this inter-function recursively for our sub-expressions. In the add expression, we have two sub-expressions, l and r. The usual thing is what? We interpret the first sub expression, l, get the value. Then evaluate the second sub-expression r get the value, then add those two values. That's the usual case. But in this new continuation passing style, the interp function takes three arguments. The expression to evaluate l, the environment, env, and the work to do next. After evaluating the first subexpression l, what are we supposed to do next? That should be the third argument. What is it going to be? That's the question. Do you have any guess? Can you guess what it is? It's going to be a continuation. The type says that. The type says when when you call this interp function, the first argument is going to be an expression. The second argument is going to be an environment, and the third argument is going to be continuation whose type is Cont, which is a function from value to value, remember? When we evaluate this first subexpression l under this environment env to some value, we are going to use the value to call the third argument because that's the continuation. Again, the continuation is the work to do after evaluating the redux. One more time. This is the continuation the work to do next after evaluating this redux to a value and using the value because we're going to use the value of this redux that's called lv and do the job. What is the next work to do evaluating the second subexpression. Isn't it cool? Then what's the continuation for the second call of the interp? When we evaluating this second set of expression r, what are we supposed to do next? Can you think? It's going to be similar to the current continuation? Let's get it. This interp function, we have this continuation which is a function that takes a value of this first subexpression. It's going to be highly likely that this third argument is going to be yet another continuation, taking a value from this r and do the remaining work. What is it going to be? Like this, just like what I said. This is the second continuation. It takes the value of the second subexpression and now we have two values, lv and rv, and add them. When you're done with all these addition, we evaluate l and get the value lv. We evaluated r get the value rv and we added it up, and now we have this result, what's next? What are we supposed to do next? Do you see that? Yeah, call k. That's what we're supposed to do after evaluating this addition. Yes, it's cool. We are going to call what? K. We are going to call k using this value. This is the second easy case. The first easy case was what? Those values, numbers, ID, and functions. Now when we have recursive call of interp, we can have this continuation. We can construct continuation like this Lambda expressions to capture what to do next. Is it clear? Hope that makes sense to you. How about subtraction? Just the same. For you, I will read the code one more time. When we interpret an expression happen to be subtraction of l and r, under this environment. When we evaluate this expression, which is this case subtraction, we are going to get the value and call k. That's what this interp function says. The interp function says that we are going to get an expression and an environment. We're going to evaluate this expression under this environment, get the value and using the value call k. That's the whole thing to do. When we have a subtraction expression, we are going to interpret the first sub-expression under the given environment and this is going to be work to do after evaluating the first subexpression. What is the next thing to do? When we have the value of the first sub-expression, we interpret the second sub expression under the given same environment and this is the work to do after that. What's that again? After evaluating the second sub-expression, we get the value rv, and now that we have two values, lv and rv, add them and now this is the point when we're done evaluating under env. What's next? Call k by using this value. We are done. So far, so good. Yeah, hopefully. Then the usual thing. The usually most important and slightly difficult case is function call. Function call is what? App. Function application takes two expressions, f for expression evaluating to a CloV function and a is an argument expression. We first evaluate the first sub expression f get the function value CloV we evaluate the second sub expression a get the value for argument. Remember what's next? We have this CloV and argument value. We are going to evaluate the function body. Where do you get the function body? From CloV and do the remaining thing. We're going to get to there in a minute but again, one more time. In this code we have this intro function we are going to evaluate f first under this environment what's next? It's going to be, you should know now. Lambda expression that takes of value for this f and to the remaining work to do. Then how would it look like? Yes. Just like addition and subtraction. This time we evaluate the first sub expression and get the value function value. We evaluate the second sub expression and get the value av. Now what? In addition, after evaluating the first and second sub-expression we added the values. In subtraction after evaluating the first and second sub-expressions we subtracted the value. Function call what's next? We need to get the CloV and evaluate the body expression. We need to check, hey, fv are you CloV or not? If not it's an error. Yeah, there could be such a case. We check, hey, fv, are you CloV or not? Oh, no, I'm NumV it's an error. I'm not CloV. Really? Then we know that CloV has three pieces of information, parameter name, body expression and an environment when this CloV was constructed. Remember, then what's next? We are going to evaluate this function body under which environment? Under the environment that's on top of this fenv, we have another piece of information saying the parameter p's value is this av. Under that extended environment we're going to evaluate this function body. Are we done? Really? One more thing to do. When we are done with evaluating this function body what's next? In this lecture if I ask questions most of the time the answer is call k. When we're done evaluating the function body, meaning when we're done evaluating this function call expression, meaning when we're done with evaluating this expression. What's next? Call k? Let's do this. How? When we have this closure v we know that we are going to interpret this function body b under which environment? Under this extended environment. On top of this fenv we add this information saying, the parameter p has this argument value. When we're done evaluating function body under this nice environment, what's the next thing to do? That's this dot. Do you know the answer? Let me say one more time. When we interpret this expression which is a function call what do we do? We evaluate the first sub-expression, the second sub expression, check whether the first expression's value is CloV or not, if it's CloV evaluate the function body and when we are done evaluating this expression then the work to do next is call k. The work to do next after evaluating this function body p is what? Yes. Call k. Are you with me? Now there is a frequently asked question about this code. Is this the only possible or only correct implementation of function call in CPS for FAE? What do you think? Can you think about another way of implementing this version? It's going to be what? It should result in the same value for a valid expression. It may have a different point to signal an error. What I just said is a hint. One more time in this version, in function call, we have two sub-expressions f and a. In this column version, we first evaluated the first sub expression f and we just evaluated the second sub-expression a, get the value. Then we checked whether this fv, the value of the first sub-expression is CloV or not. Do see the hint. Yes. Even before evaluating the second sub-expression a, we can check whether fv is CloV or not. When f's value is not CloV it's an error. Clearly an error. We do not need to evaluate the second sub-expression a, which may be better in terms of optimization because we do not even use the value av because there is an error. Why do we want to evaluate a? It's a very valid question. It's not really difficult. I recommend you to revise this code to do the version. Which version again, evaluate the first sub-expression f, get the value fv, and check whether fv is CloV or not. If fv is CloV, then interpret a. Then evaluate the function body. Do you see that? Yes, try that. Then we're almost done but not quite because this inter-function takes an expression in an environment and not continuation. In the previous version, without continuation, the inter-function took on expression and an environment and resulted in a value. As I said before under this environment Sigma we evaluate expression e and result in a value. In this continuation passing style what's going to be the initial k that we can call it in the beginning. There is no k here. What's going to be that continuation k. We need that to evaluate, to initiate that. How do we start calling inter with a continuation in the beginning, in the top level. Do you the see the question? Yes. Look at this. When we interpret this expression, actually in the beginning, the actual input is just what? FAE expression. Then we pass it to get this abstract syntax expression FAE. The initial environment is empty because there's no name information. Finally, the initial top-level continuation is going to be the identity function. Meaning that when you evaluate this expression, the whole program under this empty environment, you're going to get the value. That was do next. After evaluating though entire program the expression and you got the value for that program, what are you up to now? Return it because we're done. That's why the initial, the top-level continuation is identity. It's that awesome. Now here's time for quiz. Consider the following code that we just saw. Which of the following is incorrect? One, str. This str is an expression to interpret. Two FAE str. This FAE str is a concrete syntax of the expression str. Three Map open close is the initial empty environment. Four x arrow x is the initial continuation. What's the answer? Str is an expression to interpret that input. FAE str is calling a parser to translate this string to an abstract syntax of the expression and empty environment and the initial identity continuation. Thank you.
