Help me write my LISP :) LISP environments, Ruby Hashes

Question

I'm implementing a rudimentary version of LISP in Ruby just in order to familiarize myself with some concepts. I'm basing my implementation off of Peter Norvig's Lispy (http://norvig.com/lispy.html).

There's something I'm missing here though, and I'd appreciate some help...

He subclasses Python's dict as follows:

class Env(dict):
    "An environment: a dict of {'var':val} pairs, with an outer Env."
    def __init__(self, parms=(), args=(), outer=None):
        self.update(zip(parms,args))
        self.outer = outer
    def find(self, var):
        "Find the innermost Env where var appears."
        return self if var in self else self.outer.find(var)

He then goes on to explain why he does this rather than just using a dict. However, for some reason, his explanation keeps passing in through my eyes and out through the back of my head.

Why not use a dict, and then inside the eval function, when a new "sub-environment" needs to be created, just take the existing dict and update the key/value pairs that need to be updated, and pass that new dict into the next eval?

Won't the Python interpreter keep track of the previous "outer" envs? And won't the nature of the recursion ensure that the values are pulled out from "inner" to "outer"?

I'm using Ruby, and I tried to implement things this way. Something's not working though, and it might be because of this, or perhaps not. Here's my eval function, env being a regular Hash:

def eval(x, env = $global_env)
  ........ 
  elsif x[0] == "lambda" then
    ->(*args) { eval(x[2], env.merge(Hash[*x[1].zip(args).flatten(1)])) }
  ........ 
end

The line that matters of course is the "lambda" one.

If there is a functional difference, what's importantly different between what I'm doing here and what Norvig did with his Env class? Can someone describe to me a case where the two will deviate?

If there's no difference, then perhaps someone can enlighten me as to why Norvig uses the Env class. Thanks :)

Answer 1

If variable bindings in your Lisp are immutable, then copying environments is equivalent to linking them. But consider the following case:

(define main
  (lambda ()
    (define i 0)
    (define increment-i
      (lambda ()
        (set! i (+ i 1))))
    (increment-i)
    i))

(main)

If increment-i's environment is completely independent of main's (since it is a copy), the mutation of i will not be visible in main and the above code will return 0. If, on the other hand, the environments are linked, the return value will be 1, as expected.

Answer 2

My Python isn't that good and my Lisp is rather rusty but I'll take a guess about what's going on: you can't get away from pointers even in languages that claim not to have them.

The eval that you're talking about won't make a copy of the dict, it will just make a copy of the reference and you'll end up with two references (AKA variables) that refer to (i.e. point at) the same underlying object. What happens is basically a variant of this:

a = [ 'a', 'b', 'c' ]
b = a
a[1] = 'x'

puts a
# => ["a", "x", "c"]
puts b    
# => ["a", "x", "c"]

His Env class allows the environment to be modified inside the eval without modifying the outer environment while the find method allows you to access the outer environment without needing to know about; also, modifications will end up inside the inner environment and those changes will mask the corresponding values in the outer environment; get operations will access the local environment and the outer environment, set operations will only modify the inner environment.

I guess you could call Env an object level (rather than class level) facade.

I'm not sure what's wrong with your ruby implementation, looks like you're making a modified copy of the environment hash. Can you clarify "Something's not working though"?

Clarification: Env is a symbol table. The wrapping/redirection stuff in find allows you to access the outer symbol table while protecting it from new symbols being added, new symbols will only be added to the inner symbol table. Env essentially manages the closure.