Implementation strategies for continuations

ABSTRACT

Scheme and Smalltalk continuations may have unlimited extent. This means that a purely stack-based implementation of continuations, as suffices for most languages, is inadequate. Several implementation strategies have been described in the literature. Determining which is best requires knowledge of the kinds of programs that will commonly be run. Danvy, for example, has conjectured that continuation captures occur in clusters. That is, the same continuation, once captured, is likely to be captured again. As evidence, Danvy cited the use of continuations in a research setting. We report that Danvy's conjecture is somewhat true in the commercial setting of MacScheme+Toolsmith™, which provides tools for developing Macintosh user interfaces in Scheme. These include an interrupt-driven event system and multitasking, both implemented by liberal use of continuations. We describe several implementation strategies for continuations and compare four of them using benchmarks. We conclude that the most popular strategy may have a slight edge when continuations are not used at all, but that other strategies perform better when continuations are used and Danvy's conjecture holds.

REFERENCES

• Bartley 86: David H. Bartley , John C. Jensen, The implementation of PC Scheme, Proceedings of the 1986 ACM conference on LISP and functional programming, p.86-93, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319852]
• Caudill 86: Patrick J. Caudill , Allen Wirfs-Brock, A third generation Smalltalk-80 implementation, Conference proceedings on Object-oriented programming systems, languages and applications, p.119-130, September 29-October 02, 1986, Portland, Oregon, United States
• Danvy 87: O. Danvy, Memory allocation and higher-order functions, Papers of the Symposium on Interpreters and interpretive techniques, p.241-252, June 24-26, 1987, St. Paul, Minnesota, United States
• Deutsch 84: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• Gabriel 85: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• Goldberg 83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• Haynes 84: Christopher T. Haynes , Daniel P. Friedman, Engines build process abstractions, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.18-24, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802018]
• Holloway 80: Jack Holloway, Guy L Steele, Gerald Jay Sussman, and Alan Bell, "The SCHEME-79 Chip", MIT AI Laboratory, AI Memo 559, january 1980.
• Kranz 86: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• Kranz 88: David Andrew Kranz, ORBIT: An Optimizing Compiler for Scheme, PhD thesis, Yale University, May 1988.
• Miranda 87: Eliot Miranda, BrouHaHa- A portable Smalltalk interpreter, ACM SIGPLAN Notices, v.22 n.12, p.354-365, Dec. 1987
• Moss 87: J. E. B. Moss, Managing stack frames in Smalltalk, Papers of the Symposium on Interpreters and interpretive techniques, p.229-240, June 24-26, 1987, St. Paul, Minnesota, United States
• Rees 86: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• Samples 86: A. Dain Samples , David Ungar , Paul Hilfinger, SOAR: Smalltalk without bytecodes, Conference proceedings on Object-oriented programming systems, languages and applications, p.107-118, September 29-October 02, 1986, Portland, Oregon, United States
• Semantic 87: Semantic Microsystems, MacScheme~Toolsmith, August 1987.
• Suzuki 84: Norihisa Suzuki , Minoru Terada, Creating efficient systems for object-oriented languages, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.290-296, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800541]
• Ungar 87: David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987
• Wirfs-Brock 88: Allen Wirfs-Brock, personal communication, April 1988. Tektronix Smalltalk is described in {Caudill 86, which was not detailed enough for us to realize that Tektronix Smalltalk uses the stack/heap strategy rather than the stack strategy.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

General Terms:
Design, Performance, Theory