Revision #5851 → #5852 · back to history
modifiedSystem F (typed lambda calculus with universal quantification)2456fcb067ab
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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
| Field | From #5851 | To #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"}}] |