The dream of a lifetime: A lazy variable extent mechanism

ABSTRACT

We define a “rack”, a data abstraction hybrid of a register and a stack. It is used for encapsulating the behavior of the kind of register whose contents may have an extent which requires that it be saved during the execution of an unknown piece of code. A rack can be implemented cleverly to achieve performance benefits over the usual implementation of a stack discipline. The basic idea is that we interpose a state machine controller between the rack abstraction and its stack/registers. This controller can act as an on-the-fly run-time peephole optimizer, eliding unnecessary stack operations. We demonstrate the sorts of savings one might expect by using cleverly implemented racks in the context of a particular caller-saves implementation of an interpreter for the SCHEME dialect of LISP. For sample problems we can expect that only one out of every four pushes that would be done by a conventional machine will be done by the clever version.

REFERENCES

• 1: Hewitt, Carl. "Viewing Control Structures as Patterns of Passing Messages." AI Journal 8, 3 (June 1977), 323-364.
• 2: 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]
• 3: Hauck, E.A., and Dent, B.A. "Burroughs' B6500/B7500 Stack Mechanism." Proc. AFIPS Spring Joint Computer Conference Vol. 32 (1968), 245-251.
• 4: McDermott, Drew V. and Sussman, Gerald Jay. The CONNIVER Reference Manual. AI Memo 295a. MIT AI Lab (January 1974).
• 5: Steele, Guy Lewis Jr., and Sussman, Gerald Jay. The Dream of a Lifetime: A Lazy Scoping Mechanism. AI Memo 527. MIT AI Lab (Cambridge, November 1979).
• 6: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• 7: Bawden, Alan; Greenblatt, Richard; Holloway, Jack; Knight, Thomas; Moon, David; and Weinreb, Daniel. LISP Machine Progress Report. AI Memo 444. MIT AI Lab (August 1977).
• 8: Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199. MIT AI Lab (June 1970).
• 9: Steele, Guy Lewis Jr., and Sussman, Gerald Jay. The Revised Report on SCHEME: A Dialect of LISP. MIT AI Memo 452 (Jan. 1978).
• 10: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 11: Steele, Guy Lewis Jr., and Sussman, Gerald Jay. "Storage Management in a LISP-Based Processor." Proc. Caltech Conference on Very Large Scale Integration (Pasadena, January 1979).
• 12: Steele, Guy Lewis Jr., and Sussman, Gerald Jay. Design of LISP-Based Processors... AI Memo 514. MIT AI Lab (March 1979).
• 13: Holloway, Jack; Steele, Guy L., Jr.; Sussman, Gerald Jay; and Bell, Alan. The SCHEME-79 Chip. AI Memo 559. MIT AI Lab (Dec. 1979).
• 14: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 15: Goldberg, Adele, and Kay, Alan. Smalltalk-72 Instruction Manual. Learning Research Group, Xerox Palo Alto Research Center (March 1976).
• 16: Mitchell Wand, Continuation-Based Program Transformation Strategies, Journal of the ACM (JACM), v.27 n.1, p.164-180, Jan. 1980 [doi>10.1145/322169.322183]
• 17: J. Weizenbaum, Knotted list structures, Communications of the ACM, v.5 n.3, p.161-165, March 1962 [doi>10.1145/366862.366897]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Data abstraction

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

          Nouns: LISP; SCHEME

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

General Terms:
Design, Languages, Performance

Keywords:
Data abstraction, Procedure calling conventions, Register saving, Registers, Stack architecture, Stack discipline