Hi everyone. Today's topic is Lazy Evaluation. Lazy. What is it? Does that mean that we have been eager and diligent? You will see what we mean by a lazy evaluation. In Chapter 14 in the textbook, lazy evaluation will explain the concept really thoughtfully, carefully, in detail. Then Scala vs algebra. Scala or other programming languages you like Python, Java, C. In those programming languages, we have a specific order for evaluating sub-expressions. When we have open 4 times 3 close plus open 8 minus 7, close, close. We usually evaluate this arithmetic expression from what? Inner to outer, left to right. So we first do that 4 times 3, which is 12, and then what? Inner first, 8 minus 7 which is 1 and add 12 and 1. That's the usual order of evaluation in most programming languages. But in mathematics, such order does not matter because in mathematics, they are what commutative. [Korean] It's commutative. The order does not matter, so whether we do 4 times 3 first or 8 minus 7 first, it doesn't matter, and it does not specify the order. In mathematics, if we have two functions, f and g, f takes two parameters but ignore the second parameter, it just returns the first parameter and g is really complex function. Then in mathematics, we do not care about this weird looking g calls, because this function f will not use that and we can go straight to 17, that's the answer. But in programs, maybe not. Because in programs we just evaluate them right away. Languages like Scala, Java, and C, and you're highly likely your favorite languages are called Eager, and the expression is evaluated when it is encountered. Whenever we see an expression we just evaluate it. Fairly diligent and eager, that's eager evaluation. But there are some languages that are lazy. Languages that avoid unnecessary work are called Lazy. An expression is evaluated only if its result is needed. It's not like evaluating expression right away. We need to evaluate an expression? But I don't know whether I'm going to use the value of this expression or not. Let's leave it as it is and defer the evaluation until we really need the value. That's lazy. Do you like it? Isn't it cool? Yeah, laziness is the virtue of programmers. We can make good programs so that we do not need to work by ourselves. [Korean] Programmers and the advance in technology are [Korean] to make tools, programs, and robots work on
[Korean] tasks that humans don't want to do.
[Korean] Laziness is good for efficiency.
[Korean] But there's no free lunch.
[Korean] There must be something. Let's see, this is our language for today, LFAE, Lazy FAE. Do you see the syntax? When you see the syntax, what's new to you? [Korean] You've just seen the syntax [Korean] of a new language.
[Korean] Isn't it weird?
This is a new syntax for new language called LFAE, but we do not have a new language features. It has numbers, addition and subtraction just like AE, arithmetic expression. It has identifiers function called and function expression just like FAE. That's it. This is called LFAE. Yes, meaning that this FAE and LFAE share the same syntax but different semantics. When you say f, 3 in C, in Java, in Scala, in some other language, say Haskell, even though you share this syntax, they may have different semantics and there are different languages. [Korean] We're making a new language LFAE, [Korean] but its syntax is the same.
Wow, what does that mean? That means that when we write some code, it's not clear whether that's FAE or LFAE, unless the person who wrote the code says. The more important thing is that their results may be different. If those two expressions are evaluated in FAE, what's going to be the result? What do you think? This is going to be function expression. It's going to give us CloV. This is the function call. Let's evaluate the argument expression, which is an addition of number N or function expression. What's the result? One plus this function expression. What's the result? Yeah, error. We don't know how to add a number to a function value in FAE. But in LFAE, that's a bit different. You know what? In LFAE, we have this function call, function part, and argument expression then we first think this argument expression, the value of this argument expression may not be used in the function body. That's how we are lazy. [Korean] We don't know whether this value [Korean] will be used or not.
[Korean] Then, do you really need to
[Korean] evaluate it right now? we don't know whether we're going to use the value of this expression in the function body or not. I don't feel like evaluating it right away. Defer the valuation until when it's needed. Actually in the first line, when we just pass this expression as it is to the function, the party does now use the value of the parameter. Does it returns as zero as it is, and we are done. The result is going to be zero instead of one error. In the second expression, the x is being used here, but it's just returns its zeros. Are we using it or not? With LFAE not FAE, with FAE, two expressions that are going to error. But the first one, LFAE, will give us a value of zero because we're not evaluating the argument expression with the second one it depends, depends on how lazy we are. This is the language LFAE. The semantics of LFAE, the semantics of function call, and LFAE is like they didn't have a function called f and a. Evaluate F, it's going to be some function part. Do not evaluate argument expression and freeze that expression as it is and what the parameters value is going to be. Take expressions very if we need to use that and then evaluate the function body. Wow, then how can they implement the semantics? What we just said is, we need to explicitly delay interpretation of argument expressions when we have a function call over f and a, we do not want to interpret this expression. No, we do not want to interpret this expression. We want to delay that evaluation of that expression. How? By introducing a new value, in this LFA expression, we do not have a new expression, no new language if feature but you value ExprV. ExprV has two fields, the expression, the argument expression, and the environment when we have this function call. Later, when we need the value of this argument expression, we are going to evaluate that expression under this environment. This is a new way. Isn't it cool? Yes. We introduced a new value called ExprV. The ExprV has two fields. One expression, the argument expression, two, the environment. Later when we need the value of this expression, we cannot use the environment at the time because that environment may be different from this current environment. We need to capture the environment as it is. ExprV freezes an expression and environment at this function call site. We capture the argument expression and the environment at the function calls side freeze it inside this ExprV and pass it the function party and evaluated argument expression when we need its value. Before moving on, please note that environment and laziness are different. Some students ask like, environment also differs, replacing the values of parameters in the function body using the environment. When we evaluate a function body, instead of replacing every occurrence of a parameter with argument value, we keep the information in an environment. Whenever we encounter an identifier, we look up the environment and get the value. It's deflating the value of an identifier by using an internal environment. Is it similar to laziness? That's frequently asked a question, if we learn substitution, we did not learn substitution in this lecture but if you are interested in programming language, the concepts and theory, then I strongly recommend you to look for substitution instead of using the environment. But if you don't know that, that's okay and the more important thing is that using environment is not being lazy. Even when we use environment, we evaluate an expression and get its value and keep that information in an environment, meaning that an environment maps names to their values, not frozen expression. In lazy evaluation, in a function call, when we find the value of a parameter, instead of evaluating the argument expression right there, we freeze the argument expression and its environment into ExprV new value and map that in the environment. Hopefully, it makes it clear to you. Another thing to note is that short-circuiting is not being lazy. Do you know what short-circuiting is? Short circuiting meaning that in many programming languages like C and Java and many others, when we have these word logical AND, and logical OR the language semantics allows not to evaluate the second sub-expression when the value of the first sub-expression is special. One more time. In short-circuiting semantics when our language has this first circuiting semantics, that language provides this logical AND, and logical OR, and the language semantics allows not to evaluate the second subexpression when the first W expression has specific value, meaning if you remember a truth table, [Korean] you must have learned it in high school. when you have logical end. If the value of the first sub-expression is false, no matter what the value of e_2, it's going to be false. With this logical OR if the value of e_1 is true, no matter what the value of e_2 is it's going to be true. Some languages allow that. If the value of unit is false with this logical end do not evaluate it. With logical OR if the value of e1 is true, then do not evaluate e2. That's called short-circuiting. It's not being lazy, it's just not evaluating the second sub expression in some situation. It's one of those frequently asked questions. Then forcing evaluation for normal operations, meaning that when do we need a value? That's the question. Let's see. In order to understand that, let's look at this code example. This is what? A function call. Let's look at function call. Here this is function part F, this is argument part A and the environment is empty. Let's evaluate this, interpret the function part. Then we're going to have CloV. For the argument expression, we are not going to interpret that and we're going to make this new value ExprV, capturing this argument expression and the environment. That's going to be our new value, Av. We are going to interpret the function body in this static environment, we add this mapping saying parameter value is what? This ExprV. Are you with me? Let's do this one more time. What is fv? CloV. What is the AV ExprV. What does it look like? It's like this. Are you with me? CloV parameter is X, Pi d is 1 plus x, environment is empty. Argument is ExprV, capturing an expression 10 and the environment empty. So far so good. Using the information, what's next? The next thing is to know make an environment, new environment. On top of fenv which is empty, we add the information saying the parameter X has value av, value ExprV in the map. Then what do we have here? In the map, the parameter X has this ExprV. Using this information, let's evaluate the function body. Using the information parameter X has a value ExprV. Evaluate the function body which is 1 plus X. Then we need to evaluate 1 plus X. We better know how to evaluate that. Let's look at this audition case. Audition case? We need to interpret first expression, which is one seconds of expression, which is X. What's the value of 1 Numv 1, which was the value of X? What's the value of X? ExprV. How are we going to add NumV and ExprV? How are we going to add them? No, we cannot do that. It's an error. Yeah, no surprise. This is the place where we need the value of the argument expression. In the beginning, we said, I don't feel like evaluating the argument expression, because it may not be used. But actually it's being used in the function body. It's being used right here in addition. We need a value, how can we say that? Hey, ExprV, give me the value. That's called strict. Hey, Lazy, be strict, be eager to evaluate that expression. When we do that addition or subtraction or those number operator, we are going to strictify the value. Then what's the strict function? This is the strict function. The strict function takes a value, if it's NumV or a closure V, return it as it is, because it's already a value. If it's ExprV, strict meaning, give me extra value. ExprV is a fake value. Give me the real value, the env or closure V. That's what this strict function does. Strict function takes a value which could be NumV, or CloV, or ExprV, and returns another value which is not an ExprV. If it's ExprV, this is the time to interpret it. Interpret that frozen expression under that frozen environment, get the value, and strict it again. Really, why? Isn't it enough to just interpret it? What about the result of this one is, again, ExprV. Then we don't like it. We need NumV or CloV. That's why we have this nested function call. I strongly recommend you to write some code example that requires this nested strict function call. This is important. I'm going to repeat this in Korean and again in English. This is my challenge to you. Write down some code example which produces ExprV, and when we call strict function on that ExprV, it's going to initiate another that's typical for this strict function. If you can do that, you understand this material. Good luck. Now that we have how to ask for the real value, we need to fix this version as well. Did you notice that? The previous implementation was wrong, because the result of interpreting this function part, maybe ExprV. We need to cause two functions here as well to get CloV, because we need it. One more time. In LFAE, we freeze an expression and that an environment, a function call site onto the value of that expression is needed. When do we need the value of that frozen expression? When we perform some value computation like addition, subtraction on NumV, or a function call on CloV. Because in this language LFAE, we have three values, NumV, CloV, and ExprV, but ExprV is a fake value, just you know, temporary capturing, freezing expression and the environment value, so we don't really care. Actual values are what? NumV and CloV. When do we need numbers? For addition and subtraction. When do we use CloV? For function call. That's why we call strict function for a number operation and function call. Yes, that's the secret. Now the quiz. Consider the following code. That's the function that we just implemented. The strict function takes a value which could be NumV, CloV, or ExprV, and if the argument value is NumV or CloV, return it as it is. If the argument value is ExprV, what are we going to do? That's the question. Which of the following is the correct answer for that? Return it as it is, calls to function on that, interpret that expression and the environment, or interpret and then calls to function. What is it? Yes, the last one. We need to interpret the frozen expression under the frozen environment, get the value which may be ExprV. So call this strict function again. If the result of this evaluation is not ExprV, this nested string function call, will just return the value as it is. No problem there. Thank you.
