This paper presents two extensions of the second order polymorphic lambda calculus, system , with monotone (co)inductive types supporting (co)iteration, primitive (co)recursion and inversion principles as primitives. One extension is inspired by the usual categorical approach to programming by means of initial algebras and final coalgebras; whereas the other models dialgebras, and can be seen as an extension of Hagino’s categorical lambda calculus within the framework of parametric polymorphism. The systems are presented in Curry-style, and are proven to be terminating and type-preserving. Moreover their expressiveness is shown by means of several programming examples, going from usual data types to lazy codata types such as streams or infinite trees.
@article{ITA_2009__43_4_703_0,
author = {Miranda-Perea, Favio Ezequiel},
title = {Two extensions of system ${\mathsf {F}}$ with (co)iteration and primitive (co)recursion principles},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {43},
year = {2009},
pages = {703-766},
doi = {10.1051/ita/2009015},
mrnumber = {2589990},
zbl = {pre05650345},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2009__43_4_703_0}
}
Miranda-Perea, Favio Ezequiel. Two extensions of system ${\mathsf {F}}$ with (co)iteration and primitive (co)recursion principles. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 703-766. doi : 10.1051/ita/2009015. http://gdmltest.u-ga.fr/item/ITA_2009__43_4_703_0/
[1] , and , Iteration and coiteration schemes for higher-order and nested datatypes. Theoret. Comput. Sci. 333 (2005) 3-66. | MR 2122711 | Zbl 1070.68093
[2] and , Automatic synthesis of typed -programs on term algebras. Theoret. Comput. Sci. 39 (1985) 135-154. | MR 821198 | Zbl 0597.68017
[3] , Categories for Types. Cambridge Mathematical Textbooks. Cambridge University Press (1993). | MR 1275826 | Zbl 0837.68077
[4] , Recursion patterns as hylomorphisms. Technical Report DI-PURe-03.11.01, Department of Informatics, University of Minho (2003).
[5] and , Introduction to Lattices and Order, 2nd edn. Cambridge University Press (2002). | MR 1902334 | Zbl 1002.06001
[6] and , Comparing Hagino's categorical programming language and typed lambda-calculi. Theoret. Comput. Sci. 111 (1991) 145-189. | MR 1216428 | Zbl 0787.68014
[7] , Inductive and coinductive types with iteration and recursion. In Proceedings of the 1992 workshop on types for proofs and programs, Båstad, Sweden. Edited by B. Nordström, K. Petterson, G. Plotkin (1992) 183-207. Available via http://www.cs.kun.nl/~herman/BRABasInf_RecTyp.ps.gz.
[8] and , The under-appreciated unfold. In Proceedings 3rd ACM SIGPLAN international conference on functional programming, Baltimore, Maryland (1998) 273-279.
[9] , Une extension de l'interpretation de Gödel à l'analyse, et son application à l'élimination des coupures dans l'analyse et la théorie des types. Second Scandinavian Logic Symposium. Edited by J.E. Fenstad. North-Holland (1971) 63-92. | MR 409133 | Zbl 0221.02013
[10] , Interprétation fonctionnelle et élimination des coupures dans l'arithmetique d'ordre supérieur. Thèse de Doctorat d'État, Université de Paris VII (1972).
[11] , and , Proofs and Types. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press (1989). | MR 1003608 | Zbl 0671.68002
[12] , Programming with inductive and co-inductive types. Technical Report CMU-CS-92-109, Carnegie-Mellon University (1992)
[13] , A typed lambda calculus with categorical type constructors. In Category Theory and Computer Science. Edited by D.H. Pitt, A. Poigné and D.E. Rydeheard. Lect. Notes Comput. Sci. 283 (1987). | MR 925228 | Zbl 0643.03010
[14] , A Categorical programming language. Ph.D. Thesis CST-47-87 (also published as ECS-LFCS-87-38). Department of Computer Science, University of Edinburgh (1987).
[15] and , A tutorial on (co)algebras and (co)induction. EATCS Bull. 62 (1997) 222-259. | Zbl 0880.68070
[16] and , Recursion schemes for dynamic programming. In Proc. 8th Int. Conf. on Mathematics of Program Construction, MPC 06. Edited by T. Uustalu. Lect. Notes Comput. Sci. 4014 (2006) 235-252. | Zbl pre05539335
[17] , Lambda-calculus, types and models. Ellis Horwood Series in Computers and their Applications. Ellis Horwood, Masson (1993). | MR 1252176 | Zbl 0779.03005
[18] , Categories for the Working Mathematician, 2nd. edn., Vol. 5. Graduate Texts in Mathematics. Springer Verlag (1998). | MR 1712872 | Zbl 0906.18001
[19] , Extensions of system F by iteration and primitive recursion on monotone inductive types. Dissertation Universität München (1999). Available via http://www.tcs.informatik.uni-muenchen.de/~matthes/dissertation/ matthesdiss.ps.gz | Zbl 0943.68086
[20] , Monotone (co)inductive types and positive fixed-point types. RAIRO-Theor. Inf. Appl. 33 (1999) 309-328. | Numdam | MR 1748658 | Zbl 0940.03018
[21] , Monotone fixed-point types and strong normalization. In Computer Science Logic. Edited by G. Gottlob, E. Grandjean, K. Seyr. 12th International Workshop, Brno, Czech Republic, August 24-28, 1998. Lect. Notes Comput. Sci. 1584 (1999) 298-312. | MR 1717499 | Zbl 0933.03027
[22] , Monotone inductive and coinductive constructors of rank 2. In Computer Science Logic 2001. Lect. Notes Comput. Sci. 2142 (2001) 600-614. | MR 1908800 | Zbl 0999.68037
[23] , Non-strictly positive fixed-points for classical natural deduction. Ann. Pure Appl. Logic 133 (2005) 205-230. | MR 2126159 | Zbl 1066.03057
[24] , and , Functional programming with bananas, lenses, envelopes and barbed wire. In FPCA 91. Edited by J. Hughes. Lect. Notes Comput. Sci. 523 (1991) 124-144. | MR 1148099
[25] , Recursive types and type constraints in second-order lambda calculus. In Proceedings of the 2nd Annual Symposium on Logic in Computer Science, Ithaca, N.Y. IEEE Computer Society Press, Washington D.C. (1987) 30-36.
[26] , Inductive types and type constraints in the second-order lambda calculus. Ann. Pure Appl. Logic 51 (1991) 159-172. | MR 1100500 | Zbl 0719.03008
[27] , On extensions of AF2 with monotone and clausular (co)inductive definitions. Ph.D. Thesis, Ludwig-Maximilians-Universität München, Germany (2004).
[28] , Some remarks on type systems for course-of-value recursion. In Proceedings of the third workshop on Logical and Semantic Frameworks with Applications (LSFA 2008). Electronic Notes in Theoretical Computer Science 247 (2009).
[29] , Recursive programming with proofs. Theoret. Comput. Sci. 94 (1992) 335-356. | MR 1157863 | Zbl 0759.68014
[30] and , From algebras and coalgebras to dialgebras. In Coalgebraic Methods in Computer Science (CMCS'2001). Electronic Notes in Theoretical Computer Science 44 (2001).
[31] , Towards a theory of type structure. In Proc. Colloque sur la Programmation. Edited by B. Robinet. Lect. Notes Comput. Sci. 19 (1974). | MR 458988 | Zbl 0309.68016
[32] , Automata and coinduction (an exercise in coalgebra). In Proceedings of CONCUR '98. Edited by D. Sangiorgi and R. de Simone. Lect. Notes Comput. Sci. 1466 (1998) 194-218. | MR 1678749 | Zbl 0940.68085
[33] and , Type fixpoints: iteration vs. recursion. In Proc. International Conference on Functional Programming. ACM Press (1999), pp 102-113.
[34] , A realizability interpretation of the theory of species. In Logic Colloquium Boston 1971/72. Edited by R. Parikh. Lect. Notes Math. 453 (1975) 240-251. | MR 384503 | Zbl 0328.02014
[35] , Total functional programming. J. Universal Comput. Sci. 10 (2004) 751-768. | MR 2164648
[36] and , Primitive (co)recursion and course-of-value (co)iteration, categorically. Informatica 10 (1999) 5-26. | MR 1688964 | Zbl 0935.68011
[37] and , Least and greatest fixed-points in intuitionistic natural deduction. Theoret. Comput. Sci. 272 (2002) 315-339. | MR 1870370 | Zbl 0984.68136
[38] , Categorical programming with inductive and coinductive types. Diss. Math. Univ. Tartuensis 23, Univ. Tartu (2000). | MR 1789340 | Zbl 0966.68516
[39] , Theorems for free. In Proc. 4th international conference on functional programming languages and computer architecture. Imperial College, London (1989), pp 347-359.
[40] , A note on categorical datatypes. In Category Theory and Computer Science. Edited by D. Pitts et al. Lect. Notes Comput. Sci. 389 (1989). | MR 1031559