| Curry | |
| Paradigm: | functional, logic, non-strict, modular |
| Designer: | Michael Hanus, Sergio Antoy, et al. |
| Developer: | Kiel University Ludwig Maximilian University of Munich University of Münster Portland State University Complutense University of Madrid Technical University of Madrid |
| Latest Release Date: | |
| Typing: | static, strong, inferred |
| Platform: | x86-64 |
| Operating System: | Cross-platform |
| License: | BSD 3-clause |
| Implementations: | PAKCS (Prolog target), mcc (C target), KiCS2 (Haskell target) |
| Influenced By: | Haskell, Prolog |
Curry is a declarative programming language, an implementation of the functional logic programming paradigm,[1] [2] and based on the Haskell language. It merges elements of functional and logic programming,[3] including constraint programming integration.
It is nearly a superset of Haskell but does not support all language extensions of Haskell. In contrast to Haskell, Curry has built-in support for non-deterministic computations involving search.
A functional program is a set of functions defined by equations or rules. A functional computation consists of replacing subexpressions by equal (with regard to the function definitions) subexpressions until no more replacements (or reductions) are possible and a value or normal form is obtained. For instance, consider the function double defined by
double x = x+x
The expression “” is replaced by . The latter can be replaced by if we interpret the operator “” to be defined by an infinite set of equations, e.g.,,, etc. In a similar way, one can evaluate nested expressions (where the subexpressions to be replaced are quoted):
'double (1+2)' → '(1+2)'+(1+2) → 3+'(1+2)' → '3+3' → 6
There is also another order of evaluation if we replace the arguments of operators from right to left:
'double (1+2)' → (1+2)+'(1+2)' → '(1+2)'+3 → '3+3' → 6
In this case, both derivations lead to the same result, a property known as confluence. This follows from a fundamental property of pure functional languages, termed referential transparency: the value of a computed result does not depend on the order or time of evaluation, due to the absence of side effects. This simplifies reasoning about, and maintaining, pure functional programs.
As many functional languages like Haskell do, Curry supports the definition of algebraic data types by enumerating their constructors. For instance, the type of Boolean values consists of the constructors and that are declared as follows:
More complex data structures can be obtained by recursive data types. For instance, a list of elements, where the type of elements is arbitrary (denoted by the type variable), is either the empty list “” or the non-empty list “” consisting of a first element and a list :
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". The Curry examples of the previous section illustrate this.
As noted in the prior section, narrowing can be thought of as reduction on a program term graph, and there are often many different ways (strategies) to reduce a given term graph. Antoy et al.[4] proved in the 1990s that a particular narrowing strategy, needed narrowing, is optimal in the sense of doing 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 SLD-resolution strategy of Prolog.
The rule defining shown above expresses the fact that the actual argument must match the result of narrowing the expression . Curry can express this property also in the following more concise way:
Since Curry is able to solve equations containing function calls with unknown values, its execution mechanism is based on non-deterministic computations, similarly to logic programming. This mechanism supports also the definition of non-deterministic operations, i.e., operations that delivers more than one result for a given input. The archetype of non-deterministic operations is the predefined infix operation, called choice operator, that returns one of its arguments. This operator is defined by the following rules:
x ? y = x x ? y = y
Thus, the evaluation of the expression returns as well as . Computing with non-deterministic operations and computing with free variables by narrowing has the same expressive power.[6]
The rules defining show an important feature of Curry: all rules are tried in order to evaluate some operation. Hence, one can define by
Due to the absence of side effects, a functional logic program can be executed with different strategies. To evaluate expressions, Curry uses a variant of the needed narrowing strategy which combines lazy evaluation with non-deterministic search strategies. In contrast to Prolog, which uses backtracking to search for solutions, Curry does not fix a particular search strategy. Hence, there are implementations of Curry, like KiCS2, where the user can easily select a search strategy, like depth-first search (backtracking), breadth-first search, iterative deepening, or parallel search.