Reduction strategy

Uses your system voice; voice and rate in settings.

Q15947151Snapshot

≈ 3 min read

Names in other languages

  • afReduction strategy
  • anReduction strategy
  • astReduction strategy
  • DeutschReduction strategy
  • EnglishReduction strategy
  • EspañolReduction strategy
  • FrançaisReduction strategy
  • ItalianoReduction strategy

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

In rewriting, a reduction strategy or rewriting strategy is a relation specifying a rewrite for each object or term, compatible with a given reduction relation. Some authors use the term to refer to an evaluation strategy.

In rewriting, a reduction strategy or rewriting strategy is a relation specifying a rewrite for each object or term, compatible with a given reduction relation. Some authors use the term to refer to an evaluation strategy. \begin{align} &(\mathbf{\lambda} x . z) ((\lambda w. w w w) (\lambda w. w w w)) \\ \rightarrow &(\lambda x . z) ((\lambda w. w w w) (\lambda w. w w w) (\lambda w. w w w))\\ \rightarrow &(\lambda x . z) ((\lambda w. w w w) (\lambda w. w w w) (\lambda w. w w w) (\lambda w. w w w))\\ \rightarrow &(\lambda x . z) ((\lambda w. w w w) (\lambda w. w w w) (\lambda w. w w w) (\lambda w. w w w) (\lambda w. w w w))\\ &\ldots \end{align} But using normal-order reduction, the same starting point reduces quickly to normal form: (\mathbf{\lambda} x . z) ((\lambda w. w w w) (\lambda w. w w w)) \rightarrow z Full β-reduction refers to the nondeterministic one-step strategy that allows reducing any redex at each step. Takahashi's parallel β-reduction is the strategy that reduces all redexes in the term simultaneously. ((\lambda x. M )^\alpha N)^\beta \to \beta \overline{\alpha} \cdot M[x \mapsto \underline{\alpha}\cdot N] where \cdot concatenates labels, \beta\cdot T^\alpha = T^{\beta\alpha} , and substitution M[x \mapsto N] is defined as follows (using the Barendregt convention): \begin{align} x^{\alpha}[x\mapsto N] & = \alpha\cdot N & \quad (\lambda y.M)^{\alpha}[x\mapsto N] & = (\lambda y.M[x\mapsto N])^{\alpha} \\ y^{\alpha}[x\mapsto N] & = y^{\alpha} & \quad (MN)^{\alpha}[x\mapsto P] & = (M[x\mapsto P]N[x\mapsto P])^{\alpha} \end{align} The system can be proven to be confluent. Optimal reduction is then defined to be normal order or leftmost-outermost reduction using reduction by families, i.e. the parallel reduction of all redexes with the same function part label. The strategy is optimal in the sense that it performs the optimal (minimal) number of family reduction steps. A practical algorithm for optimal reduction was first described in 1989, more than a decade after optimal reduction was first defined in 1974. The Bologna Optimal Higher-order Machine (BOHM) is a prototype implementation of an extension of the technique to interaction nets. Lambdascope is a more recent implementation of optimal reduction, also using interaction nets.

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

Provenance

snapshot reduction-strategy-1738804-25ad0569b007ddfe · hash 25ad0569b007ddfee23a91e5ecb96469897caad0ff771e5cdb4297f275b3ebfb · captured 1776644708.0 · version history

Cite this page as: encyclopegia.org, “Reduction strategy”, snapshot reduction-strategy-1738804-25ad0569b007ddfe. https://encyclopegia.org/a/reduction-strategy

Sources cited in this revision

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