Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-12T11:08:49.018Z Has data issue: false hasContentIssue false
  • English
  • Français

Canonical typing and ∏-conversion in the Barendregt Cube

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Fairouz Kamareddine  and
Rob Nederpelt
Fairouz Kamareddine
Affiliation:
Department of Computing Science, 17 Lilybank Gardens, University of Glasgow, Glasgow G12 8QQ, Scotland (e-mail: [email protected])
Rob Nederpelt
Affiliation:
Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600 MB Eindhoven, The Netherlands (e-mail: [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.

In this article, we extend the Barendregt Cube with ∏-conversion (which is the analogue of β-conversion, on product type level) and study its properties. We use this extension to separate the problem of whether a term is typable from the problem of what is the type of a term.

Type
Articles
Information
Journal of Functional Programming , Volume 6 , Issue 2 , March 1996 , pp. 245 - 267
Copyright
Copyright © Cambridge University Press 1996

References

Barendregt, H. 1992. Lambda calculi with types. In: Handbook of Logic in Computer Science, vol. II, pp. 118–414, Abramsky, S., Gabbay, D. M. and Maibaum, T. S. E., editors. Oxford: Oxford University Press.CrossRefGoogle Scholar
de Bruijn, N. G. 1974. Some extensions of AUTOMATH: the AUT-4 family. Department of Mathematics, Eindhoven University of Technology.Google Scholar
Church, A. 1932–1933. A set of postulates for the foundation of logic. Annals of Math. 33, 346–366, 34, 839–864.CrossRefGoogle Scholar
Church, A. 1940. A formulation of the simple theory of types. Journal of Symbolic Logic, 5, 56–68.CrossRefGoogle Scholar
Frege, G. 1879. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle, Verlag von Louis Nebert. (Reprinted 1964, Hildesheim, Georg Olms Verlagsbuchhaltung.)Google Scholar
Hilbert, D. and Ackermann, W. 1928. Grundzüge der theoretischen Logik. Berlin: Springer Verlag.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, Hindley, J. R. and Seldin, J. P., editors. New York: Academic Press.Google Scholar
Kamareddine, F. and Nederpelt, R. P. 1993. On stepwise explicit substitution. International Journal of Foundations of Computer Science, 4(3), 197–240.CrossRefGoogle Scholar
Kamareddine, F. and Nederpelt, R. P. 1994 a. Canonical Typing and ∏-Conversion. Research report, Department of Mathematics and Computing Science, Eindhoven University of Technology.Google Scholar
Kamareddine, F. and Nederpelt, R. P. 1994 b. A unified approach to type theory through a refined λ-calculus. Theoretical Computer Science, 136, 183–216.CrossRefGoogle Scholar
Kamareddine, F. and Nederpelt, R. P. 1996. A useful λ-notation. Theoretical Computer Science, 155.CrossRefGoogle Scholar
Kamareddine, F. and Nederpelt, R. P. 1995. Generalizing reduction in λ-calculus. Functional Programming, 5(4), 637–651.CrossRefGoogle Scholar
Terlouw, J. 1989. Een nadere bewijstheoretische analyse van GSTTs. Technical report, Department of Computer Science, University of Nijmegen.Google Scholar
Whitehead, A. N. and Russell, B. 1960. Principia Mathematica. Cambridge: Cambridge University Press. (Reprinted 1960.)Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.