Curry (programming language): Difference between revisions

Revision as of 02:48, 24 February 2019

Revision as of 02:39, 11 April 2019

Line 1:

{{cleanup HTML|date=February 2019}}

{{About|the programming language Curry (named in honour of a mathematician and logician)|the mathematician and logician|Haskell Curry|the computer science technique|Currying}}

{{Infobox programming language

Line 48 ⟶ 47:

double x = x+x

The expression “<tt>{{Mono|double 1</tt>}}” is replaced by <tt>{{Mono|1+1</tt>}}. The latter can be replaced by <tt>{{Mono|2</tt>}} if we interpret the operator “<tt>{{Mono|+</tt>}}” to be defined by an infinite set of equations, e.g., <tt>{{Mono|1+1 = 2</tt>}}, <tt>{{Mono|1+2 = 3</tt>}}, 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

Line 58 ⟶ 57:

In this case, both derivations lead to the same result, a property known as [[Confluence (term rewriting)|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 the reasoning about and maintenance of pure functional programs.

As many functional languages like [[haskell (programming language)|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 <tt>{{Mono|True</tt>}} and <tt>{{Mono|False</tt>}} that are declared as follows:

<source lang="haskell">

data Bool = True | False

Line 72 ⟶ 71:

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 <tt>{{Mono|a</tt>}}), is either the empty list “<tt>{{Mono|[]</tt>}}” or the non-empty list “<tt>{{Mono|x:xs</tt>}}” consisting of a first element <tt>{{Mono|x</tt>}} and a list <tt>{{Mono|xs</tt>}}:

<source lang="haskell">

data List a = [] | a : List a

</source>

The type “<tt>{{Mono|List a</tt>}}” is usually written as <tt>{{Mono|[a]</tt>}} and finite lists x1<tt>{{Mono|:</tt>}}x2<tt>{{Mono|:</tt>}}...<tt>{{Mono|:</tt>}}xn<tt>{{Mono|:[]</tt>}} are written as <tt>{{Mono|[</tt>}}x1<tt>{{Mono|,</tt>}}x2<tt>{{Mono|,</tt>}}...<tt>{{Mono|,</tt>}}xn<tt>{{Mono|]</tt>}}. 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 “<tt>{{Mono|++</tt>}}” on polymorphic lists can be defined as follows (the optional type declaration in the first line specifies that “<tt>{{Mono|++</tt>}}” takes two lists as input and produces an output list, where all list elements are of the same unspecified type):

<source lang="haskell">

(++) :: [a] -> [a] -> [a]

Line 82 ⟶ 81:

(x:xs) ++ ys = x : xs++ys

</source>

Beyond its application for various programming tasks, the operation “<tt>{{Mono|++</tt>}}” 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, <tt>{{Mono|last</tt>}} xs = e if ∃ys<tt>{{Mono|:</tt>}}ys<tt>{{Mono|++[</tt>}}e<tt>{{Mono|]</tt>}} = 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 ys<tt>{{Mono|++[</tt>}}e<tt>{{Mono|]</tt>}} = <tt>{{Mono|[1,2,3]</tt>}} is solved by instantiating ys to the list <tt>{{Mono|[1,2]</tt>}} and e to the value <tt>{{Mono|3</tt>}}. In Curry one can define the operation last as follows:

<source lang="haskell">

last xs | ys++[e] =:= xs = e where ys,e free

</source>

Here, the symbol “<tt>{{Mono|=:=</tt>}}” 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 “<tt>{{Mono|where...free</tt>}}” in order to provide some opportunities to detect bugs caused by typos. A conditional equation of the form l <tt>{{Mono|</tt>|}} c <tt>{{Mono|=</tt>}} 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===

Line 112 ⟶ 111:

===Functional Patterns===

The rule defining <tt>{{Mono|last</tt>}} shown above expresses the fact that the actual argument must match the result of narrowing the expression <tt>{{Mono|ys++[e]</tt>}}. Curry can express this property also in the following more concise way:

<source lang="haskell">

last (ys++[e]) = e

</source>

Haskell does not allow such a declaration since the pattern in the left-hand side contains a defined function (<tt>{{Mono|++</tt>}}). Such a pattern is also called ''functional pattern''.<ref>{{cite journal|doi=10.1007/11680093_2 | title=Declarative Programming with Function Patterns | year=2006 | journal=Lecture Notes in Computer Science | pages=6–22 | author=Antoy Sergio, Hanus Michael}}</ref> 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 <tt>{{Mono|?</tt>}}, 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 <tt>{{Mono|0 ? 1</tt>}} returns <tt>{{Mono|0</tt>}} as well as <tt>{{Mono|1</tt>}}. Computing with non-deterministic operations and computing with free variables by narrowing has the same expressive power.<ref>{{cite journal|doi=10.1007/11799573_9 | title=Overlapping Rules and Logic Variables in Functional Logic Programs | year=2006 | journal=Lecture Notes in Computer Science | pages=87–101 | author=Antoy Sergio, Hanus Michael}}</ref>

The rules defining <tt>{{Mono|?</tt>}} show an important feature of Curry: all rules are tried in order to evaluate some operation. Hence, one can define by

<source lang="haskell">

insert x ys = x : ys

insert x (y:ys) = y : insert x ys

</source>

an operation to insert an element into a list at an indeterminate position so that the operation <tt>{{Mono|perm</tt>}} defined by

<source lang="haskell">

perm [] = []