Curry (programming language): Difference between revisions

Revision as of 19:09, 21 September 2008

Revision as of 19:25, 21 September 2008

Line 80:

===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 an extension of logic programming, in that it performs a similar search, but can actually generate values as part of the search rather than just being limited to testing them.

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 athe minimuma number of reductions to get to a "normal form" corresponding to a solution that is minimal among sound and complete strategies. Needed narrowing corresponds to a lazy strategy, in contrast to the incomplete SLD-resolution strategy of Prolog.

==External links==