Code doesn't run in a vacuum. Whenever you execute/evaluate a line of code, there's always a context for that code, including all of the variables and their values. Consider the following line of code:
(+ a 2)
Don't you have to know what the value of a is in order to evaluate
this? (For that matter, don't you have to know what the value of "+"
is?)
To keep track of variables and their values, we need a structure known as an environment. An environment is basically a look-up structure that allows us to determine the value of a particular variable.
Since we saw in Lecture 9 that block-structured languages can have one scope region nested within another, we have to have some way of representing this in our environments. Each scoping block needs to have its own environment, and the environment of a nested block must have a way to refer to the environment of the outer block (and it to the environment of its outer block, etc.).
We can thus think of an environment as extending another environment. If you look something up in the environment and don't find it, look in the environment it's an extension of.
Of course, this extension structure has to stop sometime. So, we define an empty environment as one with no variable/value bindings.
We can think of an environment then as an inductively-defined type:
| The BNF for <environment> |
|---|
|
In other words, an environment is either empty or its a set of (variable,value) pairs that extend an existing environment.
(I've written this inductive definition here using a list-style notation, but you could use any type of structure to put these parts together,)Our abstraction for an environment thus requires three components: a function for creating an empty environment, a way to extend an existing environment with new variable/value bindings to create a new environment, and a way to apply an environment to a variable to get its value.
(define empty-env
|
returns an empty environment |
(define extend-env
|
returns an environment that extends "env" and binds the "vals" to the "vars" |
(define apply-env
|
returns the value of the variable "var" in "env" |
We might use these in the following way:
(define first-env (empty-env)) (define second-env (extend-env '(a b) '(1 2) first-env) (define third-env (extend-env '(c d b) '(3 4 5) second-env) (apply-env first-env 'a) ; returns an error (apply-env second-env 'a) ; returns 1 (apply-env third-env 'a) ; returns 1 (same "a") (apply-env second-env 'b) ; returns 2 (apply-env third-env 'b) ; returns 5 (different "b")
There are lots of ways of implementing environments, but we'll talk about two ways: procedural and with the datatype abstraction we talked about in Lecture 10.
If you think about it, environments work like a function: f(variable) = value. So let's use functions to store them.
The empty environment is a function that always errors no matter what you try
to look up. empty-env just returns you one of these:
(define empty-env
(lambda ()
(lambda (sym)
(eopl:error 'apply-env "No binding for ~s" sym))))
An extended environment is a function that returns values for the variables it knows about. If the variable you're looking for is one defined in that environment, it returns the corresponding value; otherwise, it calls the extended environment (function) that it's an extension of:
(define extend-env
(lambda (syms vals env)
(lambda (sym)
(let ((pos (list-find-position sym syms)))
(if (number? pos)
(list-ref vals pos)
(apply-env env sym))))))
(define list-find-position
(lambda (sym los)
(list-index (lambda (sym1) (eqv? sym1 sym)) los)))
(define list-index
(lambda (pred ls)
(cond
((null? ls) #f)
((pred (car ls)) 0)
(else (let ((list-index-r (list-index pred (cdr ls))))
(if (number? list-index-r)
(+ list-index-r 1)
#f))))))
Applying an environment is now really simple--just call the function:
(define apply-env
(lambda (env sym)
(env sym)))
Another way of storing environments is with data structures defined using the define-datatype construct:
(define-datatype environment environment?
(empty-env-record)
(extended-env-record
(syms (list-of symbol?))
(vals (list-of scheme-value?))
(env environment?)))
(define scheme-value? (lambda (v) #t))
Creating an empty environment is pretty simple--just use the empty-env-record constructor:
(define empty-env
(lambda ()
(empty-env-record)))
Extending an environment is also straightforward--just use the extended-env-record constructor:
(define extend-env
(lambda (syms vals env)
(extended-env-record syms vals env)))
Applying the environment is a little more complicated than with a procedural implementation because you
have to traverse the data structures instead of just calling a function. Re-using the list-find-position
function from earlier:
(define apply-env
(lambda (env sym)
(cases environment env
(empty-env-record ()
(eopl:error 'apply-env "No binding for ~s" sym))
(extended-env-record (syms vals env)
(let ((pos (list-find-position sym syms)))
(if (number? pos)
(list-ref vals pos)
(apply-env env sym)))))))
We'll use this environment abstraction when we implement our own interpreter. Which one will be use? That's the beauty of abstraction: we don't have to care how its implemented, just that it is.
Last updated at 9:54 am on Friday, August 27, 2004.