Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T15:20:03.791Z Has data issue: false hasContentIssue false
  • English
  • Français

A tutorial on computational classical logic and the sequent calculus

Part of: JFP Research Articles

Published online by Cambridge University Press:  01 February 2018

PAUL DOWNEN  and
ZENA M. ARIOLA
PAUL DOWNEN
Affiliation:
University of Oregon, USA (e-mail: [email protected], [email protected])
ZENA M. ARIOLA
Affiliation:
University of Oregon, USA (e-mail: [email protected], [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.

We present a model of computation that heavily emphasizes the concept of duality and the interaction between opposites–production interacts with consumption. The symmetry of this framework naturally explains more complicated features of programming languages through relatively familiar concepts. For example, binding a value to a variable is dual to manipulating the flow of control in a program. By looking at the computational interpretation of the sequent calculus, we find a language that lets us speak about duality, control flow, and evaluation order in programs as first-class concepts.

We begin by reviewing Gentzen's LK sequent calculus and show how the Curry–Howard isomorphism still applies to give us a different basis for expressing computation. We then illustrate how the fundamental dilemma of computation in the sequent calculus gives rise to a duality between evaluation strategies: strict languages are dual to lazy languages. Finally, we discuss how the concept of focusing, developed in the setting of proof search, is related to the idea of type safety for computation expressed in the sequent calculus. In this regard, we compare and contrast two different methods of focusing that have appeared in the literature, static and dynamic focusing, and illustrate how they are two means to the same end.

Type
Articles
Information
Journal of Functional Programming , Volume 28 , 2018 , e3
Copyright
Copyright © Cambridge University Press 2018 

References

Andreoli, J.-M. (1992) Logic programming with focusing proofs in linear logic. J. Log. Comput. 2 (3), 297–347. doi: 10.1093/logcom/2.3.297.CrossRefGoogle Scholar
Appel, A. W. (1992) Compiling with Continuations. New York, NY, USA, 1992: Cambridge University Press. ISBN 0-521-41695-7.Google Scholar
Ariola, Z. M. & Herbelin, H. (2003) Minimal classical logic and control operators. In Proceedings of 30th International Colloquium in Automata, Languages and Programming:(ICALP 2003). Berlin, Heidelberg: Springer, p. 871–885. ISBN 978-3-540-45061-0. doi:10.1007/3-540-45061-068.Google Scholar
Ariola, Z. M., Bohannon, A. & Sabry, A. (2009) Sequent calculi and abstract machines. ACM Trans. Program. Lang. Syst. 31 (4), 13:1–13:48. ISSN 0164-0925. doi: 10.1145/1516507.1516508.CrossRefGoogle Scholar
Ariola, Z. M., Herbelin, H. & Saurin, A. (2011) Classical call-by-need and duality. In Proceedings of 10th International Conference in Typed Lambda Calculi and Applications (TLCA '11). Berlin, Heidelberg: Springer, pp. 27–44. ISBN 978-3-642-21690-9. doi: 10.1007/978-3-642-21691-6_6.CrossRefGoogle Scholar
Ariola, Z. M., Maraist, J., Odersky, M., Felleisen, M., & Wadler, P. (1995) A call-by-need lambda calculus. In Proceedings of 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '95). New York, NY, USA: ACM, pp. 233–246. ISBN 0-89791-692-1. doi: 10.1145/199448.199507.CrossRefGoogle Scholar
Church, A. (1932) A set of postulates for the foundation of logic. Ann. Math. 33 (2), 346–366. doi: 10.2307/1968337.CrossRefGoogle Scholar
Curien, P.-L. & Herbelin, H. (2000) The duality of computation. In Proceedings of 5th ACM SIGPLAN International Conference on Functional Programming (ICFP '00). New York, NY, USA: ACM, pp. 233–243. ISBN 1-58113-202-6. doi: 10.1145/351240.351262.CrossRefGoogle Scholar
Curien, P.-L. & Munch-Maccagnoni, G. (2010) The duality of computation under focus. In Proceedings of 6th IFIP TC 1/WG 2.2 International Conference in Theoretical Computer Science (TCS '10). Held as Part of WCC 2010, TCS, Berlin Heidelberg: Springer, pp. 165–181. ISBN 978-3-642-15240-5. doi: 10.1007/978-3-642-15240-5_13.CrossRefGoogle Scholar
Curry, H. B., Feys, R. & Craig, W. (1958) Combinatory Logic, vol. 1. North-Holland Publishing Company.Google Scholar
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., & Zadeck, F. K. (1991) Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst. 13 (4), 451–490. ISSN 0164-0925. doi: 10.1145/115372.115320.CrossRefGoogle Scholar
de Bruijn, N. (1968) AUTOMATH, A Language for Mathematics. Technical Report 66-WSK-05, Technological University Eindhoven.Google Scholar
Downen, P. & Ariola, Z. M. (2014) The duality of construction. In Proceedings of 23rd European Symposium on Programming in Programming Languages and Systems (ESOP '14). Held as Part of the European Joint Conferences on Theory and Practice of Software, Lecture Notes in Computer Science, vol. 8410, Berlin Heidelberg: Springer, pp. 249–269. ISBN 978-3-642-54832-1. doi: 10.1007/978-3-642-54833-8_14.CrossRefGoogle Scholar
Downen, P., Johnson-Freyd, P. & Ariola, Z. M. (2015) Structures for structural recursion. In Proceedings of 20th ACM SIGPLAN International Conference on Functional Programming (ICFP '15). New York, NY, USA: ACM, pp. 127–139. ISBN 978-1-4503-3669-7. doi: 10.1145/2784731.2784762.CrossRefGoogle Scholar
Downen, P., Maurer, L., Ariola, Z. M. & Peyton Jones, S. (2016) Sequent calculus as a compiler intermediate language. In Proceedings of 21st ACM SIGPLAN International Conference on Functional Programming (ICFP '16). New York, NY, USA: ACM, pp. 74–88. ISBN 978-1-4503-4219-3. doi: 10.1145/2951913.2951931.CrossRefGoogle Scholar
Felleisen, M. & Friedman, D. P. (1986) Control operators, the SECD machine, and the λ-calculus. In Proceedings of the IFIP TC 2/WG2.2 Working Conference on Formal Descriptions of Programming Concepts Part III, pp. 193–219.Google Scholar
Felleisen, M. & Hieb, R. (1992) The revised report on the syntactic theories of sequential control and state. Theor. Comput. Sci. 103 (2), 235–271. ISSN 0304-3975. doi: 10.1016/0304-3975(92)90014-7.CrossRefGoogle Scholar
Filinski, A. (1989) Declarative Continuations and Categorical Duality. Master's thesis, Computer Science Department, University of Copenhagen, 1989.Google Scholar
Gentzen, G. (1935a) Untersuchungen über das logische schließen. I. Math. Z. 39 (1), 176–210. ISSN 0025-5874. doi: 10.1007/BF01201353.CrossRefGoogle Scholar
Gentzen, G. (1935b) Untersuchungen über das logische schließen. II. Math. Z. 39 (1), 405–431. ISSN 0025-5874. doi: 10.1007/BF01201363.CrossRefGoogle Scholar
Girard, J.-Y. (1987) Linear logic. Theor. Comput. Sci. 50 (1):1–101. ISSN 0304-3975. doi:10.1016/0304-3975(87)90045-4.CrossRefGoogle Scholar
Girard, J.-Y. (1991) A new constructive logic: Classical logic. Math. Struct. Comput. Sci. 1 (3), 255–296. doi: 10.1017/S0960129500001328.CrossRefGoogle Scholar
Girard, J.-Y. (1993) On the unity of logic. Ann. Pure Appl. Log. 59 (3), 201–217. ISSN 0168-0072. doi: 10.1016/0168-0072(93)90093-S.CrossRefGoogle Scholar
Girard, J.-Y. (2001) Locus solum: From the rules of logic to the logic of rules. Math. Struct. Comput. Sci. 11 (3), 301–506. ISSN 0960-1295. doi: 10.1017/S096012950100336X.CrossRefGoogle Scholar
Girard, J.-Y., Taylor, P. & Lafont, Y. (1989) Proofs and Types. New York, USA: Cambridge University Press. ISBN 0-521-37181-3.Google Scholar
Graham-Lengrand, S. (2016) The Curry-Howard view of classical logic: A short introduction. Lecture Notes for the MPRI course on Curry-Howard correspondence for Classical Logic. URL http://www.lix.polytechnique.fr/~lengrand/Work/Teaching/MPRI/Notes.pdf. Unpublished Manuscript.Google Scholar
Griffin, T. G. (1990) A formulae-as-types notion of control. In Proceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '90, New York, NY, USA: ACM, pp. 47–58. ISBN 0-89791-343-4. doi: 10.1145/96709.96714.CrossRefGoogle Scholar
Herbelin, H. (1995) Séquents qu'on calcule: de l'interprétation du calcul des séquents comme calcul de λ-termes et comme calcul de stratégies gagnantes. PhD thesis, Université Paris 7, January 1995.Google Scholar
Herbelin, H. (2005) C'est maintenant qu'on calcule : Au coeur de la dualité. Habilitation thesis, Université Paris 11, 2005.Google Scholar
Howard, W. A. (1980) The formulae-as-types notion of constructions. In To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. Academic Press, pp. 479–490. ISBN 0123490502. Unpublished manuscript of 1969.Google Scholar
Kelsey, R., et al. (1998) Revised5 report on the algorithmic language Scheme. Higher-Order and Symb. Comput. 11 (1), 7–105. ISSN 1573-0557. doi: 10.1023/A:1010051815785.Google Scholar
Kennedy, A. (2007) Compiling with continuations, continued. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP '07, New York, NY, USA: ACM, pp. 177–190. ISBN 978-1-59593-815-2. doi: 10.1145/1291151.1291179.CrossRefGoogle Scholar
Krivine, J.-L. (2007) A call-by-name lambda-calculus machine. Higher-Order Symb. Comput. 20 (3), 199–207. ISSN 1388-3690. doi: 10.1007/s10990-007-9018-9.CrossRefGoogle Scholar
Laurent, O. (2002) Étude de la polarisation en logique. PhD thesis, Université de la Méditerranée - Aix-Marseille II.Google Scholar
Munch-Maccagnoni, G. (2009) Focalisation and classical realisability. In Computer Science Logic: 23rd international Workshop, CSL 2009, 18th Annual Conference of the EACSL, CSL 2009, Berlin Heidelberg: Springer, pp. 409–423. ISBN 978-3-642-04027-6. doi: 10.1007/978-3-642-04027-6_30.CrossRefGoogle Scholar
Munch-Maccagnoni, G. & Scherer, G. (2015) Polarised intermediate representation of lambda calculus with sums. In Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, pp. 127–140. doi: 10.1109/LICS.2015.22.CrossRefGoogle Scholar
Ohori, A. (1999) The logical abstract machine: A Curry-Howard isomorphism for machine code. In Functional and Logic Programming: 4th Fuji International Symposium, FLOPS '99, Berlin, Heidelberg: Springer, pp. 300–318. ISBN 978-3-540-47950-5. doi: 10.1007/10705424_20.CrossRefGoogle Scholar
Ohori, A. (2003) Register allocation by proof transformation. In Programming Languages and Systems: 12th European Symposium on Programming, ESOP 2003 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, ESOP 2003, Berlin Heidelberg: Springer, pp. 399–413. ISBN 978-3-540-36575-4. doi: 10.1007/3-540-36575-3_27.CrossRefGoogle Scholar
Parigot, M. (1992) l m-calculus: An algorithmic interpretation of classical natural deduction. In Logic Programming and Automated Reasoning: International Conference, LPAR '92, pages 190–201, Berlin, Heidelberg, July 1992. Springer Berlin Heidelberg. ISBN 978-3-540-47279-7. doi:10.1007/BFb0013061.CrossRefGoogle Scholar
Peyton Jones, S., Tolmach, A. & Hoare, T. (2001) Playing by the rules: Rewriting as a practical optimisation technique in GHC. In Haskell Workshop 2001. ACM SIGPLAN.Google Scholar
Pfenning, F. (2010a) Lecture notes on focusing. Lecture notes for the Oregon Programming Languages Summer School 2010 course on Proof Theory Foundations, Lecture 4. URL http://www.cs.cmu.edu/~fp/courses/oregon-m10/04-focusing.pdf. Unpublished Manuscript.Google Scholar
Pfenning, F. (2010b) Lecture notes on sequent calculus. Lecture Notes for the Carnegie Mellon University course 15-816 on Modal Logic, Lecture 8. URL http://www.cs.cmu.edu/~fp/courses/15816-s10/lectures/08-seqcalc.pdf. Unpublished Manuscript.Google Scholar
Emmanuel, P. (2004) Explicit Substitutions, Logic and Normalization. PhD thesis, Université Paris-Diderot – Paris VII, Jun. 2004.Google Scholar
Reynolds, J. C. (1983) Types, abstraction and parametric polymorphism. In Proceedings of the IFIP 9th World Computer Congress, Information Processing 83. Amsterdam: Elsevier Science Publishers B. V. (North-Holland), pp. 513–523.Google Scholar
Reynolds, J. C. (1993) The discoveries of continuations. Lisp and Symbol. Comput. 6 (3–4), 233–248. ISSN 0892-4635. doi: 10.1007/BF01019459. URL http://dx.doi.org/10.1007/BF01019459.CrossRefGoogle Scholar
Reynolds, J. C. (1998) Definitional interpreters for higher-order programming languages. Higher-Order Symbol. Comput. 11 (4), 363–397. ISSN 1388-3690. doi: 10.1023/A:1010027404223.CrossRefGoogle Scholar
Scherer, G. (2016) Which Types Have a Unique Inhabitant? Focusing on Pure Program Equivalence. PhD thesis, Université Paris-Diderot.CrossRefGoogle Scholar
Selinger, P. (2001) categories, Control and duality: On the categorical semantics of the lambda-mu calculus. Math. Struct. Comput. Sci. 11 (2), 207–260. ISSN 0960-1295. doi: 10.1017/S096012950000311X.CrossRefGoogle Scholar
Selinger, P. (2003) Some remarks on control categories, 2003. URL http://mathstat.dalca/~selinger/papers/controlremarks.pdf. Unpublished Manuscript.Google Scholar
Singh, S., Peyton Jones, S., Norell, U., Pottier, F., Meijer, E., & McBride, C. (2011) Sexy types–-are we done yet? Software Summit. URL https://www.microsoft.com/en-us/research/video/sexy-types-are-we-done-yet/.Google Scholar
Wadler, P. (2003) Call-by-value is dual to call-by-name. In Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming. New York, NY, USA: ACM, pp. 189–201. ISBN 1-58113-756-7. doi: 10.1145/944705.944723.CrossRefGoogle Scholar
Wadler, P. (2005) Call-by-value is dual to call-by-name, reloaded. In Proceedings of 16th International Conference in Term Rewriting and Applications (RTA '05)., Berlin Heidelberg: Springer, pp. 185–203. ISBN 978-3-540-32033-3. doi: 10.1007/978-3-540-32033-3_15. URL dx.doi.org/10.1007/978-3-540-32033-3_15.CrossRefGoogle Scholar
Wright, A. K. & Felleisen, M. (1994) A syntactic approach to type soundness. Inform. Comput. 115 (1), 38–94. ISSN 0890-5401. doi: 10.1006/inco.1994.1093.CrossRefGoogle Scholar
Zeilberger, N. (2009) The Logical Basis of Evaluation Order and Pattern-Matching. PhD thesis, Carnegie Mellon University.Google Scholar
Zeilberger, N. (2013) Polarity in proof theory and programming. Lecture Notes for the Summer School on Linear Logic and Geometry of Interaction in Torino, Italy. URL http://noamz.org/talks/logpolpro.pdf. Unpublished Manuscript.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.