{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T15:18:02Z","timestamp":1790435882433,"version":"4.1.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,7,26]]},"abstract":"<jats:p>We describe a type system with mixed linear and non-linear recursive types called LNL-FPC (the linear\/non-linear fixpoint calculus). The type system supports linear typing which enhances the safety properties of programs, but also supports non-linear typing as well which makes the type system more convenient for programming. Just like in FPC, we show that LNL-FPC supports type-level recursion which in turn induces term-level recursion. We also provide sound and computationally adequate categorical models for LNL-FPC which describe the categorical structure of the substructural operations of Intuitionistic Linear Logic at all non-linear types, including the recursive ones. In order to do so, we describe a new technique for solving recursive domain equations within the category CPO by constructing the solutions over pre-embeddings. The type system also enjoys implicit weakening and contraction rules which we are able to model by identifying the canonical comonoid structure of all non-linear types. We also show that the requirements of our abstract model are reasonable by constructing a large class of concrete models that have found applications not only in classical functional programming, but also in emerging programming paradigms that incorporate linear types, such as quantum programming and circuit description programming languages.<\/jats:p>","DOI":"10.1145\/3341715","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T20:55:51Z","timestamp":1564433751000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Mixed linear and non-linear recursive types"],"prefix":"10.1145","volume":"3","author":[{"given":"Bert","family":"Lindenhovius","sequence":"first","affiliation":[{"name":"Tulane University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mislove","sequence":"additional","affiliation":[{"name":"Tulane University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vladimir","family":"Zamdzhiev","sequence":"additional","affiliation":[{"name":"University of Lorraine, France \/ CNRS, France \/ Inria, France \/ LORIA, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,26]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings 11th Annual IEEE Symposium on Logic in Computer Science. 242\u2013252","author":"Abadi M.","unstructured":"M. Abadi and M. P. Fiore . 1996. Syntactic Considerations on Recursive Types . In Proceedings 11th Annual IEEE Symposium on Logic in Computer Science. 242\u2013252 . M. Abadi and M. P. Fiore. 1996. Syntactic Considerations on Recursive Types. In Proceedings 11th Annual IEEE Symposium on Logic in Computer Science. 242\u2013252."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90181-R"},{"key":"e_1_2_2_3_1","unstructured":"S. Abramsky and A. Jung. 1994. Handbook of Logic in Computer Science (Vol. 3). Oxford University Press Oxford UK Chapter Domain Theory 1\u2013168. http:\/\/dl.acm.org\/citation.cfm?id=218742.218744   S. Abramsky and A. Jung. 1994. Handbook of Logic in Computer Science (Vol. 3). Oxford University Press Oxford UK Chapter Domain Theory 1\u2013168. http:\/\/dl.acm.org\/citation.cfm?id=218742.218744"},{"key":"e_1_2_2_4_1","first-page":"589","article-title":"Free algebras and automata realizations in the language of categories","volume":"15","author":"Ad\u00e1mek Ji\u0159\u00ed","year":"1974","unstructured":"Ji\u0159\u00ed Ad\u00e1mek . 1974 . Free algebras and automata realizations in the language of categories . Commentationes Mathematicae Universitatis Carolinae 15 , 4 (1974), 589 \u2013 602 . Ji\u0159\u00ed Ad\u00e1mek. 1974. Free algebras and automata realizations in the language of categories. Commentationes Mathematicae Universitatis Carolinae 15, 4 (1974), 589\u2013602.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2017.11.003"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/647844.736565"},{"key":"e_1_2_2_8_1","volume-title":"Monads and the Lambda Calculus. In LICS","author":"Benton P. N.","year":"1996","unstructured":"P. N. Benton and P. Wadler . 1996. Linear Logic , Monads and the Lambda Calculus. In LICS 1996 . P. N. Benton and P. Wadler. 1996. Linear Logic, Monads and the Lambda Calculus. In LICS 1996."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158093"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80874-0"},{"key":"e_1_2_2_11_1","volume-title":"Handbook of Categorical Algebra 2: Categories and Structures","author":"Borceux F.","unstructured":"F. Borceux . 1994. Handbook of Categorical Algebra 2: Categories and Structures . Cambridge University Press . F. Borceux. 1994. Handbook of Categorical Algebra 2: Categories and Structures. Cambridge University Press."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00233-2"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129514000218"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BFb0063098","article-title":"On closed categories of functors II","volume":"1972","author":"Day B.","year":"1974","unstructured":"B. Day . 1974 . On closed categories of functors II . In Category Seminar: Proceedings Sydney Category Theory Seminar 1972\/1973 . 20 \u2013 54 . B. Day. 1974. On closed categories of functors II. In Category Seminar: Proceedings Sydney Category Theory Seminar 1972\/1973. 20\u201354.","journal-title":"Category Seminar: Proceedings Sydney Category Theory Seminar"},{"key":"e_1_2_2_16_1","volume-title":"An Axiomatization of Computationally Adequate Domain Theoretic Models of FPC","author":"Fiore Marcelo","unstructured":"Marcelo Fiore and Gordon Plotkin . 1994. An Axiomatization of Computationally Adequate Domain Theoretic Models of FPC . In LICS. IEEE Computer Society , 92\u2013102. Marcelo Fiore and Gordon Plotkin. 1994. An Axiomatization of Computationally Adequate Domain Theoretic Models of FPC. In LICS. IEEE Computer Society, 92\u2013102."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90045-4"},{"key":"e_1_2_2_19_1","volume-title":"Algebraic specification of data types: A synthetic approach. Mathematical Systems Theory","author":"Lehmann Daniel J","year":"1981","unstructured":"Daniel J Lehmann and Michael B Smyth . 1981. Algebraic specification of data types: A synthetic approach. Mathematical Systems Theory ( 1981 ). Daniel J Lehmann and Michael B Smyth. 1981. Algebraic specification of data types: A synthetic approach. Mathematical Systems Theory (1981)."},{"key":"e_1_2_2_20_1","volume-title":"A Functional\/Imperative Synthesis","author":"Levy Paul Blain","unstructured":"Paul Blain Levy . 2004. Call-By-Push-Value : A Functional\/Imperative Synthesis . Springer . Paul Blain Levy. 2004. Call-By-Push-Value: A Functional\/Imperative Synthesis. Springer."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209196"},{"key":"e_1_2_2_22_1","volume-title":"Presheaf Models of Quantum Computation: An Outline","author":"Malherbe Octavio","unstructured":"Octavio Malherbe , Philip Scott , and Peter Selinger . 2013. Presheaf Models of Quantum Computation: An Outline . Springer Berlin Heidelberg , Berlin, Heidelberg , 178\u2013194. Octavio Malherbe, Philip Scott, and Peter Selinger. 2013. Presheaf Models of Quantum Computation: An Outline. Springer Berlin Heidelberg, Berlin, Heidelberg, 178\u2013194."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.03.006"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951925"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535879"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0052"},{"key":"e_1_2_2_27_1","unstructured":"G. D. Plotkin. 1985. Lectures on predomains and partial functions. Notes for a course given at CSLI Stanford University.  G. D. Plotkin. 1985. Lectures on predomains and partial functions. Notes for a course given at CSLI Stanford University."},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"M. Rennela and S. Staton. 2017. Classical control and quantum circuits in enriched category theory. To appear in MFPS XXXIII.  M. Rennela and S. Staton. 2017. Classical control and quantum circuits in enriched category theory. To appear in MFPS XXXIII.","DOI":"10.1016\/j.entcs.2018.03.027"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings 14th International Conference on Quantum Physics and Logic, QPL 2017","volume":"266","author":"Rios Francisco","year":"2017","unstructured":"Francisco Rios and Peter Selinger . 2017 . A categorical model for a quantum circuit description language . In Proceedings 14th International Conference on Quantum Physics and Logic, QPL 2017 , Nijmegen, The Netherlands , 3-7 July 2017. (EPTCS), Bob Coecke and Aleks Kissinger (Eds.), Vol. 266 . 164\u2013178. Francisco Rios and Peter Selinger. 2017. A categorical model for a quantum circuit description language. In Proceedings 14th International Conference on Quantum Physics and Logic, QPL 2017, Nijmegen, The Netherlands, 3-7 July 2017. (EPTCS), Bob Coecke and Aleks Kissinger (Eds.), Vol. 266. 164\u2013178."},{"key":"e_1_2_2_30_1","unstructured":"Giuseppe Rosolini and Alex Simpson. 2004. Using synthetic domain theory to prove operational properties of a polymorphic programming language based on strictness. Manuscript.  Giuseppe Rosolini and Alex Simpson. 2004. Using synthetic domain theory to prove operational properties of a polymorphic programming language based on strictness. Manuscript."},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"M.B. Smyth and G.D. Plotkin. 1982. The Category-theoretic Solution of Recursive Domain Equations. Siam J. Comput. (1982).  M.B. Smyth and G.D. Plotkin. 1982. The Category-theoretic Solution of Recursive Domain Equations. Siam J. Comput. (1982).","DOI":"10.1137\/0211062"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926436"},{"key":"e_1_2_2_33_1","unstructured":"Philip Wadler. 1990. Linear Types Can Change the World!. In PROGRAMMING CONCEPTS AND METHODS. North.  Philip Wadler. 1990. Linear Types Can Change the World!. In PROGRAMMING CONCEPTS AND METHODS. North."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341715","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:24Z","timestamp":1750207404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":30,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2019,7,26]]}},"alternative-id":["10.1145\/3341715"],"URL":"https:\/\/doi.org\/10.1145\/3341715","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"2019-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}