Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-14T15:10:34.093Z Has data issue: false hasContentIssue false
  • English
  • Français

Cubical Agda: A dependently typed programming language with univalence and higher inductive types

Part of: ICFP 2019

Published online by Cambridge University Press:  06 April 2021

ANDREA VEZZOSI Open the ORCID record for ANDREA VEZZOSI [Opens in a new window] ,
ANDERS MÖRTBERG  and
ANDREAS ABEL
ANDREA VEZZOSI
Affiliation:
Department of Computer Science, IT University of Copenhagen, Copenhagen, Denmark (e-mail: avez@itu.dk)
ANDERS MÖRTBERG
Affiliation:
Department of Mathematics, Stockholm University, Stockholm, Sweden (e-mail: anders.mortberg@math.su.se)
ANDREAS ABEL
Affiliation:
Department of Computer Science and Engineering, Chalmers and Gothenburg University, Gothenburg, Sweden (e-mail: andreas.abel@gu.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Proof assistants based on dependent type theory provide expressive languages for both programming and proving within the same system. However, all of the major implementations lack powerful extensionality principles for reasoning about equality, such as function and propositional extensionality. These principles are typically added axiomatically which disrupts the constructive properties of these systems. Cubical type theory provides a solution by giving computational meaning to Homotopy Type Theory and Univalent Foundations, in particular to the univalence axiom and higher inductive types (HITs). This paper describes an extension of the dependently typed functional programming language Agda with cubical primitives, making it into a full-blown proof assistant with native support for univalence and a general schema of HITs. These new primitives allow the direct definition of function and propositional extensionality as well as quotient types, all with computational content. Additionally, thanks also to copatterns, bisimilarity is equivalent to equality for coinductive types. The adoption of cubical type theory extends Agda with support for a wide range of extensionality principles, without sacrificing type checking and constructivity.

Type
Research Article
Information
Journal of Functional Programming , Volume 31 , 2021 , e8
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

References

Abel, A., Öhman, J. & Vezzosi, A. (2017) Decidability of conversion for type theory in type theory. Proc. ACM Program. Lang. 2(POPL), 23:1–23:29.Google Scholar
Abel, A., Pientka, B., Thibodeau, D. & Setzer, A. (2013) Copatterns: Programming infinite structures by observations. SIGPLAN Not. 48(1), 27–38.CrossRefGoogle Scholar
Agda Development Team. (2018) Agda 2.5.4.2 Documentation.Google Scholar
Ahrens, B., Capriotti, P. & Spadotti, R. (2015) Non-wellfounded trees in homotopy type theory. CoRR abs/1504.02949.Google Scholar
Altenkirch, T., McBride, C. & Swierstra, W. (2007) Observational equality, now! In PLPV’07: Proceedings of the 2007 Workshop on Programming Languages Meets Program Verification. ACM, pp. 57–68.Google Scholar
Altenkirch, T. & Scoccola, L. (2020) The integers as a higher inductive type. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS’20. Association for Computing Machinery, pp. 67–73.CrossRefGoogle Scholar
Angiuli, C., Brunerie, G., Coquand, T., Hou (Favonia), K.-B., Harper, R. & Licata, D. R. (2019) Syntax and Models of Cartesian Cubical Type Theory. Preprint.Google Scholar
Angiuli, C., Cavallo, E., Mörtberg, A. & Zeuner, M. (2020) Internalizing Representation Independence with Univalence. Preprint arXiv:2009.05547v2 [cs.PL].Google Scholar
Angiuli, C., Hou (Favonia), K.-B. & Harper, R. (2017) Computational Higher Type Theory III: Univalent Universes and Exact Equality. Preprint arXiv:1712.01800v1.CrossRefGoogle Scholar
Angiuli, C., Hou (Favonia), K.-B. & Harper, R. (2018) Cartesian cubical computational type theory: Constructive reasoning with paths and equalities. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), Ghica, D. & Jung, A. (eds), Leibniz International Proceedings in Informatics (LIPIcs), vol. 119. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 6:1–6:17.Google Scholar
Angiuli, C., Morehouse, E., Licata, D. R. & Harper, R. (2016) Homotopical patch theory. J. Funct. Program. 26, e18.CrossRefGoogle Scholar
Annenkov, D., Capriotti, P. & Kraus, N. (2017) Two-Level Type Theory and Applications.Google Scholar
Bickford, M. (2018) Formalizing Category Theory and Presheaf Models of Type Theory in Nuprl. CoRR abs/1806.06114.Google Scholar
Birkedal, L., Bizjak, A., Clouston, R., Grathwohl, H. B., Spitters, B. & Vezzosi, A. (2019) Guarded cubical type theory. J. Auto. Reasoning 63(2), 211–253.CrossRefGoogle Scholar
Brady, E. (2013) Idris, a general-purpose dependently typed programming language: Design and implementation. J. Funct. Program. 23(5), 552–593.CrossRefGoogle Scholar
Brunerie, G. (2016) On the Homotopy Groups of Spheres in Homotopy Type Theory. PhD thesis, Université de Nice.Google Scholar
Cavallo, E. & Harper, R. (2019) Higher inductive types in cubical computational type theory. Proc. ACM Program. Lang. 3(POPL), 1:1–1:27.CrossRefGoogle Scholar
Chu, S., Weitz, K., Cheung, A. & Suciu, D. (2017) Hottsql: Proving query rewrites with univalent sql semantics. SIGPLAN Not. 52(6), 510–524.CrossRefGoogle Scholar
Cockx, J. & Abel, A. (2018) Elaborating dependent (co)pattern matching. Proc. ACM Program. Lang. 2(ICFP), 75:1–75:30.CrossRefGoogle Scholar
Cockx, J. & Devriese, D. (2018) Proof-relevant unification: Dependent pattern matching with only the axioms of your type theory. J. Funct. Program. 28, e12.CrossRefGoogle Scholar
Cohen, C., Coquand, T., Huber, S. & Mörtberg, A. (2015) Cubicaltt. https://github.com/mortberg/cubicaltt.Google Scholar
Cohen, C., Coquand, T., Huber, S. & Mörtberg, A. (2018) Cubical type theory: A constructive interpretation of the univalence axiom. In Types for Proofs and Programs (TYPES 2015). LIPIcs, vol. 69, pp. 5:1–5:34.Google Scholar
Cohen, C., Dénès, M. & Mörtberg, A. (2013) Refinements for free! In Certified Programs and Proofs, Gonthier, G. & Norrish, M. (eds). Lecture Notes in Computer Science, vol. 8307. Springer International Publishing, pp. 147–162.Google Scholar
Coquand, T. & Danielsson, N. A. (2013) Isomorphism is equality. Indagationes Mathematicae 24(4), 1105–1120.CrossRefGoogle Scholar
Coquand, T., Huber, S. & Mörtberg, A. (2018) On higher inductive types in cubical type theory. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. LICS’18. ACM, pp. 255–264.CrossRefGoogle Scholar
Coquand, T., Huber, S. & Sattler, C. (2019) Homotopy Canonicity for Cubical Type Theory. Preprint available at http://www.cse.chalmers.se/ simonhu/papers/can.pdf.Google Scholar
Danielsson, N. A. (2020) Higher Inductive Type Eliminators Without Paths. http://www.cse.chalmers.se/nad/publications/danielsson-hits-without-paths.html.Google Scholar
de Moura, L., Kong, S., Avigad, J., van Doorn, F. & von Raumer, J. (2015) The lean theorem prover. In Automated Deduction - CADE-25, 25th International Conference on Automated Deduction, Berlin, Germany, August 1–7, 2015, Proceedings.Google Scholar
Escardó, M. H. (2019) Introduction to Univalent Foundations of Mathematics with Agda.Google Scholar
Forsberg, F. N., Xu, C. & Ghani, N. (2020) Three equivalent ordinal notation systems in cubical Agda. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs. CPP 2020. Association for Computing Machinery, pp. 172–185.CrossRefGoogle Scholar
Huber, S. (2016) Canonicity for Cubical Type Theory. Preprint arXiv:1607.04156.Google Scholar
Huber, S. (2017) A Cubical Type Theory for Higher Inductive Types.Google Scholar
Kapulkin, C. & Lumsdaine, P. L. (2012) The Simplicial Model of Univalent Foundations (after Voevodsky). Preprint arXiv:1211.2851v4.Google Scholar
Licata, D. R. & Brunerie, G. (2015) A cubical approach to synthetic homotopy theory. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’15. ACM, pp. 92–103.CrossRefGoogle Scholar
Licata, D. R., Orton, I., Pitts, A. M. & Spitters, B. (2018) Internal universes in models of homotopy type theory. In 3rd International Conference on Formal Structures for Computation and Deduction, FSCD 2018, July 9–12, 2018, Oxford, UK, Kirchner, H. (ed). LIPIcs, vol. 108. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 22:1–22:17.Google Scholar
Licata, D. R. & Shulman, M. (2013) Calculating the fundamental group of the circle in homotopy type theory. In Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS’13, pp. 223–232.CrossRefGoogle Scholar
Lumsdaine, P. L. & Shulman, M. (2017) Semantics of Higher Inductive Types. Preprint arXiv:1705.07088.Google Scholar
Martin-Löf, P. (1975) An intiutionistic theory of types: Predicative part. In Logic Colloquium’73, Rose, H. E. & Shepherdson, J. (eds). Amsterdam: North–Holland, pp. 73–118.Google Scholar
McBride, C. (2009) Let’s see how things unfold: Reconciling the infinite with the intensional. In Proceedings of the 3rd International Conference on Algebra and Coalgebra in Computer Science. CALCO’09. Springer-Verlag, pp. 113–126.CrossRefGoogle Scholar
Mörtberg, A. & Pujet, L. (2020) Cubical synthetic homotopy theory. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs. CPP 2020. Association for Computing Machinery, pp. 158–171.CrossRefGoogle Scholar
Orton, I. & Pitts, A. M. (2016) Axioms for modelling cubical type theory in a topos. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). LIPIcs 62, pp. 24:1–24:19.Google Scholar
Riehl, E. (2019) The equivariant uniform Kan fibration model of cubical homotopy type theory. Talk given at The International Conference on Homotopy Type Theory (HoTT 2019) at Carnegie Mellon University.Google Scholar
Riehl, E. & Shulman, M. (2017) A type theory for synthetic ¥-categories. Higher Struct. 1(1), 147–224.Google Scholar
Sattler, C. (2018) Do cubical models of type theory also model homotopy types? Talk given at Types, Homotopy Type Theory, and Verification at the Hausdorff Center for Mathematics in Bonn.Google Scholar
Sojakova, K. (2016) The equivalence of the torus and the product of two circles in homotopy type theory. ACM Trans. Comput. Logic 17(4), 29:1–29:19.CrossRefGoogle Scholar
Sterling, J., Angiuli, C. & Gratzer, D. (2019) Cubical syntax for reflection-free extensional equality. In 4th International Conference on Formal Structures for Computation and Deduction, FSCD 2019. Leibniz International Proceedings in Informatics, LIPIcs, Geuvers, H. (ed). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.Google Scholar
Tabareau, N., Tanter, E. & Sozeau, M. (2018) Equivalences for free: Univalent parametricity for effective transport. Proc. ACM Program. Lang. 2(ICFP), 92:1–92:29.CrossRefGoogle Scholar
Tabareau, N., Tanter, É. & Sozeau, M. (2020) The Marriage of Univalence and Parametricity. Preprint arXiv:1909.05027 [cs.PL].CrossRefGoogle Scholar
Team, T. C. D. (2019) The Coq Proof Assistant, version 8.9.0.Google Scholar
The RedPRL Development Team. (2018) The redtt Proof Assistant. Google Scholar
Univalent Foundations Program, T. (2013) Homotopy Type Theory: Univalent Foundations of Mathematics.Google Scholar
Veltri, N. & Vezzosi, A. (2020) Formalizing π-calculus in guarded cubical Agda. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs. CPP 2020. Association for Computing Machinery, pp. 270–283.CrossRefGoogle Scholar
Vezzosi, A. (2017) Streams for Cubical Type Theory. http://saizan.github.io/streams-ctt.pdf.Google Scholar
Vezzosi, A., Mörtberg, A. & Abel, A. (2019) Cubical Agda: A dependently typed programming language with univalence and higher inductive types. Proc. ACM Program. Lang. 3(ICFP), 87:1–87:29.CrossRefGoogle Scholar
Voevodsky, V. (2013) A Simple Type System with Two Identity Types. https://www.math.ias.edu/vladimir/sites/math.ias.edu.vladimir/files/HTS.pdf.Google Scholar
Voevodsky, V. (2015) An experimental library of formalized mathematics based on the univalent foundations. Math. Struct. Comput. Sci. 25, 1278–1294.CrossRefGoogle Scholar
Wood, J. (2019) Vectors and Matrices in Agda. Blog post at https://personal.cis.strath.ac.uk/james.wood.100/blog/html/VecMat.html.Google Scholar
Supplementary material: File

Vezzosi supplementary material

Vezzosi supplementary material 1

Download Vezzosi supplementary material(File)
File 3.2 MB
Supplementary material: PDF

Vezzosi supplementary material

Vezzosi supplementary material 2

Download Vezzosi supplementary material(PDF)
PDF 146.3 KB
Submit a response

Discussions

No Discussions have been published for this article.