system F
E588093
System F is a polymorphically typed lambda calculus that extends the simply typed lambda calculus with universal quantification over types, forming a foundational system for studying parametric polymorphism in programming languages and type theory.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| System F | 0 |
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
formal system
ⓘ
polymorphically typed lambda calculus ⓘ typed lambda calculus ⓘ |
| canEncode |
Church encodings of data structures
ⓘ
algebraic data types ⓘ existential types ⓘ product types ⓘ sum types ⓘ |
| extends | simply typed lambda calculus ⓘ |
| formalizes | parametric polymorphism ⓘ |
| hasAlternativeName |
polymorphic lambda calculus
NERFINISHED
ⓘ
second-order lambda calculus NERFINISHED ⓘ |
| hasCorrespondenceWith | second-order intuitionistic logic ⓘ |
| hasFeature |
impredicative polymorphism
ⓘ
type abstraction ⓘ type application ⓘ type variables ⓘ |
| hasJudgmentForm | Γ ⊢ t : τ ⓘ |
| hasKindOfPolymorphism | parametric polymorphism ⓘ |
| hasProperty |
Church–Rosser property
ⓘ
confluent reduction ⓘ strong normalization ⓘ subject reduction ⓘ type safety ⓘ |
| hasQuantificationLevel | second-order ⓘ |
| hasRestriction | no general algorithm for type inference ⓘ |
| hasTermLanguage | lambda terms with type abstraction and application ⓘ |
| hasTypeSystem | second-order type system ⓘ |
| hasTypicalNotation | ∀α. τ for universal type quantification ⓘ |
| influenced |
Girard–Reynolds polymorphism in programming languages
ⓘ
Hindley–Milner type system NERFINISHED ⓘ System Fω NERFINISHED ⓘ |
| isBasisFor | design of polymorphic type systems ⓘ |
| isMoreExpressiveThan | simply typed lambda calculus ⓘ |
| isSubsetOf | Calculus of Constructions (in terms of expressiveness hierarchy) NERFINISHED ⓘ |
| isUndecidable |
typability problem
ⓘ
type inhabitation problem ⓘ |
| relatedTo | Curry–Howard correspondence NERFINISHED ⓘ |
| requires | explicit type annotations for full type checking ⓘ |
| supports | universal quantification over types ⓘ |
| usedFor |
studying polymorphism in programming languages
ⓘ
studying type abstraction ⓘ |
| usedIn |
programming language theory
ⓘ
type theory ⓘ |
| wasIndependentlyIntroducedBy | John C. Reynolds NERFINISHED ⓘ |
| wasIntroducedBy | Jean-Yves Girard NERFINISHED ⓘ |
| wasIntroducedInYear | 1972 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.