[music] In this segment I want to talk to you about how to implement an interpreter for a language that has variables. This is important for a couple reasons, 1st real programming languages have variables and 2nd the language you're interpreting on your homework assignment has variables. So notice, that so far, the interpreters we've written didn't have anything like variables, let-expressions, functions that took arguments and so on. Once we have those things, we need to change how our eval with x function works to take into account that it may need to look up variables as it's evaluating a program. So the idea here is, I'm not going to show you the code in this segment, because that's your homework problem. But I am going to describe in English exactly how the interpreter should work, so it's really your job to code this up on the homework assignment. Fortunately, the way variables and environments work is really exactly as I've been teaching since the very, very beginning of the course when we first learned the very beginning of ML. And, what better way to really make sure we understand the semantics than to have to implement that semantic for a small programming language, like you will on the homework. So here's how we do it. When we're interpreting something, when we're evaluating an expression, we do that with a current environment. An environment is what I've always said an environment is, it maps variables to values. Now in our homework, how are we going to map variables to values? Let's just have a list of pairs. Where the first thing in every pair is a string. This is a Racket string that says what variable we're talking about. And then the value that's one of those values in the language we're interpreting. It's one of the expressions that can be in returned by the evaluation of the expression. So something like a constant or a closure or a boolean or whatever it might be. And if we had a list of these pairs, that could work as an environment. And we would pass into our interpreter, the current environment. Okay? So, you get it as an argument. And then, when you have a variable expression, you do what I've said you always do, to evaluate variable expressions, you look them up in the environment. There's nothing magic about that. We get in the environment as an argument to the interpreter. When we have a variable, we look it up. Now the interesting part. When we recursively evaluate subexpressions, we will need to pass an environment to the interpreter for those subexpressions. Now for a lot of expressions it will be the same environment that we were given, right? If you have an addition, then you need to recursively evaluate the two subexpressions using the same environment. So if it was adding the variable x and the variable y We are passing the same environment to the first of expression which will look up x or pass the same environment into the second expression that will look up y. If x or y is not in the environment as you might imagine the interpreter case for variables will as part of its look up procedure give an error message saying that it did not find the variable, okay? Now, sometimes, when you evaluate a sub expression, you do it with a different environment. Perhaps the most obvious example is if you have a let expression. When you evaluate the body of that let expression, you need a larger environment. You need a new pair in it, so that the body of the let expression, the body can use the variable that was defined by the let expression. So that's really all there is to it, in terms of variables and let expressions. Let me describe a little bit more of the setup here. Okay? In your interpreter now. You should really think of there being a recursive helper function. We might call it eval-under-env, for evaluate under an environment. And it takes in two arguments. In expression e yes, but also an environment. We'll call it e n v, and this is where your big kind is with one case for each kind of expression. The variable case will need to use the environment. Some cases, when making recursive calls will just pass the same environment. Other ones will make, pass slightly different environment. So this where all the action is but then your run a program, your eval-exp for the entire program would then just call eval-under-env and the only question is what environment do you start with? And the answer is the empty environment, just the thing that has no pairs of strings and values in it. Because we start without any variables being in our environment. Okay? So, the only thing I haven't told you is the actual representation of the environment. The representation of the environment is just a, a racket list on you homework. It can be anything you want. It's a racket list containing racket pairs where each pair is the string that is the variable we are mapping to something. And then the MUPL value, on the homework we called the language being interpreted MUPL, it stands for Made Up Programming Language. And that would be something like the constant 17, which on your homework is written int of 17. So that's the entire setup. I want to finish with one grading detail, one stylistic issue. Because if you look at it, eval-under-env is really just a helper function for eval-exp. Eval-exp calls eval-under-env with the empty environment. You should not generally call eval-under-env directly that wouldn't make a lot of sense, it's just a recursive helper function for our interpreter. So you might be tempted to therefore make eval-under-env a locally defined helper function of eval x and please do not do that and the reason is for grading scripts. Okay? In order to be able to test your interpreter and figure out which parts you got right and which parts you struggled with we want to be able to call eval-under-env directly with particular environments. This way if you mess up a little bit of how you handle enviroments you won't miss all the tests. So we need you to leave eval-under-env up at the top level of the file. Even though in general you could certainly make an argument that would be better style to just make it a locally defined helper function. And that is really everything you need to know to implement variables in environments for a programming language.
