WikiLean Articles · Brain · Contribute · About

Diff — Simply typed lambda calculus

Revision #5752 → #6142 · back to history

modifiedSimply typed lambda calculus (STLC)382887623d19
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"is a typed interpretation of the lambda calculus with only one type constructor"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"is a typed interpretation of the lambda calculus with only one type constructor"},"resolution":"not_attempted"}}]
modifiedSimple type (extensions: products, coproducts, System T, PCF)b48209d32b25
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"The term simple type is also used to refer to extensions of the simply typed lambda calculus"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"The term simple type is also used to refer to extensions of the simply typed lambda calculus"},"resolution":"not_attempted"}}]
modifiedChurch's base types (o and ι)a117834ff28c
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"Church used only two base types"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"Church used only two base types"},"resolution":"not_attempted"}}]
modifiedFunction type37df5d10aef9
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"refers to the type of functions that, given an input of type"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"refers to the type of functions that, given an input of type"},"resolution":"not_attempted"}}]
modifiedSyntax of types (grammar)6c9b9947a949
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"To define the types, a set of base types"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"To define the types, a set of base types"},"resolution":"not_attempted"}}]
modifiedExample: infinite set of generated typescce068486fd9
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"generates an infinite set of types starting with"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"generates an infinite set of types starting with"},"resolution":"not_attempted"}}]
modifiedTerm constants for base types001d08fef732
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"A set of term constants is also fixed for the base types."},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"A set of term constants is also fixed for the base types."},"resolution":"not_attempted"}}]
modifiedTerm syntax (BNF)71306120176f
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"The syntax of the simply typed lambda calculus is essentially that of the lambda calculus itself."},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"The syntax of the simply typed lambda calculus is essentially that of the lambda calculus itself."},"resolution":"not_attempted"}}]
modifiedBound variable and closed term56ba1f4140d8
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"is bound if it is inside of an abstraction binding"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Syntax","snippet":"is bound if it is inside of an abstraction binding"},"resolution":"not_attempted"}}]
modifiedTyping context and typing assumptionac8a7e59681c
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"To define the set of well-typed lambda terms of a given type, one defines a typing relation between terms and types."},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"To define the set of well-typed lambda terms of a given type, one defines a typing relation between terms and types."},"resolution":"not_attempted"}}]
modifiedTyping relation, judgment, and derivation1628c7e21281
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"Instances of the typing relation are called typing judgments"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"Instances of the typing relation are called typing judgments"},"resolution":"not_attempted"}}]
modifiedTyping rules (Var, Const, Abs, App)7a67a60aabcb
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"in the context, then"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"in the context, then"},"resolution":"not_attempted"}}]
modifiedI, K, S combinators as closed terms493236d288c4
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"Examples of closed terms, i.e. terms typable in the empty context, are"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"Examples of closed terms, i.e. terms typable in the empty context, are"},"resolution":"not_attempted"}}]
modifiedOrder of a type1f398d8a3d45
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"the order of a type measures the depth of the most left-nested arrow"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Typing rules","snippet":"the order of a type measures the depth of the most left-nested arrow"},"resolution":"not_attempted"}}]
modifiedIntrinsic semanticsc45b1f5f17c1
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intrinsic vs. extrinsic interpretations","snippet":"An intrinsic semantics only assigns meaning to well-typed terms"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intrinsic vs. extrinsic interpretations","snippet":"An intrinsic semantics only assigns meaning to well-typed terms"},"resolution":"not_attempted"}}]
modifiedExample: identity term on integers vs Booleans8e7f87e083eb
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intrinsic vs. extrinsic interpretations","snippet":"For example, the identity term"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intrinsic vs. extrinsic interpretations","snippet":"For example, the identity term"},"resolution":"not_attempted"}}]
modifiedExtrinsic semantics730923b612a3
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intrinsic vs. extrinsic interpretations","snippet":"an extrinsic semantics assigns meaning to terms regardless of typing"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intrinsic vs. extrinsic interpretations","snippet":"an extrinsic semantics assigns meaning to terms regardless of typing"},"resolution":"not_attempted"}}]
modifiedEquational theory of STLC (βη-equivalence)d0796d17c1b8
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Equational theory","snippet":"The simply typed lambda calculus (STLC) has the same equational theory of βη-equivalence as untyped lambda calculus"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Equational theory","snippet":"The simply typed lambda calculus (STLC) has the same equational theory of βη-equivalence as untyped lambda calculus"},"resolution":"not_attempted"}}]
modifiedBeta reduction rulece8ed690f042
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Equational theory","snippet":"The equation for beta reduction"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Equational theory","snippet":"The equation for beta reduction"},"resolution":"not_attempted"}}]
modifiedEta reduction rule19e1e6185e24
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Equational theory","snippet":"the equation for eta reduction"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Equational theory","snippet":"the equation for eta reduction"},"resolution":"not_attempted"}}]
modifiedType safety and termination of evaluation strategiesd1818eafaeb0
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Operational semantics","snippet":"type safety is a fundamental property of all of these evaluation strategies"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Operational semantics","snippet":"type safety is a fundamental property of all of these evaluation strategies"},"resolution":"not_attempted"}}]
modifiedLambek's STLC–CCC correspondenceeb0636137a94
FieldFrom #5752To #6142
links[{"id":"eb0636137a94:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"is the internal language of Cartesian closed categories"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.CartesianMonoidalCategory","module":"Mathlib.CategoryTheory.Monoidal.Cartesian.Basic"}}]}}][{"id":"eb0636137a94:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"is the internal language of Cartesian closed categories"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.CartesianMonoidalCategory","module":"Mathlib.CategoryTheory.Monoidal.Cartesian.Basic"}}]}}]
modifiedPairing, projection, and unit term rules375aea8154d7
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"There are typing rules for pairing"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"There are typing rules for pairing"},"resolution":"not_attempted"}}]
modifiedUnit term reduces to nil5e17cd758236
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"This last is read as"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"This last is read as"},"resolution":"not_attempted"}}]
modifiedSTLC as a category (objects=types, morphisms=term classes)275c12c545cb
FieldFrom #5752To #6142
links[{"id":"275c12c545cb:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"The above can then be turned into a category by taking the types as the objects"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}][{"id":"275c12c545cb:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"The above can then be turned into a category by taking the types as the objects"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}]
modifiedFunctorial extension to language homomorphisms71721b52b943
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"This correspondence can be extended to include"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"This correspondence can be extended to include"},"resolution":"not_attempted"}}]
modifiedExtension to closed symmetric monoidal categories (linear types)e29de638d361
FieldFrom #5752To #6142
links[{"id":"e29de638d361:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"Part of this correspondence can be extended to closed symmetric monoidal categories"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}][{"id":"e29de638d361:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Categorical semantics","snippet":"Part of this correspondence can be extended to closed symmetric monoidal categories"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}]
modifiedCurry–Howard correspondence for STLCc95e675f040c
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Proof-theoretic semantics","snippet":"via the Curry–Howard isomorphism"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Proof-theoretic semantics","snippet":"via the Curry–Howard isomorphism"},"resolution":"not_attempted"}}]
modifiedHindley–Milner inference correctness5dc5f6f262e6
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Type Erasure","snippet":"The inference algorithm is terminating, sound, and complete"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Type Erasure","snippet":"The inference algorithm is terminating, sound, and complete"},"resolution":"not_attempted"}}]
modifiedBidirectional checking and synthesis judgmentsacb33fbac1df
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"Another alternative presentation of simply typed lambda calculus is based on bidirectional type checking"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"Another alternative presentation of simply typed lambda calculus is based on bidirectional type checking"},"resolution":"not_attempted"}}]
modifiedBidirectional typing rules [1]–[4]11458d9df855
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"Observe that rules [1]–[4] are nearly identical to rules (1)–(4) above"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"Observe that rules [1]–[4] are nearly identical to rules (1)–(4) above"},"resolution":"not_attempted"}}]
modifiedBidirectional coercion rules [5]–[6]becb35172f54
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"Finally, we explain rules [5] and [6] as follows"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"Finally, we explain rules [5] and [6] as follows"},"resolution":"not_attempted"}}]
modifiedCompleteness of bidirectional system with minimal annotationsd28f175717f8
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"any well-typed but unannotated term can be checked in the bidirectional system"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Bidirectional Type Checking","snippet":"any well-typed but unannotated term can be checked in the bidirectional system"},"resolution":"not_attempted"}}]
modifiedStrong normalization of STLCb2aceb44718e
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"General observations","snippet":"the simply typed lambda calculus is strongly normalizing"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"General observations","snippet":"the simply typed lambda calculus is strongly normalizing"},"resolution":"not_attempted"}}]
modifiedSTLC is not Turing complete06a6dc0a2e02
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"General observations","snippet":"the simply typed lambda calculus is not Turing complete"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"General observations","snippet":"the simply typed lambda calculus is not Turing complete"},"resolution":"not_attempted"}}]
modifiedTait's strong normalization theorem (1967)59443c230e1e
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Tait showed in 1967 that"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Tait showed in 1967 that"},"resolution":"not_attempted"}}]
modifiedDecidability of βη-equivalence (corollary)25f70e437837
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"As a corollary"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"As a corollary"},"resolution":"not_attempted"}}]
modifiedStatman's non-elementary complexity result (1979)51abb7d7a981
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Statman showed in 1979 that the normalisation problem is non-elementary"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Statman showed in 1979 that the normalisation problem is non-elementary"},"resolution":"not_attempted"}}]
modifiedMairson's simplified proofab2d2c3c8be1
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"a proof that was later simplified by Mairson"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"a proof that was later simplified by Mairson"},"resolution":"not_attempted"}}]
modifiedTOWER-completeness of the normalization probleme508b63b54a8
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"it is complete in the complexity class called TOWER"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"it is complete in the complexity class called TOWER"},"resolution":"not_attempted"}}]
modifiedBerger–Schwichtenberg normalization by evaluation (1991)352829306d2b
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"A purely semantic normalisation proof"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"A purely semantic normalisation proof"},"resolution":"not_attempted"}}]
modifiedUndecidability of unification for βη-equivalence826e55be5180
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"The unification problem for"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"The unification problem for"},"resolution":"not_attempted"}}]
modifiedHuet's 3rd order unification undecidability (1973)9afc9cfed43d
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Huet showed in 1973 that 3rd order unification is undecidable"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Huet showed in 1973 that 3rd order unification is undecidable"},"resolution":"not_attempted"}}]
modifiedGoldfarb's 2nd order unification undecidability (1981)de68eca7cb8b
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"by showing that 2nd order unification is already undecidable"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"by showing that 2nd order unification is already undecidable"},"resolution":"not_attempted"}}]
modifiedStirling's decidability of higher-order matching (2006/2009)bd3c3a6b6e45
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"A proof that higher order matching"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"A proof that higher order matching"},"resolution":"not_attempted"}}]
modifiedChurch numeralsfddbd8201217
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"We can encode natural numbers by terms of the type"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"We can encode natural numbers by terms of the type"},"resolution":"not_attempted"}}]
modifiedSchwichtenberg's representable-functions theorem (1975)96a01c03b2df
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Schwichtenberg showed in 1975 that in"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Schwichtenberg showed in 1975 that in"},"resolution":"not_attempted"}}]
modifiedFull set-theoretic model of STLC66679b7be1e5
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"is given by interpreting base types as sets and function types by the set-theoretic function space"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"is given by interpreting base types as sets and function types by the set-theoretic function space"},"resolution":"not_attempted"}}]
modifiedFriedman's completeness theorem (1975)b35f51cbf6e7
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Friedman showed in 1975 that this interpretation is complete for"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Friedman showed in 1975 that this interpretation is complete for"},"resolution":"not_attempted"}}]
modifiedStatman's Typical Ambiguity Theorem (1983)c5e5d0be9f8b
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Statman showed in 1983 that"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Statman showed in 1983 that"},"resolution":"not_attempted"}}]
modifiedFinite model property (corollary)170ed3cc7d44
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"A corollary of this is that the finite model property holds"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"A corollary of this is that the finite model property holds"},"resolution":"not_attempted"}}]
modifiedPlotkin's logical relations (1973)f36409cb436b
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Plotkin introduced logical relations in 1973 to characterize the elements of a model that are definable by lambda terms"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Plotkin introduced logical relations in 1973 to characterize the elements of a model that are definable by lambda terms"},"resolution":"not_attempted"}}]
modifiedJung–Tiuryn characterization theorem (1993)d2109cf99930
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"In 1993 Jung and Tiuryn showed that a general form of logical relation"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"In 1993 Jung and Tiuryn showed that a general form of logical relation"},"resolution":"not_attempted"}}]
modifiedPlotkin–Statman conjecturea00f3b059f09
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Plotkin and Statman conjectured that it is decidable whether a given element of a model generated from finite sets is definable by a lambda term"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"Plotkin and Statman conjectured that it is decidable whether a given element of a model generated from finite sets is definable by a lambda term"},"resolution":"not_attempted"}}]
modifiedLoader's refutation of the Plotkin–Statman conjecture (2001)d8b155c6bcc3
FieldFrom #5752To #6142
unlinked[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1382031389","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"The conjecture was shown to be false by Loader in 2001"},"resolution":"not_attempted"}}][{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Simply_typed_lambda_calculus&oldid=1383125970","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Important results","snippet":"The conjecture was shown to be false by Loader in 2001"},"resolution":"not_attempted"}}]