{"history":[{"id":"66f89064-765a-4fad-af97-4114fc336165","wordChanged":"(\\lambda^\\to),","newWord":":::summary\n:::\n\n# \nThe **simply typed lambda calculus** Banana a form\nof [type theory](https://bliptext.com/articles/type-theory), is a [typed interpretation](https://bliptext.com/articles/typed-lambda-calculus) of the [lambda calculus](https://bliptext.com/articles/lambda-calculus) with only one [type constructor](https://bliptext.com/articles/type-constructor) (\\to) that builds [function types](https://bliptext.com/articles/function-type).\nIt is the canonical and simplest example of a typed lambda calculus.\nThe simply typed lambda calculus was originally introduced by [Alonzo Church](https://bliptext.com/articles/alonzo-church) in 1940 as an attempt to avoid paradoxical use of the [untyped lambda calculus](https://bliptext.com/articles/untyped-lambda-calculus).\nThe term simple type is also used to refer to extensions of the simply typed lambda [calculus](https://bliptext.com/articles/calculus) with constructs such as [products](https://bliptext.com/articles/cartesian-product), co[products](https://bliptext.com/articles/cartesian-product) or [natural numbers](https://bliptext.com/articles/natural-number) ([System T](https://bliptext.com/articles/dialectica-interpretation)) or even full [recursion](https://bliptext.com/articles/recursion) (like [PCF](https://bliptext.com/articles/programming-language-for-computable-functions)).\nIn contrast, systems that introduce [polymorphic types](https://bliptext.com/articles/parametric-polymorphism) (like [System F](https://bliptext.com/articles/system-f)) or [dependent types](https://bliptext.com/articles/dependent-type) (like the [Logical Framework](https://bliptext.com/articles/lf-logical-framework)) are not considered simply typed.\nThe simple types, except for full recursion, are still considered simple because the [Church encodings](https://bliptext.com/articles/church-encoding) of such structures can be done using only \\to and suitable type variables, while polymorphism and dependency cannot.\n\n# Syntax\nIn the 1930s Alonzo Church sought to use the logistic method: his [lambda calculus](https://bliptext.com/articles/lambda-calculus), as a formal language based on symbolic expressions, consisted of a denumerably infinite series of axioms and variables, but also a finite set of primitive symbols, denoting abstraction and scope, as well as four constants: negation, disjunction, universal quantification, and selection respectively; and also, a finite set of rules I to VI.\nThis finite set of rules included rule V [modus ponens](https://bliptext.com/articles/modus-ponens) as well as IV and VI for substitution and generalization respectively.\nRules I to III are known as alpha, beta, and eta conversion in the lambda calculus.\nChurch sought to use English only as a syntax language (that is, a metamathematical language) for describing symbolic expressions with no interpretations.\nIn 1940 Church settled on a subscript notation for denoting the type in a symbolic expression.\nIn his presentation, Church used only two base types: o for \"the type of propositions\" and \\iota for \"the type of individuals\".\nThe type o has no term constants, whereas \\iota has one term constant.\nFrequently the calculus with only one base type, usually o, is considered.\nThe Greek letter subscripts, etc. denote type variables; the parenthesized subscripted denotes the function type.\nChurch 1940 p.58 used 'arrow or \\to' to denote stands for, or is an abbreviation for.\nBy the 1970s stand-alone arrow notation was in use; for example in this article non-subscripted symbols \\sigma and \\tau can range over types.\nThe infinite number of axioms were then seen to be a consequence of applying rules I to VI to the types (see [Peano axioms](https://bliptext.com/articles/peano-axioms)).\nInformally, the function type refers to the type of functions that, given an input of type \\sigma, produce an output of type \\tau.\nBy convention, \\to associates to the right: is read as.\nTo define the types, a [set](https://bliptext.com/articles/set-mathematics) of base types, B, must first be defined.\nThese are sometimes called atomic types or type constants.\nWith this fixed, the syntax of types is:\nFor example,, generates an infinite set of types starting with a, b, a \\to a, a \\to b, b \\to b, b \\to a, , ..., , ...\nA set of term constants is also fixed for the base types.\nFor example, it might be assumed that one of the base types is nat, and its term constants could be the natural numbers.\nThe syntax of the simply typed lambda calculus is essentially that of the lambda calculus itself.\nThe term denotes that the variable x is of type \\tau.\nThe term syntax, in [Backus–Naur form](https://bliptext.com/articles/backus-naur-form), is variable reference, abstractions, application, or constant:\nwhere c is a term constant.\nA variable reference x is bound if it is inside of an abstraction binding x. A term is closed if there are no unbound variables.\nIn comparison, the syntax of untyped lambda calculus has no such typing or term constants:\nWhereas in typed lambda calculus every abstraction (i.e. function) must specify the type of its argument.\n\n# Typing rules\nTo define the set of well-typed lambda terms of a given type, one defines a typing relation between terms and types.\nFirst, one introduces typing contexts, or [typing environments](https://bliptext.com/articles/typing-environment), which are sets of typing assumptions.\nA typing assumption has the form, meaning variable x has type \\sigma.\nThe typing relation indicates that e is a term of type \\sigma in context \\Gamma.\nIn this case e is said to be well-typed (having type \\sigma).\nInstances of the typing relation are called typing judgments.\nThe validity of a typing judgment is shown by providing a typing derivation, constructed using [typing rules](https://bliptext.com/articles/typing-rule) (wherein the premises above the line allow us to derive the conclusion below the line).\nSimply typed lambda calculus uses these rules:\nIn words,\nExamples of closed terms, i.e. terms typable in the empty context, are:\nThese are the typed lambda calculus representations of the basic combinators of [combinatory logic](https://bliptext.com/articles/combinatory-logic).\nEach type \\tau is assigned an order, a number o(\\tau).\nFor base types, o(T)=0; for function types,.\nThat is, the order of a type measures the depth of the most left-nested arrow.\nHence:\n\n# Semantics\n\n## Intrinsic vs. extrinsic interpretations\nBroadly speaking, there are two different ways of assigning meaning to the simply typed lambda calculus, as to typed languages more generally, variously called intrinsic vs. extrinsic, ontological vs. semantical, or Church-style vs. Curry-style.\nAn intrinsic semantics only assigns meaning to well-typed terms, or more precisely, assigns meaning directly to typing derivations.\nThis has the effect that terms differing only by type annotations can nonetheless be assigned different meanings.\nFor example, the identity term on [integers](https://bliptext.com/articles/integer) and the identity term on [booleans](https://bliptext.com/articles/boolean-data-type) may mean different things.\n(The classic intended interpretations are the identity function on integers and the identity function on boolean values.)\nIn contrast, an extrinsic semantics assigns meaning to terms regardless of typing, as they would be interpreted in an untyped language.\nIn this view, and mean the same thing (i.e., the same thing as ).\nThe distinction between intrinsic and extrinsic semantics is sometimes associated with the presence or absence of annotations on lambda abstractions, but strictly speaking this usage is imprecise.\nIt is possible to define an extrinsic semantics on annotated terms simply by ignoring the types (i.e., through [type erasure](https://bliptext.com/articles/type-erasure)), as it is possible to give an intrinsic semantics on unannotated terms when the types can be deduced from context (i.e., through [type inference](https://bliptext.com/articles/type-inference)).\nThe essential difference between intrinsic and extrinsic approaches is just whether the typing rules are viewed as defining the language, or as a formalism for verifying properties of a more primitive underlying language.\nMost of the different semantic interpretations discussed below can be seen through either an intrinsic or extrinsic perspective.\n\n## Equational theory\nThe simply typed lambda calculus (STLC) has the same [equational theory](https://bliptext.com/articles/equational-theory) of βη-equivalence as [untyped lambda calculus](https://bliptext.com/articles/untyped-lambda-calculus), but subject to type restrictions.\nThe equation for [beta reduction](https://bliptext.com/articles/beta-reduction)\nholds in context \\Gamma whenever and, while the equation for [eta reduction](https://bliptext.com/articles/eta-reduction)\nholds whenever and x does not appear free in t. The advantage of typed lambda calculus is that STLC allows potentially nonterminating computations to be cut short (that is, reduced).\n\n## Operational semantics\nLikewise, the [operational semantics](https://bliptext.com/articles/operational-semantics) of simply typed lambda calculus can be fixed as for the untyped lambda calculus, using [call by name](https://bliptext.com/articles/call-by-name), [call by value](https://bliptext.com/articles/call-by-value), or other [evaluation strategies](https://bliptext.com/articles/evaluation-strategy).\nAs for any typed language, [type safety](https://bliptext.com/articles/type-safety) is a fundamental property of all of these evaluation strategies.\nAdditionally, the [strong normalization](https://bliptext.com/articles/strong-normalization) property [described below](https://bliptext.com/articles/simply-typed-lambda-calculus) implies that any evaluation strategy will terminate on all simply typed terms.\n\n## Categorical semantics\nThe simply typed lambda calculus enriched with product types, pairing and projection operators (with \\beta\\eta-equivalence) is the [internal language](https://bliptext.com/articles/internal-language) of [Cartesian closed categories](https://bliptext.com/articles/cartesian-closed-categories) (CCCs), as was first observed by [Joachim Lambek](https://bliptext.com/articles/joachim-lambek).\nGiven any CCC, the basic types of the corresponding lambda calculus are the [objects](https://bliptext.com/articles/object-category-theory), and the terms are the [morphisms](https://bliptext.com/articles/morphism).\nConversely, the simply typed lambda calculus with product types and pairing operators over a collection of base types and given terms forms a CCC whose objects are the types, and morphisms are equivalence classes of terms.\nThere are [typing rules](https://bliptext.com/articles/typing-rule) for pairing, projection, and a unit term.\nGiven two terms and, the term (s,t) has type.\nLikewise, if one has a term, then there are terms and where the \\pi_i correspond to the projections of the Cartesian product.\nThe unit term, of type 1, written as and vocalized as 'nil', is the [final object](https://bliptext.com/articles/final-object).\nThe equational theory is extended likewise, so that one has\nThis last is read as \"if t has type 1, then it reduces to nil\".\nThe above can then be turned into a category by taking the types as the [objects](https://bliptext.com/articles/object-category-theory).\nThe [morphisms](https://bliptext.com/articles/morphism) are [equivalence classes](https://bliptext.com/articles/equivalence-class) of pairs where x is a variable (of type \\sigma) and t is a term (of type \\tau), having no free variables in it, except for (optionally) x.\nThe set of terms in the language is the closure of this set of terms under the operations of abstraction and [application](https://bliptext.com/articles/apply).\nThis correspondence can be extended to include \"language homomorphisms\" and [functors](https://bliptext.com/articles/functor) between the category of Cartesian closed categories, and the category of simply typed lambda theories.\nPart of this correspondence can be extended to [closed symmetric monoidal categories](https://bliptext.com/articles/closed-monoidal-category) by using a [linear type system](https://bliptext.com/articles/linear-type-system).\n\n## Proof-theoretic semantics\nThe simply typed lambda calculus is closely related to the implicational fragment of propositional [intuitionistic logic](https://bliptext.com/articles/intuitionistic-logic), i.e., the [implicational propositional calculus](https://bliptext.com/articles/implicational-propositional-calculus), via the [Curry–Howard isomorphism](https://bliptext.com/articles/curry-howard-isomorphism): terms correspond precisely to proofs in [natural deduction](https://bliptext.com/articles/natural-deduction), and [inhabited types](https://bliptext.com/articles/type-inhabitation) are exactly the [tautologies](https://bliptext.com/articles/tautology-logic) of this logic.\nFrom his logistic method Church 1940 p.58 laid out an [axiom schema](https://bliptext.com/articles/axiom-schema), p. 60, which Henkin 1949 filled in with type domains (e.g. the natural numbers, the real numbers, etc.).\nHenkin 1996 p. 146 described how Church's logistic method could seek to provide a foundation for mathematics (Peano arithmetic and real analysis), via [model theory](https://bliptext.com/articles/model-theory).\n\n# Alternative syntaxes\nThe presentation given above is not the only way of defining the syntax of the simply typed lambda calculus.\nOne alternative is to remove type annotations entirely (so that the syntax is identical to the untyped lambda calculus), while ensuring that terms are well-typed via [Hindley–Milner type inference](https://bliptext.com/articles/hindley-milner-type-inference).\nThe inference algorithm is terminating, sound, and complete: whenever a term is typable, the algorithm computes its type.\nMore precisely, it computes the term's [principal type](https://bliptext.com/articles/principal-type), since often an unannotated term (such as ) may have more than one type (,, etc., which are all instances of the [principal type](https://bliptext.com/articles/principal-type) ).\nAnother alternative presentation of simply typed lambda calculus is based on **bidirectional type checking**, which requires more type annotations than Hindley–Milner inference but is easier to describe.\nThe [type system](https://bliptext.com/articles/type-system) is divided into two judgments, representing both checking and synthesis, written and respectively.\nOperationally, the three components \\Gamma, e, and \\tau are all inputs to the checking judgment, whereas the synthesis judgment only takes \\Gamma and e as inputs, producing the type \\tau as output.\nThese judgments are derived via the following rules:\nObserve that rules [1]–[4] are nearly identical to rules (1)–(4) [above](https://bliptext.com/articles/), except for the careful choice of checking or synthesis judgments.\nThese choices can be explained like so:\nObserve that the rules for synthesis are read top-to-bottom, whereas the rules for checking are read bottom-to-top.\nNote in particular that we do **not** need any an**not**ation on the lambda abstraction in rule [3], because the type of the bound variable can be deduced from the type at which we check the function.\nFinally, we explain rules [5] and [6] as follows:\n

To check that e has type \\tau, it suffices to synthesize type \\tau.

If e checks against type \\tau, then the explicitly annotated term synthesizes \\tau.\n

\n\nBecause of these last two rules coercing between synthesis and checking, it is easy to see that any well-typed but unannotated term can be checked in the bidirectional system, so long as we insert \"enough\" type annotations.\nAnd in fact, annotations are needed only at β-redexes.\n\n# General observations\nGiven the standard semantics, the simply typed lambda calculus is [strongly normalizing](https://bliptext.com/articles/normalization-property-lambda-calculus): every sequence of reductions eventually terminates.\nThis is because recursion is not allowed by the typing rules: it is impossible to find types for [fixed-point combinators](https://bliptext.com/articles/fixed-point-combinator) and the looping term.\nRecursion can be added to the language by either having a special operator of type or adding general [recursive types](https://bliptext.com/articles/recursive-type), though both eliminate strong normalization.\nUnlike the untyped lambda calculus, the simply typed lambda calculus is not [Turing complete](https://bliptext.com/articles/turing-complete).\nAll programs in the simply typed lambda calculus halt.\nFor the untyped lambda calculus, there are programs that do not halt, and moreover there is no general decision procedure that can determine whether a program halts.\n\n# Important results","wordIndex":3,"createdAt":"2025-03-03T00:47:24.198Z","user":{"id":"WitEc2DUAyXQ0fv4VksYEV2XeyyYkFxJ","name":"Verchot Jacob","image":"https://lh3.googleusercontent.com/a/ACg8ocL8PKPiPB28CAAEkSAmn5K6Kai1ek4lJLoI7hjotf9d1GD4Hw=s96-c"}}],"article":{"id":"5f7c034c-ba71-4741-9875-41a87efdac88","title":"Simply typed lambda calculus","slug":"simply-typed-lambda-calculus","content":":::summary\n:::\n\n# \nThe **simply typed lambda calculus** Banana a form\nof [type theory](https://bliptext.com/articles/type-theory), is a [typed interpretation](https://bliptext.com/articles/typed-lambda-calculus) of the [lambda calculus](https://bliptext.com/articles/lambda-calculus) with only one [type constructor](https://bliptext.com/articles/type-constructor) (\\to) that builds [function types](https://bliptext.com/articles/function-type).\nIt is the canonical and simplest example of a typed lambda calculus.\nThe simply typed lambda calculus was originally introduced by [Alonzo Church](https://bliptext.com/articles/alonzo-church) in 1940 as an attempt to avoid paradoxical use of the [untyped lambda calculus](https://bliptext.com/articles/untyped-lambda-calculus).\nThe term simple type is also used to refer to extensions of the simply typed lambda [calculus](https://bliptext.com/articles/calculus) with constructs such as [products](https://bliptext.com/articles/cartesian-product), co[products](https://bliptext.com/articles/cartesian-product) or [natural numbers](https://bliptext.com/articles/natural-number) ([System T](https://bliptext.com/articles/dialectica-interpretation)) or even full [recursion](https://bliptext.com/articles/recursion) (like [PCF](https://bliptext.com/articles/programming-language-for-computable-functions)).\nIn contrast, systems that introduce [polymorphic types](https://bliptext.com/articles/parametric-polymorphism) (like [System F](https://bliptext.com/articles/system-f)) or [dependent types](https://bliptext.com/articles/dependent-type) (like the [Logical Framework](https://bliptext.com/articles/lf-logical-framework)) are not considered simply typed.\nThe simple types, except for full recursion, are still considered simple because the [Church encodings](https://bliptext.com/articles/church-encoding) of such structures can be done using only \\to and suitable type variables, while polymorphism and dependency cannot.\n\n# Syntax\nIn the 1930s Alonzo Church sought to use the logistic method: his [lambda calculus](https://bliptext.com/articles/lambda-calculus), as a formal language based on symbolic expressions, consisted of a denumerably infinite series of axioms and variables, but also a finite set of primitive symbols, denoting abstraction and scope, as well as four constants: negation, disjunction, universal quantification, and selection respectively; and also, a finite set of rules I to VI.\nThis finite set of rules included rule V [modus ponens](https://bliptext.com/articles/modus-ponens) as well as IV and VI for substitution and generalization respectively.\nRules I to III are known as alpha, beta, and eta conversion in the lambda calculus.\nChurch sought to use English only as a syntax language (that is, a metamathematical language) for describing symbolic expressions with no interpretations.\nIn 1940 Church settled on a subscript notation for denoting the type in a symbolic expression.\nIn his presentation, Church used only two base types: o for \"the type of propositions\" and \\iota for \"the type of individuals\".\nThe type o has no term constants, whereas \\iota has one term constant.\nFrequently the calculus with only one base type, usually o, is considered.\nThe Greek letter subscripts, etc. denote type variables; the parenthesized subscripted denotes the function type.\nChurch 1940 p.58 used 'arrow or \\to' to denote stands for, or is an abbreviation for.\nBy the 1970s stand-alone arrow notation was in use; for example in this article non-subscripted symbols \\sigma and \\tau can range over types.\nThe infinite number of axioms were then seen to be a consequence of applying rules I to VI to the types (see [Peano axioms](https://bliptext.com/articles/peano-axioms)).\nInformally, the function type refers to the type of functions that, given an input of type \\sigma, produce an output of type \\tau.\nBy convention, \\to associates to the right: is read as.\nTo define the types, a [set](https://bliptext.com/articles/set-mathematics) of base types, B, must first be defined.\nThese are sometimes called atomic types or type constants.\nWith this fixed, the syntax of types is:\nFor example,, generates an infinite set of types starting with a, b, a \\to a, a \\to b, b \\to b, b \\to a, , ..., , ...\nA set of term constants is also fixed for the base types.\nFor example, it might be assumed that one of the base types is nat, and its term constants could be the natural numbers.\nThe syntax of the simply typed lambda calculus is essentially that of the lambda calculus itself.\nThe term denotes that the variable x is of type \\tau.\nThe term syntax, in [Backus–Naur form](https://bliptext.com/articles/backus-naur-form), is variable reference, abstractions, application, or constant:\nwhere c is a term constant.\nA variable reference x is bound if it is inside of an abstraction binding x. A term is closed if there are no unbound variables.\nIn comparison, the syntax of untyped lambda calculus has no such typing or term constants:\nWhereas in typed lambda calculus every abstraction (i.e. function) must specify the type of its argument.\n\n# Typing rules\nTo define the set of well-typed lambda terms of a given type, one defines a typing relation between terms and types.\nFirst, one introduces typing contexts, or [typing environments](https://bliptext.com/articles/typing-environment), which are sets of typing assumptions.\nA typing assumption has the form, meaning variable x has type \\sigma.\nThe typing relation indicates that e is a term of type \\sigma in context \\Gamma.\nIn this case e is said to be well-typed (having type \\sigma).\nInstances of the typing relation are called typing judgments.\nThe validity of a typing judgment is shown by providing a typing derivation, constructed using [typing rules](https://bliptext.com/articles/typing-rule) (wherein the premises above the line allow us to derive the conclusion below the line).\nSimply typed lambda calculus uses these rules:\nIn words,\nExamples of closed terms, i.e. terms typable in the empty context, are:\nThese are the typed lambda calculus representations of the basic combinators of [combinatory logic](https://bliptext.com/articles/combinatory-logic).\nEach type \\tau is assigned an order, a number o(\\tau).\nFor base types, o(T)=0; for function types,.\nThat is, the order of a type measures the depth of the most left-nested arrow.\nHence:\n\n# Semantics\n\n## Intrinsic vs. extrinsic interpretations\nBroadly speaking, there are two different ways of assigning meaning to the simply typed lambda calculus, as to typed languages more generally, variously called intrinsic vs. extrinsic, ontological vs. semantical, or Church-style vs. Curry-style.\nAn intrinsic semantics only assigns meaning to well-typed terms, or more precisely, assigns meaning directly to typing derivations.\nThis has the effect that terms differing only by type annotations can nonetheless be assigned different meanings.\nFor example, the identity term on [integers](https://bliptext.com/articles/integer) and the identity term on [booleans](https://bliptext.com/articles/boolean-data-type) may mean different things.\n(The classic intended interpretations are the identity function on integers and the identity function on boolean values.)\nIn contrast, an extrinsic semantics assigns meaning to terms regardless of typing, as they would be interpreted in an untyped language.\nIn this view, and mean the same thing (i.e., the same thing as ).\nThe distinction between intrinsic and extrinsic semantics is sometimes associated with the presence or absence of annotations on lambda abstractions, but strictly speaking this usage is imprecise.\nIt is possible to define an extrinsic semantics on annotated terms simply by ignoring the types (i.e., through [type erasure](https://bliptext.com/articles/type-erasure)), as it is possible to give an intrinsic semantics on unannotated terms when the types can be deduced from context (i.e., through [type inference](https://bliptext.com/articles/type-inference)).\nThe essential difference between intrinsic and extrinsic approaches is just whether the typing rules are viewed as defining the language, or as a formalism for verifying properties of a more primitive underlying language.\nMost of the different semantic interpretations discussed below can be seen through either an intrinsic or extrinsic perspective.\n\n## Equational theory\nThe simply typed lambda calculus (STLC) has the same [equational theory](https://bliptext.com/articles/equational-theory) of βη-equivalence as [untyped lambda calculus](https://bliptext.com/articles/untyped-lambda-calculus), but subject to type restrictions.\nThe equation for [beta reduction](https://bliptext.com/articles/beta-reduction)\nholds in context \\Gamma whenever and, while the equation for [eta reduction](https://bliptext.com/articles/eta-reduction)\nholds whenever and x does not appear free in t. The advantage of typed lambda calculus is that STLC allows potentially nonterminating computations to be cut short (that is, reduced).\n\n## Operational semantics\nLikewise, the [operational semantics](https://bliptext.com/articles/operational-semantics) of simply typed lambda calculus can be fixed as for the untyped lambda calculus, using [call by name](https://bliptext.com/articles/call-by-name), [call by value](https://bliptext.com/articles/call-by-value), or other [evaluation strategies](https://bliptext.com/articles/evaluation-strategy).\nAs for any typed language, [type safety](https://bliptext.com/articles/type-safety) is a fundamental property of all of these evaluation strategies.\nAdditionally, the [strong normalization](https://bliptext.com/articles/strong-normalization) property [described below](https://bliptext.com/articles/simply-typed-lambda-calculus) implies that any evaluation strategy will terminate on all simply typed terms.\n\n## Categorical semantics\nThe simply typed lambda calculus enriched with product types, pairing and projection operators (with \\beta\\eta-equivalence) is the [internal language](https://bliptext.com/articles/internal-language) of [Cartesian closed categories](https://bliptext.com/articles/cartesian-closed-categories) (CCCs), as was first observed by [Joachim Lambek](https://bliptext.com/articles/joachim-lambek).\nGiven any CCC, the basic types of the corresponding lambda calculus are the [objects](https://bliptext.com/articles/object-category-theory), and the terms are the [morphisms](https://bliptext.com/articles/morphism).\nConversely, the simply typed lambda calculus with product types and pairing operators over a collection of base types and given terms forms a CCC whose objects are the types, and morphisms are equivalence classes of terms.\nThere are [typing rules](https://bliptext.com/articles/typing-rule) for pairing, projection, and a unit term.\nGiven two terms and, the term (s,t) has type.\nLikewise, if one has a term, then there are terms and where the \\pi_i correspond to the projections of the Cartesian product.\nThe unit term, of type 1, written as and vocalized as 'nil', is the [final object](https://bliptext.com/articles/final-object).\nThe equational theory is extended likewise, so that one has\nThis last is read as \"if t has type 1, then it reduces to nil\".\nThe above can then be turned into a category by taking the types as the [objects](https://bliptext.com/articles/object-category-theory).\nThe [morphisms](https://bliptext.com/articles/morphism) are [equivalence classes](https://bliptext.com/articles/equivalence-class) of pairs where x is a variable (of type \\sigma) and t is a term (of type \\tau), having no free variables in it, except for (optionally) x.\nThe set of terms in the language is the closure of this set of terms under the operations of abstraction and [application](https://bliptext.com/articles/apply).\nThis correspondence can be extended to include \"language homomorphisms\" and [functors](https://bliptext.com/articles/functor) between the category of Cartesian closed categories, and the category of simply typed lambda theories.\nPart of this correspondence can be extended to [closed symmetric monoidal categories](https://bliptext.com/articles/closed-monoidal-category) by using a [linear type system](https://bliptext.com/articles/linear-type-system).\n\n## Proof-theoretic semantics\nThe simply typed lambda calculus is closely related to the implicational fragment of propositional [intuitionistic logic](https://bliptext.com/articles/intuitionistic-logic), i.e., the [implicational propositional calculus](https://bliptext.com/articles/implicational-propositional-calculus), via the [Curry–Howard isomorphism](https://bliptext.com/articles/curry-howard-isomorphism): terms correspond precisely to proofs in [natural deduction](https://bliptext.com/articles/natural-deduction), and [inhabited types](https://bliptext.com/articles/type-inhabitation) are exactly the [tautologies](https://bliptext.com/articles/tautology-logic) of this logic.\nFrom his logistic method Church 1940 p.58 laid out an [axiom schema](https://bliptext.com/articles/axiom-schema), p. 60, which Henkin 1949 filled in with type domains (e.g. the natural numbers, the real numbers, etc.).\nHenkin 1996 p. 146 described how Church's logistic method could seek to provide a foundation for mathematics (Peano arithmetic and real analysis), via [model theory](https://bliptext.com/articles/model-theory).\n\n# Alternative syntaxes\nThe presentation given above is not the only way of defining the syntax of the simply typed lambda calculus.\nOne alternative is to remove type annotations entirely (so that the syntax is identical to the untyped lambda calculus), while ensuring that terms are well-typed via [Hindley–Milner type inference](https://bliptext.com/articles/hindley-milner-type-inference).\nThe inference algorithm is terminating, sound, and complete: whenever a term is typable, the algorithm computes its type.\nMore precisely, it computes the term's [principal type](https://bliptext.com/articles/principal-type), since often an unannotated term (such as ) may have more than one type (,, etc., which are all instances of the [principal type](https://bliptext.com/articles/principal-type) ).\nAnother alternative presentation of simply typed lambda calculus is based on **bidirectional type checking**, which requires more type annotations than Hindley–Milner inference but is easier to describe.\nThe [type system](https://bliptext.com/articles/type-system) is divided into two judgments, representing both checking and synthesis, written and respectively.\nOperationally, the three components \\Gamma, e, and \\tau are all inputs to the checking judgment, whereas the synthesis judgment only takes \\Gamma and e as inputs, producing the type \\tau as output.\nThese judgments are derived via the following rules:\nObserve that rules [1]–[4] are nearly identical to rules (1)–(4) [above](https://bliptext.com/articles/), except for the careful choice of checking or synthesis judgments.\nThese choices can be explained like so:\nObserve that the rules for synthesis are read top-to-bottom, whereas the rules for checking are read bottom-to-top.\nNote in particular that we do **not** need any an**not**ation on the lambda abstraction in rule [3], because the type of the bound variable can be deduced from the type at which we check the function.\nFinally, we explain rules [5] and [6] as follows:\n

To check that e has type \\tau, it suffices to synthesize type \\tau.

If e checks against type \\tau, then the explicitly annotated term synthesizes \\tau.\n

\n\nBecause of these last two rules coercing between synthesis and checking, it is easy to see that any well-typed but unannotated term can be checked in the bidirectional system, so long as we insert \"enough\" type annotations.\nAnd in fact, annotations are needed only at β-redexes.\n\n# General observations\nGiven the standard semantics, the simply typed lambda calculus is [strongly normalizing](https://bliptext.com/articles/normalization-property-lambda-calculus): every sequence of reductions eventually terminates.\nThis is because recursion is not allowed by the typing rules: it is impossible to find types for [fixed-point combinators](https://bliptext.com/articles/fixed-point-combinator) and the looping term.\nRecursion can be added to the language by either having a special operator of type or adding general [recursive types](https://bliptext.com/articles/recursive-type), though both eliminate strong normalization.\nUnlike the untyped lambda calculus, the simply typed lambda calculus is not [Turing complete](https://bliptext.com/articles/turing-complete).\nAll programs in the simply typed lambda calculus halt.\nFor the untyped lambda calculus, there are programs that do not halt, and moreover there is no general decision procedure that can determine whether a program halts.\n\n# Important results","current_revision":"66f89064-765a-4fad-af97-4114fc336165","created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:41:31.939Z","updated_at":"2025-03-03T00:47:24.201Z","search_vector":"'calculus':4 'lambda':3 'simpli':1 'type':2","search_content":" \n \n\n# \nThe **simply typed lambda calculus** (\\lambda^\\to), a form\nof [type theory](https://bliptext.com/articles/type-theory), is a [typed interpretation](https://bliptext.com/articles/typed-lambda-calculus) of the [lambda calculus](https://bliptext.com/articles/lambda-calculus) with only one [type constructor](https://bliptext.com/articles/type-constructor) (\\to) that builds [function types](https://bliptext.com/articles/function-type).\nIt is the canonical and simplest example of a typed lambda calculus.\nThe simply typed lambda calculus was originally introduced by [Alonzo Church](https://bliptext.com/articles/alonzo-church) in 1940 as an attempt to avoid paradoxical use of the [untyped lambda calculus](https://bliptext.com/articles/untyped-lambda-calculus).\nThe term simple type is also used to refer to extensions of the simply typed lambda [calculus](https://bliptext.com/articles/calculus) with constructs such as [products](https://bliptext.com/articles/cartesian-product), co[products](https://bliptext.com/articles/cartesian-product) or [natural numbers](https://bliptext.com/articles/natural-number) ([System T](https://bliptext.com/articles/dialectica-interpretation)) or even full [recursion](https://bliptext.com/articles/recursion) (like [PCF](https://bliptext.com/articles/programming-language-for-computable-functions)).\nIn contrast, systems that introduce [polymorphic types](https://bliptext.com/articles/parametric-polymorphism) (like [System F](https://bliptext.com/articles/system-f)) or [dependent types](https://bliptext.com/articles/dependent-type) (like the [Logical Framework](https://bliptext.com/articles/lf-logical-framework)) are not considered simply typed.\nThe simple types, except for full recursion, are still considered simple because the [Church encodings](https://bliptext.com/articles/church-encoding) of such structures can be done using only \\to and suitable type variables, while polymorphism and dependency cannot.\n\n# Syntax\nIn the 1930s Alonzo Church sought to use the logistic method: his [lambda calculus](https://bliptext.com/articles/lambda-calculus), as a formal language based on symbolic expressions, consisted of a denumerably infinite series of axioms and variables, but also a finite set of primitive symbols, denoting abstraction and scope, as well as four constants: negation, disjunction, universal quantification, and selection respectively; and also, a finite set of rules I to VI.\nThis finite set of rules included rule V [modus ponens](https://bliptext.com/articles/modus-ponens) as well as IV and VI for substitution and generalization respectively.\nRules I to III are known as alpha, beta, and eta conversion in the lambda calculus.\nChurch sought to use English only as a syntax language (that is, a metamathematical language) for describing symbolic expressions with no interpretations.\nIn 1940 Church settled on a subscript notation for denoting the type in a symbolic expression.\nIn his presentation, Church used only two base types: o for \"the type of propositions\" and \\iota for \"the type of individuals\".\nThe type o has no term constants, whereas \\iota has one term constant.\nFrequently the calculus with only one base type, usually o, is considered.\nThe Greek letter subscripts, etc. denote type variables; the parenthesized subscripted denotes the function type.\nChurch 1940 p.58 used 'arrow or \\to' to denote stands for, or is an abbreviation for.\nBy the 1970s stand-alone arrow notation was in use; for example in this article non-subscripted symbols \\sigma and \\tau can range over types.\nThe infinite number of axioms were then seen to be a consequence of applying rules I to VI to the types (see [Peano axioms](https://bliptext.com/articles/peano-axioms)).\nInformally, the function type refers to the type of functions that, given an input of type \\sigma, produce an output of type \\tau.\nBy convention, \\to associates to the right: is read as.\nTo define the types, a [set](https://bliptext.com/articles/set-mathematics) of base types, B, must first be defined.\nThese are sometimes called atomic types or type constants.\nWith this fixed, the syntax of types is:\nFor example,, generates an infinite set of types starting with a, b, a \\to a, a \\to b, b \\to b, b \\to a, , ..., , ...\nA set of term constants is also fixed for the base types.\nFor example, it might be assumed that one of the base types is nat, and its term constants could be the natural numbers.\nThe syntax of the simply typed lambda calculus is essentially that of the lambda calculus itself.\nThe term denotes that the variable x is of type \\tau.\nThe term syntax, in [Backus–Naur form](https://bliptext.com/articles/backus-naur-form), is variable reference, abstractions, application, or constant:\nwhere c is a term constant.\nA variable reference x is bound if it is inside of an abstraction binding x. A term is closed if there are no unbound variables.\nIn comparison, the syntax of untyped lambda calculus has no such typing or term constants:\nWhereas in typed lambda calculus every abstraction (i.e. function) must specify the type of its argument.\n\n# Typing rules\nTo define the set of well-typed lambda terms of a given type, one defines a typing relation between terms and types.\nFirst, one introduces typing contexts, or [typing environments](https://bliptext.com/articles/typing-environment), which are sets of typing assumptions.\nA typing assumption has the form, meaning variable x has type \\sigma.\nThe typing relation indicates that e is a term of type \\sigma in context \\Gamma.\nIn this case e is said to be well-typed (having type \\sigma).\nInstances of the typing relation are called typing judgments.\nThe validity of a typing judgment is shown by providing a typing derivation, constructed using [typing rules](https://bliptext.com/articles/typing-rule) (wherein the premises above the line allow us to derive the conclusion below the line).\nSimply typed lambda calculus uses these rules:\nIn words,\nExamples of closed terms, i.e. terms typable in the empty context, are:\nThese are the typed lambda calculus representations of the basic combinators of [combinatory logic](https://bliptext.com/articles/combinatory-logic).\nEach type \\tau is assigned an order, a number o(\\tau).\nFor base types, o(T)=0; for function types,.\nThat is, the order of a type measures the depth of the most left-nested arrow.\nHence:\n\n# Semantics\n\n## Intrinsic vs. extrinsic interpretations\nBroadly speaking, there are two different ways of assigning meaning to the simply typed lambda calculus, as to typed languages more generally, variously called intrinsic vs. extrinsic, ontological vs. semantical, or Church-style vs. Curry-style.\nAn intrinsic semantics only assigns meaning to well-typed terms, or more precisely, assigns meaning directly to typing derivations.\nThis has the effect that terms differing only by type annotations can nonetheless be assigned different meanings.\nFor example, the identity term on [integers](https://bliptext.com/articles/integer) and the identity term on [booleans](https://bliptext.com/articles/boolean-data-type) may mean different things.\n(The classic intended interpretations are the identity function on integers and the identity function on boolean values.)\nIn contrast, an extrinsic semantics assigns meaning to terms regardless of typing, as they would be interpreted in an untyped language.\nIn this view, and mean the same thing (i.e., the same thing as ).\nThe distinction between intrinsic and extrinsic semantics is sometimes associated with the presence or absence of annotations on lambda abstractions, but strictly speaking this usage is imprecise.\nIt is possible to define an extrinsic semantics on annotated terms simply by ignoring the types (i.e., through [type erasure](https://bliptext.com/articles/type-erasure)), as it is possible to give an intrinsic semantics on unannotated terms when the types can be deduced from context (i.e., through [type inference](https://bliptext.com/articles/type-inference)).\nThe essential difference between intrinsic and extrinsic approaches is just whether the typing rules are viewed as defining the language, or as a formalism for verifying properties of a more primitive underlying language.\nMost of the different semantic interpretations discussed below can be seen through either an intrinsic or extrinsic perspective.\n\n## Equational theory\nThe simply typed lambda calculus (STLC) has the same [equational theory](https://bliptext.com/articles/equational-theory) of βη-equivalence as [untyped lambda calculus](https://bliptext.com/articles/untyped-lambda-calculus), but subject to type restrictions.\nThe equation for [beta reduction](https://bliptext.com/articles/beta-reduction)\nholds in context \\Gamma whenever and, while the equation for [eta reduction](https://bliptext.com/articles/eta-reduction)\nholds whenever and x does not appear free in t. The advantage of typed lambda calculus is that STLC allows potentially nonterminating computations to be cut short (that is, reduced).\n\n## Operational semantics\nLikewise, the [operational semantics](https://bliptext.com/articles/operational-semantics) of simply typed lambda calculus can be fixed as for the untyped lambda calculus, using [call by name](https://bliptext.com/articles/call-by-name), [call by value](https://bliptext.com/articles/call-by-value), or other [evaluation strategies](https://bliptext.com/articles/evaluation-strategy).\nAs for any typed language, [type safety](https://bliptext.com/articles/type-safety) is a fundamental property of all of these evaluation strategies.\nAdditionally, the [strong normalization](https://bliptext.com/articles/strong-normalization) property [described below](https://bliptext.com/articles/simply-typed-lambda-calculus) implies that any evaluation strategy will terminate on all simply typed terms.\n\n## Categorical semantics\nThe simply typed lambda calculus enriched with product types, pairing and projection operators (with \\beta\\eta-equivalence) is the [internal language](https://bliptext.com/articles/internal-language) of [Cartesian closed categories](https://bliptext.com/articles/cartesian-closed-categories) (CCCs), as was first observed by [Joachim Lambek](https://bliptext.com/articles/joachim-lambek).\nGiven any CCC, the basic types of the corresponding lambda calculus are the [objects](https://bliptext.com/articles/object-category-theory), and the terms are the [morphisms](https://bliptext.com/articles/morphism).\nConversely, the simply typed lambda calculus with product types and pairing operators over a collection of base types and given terms forms a CCC whose objects are the types, and morphisms are equivalence classes of terms.\nThere are [typing rules](https://bliptext.com/articles/typing-rule) for pairing, projection, and a unit term.\nGiven two terms and, the term (s,t) has type.\nLikewise, if one has a term, then there are terms and where the \\pi_i correspond to the projections of the Cartesian product.\nThe unit term, of type 1, written as and vocalized as 'nil', is the [final object](https://bliptext.com/articles/final-object).\nThe equational theory is extended likewise, so that one has\nThis last is read as \"if t has type 1, then it reduces to nil\".\nThe above can then be turned into a category by taking the types as the [objects](https://bliptext.com/articles/object-category-theory).\nThe [morphisms](https://bliptext.com/articles/morphism) are [equivalence classes](https://bliptext.com/articles/equivalence-class) of pairs where x is a variable (of type \\sigma) and t is a term (of type \\tau), having no free variables in it, except for (optionally) x.\nThe set of terms in the language is the closure of this set of terms under the operations of abstraction and [application](https://bliptext.com/articles/apply).\nThis correspondence can be extended to include \"language homomorphisms\" and [functors](https://bliptext.com/articles/functor) between the category of Cartesian closed categories, and the category of simply typed lambda theories.\nPart of this correspondence can be extended to [closed symmetric monoidal categories](https://bliptext.com/articles/closed-monoidal-category) by using a [linear type system](https://bliptext.com/articles/linear-type-system).\n\n## Proof-theoretic semantics\nThe simply typed lambda calculus is closely related to the implicational fragment of propositional [intuitionistic logic](https://bliptext.com/articles/intuitionistic-logic), i.e., the [implicational propositional calculus](https://bliptext.com/articles/implicational-propositional-calculus), via the [Curry–Howard isomorphism](https://bliptext.com/articles/curry-howard-isomorphism): terms correspond precisely to proofs in [natural deduction](https://bliptext.com/articles/natural-deduction), and [inhabited types](https://bliptext.com/articles/type-inhabitation) are exactly the [tautologies](https://bliptext.com/articles/tautology-logic) of this logic.\nFrom his logistic method Church 1940 p.58 laid out an [axiom schema](https://bliptext.com/articles/axiom-schema), p. 60, which Henkin 1949 filled in with type domains (e.g. the natural numbers, the real numbers, etc.).\nHenkin 1996 p. 146 described how Church's logistic method could seek to provide a foundation for mathematics (Peano arithmetic and real analysis), via [model theory](https://bliptext.com/articles/model-theory).\n\n# Alternative syntaxes\nThe presentation given above is not the only way of defining the syntax of the simply typed lambda calculus.\nOne alternative is to remove type annotations entirely (so that the syntax is identical to the untyped lambda calculus), while ensuring that terms are well-typed via [Hindley–Milner type inference](https://bliptext.com/articles/hindley-milner-type-inference).\nThe inference algorithm is terminating, sound, and complete: whenever a term is typable, the algorithm computes its type.\nMore precisely, it computes the term's [principal type](https://bliptext.com/articles/principal-type), since often an unannotated term (such as ) may have more than one type (,, etc., which are all instances of the [principal type](https://bliptext.com/articles/principal-type) ).\nAnother alternative presentation of simply typed lambda calculus is based on **bidirectional type checking**, which requires more type annotations than Hindley–Milner inference but is easier to describe.\nThe [type system](https://bliptext.com/articles/type-system) is divided into two judgments, representing both checking and synthesis, written and respectively.\nOperationally, the three components \\Gamma, e, and \\tau are all inputs to the checking judgment, whereas the synthesis judgment only takes \\Gamma and e as inputs, producing the type \\tau as output.\nThese judgments are derived via the following rules:\nObserve that rules [1]–[4] are nearly identical to rules (1)–(4) [above](https://bliptext.com/articles/), except for the careful choice of checking or synthesis judgments.\nThese choices can be explained like so:\nObserve that the rules for synthesis are read top-to-bottom, whereas the rules for checking are read bottom-to-top.\nNote in particular that we do **not** need any an**not**ation on the lambda abstraction in rule [3], because the type of the bound variable can be deduced from the type at which we check the function.\nFinally, we explain rules [5] and [6] as follows:\n To check that e has type \\tau, it suffices to synthesize type \\tau. \n If e checks against type \\tau, then the explicitly annotated term synthesizes \\tau.\n \n \nBecause of these last two rules coercing between synthesis and checking, it is easy to see that any well-typed but unannotated term can be checked in the bidirectional system, so long as we insert \"enough\" type annotations.\nAnd in fact, annotations are needed only at β-redexes.\n\n# General observations\nGiven the standard semantics, the simply typed lambda calculus is [strongly normalizing](https://bliptext.com/articles/normalization-property-lambda-calculus): every sequence of reductions eventually terminates.\nThis is because recursion is not allowed by the typing rules: it is impossible to find types for [fixed-point combinators](https://bliptext.com/articles/fixed-point-combinator) and the looping term.\nRecursion can be added to the language by either having a special operator of type or adding general [recursive types](https://bliptext.com/articles/recursive-type), though both eliminate strong normalization.\nUnlike the untyped lambda calculus, the simply typed lambda calculus is not [Turing complete](https://bliptext.com/articles/turing-complete).\nAll programs in the simply typed lambda calculus halt.\nFor the untyped lambda calculus, there are programs that do not halt, and moreover there is no general decision procedure that can determine whether a program halts.\n\n# Important results","revisionCount":1},"hasMore":false,"nextCursor":null}

History