I Language Features

Chapter 2 Getting Started with Curry

There are different implementations of Curry available22Check the web page http://www.curry-lang.org for details.. As such we can not describe the use of a Curry system in general. Some implementations are batch-oriented. In this case a Curry program is compiled into machine code and then executed. In this introduction we prefer an implementation that supports an interactive environment which provides faster program development by loading and testing programs within the integrated environment.

PAKCS (Portland Aachen Kiel Curry System) [12]33http://www.informatik.uni-kiel.de/~pakcs contains such an interactive environment so that we show the use of this system here in order to get started with Curry. When you start the interactive environment of PAKCS (e.g., by typing “pakcs” as a shell command), you see something like the following output after the system’s initialization:

  ______      __       _    _    ______   _______
 |  __  |    /  \     | |  / /  |  ____| |  _____|   Portland Aachen Kiel
 | |  | |   / /\ \    | |_/ /   | |      | |_____    Curry System
 | |__| |  / /__\ \   |  _  |   | |      |_____  |
 |  ____| / ______ \  | | \ \   | |____   _____| |   Version 2.1.2-b8
 |_|     /_/      \_\ |_|  \_\  |______| |_______|
Curry2Prolog(swi 8.1) Compiler Environment (Version of 2019-08-12)
(RWTH Aachen, CAU Kiel, Portland State University)
Type ":h" for help (contact: pakcs@curry-lang.org)
Prelude>

Now the system is ready and waits for some input. By typing “:q” (quit) you can always leave the system, but this is not what we intend to do now. The prefix of the current input line always shows the currently loaded module or program. In this case the module Prelude is loaded during system startup. The standard system module Prelude contains the definition of several predefined functions and data structures which are available in all Curry programs. For instance, the standard arithmetic functions like +, * etc are predefined so that we can use the system as a simple calculator (the input typed by the user is underlined):


Prelude> 3+5*4
23

In this simple example you can already see the basic functionality of the environment: if you type an expression, the system evaluates this expression to a value (i.e., an expression without evaluable functions) and prints this value as the result. Now you can type additional expressions to be evaluated. For instance, you can compare the values of two expressions with the usual comparison operators >, <, <=, >=:


Prelude> 3+5*4 >= 3*(4+2)
True

== and /= are the operators for equality and disequality and can be used on numbers as well as on other datatypes:


Prelude> 4+3 == 8
False

One may want to use Curry as more than a mere desk calculator. Therefore, we will discuss how to write programs in Curry. In general, a Curry program is a set of function definitions. The simplest sort of functions are those that do not depend on any input value, i.e., constant functions. For instance, a definition like

nine = 3*3

(such definitions are also called rules or defining equations) defines the name nine as equal to the value of 3*3, i.e., 9. This means that each occurrence of the name nine in an expression is replaced by the value 9, i.e., the value of the expression “4*nine” is 36.

Of course, it is more interesting to define functions depending on some input arguments. For instance, a function to compute the square value of a given number can be defined by

square x = x*x

Now it is time to make some remarks about the syntax of Curry (which is actually very similar to Haskell [20]). The names of functions and parameters usually start with a lowercase letter followed by letters, digits and underscores. The application of a function f to an expression e is denoted by juxtaposition, i.e., by “fe”. An exception are the infix operators like + or * that can be written between their arguments to enable the standard mathematical notation for arithmetic expressions. Furthermore, these operators are defined with the usual associativity and precedence rules so that an expression like “2+3+4*5” is interpreted as ((2+3)+(4*5)). However, one can also enclose expressions in parenthesis to enforce the intended grouping.

If we write the definitions of nine and square with a standard text editor into a file (note that each definition must be written on a separate line starting in the first column) named “firstprog.curry” ([Browse Program][Download Program]), we can load (and compile) the program into our environment by the command


Prelude> :l firstprog

which reads and compiles the file “firstprog.curry” and makes all definitions in this program visible in the environment. After the successful processing of this program, the environment shows the prefix to the input line as


firstprog>

indicating that the program “firstprog” is currently loaded. Now we can use the definitions in this program in the expressions to be evaluated:


firstprog> square nine
81

If we change our currently loaded program, we can easily reload the new version by typing “:r”. For instance, if we add the definition “two = 2” to our file “firstprog.curry”, we can reload the program as follows:


firstprog> :r

firstprog> square (square two)
16

Functions containing only a single arithmetic expression in the right-hand side of their defining equations might be useful abstractions of complex expressions but are generally only of limited use. More interesting functions can be written using conditional expressions. A conditional expression has the general form “if c then e_1 else e_2” where c is a Boolean expression (yielding the value True or False). A conditional expression is evaluated by evaluating the condition c first. If its value is True, the value of the conditional is the value of e_1, otherwise it is the value of e_2. For instance, the following rule defines a function to compute the absolute value of a number:

absolute x = if x>=0 then x else -x

Using recursive definitions, i.e., rules where the defined function occurs in a recursive call in the right-hand side, we can define functions whose evaluation requires a non-constant number of evaluation steps. For instance, the following rule defines the factorial of a natural number [Browse Program][Download Program]:

fac n = if n==0 then 1
                else n * fac(n-1)

Note that function definitions can be put in several lines provided that the subsequent lines start in a column greater than the column where the left-hand side starts (this is also called the layout or off-side rule for separating definitions).

You might have noticed that functions are defined by rules like in mathematics without providing any type declarations. This does not mean that Curry is an untyped language. On the contrary, Curry is a strongly typed language which means that each entity in a program (e.g., functions, parameters) has a type and ill-typed combinations are detected by the compiler. For instance, expressions like “3*True” or “fac False” are rejected by the compiler. Although type annotations need not be written by the programmer, they are automatically inferred by the compiler using a type inference algorithm. Nevertheless, it is a good idea to write down the types of functions in order to provide at least a minimal documentation of the intended use of functions. For instance, the function fac maps integers into integers and so its type can be specified by

fac :: Int -> Int

(Int denotes the predefined type of integers; similarly Bool denotes the type of Boolean values). If one is interested in the type of a function or expression inferred by the type inference algorithm, one can show it using the command “:t” in PAKCS:


absfac> :t fac
fac :: Int -> Int
absfac> :t  fac 3
fac 3 :: Int

A useful feature of Curry (as well as most functional and logic programming languages) is the ability to define functions in a pattern-oriented style. This means that we can put values like True or False in arguments of the left-hand side of a rule and define a function by using several rules. The rule that matches the pattern of left-hand side will be called. For instance, instead of defining the negation on Boolean values by the single rule

not x = if x==True then False
                   else True

we can define it by using two rules, each with a different pattern (here we also add the type declaration):

not :: Bool -> Bool
not False = True
not True  = False

The pattern-oriented notation becomes very useful in combination with more complex data structures, as we will see later.

One of the distinguishing features of Curry in comparison to functional languages is its ability to search for solutions, i.e., to compute values for the arguments of functions so that the functions can be evaluated. For instance, consider the following definitions of some functions on Boolean values contained in the prelude (note that Curry also allows functions defined as infix operators, i.e., “x && y” denotes the application of function && to the arguments x and y):

False && _  =  False
True  && x  =  x
~
False || x  =  x
True  || _  =  True
~
not False   =  True
not True    =  False

The underscore “_” occurring in the rules for && and || denotes an arbitrary value, i.e., such an anonymous variable is used for argument variables that occur only once in a rule.

We can use these definitions to compute the value of a Boolean expression:


Prelude> True && (True || (not True))
True

However, we can do more and use the same functions to compute Boolean values for some (initially unknown) arguments:


Prelude> x && (y || (not x))  where x,y free
{x=True, y=True} True
{x=True, y=False} False
{x=False, y=y} False

Note that the initial expression contains the free variables x and y as arguments. To support the detection of typos, free variables in initial expressions must be explicitly declared by a “where…free” clause at the end of the expression. Free variables denote “unknown” values. They are instantiated (i.e., replaced by some concrete values) so that the instantiated expression is evaluable. As we have seen above, replacing both x and y by True makes the expression reducible to True. Therefore, the Curry system shows in the first result line True together with the bindings (i.e., instantiations) of the free variables it has done to compute this value.

In general, there is more than one possibility to instantiate the arguments, e.g., the Boolean variables x and y can be instantiated to True or False. This leads to different solutions which are printed one after the other as shown above: there is one instantiation for x and y so that the instantiated expression evaluates to True, and there are two instantiations so that the instantiated expression evaluates to False. The last result line shows that the initial expression has the value False provided that x is instantiated to False but y can be arbitrary (i.e., y is not instantiated).

As we have seen, PAKCS evaluates and shows all the values (also called solutions if variables are instantiated) of an initial expression. This default mode can be changed by the command “:set +interactive”. In the interactive mode, we are asked after each computed value how to proceed: whether we want to see the next value (“yes”), no more values (“no”), or all values without any further interaction (“all”). Thus, we can show the values of the initial expression step-by-step as follows (note that it is sufficient to type the first letter of the answer followed by the “enter” key):


Prelude> :set +interactive
Prelude> x && (y || (not x))  where x,y free
{x=True, y=True}  True
More values? [Y(es)/n(o)/a(ll)] y
{x=True, y=False} False
More values? [Y(es)/n(o)/a(ll)] y
{x=False, y=y} False
More values? [Y(es)/n(o)/a(ll)] y
No more values.

The final line indicates that there are no more values to the initial expression. This situation can also occur if functions are partially defined, i.e., there is a call to which no rule is applicable. For instance, assume that we define the function pneg by the single rule [Browse Program][Download Program]

pneg True = False

then there is no rule to evaluate the call “pneg False”:


bool> pneg False
*** No value found!

As we have seen in the Boolean example above, Curry can evaluate expressions containing free variables by guessing values for the free variables so that the expression becomes evaluable (the concrete strategy used by Curry will be explained later, but don’t worry: Curry is based on an optimal evaluation strategy [1] that performs these instantiations in a goal-oriented manner). However, we might not be interested to see all possible evaluations but only those that lead to a required result. For instance, we might be only interested to compute instantiations in a Boolean formula so that the formula becomes true, e.g., as in solving an equation.

For this purpose, Curry offers constraints, i.e., formulas that are intended to be solved (instead of computing an overall value). One of the basic constraints supported by Curry is equality, i.e., “e_1 =:= e_2” denotes an equational constraint which is solvable whenever the expressions e_1 and e_2 (which must be of the same type) can be instantiated so that they are evaluable to the same value. For instance, the constraint “1+4=:=5” is solvable, and the constraint “2+3=:=x” is solvable if the variable x is instantiated to 5. Now we can compute positive solutions to a Boolean expression by solving a constraint containing True on one side:


Prelude> (x && (y || (not x))) =:= True  where x,y free
{x=True, y=True} True

Curry allows the definition of functions by several rules and is able to search for several solutions. We can combine both features to define operations that yield more than one result for a given input. Such operations are called non-deterministic operations. A simple example for a non-deterministic operation is the following function choose which yields non-deterministically one of its arguments as a result [Browse Program][Download Program]:

choose x y = x
choose x y = y

With this function we could have several results for a particular call:


choose> choose 1 3
1
3

We can use choose to define other non-deterministic operations:

one23 = choose 1 (choose 2 3)

Thus, a call to one23 delivers one of the results 1, 2, or 3. Such a function might be useful to specify the domain of values for which we want to solve a constraint. For instance, to search for values x{1,2,3} satisfying the equation x+x=x*x, we can solve this constraint (c_1&c_2 denotes the conjunction of the two constraints c_1 and c_2):


choose> x=:=one23 & x+x=:=x*x  where x free
{x=2} True

The advantages of non-deterministic operations will become clear when we have discussed the (demand-driven) evaluation strategy in more detail.

This chapter is intended to provide a broad overview of the main features of Curry and the use of an interactive programming environment so that one can easily try the subsequent examples. In the next chapter, we will discuss the features of Curry in more detail.