Will Clinger
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.
- Bartley 86.David H Bartley and John C Jenscn, "The Implementation of PC Scheme", Proceedings oft he 1986 ACM Conference on Lisp and Functional Programming, August 1986, pages 86-93. Google Scholar
Digital Library
- Caudill 86.Patrick I Caudill and Alien Wirfs-Brock, "A Third Generation SmaUtalk-80 Implementation", Conference Proceedings of OOPSLA '86, SIGPLAN Notices 21, 11, November 1986, pages 119-130. Google ScholarDigital Library
- Danvy 87.Olivier Danvy, "Memory Allocation and Higher- Order Functions", Proceedings of the SIGPLAN '8717ymposiurn on Interpreters and Interpretive Techniques, June 1987, pages 241-252. Google ScholarDigital Library
- Deutsch 84.L Peter Deutsch and Allan M Schiffman, "Efficient Implementation of the Smalltalk-80 System", Conference Record of the llth Annual ACM Symposium on Principles of Programming Languages, January 1984, pages 297--302. Google ScholarDigital Library
- Gabriel 85.Richard P Gabriel, Performance and Evaluation of Lisp Systems, The MIT Press, 1985. Google ScholarDigital Library
- Goldberg 83.Adele Goldberg and David Robson, Smalhalk- 80: the Language and its Implementation, Addison-Wesley, 1983. Google ScholarDigital Library
- Haynes 84.Christopher T Haynes and Daniel P Friedman, "Engines Build Process Abstractions", Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, August 1984, pages 18-24. Google ScholarDigital Library
- 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.Google Scholar
- Kranz 86.David Kranz, Richard Kelsey, Jonathan Rees, Paul Hudak, James Philbin, and Norman Adams, "Orbit: An Optimizing Compiler for Scheme", Proceedingsof the SIG- PLAN '86 Symposium on Compiler Construction, July 1986, pages 219-233. Google ScholarDigital Library
- Kranz 88.David Andrew Kranz, ORBIT: An Optimizing Compiler for Scheme, PhD thesis, Yale University, May 1988.Google ScholarDigital Library
- Miranda 87.Eliot Miranda, "BrouHaHa--A Portable Smalltalk Interpreter", Conference Proceedings of OOPSLA '87, SIGPLAN Notices 22, 12, December 1987, pages 354-365. Google ScholarDigital Library
- Moss 87.j Eliot B Moss, "Managing Stack Frames in Smalltalk", Proceedings of the SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques, lune 1987, pages 229- 240. Google ScholarDigital Library
- Rees 86.Jonathan Rees and William Clinger {editors}, "Reviseda Report on the Algorithmic Language Scheme", SIG- PLAN Noticea 21, 12, December 1986, pages 37-79. Google ScholarDigital Library
- Samples 86.A Dain Samples, David Ungar, and Paul Hilfinger, "SOAR: Smalltalk without Bytecodes", Conference Proceedings of OOPSLA ' 86, SIGPLAN Notices 21, 11, November 1986, pages 107-118. Google ScholarDigital Library
- Semantic 87.Semantic Microsystems, MacScheme~Toolsmith, August 1987.Google Scholar
- Suzuki 84.Norihisa Suzuki and Minom Terada, "Creating Efficient Systems for Object-Oriented Languages", Conference Record of the llth Annual ACM Symposium on Principles of Programming Languages, January 1984, pages 290-296. Google ScholarDigital Library
- Ungar 87.David M Ungar, The Design and Evaluation of a High Performance Smalltalk System, The MIT Press, 1987. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Implementation strategies for continuations
Recommendations
Formalizing Implementation Strategies for First-Class Continuations
ESOP '00: Proceedings of the 9th European Symposium on Programming Languages and SystemsWe present the first formalization of implementation strategies for first-class continuations. The formalization hinges on abstract machines for continuation-passing style (CPS) programs with a special treatment for the current continuation, accounting ...
Implementation Strategies for First-Class Continuations
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. We review several implementation strategies for continuations and compare ...
Subtyping delimited continuations
ICFP '11: Proceedings of the 16th ACM SIGPLAN international conference on Functional programmingWe present a type system with subtyping for first-class delimited continuations that generalizes Danvy and Filinski's type system for shift and reset by maintaining explicit information about the types of contexts in the metacontext. We exploit this ...
Comments