Information and Computation · 1995 · 68 citations · 7 references
ComputingComputer ScienceMathematicsFormal MethodsLogicTheory Of ComputationAxiomatic Set TheoryFirst-order LogicFormal SemanticsModel TheoryPredicate LogicType SystemsAbstractionDefinability TheoryLambda AbstractionLambda CalculusLambda Calculus SemanticsLogical RelationsType-logical SemanticsTyped Lambda Calculus
Sieber has described a model of PCF consisting of continuous functions that are invariant under certain (finitary) logical relations, and shown that it is fully abstract for closed terms of up to third-order types. We show that one may achieve full abstraction at all types using a form of "Kripke logical relations" introduced by Jung and Tiuryn to characterize λ-definability.
7
LCF considered as a programming language
Gordon Plotkin · Theoretical Computer Science · 1977 · 1.1K citations
Types, Abstraction and Parametric Polymorphism.
John Reynolds · IFIP Congress · 1983 · 771 citations
Parametricity and local variables
Peter W. O’Hearn, R. D. Tennent · Journal of the ACM · 1995 · 122 citations · Full text
Type Systems for Programming Languages.
John C. Mitchell · 1990 · 87 citations