Assign-once Variables

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 + Head

The first line (preceding the :-) declares the name of the procedure and its formal parameters. The remaining lines (following the :-) 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, Head, and then calls sum recursively on the tail of the list, getting the sum of the rest of the list in the local variable TailSum. It then adds Head to 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 Sum 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 Sum variables.)

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 := X

We'll assume that neither X nor 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 X, so Y gets the value 5 as well. Now consider the following statements:

     X := 5
     X := Y

The first statement again assigns 5 to X. Now consider the second. 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 Y doesn't yet have a value. So the only reasonable thing to do is to set Y to be 5, i.e., to X's value. Note that this sequence of assignments has the same net effect that the previous sequence had.

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 := 5

Again assuming that X and Y start with no values, the first statement causes Prolog to bind X and Y together, 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 X and 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 -> and ;. Here we've said that Sum = 0; using the properties of symmetric assignment, we could just as well have said that 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 known as 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 Head and 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 [Head|Tail]. Head and 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 [Head|Tail] 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 is.

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 L1 and L2 is just L2. Otherwise, we let X be the head of the first list and L1t be its tail. Then we concatenate L1t and L2, using append recursively, to get L3t. Finally we add X to the beginning of L3t to construct the final result, L3.

Consider the following version of append:

    append(L1,L2,L3) :-
        L1 = [X|L1t]
         ->  L3 = [X|L3t],
             append(L1t,L2,L3t)
         ;   L3 = L2

This 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 to 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.