Curry (programming language): Difference between revisions

Revision as of 19:25, 21 September 2008

Revision as of 19:33, 21 September 2008

Line 82:

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 theThe Curry programexamples <example needed here, but I don't knowof the Wikipediaprevious syntaxsection andillustrate barely remember Curry's>this.

NarrowingAs noted in the previous section, narrowing can be thought of as reduction on a program term graph., and Therethere are often severalmany choicesdifferent as to which subgraphways (subexpression or "redex"*strategies*) to narrowreduce ona firstgiven term graph. Sergio Antoy proved in the 1990's that a particular narrowing strategy, *needed narrowing*, is optimal in the sense of doing the a 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==