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.
Keywords: coiteration, corecursion, iteration, primitive recursion, system F, monotone inductive type, monotone coinductive type, monotonicity witness, saturated sets, algebras, coalgebras, dialgebras
@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}, pages = {703--766}, publisher = {EDP-Sciences}, volume = {43}, number = {4}, year = {2009}, doi = {10.1051/ita/2009015}, mrnumber = {2589990}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita/2009015/} }
TY - JOUR AU - Miranda-Perea, Favio Ezequiel TI - Two extensions of system ${\mathsf {F}}$ with (co)iteration and primitive (co)recursion principles JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2009 SP - 703 EP - 766 VL - 43 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2009015/ DO - 10.1051/ita/2009015 LA - en ID - ITA_2009__43_4_703_0 ER -
%0 Journal Article %A Miranda-Perea, Favio Ezequiel %T Two extensions of system ${\mathsf {F}}$ with (co)iteration and primitive (co)recursion principles %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 703-766 %V 43 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2009015/ %R 10.1051/ita/2009015 %G en %F 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, Volume 43 (2009) no. 4, pp. 703-766. doi : 10.1051/ita/2009015. http://www.numdam.org/articles/10.1051/ita/2009015/
[1] Iteration and coiteration schemes for higher-order and nested datatypes. Theoret. Comput. Sci. 333 (2005) 3-66. | MR | Zbl
, and ,[2] Automatic synthesis of typed -programs on term algebras. Theoret. Comput. Sci. 39 (1985) 135-154. | MR | Zbl
and ,[3] Categories for Types. Cambridge Mathematical Textbooks. Cambridge University Press (1993). | MR | Zbl
,[4] Recursion patterns as hylomorphisms. Technical Report DI-PURe-03.11.01, Department of Informatics, University of Minho (2003).
,[5] Introduction to Lattices and Order, 2nd edn. Cambridge University Press (2002). | MR | Zbl
and ,[6] Comparing Hagino's categorical programming language and typed lambda-calculi. Theoret. Comput. Sci. 111 (1991) 145-189. | MR | Zbl
and ,[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] The under-appreciated unfold. In Proceedings 3rd ACM SIGPLAN international conference on functional programming, Baltimore, Maryland (1998) 273-279.
and ,[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 | Zbl
,[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] Proofs and Types. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press (1989). | MR | Zbl
, and ,[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 | Zbl
,[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] A tutorial on (co)algebras and (co)induction. EATCS Bull. 62 (1997) 222-259. | Zbl
and ,[16] 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.
and ,[17] Lambda-calculus, types and models. Ellis Horwood Series in Computers and their Applications. Ellis Horwood, Masson (1993). | MR | Zbl
,[18] Categories for the Working Mathematician, 2nd. edn., Vol. 5. Graduate Texts in Mathematics. Springer Verlag (1998). | MR | Zbl
,[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
,[20] Monotone (co)inductive types and positive fixed-point types. RAIRO-Theor. Inf. Appl. 33 (1999) 309-328. | Numdam | MR | Zbl
,[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 | Zbl
,[22] Monotone inductive and coinductive constructors of rank 2. In Computer Science Logic 2001. Lect. Notes Comput. Sci. 2142 (2001) 600-614. | MR | Zbl
,[23] Non-strictly positive fixed-points for classical natural deduction. Ann. Pure Appl. Logic 133 (2005) 205-230. | MR | Zbl
,[24] 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
, and ,[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 | Zbl
,[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 | Zbl
,[30] From algebras and coalgebras to dialgebras. In Coalgebraic Methods in Computer Science (CMCS'2001). Electronic Notes in Theoretical Computer Science 44 (2001).
and ,[31] Towards a theory of type structure. In Proc. Colloque sur la Programmation. Edited by B. Robinet. Lect. Notes Comput. Sci. 19 (1974). | MR | Zbl
,[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 | Zbl
,[33] Type fixpoints: iteration vs. recursion. In Proc. International Conference on Functional Programming. ACM Press (1999), pp 102-113.
and ,[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 | Zbl
,[35] Total functional programming. J. Universal Comput. Sci. 10 (2004) 751-768. | MR
,[36] Primitive (co)recursion and course-of-value (co)iteration, categorically. Informatica 10 (1999) 5-26. | MR | Zbl
and ,[37] Least and greatest fixed-points in intuitionistic natural deduction. Theoret. Comput. Sci. 272 (2002) 315-339. | MR | Zbl
and ,[38] Categorical programming with inductive and coinductive types. Diss. Math. Univ. Tartuensis 23, Univ. Tartu (2000). | MR | Zbl
,[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
,Cited by Sources: