Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T20:22:40.188Z Has data issue: false hasContentIssue false
  • English
  • Français

Quotienting the delay monad by weak bisimilarity

Published online by Cambridge University Press:  17 October 2017

JAMES CHAPMAN Open the ORCID record for JAMES CHAPMAN [Opens in a new window] ,
TARMO UUSTALU Open the ORCID record for TARMO UUSTALU [Opens in a new window]  and
NICCOLÒ VELTRI
JAMES CHAPMAN
Affiliation:
Department of Computer and Information Sciences, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, U.K. Email: james.chapman@strath.ac.uk
TARMO UUSTALU
Affiliation:
Department of Software Science, Tallinn University of Technology, Akadeemia tee 21B, 12618 Tallinn, Estonia Email: tarmo@cs.ioc.ee, niccolo@cs.ioc.ee
NICCOLÒ VELTRI
Affiliation:
Department of Software Science, Tallinn University of Technology, Akadeemia tee 21B, 12618 Tallinn, Estonia Email: tarmo@cs.ioc.ee, niccolo@cs.ioc.ee
Get access Rights & Permissions [Opens in a new window]

Abstract

The delay datatype was introduced by Capretta (Logical Methods in Computer Science, 1(2), article 1, 2005) as a means to deal with partial functions (as in computability theory) in Martin-Löf type theory. The delay datatype is a monad. It is often desirable to consider two delayed computations equal, if they terminate with equal values, whenever one of them terminates. The equivalence relation underlying this identification is called weak bisimilarity. In type theory, one commonly replaces quotients with setoids. In this approach, the delay datatype quotiented by weak bisimilarity is still a monad–a constructive alternative to the maybe monad. In this paper, we consider the alternative approach of Hofmann (Extensional Constructs in Intensional Type Theory, Springer, London, 1997) of extending type theory with inductive-like quotient types. In this setting, it is difficult to define the intended monad multiplication for the quotiented datatype. We give a solution where we postulate some principles, crucially proposition extensionality and the (semi-classical) axiom of countable choice. With the aid of these principles, we also prove that the quotiented delay datatype delivers free ω-complete pointed partial orders (ωcppos).

Altenkirch et al. (Lecture Notes in Computer Science, vol. 10203, Springer, Heidelberg, 534–549, 2017) demonstrated that, in homotopy type theory, a certain higher inductive–inductive type is the free ωcppo on a type X essentially by definition; this allowed them to obtain a monad of free ωcppos without recourse to a choice principle. We notice that, by a similar construction, a simpler ordinary higher inductive type gives the free countably complete join semilattice on the unit type 1. This type suffices for constructing a monad, which is isomorphic to the one of Altenkirch et al. We have fully formalized our results in the Agda dependently typed programming language.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 29 , Special Issue 1: Special Issue: Best Papers Presented at ICTAC 2015 , January 2019 , pp. 67 - 92
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abbott, M., Altenkirch, T. and Ghani, N. (2005). Containers: Constructing strictly positive types. Theoretical Computer Science 342 (1) 3–27.Google Scholar
Ahman, D., Chapman, J. and Uustalu, T. (2014). When is a container a comonad? Logical Methods in Computer Science 10 (3), article 14.Google Scholar
Altenkirch, T., Danielsson, N.A. and Kraus, N. (2017). Partiality, revisited: The partiality monad as a quotient inductive-inductive type. In: Esparza, J. and Murawski, A. (eds.) Proceedings of the 20th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2017, Lecture Notes in Computer Science, vol. 10203, Springer, Heidelberg, 534–549.Google Scholar
Bauer, A., Gross, J., Lumsdaine, P.L., Shulman, M., Sozeau, M. and Spitters, B. (2017). The HoTT library: A formalization of homotopy type theory in Coq. In: Proceedings of 6th ACM SIGPLAN Conference on Certified Programs and Proofs, CPP 2017, ACM, New York, 164–172.Google Scholar
Bauer, A. and Lesnik, D. (2012). Metric spaces in synthetic topology. Annals of Pure and Applied Logic 163 (2) 87–100.Google Scholar
Kennedy, A. and Varming, C. (2009). Some domain theory and denotational semantics in Coq. In: Berghofer, S., Nipkow, T. Urban, C. and Wenzel, M. (eds.) Proceedings of 22nd International Conference on Theorem Proving in Higher Order Logics, TPHOLs 2009, Lecture Notes in Computer Science, vol. 5674, Springer, Heidelberg, 115–130.Google Scholar
Capretta, V. (2005). General recursion via coinductive types. Logical Methods in Computer Science, 1 (2), article 1.Google Scholar
Chicli, L., Pottier, L. and Simpson, C. (2003). Mathematical quotients and quotient types in Coq. In: Geuvers, H. and Wiedijk, F. (eds.) Selected Papers from Int. Wksh. on Types for Proofs and Programs, TYPES 2002, Lecture Notes in Computer Science, vol. 2646, Springer, Heidelberg, 95–107.Google Scholar
Cockett, R., Díaz-Boïls, J., Gallagher, J. and Hrubes, P. (2012). Timed sets, complexity, and computability. In: Berger, U. and Mislove, M. (eds.) Proceedings of 28th Conference on the Mathematical Foundations of Program Semantics, MFPS XXVIII, Electronic Notes in Theoretical Computer Science, vol. 286, Elsevier, Amsterdam, 117–137.Google Scholar
Coquand, T., Mannaa, B. and Ruch, F. (2017). Stack semantics of type theory. Preprint. https://arxiv.org/abs/1701.02571Google Scholar
Escardó, M. (2004). Synthetic topology of data types and classical spaces. In: Desharnais, J. and Panangaden, P. (eds.) Proceedings of Wksh. on Domain-Theoretical Methods for Probabilistic Programming, Electronic Notes in Theoretical Computer Science, vol. 87, Elsevier, Amsterdam, 21–156.Google Scholar
Goncharov, S., Rauch, C. and Schröder, L. (2015). Unguarded recursion on coinductive resumptions. In: Ghica, D. (ed.) Proceedings of 31st Conference on Mathematical Foundations of Programming Semantics, MFPS XXXI, Electronic Notes in Theoretical Computer Science, vol. 319, Elsevier, Amsterdam, 183–198.Google Scholar
Hofmann, M. (1997). Extensional Constructs in Intensional Type Theory. CPHS/BCS Distinguished Dissertations. Springer, London.Google Scholar
Hyland, J.M.E. (1990). First steps in synthetic domain theory. In: Carboni, A., Pedicchio, M. C. and Rosolini, G. (eds.) Proceedings of International Conference on Category Theory, Lecture Notes in Mathematics, vol. 1488, Springer, Heidelberg, 131–156.Google Scholar
Hughes, J. (2000). Generalising monads to arrows. Science of Computer Programming 37 (1–3) 67–111.Google Scholar
Jacobs, B., Heunen, C. and Hasuo, I. (2009). Categorical semantics for arrows. Journal of Functional Programming 19 (3–4) 403–438.Google Scholar
Kraus, N., Escardó, M., Coquand, T. and Altenkirch, T. (2013). Generalizations of Hedberg's theorem. In: Hasegawa, M. (ed.) Proceedings of 11th International Conference on Typed Lambda Calculi and Applications, TLCA 2013, Lecture Notes in Computer Science, vol. 7941, Springer, Heidelberg, 173–188.Google Scholar
Maietti, M.E. (1999). About effective quotients in constructive type theory. In: Altenkirch, T., Naraschewski, W. and Reus, B. (eds.) Selected Papers from International Wksh. on Types for Proofs and Programs, TYPES '98, Lecture Notes in Computer Science, vol. 1657, Springer, Heidelberg, 166–178.Google Scholar
Martin-Löf, P. (2006). 100 years of Zermelo's axiom of choice: What was the problem with it? Computer Journal 49 (3) 345–350.Google Scholar
Moggi, E. (1991). Notions of computation and monads. Information and Computation 93 (1) 55–92.Google Scholar
Mulry, P.S. (1994). Partial map classifiers and partial Cartesian closed categories. Theoretical Computer Science 136 (1) 109–123.Google Scholar
Norell, U. (2009). Dependently typed programming in Agda. In: Koopman, P., Plasmeijer, R. and Swierstra, S.D. (eds.) Revised Lectures from Proceedings of the 6th International School on Advanced Functional Programming, AFP 2008, Lecture Notes in Computer Science, vol. 5832, Springer, Heidelberg, 230–266.Google Scholar
Nuo, L. (2015). Quotient types in type theory. PhD thesis, University of Nottingham.Google Scholar
Rosolini, G. (1986). Continuity and Effectiveness in Topoi. PhD thesis, University of Oxford.Google Scholar
Troelstra, A.S. and Van Dalen, D. (1988). Constructivism in Mathematics: An Introduction, vol. I. Studies in Logic and the Foundations of Mathematics, vol. 121, North-Holland, Amsterdam.Google Scholar
The Univalent Foundations Program (2013). Homotopy Type Theory: Univalent Foundations of Mathematics. Institute for Advanced Study, Princeton, NY. http://homotopytypetheory.org/book.Google Scholar