Top Qs
Timeline
Chat
Perspective

Beta normal form

From Wikipedia, the free encyclopedia

Remove ads

In lambda calculus, a term is in beta normal form if no beta reduction is possible.[1] 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).[2] However, a term may have more than one head normal form.

Remove ads

Beta reduction

Summarize
Perspective

In the lambda calculus, a beta redex is a term of the form:[3][4]

.

A redex is in head position in a term , if 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):

, where and .

A beta reduction is an application of the following rewrite rule to a beta redex contained in a term:

where is the result of substituting the term for the variable in the term .

A head beta reduction is a beta reduction applied in head position, that is, of the following form:

, where and .

Any other reduction is an internal beta reduction.

Remove ads

Normal forms

Summarize
Perspective

A normal form is a term that does not contain any beta redex,[3][5] i.e. that cannot be further reduced. Some authors may also include η reductions, hence the distinguishing terms beta normal form and beta-eta normal form.

A head normal form is a term that does not contain a beta redex in head position, i.e. that cannot be further reduced by a head reduction. When considering the simple lambda calculus (viz. without the addition of constant or function symbols, meant to be reduced by additional delta rule head normal forms are the terms of the following shape:

, where is a variable, and .

A head normal form is not always a normal form,[5] because the applied arguments need not be normal. However, the converse is true: any normal form is also a head normal form.[5] In fact, the normal forms are exactly the head normal forms in which the subterms 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, where 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 , where is any variable and ).[6][7] Weak head normal forms were introduced by Simon Peyton Jones to reflect the form to which functional languages actually evaluate.[7][8]

Remove ads

See also

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads