Hi everyone. Today we are going to learn the semantics of functions in the operational semantics. The relevant part of the textbook is chapter 9, First-Class Functions. Before explaining the semantics of functions in the operational semantics, let's review the semantics in Scala, the interpreter semantics. FVAE was the new kinds of values to express functions as values. Previously, values were only numbers. We used integers as return values of the interfunction. But now their functions are values as well. We have a new value called trade value, which has two variants: NumV for numbers, CloV for function values. A NumV obviously has an integer value, and CloV has three pieces of information: the parameter of a function, the body expression of a function, and the environment when this function value was constructed. That's what we call by CloV. Then when we have this expression saying that y's value is 10, remember that. We are going to make a function value whose parameter is x, body is y plus x, and the environment when this function value is constructed contains y's value, which is 10. Are you with me? Then how can you construct a value? It's a function value, so CloV. As I said before, CloV has three pieces of information. The parameter of the function is what? X. The body of the function is y plus x. Finally, the environment when this CloV is constructed contains one mapping from y to 10. It's going to be like this. The parameter is x, the body is addition of y and x, and the environment contains the information that y's value is 10. So far so good. We are reviewing what we've learned so far. In F1VAE, if you remember, functions were not values. In a given function definition, only legal free identifiers are the parameters of those functions. Because functions are not values. Function expressions do not exist there. Function definitions are different kinds. They may not contain any free identifiers except their parameters. When we call a function in this language called F1VAE, the environment when we interpret the body of the function should contain only one piece of information, the parameters and its value. If you remember, when we call this function, this f should be a function name which can be looked up by this function. Get the function definition. When we interpret the function by the expression. On top of empty environment, we should have only one piece of information saying that the parameter's value is the value of the argument expression. That was F1VAE. But in FVAE, we have different thing. What's that? In FVAE, functions are values. In this function called App (f, a), f is not anymore a simple string, but it could be any expression. When we interpret this function part expression, that could be CloV or not. If it's not a CloV, it's an error. If it's CloV, we know that it has three pieces of information. When we interpret this function body, we need to know the value of the parameter as before, but this is not empty environment. Then what was that? That was the environment when the function was being defined. It's going to be what? fenv, when this function was defined. So far so good. If you remember, we had scoping. In this example, when we construct this function expression, y is valid, y is introduced when we construct this CloV. In this example, when we construct these CloV, y does not exist. It's a free identifier error. You should be able to do this by yourself. We learned that this valid expression is optional. Remember? In general, when we have this val id is e_1, 1_2. It's just the same as what? This is a Lambda expression introducing this ID, whose value is what? Expr_1 e1 and using that information, we evaluate e2. What can you do? From now on we can make sure that val, this id, this value is the value of e1. Using the information evaluate e2, which is the same as we are calling function, whose parameters id the same, whose value is going to be e1 the same. It's going to be passed to this and interpret this function body. They are just the same, the same thing with two different syntax. We are going to get rid of one thing and use only one to be productive. What we learned so far is to grow our language, grow one simple AE language to VAE, VAE to FVAE, which is just the same as FAE. We are growing languages by adding features. FAE, this is the concrete syntax. Now, you know. AE for asymmetric expressions, names, function call, and function expression. This is the abstract syntax representing the same thing in Scala. As we reviewed in the beginning of this lecture, we introduce new kind of value to represent two kinds of values. NumV for numbers, cloV for function values. Hope you understand this clearly by now. This was our interpreter implementation in Scala. Then, what are we going to do today? We are going to explain the same thing as before in this previous slide in black, in Scala, we explained the semantics of FAE. We explained the semantics of a language called FAE by implementing its interpreter [Korean] We make a language named FAE
[Korean] by growing it from AE we are growing our language [Korean] The language grows like us. by adding new language features. For each language that we newly introduced, we explained its semantics in prose, in the interp implementation and in the operational semantics [Korean] For each language that we newly introduced, [Korean] we explained its semantics
[Korean] in prose, with code examples,
[Korean] in interpreter implementation in Scala,
[Korean] and in operational semantics. I already explained the semantics of FAE in prose using some concrete examples. In the interp implementation using Scala. Finally, we are going to explain its semantics in the operational semantics. This beautiful mathematic notation. In this language, FAE, we have numbers, addition and subtraction for arithmetic expressions, identifiers, function expressions, and function call for functions as values, first-class functions. In this syntax, when we say n, n1, n2, and n prime like this, they are all integer numbers. When you say x, y, z, x prime, like that, they are all identifiers, a set of identifier names, and when you say e, e1, e2, e prime, e double prime like that, they are all expressions. Then, how can you represent values in this new language? There, a value is either numV or cloV. Same here. A value is either a number n or closure v. Closure v has three pieces of information, parameter name, body expression, and environment so this closure v has what? Parameter name, body expression and the environment. Are you with me? One more time. Closure v has what? We're going to just use these angle brackets to represent a closure value and we're going to use this Lambda dot comma to represent three pieces of information. They are just delimiters. [Korean] We're using these angle brackets, period, and comma [Korean] just to separate the parameter name,
[Korean] the body expression, and the environment. They do not have any specific meaning, they are just delimiters. The important things are what? Parameter name, body expression, and the environment. We're going to say that v is for value, again, v1, v2, v prime. They are all values. Value v is union. Either an integer value or a closure value. What is a closure value? Parameter, body expression, and environment. This is Lambda expression, function expression. We just enlarge the set saying expression and an environment. An environment was what? Final mapping from names to their values. One more time. A closure is actually a parameter by the expression in the environment. A closure is a package of a parameter, body expression and environment, but we just abuse the notation saying that it's a pair of an expression in an environment. Actually, this expression should be a function expression, but we're just abusing the notation here. Then how can you write the semantics? We already know this. Under a given environment, Sigma, number n evaluates to n. This was what we've been doing. Addition, we know that under the given environment, evaluate e_1 get the value n_1, evaluate e_2 get the value n_2, add them. Important thing, if you remember, is what? This one is v. V could be either n or Rho v. V could be now either number or closure v. So e_1's value could be closure v, which is an error. This rule only describes a value devaluation. E_1's value should be a number n, e_2's value should be number 2. Then we can add n_1 plus n_2. If we have some Sigma, say, Lambda x dot e plus four, then we evaluate this like Lambda x dot e, oh, we haven't learned this so far. It's going to be some star value. Four is four. Then this star clearly is not a number. It's a closure v. What can you do? It's an error, because there is no rule to apply this. This rule clearly says that e_1 and e_2's value should be numbers. My subtraction is just similar. How about identifier? You remember that? When we have an identifier x, we need to check whether it has a value in this given Sigma. Let's see whether x is in the domain of this environment. If it's there, then we can get the value from the environment. That's simple. Actually, in the implementation in Scala, when we have an identifier, we look up the environment Sigma, the value of x there. If x's value is in these environments Sigma, we are going to get this value here. Otherwise, it's going to be an error. Finally, what can you do? Let's look at how to evaluate a function expression. It's just simple. Why? Because this inter-function we already learned that when we have a function expression with parameter and body, we just construct clov with the parameter and the body and the environment at that time. Just like that, when we have a function expression Lambda x dot e under some environment, we are going to construct closure v with the parameter, the body expression and the environment. That's it. This is the most important slide for this lecture. You could guess that. Function call, this is the highlight. Let's see how we interpreted it that in Scala. When we have a function call f and a, f could be any expression. It doesn't need to be a function expression. We interpret that and get its value. Hopefully, it's clov, otherwise, it's an error. If it's clov, we have this parameter, body and the environment when this clov was constructed. Then what's the semantics? Remember, we are going to interpret this body expression using the information that this parameter name has the value of this argument expression. Using this information on top of the environment when the function was being defined, this was the semantics. Then how can you write that in the operational semantics? This is it. Let's see, one-by-one. Under a given environment Sigma, we now have e function f argument a. It's e_1, e_2, just two expression. We just hope that e_1's value is a function value, so that it's not an error. Then with that hope, let's see value e_1. If it's not CloV, we cannot apply this at all, it's already an error. If it's CloV, it should have parameter name, per the expression, and environment when that's constructed, the important thing, meaning that we now have E1 and E2 for function call and E_i, which is function body, which is our b there. That's E_i. We have this Sigma prime. What? That F, E and V there. So far so good? Yes. Then we just evaluate E2 get its value V2. One more time, this V2, doesn't need to be n. It could be some other Lambda y.E prime, Sigma double-prime. Because functions have values. It could be numbers or this. We just say V2. Now that we evaluated E1 and E2, let's evaluate the function body. How? This is it. We are going to evaluate function body, which is this E. Under which environment? Under this environment, was that on top of F of U and V, we add this information saying that parameter has arguments value. Using this information we evaluate this expression get another value of V, which could be either number or closure V. That's going to be the value of this function call. This is the somatic cell function call. I hope you understood this clearly. If not, you'd better rewind and watch this one more time. This is the most important semantics throughout this course because later on top of FAE, we're going to add new language features. But whatever we add new features, the basic language constructs are identifier's, function expressions and function calls. Identifier's look up the environment. Functional expression construct closure V. Those are simple. Function call is the most important semantics. Function call, meaning that there's a color of some function part E1, and there may be some argument because in this language, every function has only one parameter. We have E1 and E2. Evaluate E1. If it's not CloV error. If it's CloV, that's good. If it's CloV, we know that that has parameter name, per the expression and functions environment. Now that we evaluated E1 to CloV, evaluate E2. I don't care its value. I'm going to just use that later when I need to, but it should be some value V2. Using that information, evaluate the function body. How? Evaluate the function body under which environment? On top of the environment when this CloV was constructed, because that environment contains all the information about the free identifiers in the function body. On top of that F, E and V or a Sigma prime, we add one more piece of information saying the parameter's value is this argument value V2. Using that environment interpret the function body B and get the value. That's going to be the value of function call. Then let's move on to the quiz. Consider the following semantics that I just explained. Which of the following is the correct answer for the box? Let's see. What is that? We have function called E1 and E2. We evaluated E1, we got these CloV. We evaluated E2, we've got this V2. Then we're going to evaluate this function body and get some value. On top of which environment? That's the question. What do you think? Let's see. Number 1 is given sigma. Number 2 is CloVs Sigma prime. Number 3 is on top of the given Sigma, we add parameters value. Number 4, on top of these functions environment, we add parameters value. What's the answer? What do you think? It's going to be 4. Why? If we use just given environment, it does not have the parameter's value. If we use just the environment when the CloV was constructed, again, it does not have parameters value. Number 3 and 4 has parameters value, but if we use Sigma, it's going to be dynamic scope. We should use Sigma prime, the environment where the function has been defined, because that's static scope. Thank you.
