On principal types of combinators

✍ Scribed by Sabine Broda; Luı́s Damas

• Book ID: 104326759
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 125 KB
• Volume: 247
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00086-9

✦ Synopsis

In this paper we study (in some cases) the relationship between the combinatory completeness of a set of typable combinators, with simple types, for a system of -calculus and the axiomatic completeness, under substitution and modus ponens, of the respective set of principal types for the corresponding logical system. We show that combinatory completeness is a necessary, but not su cient, condition for axiomatic completeness in the K-and in the I-calculus, while the two problems become equivalent for the BCK--as well as for the BCI--calculus. Furthermore, we present an algorithm which, whenever (B; ) is a principal pair for some normal BCK--term M , reconstructs M up to -conversion and which fails if there is no normal BCK--term for which (B; ) is a principal pair. From the correctness proof of the algorithm we also obtain another proof for the fact that each BCK--term in normal form is completely determined by its principal pairs.