On completeness and parametricity in the realizability semantics of System F
share
A general approach to the realizability semantics of System F is obtained by considering closure operators over sets of lambda-terms. We investigate completeness and relational parametricity in the semantics generated by such closure operators. We prove general results and show that they can be applied to several well-known semantics, as those arising from Tait's saturatedness conditions and from Girard's reducibility candidates. First, we show that, for a wide class of semantics, completeness holds for positive second order types, by generalizing some completeness results in the literature. Then we show that Reynolds parametric semantics can be formulated within the realizability semantics which are stable by union. We prove a parametricity theorem stating that closed realizers of a given type are parametric at that type. Finally, we consider syntactic dinaturality and prove that, for positive second order types, parametric terms are dinatural. Our results show that, for positive second order types, realizability, parametricity, dinaturality and typability are equivalent properties of closed normal lambda-terms.
READ FULL TEXT