Abstract
Monads are a well-established tool for modelling various computational effects. They form the semantic basis of Moggi’s computational metalanguage, the metalanguage of effects for short, which made its way into modern functional programming in the shape of Haskell’s do-notation. Standard computational idioms call for specific classes of monads that support additional control operations. Here, we introduce Kleene monads, which additionally feature nondeterministic choice and Kleene star, i.e. nondeterministic iteration, and we provide a metalanguage and a sound calculus for Kleene monads, the metalanguage of control and effects, which is the natural joint extension of Kleene algebra and the metalanguage of effects. This provides a framework for studying abstract program equality focussing on iteration and effects. These aspects are known to have decidable equational theories when studied in isolation. However, it is well known that decidability breaks easily; e.g. the Horn theory of continuous Kleene algebras fails to be recursively enumerable. Here, we prove several negative results for the metalanguage of control and effects; in particular, already the equational theory of the unrestricted metalanguage of control and effects over continuous Kleene monads fails to be recursively enumerable. We proceed to identify a fragment of this language which still contains both Kleene algebra and the metalanguage of effects and for which the natural axiomatisation is complete, and indeed the equational theory is decidable.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Benton, P.N., Bierman, G.M., de Paiva, V.: Computational types from a logical perspective. J. Funct. Prog. 8(2), 177–193 (1998)
Curien, P.-L., di Cosmo, R.: A confluent reduction for the lambda-calculus with surjective pairing and terminal object. J. Funct. Program. 6(2), 299–327 (1996)
Fluet, M., Morrisett, G., Ahmed, A.J.: Linear regions are all you need. In: Sestoft, P. (ed.) ESOP 2006. LNCS, vol. 3924, pp. 7–21. Springer, Heidelberg (2006)
Hinze, R.: Deriving backtracking monad transformers. ACM SIGPLAN Notices 35(9), 186–197 (2000)
Hyland, M., Plotkin, G.D., Power, J.: Combining effects: Sum and tensor. Theoret. Comput. Sci. 357, 70–99 (2006)
Jacobs, B., Poll, E.: Coalgebras and Monads in the Semantics of Java. Theoret. Comput. Sci. 291, 329–349 (2003)
Jouannaud, J.-P., Munoz, M.: Termination of a set of rules modulo a set of equations. In: Shostak, R.E. (ed.) CADE 1984. LNCS, vol. 170, pp. 175–193. Springer, Heidelberg (1984)
Kiselyov, O., Shan, C., Friedman, D., Sabry, A.: Backtracking, interleaving, and terminating monad transformers. In: Functional Programming, ICFP 2005, pp. 192–203. ACM Press, New York (2005)
Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events. Inf. Comput. 110, 366–390 (1994)
Kozen, D.: Kleene algebra with tests and commutativity conditions. In: Margaria, T., Steffen, B. (eds.) TACAS 1996. LNCS, vol. 1055, pp. 14–33. Springer, Heidelberg (1996)
Kozen, D.: Nonlocal flow of control and Kleene algebra with tests. In: Logic in Computer Science, LICS 2008, pp. 105–117. IEEE Computer Society Press, Los Alamitos (2008)
Moggi, E.: Notions of computation and monads. Inf. Comput. 93, 55–92 (1991)
Moggi, E., Sabry, A.: Monadic encapsulation of effects: A revised approach (extended version). J. Funct. Prog. 11, 591–627 (2001)
Mossakowski, T., Schröder, L., Goncharov, S.: A generic complete dynamic logic for reasoning about purity and effects (Extended version to appear in Formal Aspects of Computing). In: Fiadeiro, J.L., Inverardi, P. (eds.) FASE 2008. LNCS, vol. 4961, pp. 199–214. Springer, Heidelberg (2008)
Peyton Jones, S. (ed.): Haskell 98 Language and Libraries — The Revised Report. Cambridge University Press (2003); J. Funct. Prog. 13 (2003)
Schröder, L., Mossakowski, T.: Generic exception handling and the Java monad. In: Rattray, C., Maharaj, S., Shankland, C. (eds.) AMAST 2004. LNCS, vol. 3116, pp. 443–459. Springer, Heidelberg (2004)
Schröder, L., Mossakowski, T.: Monad-independent dynamic logic in HasCASL. J. Logic Comput. 14, 571–619 (2004)
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: Symposium on Theory of Computing, STOC 1973, pp. 1–9. ACM Press, New York (1973)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goncharov, S., Schröder, L., Mossakowski, T. (2009). Kleene Monads: Handling Iteration in a Framework of Generic Effects. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds) Algebra and Coalgebra in Computer Science. CALCO 2009. Lecture Notes in Computer Science, vol 5728. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03741-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-03741-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03740-5
Online ISBN: 978-3-642-03741-2
eBook Packages: Computer ScienceComputer Science (R0)