[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.
Dan GrossmanProfessor
