The converse principal type-scheme theorem in lambda calculus

✍ Scribed by Sachio Hirokawa

• Book ID: 104744847
• Publisher: Springer Netherlands
• Year: 1992
• Tongue: English
• Weight: 637 KB
• Volume: 51
• Category: Article
• ISSN: 0039-3215
• DOI: 10.1007/bf00370332

✦ Synopsis

A principal type-scheme of a A-term is the most general type-scheme for the term. The converse principal type-scheme theorem (J.R. Hindley, The principal typescheme of an object in combinatory logic, Trans. Amer. Math. Soe. 146 (1969) P9-60) states that every type-scheme of a combinatory term is a principal type-scheme of some combinatory term.

This paper shows a simple proof for the theorem in A-calculus, by constructing an algorithm which transforms a type assignment to a A-term into a principal type assignment to another A-term that has the type as its principal type-scheme. The clearness of the algorithm is due to the characterization theorem of principal type-assignment figures. The algorithm is applicable to BCIW-A-terms as well. Thus a uniform proof is presented for the converse principal type-scheme theorem for general A-terms and BCIW-A-terms.