Hi everyone. In the previous lecture, we defined the second programming language called VAE. Actually we didn't give you the name formally, but let's call it VAE; arithmetic expression with val identifier. In the previous lecture, we defined its concrete syntax and wrote some examples in concrete syntax, and discussed how it behaves and what's the value of this expression thing. We also defined it's abstract syntax in Scala. I showed you a parser that you didn't need to understand so that it can translate, it can parse, some expression in concrete syntax to abstraction. Today we are going to discuss how to evaluate that language called VAE. If you do not understand what this lecture is talking about, read the textbook. This is the concrete syntax that we defined in the previous lecture; arithmetic expression with identifiers. The first three language constructs are for arithmetic expressions, number addition and subtraction, and the last two language features are for names. The first thing of those two is name introduction, identifier declaration, and the last one was how we can use names just by naming it. This was the abstract syntax in Scala. Again, the first four lines are about arithmetic expressions. You know that by heart by now. The last two are for names; identifiers. Remember that val is for introducing name x, which is a string whose value is the value of this first sub-expression. Using the information that x's value is the value of this i, with that information, we evaluate the second sub-expression, and the value of the second sub-expression is the value of the whole expression. In the body expression, in the second sub-expression, we may use this name x by just saying x. That was the abstract syntax. Now let's evaluate it, and not even just evaluating it. Let's think what happens when we evaluate that expression in a computer. [Korean] Let's pretend you're a computer. [Korean] What does happen when you have this expression? [Korean] How can you interpret it?
[Korean] Let's think about it. Let's interpret this expression VAE. It looks like this. That's an expression which introduces a name x. Now when we interpret this expression, we are going to keep a blue box one side. [Korean] We'll carry a blue box. in the box. We are going to keep the information, which name has which value [Korean] I'll store which name has which value in the blue box. [Korean] Because my memory is poor.
[Korean] The value of x is 1?
[Korean] I'll forget it, so let me write it down here. Let's see. When we evaluate this expression; one, that's value one and x equals 1. X's value is one. We're going to keep that in this blue box and then evaluate this next expression. After evaluating this part, we got rid of that and add that information into this blue box, and blue box says x's value is one, remember. If you want to know x's value, come back to me and ask. I will let you know. With that information, let's evaluate the remaining expression. Our y is two. Now you can guess what's going to happen. Y's value is two and we're going to put that information into the blue box. Then let's see. Now in the blue box we have x is one, and y is two. Using that information, we evaluate this long and complex expression; 100 plus 99 plus 98 plus dah dah dah. Let's do all that complex evaluation, and then finally we get to y. Actually we get to y plus x and then in order to evaluate y plus x, we need to know the value of y. What's the value of y? Why are you doing all this complex expression? I forgot. Don't worry, blue box has the answer. What's the value of y? Look up this blue box. It says two and we can get the value. This is how the computer evaluates this expression, and we are going to implement that in this lecture. Isn't it cool? Yeah. Before interpreting, before actually evaluating the interpreter, let's play one more example. We have all of that nested thingy. The inner one wins over the outer one, the inner x hides, the outer x example. What happens in this example? Why that happened? We're going to see actually several examples, but let's see this one now. Again, we have this blue box x's value is 1. Let's put that into that. Let's put that information into the box. We now have x is 1, when x is 2, what's going to happen? Don't worry. We know how to do that. How? Just put it into the blue box, x was 1 but now x is 2. It doesn't make any trouble. A new mapping replaces any old value our x is 2, wins over x is 1, x is 2 hides x is 1. Is it really okay? I think it may make some problems with some complex expression like this. Let's look at that together again. What happens? Here we have x is 1 here. I know I can expect that you're going to put that information into the blue box. But what about this? In the body, we have 2 sub-expressions, e_1 and e_2. What if e_1 and e_2 have xs, but with different values? [Korean] Is it ok to put new things in the box [Korean] and keep deleting old ones?
[Korean] I don't think so.
[Korean] Right?
[Korean] What will you do if you want to use the old one somewhere
[Korean] and the new one somewhere else.
[Korean] This is such an example. This is the example where old values and new values are going to be used. How can you do that using these blue boxes? Don't worry, we are smart enough to handle that. Look at this. Now that x's value is 1, we have that information and using that we evaluate this e_1 and e_2, really then how do you keep those two information? Look at this. We are going to split boxes, the blue box to 2 sub-expressions. We have this e_1 and e_2. We have one blue box, but we have e_1 and e_2. We need to interpret e_1 and e_2. Then blue box folks. The blue box makes copy of it. We have now two copies of blue boxes and put give them to two sub-expressions and ask them, do whatever they want to do. Meaning that in the beginning, the blue box has x is 1. In the beginning, x is 1, x is 1 in both cases. So far so good. If you want to change that in this first self-expression e_1, do that. Here it says x is 2, then x is 2. But in the second sub-expression, we didn't do anything, so x is still 1. When you have two sub-expressions, e_1 and e_2, in e_1, we wanted to change the value of x. Change that in your blue box. On e_2, we do not want to change the value of x. You use the blue box. Here there are two copies and change in one box does not affect the other box. [Korean] The two are distributed one by one in this way. [Korean] So changing the value of x here doesn't affect the other box.
[Korean] We're independent environments.
[Korean] We're independent villages.
[Korean] It's like "You do it. I don't want to." We have two different disjoint scope that can use different blue boxes. That's why we can have x is 2 here, x is 1 here. We can have x is 2 here, x is 1 here. Finally, we can get 2 plus 1. We made it. How are we going to do this in Scala? How can we implement this? We are going to change the definition of inter, to take a blue box. A blue box is a kit term, so we're going to call that environment. [Korean] It's fancier, isn't it? It's going to be environment. In some languages, we call that symbol table. There could be many other names, but we're going to call them environment. Now the inter function takes an environment. Previously, our inter function takes an expression interpreter that gives us our value. Now, new interpreter function takes an expression and an environment, the blue box, and evaluates the expression, and gives us a neat value, meaning that names require us to have this environment. With the arithmetic expression. We didn't need to have an environment but now that we have names, we need to have an environment. Then, what is an environment? In Scala, an environment is a map from strings to integers. Because what was the blue box? Which name has which value? Which string name has which integer value? That's a map. [Korean] It's a table. It's a table. [Korean] It's a table. [Korean] A table storing which name has which value.
It's simply a map, simply a table mapping a string name to its value. That's an environment. We created a map. We define a map from string to integer and call that env, this type env mean that we are defining a new type named env to represent a map from string to integer. How can we do that? Either just construct a map open, close, it's an empty table, or map with this initial mapping, a name called the a's value is zero, a name called b's value is one. We can add more mapping like this. We can remove a mapping from this. We can get the value of a, we can get value of c like this. Note that adding or subtracting new mapping to a map does not change the map itself. In order to change that, you need to assign this new map to a new name. It's a Scala thing so you go study Scala. Finally, why is mapping like this? This one. Then look at that, y's value is this initially. Y's value is that a's value is 0, b's value is 1. Then when we ask what's the value of a, that's going to be 0. What's the value of c? What is c? I don't know. C is not in this map. So the result of this GET method gives us option value. This is called option value. This is another Scala thing. You'd better look at the Scala menu. When it has a value, it gives us some and value. If it doesn't have a value, it gives us none. Option type is really cool and interesting and we're going to discuss that later. Long time, later. But until then if you are interested in option type, I strongly recommend you to read the Scala manual about option. It's really cool. It's some or none, it's much better than null value in Java. The Java program language provides null to simulate this null value, but it's really bad. Why? We can discuss that later. Stay tuned. Now comeback. In this example, we can either use get or get or else. Meaning that get gives you some of value or none. If this mapping has a mapping from a to some value, then gives us the value. If not, it's going to give us none. It's pretty annoying to get this option value and unwrap it. When we have a value, we need to get rid of that some tech and get the value. The map library provides another method called get or else, meaning that, give me the value of a. If it does not have a value, if you do not have the mapping for a, then gives me 42 as a default value because 42 is the ultimate answer of the universe if you read the book called Hitchhiker's Guide to the Galaxy. If you don't know the book, Google it. It's pretty cool. Now we are going to use these methods later. I will explain that a bit more when we get there. Now, let's play the same thing instead of using blue box, using environment. Now, I know that you are understanding this, so we are going to move a bit quicker. When we interpret this expression previously we had blue box and now we have empty map. Previously, we put this information x is 1 in the blue box. What are we going to do now? We're going to put that into the map. Map now has x is 1. Previously it was x is 1 in blue box and they're just the same. Then what's going to happen here? Y is 2 is going be in the map. X is 1 and y is 2. Previously, when we had y like this, we had to look up the blue box and now we can look up the map. What's the value of y? That's 2. Just the same. Blue box is the environment. Then how can we implement this? Let's see. Identifier. Because that's easier. How can you do that? Lookup the environment. That's what I just said in prose multiple times. [Korean] What's the value of an identifier? [Korean] It's in the environment.
[Korean] Go and look for it.
that's the semantics. Lookup the environment using x; that's why we keep environment here. [Korean] There's a reason to carry an environment. The interp function now takes an environment as a second argument. Why? Because when we have an identifier, we do have to lookup the environment. That's that easy. What is the local function then? How can you lookup the value from the environment? [Korean] What does "lookup the environment" mean? [Korean] How do you search from the environment?
Let's see. Lookup takes a name which is a string and an environment. The environment is blue box, right? X is one, y is two, z is zero. Then we can say, hey, int, that's env which was what? Map from string to integer, remember. Hey, environment, do you have a value for this name x? Remember? Yeah. Then it's going to give us some value or a none. Then we're going to do pattern matching here. Oh, yeah, I have a value of v, then we return the value. No, I don't have any mapping for this name. I don't know its value. Free identifier, yay. You know what that means. But it's a bit long and tedious. That's why, again, I showed you this method before. It gives us getOrElse message. How are we supposed to use that? Hey, environment, do you have a name? I mean, do you have the value for this name? Oh, yeah, I have that. Then it's going to give you the value. Otherwise, the default value is signal an error saying free identifier error. So far so good? Yay. Then we now have the final case, which is the highlight for this implementation, introduction. How can you implement that? Remember, the semantics was when we have val x equals e_1, semicolon, e_2, close, x's value is e_1's value. Using that information, evaluate e_2. Then e_2's value is the value of the whole expression. So far so good, right? Then we need to evaluate e_1 first. This is x, this is e_1, this is e_2. We need to evaluate e_1 first, and get the value. Remember that the value of x is the value of this. How do you remember that? We put that into the environment. Are you with me? Yeah, that's what I mean. What did I say? What did I do? We interpret e_1. This is e_1's value because we interpreted e_1. E_1's value is going to be x's value. We put that into the environment. Oo, magic. For a given environment, we added this piece of information. Using this information, what are we going to do? We're going to interpret this body expression. How can you say that? It's not difficult. It's just like what, interpret b. Interpret body expression. Under which environment? This extended environment. We're going to describe that more formally later, but until then, this is its semantics. One more time. Last time. What's the value of this expression? The value of this expression is the value of a b. Then let's interpret this. Value of b. But remember that when you interpret b when you evaluate b, you may encounter x. Hey, welcome x. Who are you? What's the value of x? We need to know that to interpret b. We need to extend this given environment with new information. Which information? X's value, because we may use x here. Oh, okay. What's the value of x? The value of x is the value of i. So far so good? Yeah. If you don't understand, listen one more time. Thank you. Now we are going to see the quiz to see whether you understood it. I think the quiz is easy. The same example I think that we saw before. Which of the following is the value of the above code? Take your time and see. Here, x's value is one. In the body, x's value is one. Here x's value is one. Oh, this is one. In this blue box, I mean, yeah, blue box is a dangerous term. In this body, x is two here, and this x is two. This is two, and this is one. Then what's the result? What's the result? Yeah, that's three.