An efficient environment allocation scheme in an interpreter for a lexically-scoped LISP

ABSTRACT

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.

REFERENCES

• 1: Eugene Charniak , James R. Meehan , Christopher K. Reisbeck , Drew V. McDermott, Artificial Intelligence Programming, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1987
• 2: Carl Hewitt 1977 Viewing control structures as patterns of passing messages, AI J. 8, no. 3, pp. 323-364
• 3: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 4: Guy L Steele, Debunking the ``Expensive Procedure Call'''' Myth or, Procedure Call Implementations Considered Harmful or, LAMDBA: The Ultimate GOTO, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 5: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 6: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 7: Guy L. Steele Jr. and Gerald J. Sussman 1978a The revised report on SCHEME, a dialect of LISP, Cambridge: MIT AI Laboratory Memo 452
• 8: Guy L. Steele Jr. and Gerald J. Sussman 1978b The art of the interpreter, Cambridge: MIT AI Laboratory Memo 453
• 9: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP
      D.3.4 Processors
          Subjects: Interpreters; Memory management (garbage collection)

General Terms:
Languages, Management