×

A faithful and quantitative notion of distant reduction for the lambda-calculus with generalized applications. (English) Zbl 07906372

Summary: We introduce a call-by-name \(\lambda\)-calculus \(\lambda J_n\) with generalized applications which is equipped with distant reduction. This allows to unblock \(\beta\)-redexes without resorting to the standard permutative conversions of generalized applications used in the original \(\Lambda J\)-calculus with generalized applications of Joachimski and Matthes. We show strong normalization of simply-typed terms, and we then fully characterize strong normalization by means of a quantitative (i.e. non-idempotent intersection) typing system. This characterization uses a non-trivial inductive definition of strong normalization – related to others in the literature –, which is based on a weak-head normalizing strategy. We also show that our calculus \(\lambda J_n\) relates to explicit substitution calculi by means of a faithful translation, in the sense that it preserves strong normalization. Moreover, our calculus \(\lambda J_n\) and the original \(\Lambda J\)-calculus determine equivalent notions of strong normalization. As a consequence, \(\lambda J\) inherits a faithful translation into explicit substitutions, and its strong normalization can also be characterized by the quantitative typing system designed for \(\lambda J_n\), despite the fact that quantitative subject reduction fails for permutative conversions.

MSC:

03B70 Logic in computer science
68-XX Computer science

References:

[1] Andreas Abel. On model-theoretic strong normalization for truth-table natural deduction. In Ugo de’Liguoro, Stefano Berardi, and Thorsten Altenkirch, editors, 26th International Conference on Types for Proofs and Programs (TYPES 2020), volume 188 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl -Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.TYPES.2020.1. · doi:10.4230/LIPIcs.TYPES.2020.1
[2] Beniamino Accattoli. An abstract factorization theorem for explicit substitutions. In 23rd International Conference on Rewriting Techniques and Applications (RTA), volume 15 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6-21, Dagstuhl, Germany, 2012. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.RTA.2012.6. · Zbl 1437.68038 · doi:10.4230/LIPIcs.RTA.2012.6
[3] Beniamino Accattoli, Stéphane Graham-Lengrand, and Delia Kesner. Tight typings and split bounds, fully developed. Journal of Functional Programming, 30(ICFP), 2020. doi:10.1017/ s095679682000012x. 10:48 J. Espírito Santo, D. Kesner, and L. Peyrot Vol. 20:3 · Zbl 1482.68077 · doi:10.1017/s095679682000012x
[4] Beniamino Accattoli and Delia Kesner. The structural λ-calculus. In 19th EACSL Annual Conference on Computer Science Logic (CSL), Brno, Czech Republic, 2010, volume 6247 of Lecture Notes in Computer Science, pages 381-395. Springer, 2010. doi:10.1007/978-3-642-15205-4_30. · Zbl 1287.03034 · doi:10.1007/978-3-642-15205-4_30
[5] Beniamino Accattoli and Delia Kesner. Preservation of strong normalisation modulo per-mutations for the structural lambda-calculus. Log. Methods Comput. Sci., 8(1), 2012. doi: 10.2168/LMCS-8(1:28)2012. · Zbl 1237.03011 · doi:10.2168/LMCS-8(1:28)2012
[6] Henk Barendregt. The Lambda Calculus -Its Syntax and Semantics. Elsevier, 1984. doi:10. 1016/c2009-0-14341-6. · Zbl 0551.03007 · doi:10.1016/c2009-0-14341-6
[7] Freiric Barral. Decidability for Non-Standard Conversions in Typed Lambda-Calculi. PhD thesis, Université de Toulouse III -Paul Sabatier and Ludwig-Maximilian Universität München, 2008. · Zbl 1331.03002
[8] Daniel de Carvalho. Sémantiques de la logique linéaire et temps de calcul. PhD thesis, Université de la Méditerranée Aix-Marseille II, 2007.
[9] Roel. C. de Vrijer. Exactly estimating functionals and strong normalization. Indagationes Mathematicae (Proceedings), 90(4):479-493, 1987. · Zbl 0642.03008
[10] José Espírito Santo, Maria João Frade, and Luís Pinto. Permutability in proof terms for intuitionistic sequent calculus with cuts. In 22nd International Conference on Types for Proofs and Programs (TYPES), Novi Sad, Serbia, 2016, volume 97 of LIPIcs, pages 10:1-10:27. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.TYPES.2016.10. · doi:10.4230/LIPIcs.TYPES.2016.10
[11] José Espírito Santo, Maria João Frade, and Luís Pinto. Variations and interpretations of naturality in call-by-name lambda-calculi with generalized applications. Journal of Logical and Algebraic Methods in Programming, 131:100830, 2023. · Zbl 07649237
[12] José Espírito Santo, Jelena Ivetić, and Silvia Likavec. Characterising strongly normalising intu-itionistic terms. Fundamenta Informaticae, 121(1-4):83-120, 2012. doi:10.3233/FI-2012-772. · Zbl 1277.03003 · doi:10.3233/FI-2012-772
[13] José Espírito Santo, Delia Kesner, and Loïc Peyrot. A faithful and quantitative notion of distant reduction for generalized applications. In 25th International Conference on Foundations of Software Science and Computation Structures (FOSSACS), Munich, Germany, 2022, volume 13242 of Lecture Notes in Computer Science, pages 285-304. Springer, 2022. doi:10.1007/ 978-3-030-99253-8_15. · Zbl 07793034 · doi:10.1007/978-3-030-99253-8_15
[14] José Espírito Santo and Luís Pinto. Permutative conversions in intuitionistic multiary sequent calculi with cuts. In 6th International Conference on Typed Lambda Calculi and Applications (TLCA), Valencia, Spain, 2003, volume 2701 of Lecture Notes in Computer Science, pages 286-300. Springer, 2003. doi:10.1007/3-540-44904-3_20. · Zbl 1041.03040 · doi:10.1007/3-540-44904-3_20
[15] José Espírito Santo and Luís Pinto. A calculus of multiary sequent terms. ACM Transactions on Computational Logic, 12(3):22:1-22:41, 2011. doi:10.1145/1929954.1929959. · Zbl 1352.03063 · doi:10.1145/1929954.1929959
[16] José Espírito Santo. Delayed substitutions. In 18th International Conference on Term Rewriting and Applications (RTA), Paris, France, 2007, volume 4533 of Lecture Notes in Computer Science, pages 169-183. Springer, 2007. doi:10.1007/978-3-540-73449-9_14. · Zbl 1203.68031 · doi:10.1007/978-3-540-73449-9_14
[17] José Espírito Santo. The λ-calculus and the unity of structural proof theory. Theory of Computing Systems, 45(4):963-994, 2009. doi:10.1007/s00224-009-9183-9. · Zbl 1187.68126 · doi:10.1007/s00224-009-9183-9
[18] José Espírito Santo. The polarized λ-calculus. In 11th Workshop on Logical and Semantic Frameworks with Applications (LSFA), Porto, Portugal, 2016, volume 332 of Electronic Notes in Theoretical Computer Science, pages 149-168. Elsevier, 2016. doi:10.1016/j.entcs.2017.04. 010. · Zbl 1394.68059 · doi:10.1016/j.entcs.2017.04.010
[19] José Espírito Santo. The call-by-value lambda-calculus with generalized applications. In 28th EASCL Annual Conference on Computer Science Logic (CSL 2020). Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik GmbH, 2020. doi:10.4230/LIPICS.CSL.2020.35. · Zbl 07650848 · doi:10.4230/LIPICS.CSL.2020.35
[20] Philippa Gardner. Discovering needed reductions using type theory. In Masami Hagiya and John C. Mitchell, editors, International Conference on Theoretical Aspects of Computer Software (TACS), Sendai, Japan, 1994, volume 789 of Lecture Notes in Computer Science, pages 555-574. · Zbl 0942.03508
[21] Springer, 1994. doi:10.1007/3-540-57887-0_115. · doi:10.1007/3-540-57887-0_115
[22] Herman Geuvers and Tonny Hurkens. Deriving natural deduction rules from truth tables. In Logic and Its Applications, pages 123-138. Springer Berlin Heidelberg, 2016. doi:10.1007/ 978-3-662-54069-5_10. · Zbl 1485.03230 · doi:10.1007/978-3-662-54069-5_10
[23] Herman Geuvers and Tonny Hurkens. Proof terms for generalized natural deduction. In Andreas Abel, Fredrik Nordvall Forsberg, and Ambrus Kaposi, editors, 23rd International Conference on Types for Proofs and Programs (TYPES 2017), volume 104 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:39, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.TYPES.2017.3. · Zbl 1528.03226 · doi:10.4230/LIPIcs.TYPES.2017.3
[24] Herman Geuvers, Iris van der Giessen, and Tonny Hurkens. Strong normalization for truth table natural deduction. Fundamenta Informaticae, 170(1-3):139-176, 2019. doi:10.3233/ fi-2019-1858. · Zbl 1454.03076 · doi:10.3233/fi-2019-1858
[25] Felix Joachimski and Ralph Matthes. Standardization and confluence for a lambda calculus with generalized applications. In 11th International Conference on Rewriting Techniques and Applications (RTA), Norwich, UK, 2000, volume 1833 of Lecture Notes in Computer Science, pages 141-155. Springer, 2000. doi:10.1007/10721975_10. · Zbl 0964.03014 · doi:10.1007/10721975_10
[26] Felix Joachimski and Ralph Matthes. Short proofs of normalization for the simply-typed λ-calculus, permutative conversions and gödel’s T. Archive for Mathematical Logic, 42(1), 2003. doi:10.1007/s00153-002-0156-9. · Zbl 1025.03010 · doi:10.1007/s00153-002-0156-9
[27] Delia Kesner and Loïc Peyrot. Solvability for generalized applications. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD), Haifa, Israel, 2022, volume 228 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:22, Dagstuhl, Germany, 2022. Schloss Dagstuhl -Leibniz-Zentrum für Informatik. doi:10.4230/ LIPIcs.FSCD.2022.18. · Zbl 1541.68086 · doi:10.4230/LIPIcs.FSCD.2022.18
[28] Delia Kesner and Daniel Ventura. A resource aware computational interpretation for Herbelin’s syntax. In 12th International Colloquium on Theoretical Aspects of Computing (ICTAC), Cali, Colombia, 2015, volume 9399 of Lecture Notes in Computer Science, pages 388-403. Springer, 2015. doi:10.1007/978-3-319-25150-9_23. · Zbl 1407.68272 · doi:10.1007/978-3-319-25150-9_23
[29] Delia Kesner and Pierre Vial. Non-idempotent types for classical calculi in natural deduction style. Logical Methods in Computer Science ; Volume 16, 16(1), 2020. doi:10.23638/LMCS-16(1: 3)2020. · Zbl 1528.03127 · doi:10.23638/LMCS-16(1:3)2020
[30] Delia Kesner and Andrés Viso. Encoding tight typing in a unified framework. In 30th EACSL Annual Conference on Computer Science Logic (CSL), Göttingen, Germany (Virtual Conference), 2022, volume 216 of LIPIcs, pages 27:1-27:20. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CSL.2022.27. · Zbl 1541.68087 · doi:10.4230/LIPIcs.CSL.2022.27
[31] Paul Blain Levy. Call-by-push-value: Decomposing call-by-value and call-by-name. Higher-Order and Symbolic Computation, 19(4):377-414, 2006. doi:10.1007/s10990-006-0480-6. · Zbl 1112.68025 · doi:10.1007/s10990-006-0480-6
[32] Ralph Matthes. Characterizing strongly normalizing terms for a lambda calculus with generalized applications via intersection types. In Proceedings of the Satelite Workshops of the 27th Interna-tional Colloquium on Automata, Languages and Programming (ICALP), Geneva, Switzerland, 2000, pages 339-354. Carleton Scientific, Waterloo, Ontario, Canada, 2000.
[33] Ralph Matthes. Interpolation for natural deduction with generalized eliminations. In International Seminar on Proof Theory in Computer Science (PTCS), Dagstuhl Castle, Germany, 2001, volume 2183 of Lecture Notes in Computer Science, pages 153-169. Springer, 2001. doi:10. 1007/3-540-45504-3_10. · Zbl 1024.03016 · doi:10.1007/3-540-45504-3_10
[34] Loïc Peyrot. From Proof Terms to Programs: An operational and quantitative study of intuition-istic Curry-Howard calculi. PhD thesis, Université Paris Cité, 2022.
[35] Laurent Regnier. Une équivalence sur les lambda-termes. Theoretical Computer Science, 126(2):281-292, 1994. doi:10.1016/0304-3975(94)90012-4. · Zbl 0801.03013 · doi:10.1016/0304-3975(94)90012-4
[36] Peter Schroeder-Heister. Generalized rules for quantifiers and the completeness of the intuitionistic operators &, ∨, ⊃, f, ∀, ∃. In Computation and Proof Theory, pages 399-426. Springer, 1984. doi:10.1007/bfb0099494. · doi:10.1007/bfb0099494
[37] Peter Schroeder-Heister. A natural extension of natural deduction. Journal of Symbolic Logic, 49(4):1284-1300, 1984. doi:10.2307/2274279. · Zbl 0574.03045 · doi:10.2307/2274279
[38] Peter Schroeder-Heister. Generalized elimination inferences, higher-level rules, and the implications-as-rules interpretation of the sequent calculus. In Trends in Logic, pages 1-29. · Zbl 1339.03049
[39] Springer Netherlands, 2014. doi:10.1007/978-94-007-7548-0_1. · Zbl 1339.03049 · doi:10.1007/978-94-007-7548-0_1
[40] Masako Takahashi. Parallel reductions in λ-calculus. Information and Computation, 118(1):120-127, 1995. doi:10.1006/inco.1995.1057. · Zbl 0827.68060 · doi:10.1006/inco.1995.1057
[41] Neil Tennant. Autologic. Edinburgh University Press, Edinburgh, 1992.
[42] Neil Tennant. Ultimate normal forms for parallelized natural deductions. Logic Journal of IGPL, 10(3):299-337, 2002. doi:10.1093/jigpal/10.3.299. · Zbl 1010.03048 · doi:10.1093/jigpal/10.3.299
[43] Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2003. · Zbl 1030.68053
[44] Jan von Plato. Natural deduction with general elimination rules. Archive for Mathematical Logic, 40(7):541-567, 2001. doi:10.1007/s001530100091. · Zbl 1021.03050 · doi:10.1007/s001530100091
[45] Femke van Raamsdonk. Confluence and Normalisation for Higher-order Rewriting. PhD thesis, Vrije Universiteit Amsterdam, 1996.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.