Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-21T19:07:35.004Z Has data issue: false hasContentIssue false
  • English
  • Français

An insider's look at LF type reconstruction: everything you (n)ever wanted to know

Part of: JFP Research Articles

Published online by Cambridge University Press:  02 November 2012

BRIGITTE PIENTKA
BRIGITTE PIENTKA*
Affiliation:
McGill University, Montreal, Quebec, Canada (e-mail: bpientka@cs.mcgill.ca)
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.

Although type reconstruction for dependently typed languages is common in practical systems, it is still ill-understood. Detailed descriptions of the issues around it are hard to find and formal descriptions together with correctness proofs are non-existing. In this paper, we discuss a one-pass type reconstruction for objects in the logical framework LF, describe formally the type reconstruction process using the framework of contextual modal types, and prove correctness of type reconstruction. Since type reconstruction will find most general types and may leave free variables, we in addition describe abstraction which will return a closed object where all free variables are bound at the outside. We also implemented our algorithms as part of the Beluga language, and the performance of our type reconstruction algorithm is comparable to type reconstruction in existing systems such as the logical framework Twelf.

Type
Articles
Information
Journal of Functional Programming , Volume 23 , Issue 1 , January 2013 , pp. 1 - 37
Copyright
Copyright © Cambridge University Press 2012

References

Abadi, M., Cardelli, L., Curien, P.-L. & Lévy, J.-J. (1990) Explicit substitutions. In Proceedings of the 17th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, pp. 31–46.Google Scholar
Aydemir, B., Chargueraud, A., Pierce, B., Pollack, R. & Weirich, S. (2008) Engineering formal metatheory. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Wadler, P. (ed.). ACM Press, pp. 3–15r.CrossRefGoogle Scholar
Barras, B. & Bernardo, B. (2008) The implicit calculus of constructions as a programming language with dependent types. In Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures (FOSSACS'08), Amadio, R. M. (ed.), Lecture Notes in Computer Science (LNCS 4962). Springer, pp. 365–379.Google Scholar
Bertot, Y. & Castéran, P. (2004) Interactive Theorem Proving and Program Development. Coq'art: The Calculus of Inductive Constructions. Springer.CrossRefGoogle Scholar
Boespflug, M. (2010) Dedukti. Available at: http://www.lix.polytechnique.fr/deduktiGoogle Scholar
Cervesato, I. & Pfenning, F. (2003) A linear spine calculus. J. Logic Comput. 13 (5), 639–688.CrossRefGoogle Scholar
Crary, K. (2003) Toward a foundational typed assembly language. In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'03). New Orleans, LA: ACM Press, pp. 198–212.CrossRefGoogle Scholar
Dowek, G. (1993) The undecidability of typability in the lambda-pi-calculus. In Proceedings of the International Conference on Typed Lambda Calculi and Applications (TLCA '93). London: Springer-Verlag, pp. 139–145.CrossRefGoogle Scholar
Dowek, G., Hardin, T. & Kirchner, C. (1995) Higher-order unification via explicit substitutions. In Proceedings of the 10th Annual Symposium on Logic in Computer Science, Kozen, D. (ed.). San Diego, CA: IEEE Computer Society Press, pp. 366–374.CrossRefGoogle Scholar
Dowek, G., Hardin, T., Kirchner, C. & Pfenning, F. (1996) Unification via explicit substitutions: The case of higher-order patterns. In Proceedings of the Joint International Conference and Symposium on Logic Programming, Maher, M. (ed.). Bonn: MIT Press, pp. 259–273.Google Scholar
Hagiya, M. & Toda, Y. (1994) On implicit arguments. In Logic, Language and Computation: Festschrift in Honor of Satoru Takasu. Jones, N. D., Hagiya, M. & Sato, M. (eds.), Lecture Notes in Computer Science, vol. 792. Springer, pp. 10–30.CrossRefGoogle Scholar
Harper, R., Honsell, F. & Plotkin, G. (1993) A framework for defining logics. J. ACM 40 (1), 143–184.CrossRefGoogle Scholar
Harper, R. & Licata, D. R. (2007) Mechanizing metatheory in a logical framework. J. Funct. Program. 17 (4–5), 613–673.CrossRefGoogle Scholar
Lee, D. K., Crary, K. & Harper, R. (2007) Towards a mechanized metatheory of standard ML. In Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'07). New York: ACM Press, pp. 173–184.Google Scholar
Licata, D. R., Zeilberger, N. & Harper, R. (2008) Focusing on binding and computation. In Proceedings of the 23rd Symposium on Logic in Computer Science, Pfenning, F. (ed.). IEEE Computer Society Press, pp. 241–252.Google Scholar
Luther, M. (2001) More on implicit syntax. In Proceedings of the First International Joint Conference on Automated Reasoning (IJCAR'01), Gore, R., Leitsch, A. & Nipkow, T. (eds.), Lecture Notes in Artificial Intelligence (LNAI) 2083. Springer, pp. 386–400.Google Scholar
McBride, C. & McKinna, J. (2004) The view from the left. J. Funct. Program. 14 (1), 69–111.CrossRefGoogle Scholar
Miller, D. (1991) Unification of simply typed lambda-terms as logic programming. In Proceedings of the 8th International Logic Programming Conference. MIT Press, pp. 255–269.Google Scholar
Miquel, A. (2001) The implicit calculus of constructions: Extending pure type systems with an intersection type binder and subtyping. In Proceedings of the 5th International Conference on Typed Lambda Calculi and Aplications (TLCA'01), Abramsky, S. (ed.), Lecture Notes in Computer Science (LNCS 2044). Springer, pp. 344–359.CrossRefGoogle Scholar
Nanevski, A., Pfenning, F. & Pientka, B. (2008) Contextual modal type theory. ACM Trans. Comput. Logic 9 (3), 1–49.CrossRefGoogle Scholar
Necula, G. C. (1997) Proof-carrying code. In Proceedings of the 24th Annual Symposium on Principles of Programming Languages (POPL'97). ACM Press, pp. 106–119.Google Scholar
Necula, G. C. & Lee, P. (1998) Efficient representation and validation of logical proofs. In Proceedings of the 13th Annual Symposium on Logic in Computer Science (LICS'98), Pratt, V. (ed.). Indianapolis, IN: IEEE Computer Society Press, pp. 93–104.Google Scholar
Norell, U. (2007 September) Towards a Practical Programming Language Based on Dependent Type Theory. PhD. thesis, Department of Computer Science and Engineering, Chalmers University of Technology. Technical Report 33D.Google Scholar
Pfenning, F. (1991) Logic programming in the LF logical framework. In Logical Frameworks, Huet, G. & Plotkin, G. (eds.), Cambridge University Press, pp. 149–181.CrossRefGoogle Scholar
Pfenning, F. (2012) Computation and Deduction. Cambridge University Press. In press.Google Scholar
Pfenning, F. & Schürmann, C. (1999) System description: Twelf — a meta-logical framework for deductive systems. In 16th International Conference on Automated Deduction (CADE-16), Ganzinger, H. (ed), Lecture Notes in Artificial Intelligence, vol. 1632. Springer, pp. 202–206.CrossRefGoogle Scholar
Pientka, B. (2003) Tabled Higher-Order Logic Programming. PhD. thesis, Department of Computer Science, Carnegie Mellon University. CMU-CS-03-185.Google Scholar
Pientka, B. (2007) Proof pearl: The power of higher-order encodings in the logical framework LF. In Proceedings of the 20th International Conference on Theorem Proving in Higher Order Logics (TPHOLs'07), Schneider, K. & Brandt, J. (eds.), Lecture Notes in Computer Science (LNCS 4732). Springer, pp. 246–261.CrossRefGoogle Scholar
Pientka, B. (2008) A type-theoretic foundation for programming with higher-order abstract syntax and first-class substitutions. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'08). ACM Press, pp. 371–382.Google Scholar
Pientka, B. & Dunfield, J. (2008) Programming with proofs and explicit contexts. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP'08). ACM Press, pp. 163–173.Google Scholar
Pientka, B. & Dunfield, J. (2010) Beluga: A framework for programming and reasoning with deductive systems (System Description). In Proceedings of the 5th International Joint Conference on Automated Reasoning (IJCAR'10), Giesl, J. & Haehnle, R. (eds.). Lecture Notes in Artificial Intelligence (LNAI 6173). Springer-Verlag, pp. 15–21.Google Scholar
Pollack, R. (1990). Implicit syntax. Proceedings of First Workshop on Logical Frameworks, Eds. Huet, G. and Plotkin, G., pp 421–435Google Scholar
Poswolsky, A. B. & Schürmann, C. (2008) Practical programming with higher-order encodings and dependent types. In Proceedings of the 17th European Symposium on Programming (ESOP '08), vol. 4960. Springer, pp. 93–107.Google Scholar
Poswolsky, A. & Schürmann, C. (2009) System description: Delphin—a functional programming language for deductive systems. In Proceedings of the International Workshop on Logical Frameworks and Meta-languages: Theory and Practice (LFMTP'08), Electronic Notes in Theoretical Computer Science (ENTCS), vol. 228. Elsevier, pp. 135–141.Google Scholar
Reed, J. (2004) Redundancy Elimination for LF. In 4th Workshop on Logical Frameworks and Meta-Languages (LFM'04), Schürmann, C (ed.). Electronic Notes in Theoretical Computer Science (ENTCS) vol 199, pp 89–106.Google Scholar
Reed, J. (2009) Higher-order constraint simplification in dependent type theory. In International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP'09), Felty, A & Cheney, J. (eds.). ACM Press, pp 49–56.CrossRefGoogle Scholar
Schürmann, C. & Pfenning, F. (2003) A coverage checking algorithm for LF. In Proceedings of the 16th International Conference on Theorem Proving in Higher Order Logics (TPHOLS'03), Basin, D. & Wolff, B. (eds.). Springer, pp. 120–135.CrossRefGoogle Scholar
Virga, R. (1999) Higher-Order Rewriting with Dependent Types. PhD. thesis, Department of Mathematical Sciences, Carnegie Mellon University. CMU-CS-99-167.Google Scholar
Watkins, K., Cervesato, I., Pfenning, F. & Walker, D. (2002) A Concurrent Logical Framework I: Judgments and Properties. Technical Report. CMU-CS-02-101. Department of Computer Science, Carnegie Mellon University.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.