| Curry | |
|---|---|
| Paradigm | functional, logic, non-strict, modular |
| Designed by | Michael Hanus, et al |
| Typing discipline | static, strong, inferred |
| Major implementations | PAKCS, mcc |
| OS | portable |
| Website | Curry |
Curry is an experimental functional logic programming language, based on the Haskell language. A programming paradigm is a fundamental style of Computer programming. In Computer science, functional programming is a Programming paradigm that treats Computation as the evaluation of mathematical functions and Logic programming is in its broadest sense the use of mathematical logic for computer programming In Computer science, a type system defines how a Programming language classifies values and expressions into '''types''', how it can In Computer science, a type system defines how a Programming language classifies values and expressions into '''types''', how it can In Computer science and Computer programming, the term strong typing is used to describe those situations where Programming languages specify one or more Type inference, or implicit typing, refers to the ability to deduce automatically the type of a value in a Programming language. Implementation is the realization of an application or execution of a Plan, idea Model, Design, Specification, standard, Algorithm An operating system (commonly abbreviated OS and O/S) is the software component of a Computer system that is responsible for the management and coordination A website (alternatively web site or Web site, a back-construction from the Proper noun World Wide Web) is a collection of Web pages In Computer science, functional programming is a Programming paradigm that treats Computation as the evaluation of mathematical functions and Logic programming is in its broadest sense the use of mathematical logic for computer programming A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer. Haskell is a standardized Purely functional Programming language with non-strict semantics, named after the Logician Haskell Curry It merges elements of functional and logic programming, including constraint programming integration. Constraint programming is a Programming paradigm where relations between variables are stated in the form of constraints
It is nearly a superset of Haskell, lacking support mostly for overloading using type classes, which some implementations provide anyway as a language extension, such as the Münster Curry Compiler. In Computer science, polymorphism is a Programming language feature that allows values of different Data types to be handled using a
Contents |
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 (w. r. t. 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 “double 1” is replaced by 1+1. The latter can be replaced by 2 if we interpret the operator “+” to be defined by an infinite set of equations, e. g. ,1+1 = 2, 1+2 = 3, etc. In a similar way, one can evaluate nested expressions (where the subexpression 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. This indicates a fundamental property of declarative languages, also 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 declarative programs.
Obviously, these are not all possible evaluation orders since one can also evaluate the argument of double before applying its defining equation:
double '(1+2)' → 'double 3' → '3+3' → 6
In this case, we obtain the same result with less evaluation steps. . . .
As functional languages like Haskell do, Curry supports the definition of algebraic data types by enumerating their constructors. Haskell is a standardized Purely functional Programming language with non-strict semantics, named after the Logician Haskell Curry For instance, the type of Boolean values consists of the constructors True and False 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 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 a), is either the empty list “[]” or the non-empty list “e:l” consisting of a first element e and a list l:
data List a = [] | a : List a
The type “List a” is usually written as [a] and finite lists e1:e2:. . . :en:[] are written as [e1,e2,. . . ,en]. 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):
(++) :: [a] -> [a] -> [a] [] ++ 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 l and elements e, last l = e iff ∃xs:xs++[e] = l.
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 xs++[e] = [1,2,3] is solved by instantiating xs to the list [1,2] and e to the value 3. In Curry one can define the operation last as follows:
last l | xs++[e] =:= l = e where xs,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 “where. . . free” 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.