Content deleted Content added
Mofoburrell (talk | contribs) Added link to "confluence" |
→Narrowing: Added brief, incomplete description |
||
Line 79:
===Narrowing===
Narrowing is a mechanism whereby a variable is bound to a value selected from among alternatives imposed by constraints. Each possible value is tried in some order, with the remainder of the program invoked in each case to determine the validity of the binding.
Narrowing is useful because it allows a function to be treated as a relation: its value can be computed "in both directions". Consider the Curry program <example needed here, but I don't know the Wikipedia syntax and barely remember Curry's>.
Narrowing can be thought of as reduction on a program graph. There are often several choices as to which subgraph (subexpression or "redex") to narrow on first. Sergio Antoy proved in the 1990's that a particular narrowing strategy, "needed narrowing", is optimal in the sense of doing a minimum number of reductions to get to a "normal form" corresponding to a solution.
==External links==
| |||