Representing monads

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Representing monads

Full text

Pdf (1.19 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Portland, Oregon, United States

Pages: 446 - 457

Year of Publication: 1994

ISBN:0-89791-636-0

Author

Andrzej Filinski

School of Computer Science, Carnegie Mellon University, Pittsburgh, PA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 62, Citation Count: 38

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174675.178047 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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.
	2	H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
	3	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]
	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.
	5	Bruce Duba , Robert Harper , David MacQueen, Typing first-class continuations in ML, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99608]
	6	M. 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 , Robert Hieb, The revised report on the syntactic theories of sequential control and state, Theoretical Computer Science, v.103 n.2, p.235-271, 14 Sept. 1992 [doi>10.1016/0304-3975(92)90014-7]
	8	Matthias Felleisen , Mitch Wand , Daniel Friedman , Bruce Duba, Abstract continuations: a mathematical semantics for handling full jumps, Proceedings of the 1988 ACM conference on LISP and functional programming, p.52-62, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62684]
	9	R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.66-77, June 1990, White Plains, New York, United States
	10	G. F. Johnson , D. Duggan, Stores and partial continuations as first-class objects in a language and its environment, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.158-168, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73574]
	11	David J. King , Philip Wadler, Combining Monads, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.134-143, July 06-08, 1992
	12	Julia L. Lawall and Olivier Danvy. Continuationbased partial evaluation. Indiana University and Aarhus University. Personal communication, October 1993.
	13	Albert R. Meyer , Mitchell Wand, Continuation Semantics in Typed Lambda-Calculi (Summary), Proceedings of the Conference on Logic of Programs, p.219-224, June 17-19, 1985
	14	E. Moggi, Computational lambda-calculus and monads, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.14-23, June 1989, Pacific Grove, California, United States
	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.
	16	Eugenio Moggi, Notions of computation and monads, Information and Computation, v.93 n.1, p.55-92, July 1991 [doi>10.1016/0890-5401(91)90052-4]
	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).
	18	Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
	19	Gordon D. Plotkin. Call-by-name, call-by-value and the ,~-calculus. Theoretical Computer Science, 1(2):125-159, December 1975.
	20	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]
	21	John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
	22	John C. Reynolds, On the Relation between Direct and Continuation Semantics, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.141-156, July 29-August 02, 1974
	23	Jon G. Riecke, Delimiting the scope of effects, Proceedings of the conference on Functional programming languages and computer architecture, p.146-155, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165200]
	24	Amr Sabry , Matthias Felleisen, Reasoning about programs in continuation-passing style., Proceedings of the 1992 ACM conference on LISP and functional programming, p.288-298, June 22-24, 1992, San Francisco, California, United States
	25	Ravi Sethi , Adrian Tang, Constructing Call-by-Value Continuation Semantics, Journal of the ACM (JACM), v.27 n.3, p.580-597, July 1980 [doi>10.1145/322203.322216]
	26	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]
	27	Dorai Sitaram , Matthias Felleisen, Reasoning with continuations II: full abstraction for models of control, Proceedings of the 1990 ACM conference on LISP and functional programming, p.161-175, June 27-29, 1990, Nice, France [doi>10.1145/91556.91626]
	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.
	29	Guy L. Steele, Jr., Building interpreters by composing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.472-492, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178068]
	30	Joseph E. Stoy. The congruence of two programming language definitions. Theoretical Computer Science, 13(2):151-174, February 1981.
	31	Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]
	32	Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
	33	Philip Wadler, Monads and composable continuations, Lisp and Symbolic Computation, v.7 n.1, p.39-56, Jan. 1994 [doi>10.1007/BF01019944]
	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.

CITED BY 39

	Jakov Kučan, Retraction Approach to CPS Transform, Higher-Order and Symbolic Computation, v.11 n.2, p.145-175, September 1998
	Kenichi Asai, Online partial evaluation for shift and reset, ACM SIGPLAN Notices, v.37 n.3, p.19-30, March 2002
	Tim Sheard, A type-directed, on-line, partial evaluator for a polymorphic language, ACM SIGPLAN Notices, v.32 n.12, p.22-35, Dec. 1997
	Mads Sig Ager , Dariusz Biernacki , Olivier Danvy , Jan Midtgaard, A functional correspondence between evaluators and abstract machines, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.8-19, August 27-29, 2003, Uppsala, Sweden
	Bernd Grobauer, Cost recurrences for DML programs, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Bernd Grobauer , Zhe Yang, The second Futamura projection for type-directed partial evaluation, ACM SIGPLAN Notices, v.34 n.11, p.22-32, Nov. 1999
	Peter J. Thiemann, Cogen in six lines, ACM SIGPLAN Notices, v.31 n.6, p.180-189, June 15, 1996
	Eijiro Sumii , Naoki Kobayashi, Online-and-offline partial evaluation (extended abstract): a mixed approach, ACM SIGPLAN Notices, v.34 n.11, p.12-21, Nov. 1999
	Eijiro Sumii , Naoki Kobayashi, A Hybrid Approach to Online and Offline Partial Evaluation, Higher-Order and Symbolic Computation, v.14 n.2-3, p.101-142, September 2001
	Julia L. Lawall , Olivier Danvy, Continuation-based partial evaluation, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.227-238, July-Sept. 1994
	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
	Philip Wadler, How to declare an imperative, ACM Computing Surveys (CSUR), v.29 n.3, p.240-263, Sept. 1997
	Yukiyoshi Kameyama , Masahito Hasegawa, A sound and complete axiomatization of delimited continuations, ACM SIGPLAN Notices, v.38 n.9, p.177-188, September 2003
	Olivier Danvy, Type-directed partial evaluation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-257, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Andrzej Filinski, Representing layered monads, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.175-188, January 20-22, 1999, San Antonio, Texas, United States
	Martin Gasbichler , Michael Sperber, Final shift for call/cc:: direct implementation of shift and reset, ACM SIGPLAN Notices, v.37 n.9, p.271-282, September 2002
	Zena M. Ariola , Hugo Herbelin , Amr Sabry, A type-theoretic foundation of continuations and prompts, ACM SIGPLAN Notices, v.39 n.9, September 2004
	Bernd Grobauer , Zhe Yang, The Second Futamura Projection for Type-Directed Partial Evaluation, Higher-Order and Symbolic Computation, v.14 n.2-3, p.173-219, September 2001
	Sheng Liang , Paul Hudak , Mark Jones, Monad transformers and modular interpreters, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 23-25, 1995, San Francisco, California, United States
	Dariusz Biernacki , Olivier Danvy , Chung-chieh Shan, On the dynamic extent of delimited continuations, Information Processing Letters, v.96 n.1, p.7-17, 16 October 2005
	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
	Miley Semmelroth , Amr Sabry, Monadic encapsulation in ML, ACM SIGPLAN Notices, v.34 n.9, p.8-17, Sept. 1999
	Yukiyoshi Kameyama, Axioms for control operators in the CPS hierarchy, Higher-Order and Symbolic Computation, v.20 n.4, p.339-369, December 2007
	Chung-Chieh Shan, A static simulation of dynamic delimited control, Higher-Order and Symbolic Computation, v.20 n.4, p.371-401, December 2007
	Mads Sig Ager , Olivier Danvy , Jan Midtgaard, A functional correspondence between monadic evaluators and abstract machines for languages with computational effects, Theoretical Computer Science, v.342 n.1, p.149-172, 6 September 2005
	Oleg Kiselyov , Chung-chieh Shan , Amr Sabry, Delimited dynamic binding, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Andrzej Filinski, On the relations between monadic semantics, Theoretical Computer Science, v.375 n.1-3, p.41-75, May, 2007
	Martin Hyland , Paul Blain Levy , Gordon Plotkin , John Power, Combining algebraic effects with continuations, Theoretical Computer Science, v.375 n.1-3, p.20-40, May, 2007
	Ernie G. Manes, Implementing collection classes with monads, Mathematical Structures in Computer Science, v.8 n.3, p.231-276, June 1998
	John Hatcliff , Olivier Danvy, A computational formalization for partial evaluation, Mathematical Structures in Computer Science, v.7 n.5, p.507-541, October 1997
	Amr Sabry, What is a purely functional language?, Journal of Functional Programming, v.8 n.1, p.1-22, January 1998
	Peter Thiemann, Combinators for program generation, Journal of Functional Programming, v.9 n.5, p.483-525, September 1999
	H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998
	Matthew Flatt , Gang Yu , Robert Bruce Findler , Matthias Felleisen, Adding delimited and composable control to a production programming environment, ACM SIGPLAN Notices, v.42 n.9, September 2007
	Hugo Herbelin , Silvia Ghilezan, An approach to call-by-name delimited continuations, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Yukiyoshi Kameyama , Oleg Kiselyov , Chung-chieh Shan, Shifting the stage: staging with delimited control, Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, January 19-20, 2009, Savannah, GA, USA
	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
	Tristan Crolard , Emmanuel Polonowski , Pierre Valarcher, Extending the loop language with higher-order procedural variables, ACM Transactions on Computational Logic (TOCL), v.10 n.4, p.1-37, August 2009
	Jacques Carette , Oleg Kiselyov , Chung-chieh Shan, Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages, Journal of Functional Programming, v.19 n.5, p.509-543, September 2009