4 ms·
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
by mark-probst 14y ago
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.
- DanWaterworth 14y agoCould you give an example of where an environment can fork. Do you mean when you create a closure?
- mark-probst 14y agoThis 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''.
- DanWaterworth 14y agoSure, 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)))))