Reduction strategy
≈ 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.