9.8 Case Study: Environments

Recall from Chapter 6 that a referencing environment is a mapping that associates variable names (or symbols) with their current bindings at any point in a program in an implementation of a programming language (e.g., {(a, 4), (b, 2), (c, 3), (x, 5)}). Consider an interface specification of an environment, where formally an environment expressed in the mathematical form {(s₁, v₁), (s₂, v₂), . . . , (s_n, v_n)} is a mapping (or a set of pairs) from the domain— the finite set of Scheme symbols—to the range—the set of all Scheme values:

where {g(s′) = v_i if s′ = s_i for some i, 1 ≤ i ≤ n, and f(s′) otherwise; and [v] means “the representation of data v.″

The environment {(a, 4), (b, 2), (c, 3), (x, 5)} may be constructed and accessed with the following client code:

Here the constructors are empty-environment and extend-environment, which each create an environment. The observer, which extracts from an environment, is apply-environment.

9.8.1 Choices of Representation

We consider the following representations for an environment:

• data structure representation (e.g., lists)

• abstract-syntax representation (ASR)

• closure representation (CLS)

We have already discussed list and abstract-syntax representations—though not for representing environments. (We briefly discussed a list representation for an environment in Chapter 6.) We will leave abstract-syntax representations of environments and list representations of environments in Racket Scheme as exercises (Programming Exercises 9.8.3 and 9.8.4, respectively) and focus on a closure representation of abstract data types here. Specifically, we discuss a closure representation of an environment because it is not only perhaps the most interesting of these representations, but also probably the least familiar for readers.

9.8.2 Closure Representation in Scheme

Often the set of values of a data type can be advantageously represented as a set of functions, particularly when the abstract data type has multiple constructors but only a single observer. Moreover, languages with first-class functions, such as Scheme, facilitate use of a closure representation. Representing a data structure as a function—here, a closure—is a non-intuitive use of functions, because we do not typically think of data as code.⁵

Analogous to our cognitive shift from thinking imperatively to thinking functionally in the conception of a program, here we must consider how we might represent an environment (which we think of as a data structure) as a function (which we think of as code). This cognitive shift is natural because an environment, like a function, is a mapping. However, representing, for example, a stack as a function is less natural (Programming Exercise 9.8.1). The most natural closure representation for the environment is a Scheme closure that accepts a symbol and returns its associated value. With such a representation, we can define the interface functionally in the following implementation:

Getting acclimated to the reality that the data structure is a function can be a cognitive challenge. One way to get accustomed to this representation is to reify the function representing an environment every time one is created or extended and unpack it every time one is applied (i.e., accessed). For instance, let us step through the evaluation of the following application code:

First, the expression (empty-environment) (line 4) is evaluated and returns

Here, eopl:error is a facility for printing error messages in the Essentials of Programming Languages language. Thus, we have

Next, the expression on lines 3–6 is evaluated and returns

Thus, we have

Next, the expression on lines 2–12 is evaluated and returns

Thus, we have

The identifiers list-find-position and list-ref are also expanded to their function bindings, but, for purposes of simplicity of presentation, we omit such expansions as they are not critical to the idea at hand. Finally, the lambda expression on lines 2–20 representing the simple environment is stored in the Racket Scheme environment under the symbol simple-environment.

To evaluate (apply-environment simple-environment 'e), we must unpack this lambda expression representing the simple environment. The expression (apply-environment simple-environment 'e) evaluates to

Given our definition of the apply-environment function, this expression, when evaluated, returns

Since the symbol e (line 21) is not found in the list of symbols in the outermost environment '(a b) (line 2), this expression, when evaluated, returns

This expression, when evaluated, returns

Since the symbol ’e (line 10) is found in the list of symbols in the intermediate environment ’(c d e) (line 2) at position 2, this expression, when evaluated, returned (list-ref ’(3 4 5) position), which, when evaluated, returns 5. This example brings us face to face with the fact that a program is nothing more than data. In turn, a data structure can be represented as a program.

9.8.3 Closure Representation in Python

Since Python supports first-class closures, we can replicate our closure representation of an environment data structure in Scheme in Python:

We can extract the interface for and the (closure representation) implementation of an ADT from the application code:

1. Identify all of the lambda expressions in the application code whose evaluation yields values of the data type. Define a constructor function for each such lambda expression. The parameters of the constructor are the free variables of the lambda expression. Replace each of these lambda expressions in the application code with an invocation of the corresponding constructor.

2. Define an observer function such as apply-environment. Identify all the points in the application code, including the bodies of the constructors, where a value of the type is applied. Replace each of these applications with an invocation of the observer function (Friedman, Wand, and Haynes 2001, p. 58).

If we do this, then

• the interface consists of the constructor functions and the observer function

• the application is independent of the representation

• we are free to substitute any other implementation of the interface without breaking the application code (Friedman, Wand, and Haynes 2001, p. 58)

9.8.4 Abstract-Syntax Representation in Python

We can also build abstract-syntax representations (discussed in Section 9.5) of data structures (as in Programming Exercise 9.8.3). The following code is an abstract-syntax representation of the environment in Python (Figure 9.3).

Programming Exercises for Sections 9.7 and 9.8

Exercise 9.8.1 (Friedman, Wand, and Haynes 2001, Exercise 2.15, p. 58) Consider a stack data type with the interface:

where ⌈v⌉ means “the representation of data v.”

Example client code:

Implement this interface in Scheme using a closure representation for the stack. The functions empty-stack and push are the constructors, and the functions pop, top, and empty-stack? are the observers. Therefore, the closure representation of the stack must take only a single atom argument and use it to determine which observation to make. Call this parameter message. The messages can be the atoms ’empty-stack?, ’top, or ’pop. The implementation requires approximately 20 lines of code.

Exercise 9.8.2 Solve Programming Exercise 9.8.1 using lambda expressions in Python.

Example client code:

The remaining programming exercises deal with the implementation of a variety of representations (e.g., abstract-syntax, list, and closure) for environments. Tables 9.3 and 9.4 summarize the representations and languages used in these programming exercises.

Table 9.3 Summary of the Programming Exercises in This Chapter Involving the Implementation of a Variety of Representations for an Environment (Key: ASR = abstract-syntax representation; CLS = closure; LOLR = list-of-lists representation; and PE = programming exercise.)

Table 9.4 The Variety of Representations of Environments in Racket Scheme and Python Developed in This Chapter (Key: ASR = abstract-syntax representation; CLS = closure; LOLR = list-of-lists representation; and PE = programming exercise.)

Exercise 9.8.3 (Friedman, Wand, and Haynes 2001) Define and implement in Racket Scheme an abstract-syntax representation of the environment shown in Section 9.8 (Figure 9.4).

(a) Define a grammar in EBNF (i.e., a concrete syntax) that defines a language of environment expressions in the following form:

Specifically, complete the following grammar definition:

(b) Annotate that grammar (i.e., concrete syntax) with abstract syntax as shown at the beginning of Section 9.5 for λ-calculus; in other words, represent it as an abstract syntax.

(c) Define the environment data type using (define-datatype ...). You may use the function list-of, which is given in Programming Exercise 9.6.1.

(d) Define the implementation of this environment; that is, define the empty-environment, extend-environment, and apply-environment functions. Use the function rib-find-position in your implementation:

Exercise 9.8.4 (Friedman, Wand, and Haynes 2001) In this programming exercise you implement a list representation of an environment in Scheme and make three progressive improvements to it (Table 9.5). Start with the solution to Programming Exercise 9.8.3.a.

Table 9.5 List-of-Lists/Vectors Representations of an Environment Used in Programming Exercise 9.8.4

(a) Implement the grammar defined in Programming Exercise 9.8.3.a. In this representation, the empty environment is represented by an empty list and constructed from the empty-environment function. A non-empty environment is represented by a list-of-lists and constructed from the extend-environment function, where the car of the list is a list representing the outermost environment (created by extend-environment) and the cdr is the list representing the next inner environment.

Example client code:

This is called the ribcage representation (Friedman, Wand, and Haynes 2001). The environment is represented by a list of lists. The lists contained in the environment list are called ribs. The car of each rib is a list of symbols, and the cadr of each rib is the corresponding list of values. Define the implementation of this environment; that is, define the empty-environment and extend-environment functions. Use the functions list-find-position and list-index, shown in Chapter 10, in your implementation. Also, use the following definition:

We call this particular implementation of the ribcage representation the list-of-lists representation (LOLR) of a named environment.

(b) Improve the efficiency of access in the solution to (a) by using a vector for the value of each rib instead of a list:

Lookup in a list through (list-ref ...) requires linear time, whereas lookup in a vector through (vector-ref ...) requires constant time. The list->vector function can be used to convert a list to a vector.

(c) Improve the efficiency of access in the solution to (b) by changing the representation of a rib from a list of two elements to a single pair—so that the values of each rib can be accessed simply by taking the cdr of the rib rather than the car of the cdr (Figure 9.5):

(d) If lookup in an environment is based on lexical distance information, then we can eliminate the symbol list from each rib in the representation and represent environments simply as a list of vectors (Figure 9.6)—so that the values of each rib can be accessed simply by taking the cdr of the rib:

Improve the solution to (c) to incorporate this optimization. Use the following interface for the nameless environment:

We call this particular implementation of the ribcage representation the list-of-vectors representation (LOVR) of a nameless environment.

Exercise 9.8.5 In this programming exercise, you build two different ribcage representations of the environment in Python (Table 9.6).

Table 9.6 List-of-Lists Representations of an Environment Used in Programming Exercise 9.8.5

(a) (list-of-lists representation of a named environment) Complete Programming Exercise 9.8.4.a in Python (Figure 9.7). Since Python does not support function names containing a hyphen, replace each hyphen in the function names in the environment interface with an underscore, as shown in the closure representation of an environment in Python shown in Section 9.8.4. Also, note that lists in Python are used and accessed as if they were vectors, rather than like lists in Scheme, ML, or Haskell. In particular, unlike lists used in functional programming, the individual elements of lists in Python can be directly accessed through an integer index in constant time.

(b) (Friedman, Wand, and Haynes 2001, Exercise 3.25, p. 90) (list-of-lists representation of a nameless environment) Build a list-of-lists (i.e., ribcage) representation of a nameless environment (Figure 9.8) with the following interface:

In other words, complete Programming Exercise 9.8.4.d in Python using a list-of-lists representation (Figure 9.8), instead of a list-of-vectors representation.

In this representation of a nameless environment, the lexical address of a variable reference v is (depth, position); it indicates where to find (and retrieve) the value bound to the identifier used in a reference (i.e., at rib depth in position position). Thus, invoking the function apply_nameless_environment with the parameters environment, depth, and position retrieves the value at the (depth, position) address in the environment.

Exercise 9.8.6 (closure representation of a nameless environment in Scheme) Complete Programming Exercise 9.8.4.d (a nameless environment), but this time use a closure representation, instead of a ribcage representation, for the environment. The closure representation of a named environment in Scheme is given in Section 9.8.2.

Exercise 9.8.7 (closure representation of a nameless environment in Python) Complete Programming Exercise 9.8.5.b (a nameless environment), but this time use a closure representation, instead of a ribcage representation, for the environment. The closure representation of a named environment in Python is given in Section 9.8.3.

Exercise 9.8.8 (abstract-syntax representation of a nameless environment in Racket Scheme) Complete Programming Exercise 9.8.4.d (a nameless environment), but this time use an abstract-syntax representation, instead of a ribcage representation, for the environment (Figure 9.9). The abstract-syntax representation of a named environment in Racket Scheme is developed in Programming Exercise 9.8.3.

Exercise 9.8.9 (abstract-syntax representation of a nameless environment in Python) Complete Programming Exercise 9.8.5.b (a nameless environment), but this time use an abstract-syntax representation, instead of a ribcage representation, for the environment (Figure 9.10). The abstract-syntax representation of a named environment in Python is given in Section 9.8.4 and shown in Figure 9.3.

5. In the von Neumann architecture, we think of and represent code as data; in other words, code and data are represented uniformly in main memory.