Normalization, approximation, and semantics for combinator systems

This paper studies normalization of typeable terms and the relation between approximation semantics and filter models for Combinator Systems. It presents notions of approximants for terms, intersection type assignment, and reduction on type derivations; the last will be proved to be strongly normalizable. With this result, it is proved that every typeable term has an approximant with the same type, and a characterization of the normalization behaviour of terms using their assignable types is given. Then the two semantics are defined and compared, and it is shown that the approximants semantics is fully abstract but the filter semantics is not.

Authors

• Steffen van Bakel
• Maribel Fernández

Keywords

• Intersection types
• Approximants
• Filter semantics
• Combinators