There are different implementations of Curry
available^{2}^{2}Check 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]^{3}^{3}http://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 $\mathrm{c}$ then $\mathrm{e}\mathtt{}\mathrm{\_}\mathtt{}\mathrm{1}$ else $\mathrm{e}\mathtt{}\mathrm{\_}\mathtt{}\mathrm{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\mathrm{\_}1$, otherwise
it is the value of $e\mathrm{\_}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]:

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

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

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\mathrm{\_}1$ =:= $\mathrm{e}\mathtt{}\mathrm{\_}\mathtt{}\mathrm{2}$” denotes an
*equational constraint*
which is solvable whenever the expressions $e\mathrm{\_}1$ and $e\mathrm{\_}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]:

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\in \{1,2,3\}$ satisfying the equation $x+x=x*x$, we can solve this constraint ($c\mathrm{\_}1\mathtt{\text{\&}}c\mathrm{\_}2$ denotes the conjunction of the two constraints $c\mathrm{\_}1$ and $c\mathrm{\_}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.