By saying that Prolog has assign-once variables, I mean that any particular variable in a Prolog procedure can only ever get one value assigned to it. A Prolog variable at any point in execution either has a value, which can thereafter never be changed, or it has not yet been given a value. This may seem to be an incredibly strong restriction. In Pascal, for instance, one usually programs by setting a variable's value and then changing it during the execution of the program. For example, to sum up an array of numbers, one sets the accumulator variable to 0 and the loop variable to 1, and then increments the loop variable to step through the array modifying the accumulator at each step. How in the world could this be done with assign-once variables? The secret is that it can be done easily through the use of recursion.
So let's write a simple Prolog program to see how we can do something interesting with only assign-once variables. Let's consider the problem of adding up the numbers in a list. Prolog is a list-processing language, similar to Lisp. Its primary data structure is the tree (called a term), a very common form of which is the list. There are three basic data types in Prolog: 1) integers, 2) floating point numbers, and 3) atoms. The first two should be self-explanatory. Atoms are simply symbols that represent themselves. Prolog terms (trees) are constituted of integers, floats, atoms and other terms.
A list in Prolog is written with square brackets and with its elements separated by commas. For example the following are lists:
[1,2,3] [aa,bbb,d]  [[2,b],or,not,[2,b]]The first is a list of integers, the second a list of atoms, the third is the empty list consisting of no elements, and the fourth is a list containing four elements, the first and last being themselves lists.
So let's now write a program in a made-up procedural language (that is not Prolog, but somewhat similar) and see if we can sum up the elements of an integer list with assign-once variables.
sum(List,Sum) :- if List =  then Sum := 0 else Head := head(List) Tail := tail(List) sum(Tail,TailSum) Sum := TailSum + HeadThe first line (preceding the
:-) declares the name of the
procedure and its formal parameters. The remaining lines (following
:-) make up the body of the procedure definition. We have
assumed the existence of two functions, head and tail, to extract the
first element of a list, and the remainder of the list after the head
is removed, respectively. Sum is a recursive procedure. It takes a
list of numbers as its first argument and returns the sum of the
numbers in its second. It first checks to see if the list is empty.
If so, it sets the sum to 0 and returns directly. If not, it saves
the first element of the list in a local variable,
sum recursively on the tail of the list, getting the
sum of the rest of the list in the local variable
TailSum to get the value for
Sum, which it sets and returns. Notice that no single variable
gets two different values. The variable
Sum is not set and
then changed; each recursive invocation has a different
variable and each gets set only once, to its appropriate partial sum.
Note also that the loop variable in the iterative version of summing
an array is here replaced by the variables containing each sublist.
So here too there is no need to have multiply assigned variables.
Instead of one variable getting many values, we can instead uses many
variables, each getting one value. (Let me point out for those of you
who may be worried about efficiency that this is a conceptual point;
it may well be that the underlying implementation of such a program
would actually use just one location for all the
So we see that we are able get by in this case with assign-once variables. It turns out that this idea of using recursion and the multiple variables at the different recursion levels is very general. This is not just a trick that works in this case only, but is an example of a very general technique.
Now having assign-once variables gives rise to a very interesting phenomenon: assignment can be symmetrical in Prolog. That is, Prolog doesn't have to treat the left and the right sides of an assignment differently, as must be done in normal procedural languages such as Pascal or C. As a matter of fact, Prolog doesn't have to treat tests and assignments differently either. I.e., Prolog doesn't need two operators, say == for testing and = for assignment as C does; it needs only one.
Let's first consider assignment. Consider the following assignments:
X := 5 Y := XWe'll assume that neither
Y have been assigned a
value before this sequence is executed. So
X gets the value 5
by the first statement, and then
Y is assigned the value of
Y gets the value 5 as well. Now consider the
X := 5 X := YThe first statement again assigns 5 to
X. Now consider the
X has the value 5 and
Y has no value. Since
Prolog is an assign-once language,
X can get only one value and
it already has it, so we know we can't change it. But
doesn't yet have a value. So the only reasonable thing to do is to
Y to be 5, i.e., to
X's value. Note that this
sequence of assignments has the same net effect that the previous
This suggests how we can treat both sides of an assignment in the same way. If one of the variables has a value and the other doesn't, then assign the value that the one has to the other. If neither variable has a value yet, then make it so that whenever one of them gets a value, the other gets that same value. If they both have a value, then if it's the same value, then the assignment is a no-op. If the two values are different, then there is a problem since neither can get a new value. In this case we say the computation fails. (We will talk more about failure later.)
Notice that this definition of ``assignment'' means that any ordering of the same (or symmetric) assignments gives the same result. For example, consider the different ordering of our assignments above:
X := Y X := 5Again assuming that
Y start with no values, the
first statement causes Prolog to bind
so that whenever one of them gets a value, the other will also get
that same value. Then the second statement causes
X to get the
value 5, and so
Y gets that value, too. So after these two
assignments are executed, both
Y have the value 5,
exactly as they do after the previous two versions of these
assignments. This is also a very general phenonemon: with this
meaning of assignment, any ordering of any set of assignments gives
the same result.
So let's rewrite our sum program with these ideas in mind. We will use = for our symmetric assignment statement. (From now on, all our programs will be syntactically correct Prolog, and XSB, programs, so you can type them into XSB and try them out. [sidebar] to explain how to create files, consult them, and run defined predicates).
sum(List,Sum) :- List =  -> Sum = 0 ; List = [Head|Tail], sum(Tail,TailSum), Sum is TailSum + Head.I've changed the syntax for if-then-else to Prolog's syntax, using
;. Here we've said that
Sum = 0; using
the properties of symmetric assignment, we could just as well have
0 = Sum. Consider the symmetric assignment:
List = [Head|Tail]. The structure on the right is how one
constructs a list from a head element and a tail list. (In Lisp it is
cons.) So our symmetric assignment here is even more
powerful. We know that the variable
List has a list as its
value. So this assignment assigns both variables
Tail so that they get the values of the first element of
List and the tail of
List, respectively. We can see
that symmetric assignment is here extended to matching. We match the
value in the variable
List, which is a list, to the structure
Tail are the only variables
without values, so the symmetric assignment will fill them in with the
appropriate values to make the
List and the
structure the same. This matching process, which we have been
referring to as ``symmetric assignment'', is called unification.
Notice that we've used the same operation of unification,
List = , in the test of the if-then-else. Here we see a use of failure.
Recall that we said that if a symmetric assignment cannot be made
because the two sides have values that are different, then the
assignment (or unification) fails. The if-then-else construct does
the unification and if it succeeds, then it executes the then
statement (which follows the
->); if it fails, it executes the
else statement (which follows the
;.) So even the boolean test
of an if-then-else can use our universal unification operation.
Notice, however, that we have not used unification for the last
statement that adds Head to the partial sum. This is because here we
don't want to match the two sides, since Prolog considers the right
side to be a tree (with + at the root and with two leaves of TailSum
and Head.) So here we must use an operation that explicitly asks for
the tree on the right to be evaluated as a numeric expression. In
Prolog that operation is named
As another example, consider the append procedure:
append(L1,L2,L3) :- L1 =  -> L3 = L2 ; L1 = [X|L1t], append(L1t,L2,L3t), L3 = [X|L3t].This is a procedure that takes two lists and concatenates them together, returning the resulting list in its third argument. This definition says that if the first list is empty, then the result of concatenating
L2 is just
X be the head of the first list and
L1t be its
tail. Then we concatenate
L2, using append
recursively, to get
L3t. Finally we add
X to the
L3t to construct the final result,
Consider the following version of append:
append(L1,L2,L3) :- L1 = [X|L1t] -> L3 = [X|L3t], append(L1t,L2,L3t) ; L3 = L2This one looks rather strange, but it also works. We've used the boolean test unification also to deconstruct the list. (This is probably a poor idea in real Prolog programming.) The other perhaps stranger (but less bad) difference is that we've moved the construction of the output list
L3 to before the recursive call
append. You might wonder how we can construct a list before
we have its components. But with unification, that works just fine.
The intuition is that if a variable can get only one value, it doesn't
really matter when it gets it. So it is often the case that
unifications can be moved earlier. What happens here is that the list
cell is constructed before the call to
append, and then the
recursive call to
append will fill in the tail of that cell
with the appropriate value.
We've looked at assign-once variables and seen how they lead to symmetric assignment, which leads to unification. Next let's consider the other unusal property of Prolog programs, the fact that they can be nondeterministic.