env.py
#

The Environment class represents the dynamic environment of McCarthy's original Lisp. The creation of this class is actually an interesting story. As many of you probably know, Paul Graham wrote a paper and code for McCarthy's original Lisp and it was my first exposure to the stark simplicity of the language. The simplicity is breath-taking!

However, while playing around with the code I found that in using the core functions (i.e. null., not., etc.) I was not experiencing the full effect of the original. That is, the original Lisp was dynamically scoped, but the Common Lisp used to implement and run (CLisp in the latter case) Graham's code was lexically scoped. Therefore, by attempting to write high-level functions using only the magnificent 7 and Graham's core functions in the Common Lisp I was taking advantage of lexical scope; something not available to McCarthy and company. Of course, the whole reason that Graham wrote eval. was to enforce dynamic scoping (he used a list of symbol-value pairs where the dynamic variables were added to its front when introduced). However, that was extremely cumbersome to use:

(eval. 'a '((a 1) (a 2)))
;=> 1

So I then implemented a simple REPL in Common Lisp that fed input into eval. and maintained the current environment list. That was fun, but I wasn't sure that I was learning anything at all. Therefore, years later I came across the simple REPL and decided to try to implement my own core environment for the magnificent 7 to truly get a feel for what it took to build a simple language up from scratch. I suppose if I were a real manly guy then I would have found an IBM 704, but that would be totally insane. (email me if you have one that you'd like to sell for cheap)

Anyway, the point of this is that I needed to start with creating an Environment that provided dynamic scoping, and the result is this.

 
class Environment:
#

The binding are stored in a simple dict and the stack discipline is emulated through the parent link

 
    def __init__(self, par=None, bnd=None):
        if bnd:
            self.binds = bnd
        else:
            self.binds = {}

        self.parent = par

        if par:
            self.level = self.parent.level + 1
        else:
            self.level = 0
#

Getting a binding potentially requires the traversal of the parent link

 
    def get(self, key):
        if key in self.binds:
            return self.binds[key]
        elif self.parent:
            return self.parent.get(key)
        else:
            raise ValueError("Invalid symbol " + key)
#

Setting a binding is symmetric to getting

 
    def set(self, key, value):
        if key in self.binds:
            self.binds[key] = value
        elif self.parent:
            self.parent.set(key,value)
        else:
            self.binds[key] = value

    def definedp(self, key):
        if key in self.binds.keys():
            return True

        return False
#

Push a new binding by creating a new Env

Dynamic scope works like a stack. Whenever a variable is created it's binding is pushed onto a global stack. In this case, the stack is simulated through a chain of parent links. So if you were to create the following:

(label a nil)
(label frobnicate (lambda () (cons a nil)))

((lambda (a)
   (frobnicate))
 (quote x))

Then the stack would look like the figure below within the body of frobnicate:

|         |
|         |
| a = 'x  |
| ------- |
| a = nil |
+---------+

Meaning that when accessing a, frobnicate will get the binding at the top of the stack, producing the result (x). This push/pop can become difficult, so people have to do all kinds of tricks to avoid confusion (i.e. pseudo-namespace via variable naming schemes).

 
    def push(self, bnd=None):
        return Environment(self, bnd)

    def pop(self):
        return self.parent

    def __repr__( self):
        ret = "\nEnvironment %s:\n" % self.level
        keys = self.binds.keys()

        for key in keys:
            ret = ret + " %5s: %s\n" % (key, self.binds[key])

        return ret