# CURRY An integrated functional and Logic Programming Language

CURRY is an experimental programming language which combines elements of the functional and logic programming paradigms. Based on Haskell, Curry was created to provide a common language for the research, teaching and application of integrated functional logic languages. Curry has the features of functional programming such as built in search, nested expressions, lazy evaluation and higher-order functions and features from logic programming such as concurrent evaluation of constraints on logical variables. (Antoy, 2007)CURRY has a compiler implementation method, since the programs are translated into machine language. However CURRY is hybrid implementation system, CURRY appears as an interpreter as it compilers the code on the fly. Once in the interpreter you can type expressions or you can load a file for pre existing expressions, or you can load a file of curry definitions, if no definitions are loaded the default is used.

Syntax and Types

CURRY does not have conditional execution, however it does have an if-then-else expression but it is not a control statement like other more popular languages such as C++ and Java. In these languages, “if” is a control statement and represents conditional execution.

if(boolean expression)

do this statement 1

else

do this other statement 2

In the above curry code the boolean expression and statements can all deal with different types. (Hanus, M , 2007)

All languages provide some way to perform arithmetic computations and standard arithmetic functions like addition (+) and multiplication (*) are predefined so the language can be used as a simple calculator. CURRY differs in how the if statement is represented. The “if” represents an expression so both parts of the “if” must have the same data type. For example the expression

x = if x<=0 then 0 else x

the x in the expression is treated as an numeric value.

Prelude> 3+5*4

Result: 23?

The above example shows the basic functionality of the environment an expression is entered and the value is displayed as a result with a question mark. The reason for this is that Curry can not perform functional and therefore purely deterministic computations which yield at most one result.

A Curry program is a set of functional definitions also known as rules or defining equations with the simplest form. Functions which do not depend on any input value, for example

ten = 5*2

the name ten is then defined as the value of 10. This can be extended to more complicated functions which require input arguments for example to find the cubed value of a given number

cubed x= x * x * x

Curry’s syntax is very similar to Haskell, the names of functions and parameters usually start with a lowercase letter followed by letter, digits and underscores (as above). Usual precedence rules apply to expressions like “2+5+5*5” (interpreted as ((2+5)+(5*5)) (Hanus, M , 2007)

The above features of the above Curry code can be combined to calculate the factorial of a natural number

fac n = if n==0 then 1

else n * fact(n-1)

(Antoy, 2007)

Note the exact layout of the function definition for several lines. If a definition flows onto several lines the next line must start in a column greater than the column where the previous line started, this is simple called the “layout” or off-side rule. In the above code functions are defined by rules like in maths without providing type declarations. In Java for example

int variableName = 1;

Despite this Curry is not an untyped language, Curry is actually a strongly typed language expressions like

3 * True

fac True

or using the previous function would be rejected by the compiler. Although type notations such as int or string are not written by the programmer, they are automatically inferred

by the compiler using a type inference algorithm. (Antoy, 2007) However it is important to document the intended use of the functions for example the factorial fac  uses integers so its type can be specified by

fac :: Int -> Int

A useful feature of curry and most functional and logic programming languages, is the ability to define functions in a pattern-oriented style. This means that we can define a function by several rules. Each with a different pattern

not False = True

not true = false

Whilst this may appear cryptic to some it actually makes more complex data structures clearer.

When comparing Cury to other functional languages such as LISP one of the distinguishing features is the ability to search for solutions. By using the underscore character “_” blank or missing entries can be entered also known as an anonymous variable.

False && _ = False

True && x = x

False || x = x

True || _ = True

Not False = True

Not True = False

We can use these definitions to compute the value just as normal ie

True && (True || ( not True))

Result >True ?

We can take this function further because of the defined anonymous values.

x && (y || (not x)) where x,y free

Free variables in goal: x, y

Result True

Bindings:

x = True

y= True?

The x and y variables are contained in the expression as arguments. To detect typos, free variables are declared by “where free” clause at the end of the expression.

Different solutions can be found by typing the enter key after the question mark, until No more solutions is displayed. (Hanus, M , 2007)

If we want to find a specific solution and reverse engineer the solution we simply add =:= True

x && (y || (not x)) =:= True where x,y free

Free variables in goal: x, y

Result: success

Bindings:

x=True

y=True ? ;

No more solutions.

# Lazy Evaluation

Unlike C and Java, Curry is lazy for the computation of any expression. Also referred to as lazy evaluation, any computation involved is delayed until the expression’s value is actually needed. C and Java only use this evaluation strategy for Boolean expressions named short circuit. The opposite of lazy evaluation is what many programming languages evaluation of the arguments of a function are called eagerly.

For example

4 + cubed (2+3)

is replaced by

4 +(2+3) * (2+3) *(2+3)

and not

4 +(5) * (5) *(2+3).

An evaluation of an expression is the process of obtaining the value from the expression. A value is an expression consisting of only built-in literals and /or data constructors. Due to the semantics of Curry; Curry guarantees that any value obtained from an expression is eventually obtained; this is referred to as completeness of evaluation. (source)

To ensure completeness expressions must be evaluated lazily. Which means a sub expression is evaluated only if it’s unavoidable to obtain a result.

An expression may contain several distinct replaceable sub-expressions or in simple terms we maybe able to write the expression in a different way. For example

from n = n

from (n+1)

An attempt to evaluate from 1 would abort with a memory overflow since the result is an infinite term. 1 +1 =2, 2+1 = 3 etc

However using the from function in the following manner is perfectly legal.

Nth n (x:xs)= if n ==1 then x else nth ( n -1) xs

The expression nth 3 (from 1)

Results in 3

A result is found because only the third number of from 1 is needed, and therefore do not need to be evaluated.

Lazy evaluation makes Curry very powerful in the realms of infinite data structures. Programs that use infinite structure are often simpler than programs for the same problem that use finite structures. For example a function that computes a finite prefix of 1 – 100 is more complicated than the “from” expression. Furthermore the expressions of the program are less interdependent and are therefore more reusable.

# Logical Variable

A logical variable is a variable in the condition, such as the where condition or is a variable that occurs on the right hand side of a expression but does not occur on the left hand side. The previous example

x && (y || (not x)) =:= True where x,y free

In the above example x and y are logic variables since they are being using in a where condition.

Another example were a condition is typed in the expression can be seen below.

z== 2+2 where z free

This syntax is similar to SQL Structured Query Language as conditions can be set and the answer is retrieved.

The second kind of logic variable is shown below

path a z = edge a b && path b z where b free

The names of the expression says there is a path from node a to node z. if there is an edge from node a to some node b as well as a path from node b to node z. In the above example the z is a logic variable that is not initially to any value. “a” and z are ordinary variables where b is a logic variable or an extra variable. These variables must be explicitly declared free in a “where” or “let” clause as shown above.

When evaluating expressions such as the examples above and curry finds a logic variable like the b, the idea of residuation and narrowing occurs.

With residuation, the evaluation is suspended so if there is a value that can be evaluated to provide the value of x or y then the evaluation of the original expression can be resumed otherwise the expression is said to flounder.

Alternatively another evaluation strategy is narrowing a value for the unknown variable is guessed. The guess is based on what will make it possible for the next part of the evaluation to proceed.

Operation in curry can be rigid or flexible. By default curry IO and arithmetic operations rigid these are operations that residuate as discussed above. Others are flexible but this can be altered using the eval declaration.

infixr 5 +++

(+++) eval rigid

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

[] +++ ys = ys

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

rigidApp> X +++ [3,4] =:= [1,2,3,4]

Free variables in goal: X

*** Goal suspended (use ":set +suspend" for details)!

Bindings:

X=_1643

rigidApp> X ++ [3,4] =:= [1,2,3,4]

Free variables in goal: X

Result: success

Bindings:

X=[1,2] ?

rigidApp>

In the above example +++ is declared as rigid so it will behave differently from (++).

The operator =:= is called constrained equality. It does not return a boolean value but instead either succeeds or fails. So for the flexible ++ above, it should read: find a value for X such that the result of comparing the append of X and [3,4] to [1,2,3,4] will succeed. The guess that will be made for X is based on what will allow the computation to continue. In the above example the computation will continue as long as =:= does not return fail.

# Higher-order functions

In arguments or inputs of a function can be functions themselves. This feature is banned or restricted by many programming languages. C only pointers can be used to achieve this function and C++ uses templates and java uses interfaces. However like the scripting language PHP (Hypertext Preprocessor). No special construct is needed.

A function that takes an argument of function type is referred to as a higher-order function. This feature is powerful, this is shown in the short example below.

A list of numbers is sorted into ascending order.

sort []   = []  //creates list

sort (x: xs)  = insert x (sort xs) //sort function has a logic variable

insert x [] = [x]

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

| otherwise = y : insert x ys

sort (<=) [3,5,1,2,7,9,8,6]

Result [1,2,3,4,5,6,7,8,9] ?

In the above expression <= is placed in brackets since they are the functional arguments, without them the expression would test whether sort is less than or equal ie “<=” to [3,5,1,2,7,9,8,6] which is irrelevant.

# Pattern Matching

Pattern matching allows code to be simplified creating making it easier to code and understand. For example a function which negates a boolean is shown below

not True = False

not False = True

Most languages such as java which does not have pattern matching but relies on conditional expression would have to define the above function like so

public boolean not (boolean x)

{

if (x)

{

return false;

}

else{

return true

}

}

# References

Antoy, S. (2007) Curry A Tutorial Introduction Retrieved 17th May 2008 From http://www.informatik.uni-kiel.de/~curry/tutorial/tutorial.pdf

Antoy, S. (2007) Functional Logic Programming 17th May 2008 From http://web.cecs.pdx.edu/~antoy/Courses/syllabi/WIN206CS510FLP.html

Antoy, S. (2007) Curry Features 17th May 2008 From http://grace.evergreen.edu/cnc/curry/lect/lec.3.html

Hanus, M., Antoy, S., Brabel B., Engelke, M., Hoppner K., Koj  J., Niederau O.,Steiner. PAKCS: The Portland Aachen Kiel Curry System Retrieved 15th May 2008, from http://www.informatik.uni0kiel.de/~pakcs/

Hanus, M.. The integration of functions into logic programming: From theory to practice Journal of Logic Programming 19 & 20 (pg583-628).