An environment is an abstract data type (i.e., a data type together with some operators and only usable through these operators) for binding names (represented here as Scheme symbols) to their denotation (represented here as Scheme values).
This note describes two implementations of environments: Environments as association lists and Environments as functions.
In mathematics, one often consider expressions with unknowns such as (x + y)^2, i.e., the square of the sum of x and y. We can reason about this expression, e.g., with the binomial expansion theorem from elementary algebra. We can also compute this expression in a given environment. For example, in the environment where x denotes 0 and y denotes 0, evaluating (x + y)^2 yields 0, and in the environment where x denotes 3 and y denotes 6, evaluating (x + y)^2 yields 81.
So what is an environment? It is a collection of bindings that associate names and the denotation of these names. An environment can be empty, or it can be the extension of another environment with a new binding of a name to a denotation – which is (what a surprise) an inductive characterization.
In the rest of this note, we first characterize an environment as an abstract data type, we set up a unit test that captures our expectations about how an environment should behave, and we present two representations of environments: as association lists and as functions.
An environment is an abstract data type, i.e., a functionality with operators.
The functionality: an environment maps names to denotables. It represents an ordered collection of bindings that can be extended and consulted. If an environment is extended several times with a binding of the same name to different values, consulting the environment with that name yields the value in the latest binding.
An analogy: Scheme programs operate in an environment. This environment can be extended with, e.g., let-expressions. In the course of the evaluation of a Scheme expression, a variable is evaluated by looking it up in the current environment:
> (let ([x 10])
(let ([x 100])
x))
100
>
The operators: a representation of the empty environment, the ability to extend an environment with a new binding of a name to a denotable, and the ability to look up a given name in a given environment to find its associated denotable, if this name is bound in this environment.
We start by setting up a unit-test procedure:
(define test-env
(lambda (mt extend lookup)
(and ;;; first test:
(or (lookup 'x
mt
(lambda (denotable)
#f)
(lambda (name)
#t))
(errorf 'test-env "empty environment"))
;;; second test:
(or (lookup 'x
(extend 'x 32 mt)
(lambda (denotable)
(= denotable 32))
(lambda (name)
#f))
(errorf 'test-env "lookup 32"))
;;; third test:
(or (lookup 'x
(extend 'x 33 (extend 'x 32 mt))
(lambda (denotable)
(= denotable 33))
(lambda (name)
#f))
(errorf 'test-env "lookup 33"))
;;; fourth test:
(or (lookup 'y
(extend 'x 33 (extend 'x 32 mt))
(lambda (denotable)
#f)
(lambda (name)
#t))
(errorf 'test-env "undeclared name"))
;;; add more tests here
)))
Procedure test-env is parameterized by the three operators, and runs a conjunction of 4 tests, all of which must yield #t:
An association list (or A-list for short) is a proper list of pairs, where each pair holds a name and a denotable:
Let us represent environments as A-lists:
The empty environment is represented by the empty list:
(define alist-mt
'())
Extending an environment is achieved by cons’ing a new pair in front of a given A-list:
(define alist-extend
(lambda (name denotable environment)
(cons (cons name denotable)
environment)))
Looking up a given name is achieved by recursively traversing the given A-list:
(define alist-lookup
(lambda (name environment found not-found)
(letrec ([visit (lambda (e)
(if (null? e)
(not-found name)
(let ([binding (car e)])
(if (equal? name (car binding))
(found (cdr binding))
(visit (cdr e))))))])
(visit environment))))
(Note how each recursive call to visit matches the inductive definition of association lists: visit is structurally recursive.)
Thus equipped, we can run the unit test:
> (test-env alist-mt alist-extend alist-lookup)
#t
>
Let us represent environments as functions that are given a name and what to do with the corresponding denotable, if there is one.
The empty environment is represented by a procedure that is given a name, a procedure found, and a procedure not-found, and that unconditionally applies not-found:
(define function-mt
(lambda (name found not-found)
(not-found name)))
Looking up a given name in a given environment is achieved by applying the environment to this name:
(define function-lookup
(lambda (name environment found not-found)
(environment name found not-found)))
Extending a given environment with a new name and a new denotable is achieved by returning a procedure that, when applied to a name, will check whether this name is the new name, and otherwise will look up this name in the given environment:
(define function-extend
(lambda (new-name new-denotable given-environment)
(lambda (name found not-found)
(if (equal? name new-name)
(found new-denotable)
(function-lookup name given-environment found not-found)))))
Again, let us run the unit test:
> (test-env function-mt function-extend function-lookup)
#t
>
Created [18 Oct 2025]