Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-09T14:06:32.529Z Has data issue: false hasContentIssue false

Sequent combinators: a Hilbert system for the lambda calculus

Published online by Cambridge University Press:  01 February 2000

HEALFDENE GOGUEN
Affiliation:
Department of Computer Science, The King's Buildings, University of Edinburgh, Edinburgh, EH9 3JZ, Scotland. Email: [email protected] Now at AT&T Labs, 180 Park Ave., Florham Park NJ 07932 USA.
JEAN GOUBAULT-LARRECQ
Affiliation:
G.I.E. Dyade, INRIA Rocquencourt, Domaine de Voluceau, B.P.105, F-78153 Le Chesnay Cedex, France. Email: [email protected]

Abstract

This paper introduces Hilbert systems for λ-calculus, called sequent combinators, addressing many of the problems of Hilbert systems that have led to the more widespread adoption of natural deduction systems in computer science. This suggests that Hilbert systems, with their uniform approach to meta-variables and substitution, may be a more suitable framework than λ-calculus for type theories and programming languages. Two calculi are introduced here. The calculus SKIn captures λ-calculus reduction faithfully, is confluent even in the presence of meta-variables, is normalizing but not strongly normalizing in the typed case, and standardizes. The sub-calculus SKInT captures λ-reduction in slightly less obvious ways, and is a language of proof-terms not directly for intuitionistic logic, but for a fragment of S4 that we name near-intuitionistic logic. To our knowledge, SKInT is the first confluent, first-order calculus to capture λ-calculus reduction fully and faithfully and be strongly normalizing in the typed case. In particular, no calculus of explicit substitutions has yet achieved this goal.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This paper was submitted by invitation for inclusion in the special issue in honor of Professor Roger Hindley's 60th birthday.