[MUSIC]. Hi everyone, welcome to the second lecture about lazy evaluation. We learned a bit weird the semantics of a language called LFAE in the previous lecture. And today we are going to improve the evaluation of that language. Improve meaning that our implementation had some issues. Did you notice that, what is it? A detailed explanation is available in Chapter 14 lazy evaluation of the textbook. The problem with our previous implementation is that it has possibly many redundant evaluation. Really? Does that make sense? We are using lazy evaluation because we want to delay, defer the evaluation until it's necessary. So we are not going to evaluate unnecessary computation. [Korean] Why do we use lazy evaluation? [Korean] For efficiency. [Korean] We have a good philosophy of [Korean] not evaluating a value that won't be used.
[Korean] But we're doing redundant evaluation. We wanted to be efficient by not evaluating unnecessary computation. And how were we doing? How did we do redundant computation? Let's look at this example. This is a quadratic example in LFAE, saying that this is a function called and the argument expression is so complex expression in the function party. We get the parameter and we use the parameter multiple times. And whenever we have this addition of those parameter values we are going to get the value of X from the environment which is going to be expr V and then what? Interpret that frozen expression multiple times, right? How many times are we going to evaluate this expression? Four times instead of one. Do you see that? So we want it to be clever but we're actually not right? In LFAE we only need to evaluate the complex expression once at function call side. We're going to evaluate the argument expression get the value, put the parameter name and argument value mapping in an environment. And whenever we see a parameter in the function body go look up the environment, get the value right there. So we evaluate the argument expression only once. In LFAE we do not evaluate that at the function call side just put that into expr V. But in the function body, if the parameter is being used multiple times, we need to evaluate the multiple times. No, this is really stupid, so what can we do? We are going to compute that only ones or less if not, if it's not used if it's used only once at most once. And we used that since the result is always the same, we do like to evaluate that at most ones. How? By remembering the value. So in the beginning we are not going to have the value for the argument expression but once we validate that expression we have a value and remember that and we use that. Meaning that we're going to have some plans to remember the value but we may have a value or not, it's optional. Do you see that? We may have a value or not. In the beginning we do not have a value but later we are going to have a value that's optional. In object oriented languages especially java, in many object oriented languages they use null type, null value to represent that. Every class can be a null value, which is convenient. But really error-prone. One of the biggest problem, biggest errors that's difficult to capture catch in java programs that's null dereference error. Even though the Java program language has a pretty well designed type system. Many errors are caught by the compiler type checker at compile time in java programs, but null dereference error is one of the notorious error that cannot be detected at compile time. If there is an error it's really difficult to catch that. [Korean] Java has a great type system. [Korean] It detects lots of bugs at compile time
[Korean] before the program runs. [Korean] It makes Java programmers really annoying. [Korean] “Don’t do that.”
[Korean] “Fix this.” [Korean] It’s annoying, [Korean] but when the compiler says “done. run it,”
[Korean] bad things hardly happen
[Korean] during the program runs.
[Korean] Because checking is so good. [Korean] But null dereference errors are [Korean] extremely hard to catch.
[Korean] It’s really difficult to
[Korean] figure out where null comes from. So it's really bad to use null values in object oriented languages. It's really a bad habit. So Java, Scala and many object oriented languages introduce option type instead of null value and they are saying please do not use null value, it's going to bite you back. So consider using an option type which is much better. What is an option type then? An option type represents optional values, it has a value or not, it's optional. Instances of options are either on instance of some with the value or the object none. So you may want to look at that site but it's not that difficult. We can construct some value and that may have type option int, meaning that this is an option type of value in teacher value of typing teacher. So when this value is has this type, it's going to be either some in teacher or none. This is an option time. And we are going to use option type to capture a value of an expr V. Let's see caching strict results. Caching meaning that remember a value and reuse that. It's all very different from caching computer organization and computer system. So don't be so obsessed about the term itself, just saying what that's what they're saying, is that we are going to remember of value of an expr V when it's first evaluated and use it later. That's what we mean by cashing. So this expr V has Value component. Previously, Expr V had only an expression and an environment. And when we have an Expr V, we evaluated this expression under this environment. And now we have a third field V, which is var. We'd like to use mutation, because the value of V in the beginning is going to be none, we do not have a value. But when we evaluate this expression for the first time, we are going to get the value and store that in this value V. Okay? Then, we are going to revise the strip function to use them, how? This is a previous function. Previously, when we have a strict function, we get a value. If it's non V clubby, return realizes it as it is. If it's Expr V, evaluate that expression. The frozen expression, under the frozen environment and then strict it. So, that's why we need to evaluate the same expression multiple times. That was the previous version. All right, yeah. Experts we had only two feels. And this time we'd like to make it better by having cash. What? Now, strict function compares this value to expert B with an expression and environment and some remember to value. So, r its time is going to be what option value. So, hey r do you have already evaluated value or not? It's going to be some or none, right? Non meaning that we haven't evaluated this expression yet. Some meaning, I already evaluate that expression and I have its value right here. Are you with me? Yeah. You know what, we already evaluated expression under this environment. And the value is this, captured in this option value cash then what are we going to do? No, yeah use it. Use the value. All right, are you with me? Yes. Just use the value. Now, we do not need to evaluate the same expression multiple times. So happy. What about the non case? I haven't evaluated the expression, this is the first time. Okay, don't worry, we just re-evaluated expression. And then remember that in this cash value and return the value. That's simple. What did I say? Yeah. First, just evaluated expression as before. As in the previous strict function, evaluate the frozen expression under the frozen environment and get the value. Yeah, it may be expertise so strictify it. And get the value, let's call it cash. Okay, so first we're good we evaluated that expression and got a value. What can we do next? We need to change this from none to some, right? Yeah. In this Expr V. Yeah, in this Expr V we'd like to replace this non value to some. That's how we can remember the value. How can they do that? Can you guess? How can you remember the value By making the third field of the value Have this one. One more time. By making this third component, EVs V component V field. EVs V field to have this new value some with the new value. And then we'll return it, return the value. See, right? We are done. So, one more time. Now that we would like to remember the value of frozen expression when we evaluate it. We extend Expr V from an expression and environment to have this place to remember the value. When we first make this exper V value, we do not have a value because we haven't evaluated the expression and we may not need to. because probably may not be used in the function body. So, make Expr V with an expression and environment and none I have nothing. And in the function body, we evaluated expression function body and we encounter the parameter X. And we we need to even get the value for addition subtraction or function call. Then, what? Trickify devaluating the argument expression. Evaluate the argument expression get the value and strictify it get the real value, right? Don't view your claw V. And remember that into this Expr V. So, later when you look up that Expr V and get the value we can get the previously evaluated value in the third field of Expr V. So far so good. Yeah. One thing to note another frequently asked question here, which is really good. Is why do we need Why do you need a ev here? I know the name of the value V. That's why I perform this pattern matching on that. Yeah, that's V. And why do I need to give it another name ev even though they are just the same? Do you understand my question? [Korean] v is v and v is ev. [Korean] They are all the same.
[Korean] Why do we give a new name ev
[Korean] instead of writing just v. Why do we need yet another name for this because it's already V? Why? Because this type is value Even we type this Expr V. Because this type is value. It could be Novi Clovi or Expr V. Because even this type is Expr V. We can say ev dot V. If we do not have this ev.v, we cannot say ev.v here because we may not have the third field V. That's why That's why we give this V to a new name, ev not and treat that as an Expr V. And we can't get ev.v here. I hope it's clear to you. Okay, then, as I said before, when we make an Expr V now we need to have an extra argument. Now, Expr V has an expression on environment and what the cash? In the beginning, what is it going to be? Yeah. We haven't evaluated this expression. We may not evaluate this expression. So, what is it? It's going to be None. There's an option there. So, this one finishes the implementation of an interpreter of LFE, with the optimization using cash Okay, so this is LFAE again. Back to the initial flight. So when we have this function call the same text is just the same for FAE and FA. So when we just look at this quick example, we don't know it's a result. Depending on its semantics experimenter or zero, righ? Even for lazy evaluation. Yeah, even for lazy evaluation, the first time is going to be always zero. Yeah, that's for sure. Because the primary is now being used in the function body. But in the second example, what's going to be the result? What's going to be the result? Is it an error or expert V? Do you see that when we have this function call? We evaluate the first part. Yeah, right? We evaluate this function first part and strictify it we get closer. We we do not evaluate the argument expression. Make expert V here and then make a map saying dysfunction parameter. X's value is expert view with this expression. In the body we have an identifyer. What's the semantics of an identify rare when you meet and identifyer in evaluating the function body. What do you do? Look up the environment excess of mapping to expert V. Are we done? That's the result of this expression. So what's the result of this expression? Expert V, do you like that? It depends, there are several ways to define the value. I mean the top level value. As I said, non viene clove are real values, numbers enclosures but expertise of fake value. It's not really a value. It's a placeholder. A temporary place to keep an expression that's not yet evaluated. So what do you want to say? Maybe we may want to close trick at the top level. After evaluating the whole expression with the last value, we may close trick, in this case it's going to be an error. That's number one semantics. Number two, we may just say that experti V is a value. I don't care. That's another exam both semantics, number three we may change or course site of the strict function. Currently we close to function in number operation and function code whenever we actually need to violate, but we may change that so that just coastal function. Whenever we look at the environment, whenever we have an identifier coast trip there looking up the environment. Yes, there are several kinds of laziness depending on where you cause trip function you may have different values. So even with lazy evaluation you may have different level of laziness and there is a language called Haskell. That's really cool language. There have been historically multiple trials to make lazy programming languages, and now I think husker is the only realistic programming language with lazy evaluation. If you're interested go for that, it's really cool. Okay, then final quiz. Consider the following LFAE code which of the following is the result of the above code. It's a function called function part has one product gets a parameter and returns some numbers and the argument expression has some weird expression. What's the result? Yeah, do we need to know the laziness of this language? Do we need to know where we call the strip function? Not really. It's zero, right? because in this code parameter is not being used in the function body. Thank you. [MUSIC]
