ABSTRACT
We show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with “composable continuations”. As part of the development, we extend Meyer and Wand's characterization of the relationship between continuation-passing and direct style to one for continuation-passing vs. general “monadic” style. We further show that the composable-continuations construct can itself be represented using ordinary, non-composable first-class continuations and a single piece of state. Thus, in the presence of two specific computational effects - storage and escapes - any expressible monadic structure (e.g., nondeterminism as represented by the list monad) can be added as a purely definitional extension, without requiring a reinterpretation of the whole language. The paper includes an implementation of the construction (in Standard ML with some New Jersey extensions) and several examples.
- 1.Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. in Third international Symposium on Programming Language implementation and Logic Programming, number 528 in Lecture Notes in Computer Science, pages 1-13, Passau, Germany, August 1991.Google Scholar
- 2.William Clinger and Jonathan Rees. Revised4 report on the algorithmic language Scheme. Lisp Pointers, 4(3):1-55, July 1991. Google ScholarDigital Library
- 3.Olivier Danvy and Andrzej Filinski. Abstracting control. In Proceedings of the 1990 A CM Conference on Lisp and Functional Programming, pages 151-160, Nice, France, June 1990. Google ScholarDigital Library
- 4.Olivier Danvy and Andrzej Filinski. Representing control: A study of the CPS transformation. Mathematical Structures in Computer Science, 2(4):361- 391, December 1992.Google ScholarCross Ref
- 5.Bruce F. Duba, Robert Harper, and David Mac- Queen. Typing first-class continuations in ML. In Proceedings of the Eighteenth Annual A CM Symposium on Principles of Programming Languages, pages 163-173, Orlando, Florida, January 1991. Google ScholarDigital Library
- 6.Matthias Felleisen. The theory and practice of firstclass prompts, in Proceedings of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, pages 180-190, San Diego, California, January 1988. Google ScholarDigital Library
- 7.Matthias Felleisen and Robert Hieb. The revised report on the syntactic theories of sequential control and state. Theoretical Computer Science, 103(2):235-271, September 1992. Google ScholarDigital Library
- 8.Matthias Felleisen, Mitchell Wand, Daniel P. Friedman, and Bruce F. Duba. Abstract continuations: A mathematical semantics for handling full functional jumps. In Proceedings of the 1988 A CM Conference on Lisp and Functional Programming, pages 52-62, Snowbird, Utah, July 1988. Google ScholarDigital Library
- 9.Robert Hieb, R. Kent Dybvig, and Carl Bruggeman. Representing control in the presence of firstclass continuations, in Proceedings of the A CM SIGPLAN '90 Conference on Programming Languages Design and Implementation, pages 66-77, White Plains, New York, June 1990. Google ScholarDigital Library
- 10.Gregory F. Johnson and Dominic Duggan. Stores and partial continuations as first-class objects in a language and its environment. In Proceedings of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, pages 158-168, San Diego, California, january 1988. Google ScholarDigital Library
- 11.David J. King and Philip Wadler. Combining monads. In J. Launchbury and P. M. Sansom, editors, Functional Programming, Glasgow 1992, pages 134-143, Ayr, Scotland, 1993. Springer- Verlag. Google ScholarDigital Library
- 12.Julia L. Lawall and Olivier Danvy. Continuationbased partial evaluation. Indiana University and Aarhus University. Personal communication, October 1993.Google Scholar
- 13.Albert R. Meyer and Mitchell Wand. Continuation semantics in typed lambda-calculi (summary). In Rohit Parikh, editor, Logics of Programs - Proceedings, number 193 in Lecture Notes in Computer Science, pages 219-224, Brooklyn, June 1985. Google ScholarDigital Library
- 14.Eugenio Moggi. Computational lambda-calculus and monads, in Proceedings of ~he Fourth Annual Symposium on Logic in Computer Science, pages 14-23, Pacific Grove, California, June 1989. IEEE. Google ScholarDigital Library
- 15.Eugenio Moggi. An abstract view of programming languages. Technical Report ECS-LFCS-90- 113, Laboratory for Foundations of Computer Science, University of Edinburgh, Edinburgh, Scotland, April 1990.Google Scholar
- 16.Eugenio Moggi. Notions of computation and monads. Information and Computation, 93(1):55-92, July 1991. Google ScholarDigital Library
- 17.Chetan R. Murthy. Control operators, hierarchies, and pseudo-classical type systems" A-translation at work. In Proceedings of the A CM SIGPLAN Workshop on Continuations, pages 49-71, San Francisco, California, June 1992. (Technical Report No. STAN-CS-92-1426, Department of Computer Science, Stanford University).Google Scholar
- 18.Simon L. Peyton Jones and Philip Wadler. Imperative functional programming. In Proceedings of the Twentieth Annual A CM Symposium on Principles of Programming Languages, pages 71-84, Charleston, South Carolina, January 1993. Google ScholarDigital Library
- 19.Gordon D. Plotkin. Call-by-name, call-by-value and the ,~-calculus. Theoretical Computer Science, 1(2):125-159, December 1975.Google ScholarCross Ref
- 20.Christian Queinnec and Bernard Serpette. A dynamic extent control operator for partial continuations. In Proceedings of the Eighteenth Annual A CM Symposium on Principles of Programming Languages, pages 174-184, Orlando, Florida, January 1991. Google ScholarDigital Library
- 21.John H. Reppy. CML: A higher-order concurrent language. In Proceedings of the A CM SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 293-305, Toronto, Canada, June 1991. Google ScholarDigital Library
- 22.john C. Reynolds. On the relation between direct and continuation semantics. In Jacques Loeckx, editor, 2nd Colloquium on Automata, Languages and Programming, number 14 in Lecture Notes in Computer Science, pages 141-156, Saarbriicken, West Germany, July 1974. Google Scholar
- 23.:Ion G. Riecke. Delimiting the scope of effects. In Functional Programming Languages and Computer Architecture 1993, pages 146-155, Copenhagen, Denmark, June 1993. ACM Press. Google Scholar
- 24.Amr Sabry and Matthias Felleisen. Reasoning about programs in continuation-passing style, in Proceedings of the 1992 A CM Conference on Lisp and Functional Programming, pages 288-298, San Francisco, California, june 1992. Revised version to appear in Lisp and Symbolic Computation. Google ScholarDigital Library
- 25.Ravi Sethi and Adrian Tang. Constructing call-byvalue continuation semantics. Journal of the A CM, 27(3):580-597, july 1980. Google ScholarDigital Library
- 26.Dorai Sitaram and Matthias Felleisen. Control delimiters and their hierarchies. Lisp and Symbolic Computation, 3(1):67-99, January 1990. Google ScholarDigital Library
- 27.Dorai Sitaram and Matthias Felleisen. Reasoning with continuations II: Full abstraction for models of control. In Proceedings of the 1990 A CM Conference on Lisp and Functional Programming, pages 161-175, Nice, France, June 1990. Google ScholarDigital Library
- 28.Brian C. Smith. Reflection and Semantics in a Procedural Language. PhD thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, January 1982. MIT-LCS-TR-272.Google Scholar
- 29.Guy L. Steele, Jr. Building interpreters by composing monads. In Proceedings of the Twenty.First An. anal A CM Symposium on Principles of Programming Languages, Portland, Oregon, January 1994. (To appear). Google ScholarDigital Library
- 30.Joseph E. Stoy. The congruence of two programming language definitions. Theoretical Computer Science, 13(2):151-174, February 1981.Google ScholarCross Ref
- 31.Philip Wadler. Comprehending monads. Mathematical Structures in Computer Science, 2(4):461- 493, December 1992. (An earlier version appeared in Proceedings of the 1990 A CM Conference on Lisp and Functional Programming). Google ScholarDigital Library
- 32.Philip Wadler. The essence of functional programming (invited talk). In Proceedings of the Nineteenth Annual A CM Symposium on Principles of Programming Languages, pages 1-14, Albuquerque, New Mexico, January 1992. Google ScholarDigital Library
- 33.Philip Wadler. Monads and eomposable continuations. Lisp and Symbolic Computation, 1994. (To appear). Google ScholarDigital Library
- 34.Mitchell Wand and Daniel P. Friedman. The mystery of the tower revealed: A non-reflective description of the reflective tower. Lisp and Symbolic Computation, 1(1), May 1988.Google Scholar
Index Terms
- Representing monads
Recommendations
Representing layered monads
POPL '99: Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThere has already been considerable research on constructing modular, monad-based specifications of computational effects (state, exceptions, nondeterminism, etc.) in programming languages. We present a simple framework in this tradition, based on a ...
DSL implementation using staging and monads
DSL '99: Proceedings of the 2nd conference on Domain-specific languagesThe impact of Domain Specific Languages (DSLs) on software design is considerable. They allow programs to be more concise than equivalent programs written in a high-level programming languages. They relieve programmers from making decisions about data-...
Modeling with monads: extensible modeling semantics as syntactic sugar
EOOLT '16: Proceedings of the 7th International Workshop on Equation-Based Object-Oriented Modeling Languages and ToolsWe present an extensible implementation of Modelica-style modeling semantics. Modeling features are implemented using an intuitive encoding as an extensible state monad. Monadic computation naturally yields model composition and interpretation. This in ...
Comments