Philip Wadler
Abstract
How can we integrate interaction into a purely declarative language? This tutorial describes a solution to this problem based on a monad. The solution has been implemented in the functional language Haskell and the declarative language Escher. Comparisons are given with other approaches to interaction based on synchronous streams, continuations, linear logic, and side effects.
- ABRAMSKY, S. 1993. Computational interpretations of linear logic. Theor. Comput. Sci. 111, 3-57. Google Scholar
- ACHTEN, P. AND PLASMEIJER, R. 1995. The ins and outs of Clean I/O. J. Funct. Program. 5, 1 (Jan.), 81-110.Google Scholar
- BARENDSEN, E. AND SMETSERS, S. 1993. Conventional and uniqueness typing in graph rewrite systems (extended abstract). In Proceedings of the 13th Conference on the Foundations of Software Technology and Theoretical Computer Science (Bombay, India). Google Scholar
- BARR, M. AND WELLS, C. 1985. Toposes, Triples, and Theories. Springer-Verlag.Google Scholar
- BIRD, R. AND WADLER, P. 1987. Introduction to Functional Programming. Prentice Hall, Englewood Cliffs, NJ. Google Scholar
- CHURCH, A. 1940. A formulation of the simple theory of types. J. Symbol. Logic 5, 56-68.Google Scholar
- CUPITT, J. 1989. A brief walk through KAOS. Tech. Rep. 52, Computing Laboratory, University of Kent at Canterbury.Google Scholar
- CHEN, C.-P. AND HUDAK, P. 1997. Rolling your own mutable ADT--a connection between linear types and monads. In 24th Symposium on Principles of Programming Languages (Paris, France, Jan.), ACM, New York. Google Scholar
- DENNETT, D. 1991. Consciousness Explained. Little, Brown & Co., Boston, MA.Google Scholar
- FILINSKI, A. 1994. Representing monads. In 21st Symposium on Principles of Programming Languages (Portland, OR, Jan.), ACM, New York. Google Scholar
- FOKKER, J. 1995. Functional parsers. In Advanced Functional Programming, J. Jeuring and E. Meijer, Eds., LNCS 925, Springer- Verlag. Google Scholar
- GIRARD, J.-Y. 1987. Linear logic. Theor. Comput. Sci. 50, 1-102. Google Scholar
- GOGUEN, J. 1990. Higher-order functions considered unnecessary for higher-order programming. In Research Topics in Functional Prefrogramming, D. Turner, Ed., Addison-Wesley, Reading, MA. Google Scholar
- GORDON, A. 1993. Functional Programming and Input~Output. Distinguished Dissertations in Computer Science, Cambridge University Press, New York. Google Scholar
- GUZMAN, J. AND HUDAK, P. 1990. Singlethreaded polymorphic lambda calculus. In Fifth IEEE Symposium on Logic in Computer Science, (Philadelphia, PA, June).Google Scholar
- HALL, C., HAMMOND, K., PARTAIN, W., PEYTON JONES, S. L., AND WADLER, P. 1992. The Glasgow Haskell compiler: A retrospective. In Proceedings of the 1992 Glasgow Workshop on Functional Programming (Ayr, Scotland, July), Springer Verlag Workshops in Computing Series, 134-143. Google Scholar
- HATCLIFF, J. AND DANVY, O. 1994. A generic account of continuation-passing styles. In 21st Symposium on Principles of Programming Languages (Portland, OR, Jan.), ACM, New York. Google Scholar
- HOLMSTROM, S. 1988. A linear functional language. In Proceedings of the Workshop on Implementation of Lazy Functional Languages, Programming Methodology Group Rep. 53 (Chalmers University of Technology, Sept.).Google Scholar
- HOWARD, W. A. 1980. The formulae-as-types notion of construction. In To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism, J. P. Seldin and J. R. Hindley, Eds., Academic Press. (The original version was circulated privately in 1969.)Google Scholar
- HUDAK, P. AND SUNDARESH, R.S. 1989. On the expressiveness of purely functional I/O systems. Tech. Rep. YALEU/DCS/RR-665, Yale University Dept of Computer Science, March.Google Scholar
- HUDAK, P., PEYTON JONES, S., AND WADLER, P. Eds. 1992. Report on the programming language Haskell, a non-strict purely-functional programming language, Version 1.2. Sigplan Not. 27, 5 (May). Google Scholar
- HUGHES, g. 1995. The design of a pretty-printing library. In Advanced Functional Programming, J. Jeuring and E. Meijer, Eds., LNCS 925, Springer-Verlag. Google Scholar
- JONES, M. P. 1993. A system of constructor classes: Overloading and implicit higher-order polymorphism. In Conference on Functional Programming Languages and Computer Architecture (Copenhagen, June), ACM, New York. Google Scholar
- JONES, M.P. 1994. Gofer 2.30 implementation. Available by ftp from ftp.cs.nott.ac.uk/nott-fp/ languages/gofer.Google Scholar
- JONES, M. P. 1995. Functional programming with overloading and higher-order polymorphism. In Advanced Functional Programming, J. Jeuring and E. Meijer, Eds., LNCS 925, Springer-Verlag. Google Scholar
- JONES, M. P. AND DUPONCHEEL, L. 1993. Composing monads. Res. Rep. YALE/DCS/RR- 1004, Yale University, New Haven, Dec.Google Scholar
- JONES, S.B. 1995. Experiences with Clean I/O, Proceedings of the Glasgow Workshop on Functional Programming (Ullapool, Scotland, July), Electronic Workshops in Computing, Springer-Verlag. Google Scholar
- KING, D. AND LAUNCHBURY, J. 1995. Structuring depth-first search algorithms in Haskell. In 22nd Symposium on Principles of Programming Languages (San Francisco, CA, Jan.), ACM, New York. Google Scholar
- KING, D. AND WADLER, P. 1992. Combining monads. In Glasgow Workshop on Functional Programming (Ayr, Scotland, July), Workshops in Computing Series, Springer-Verlag. Google Scholar
- LAFONT, Y. 1988. The linear abstract machine. Theor. Comput. Sci. 59, 157-180. Google Scholar
- LANDIN, P.J. 1965. A correspondence between ALGOL 60 and Church's lambda notation: Parts I and II. Commun. ACM 8, 2,3 (Feb./ March), 89-101, 158-165. Google Scholar
- LAUNCHBURY, J. 1993. Lazy imperative programming. In Workshop on State in Programming Languages (Copenhagen, Denmark, June), ACM, New York.Google Scholar
- LAUNCHBURY, J. 1995. Graph algorithms with a functional flavour. In Advanced Functional Programming, J. Jeuring and E. Meijer, Eds., LNCS 925, Springer-Verlag. Google Scholar
- LAUNCHBURY, J. AND PEYTON JONES, S. L. 1994. Lazy functional state threads. In Conference on Programming Language Design and Implementation (Orlando, FL), ACM, New York. Google Scholar
- LAUNCHBURY, J. AND SABRY, A. 1997. Monadic state: Axiomatization and type safety (ICFP 1997) In Second International Conference on Functional Programming (Amsterdam, The Netherlands, July), ACM, New York. Google Scholar
- LIANG, S., HUDAK, P., AND JONES, M.P. 1995. Monad transformers and modular interpreters. In 22nd Symposium on Principles of Programming Languages, (San Francisco, CA, Jan.), ACM, New York. Google Scholar
- LLOYD, g.W. 1995. Declarative programming in Escher. Tech. Rep. CSTR-95-013, Department of Computer Science, University of Bristol, June. Google Scholar
- MACLANE, S. 1971. Categories for the Working Mathematician. Springer-Verlag.Google Scholar
- MEIJER, E. AND JEURING, J. 1995. Merging monads and folds for functional programming. In Advanced Functional Programming, J. Jeuring and E. Meijer, Eds., LNCS 925, Springer-Verlag. Google Scholar
- MILNER, R., TOFTE, M., AND HARPER, R. 1990. The Definition of Standard ML. MIT Press, Cambridge, MA. Google Scholar
- MILNER, R., TOFTE, M., HARPER, R., AND MAC- QUEEN, D. 1997. The Definition of Standard ML (Revised). MIT Press, Cambridge, MA. Google Scholar
- MOGGI, E. 1989. Computational lambda-calculus and monads. In Symposium on Logic in Computer Science, (Asilomar, CA, June), IEEE. Google Scholar
- MOGGI, E. 1991. Notions of computation and monads. Inf. Comput. 93, 1. Google Scholar
- ODERSKY, M., RABIN, D., AND HUDAK, P. 1993. Call-by-name, assignment, and the lambda calculus. In 20th Symposium on Principles of Programming Languages (Charleston, SC, Jan.), ACM, New York. Google Scholar
- PAULSON, L.C. 1991. ML for the Working Programmer. Cambridge University Press, New York. Google Scholar
- PERRY, N. 1989. I/O and inter-language calling for functional languages. In Proceedings of Ninth International Conference of the Chilean Computer Society and 15th Latin American Conference on Informatics (Chile). Also available at ftp://smis-asterix/pub/ResearchPapers/ FL_IO IL Chile_Ju189.ps.Z.Google Scholar
- PETERSON, J. AND HAMMOND, K., Eds. 1996. Report on the programming language Haskell, a non-strict purely-functional programming language, Version 1.3. Tech. Rep., Yale University, May.Google Scholar
- PEYTON JONES, S. L. AND FINNE, S. 1995. Composing Haggis. Manuscript.Google Scholar
- PEYTON JONES, S. L. AND WADLER, P. 1993. Imperative functional programming. In 20th Symposium on Principles of Programming Languages, (Charleston, SC, Jan.), ACM, New York. Google Scholar
- PEYTON JONES, S. L., GORDON, A., AND FINNE, S. 1996. Concurrent Haskell. In 23rd Symposium on Principles of Programming Languages (St. Petersburg, FL, Jan.), ACM, New York. Google Scholar
- PLOTKIN, G. 1975. Call-by-name, call-by-value, and the ~-calculus. Theor. Comput. Sci. 1, 125-159.Google Scholar
- REYNOLDS, J. C. 1993. The discoveries of continuations. Lisp Symbol. Comput. 6, 3/4, 233- 247. Google Scholar
- SABRY, A. AND WADLER, P. 1996. A reflection on call-by-value. In First International Conference on Functional Programming (Philadelphia, PA, May), ACM, New York. Google Scholar
- SCHMIDT, D.A. 1985. Detecting global variables in denotational specifications. ACM Trans. Program. Lang. Syst. 7, 299-310. Google Scholar
- SPIVEY, M. 1990. A functional theory of exceptions. Sci. Comput. Program. 14, 1 (June), 25-42. Google Scholar
- STEELE, G. L., JR. 1994. Building interpreters by composing monads. In 21st Symposium on Principles of Programming Languages (Portland, OR, Jan.), ACM, New York. Google Scholar
- STOYE, W. 1986. Message-based functional operating systems. Sci. Comput. Program. 6, 3, 291-311. Google Scholar
- WADLER, P. 1985. How to replace failure by a list of successes. In Conference on Functional Programming Languages and Computer Architecture (Nancy, France, Sept.), LNCS 201, Springer-Verlag. Google Scholar
- WADLER, P. 1990a. Comprehending monads. In Conference on Lisp and Functional Programming (Nice, France, June), ACM, New York. Google Scholar
- WADLER, P. 1990b. Linear types can change the world! In Programming Concepts and Methods (Sea of Galilee, Israel, April), M. Broy and C. Jones, Eds., North Holland.Google Scholar
- WADLER, P. 1992. The essence of functional programming (invited talk). In 19th Symposium on Principles of Programming Languages (Albuquerque, NM, Jan.), ACM, New York. Google Scholar
- WADLER, P. 1993a. Monads for functional programming. In Program Design Calculi, M. Broy, Ed., NATO ASI Series, Springer-Verlag, 1993. Also in Advanced Functional Programming, J. Jeuring and E. Meijer, Eds., LNCS 925, Springer-Verlag, 1995. Google Scholar
- WADLER, P. 1993b. A taste of linear logic. (Invited talk). Mathematical Foundations of Computing Science (Gdansk, Poland, Aug.), LNCS 711, Springer-Verlag. Google Scholar
- WADLER, P. 1994. Monads and composable continuations. Lisp Symbol. Comput. 7, 1 (Jan.), 39 -55. Google Scholar
- WADLER, P. 1995. How to declare an imperative. In International Logic Programming Symposium, (Dec.), John Lloyd, Ed., MIT Press, Cambridge, MA.Google Scholar
- WARREN, D. H. D. 1981. Higher-order extensions to Prolog--are they needed? In Machine Intelligence 10, D. Michie, et al., Eds., Ellis Horwood, Chichester, UK.Google Scholar
Recommendations
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell SymposiumProgrammers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Polymonad programming in Haskell
IFL '15: Proceedings of the 27th Symposium on the Implementation and Application of Functional Programming LanguagesPolymonads were recently introduced by Hicks et al. as a unified approach to programming with different notions of monads. Their work was mainly focused on foundational aspects of the approach. In this article, we show how to incorporate the notion of ...
Bringing back monad comprehensions
Haskell '11: Proceedings of the 4th ACM symposium on HaskellThis paper is about a Glasgow Haskell Compiler (GHC) extension that generalises Haskell's list comprehension notation to monads. The monad comprehension notation implemented by the extension supports generator and filter clauses, as was the case in the ...
Reviews
Max Hailperin
Wadler attempts to popularize a topic fashionable in the functional programming community: the use of a monad to integrate input/output into a purely functional setting. As in other approaches, the functional program computes a value that describes the interaction, rather than engaging in the interaction itself. A mechanism external to the program then performs the described interaction. What distinguishes the monadic approach is the particular operations constituting the data type of interaction descriptions. An action affects the world, but also returns a value. (For example, reading a character advances the cursor and returns the character.) Thus for each type, T, there is a type, IO[T], of action descriptors that, when performed, return a T. There are two constructors of action descriptors beyond those for primitive I/O actions. One takes a value, x, of type T and returns a descriptor of type IO[T]. When it is performed, no action results, and x is returned. The other constructor takes a descriptor, d, of type IO[T1] and a function, f, from T1 to IO[T2] and composes them to produce a descriptor of type IO[T2]. Performing the composite descriptor has three steps: perform d, apply f to the value returned, and perform the descriptor computed by step 2. Regrettably, Wadler's attempt at popularization is not entirely successful, because he presumes a reading knowledge of Haskell, which few outside the functional programming community have. As Haskell now includes monadic I/O, people with an out-of-date knowledge of Haskell will benefit most from this tutorial.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments