Most of the programs discussed so far are functional. They declare data and/or define functions. An execution of the program is the functional-like evaluation of an expression. Curry is a functional logic programming language. It adds two crucial features to the model outlined above: non-determinism, which was discussed in Section 3.5.4, and logic variables, which are discussed in this section.
A logic variable differs from the variables introduced by the left-hand side of a rewrite rule. A variable introduced by the left-hand side of a rewrite rule, also called pattern variable, stands for any expression (of an appropriate type). For example, the following definition:
is read as “for all expressions and the head of (the list) (x:xs) is x.” Since Curry is strongly typed, the type of xs must be list, otherwise the program would be invalid, but no other conditions are imposed on xs.
A logic variable either is a variable occurring in an expression typed by the user at the interpreter prompt or it is a variable in the condition and/or right-hand side of a rewrite rule which does not occur in the left-hand side. We show an example of both. The operation “==”, called Boolean equality, is predefined in Curry. Hence, one can (attempt to) evaluate:
Prelude> z==2+2 where z free
Every variable in a query, such as “z” in the above example,
is a logic variable that initially is not bound to any value.
We will discuss shortly why queries with variables
may be useful and how variables are handled.
The second kind of logic variable is shown in the following
example:
The intuition behind the names tells that in a graph there exists a path from a node to a node if there exists an edge from the node to some node and a path from the node to the node . In the definition, both “a” and “z” are ordinary (rule) variables, whereas “b” is a logic variable. Variables, such as “b”, which occur in the condition and/or right-hand side of a rule, but not in the left-hand side, are also called extra variables. Extra variables are explicitly declared “free” in a “where” or “let” clause as shown in the example, or are anonymous.
The evaluation of expressions containing logic variables is a delicate issue and the single most important feature of functional logic languages. There are two approaches to deal with the evaluation of expressions containing logic variables: residuation and narrowing.
Let be an expression to evaluate and a variable occurring in . Suppose that cannot be evaluated because the value of is not known. Residuation suspends the evaluation of . If it is possible, we will address this possibility shortly, some other expression is evaluated in hopes that the evaluation of will bind a value to . If and when this happens, the evaluation of resumes. If the expression does not exists, is said to flounder and the evaluation of fails. For example, this is what would happen for the query we showed earlier:
Prelude> z == 2+2 where z free
*** Warning: there are suspended constraints (for details: ":set +suspend")
By contrast to residuation, if cannot be evaluated because the value of is not known, narrowing guesses a value for . The guessed value is uninformed except that only values that make it possible to continue the computation are chosen.
The operation “=:=”, called constrained equality, is predefined in Curry. This operation is similar to the Boolean equality discussed earlier except that it returns only True (if the equality can be satisfied) or it fails, i.e., it does not return False if both sides are not evaluable to identical values. Since this operation succeeds only if both sides have identical values, it also binds logic variables if this is necessary to make the sides identical. Thus:
Prelude> z =:= 2+2 where z free
{z=4} True
Therefore, this operation can be used to express an equational constraint that must be satisfied to compute some result.
Operations that residuate are called rigid, whereas operations that narrow are called flexible. All defined operations are flexible whereas most primitive operations, like arithmetic operations, are rigid since guessing is not a reasonable option for them. For example, the prelude defines a list concatenation operation as follows:
Since the operation “++” is flexible, we can use it to search for a list satisfying a particular property:
Prelude> xs ++ [3,4] =:= [1,2,3,4] where xs free
{xs=[1,2]} True
On the other hand, predefined arithmetic operations like the addition “+” are rigid. Thus, a call to “+” with a logic variable as an argument flounders:
Prelude> x + 2 =:= 4 where x free
*** Warning: there are suspended constraints (for details: ":set +suspend")
For ground expressions, i.e., expressions without logic variables, the flex/rigid status of a function makes no difference. In the context of concurrent/distributed object-oriented programming, rigid user-defined functions can be useful. For this purpose, there is a primitive operation ensureNotFree that evaluates its argument and suspends if it is a logic variable.
Often, programming with variables leads to conceptually simple, terse and elegant code at the cost of an acceptable loss of efficiency. The logic variables of a program and/or a query are not much different from the variables that are typically used to solve algebra or geometry problems. In both cases, some unknown entities of the problem are related to each other by expressions involving functions. Narrowing allows us to evaluate these expressions—and in the process to find values for the variables. The simplest application, and the most familiar for those used to solve algebra and geometry problems with variables, is when the expression to evaluate is an equation.
In later chapters, we will discuss some problems that are conveniently solved if one uses variables in computations. Here we want to present a simple, but non-trivial, motivating example. The problem is to parse a string that represents an expression. To keep the example small, our expressions are functional terms whose syntax is defined by:
term ::= identifier
| identifier ’(’ args ’)’
args ::= term
| term ’,’ args
identifier ::= any non-null string of alphabetic characters
For example, "f(g(a,b))" is a term described by the above syntax. When a term is represented as a string, answering questions such as how many arguments “g” has, is more complicated and less efficient than it needs to be. A parser converts a term from its string representation into a data structure that makes easy and efficient answering questions of that kind. Thus, the first step to build a parser is to design a suitable type to represent a term. Our choice is: [Browse Program][Download Program]:
Note that the occurrence of “Term” to right of the “=” character is a data constructor, whereas the two other occurrences are type constructors. The “Term” identifier is overloaded by the declaration.
Using this data structure, we represent a function identifier with a string and the function’s arguments with a list of terms. For example, the term "f(g(a,b))" would be represented as “Term "f" [Term "g" [Term "a" [],Term "b" []]]”. The following operation parses a term [Browse Program][Download Program]:
The elements of the program relevant to our discussion are the variables “fun” and “args”. The functional pattern in the first rule acts similarly to solving the equation “s =:= fun++"("++args++")"” in which “s” is the argument of “parseTerm”. The first condition of the first rule of the operation “parseTerm” instantiates these variables and ensures that “fun” is an alphabetic identifier. The operation “isAlpha”, defined in the library “Data.Char”, ensures that its argument, a character, is alphabetic. The operation “all” is defined in the “Prelude”. The combination “all isAlpha” ensures that all the characters of a string are alphabetic.
If a term has arguments, these arguments are parsed by the operation “parseArgs”. The overall design of this operation is very similar to that of “parseTerm”. In this case, though, a string is decomposed according to different criteria [Browse Program][Download Program]:
One could code more efficient versions of this parser. This version is very simple to understand and it is the starting point for the design of more efficient versions that will be discussed later in this book.