Implementing Variables and Environments

Loading...

From the course by University of Washington

Programming Languages, Part B

344 ratings

University of Washington

Programming Languages, Part B

344 ratings

[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module of Part A. Part B assumes successful completion of Part A. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.

From the lesson

Section 6 and Homework 5 (Second Module with Racket)

Welcome to the second week of Part B where we will focus on (a) building data structures in dynamically typed languages and (b) implementing programming languages with interpreters. Most of the programming assignment is focused on (b) -- implementing a small programming language that has function closures. As usual, start with the welcome message and enjoy!

Datatype-Programming in Racket Without Structs13:21

Datatype-Programming in Racket With Structs9:34

Advantages of Structs8:13

Implementing Programming Languages10:07

What Your Interpreter Can and Cannot Assume13:47

Implementing Variables and Environments6:29

Implementing Closures6:32

Optional: Are Closures Efficient?9:03

Racket Functions As “Macros” For Interpreted Language9:15

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

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

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play