Typing rule

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In type theory and programming language theory, a typing rule is an inference rule that specifies sufficient conditions for a typing judgment to hold. A common form of typing judgment is : \Gamma \vdash e : \tau, read as “under typing context \Gamma , expression e has type \tau ”. A collection of typing rules normally defines a typing relation inductively: a judgment holds when it has a finite derivation constructed from the rules. A program is well-typed when its required top-level typing judgment can be derived. Typing rules are relational specifications rather than necessarily functions from expressions to types. Depending on the type system, an expression may have no derivable type, one type, or several types. Rules may be presented as a declarative mathematical specification or organized into a procedure for type checking or type inference. A common algorithmic organization is bidirectional typing, which distinguishes rules that synthesize a type from rules that check an expression against a type already known from its context.

In type theory and programming language theory, a typing rule is an inference rule that specifies sufficient conditions for a typing judgment to hold. A common form of typing judgment is \Gamma \vdash e : \tau, read as “under typing context \Gamma , expression e has type \tau ”. A collection of typing rules normally defines a typing relation inductively: a judgment holds when it has a finite derivation constructed from the rules. A program is well-typed when its required top-level typing judgment can be derived. Typing rules are relational specifications rather than necessarily functions from expressions to types. Depending on the type system, an expression may have no derivable type, one type, or several types. Rules may be presented as a declarative mathematical specification or organized into a procedure for type checking or type inference. A common algorithmic organization is bidirectional typing, which distinguishes rules that synthesize a type from rules that check an expression against a type already known from its context. \Gamma = x_1{:}\tau_1,\ldots,x_n{:}\tau_n. The notation \Gamma,x{:}\tau means that the context has been extended with the assumption that x has type \tau . A closed expression, having no free variables, is commonly typed under the empty context \varnothing . More elaborate systems may use several contexts or auxiliary judgments. These can record type variables, kinds, locations, constraints, effects, modules, or resources. Examples of auxiliary judgments include type formation, type equality, subtyping, and kinding. The structure of a context is also significant: ordinary structural type systems often treat contexts as finite mappings, whereas linear and other substructural systems may make order or multiplicity relevant. An inference rule is conventionally written \frac{J_1 \qquad \cdots \qquad J_n}{J}, where J_1,\ldots,J_n are the rule's premises and J is its conclusion. The rule states that the conclusion may be derived whenever all its premises have been derived. A rule with no premises is an axiom. Rules can also contain side conditions, such as a freshness requirement or a membership test on a context. Typing rules are generally rule schemes: their metavariables range over all expressions, types, and contexts of the language. A typing derivation is a finite tree whose nodes are judgments, whose root is the judgment being established, and whose children are the premises of the rule used at that node. The inductive structure of derivations is later used in proofs about the type system. \tau ::= \mathsf{Bool} \mid \tau \mathbin{\to} \tau and e ::= x \mid \mathsf{true} \mid \mathsf{false} \mid \mathbf{if}\ e\ \mathbf{then}\ e\ \mathbf{else}\ e \mid \lambda x{:}\tau.\,e \mid e\ e. Boolean constants are typed by axiom schemes: \frac{}{\Gamma \vdash \mathsf{true} : \mathsf{Bool}} \quad\text{(T-True)} \qquad \frac{}{\Gamma \vdash \mathsf{false} : \mathsf{Bool}} \quad\text{(T-False)}. A conditional requires a Boolean condition and branches having the same type: \frac{ \Gamma \vdash e_1 : \mathsf{Bool} \qquad \Gamma \vdash e_2 : \tau \qquad \Gamma \vdash e_3 : \tau }{ \Gamma \vdash \mathbf{if}\ e_1\ \mathbf{then}\ e_2\ \mathbf{else}\ e_3 : \tau } \quad\text{(T-If)}. Variables, abstractions, and applications are typed by the following rules: \frac{x{:}\tau \in \Gamma}{ \Gamma \vdash x : \tau } \quad\text{(T-Var)} \frac{ \Gamma,x{:}\tau_1 \vdash e : \tau_2 }{ \Gamma \vdash \lambda x{:}\tau_1.\,e : \tau_1 \mathbin{\to} \tau_2 } \quad\text{(T-Abs)} \frac{ \Gamma \vdash e_1 : \tau_1 \mathbin{\to} \tau_2 \qquad \Gamma \vdash e_2 : \tau_1 }{ \Gamma \vdash e_1\,e_2 : \tau_2 } \quad\text{(T-App)}. These rules are schemes because \Gamma , e , and the types may be replaced by arbitrary instances. For example, the rules derive \varnothing \vdash (\lambda x{:}\mathsf{Bool}.\,x)\,\mathsf{true} \mathsf{Bool}. The abstraction rule checks the body under a context extended with an assumption about the bound variable. In its conclusion, that assumption has been abstracted into the function type. In proof-theoretic terms, T-Abs is an introduction rule for the function type and T-App is its elimination rule. This correspondence with the introduction and elimination rules of natural deduction is part of the Curry–Howard correspondence. \mathbf{let}\ x=e_1\ \mathbf{in}\ e_2 : \tau_2 }. Here x is available in e_2 at the single type \tau_1 . This is not the full rule for Hindley–Milner let-polymorphism. In a Hindley–Milner system, eligible type variables in the type of e_1 can be generalized into a type scheme, whose different occurrences may subsequently be instantiated at different types.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373649893 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.