Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-30T18:34:08.307Z Has data issue: false hasContentIssue false
  • English
  • Français

The essence of ornaments

Part of: JFP Research Articles

Published online by Cambridge University Press:  06 February 2017

PIERRE-EVARISTE DAGAND
PIERRE-EVARISTE DAGAND*
Affiliation:
Sorbonne Universités, UPMC Univ Paris 06, CNRS, Inria, LIP6 UMR 7606, Paris, France (e-mail: [email protected])
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.

Functional programmers from all horizons strive to use, and sometimes abuse, their favorite type system in order to capture the invariants of their programs. A widely used tool in that trade consists in defining finely indexed datatypes. Operationally, these types classify the programmer's data, following the ML tradition. Logically, these types enforce the program invariants in a novel manner. This new programming pattern, by which one programs over inductive definitions to account for some invariants, lead to the development of a theory of ornaments (McBride, 2011 Ornamental Algebras, Algebraic Ornaments. Unpublished). However, ornaments originate as a dependently-typed object and may thus appear rather daunting to a functional programmer of the non-dependent kind. This article aims at presenting ornaments from first-principles and, in particular, to declutter their presentation from syntactic considerations. To do so, we shall give a sufficiently abstract model of indexed datatypes by means of many-sorted signatures. In this process, we formalize our intuition that an indexed datatype is the combination of a data-structure and a data-logic. Over this abstraction of datatypes, we shall recast the definition of ornaments, effectively giving a model of ornaments. Benefiting both from the operational and abstract nature of many-sorted signatures, ornaments should appear applicable and, one hopes, of interest beyond the type-theoretic circles, case in point being languages with generalized abstract datatypes or refinement types.

Type
Articles
Information
Journal of Functional Programming , Volume 27 , 2017 , e9
Copyright
Copyright © Cambridge University Press 2017 

References

Abbott, M. (2003) Categories of Containers. Ph.D. thesis, University of Leicester.Google Scholar
Abbott, M., Altenkirch, T., McBride, C. & Ghani, N. (2005) ∂ for data: Differentiating data structures. Fundam. Inform. 65 (1–2), 1–28.Google Scholar
Adelson-Velskii, G. & Landis, E. (1962) An algorithm for the organization of information. Dokl. Akad. Nauk USSR 146 (2), 263–266.Google Scholar
Atkey, R., Johann, P. & Ghani, N. (2012) Refining inductive types. Log. Methods Comput. Sci. 8 (2), 1–30.Google Scholar
Brady, E. (2013) Idris, a general-purpose dependently typed programming language: Design and implementation. J. Funct. Program. 23 (5), 552–593.CrossRefGoogle Scholar
Cheney, J. & Hinze, R. (2003) First-Class Phantom Types. Technical Report, Cornell University.Google Scholar
Chlipala, A. (2013) Certified Programming with Dependent Types. MIT Press.Google Scholar
Constable, R. L. (1986) Implementing Mathematics with the Nuprl Proof Development System. Prentice Hall.Google Scholar
Coq development team. (2015) The Coq proof assistant reference manual.Google Scholar
Dagand, P.-E. & McBride, C. (2012) Transporting functions across ornaments. In Proceedings of International Conference on Functional Programming, Copenhagen, Denmark: ACM, pp. 103–114.Google Scholar
Dagand, P.-E. & McBride, C. (2013) A categorical treatment of ornaments. Logics Comput. Sci. 530–539.Google Scholar
Dybjer, P. (1994) Inductive families. Form. Asp. Comput. 6 (4), 440–465.Google Scholar
Dybjer, P. (1997) Representing inductively defined sets by wellorderings in Martin-Löf's type theory. Theor. Comput. Sci. 176 (1–2), 329–335.Google Scholar
Freeman, T. & Pfenning, F. (1991) Refinement types for ML. In Programming Language Design and Implementation, Toronto, Ontario, Canada: ACM, pp. 268–277.Google Scholar
Fumex, C. (2012) Induction and Coinduction Schemes in Category Theory. PhD Thesis, University of Strathclyde.Google Scholar
Gambino, N. & Hyland, M. (2004) Wellfounded trees and dependent polynomial functors. In Types for Proofs and Programs, vol. 3085, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 210–225.Google Scholar
Gambino, N. & Kock, J. (2013) Polynomial functors and polynomial monads. Math. Proc. Camb. Phil. Soc. 154 (1), 153–192.CrossRefGoogle Scholar
Goguen, H. & Luo, Z. (1993) Inductive data types: Well-ordering types revisited. In Workshop on Logical Environments, Cambridge University Press, pp. 198–218.Google Scholar
Goguen, J. A., Thatcher, J. W., Wagner, E. G. & Wright, J. B. (1975 May) Abstract data-types as initial algebras and correctness of data representations. In Proceedings of the Conference on Computer Graphics, Pattern Recognition and Data Structure.Google Scholar
Guibas, L. J. & Sedgewick, R. (1978) A dichromatic framework for balanced trees. In Foundations of Computer Science, pp. 8–21.Google Scholar
Hamana, M. & Fiore, M. (2011) A foundation for GADTs and inductive families: Dependent polynomial functor approach. In Workshop on Generic Programming, pp. 59–70.Google Scholar
Hinze, R. (1998) Numerical Representations as Higher-Order Nested Datatypes. Technical Report, Institut für Informatik III, Universität Bonn.Google Scholar
Huet, G. (1997) The zipper. J. Funct. Program. 7 (05), 549–554.CrossRefGoogle Scholar
Knuth, D. E. (1981) The Art of Computer Programming, Volume II: Seminumerical Algorithms. Addison-Wesley.Google Scholar
Ko, H.-S. (2014) Analysis and Synthesis of Inductive Families. PhD Thesis, University of Oxford.Google Scholar
Ko, H.-S. & Gibbons, J. (2011) Modularising inductive families. In Workshop on Generic Programming, pp. 13–24.Google Scholar
Ko, H.-S. & Gibbons, J. (2013) Relational algebraic ornaments. In Workshop on Dependently-Typed Programming, pp. 37–48.Google Scholar
Martin-Löf, P. (1984) Intuitionistic Type Theory. Bibliopolis Napoli.Google Scholar
McBride, C. (2011) Ornamental Algebras, Algebraic Ornaments. Unpublished.Google Scholar
Morris, P. (2007) Constructing Universes for Generic Programming. PhD Thesis, University of Nottingham.Google Scholar
Morris, P. & Altenkirch, T. (2009) Indexed containers. Logics Comput. Sci. pp. 277–285.Google Scholar
Morris, P., Altenkirch, T. & Ghani, N. (2009) A universe of strictly positive families. Int. J. Found. Comput. Sci. 20 (1), 83–107.Google Scholar
Norell, U. (2007) Towards a Practical Programming Language Based on Dependent Type Theory. PhD Thesis, Chalmers University of Technology.Google Scholar
Okasaki, C. (1998) Purely Functional Data Structures. Cambridge University Press.Google Scholar
Petersson, K. & Synek, D. (1989) A set constructor for inductive sets in Martin-Löf's type theory. In Category Theory and Computer Science, pp. 128–140.Google Scholar
Pottier, F. & Régis-Gianas, Y. (2006) Stratified type inference for generalized algebraic data types. In Principles of Programming Languages, Charleston, South Carolina, USA: ACM, pp. 232–244.Google Scholar
Schrijvers, T., Peyton Jones, S., Sulzmann, M. & Vytiniotis, D. (2009) Complete and decidable type inference for GADTs. In Proceedings of International Conference on Functional Programming, Edinburgh, Scotland: ACM, pp. 341–352.CrossRefGoogle Scholar
Seely, R. A. G. (1983) Locally cartesian closed categories and type theory. Math. Proc. Camb. Phil. Soc. 95 (1), 33–48.Google Scholar
Sheard, T. & Linger, N. (2007) Programming in Omega. In Central European Functional Programming School. vol. 5161, Lecture Notes in Computer Science, Springer, pp. 158–227.Google Scholar
Smyth, M. B. & Plotkin, G. D. (1982) The category-theoretic solution of recursive domain equations. In Foundations of Computer Science 11 (4), pp. 761–783.Google Scholar
Swamy, N., Chen, J., Fournet, C., Strub, P.-Y., Bhargavan, K. & Yang, J. (2011) Secure distributed programming with value-dependent types. In Proceedings of International Conference on Functional Programming, ACM, pp. 266–278.CrossRefGoogle Scholar
Williams, T., Dagand, P.-É. & Rémy, D. (2014) Ornaments in practice. In Workshop on Generic Programming, Gothenburg, Sweden: ACM, pp. 15–24.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.