Hi everyone today's lecture is going to discuss another way of explaining operation semantics called Small step. Operational semantics. The relevant part of the textbook is Chapter 15 continuations. We are going to go back to this language called F A A. You now just know memorize this language. Right? This F a a has number related expressions and function related expressions. And in this language there are what Two kinds of values, numbers and closures. And this is the usual way of describing the semantics in mathematics. Right? So we explained that in this way, a value V is either number or closure V. So value V is either number or closure and the closure is a expression and environment. It's a pair of an expression and an environment Actually the expression is always this lambda expression but we just, you know, abuse the notation or just relax the definition to have expression and an environment. So you should be familiar with this until this point. How about the red part. Now that we are implementing an interpreter of F A e using cps using this continuation. We may want to describe this semantics, this interpreter implementation in on operational semantics, then what is going to be continuation? How are we going to express that? That's the question. So, semantics, if you remember in the beginning of the first part of the programming languages, of course, discourse are of course we discussed several ways of describing semantics And in these courses courses we always use big style operation semantics except this one. Yeah. Do we use another? Maybe not? I don't think that, but maybe we discuss that later. But the main point is that big step, operation semantics is easier to understand. And it's closer to a language specification description in a sense that under a given environment we evaluate an expression to a value. It's a big step on expression to a value, an expression to a value. So in between there could be some intermediate steps but the big step operation semantics does not describe that. However, we may want to represent the intermediate status then we'd like to use small step operation semantics instead of saying that, you know, an expression is evaluates to a value. We may want to say that on the expression is evaluated or reduced to under the expression that instead of a big step we may want to go small steps to see the intermittent id steps that's called small step operation semantics. And in this lecture we are going to describe the semantics of F a. Using this small step operational semantics. So as I said in the previous slide, big step operation semantics is more like this. Under this environment. We evaluate an expression to value simple. But in the small step operation semantics we are going to capture those intermediate status. How this is our new format from this to that from this pair of continuation of step to this pair of continuation and a step. In the beginning we have this K continuation and s stack and after one step. One small step. This continuation is changed to this continuation. And this steak is changed to this step? What is the continuation When you're done or in the beginning it's going to be empty continuation box. White box. And what are other continuation? Evaluate this expression kind of continuation. Is what on top of existing K on top of this K. We put this saying, interpreted the expression under this environment. Another continuation is add on top of existing K. We say add subtraction on top of this continuation. K. We say do subtraction. Finally, application on top of existing K. We say do this function call. Can you see that continuation is a list or stick whatever you call that? Yes, steak is better and it pushes work to do on top of existing K and pop the work to do next. So when we are done plus and then the next work to do is this K. The continuation. K Is a stack of work to do. Yeah, the word steak is overloaded here. So yeah, continuation. K. Is a sequence of work to do is what? Either nothing this time, red or black box or on top of the state. S we have some value. So for a given work to do and a value stag If the one step depending on the top work to do top most work to do in the continuation. We do some work then move on to the next status. Okay? You may not find it intuitive, but examples will help you understand this thing? Yeah. The easiest one is again number. What's the semantics? Yeah. The semantics is that when we have a number we make a non value and co. Okay. Again, this blue thing is a template under this. For a given this continuation at stake, we move to this one. How what's going to be the semantics of number in this small step? Operational semantics. Look at this, What does it say? You know what given S and given K. This is a continuation. That's what on top of K the work to do is what evaluate and under the environment sigma. Then what's the semantics? Yeah. Then Call k using the value, meaning that push the value to the stack and do the next thing. Push the value n on top of the given stake and pop the work to do, because we are done. Are you with me, yeah? When we have a number we evaluate that which is just num v v so pop it because we are done and push the value to the state and move on to the next work to do. How bad addition? It's slightly complex, but let's see. For an addition of l and r. We first evaluate l then evaluate r then add them and call k. So first thing to do is to split the job, can you see that? We have this inter function and here is the continuation. Oops, and here's another continuation. So we split the job to smaller pieces, how do we do that? Look at this, for a given stake s and this continuation the top continuation is, top work to do is addition. Then what do we do? Stake remains the same. But we split this job to three pieces. Evaluate e1, evaluate e2 and add them. Does it make sense? Yeah, evaluate e1 that's the first row to do. And then evaluate e2 and then add the values. So when we are done evaluating e1, we are going to push the value to stake. Then we are going to evaluate e2 push the value, under stake. Then when we finally got 2 plus we are going to get those two values, add them and push the result on the stake. Are you with me, yeah? Yeah, let's see whether what I just said is correct. Right when we are done evaluating e1 and e2 their values are going to be on the stake. So When we have plus on top of the continuation we should have two values on top of the stake. Otherwise it's the wrong code, we cannot evaluate further. Do you see that? One more time when we you see plus on top of this continuation, then we should have at least two numbers in sequence on top of the stake n2 and n1. Why is it n2 and n1 instead of n1 and n2? [LAUGH] Because what again we evaluate e1 and push it first which is going to be n1 and then evaluate 2 push it on top of that which is n2. So it's going to be n2, n1 and then s, n2, n1 and the s. Okay, when we have that we have this satisfied condition then what's next? Top two values as is m and push the results back. What is it, pop n2 and n1 and add them and push the results back like this. Then we are done this work and there's the next thing to do. So far so good, yeah? Yeah so when we have an addition we pop the work and we pop the values and push the result back. So it's going to be, k, s, on top of s, we're going to have the result. Yay, then what? Subtraction is going to be just similar, right? Yeah, when we have e1 minus e2, we are going to split this evaluation to evaluate e1, evaluate e2 and then do subtraction and stake remains the same. When we are done evaluating e1 then we are going to put n1 here, and when we are done evaluating e2 we're going to put n2 here, right? And when you see minus we're going to pop those two values and do so to n1 minus n2 and push it back, are you with me? Yeah, then let's see, right? What I just said is correct when we see this minus subtraction, we should have n2 and n1 on the stake. Then pop it, pop it, pop it and push the results back. So it's going to be k that's work to do next. On top of stake s we have this result. Yay, so far so good, yes? Then identifier, yeah that's easy, right? What do we do usually, when we evaluate on identifier, right? We look up the environment and get the value. So we're going to pop this work and get the value of sigma x and push it to the stake. So it's going to be what K is going to be the work to do next. And on top of stack we have the value of identifier x. Yeah it's an easy case. What's the next easy case, right? Function why are they easy, because they are primitive cases like numbers, identier and functions. They just make values and push them onto the stack right Then you can guess what's going to next? What's going to happen next? Yes that's it. So one more time when we evaluated function expression this is the work to do. Pop it and make a clo v lambda X dot E. Common sigma. And push it to the step and that's it. So the work to do is going to be K on top of s we have this clothing as he expected. Okay very nice. Then finally function call. Yes or as usual function call is the highlight then how can we evaluate this? Yeah one more time in function call. We have even any two. We are going to evaluate even any two. Then what are we going to do? Just like additional subtraction. Which had two sub expressions. We are going to split this work to smaller pieces. For additional subtraction. We took this expression plus E two or minus E two. And split those network two smaller pieces like ability to and then add the word subject. Just like that. Split this work to evaluate yuan evaluate E two. And then call So for a second, yeah, remember what happened for additional subtraction? When we evaluate l and r we would have those values on top of the stack, so n1 and then n2. So when we see additional course subtraction on the top of continuation we had n2 and n1 on top of stack. For function code when we evaluate e1 we push what cloV. When we evaluate e2 we push some value. So when we see this function code on top of the continuation we should have two values on top of stack. What argument value and cloV are you with me? Yeah, then let's see whether what I just said is correct. Yeah, here it is when we have a function call on top of k, on the stack we have two values argument value and cloV. That's what I promised. And what's next thing to do? Evaluate the function body, evaluate the function body. On top of which environment, on top of the environment. When the cloV was constructed add one more piece of information saying the parameter x has value V. And evaluate the function body e. [SOUND] That's what to do next. So what's going to happen when we see this function call we pop two values from stacks, the steak is going to be S. And we pop this function call but we push another work to do. What is it on k? On top of k we push this work to do. What does it say? It says that under this given environment, I mean the environment from cloV we extend the sigma to help this information saying parameter x value is argument value v. Under this environment evaluate the function body e. [SOUND] We are done. This is how we explain the semantics of function call in a small step operational semantics, okay. Yes, it's very cool. So now that we have these rules, what we are supposed to do is to have what many, many steps using the small steps. So we are going to have in the topic step operation semantics. When we evaluate an expression the rule says this is the value. But this time when we evaluate some expression we split that two smaller pieces of work to do and keeps going on, keep going on. Then when are we done or what's going to be the value? What's the relationship between big step operation semantics and small step operational semantics. Here is the thing, you look at this semantics equivalent, semantics, they are actually saying they are saying the same thing. Big step operation semantics. Small step operational semantics. They are in just different styles but telling you the same thing, the same semantics. Otherwise one of them is going to be wrong, right. They are talking about the behavior, the semantics of one language in two different styles, but they should describe the same thing, the same semantics. Yes, indeed. In the big stable presence semantic under this environment sigma when we interpret this expression e, it's going to be a value v. What does that mean in the small step operation semantics? In the beginning, in the small step operational semantics, our stack is going to be empty. Our work to do is going to be only one. What evaluate e under sigma, right. Then depending on the shape of e we're going to split the job and push the values and work to do to continuation instead and keep going on. That's going to be what RTCORR, RTCORR meaning a reflexive transitive closure of reduction relations. Meaning that when we have this k1 and s1 initial continuation instead and it goes to k2 and s2 and k2 and s2 goes to k3 and s3 da da da da until kn to sn whatever n it is. Then we can shorten this thingy to just one rule saying, hey, you know what the initial k1 and s1 will be reduced to kn and sn. This is called this reflexive transitive closure. If you are not familiar with this concept, go back to this discrete math and check the definition. And back to here this initial k and s, when we apply the small step semantics rules multiple times then at the end it's going to be what the continuation is going to be empty. No more work to do. Yeah, we're happy then on the stack there's going to be only one value v. Are you with me? Yeah, one more time in the big step operation semantics we say that under this environment sigma when we evaluate e then it's going to be resulting in value v. So simple, and actually we are going to have some deprivation to explain why. In the operation semantics we say that in this initial configuration where stack is empty and the continuation is we need this under this environment evaluate e. And we go many steps following this small steps semantics rules. Then we are going to get to this final form saying that continuation is empty. No more work to do. And on top of stack we have only one value which is the result, and they are just the same. Hey, that's awesome. Okay, hope you enjoyed this small step operational semantics. And here's an example interpretation of the expression. On the benefit of the time I will not explain every step and this is actually an exercise or to encourage you to understand this. I'll just show you as a picture what happens. So in the beginning we have this empty continuation and empty stack. When we have this function code we split the job to evaluating the first six of expression, the second sub expression and function call. And we evaluate that one by one, push the values onto the stack. And when we have a function call get the function body and evaluated, what's the function body, addition. How do we interpret an addition? Split the work and evaluate one by one and at them push the result on the top. At the end, continuation is empty, stack has only one resulting value. So I just show you the process this procedure as a picture, right. I strongly recommend you to just write the first line and write down the next steps by yourself. Okay, here's quiz. Consider the following code. This is the interpreter in continuation passing style for the function call case, right. And the following rule, the small step operation semantics for function call. Which of the following is correct for this red star, right? What do this function call on top of the stack? We have value and cloV e. What's going to be the next work for us to do? What do you think? Right, the work to do is to evaluate the function body, right? Evaluate the function body on top of the cloV environment using this information saying parameters values v. So this is going to be our continuation. Thank you. [MUSIC]
