Here’s a different take on environments. In a pure functional language all data is immutable, end of story, and that would apply to any environments implemented in such a paradigm too. Operators like define would not be allowed to modify an environment, instead such operators would have to return a copy of the environment with the modified value. This has some interesting implications for any language using such an environment. For example:
|
1 2 3 4 5 6 |
define PI = 3.14159265; fn printPI { print(PI); } define PI = 4; fn printNewPI { print(PI); } printPI(); // prints 3.14159265 printNewPI(); // prints 4 |
So each fn captures the current environment, and since nothing is allowed to change, the environment captured is precisely as it was when it was captured.
So how can we make a functional environment that is even remotely efficient? A standard technique is to implement it as a binary tree. Let’s assume symbols have unique numeric identifiers, so that symbol lookup can be reduced to numeric lookup. Then our environment can be a tree who’s left nodes all have indexes less than the current node, and who’s right nodes all have indexes greater than the current node. Here’s a pair of classes that implement such a tree:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
abstract class Env {} class Node extends Env { Env left; Env Right; int index; Datum value; Datum lookup(int ix) { if (ix < index) { return left.lookup(ix); } else if (ix > index) { return right.lookup(ix); } else { return value; } } } class EmptyNode extends Env { Datum lookup(int id) { error(...); } } |
So far so good, but what about extension?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Node extends Env { // ... Env extend(int ix, Datum val) { if (ix < index) { return new Env( left.extend(ix, val), right, index, value ); } else if (ix > index) { return new Env( left, right.extend(ix, val), index, value ); } else { return new Env( left, right, ix, val ); } } } class EmptyNode extends Env { // ... Env extend(int ix, Datum val) { return new Env( self, self, ix, val ); } } |
extend() only makes a copy of the path through the tree that was traversed in order to find the node to add or replace. this means that for a balanced tree, extend() is O(log n) of the number of items in the environment, which is not too bad.
Note also how the EmptyNode behaves as a singleton without explicitly requiring a static instance variable. This makes the implementation quite space efficient too.
The implementation does not support deletion of values, but that is ok since only a non-functional language with backtracking would require it, in order to undo side-effects.
Lastly, note that because these environments are immutable, we do not need any notion of an environment frame to encapsulate local changes, the old environment is still present and will be reverted to outside of a closure just as if we were using environment frames.
Of course this completely ignores the issues of maintaining balanced binary trees, for the sake of simplicity.