WikiLean Articles · Brain · Contribute · About

Diff — System F

Revision #5851 → #5852 · back to history

modifiedSystem F (typed lambda calculus with universal quantification)2456fcb067ab
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"is a typed lambda calculus that introduces, to simply typed lambda calculus , a mechanism of universal quantification over types"},"resolution":"not_attempted"}}]
modifiedIdentity function type A→A in System Fbe1a45e4aa3c
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"the fact that the identity function can have any type of the form A → A would be formalized in System F"},"resolution":"not_attempted"}}]
modifiedStrong normalization of System F039e376a0a2c
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"System F is strongly normalizing"},"resolution":"not_attempted"}}]
modifiedUndecidability of type inference in System F559d615adaf9
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"type inference in System F (without explicit type annotations) is undecidable"},"resolution":"not_attempted"}}]
modifiedCurry–Howard correspondence for System F5bacd57af372
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"System F corresponds to second-order propositional intuitionistic logic"},"resolution":"not_attempted"}}]
modifiedSystem F within the lambda cube6f3b25eac98f
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"System F can be seen as part of the lambda cube"},"resolution":"not_attempted"}}]
modifiedTyping rules of System F735bd298299b
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"The typing rules of System F are those of simply typed lambda calculus with the addition of the following:"},"resolution":"not_attempted"}}]
modifiedUniversal Bool type in System F5f5020d033f7
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Logic and predicates","snippet":"is the type of all functions which take as input a type α and two expressions of type α, and produce as output an expression of type α"},"resolution":"not_attempted"}}]
modifiedTRUE and FALSE Church Booleans06088274786c
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Logic and predicates","snippet":"The following two definitions for the Boolean values"},"resolution":"not_attempted"}}]
modifiedLogic operators in System Fddc0ce029501
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Logic and predicates","snippet":"we can define some logic operators"},"resolution":"not_attempted"}}]
modifiedIFTHENELSE functiona4ee408e496d
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Logic and predicates","snippet":"there is no need for an IFTHENELSE function as one can just use raw"},"resolution":"not_attempted"}}]
modifiedISZERO predicatedb4b403886b6
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Logic and predicates","snippet":"The most fundamental predicate is ISZERO which returns"},"resolution":"not_attempted"}}]
modifiedExistential quantifier encoding in System F1f79597bc31a
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Logic and predicates","snippet":"the existential quantifier (and therefore existential types) can be implemented in system F by the following"},"resolution":"not_attempted"}}]
modifiedAbstract structures and constructors7f0e3bea9084
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F structures","snippet":"Abstract structures ( S ) are created using constructors"},"resolution":"not_attempted"}}]
modifiedRecursive type of S with m constructors3ce248e644c0
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F structures","snippet":"If you have m of these constructors, you can define the type of S as:"},"resolution":"not_attempted"}}]
modifiedNatural numbers as inductive datatype N7ce4d793bf65
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F structures","snippet":"the natural numbers can be defined as an inductive datatype N with constructors"},"resolution":"not_attempted"}}]
modifiedTyped Church numerals in System F220ab9387de6
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F structures","snippet":"The terms of this type comprise a typed version of the Church numerals"},"resolution":"not_attempted"}}]
modifiedChurch numeral as higher-order function91f364dd4f0e
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F structures","snippet":"the Church numeral for n is a function that takes a function f as argument and returns the n th power of f"},"resolution":"not_attempted"}}]
modifiedWells's undecidability of Curry-style System F type checkingee6b0d3d1890
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Use in programming languages","snippet":"by proving that type checking is undecidable for a Curry-style variant of System F"},"resolution":"not_attempted"}}]
modifiedUndecidability of type inference (corollary of Wells's result)623fee3eb1a1
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Use in programming languages","snippet":"Wells's result implies that type inference for System F is impossible"},"resolution":"not_attempted"}}]
modifiedHindley–Milner type systemc8c9e1a14110
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Use in programming languages","snippet":"does have an easy type inference algorithm and is used for many statically typed functional programming languages"},"resolution":"not_attempted"}}]
modifiedSecond-order polymorphic lambda calculus (F2)9a10099df6e2
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The Girard–Reynolds isomorphism","snippet":"the second-order polymorphic lambda calculus (F2) was discovered by Girard (1972) and independently by Reynolds (1974)"},"resolution":"not_attempted"}}]
modifiedGirard's representation theoremc958ba7e3e42
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The Girard–Reynolds isomorphism","snippet":"Girard proved the representation theorem"},"resolution":"not_attempted"}}]
modifiedReynolds's abstraction theorembd953bc73fb9
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The Girard–Reynolds isomorphism","snippet":"Reynolds proved the abstraction theorem"},"resolution":"not_attempted"}}]
modifiedGirard–Reynolds isomorphismeca6d1ec6359
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The Girard–Reynolds isomorphism","snippet":"a Girard projection followed by a Reynolds embedding form the identity"},"resolution":"not_attempted"}}]
modifiedSystem F ω (higher-order polymorphic lambda calculus)3479f902f79f
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F ω","snippet":"System F ω or the higher-order polymorphic lambda calculus combines the first axis (polymorphism) with the second axis"},"resolution":"not_attempted"}}]
modifiedInductive family of kinds in System F ω97e45c284041
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F ω","snippet":"System F ω can be defined inductively on a family of systems, where induction is based on the kinds permitted in each system"},"resolution":"not_attempted"}}]
modifiedSystem F ω as a limit systemf7c3d1618405
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F ω","snippet":"In the limit, we can define system"},"resolution":"not_attempted"}}]
modifiedF ω allows arbitrary-order type functionsdbc8555f9bd8
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F ω","snippet":"F ω is the system which allows functions from types to types where the argument (and result) may be of any order"},"resolution":"not_attempted"}}]
modifiedF ω lacks dependent types106f28e36b42
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F ω","snippet":"System F ω does not permit mappings from values to types"},"resolution":"not_attempted"}}]
modifiedSystem F<: (F-sub)aa16fb7177ee
FieldFrom #5851To #5852
links—[]
unlinked—[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=System_F&oldid=1353196841","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"System F <:","snippet":"is an extension of system F with subtyping"},"resolution":"not_attempted"}}]