{
  "id": "enwiki-001359966198",
  "slug": "beta-normal-form",
  "title": "Beta normal form",
  "qid": "",
  "lead": "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.",
  "body": "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==",
  "categories": [
    "29176435",
    "29176523"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1359966198",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1781772231.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001359966198",
    "type": "webpage",
    "title": "Beta normal form",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/beta-normal-form",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          16
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          16
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001359966198",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1359966198",
    "note": "Immutable snapshot enwiki-001359966198"
  }
}