Rather than a single “Environment” type, a compiler distinguishes between compile-time and run-time environments.

In an interpreter, the value of a symbol is the result of looking it up in the current environment. That lookup process involves traversing the environment, frame by frame, until the symbol is found and the associated value is retrieved. The interpreter’s environment is constructed at run-time by closures extending a previous environment with bindings of formal to actual arguments.

A compiler can’t know the values of variables at compile time. It can however, determine the location those variables will have in the environment at run-time. A compiler will perform lexical analysis of code analagous to evaluation. It passes and (when entering a closure) extends a compile-time environment that contains only the symbols, not their values. When it comes across a variable access it looks up the symbol in the compile time environment and replaces the variable with its address in the environment (i.e.three frames back, two variables in).

At run time that data can rapidly be retrieved from the run-time environment (which contains only the data) without any laborious traversal and comparison.

That gives us three classes and a dumb data object for the location (all of this is pseudocode)

1. A compile-time environment
   
   class CTE { private CTE parentEnv; private Symbol[] symbols; Location lookup(Symbol s, int framecount=0) { if (symbols.contains(s)) { return new Location(framecount, symbols.positionOf(s)); } else { return parentEnv.lookup(s, framecount + 1); } } }

   1 2 3 4 5 6 7 8 9 10 11 12

   class CTE {     private CTE parentEnv;     private Symbol[] symbols;       Location lookup(Symbol s, int framecount=0) {         if (symbols.contains(s)) {             return new Location(framecount, symbols.positionOf(s));         } else {             return parentEnv.lookup(s, framecount + 1);         }     } }

2. A run-time environment:
   
   class RTE { private RTE parentEnv; private Datum[] data; Datum lookup(Location l) { this._lookup(l.framecount, l.pos); } Datum _lookup(int framecount, int pos) { if (framecount) { return parentEnv._lookup(framecount - 1, pos); } else { return data.valueAt[pos]; } } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class RTE {     private RTE parentEnv;     private Datum[] data;       Datum lookup(Location l) {         this._lookup(l.framecount, l.pos);     }       Datum _lookup(int framecount, int pos) {         if (framecount) {             return parentEnv._lookup(framecount - 1, pos);         } else {             return data.valueAt[pos];         }     } }

3. And of course a terminating Null object for the CTE
   
   class EmptyCTE extends CTE { Location lookup(Symbol s, int framecount=0) { error("symbol %s not found", symbol.name); } }

   1 2 3 4 5

   class EmptyCTE extends CTE {     Location lookup(Symbol s, int framecount=0) {         error("symbol %s not found", symbol.name);     } }

Extenders for the CTE and RTE take arrays of symbols and values respectively, otherwise they are just the same as interpreter extend() methods.