An efficient environment allocation scheme in an interpreter for a lexically-scoped LISP
Drew McDermott · 1980
Lexically-scoped LISP dialects offer great flexibility and expressive power. Unfortunately, they tend to be inefficiently implemented, because many interpreter structures such as variable binding environments must be allocated in the heap rather than on the stack. One solution to this problem is to allocate them on the stack, then move them to the heap if necessary. This means moving the environment of a function only if it passes an environment pointer to the last function it calls, returns an environment pointer as a value, sets a global variable to one, or CONSes one into a list structures. To make this work, the interpreter must be able to tell which current environments a function call is the last function call of, and must know exactly what parts of the stack can be moved. This approach saves dramatically on garbage collections, at the price of increasing function application time a bit. It is worth doing if free storage is not abundant, or if it is important to avoid garbage collections.