New notions of reduction and non-semantic proofs of strong /spl beta/-normalization in typed /spl lambda/-calculi

摘要

Two notions of reduction for terms of the /spl lambda/-calculus are introduced and the question of whether a /spl lambda/-term is /spl beta/-strongly normalizing is reduced to the question of whether a /spl lambda/-term is merely normalizing under one of the notions of reduction. This gives a method to prove strong /spl beta/-normalization for typed /spl lambda/-calculi. Instead of the usual semantic proof style based on Tait's realizability or Girard's "candidats de reductibilite", termination can be proved using a decreasing metric over a well-founded ordering. This proof method is applied to the simply-typed /spl lambda/-calculus and the system of intersection types, giving the first non-semantic proof for a polymorphic extension of the /spl lambda/-calculus.