Beta normal form

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 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 lambda calculus, a term is in beta normal form if no beta reduction is possible. A term is in beta-eta normal form if neither a beta reduction nor an eta reduction is possible. A term is in head normal form if there is no beta-redex in the head position. The normal form of a term, if one exists, is unique (as a corollary of the Church–Rosser theorem). However, a term may have more than one head normal form.

In lambda calculus, a term is in beta normal form if no beta reduction is possible. A term is in beta-eta normal form if neither a beta reduction nor an eta reduction is possible. A term is in head normal form if there is no beta-redex in the head position. The normal form of a term, if one exists, is unique (as a corollary of the Church–Rosser theorem). However, a term may have more than one head normal form.

Beta reduction

In the lambda calculus, a beta redex is a term of the form: (\mathbf{\lambda} x . A) M. A redex r is in head position in a term t , if t has the following shape (note that application has higher priority than abstraction, and that the formula below is meant to be a lambda-abstraction, not an application): \lambda x_1 \ldots \lambda x_n . \underbrace{(\lambda x . A) M_1}_{\text{the redex }r} M_2 \ldots M_m, where n \geq 0 and m \geq 1. A beta reduction is an application of the following rewrite rule to a beta redex contained in a term: (\mathbf{\lambda} x . A) M \longrightarrow A[x := M] where A[x := M] is the result of substituting the term M for the variable x in the term A . A head beta reduction is a beta reduction applied in head position, that is, of the following form: \lambda x_1 \ldots \lambda x_n . (\lambda x . A) M_1 M_2 \ldots M_m \longrightarrow \lambda x_1 \ldots \lambda x_n . A[x := M_1] M_2 \ldots M_m, where n \geq 0 and m \geq 1. Any other reduction is an internal beta reduction. \lambda x_1 \ldots \lambda x_n . x M_1 M_2 \ldots M_m , where x is a variable, n \geq 0 and m \geq 0 . A head normal form is not always a normal form, because the applied arguments M_j need not be normal. However, the converse is true: any normal form is also a head normal form. In fact, the normal forms are exactly the head normal forms in which the subterms M_j are themselves normal forms. This gives an inductive syntactic description of normal forms. There is also the notion of weak head normal form. A λ-term, M, is in weak head normal form in case it is a λ-abstraction, M = \mathbf{\lambda} x . N where N is any expression, even containing a redex, or it is in head normal form (in the pure lambda calculus, the only head normal forms that are not λ-abstractions are of the form x M_1 M_2 \ldots M_m , where x is any variable and m \geq 0 ). Weak head normal forms were introduced by Simon Peyton Jones to reflect the form to which functional languages actually evaluate.

See also

Lambda calculus Normal form (disambiguation) Reduction strategy

References

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

Provenance

snapshot enwiki-001359966198 · captured 1781772231.0 · version history

Cite this page as: encyclopegia.org, “Beta normal form”, snapshot enwiki-001359966198. https://encyclopegia.org/a/beta-normal-form

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.