Adding delimited and composable control to a production programming environment

ABSTRACT

Operators for delimiting control and for capturing composable continuations litter the landscape of theoretical programming language research. Numerous papers explain their advantages, how the operators explain each other (or don't), and other aspects of the operators' existence. Production programming languages, however, do not support these operators, partly because their relationship to existing and demonstrably useful constructs - such as exceptions and dynamic binding - remains relatively unexplored.

In this paper, we report on our effort of translating the theory of delimited and composable control into a viable implementation for a production system. The report shows how this effort involved a substantial design element, including work with a formal model, as well as significant practical exploration and engineering.

The resulting version of PLT Scheme incorporates the expressive combination of delimited and composable control alongside dynamic-wind, dynamic binding, and exception handling. None of the additional operators subvert the intended benefits of existing control operators, so that programmers can freely mix and match control operators.

REFERENCES

• 1: Dariusz Biernacki , Olivier Danvy , Chung-chieh Shan, On the static and dynamic extents of delimited continuations, Science of Computer Programming, v.60 n.3, p.274-297, May 2006 [doi>10.1016/j.scico.2006.01.002]
• 2: John Clements , Matthias Felleisen, A tail-recursive machine with stack inspection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.1029-1052, November 2004 [doi>10.1145/1034774.1034778]
• 3: John Clements , Matthew Flatt , Matthias Felleisen, Modeling an Algebraic Stepper, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.320-334, April 02-06, 2001
• 4: Olivier Danvy , Andrzej Filinski, Abstracting control, Proceedings of the 1990 ACM conference on LISP and functional programming, p.151-160, June 27-29, 1990, Nice, France [doi>10.1145/91556.91622]
• 5: R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry. A monadic framework for delimited continuations. Journal of Functional Programming, 2006. To appear.
• 6: Mattias Felleisen, The theory and practice of first-class prompts, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.180-190, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73576]
• 7: Matthias Felleisen, On the expressive power of programming languages, Science of Computer Programming, v.17 n.1-3, p.35-75, Dec. 1991
• 8: Andrzej Filinski, Representing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.446-457, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178047]
• 9: Robert Bruce Findler , John Clements , Cormac Flanagan , Matthew Flatt , Shriram Krishnamurthi , Paul Steckler , Matthias Felleisen, DrScheme: a programming environment for Scheme, Journal of Functional Programming, v.12 n.2, p.159-182, March 2002 [doi>10.1017/S0956796801004208]
• 10: Matthew Flatt. PLT MzScheme: Language manual. Technical Report PLT-TR2007-1-v370, PLT Scheme, 2007.
• 11: Daniel P. Friedman , Christopher T. Haynes, Constraining control, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.245-254, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318654]
• 12: Martin Gasbichler , Michael Sperber, Final shift for call/cc:: direct implementation of shift and reset, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.271-282, October 04-06, 2002, Pittsburgh, PA, USA
• 13: Martin Gasbichler, Eric Knauel, Michael Sperber, and Richard A. Kelsey. How to add threads to a sequential language without getting tangled up. In Proc. Workshop on Scheme and Functional Programming, 2003.
• 14: Carl A. Gunter , Didier Rémy , Jon G. Riecke, A generalization of exceptions and control in ML-like languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.12-23, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224173]
• 15: David Herman, Aaron Tomb, and Cormac Flanagan. Space-efficient gradual typing. In Proc. Trends in Functional Programming, 2007.
• 16: R. Hieb , R. Kent Dybvig, Continuations and concurrency, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.128-136, March 14-16, 1990, Seattle, Washington, United States
• 17: Robert Hieb , R. Kent Dybvig , Claude W. Anderson, III, Subcontinuations, Lisp and Symbolic Computation, v.7 n.1, p.83-110, Jan. 1994 [doi>10.1007/BF01019946]
• 18: N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
• 19: Richard A. Kelsey and Jonathan Rees. Scheme48, 2007. http://s48.org/
• 20: Oleg Kiselyov. How to remove a dynamic prompt: static and dynamic delimited continuation operators are equally expressible. Technical Report TR611, Indiana University Computer Science, 2005a.
• 21: Oleg Kiselyov. Generic implementation of all four *F* operators: from control0 to shift, 2005. http://okmij.org/ftp/Computation/Continuations.html#generic-control.
• 22: Oleg Kiselyov , Chung-chieh Shan , Amr Sabry, Delimited dynamic binding, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 23: Shriram Krishnamurthi , Peter Walton Hopkins , Jay Mccarthy , Paul T. Graunke , Greg Pettyjohn , Matthias Felleisen, Implementation and use of the PLT scheme Web server, Higher-Order and Symbolic Computation, v.20 n.4, p.431-460, December 2007 [doi>10.1007/s10990-007-9008-y]
• 24: James Laird, Exceptions, Continuations and Macro-expressiveness, Proceedings of the 11th European Symposium on Programming Languages and Systems, p.133-146, April 08-12, 2002
• 25: Jacob Matthews, Robert Bruce Findler, Matthew Flatt, and Matthias Felleisen. A visual environment for developing context-sensitive term rewriting systems. In Proc. International Conference on Rewriting Techniques and Applications, volume 3091 of Lecture Notes in Computer Science, 2004.
• 26: Christian Queinnec , Bernard Serpette, A dynamic extent control operator for partial continuations, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.174-184, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99610]
• 27: Jon G. Riecke , Hayo Thielecke, Typed Exeptions and Continuations Cannot Macro-Express Each Other, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.635-644, July 11-15, 1999
• 28: Chung-chieh Shan. Shift to control. In Proc. Workshop on Scheme and Functional Programming, pages 99--107, 2004.
• 29: Dorai Sitaram, Handling control, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.147-155, June 21-25, 1993, Albuquerque, New Mexico, United States
• 30: Dorai Staram , Matthias Felleisen, Control delimiters and their hierarchies, Lisp and Symbolic Computation, v.3 n.1, p.67-99, Jan. 1990 [doi>10.1007/BF01806126]
• 31: Michael Sperber (Ed.). The revised^5.97 report on the algorithmic language Scheme, 2007.
• 32: Hayo Thielecke, On Exceptions Versus Continuations in the Presence of State, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.397-411, April 02, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

General Terms:
Design, Languages