Hi everyone. Welcome to the second part of the programming languages course. In the first part, we learned various important concepts in programming languages but without types. We learned names, functions, and higher the functions and even garbage collection. And in the second part we are going to learn continuations and types. The most important concept and the wide range of the concept of this second part is going to about types. We are going to extend and our own language with small types, primitive types to usually defined types including premature polymorphism and subtyping. So, stay tuned, and today's topic is continuations. As usual, the relevant part in the textbook is Chapter 15, Continuations. In many programming languages we have program control statements. Meaning that in the beginning of the program execution we get some input and do some of operations like this and that. And when we have some conditions we check the condition and if that's true, do this. Otherwise do something else. In imperative languages, they provide several control statements like while loops and functions. In this while loop e is a conditional expression as long as the value of e is true we do some computation multiple times. If there's a break, we break out of the loop. If there's a continue, we break the current loop and just go back to the wild loop condition. So there are various kinds of control statements in imperative languages. And in the function body while evaluating the function body, when we encounter the return statement, it just evaluates that expression e and returns the value, ignoring the remaining part of the function body. So it's easy to use some control in the program evaluation. But it's not really a good idea, because control statements changes the program control. And it is not that easy to understand and reasoning about those controls. Then, functional languages usually do not like that kind of concepts, right? Functional languages do not like mutation. Functional languages do not like these abrupt or manual control statements. Then how do functional languages represent such control diverters? That's continuations, which is the concept of today's lecture. Before diving into the formal definition of continuation, let's consider some simple example. So that I can show you how we implement this problem in the usual imperative programming languages. And how we can use continuations without using those control statements. Okay, here is a motivating example, called counting example. First, count the number of occurrences of a given word in a given file. Meaning that this is a problem and we are going to get to inputs, a word and a file. If a cached result exist, use it. If we've done this job before, then use that stored result. If the given file does not exist, return -1. If the input file is wrong and there is no such file, then return -1. Which is an error code. Finally, since the number of files is usually small and files are repeatedly accessed, checking the existence of a cached result first is more efficient than checking the existence of the given file first. This is the problem statement. How are you going to implement this problem? We are going to have some helper functions. How many? We have five helper functions, right? The first one is, cached. It checks whether a cached result exists. This function called cached takes a file name and check whether we already check this file or not. It is going to be a Boolean value, yes or no. The second helper function is called getCache. If there exists a cache, get it, for a given file name, we get the cache result which is string. The third helper function is called exists. Again, it's a predicate asking whether a given file exists. The fourth function is called read, gets a file name, read the content of the file and cache it, because it's the first time. Finally, the function called numOfWords. Counts the number of occurrences of the words in the content, right? This numOfWords actually does the job, right? It takes two inputs called content, which is the file content. And the second input is word, the word that we are counting. Okay, now you understand that we have five helper functions cached, getCache, exists, read, and numOfWords. How are we going to do our homework, right? This problem. This is the first approach using imperative programming language. Let's assume that here is an imaginary imperative language and we are going to implement the work called numOfWordsFromFile. For a given file name, we'd like to count the occurrences, the number of occurrences of this word. As the previous slide explained, we are going to check. First, we are going to get the content of the file. So it's going to be a mutation in the variable named content, initialized to be empty string. If this file is already checked before, so we have a cached result, then use the result. GetCache for the file name and store that to the content variable. If not, if this is the first time that we are checking this file, let's see whether the file exists. Otherwise, if the file does not exist, return -1. If the file actually exists, read the file, store the content to this variable, right? And finally, now that we have the content and we have the word, count the number of words in this content. So for a second, yeah, this is a usual way of doing discounting in an imperative programming language. Then let's try to use functional style. The first trial usually doesn't work, right? So, this is not working version. This is not working. But let's try because it's a functional style, we are going to have this function. It takes a fine name. It takes another forward, right? And then we do not want to use that variable, right? So, what are we going to do? Just quote the function right away. The number of words to what? This content and the word. How can you get the content? No, as usual as in the previous slide we checked whether we have already checked the file. And if it's cached, if there's a cache to result, use it. Otherwise we check whether the file exists. If it doe file does not exist return minus 1. Otherwise read name. I already told you it is not working. Why it is not working, do you know? Why it is not correct? Think. Did you get it? Yeah. This part that I just said from here to here, meant to be a value of the content. The content of a file named name. But when the five does not exist we turn minus one. It is not correct value for five content. So, this is not correct. Okay, good try. Then what can you do next? This is another version which is complex but let's try. I will explain this to you. One more time, we have this function higher the function taking a fire name and word. This time it's not a valuable but name, content and we do get the content. If the file already checked, then get the cash. Otherwise, we do return minus 1 here. Yeah, I know. We do return the content of a file, if we found the file and then checked the content. Then we now know that this content value may be actual file content or minus 1. So, after this we check whether the content is minus 1 or not. If the content is minus 1, it's an erroneous case. So, return minus 1. Otherwise, do the counting. So far so good. Yeah, but complex. I don't like it. You may not like it either. Then what can we do about it? This is a slightly better version using continuation. What is continuation? This is the concept that we are going to learn today and the following several lectures. Okay, here's a new thing from here to there. We have a new language construct called VCC. This is a valuable for current continuation. And we capture the current continuation value and name it K. That's the work to do after we are done this work. You may not get it. You may not understand what I'm talking about. Stay tuned, you're going to learn that after several lectures. So, when we have that, no matter what is what it is. Then when we have this erroneous case, instead of putting this minus one to a temporary variable called content and check the value of content. We can just pass the ever code minus 1 to this continuation K. Then we are done. It's a magic, right? Instead of going, let's see. Instead of going back to this that content thingy and check the value, right? Instead of that, we can just call the continuation K in this position. We do not need to have unnecessary wrapping or storing the value and checking the value later. We can just call the continuation with this value, then we can get out of this context. So, yeah, just take it as a magic and we'll explain how that happens. That's continuation on expression in a program that is not a value can always be partitioned into two parts. One more time. In a program we have several expressions, right? On expression, there is not a value meaning that there is an expression that is of value, right? What is the value? A value is an expression that cannot be evaluated further because it's already a value. So, an expression is either a value or not. If an expression is not a value then it should be evaluated further, right? Okay, then we can partition an expression that is not a value to two parts. The redex and the continuation. The redex is the expression that will be evaluated first. And continuation is the remaining evaluation. Does it make sense? All right. One more time. On these expression that is not a value, is going to be evaluated further. So, when we evaluate an expression there should be some thing to evaluate first and the rest. The expression that's going to be evaluated first is called redex. And the remaining work to do, is called continuation. So far so good. Yeah. Here's a concrete example. For example, when we have an expression e1 plus e2, how are we going to evaluate this? We're going to evaluate e1 plus e2 in the following steps. Number one, evaluate e1 and call the value n1. The next step is evaluate e2 and called the value n2. And return n1 plus n2. These three steps in order, that's the evaluation order. So, for this e1 plus e2 the redex e1. The first expression to evaluate. And the continuation is steps 2 and 3. The remaining evaluation. So, the continuation says how to continue after the redex is reduced to a value. So, steps 2 and 3 explain how to continue after the redex e1 is evaluated and reduced to a value. Okay. Yeah, that's it. That's the whole concept of continuation. And you may think like why are we learning this weird concept? Who is going to use continuation? Actually, continuations are used in many programming languages even C you know, C is the most widely used imperative programming language. And even see has a continuation called the set context and similar variants. Haskell has continuation Monette per Right over virgin ruby, ruby has call CC called current continuation scallop provides that scheme. Small talk. Many programming languages provide that. Actually one of my students who took this course, like several years ago, he was an undergrad at the time and after several years he worked at a company, actually a game development company. And one day he sent me an email and saying that I professor, how are you doing? You know what? I really did not like the concept continuations because it didn't sound naturally. I didn't think anyone would use it. But last week yesterday I got some job homework to do from my boss and he called, it was called quarantine or something and I searched for that and that's continuation that I learned back in when I was an undergrad. So, wow, that reminded me of you and said hi to me. Right. So continuations may not be familiar to you yet, but you may find it multiple times later. Yeah. See what's going to happen. So one more time, continuation is a work to do and we have a different style of evaluation when we use continuations and we call that continuation passing style until now Without continuation. We evaluated expressions in order we evaluated even and get the value and on evaluated it to get the value into and add them and return it right. It's a function called called pop pop like that. It's more like function called and come back. But continuation passing style does not need to return to colors one more time until now. The usual style is like function call and color is waiting for the Cali is done and come back. Hey kid do this homework. I mean do this tour and my kid is going to go to do some work and come back to me and do another thing and come back to me. This is the point to come back. Return to a color. That's the usual function called style. And using continuation passing style there's no need to return because what to do next is also passed as an another argument. So this is good for time and memory performance because we do not need to remember what's going to do next and come back and resume the computation. We do not need to remember that. So this is good for time and memory performance. And another example is for this E one plus E tube. We already said that read acts is E one, then the continuation is going to be what the remaining steps 23 so we represent it like this after evaluating the one. We are going to get its value. Let's call that LV and using L V. We are going to do this additional V two after evaluating Iwan. Then let's call that values N one, the read axes E two. Then what's the next continuation? After evaluating E two. That's going to be get the value of E two. And let's call that are too. And what ad N one the value of the yuan and this value of V two. Finally, after evaluating it to two and two, the last continuation is what adding them and returning. So this is a continuation passing style. We do not need to come back because our job to do is passed as work to do as some kind of function and pass that as another argument. Let's see what I mean. By implementing an interpreter of our lovely language called F A. Using continuation passing style. If you took the first part of this programming languages course, you must be happy to see this language again. F A With what? Numbers, addition, subtraction, automatic expressions and functions. Right. Names, function called and function expression. We call this all idiomatic expressions with functions in short. F A In in the beginning. In the previous part we explained and implemented an interpreter of F A A without using a continuation. Right? We defined this value type which has non viene clove E. Meaning that in this language, F A. There are two kinds of values numbers. Non V four numbers and clothe the foreclosures. Right. And because it has names, we used environment in this continuation passing style. We need to use another type called **** which takes a value and produces another value. And this is going to be our new function in terms. Okay. What does it do? How is it different in the previous style? This inter function takes an expression and environment and evaluate to a value In this new continuation passing style it takes an expression and an environment and continuation the work to do after evaluating this expression and return of value. How we are going to discuss that in the next lecture. And here's scripts for this lecture which of the following is incorrect. One on expression that is not a value can always be partitioned into two parts. To read acts is the expression that will be evaluated first three A continuation is the remaining evaluation for a continuation says how to continue after a tax is reduced to a variable. What is the answer? Do you get it? Write a continuation, says how to continue after a re dex is reduced to a value. Not valuable. Thank you.
