Now, let's implement first-class functions in the language called FVAE. If you have any difficulties in understanding this material, please read Chapter 9 of the textbook, first-class functions. We were implementing the interpreter of FVAE in the previous lecture. Now, let's start the most important thing. What? Fun and app. In the last lecture, we change it, the usual interrupt function implementation in the sense that the result is not into anymore. Onto FVAE, the result of the inter function was all numbers, integers, but now, the functions are values in FVAE, the results could be non-numbers, which are functions. We had to extend the return type to expert, and we had to return num n and we had to devise this addition and subtraction to use numAdd and numSub. But they are all secondary issues. The main thing is, what is the function value, and what is the function call? Yes. Let's try to understand its semantics first with some concrete examples. Let's see, we have the usual valid expression, y is 10. Then I'm going to put that information into the blue box, y is 10. How about this one. The next one is function call and the first part is function expression, whose parameter is y the argument expression actual value is 10. We're going to pass 10 to function parameter y, which is going to make this y is 10 in the blue box. But how can you capture that? Do you see the problem? These two examples actually represent the same thing. When we interpret some function expression. In the function expression party, we have a free identifier, but actually, that's not a free identifier ever because that name is already introduced with some value. Are you with me? I'm going to show you what I just said with the example again. Here, which one is better? Let's look at this from here to there. We know that y is binding here and this is a bound occurrence of y, its just in a normal correct code from here to there, we introduced y, and we'd like to use y here. If you look at this function expression open-close, x is a parameter and the function body we have open y plus x close. The thing is this, x is a parameter, but what is y? Is it a free identifier error just like before in FVAE? Not really because this y is already introduced here. We'd like to keep that information in this blue box. How can we do that? How can you capture that? That's the question. Let's see one more example. Here, in this example, we have y is 10, and we have this function expression. This is going to be the whole expression that we just saw before and then this is the argument part. Argument part says, y is 7 and y. We know the y is 7, into the blue box, and y is the value is a 7. That's the usual way of introducing name and using name. Then how about function part. We'd like to do the same thing here, y is 10 and I'm evaluating this function expression where x is parameter, but what's the y's value? It's 10. Then how can I capture that in this function expression? In this function expression, I'd like to keep that information the y is 10. How can we do that? That's the question. Do you see the need? Do you see why we need to do that? Yeah, so a function expression itself is not enough. In the previous lecture, I told you that we have to extend the value set from numbers to expressions because not only numbers but functions are values as well. In the previous lecture, we used x-bar as the return type of inter. But if you remember, I told you that, that's not really correct and we're going to fix that today here in this lecture. How? By defining a new type called value. So that functions can capture that blue box. Why do we define value again? Because there are two kinds of values, number values and function values. We will need to use a function expression to represent function value. But that was not enough because function expression has this parameter name and body expression, but not the blue box. We need a new special value to capture the blue box. Let's see, FVAE values. A function value needs to keep its substitution cache or environment or blue box. We defined a new value type which has two kinds, number or closure. We call that closure. That's a function value. NumV has an integer. No surprise there. CloV has three pieces of information, parameter name, body expression, and the blue box. Parameter name, body expression, and the environment when this function value is constructed. Parameter name, body expression, and the environment when this CloV is constructed. Are you with me? We're going to see examples, don't worry. Again, environment is a mapping from names to their values. Let's see. When we have this expression saying that y's value is ten, put that into the blue box. This is closure V. Parameter name, body expression, and the environment when this function expression is going to be evaluated. That's going to be the CloV. It's going to be CloV because it's a function value. Which contains what? Parameter name x, body expression, that addition, environment, y is ten. That's what I just said. Parameter name x, body expression y plus x, environment, y is ten. Are you with me? The value of this function expression is now parameter name, body expression, and this environment. This is our new value, CloV. Welcome. You'd better be familiar with this new value because we are going to use this CloV till the end of this lecture. I mean, not only this lecture, this course. CloV is going to be with us until the end of this course, so you'd better spend some time now to understand that better. One more time. In this language, we have two kinds of values, NumV and CloV. Later when we extend the language more with different features like mutation, exception, and things like that, we may have different values, but now we have only two, NumV and CloV. NumV for numbers, CloV for functions. NumV for number, so it has numbers. CloV for functions, so it has parameter name, body expression, and the environment when the function is being defined. Why do we need that environment the function is being defined? As we saw, the concrete example in the previous slide in the function body there may be some names. Obvious name is its parameter. In function expressions, in FVAE, because functions are not special kinds in different words. They are just expressions. Functions are expressions. When we interpret functions they produce values. They may be embedded inside some value expression. Val x equals what? Val y equals what? Nested fields and then some expression which is a function expression. Then in the function body we may have parameter name but also those names introduced outside like x and y and things like that. There are now three identifiers. They are bound identifiers because they are binding occurrences outside. When we construct our closure value from this function expression we need to keep that information. Those values of captured identifiers in the function value. {FOREIGN} Those names were introduced outside of function expressions but they are captured in the function body. We need to keep their values in this special cash environment. That's why we need this third component, third field of clove. First again, please, I hope you understand this. Let's move on, finally. Then let's continue function expression. Function has a parameter name by the expression and the environment. I like that because that's what I spent several minutes to explain in the previous slide. To apply, interpret the function body with a given argument. Then how do we do that? When we interpret this function body we need to know the value of y and x. It's going to be y is 10, that's the captured environment, and x is 7, is from the coal set, x the parameter x's value is given a function called side argument 7. Now that we understood how it works let's implement that. Before implementing the fun and EP case let's fix those bits that we used before. What? remember we used the expert before because we didn't have value, which is wrong. Let's get rid of it. The return type is going to be now value. Instead of e, we returned the e before because there isn't was expert. Now it's going to be NumV. Instead the NumAdd ends up at, now it's going to be numVAdd and numVSub. I think that you can implement that. Try it. Finally, a function expression and a function call. What are we supposed to do? Function case is easy because it's going to be CloV with parameter name, paddy expression, and the environment when this function is being constructed. This is that environment. That easy. Just like when we have a number we construct NumV, when we have a function expression, we construct CloV base case. How about function call? Let's interpret f and a. You know this. Interpret f, does that make sense? In F_1VAE when we have f, a f was string. We had to look up the definitions of functions. But now in FVAE, f is an expression, it's not a string anymore. We are going to interpret f, we're going to interpret a. So far so good? Then what's next? When we interpret this function expression we know it's going to be CloV or not. One more time. Because this f is an expression. Let's interpret f. What's the return type of interp value? How many kinds of values do we have in this language? Two, numV and cloV. When we interpret this first expression function part, we're going to get either cloV or a numV. Remember one open two close syntactically correct. Parser accepts it, but the interpreter should reject that. When we have this e1 open, e2 close, which happen to be numV, it's an error, not a closure error. Relieved. Now, this example is going to be rejected here. Let's assume that everything is beautiful and we have function call and when we interpret f we got cloV. Parameter name is x body expression is b and the capture the environment. The environment when this function value is being constructed is fenv. Note that there are two kinds of environment, env and fenv. They are two different things. Env and fenv. Env is the environment when this function call is happening. Fenv is the environment when this function value is constructed. Two different timing. Is the env bigger than fenv? Is fenv bigger than env? Does anyone contain the others? No. They are just different things. They happen to be the same, but they are just unrelated to environment. Env is an environment when this function call happens, fenv is the environment when this cloV was constructed. Are you not sure about that? Concrete examples and try to interpret it, then you're going to see that. [Korean] If you don't understand, [Korean] you'd better write some code and
[Korean] run it with this interpreter
[Korean] rather than keep listening to the lecture.
[Korean] You can follow the interpreter's execution
[Korean] with your head, or with your hands.
[Korean] It'll help you understand better. Just listening to my lecture is not enough. You'd better spend your time and effort with paper and pencil to write some concrete examples. Try to have two environments a function core site and function construction site and making them same, different, like that. Good luck. Then how do we interpret this? Now that I have this function value here, I'm going to evaluate the argument expression and get the value to interpret the function body. When I interpret the function body, what's going to be the environment? When I interpret this function body? What's going to be the environment? What do we want to have? This environment? That environment or what and what else? Think. What do we need? [Korean] What do we need? What do you think? At least we need the parameter's value. That's the minimum. Because this is a function of parameter x and body b. We'd like to know the value of the parameter, which is the value of this argument expression. What else? On top of what? That's the real question. What do you think? On top of fenv. Let's spend some time to think about why and why not env? What do you think? You may want to pause and think yourself instead of just listening to what I'm just explaining. The important thing is that when we have function call, they are two expressions. When we interpret the first expression, we want to get cloV, otherwise it's an error. When we have cloV, it has a parameter name, body expression, and an environment when this cloV was constructed. Why do we need fenv? Because in this function body, there may be some names, not only x, but also some other names, and their values are kept in this environment. When we interpreted this function body, we need the value of the parameter and we also need the values of those names captured in the function body in fenv. If we use env, what do you think? The env is a cosine dynamic scoping. The fact that we use fenv is static scope. Think about it. This is the last bit for first-class functions. If you notice this, then you have very sharp eyes. Val is optional, actually. If you compare Val and App, they are very similar. Val x, I'm introducing a name x, whose Val is the value of a using the information, evaluate p. We are going to evaluate p using the information that x's value is going to be a's value. Function call. Look at that. When we have function whose parameter is x by this b and when we interpret p, we use this information that x's value is a. Do you see that correspondence? We interpret b on top of the given environment. Which extended information? X's value is the value of a. They are just the same. Can you see that? Val x equals 10 and x, it's just the same as parameters x, whose argument value is almost 10. Val x's value is 10, using that information, do this. Val, x's value is 10 using that information, do this. In other words, val, these names value is the value of x-bar one. Using that information, they're just the same. It's called syntactic sugar. [Korean] It's sugar. It's sugar. [Korean] It's pretending to be different using sugar,
[Korean] but it's actually the same.
[Korean] They are just the same. Now, we're going to use the same thing. We know that there are two things that are the same. We are going to get rid of one from now on, because maintaining two is too much. [Korean] The two are the same, [Korean] so we'd like to get rid of one. Here, from now on, we are not going to have val. Now it's not FVAE. We get rid of V, and now we have FAE because they are just the same. We can simulate one using the other. We may not use val for some languages because they are just the same. But we may still use val in examples because that's readable, more readable than function calls. We are going to get to that later when we discuss lambda calculus. [Korean] I'll explain again [Korean] when you learn lambda calculus. But until then you can just think like val expression is just function and function call. We're going to get rid of val because we have functions and function call which can simulate that. Final quiz. Consider the following code. Which of the following is the same as the above code? Let's look at that. What did we say? X is 10 and x, y is 10 and x, they are different, they are the same. We are not using x. This is just functional expression. X is 10 and x. What's that? Was it the same with the previous one? Yes. The last one. Thank you.