Type Inference for System F with and without the Eta Rule Joe Wells Church devised the lambda calculus intending it to be a foundation for mathematics instead of set theory, but the lambda calculus has been most useful as a model of computation. Types have been added to the lambda calculus to enforce meaningful computations. Typability asks for a term whether there exists some type it can be given.
Type checking asks whether a term can be given a particular type.
The decidability of these problems has been settled for restrictions and extensions of F and related systems and complexity lower-bounds have been determined for typability in F, but decidability for F was an open question for many years. Subtyping relates types so that terms of one type automatically belong to other types. Mitchell devised a simple subtyping system for F, one without bounded polymorphic quantification or a distinguished supertype of all types. Mitchell showed extending F with his subtyping is the same as adding the eta rule to produce System F plus eta, which allows eta-equivalent terms to have the same types. Until recently, the decidability of Mitchell's subtyping has been unknown as has been the decidability of type checking and typability for F plus eta.