Curry is a
declarative programming
In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Many languages that ap ...
language, an implementation of the
functional logic programming paradigm, and based on the
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
language. It merges elements of functional and logic programming,
[
] including
constraint programming
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state t ...
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.
Foundations of functional logic programming
Basic concepts
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
In geography, a confluence (also ''conflux'') occurs where two or more watercourses join to form a single channel (geography), channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main ...
. This follows from a fundamental property of pure functional languages, termed
referential transparency
In analytic philosophy and computer science, referential transparency and referential opacity are properties of linguistic constructions, and by extension of languages. A linguistic construction is called ''referentially transparent'' when for an ...
: the value of a computed result does not depend on the order or time of evaluation, due to the absence of
side effects
In medicine, a side effect is an effect of the use of a medicinal drug or other treatment, usually adverse but sometimes beneficial, that is unintended. Herbal and traditional medicines also have side effects.
A drug or procedure usually used ...
. This simplifies reasoning about, and maintaining, pure functional programs.
As many functional languages like
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
do, Curry supports the definition of
algebraic data type
In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite data type, i.e., a data type formed by combining other types.
Two common classes of algebraic types are product ty ...
s by enumerating their constructors. For instance, the type of Boolean values consists of the constructors and that are declared as follows:
data Bool = True , False
Functions on Booleans can be defined by pattern matching, i.e., by providing several equations for different argument values:
not True = False
not False = True
The principle of replacing equals by equals is still valid provided that the actual arguments have the required form, e.g.:
not '(not False)' → 'not True' → False
More complex
data structure
In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
s 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 :
data List a = [] , a : List a
The type “” is usually written as and finite lists x1x2...xn are written as x1x2...xn. We can define operations on recursive types by inductive definitions where pattern matching supports the convenient separation of the different cases. For instance, the concatenation operation “” on polymorphic lists can be defined as follows (the optional type declaration in the first line specifies that “” takes two lists as input and produces an output list, where all list elements are of the same unspecified type):
(++) :: -> ->
[] ++ ys = ys
(x:xs) ++ ys = x : xs++ys
Beyond its application for various programming tasks, the operation “” is also useful to specify the behavior of other functions on lists. For instance, the behavior of a function last that yields the last element of a list can be specified as follows: for all lists xs and elements e, xs = e if ∃ysyse = xs.
Based on this specification, one can define a function that satisfies this specification by employing logic programming features. Similarly to logic languages, functional logic languages provide search for solutions for existentially quantified variables. In contrast to pure logic languages, they support equation solving over nested functional expressions so that an equation like yse = is solved by instantiating ys to the list and e to the value . In Curry one can define the operation last as follows:
last xs , ys++ =:= xs = e where ys,e free
Here, the symbol “” is used for equational constraints in order to provide a syntactic distinction from defining equations. Similarly, extra variables (i.e., variables not occurring in the left-hand side of the defining equation) are explicitly declared by “” in order to provide some opportunities to detect bugs caused by typos. A conditional equation of the form l c r is applicable for reduction if its condition c has been solved. In contrast to purely functional languages where conditions are only evaluated to a Boolean value, functional logic languages support the solving of conditions by guessing values for the unknowns in the condition. Narrowing as discussed in the next section is used to solve this kind of conditions.
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". 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. 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
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics.
Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...
.
Functional patterns
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:
last (ys++ = e
Haskell does not allow such a declaration since the pattern in the left-hand side contains a defined function (). Such a pattern is also called ''functional pattern''. Functional patterns are enabled by the combined functional and logic features of Curry and support concise definitions of tasks requiring deep pattern matching in hierarchical data structures.
Non-determinism
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.
The rules defining show an important feature of Curry: all rules are tried in order to evaluate some operation. Hence, one can define by
insert x ys = x : ys
insert x (y:ys) = y : insert x ys
an operation to insert an element into a list at an indeterminate position so that the operation defined by
perm [] = []
perm (x:xs) = insert x (perm xs)
returns any permutation of a given input list.
Strategies
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
In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an Expression (computer science), expression until its value is needed (non-strict evaluation) and which avoids repeated eva ...
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, lik
KiCS2 where the user can easily select a search strategy, like
depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...
(backtracking),
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...
, iterative deepening, or parallel search.
References
External links
*
Smap- A web-based execution environment for Curry and Haskell with various example programs
Curry packages- A collection of software packages for Curry
MCC- The Münster Curry Compiler, targets
CPAKCSA major Curry implementation, targets
Prolog
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics.
Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...
KiCS2A Curry implementation, targets
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
Curry2GoA Curry implementation, targets
Go, and supports fair parallel search
Curry Mailing ListMichael Hanus's home page*
Purely Functional Lazy Non-deterministic Programming' (Fischer, Kiselyov, Shan, 2009),
Transforming Functional Logic Programs into Monadic Functional Programs' (Braßel, Fischer, Hanus, Reck, 2010) on modeling lazy non-deterministic (logic) programming (like in Curry) in a purely functional language (
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
); such approach might give the programmer more flexibility in the control over the strategies that—in the case of Curry—are built-in.
{{Authority control
High-level programming languages
Concurrent programming languages
Experimental programming languages
Functional logic programming languages
Haskell programming language family
Programming languages created in 1995
Nondeterministic programming languages
Literate programming
Academic programming languages
Software using the BSD license
Articles with example Haskell code
Statically typed programming languages