Shallow binding in Lisp 1.5

ABSTRACT

Shallow binding is a scheme which allows the value of a variable to be accessed in a bounded amount of computation. An elegant model for shallow binding in Lisp 1.5 is presented in which context-switching is an environment tree transformation called rerooting. Rerooting is completely general and reversible, and is optional in the sense that a Lisp 1.5 interpreter will operate correctly whether or not rerooting is invoked on every context change. Since rerooting leaves assoc [v, a] invariant, for all variables v and all environments a, the programmer can have access to a rerooting primitive, shallow[], which gives him dynamic control over whether accesses are shallow or deep, and which affects only the speed of execution of a program, not its semantics. In addition, multiple processes can be active in the same environment structure, so long as rerooting is an indivisible operation. Finally, the concept of rerooting is shown to combine the concept of shallow binding in Lisp with Dijkstra's display for Algol and hence is a general model for shallow binding.

REFERENCES

• 1: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 2: Galley, S., and Pfister, G. The MDL Language. Programming Technology Division SYS. 11.01. Proj. MAC, M.I.T., Cambridge, Mass., Sept. 1975.
• 3: Greenblatt, R. The Lisp Machine. A.I. Working Paper 79, M.I.T. A.I. Lab., Cambridge, Mass., Nov. 1974.
• 4: Henhapl, W., and Jones, C.B. A run-time mechanism for referencing variables. Inform. Processing Letters 1 (1971), 14-16.
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 7: Moon, D. MACLISP Reference Manual, Revision 0. Proj. MAC, M.I.T., Cambridge, Mass., 1974.
• 8: Moses, J. The function of FUNCTION in LISP. Memo 199, M.I.T.A.I. Lab., Cambridge, Mass., June 1970.
• 9: Brian Randall , Lawford J. Russell, Algol-60 Implementation, Academic Press, Inc., Orlando, FL, 1964
• 10: Teitelman, W. InterLISP Reference Manual. Xerox Palo Alto Res. Ctr., Palo Alto, Calif., 1974.

INDEX TERMS

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

          Nouns: LISP

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Design, Languages, Performance, Theory

Keywords:
Algol display, FUNARG's, Lisp 1.5, deep binding, environment trees, multiprogramming, shallow binding