Hi, everyone. This is the last lecture about VAE. We discussed the semantics of VAE in prose. I explained the semantics of VAE using some examples. [Korean] I've explained the semantics of VAE in prose so far, [Korean] with examples in the concrete syntax.
The first trial was to explain the semantics in prose using concrete example. In the previous lecture, I explained the semantics using Scala implementation. This is the second trial. [Korean] The second trial is [Korean] to see how to implement the `interp` function in Scala
[Korean] because explaining in prose may not be enough.
[Korean] How we implement the `interp` function
[Korean] is the semantics of VAE.
[Korean] Right?
[Korean] We saw "our explanation is implemented like this." The second trial was to explain the semantics in implementation of Scala. That's telling you another way of explaining the semantics of VAE. Today, we're going to try the third attempt to explain the semantics of VAE using operational semantics. [Korean] Today, in addition to the explanation in prose [Korean] and the Scala implementation,
[Korean] we're doing the same thing again
[Korean] for the last time, in mathematics.
[Korean] Operational semantics. Some students may feel comfortable with explanation in prose using concrete examples. Some students may prefer to see Scala implementation of the inter-function. What she said in prose means this thing. Scala implementation, this is easier to understand for some students. The last group of students who usually prefer to think in mathematics more formally and rigorously I guess, they may like today's lecture. I like this explanation the best, but your mileage may vary. Let's see what it is. Again, please read the textbook. We extended that arithmetic expression to arithmetic expressions with identifier. The first language is called AE for arithmetic expressions and now our language is called VAE, arithmetic expressions with identifiers VAE. This was the concrete syntax. VAE for declaring new names, id equals e_1; e_2, id value is used value. When we evaluate e_2, we may use id whose value is the value of e_1. If we want to use that name in e2, just name it. That's the last case, Id. This is the same thing in Scala. The previous one is the concrete syntax and this one is abstract syntax. One more time. New name introduction has three pieces of information. The name in string, the initial expression e_1 to represent the value of the name, and the body expression e_2 may use or not the identifier, and b's value is the value of the whole expression, and id is a name. This was the Scala implementation of the semantics. Remember? Yeah, number is a number. Addition and subtraction they have two sub expressions. We need to recursively call the inter-function on L and R, left and right to get their values, and then add them or subtract them depending on your case. That's arithmetic expression, and Val and Id. Id introduction and Id elimination. Id declaration and Id use. How do you use name? Just naming it? Or how do you know the value of the name? Looking up the environment. How do you look up the environment? The environment is a map from names to values. For a given name, lookup the environment and ask the environment, "Hey, do you have the value for this one?" Yeah, get the value. "No, the name is undefined." Really, it's a free identifier error. That was that Id case. Finally, how can we interpret a new name introduction? You know what, the value of this val expression is the value of add expression, the second sub expression, p. How do we get the value of p? Interpreting it under an extended environment. Using an extended environment, because when we interpret the body expression b, we may use the name x because we are introducing the name here. Then what's the value of x? The value of x is the value of i. Let's see, we need to know the value of x to interpret b. We first interpret i here under this given environment, get the value, and make a mapping say, Hey, this new name has this value, and add it to the given environment. This is the new extended environment, and using that environment, interpret b, that's the value. This was the way I explained how to interpret VAE in Scala implementation tension in the last lecture. Then what today? In mathematics, in the operational semantics. Let's do the same thing over again in mathematics. What's the syntax again? We had now five cases, num, addition, subtraction, and introduction and use of names. We can say the same thing in mathematics. We are defining a new language, e. This one saying, I'm defining this language e, which has five variants. What are they? They are either number or addition of two sub-expressions, subtraction of two sub-expressions, or introduction of name using val, whose value is going to be the value of this first expression. The value of the whole expression is going to be the value of the second sub-expression. When you interpret these sequence of expression, you may use this name x here. How do you use it? Just name it. This is the same. What are those things below? They are definition of the meta variables. When we say n, it's going to be an integer. When we describe the semantics of this language in operational semantics in the next slide, when we say n is an integer, when you say n1, n2, n3, they are all arbitrary integers. When you say x is going to be a name, powerful variable, x is a name when you say x, y, z, or x1, x2, y3, they're all names. When we say e, it's going to be an expression made out of these five cases. So far, so good. When we say environment, we're going to say Sigma. It's a Greek letter. In operational semantics, people love Greek letters. We're going to say, [Korean] What do we usually use?
Sigma or Alpha, Beta, but environments we just use Sigma. Sigma is an environment. What is an environment? It's a finite mapping from names to integer values. Don't be afraid. It's just the same thing with this Scala implementation. [Korean] Don't panic. [Korean] It's not difficult at all.
[Korean] Because they are just the same. What I just said here, is we defined new type called Env, which is simply a map from String to Integer. String to Integer is a finite mapping in mathematics. When I say Sigma, Sigma prime, Sigma 1, Sigma 2, they are all environments. Finally, when we say v, it's a value, value for val. These are sets, v is a value. In this language, all the values are integers, but later when we grow the language VAE with whatever's something new concept, value set is going to be larger, but until then, value set is now integers. So far so good. Are you ready to go start an adventure? We are going to write an operation semantics for each case. For each Scala implementation, we're going to have a corresponding operations semantics rules. Simple thing first, interpret. On the expression under this environment, is going to give us any integer value. On the whatever environment I don't know, it's a Sigma. Under that, if we evaluate some expression, it's going to give us a value. That's a template. This blue thing, what I just wrote in pink, that's a template of operational semantics of VAE. That's just like this. Interp is what? Interp is that. It's going to take an expression and environment. When interp interprates an expression under this environment, it's going to result in an integer value. When we evaluate this expression under this given environment, we're going to get this value. Same. Really? Yeah. Let's see easy case first. What's that? We have this. Hey, do you have a number case? That's number. We do not even use environment, meaning that on the whatever environment is given, I don't care because we do not lookup the environment. Under whatever environment is given, our number n value is n. That's simple. They are just the same. What about addition? Addition has two sub expressions. Because they are expressions, we are going to recursively interpret them l and r under a given environment. Then this one is going to give us an integer. How did you know that? Because Interp says so. Interp takes an expression in an environment and it's going to give us an integer. We're going to get those two values and add them. How can you say that in operational semantics? Like this. Under a given environment, now we have e_1 plus e_2. What's the value of e_1 plus e_2? In order to know the value of that, we need to know the value of e_1 and e_2. What are their values? In order to know their values, we need to recursively interpret them. We are under the same environment. Under the same environment, we interpret e_1, whose value is, we don't know. First of all, we say that I don't know what it is, but I know it should be a number. We say that n_1. That may emphasize that by saying n_1. Under the same environment when we evaluate e_2, I don't know its value, but all I know is that it should be n_2, a number. Remember, when I say n_1 or n_2, I don't know their values exactly, but I do know I enforce that they are integer values. In order to do addition, I'm telling you that n_1 and n_2 should be evaluated to numbers. Then we can finally say that's going to be n_1 plus n_2. This is just the same with this. Are you with me? Very good. Then what's next? Subtraction. Not very interesting. You do it. How about lookup? Yeah, it's slightly more interesting. We said that in order to know the value of this name, we need to lookup the environment using the name. How can you say that in mathematics? Just like this. Under a given environment, what's the value of x? Lookup the environment. How? Ask environment, because it's a map, in your domain, do you have a mapping for x? Do you have a value for x? If it's not, the rule says it's a reject. It's going to be a free identifier error. Or, oh, I know. I have the value for that. It's going to give us a value for x. Again, Sigma was what? An environment, it was, finite mapping from names to integer. We asked, hey, in your domain, do you have a mapping for this name x? In your domain, do you have a value for this name x? Oh yeah. Then we can get the value like this. Sigma is a mapping, so I will give you the name, then it's going to give us the mapped value. This is how we write the same thing for lookup. So far so good. Let's move on to the highlight. Maybe introduction. Do I need to explain this one more time? Yes. Let's do that one more time quickly. [Korean] I've explained lots of times so far. [Korean] I'll repeat for the last time.
How do we interpret this val expression? We need to interpret i first on the given environment, which is going to give us the value of i. Now that we have a value of i, we need to have this mapping. x's value is this new value. We need to extend env with that information so that we can interpret b under that extended environment. You heard this multiple times by now, then what does that mean in mathematics? This one. Look at this. Isn't it pretty? Let's see. Under whatever environment is given, when we introduce a new name x, whose value is going to be the value of e_1, and using that information, we are going to evaluate e_2, what's the value of this whole expression? Oh, I know that the first thing to do is to interpret e_1. Oh, you're right. Interpreted e_1. Then in order to interpret e_1, we need to use the given environment, the same environment. Under that given environment, when we evaluate e_1, I don't know its value, but it's going to be some value v_1. So far so good? Then with this information, we are going to extend the environment. How do we extend the environment? We get the given environment and edit this information. That's simple. That x's value is this new value v_1, the value that we just calculated. This is the pretty new environment. This one, they're just the same. Under this environment, if we evaluate e_2, it's going to be some value v_2. I didn't know what it is, but it's going to be some value v_2. That's going to be the value of this whole expression. We're done. If you do not understand what I just said, please listen to the explanation one more time. This is the highlight for the operational semantics of VAE, because all the other cases are just simple. Number, addition and subtraction, you know they're from AE. I did look up, just look up the environment. This introduction of a new names is going to be what? Creating a new mapping and add the mapping to the environment and evaluate an expression under that new environment. That's all we did in this single line, and this is just the same thing. One more time. The black color implementation and the red, not anymore red, this black color implementation and this red offers a semantics. They are just the same. You need to be able to correspond to each other. This part is that, this part is that, this red explanation is that black implementation. That back implementation of these part corresponds to this part in red. You should be able to do that by yourself. Enjoy. Let's do the quiz, the final quiz for this identifier's lectures. Look at that. Consider the following semantics of the val expression. The semantics that we just saw. The following interpreter code for the val expression, this color implementation that we just saw in black, this time in blue. This is the question, mapping between those two corresponding elements. Which of the following corresponds to v_1? Which is the value of e_1. v_1 is the value of e_1, we know that. That was in this operation semantics. What is v_1 in this implementation? That's the question. What is the answer? Look at that. i is e_1, b is is e_2, interp i, env is what? Interp i, env is this. Interp the whole thing is what? Interp b, meaning this one. What is v_1? The third one. I already explain that here, so you can read them more with this explanation. Thank you.