Henry G. Baker
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.
- 1 Bobrow, D.G., and Wegbreit, B. A model and stack implementation of multiple environments. Comm. A CM 16, 10(Oct. 1973), 591-603. Google Scholar
Digital Library
- 2 Galley, S., and Pfister, G. The MDL Language. Programming Technology Division SYS. 11.01. Proj. MAC, M.I.T., Cambridge, Mass., Sept. 1975.Google Scholar
- 3 Greenblatt, R. The Lisp Machine. A.I. Working Paper 79, M.I.T. A.I. Lab., Cambridge, Mass., Nov. 1974.Google Scholar
- 4 Henhapl, W., and Jones, C.B. A run-time mechanism for referencing variables. Inform. Processing Letters 1 (1971), 14-16.Google ScholarCross Ref
- 5 Knuth, D. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 1968, p. 417. Google ScholarDigital Library
- 6 McCarthy, J., Abrahams, P., Edwards, D., Hart, T., and Levin, M. LISP 1.5 Programmer's Manual. M.I.T. Press, Cambridge, Mass., 1965, especially pp. 12-13, 70-71. Google ScholarDigital Library
- 7 Moon, D. MACLISP Reference Manual, Revision 0. Proj. MAC, M.I.T., Cambridge, Mass., 1974.Google Scholar
- 8 Moses, J. The function of FUNCTION in LISP. Memo 199, M.I.T.A.I. Lab., Cambridge, Mass., June 1970.Google Scholar
- 9 Randell, B., and Russell, LJ. ALGOL 60 Implementation. Academic Press, London and New York, 1964, pp. 65-68, 75. Google ScholarDigital Library
- 10 Teitelman, W. InterLISP Reference Manual. Xerox Palo Alto Res. Ctr., Palo Alto, Calif., 1974.Google Scholar
Index Terms
- Shallow binding in Lisp 1.5
Recommendations
Binding strategies and scope rules are independent
The programming language Lisp employs dynamic scope rules. Binding is usually of the shallow variety, but deep (also called funarg) binding is also available. Block-structured languages, on the other hand, use static scope rules. Here, binding is always ...
The buried binding and dead binding problems of Lisp 1.5: sources of incomparability in garbage collector measurements
Lisp has become the language of choice for many applications such as artificial intelligence programs or symbol manipulation. The original implementation of Lisp 1.5 was a concise, elegant statement of the semantics of the language. Although production ...
Optimiizing Static Scope Lisp by Repetitive Interpretation of Recursive Function Calls
This paper presents some recent results in interpreter optimization. The techniques of shallow binding and repetitive interpretation of tail recursive functions are adapted to Lisp with static scoping as the binding method for-all identifiers. Then a ...
Comments