Hi, everyone. We learned the concept called continuations, the work to do next. Today's lecture will make it a value. Do you remember this first-class, the knee? In the first part of the problem languages course, we discussed first-class functions, saying that functions are values. They are just like numbers or strings or booleans so that functions can be passed as a function arguments or returned as function called results. Then what do we mean by first-class continuations? You got the hint. Continuations are values and we can use them as values. Wow, why do you want to do that? You may want to read Chapter 16, first-class continuations in the textbook to understand this clearly. Today, we are designing a new language called KFAE. FAE with a continuation that's called KFAE. The red syntax is the new language construct open, VCC, id, semicolon, expression, close. I often told you that when we have a new concept, we have usually two language constructs for introduction and use. Here we are introducing first-class continuations by introducing this VCC language construct. But how are we going to use it? How are we going to use continuation? When we say do k, we said call k, cause continuation is usually function. Now usually a continuation value is a function. Here we can introduce a new name called ID as a current continuation, and we may use it in the function body. This is a concrete example, open VCC k, meaning that, hey, I'm introducing a new name called k, which represents whose value is the current continuation. Current continuity meaning what? The work to do after evaluating this expression. What is k's value here? Oh, that's going to be the top-level initial continuation because this is the beginning of this expression. Do you remember what the initial continuation is? That's the identity function. Meaning when we call k with some value, we are going to return it and that's done. Are you with me? Yes, let's do this. Here we say that I'm evaluating this expression, but I'm going to catch the current continuation and call it k. That's what we mean by VCC k. Then evaluate this expression. Why? Evaluating this expression, I may encounter k and call it or pass it as a function argument, then the value of k is going to be what? Return it. Returns the value. What's the expression? Is an addition of 1 plus k core or k2. What core k with the Argument 2 meaning return 2. I have 1 plus, ignore that. Return 2. That's the semantics. The result is going to be two. Wow, very weird to me. That's the semantics. How about this expression? Slightly complex, but don't worry, we can do this. Here we are introducing this new name, done, whose value is going to be the current continuation. One more time, the value of done is going to be what? Get the value and return it as it is. What's next? This is a function call with the argument 3. We capture this moment as esc. Then what's the value of esc? It's going to get the value and call that using the Argument 3. That's going to be our continuation. That's enough. We have two continuations done in the esc. Next thing is going to be a continuation called done. Then I'm going to evaluate this argument value, argument part, and return value and value. This's what I'm going to do. What's next? It's going to be an audition of 1 plus this expression's value. What is the value of this expression? Capture k. K is what? K is doing the other thing. What are we going to do? Core or continuation using the continuation. What does esc do? Calling the argument using Value 3. What's the argument? The k is the work what? Get the value and add 1. Then we are going to call k which increments by one. Using which argument? Three. The result is going to be what? Four. That sounds crazy, I understand that and I reveal it's not that intuitive, but after explaining the semantics of this language in Scala implementation and operational semantics, I hope you can understand the semantics and come back to these two examples and see why and explain why by yourself. Then here's our implementation, one more time we are defining a new language called KFAE and it has only one new language construct called Vcc and I said it captures the concatination and give it a name and it has a sub-expression b and while evaluating this expression b, we may encounter, we may use this name then the value of the name is going to be the concatination and we saw two small examples as a way to explain the semantics. That's the first trial to explain the semantics of KFAE. The second trial is to implement an interpreter of KFAE to explain the semantics of Vcc, the language construct called Vcc more clearly. This Vcc takes two parameters, the name for the concantination and b, to evaluate that expression. Another cool thing is what as I promised, we are making our first-class continuation in this language called KFAE. Now we have three values, not two but three NumV and CloV the usual values and the new value for continuation ContV, NumV takes a number, CloV, takes the parameter name paddy expression and environment ContV takes a continuation. Not surprising so far so good then let's implement its semantics before that actually, we are going to use continuation by what Calling K. Then we need to revise the semantics of a function call in FAE because there were two values NunV and CloV this version was okay but in KFAE, we have the third value called ContV, which is going to be called by function called syntax remember, you remember that K2, we're not exactly like this, but something like this. Calling K with some number 2 calling done, which is a continuation with another continuation value, that thing, it's just a function called syntax. When we have function calls syntax of FNA, it could be either CloV, work ContV. One more time In KFAE, we have three values. If the value of F is NumV, it's an error CloV we know how to do that ContV, how are we going to evaluate this continuation. ContV is a continuation value which captures what, continuation. Continuation is a function, there's nothing special about this, this is a function we have an argument value so what are we going to do, you know what to do, just call it. As I said, just call k, just call this continuation kv with argument av. That simple, this is the semantic self continuation call. Now we know how to use it how can we make it we have this Vcc. We are introducing a name called x, whose value is going to be the work to do after evaluating this expression and then using that information, evaluate the expression P. How are we going to do, how are we going to do that this is what I said. We are going to interpret this expression B under which environment Under the given environment, we add this information saying, you know what, this is a new name for continuation, its value is going to be ContV. What's the value of x the work to do after evaluating Vcc what's the work to do after evaluating Vcc expression what do you think It's right there what are we supposed to do after evaluating Vcc what are we supposed to do after evaluating this expression, e. What's the value of x? The current continuation, k. After evaluating this expression, what's next thing to do? K. Are you with me? Yeah, it's that simple. The value of x is k and the work to do next is k. This is how we implement the magic. This was the second trial to explain the semantics of Vcc. Now, the third last trial to explain the same thing. Are you with me? I'm trying to explain the semantics of Vcc, the semantics of KFAE with this first-class continuation to you. The first trial was using concrete examples and in prose. The second trial was using this color implementation. Now the third trial is to use mathematics. Let's see, what's the semantics of this Vcc x e. I know that we need to extend the value definition. We need to extend the value definition. Actually in this color implementation, we extended this value definition to contain Control V for continuation. This continuation was what? Lambda. Now in this small step operational semantics, we are going to add the third value continuation as a pair of continuation and a stack. Now value V is a number, a closure, or a continuation. A continuation is now what? A pair of continuation stack and value stack. Are you with me? Then, how can we explain this semantics? Let's see. Let's review how we describe the semantics of function call in these small step operation semantics, and then try to describe the semantics of continuation call in this small step, operational semantics. Then let's see. When we have a function call, what we need to do is to split the work, saying, hey, evaluate e_1 and then evaluate e_2 and then call. That remains the same for a function call of e and function call of ContV. Then for function call, we say that how is it a function call? Then when we see this cosine on top of the stack, we should have call of e and argument value. Then we can evaluate the function body. How about ContV? When we see this function call? When we see this function call, on top of the stack, we need continuation instead of call of e. We need continuation here and some value. Then, what are we supposed to do? Instead of evaluating function body, we're going to call k, call continuation. This is going to be the rule that we'd like to describe. Are you with me? This is the semantics that we'd like to describe, how are we going to describe that? This is it. This is what we want to specify. What's that? Let's see. When we have this function call. We say evaluate e_1, evaluate e_2, and then call. After evaluating e_1, we push the value onto the stack. That should be some continuation. After evaluating e_2, we push the value onto the stack, that's some value. Then let's call. When we have call, we have two values on top of the stack, argument value and a continuation. This is how we express a continuing value and then a value on top of the stack. So far, so good? Then the last thing to do is to represent call k. Meaning what? Call that continuation. What do you mean by call the continuation? Meaning that the next thing to do is this k prime. Oh, really. What about this k that I have been accumulated? Forget that. We are not going to evaluate it, we're going to throw that away, burn the bridge, there's no way to go back. Just, throw away the value stack as well and just focus on this new thing meaning that we are going to call k prime on top of that s prime we put this new value v, that's it. This is the beauty of, calling continuation. Are you with me? One more time. When we have this function core, and we have this no current k and s, the current continuation, and current value stack. This is what we've been evaluating. Now next thing to do is what? Calling this continuation k prime, and s prime. Then this is the moment that we can forget the past, and move on to a new continuation. [inaudible] We are going to get rid of the current continuation, and just what? Call the new continuation. Call the new continuation k prime, on top of s prime we have this argument value. This is the semantics. Yes. If you don't understand this think more, and read the textbook it's going to be helpful. Then finally introducing VCC is not that difficult. What are we going to do? This is the semantics when we have value stack, and k we have this VCC expression. Then what are we going to do? Still these remains the same but we split the work. We change the work saying that we are going to interpret the expression e but the environment is extended saying that what, x's value is our current continuation k, and s. Not surprising, right? This is the semantics of VCC. Now yet another example run of this small step operational semantics. I gave you this one plus open VCC X semicolon, open X, 2 close minus 42 close. It has addition, subtraction function call, and actually continuation call. It has many cool important length to features, and I already gave you this answer. Again, I strongly recommend you to hide the answer, and try to write down these small steps by yourself. It's going to really help you understand the material. Good luck. Contrast statements in the beginning lecture of introducing, and explaining continuation, and control statements I told you that those return statements, and break continuous statements are control statements in imperative languages. Here I showed you like, not really formal way of describing return statement, and break continuous statement using continuations. Meaning that, in the imperative programming languages we have several language constructs for control statements but in functional languages just by using VCC can express them all. Now here's quiz. Which of the following results in an error? This time the quiz shows you several expressions, and here's an answer. Actually an answer for every sub-expression. Again, I strongly recommend you to evaluate these expressions just following this small steps semantics. Then you are going to learn these examples, and you are going to learn the semantics of first class continuations clearly. Thank you.
