Comment by mark-probst | Hacker News Reader

Comment by mark-probst | Hacker News Reader

Parent Full thread

A dynamic vector will not work in the general case because environments can "fork". You can, however, have shallow environments, where making a new environment based on an old one involves copying some or all of the old environment's fields. That can become a problem, however, if your language supports set!ting local variables - the local variable might be represented in more than one environment, so you'd have to keep track of that and do more than one store.

See Andrew Appel's "Compiling with Continuations", for example.

Could you give an example of where an environment can fork. Do you mean when you create a closure?

This example is completely contrived, of course:

  (let [x 1]
    (defn make-adder [y]
      (fn [] (+ x y)))
    (defn make-multiplier [z]
      (fn [] (* x z)))
    (defn mutate! [new-x]
      (set! x new-x)))

Now for

  (make-adder 2)

we get a function whose environment includes x and y, whereas the environment for

  (make-multiplier 2)

includes x and z. Assuming you have shallow environments, you'll have one environment [x' y] and another one [x'' z], whereas with deep environments (like in ClojureC) you'd have [[x] y] and [[x] z] where the [x] is shared between them. Now, if you call

  (mutate! 3)

with deep environments you only need to store the 3 once (to x), whereas with shallow environments you'll need to store to x' and x''.

Sure, you can come up with pathological cases for either option. For example, with deep environments, the following is inefficient:

  (lambda (a) (lambda (b) (lambda (c) (lambda (d) (lambda (e) a)))))

Reply on news.ycombinator.com