David S. Warren - Programming in Tabled Prolog (XSB Prolog)

Next:

Now, we can load this definition into XSB and then call it in various ways to experiment with how it works. So we put this definition into a file called, say, appendfile.P. (The `.P' suffix indicates to XSB that this is a file containing source code.) We run XSB and then compile the file and load it into XSB by:

% xsb XSB Version 1.4.1 (94/11/21) [sequential, single word, optimal mode] | ?- [appendfile]. [Compiling ./appendfile] [appendfile compiled, cpu time used: 0.901 seconds] [appendfile loaded] yes | ?-

The XSB system top-level prompt is `| ?- ', which is printed when XSB is waiting for the user to enter something. Here we've entered the filename in a list. This requests the system to compile and load the indicated file, which the system then does. The compilation creates an object file, in this case named appendfile.O. Then the XSB loader is called to load that file into XSB's space. (If the last-change date of the object file is more recent than the last-change date of the source file, then the compiler is not called, but the object file is loaded.) So now we have the append program in XSB memory and we can ask XSB to execute it. We do this by entering a call at the top-level prompt, as follows:

| ?- append([a,b,c],[d,e],X). X = [a,b,c,d,e]

XSB calls the append procedure and executes it, passing the two lists in and when append returns, X has been assigned the answer, which XSB prints. It's possible that there is more than one answer (as would be the case with a_sqrt above), so XSB waits to let the user ask for another answer, if desired. To request another answer, the user enters a `;', to which XSB responds with the next answer, if any. Here the result is as follows:

| ?- append([a,b,c],[d,e],X). X = [a,b,c,d,e]; no | ?-

XSB has responded with `no' and then returned with the top level prompt. This is because, in this case, there is just one answer so asking for another results in the response of `no'.

We could, of course, ask for different invocations of append, giving it different lists, but we can also give different forms of invocations. The unification of Prolog allows us to call some procedures in perhaps a surprising variety of different ways.

For example, we can enter the following query (i.e., procedure invocation) and will get the indicated result from XSB:

| ?- append([a,b,c],[d,e],[a,b,c,d,e]). yes | ?-

Here we've given the answer. XSB simply verifies that the answer is correct, and indicates it is by responding `yes'. In this execution, unifications that set variable values in the previous execution simply verify that the variables already have the correct values. If the values don't check out, as they won't in this following case:

| ?- append([a,b,c],[d,e],[a,b,c,d]). no | ?-

XSB gives a response of `no' indicating that the first two arguments do not concatenate to form the third.

Actually, Prolog can respond to even stranger invocations of our append procedure. Consider the following invocation:

| ?- append(X,Y,[a,b,c]).

Here we are asking for what two values will concatenate together to form the list [a,b,c]. The tokens beginning with capital letters, X and Y, are variables, and we are asking the system to fill them in with correct values. (A variable starts with an upper-case letter, and an atom starts with a lower-case letter. We've been using this convention all along, and it is important to know.)

Prolog can answer this query reasonably. There are four possible pairs of lists that do concatenate together to produce [a,b,c], and Prolog will produce them:

| ?- append(X,Y,[a,b,c]). X = [] Y = [a,b,c]; X = [a] Y = [b,c]; X = [a,b] Y = [c]; X = [a,b,c] Y = []; no | ?-

Here XSB produced the first answer and then waited for my response. I responded with a ;, and it responded by producing the next answer. We continued until all the answers were produced. Since Prolog is nondeterministic, queries that have multiple correct answers are reasonable to ask. In this case Prolog answers the query correctly and reasonably.

Let's consider another simple (and well known) Prolog program known as member. Member is a binary predicate, i.e., it is a procedure with two arguments. It is given an element and a list, and it checks to see whether the element is a member of the list:

member(X,[X|L]). member(X,[Y|L]) :- member(X,L).

The first clause says that X is a member of a list whose head is X, an unexceptional statement. The second clause X is a member of a list if X is a member of the tail of the list.

Example executions of member are:

| ?- member(2,[1,2,3]).yes| ?- member(2,[1,3,4]).no| ?- member(X,[1,2,3]).X = 1;X = 2;X = 3;no| ?-

Notice that we can use member to generate all the elements of a list.

(Aside: If you tried to compile this member program exactly as it is written here, you noticed that the XSB compiler issued some warning messages. The first message says that the variable L in the first clause appears only once in that clause. Such a variable is called an anonymous variable. An anonymous variable is just a placeholder, since the value that it might get is never used anywhere else, because the variable appears nowhere else. In such cases you are encouraged to use a slightly different notation: instead of starting anonymous variables with upper-case letters, start them with underscores (_), or simply use an underscore alone. Each occurrence of the underscore symbol is a distinct (unnamed) variable. The compiler will not complain if you begin the name of an anonymous variable with an underscore. I strongly suggest following this convention; it will save untold grief that you'll otherwise suffer when you mistype variable names. So an equivalent, but syntactically improved, version of member is:

member(X,[X|_L]). member(X,[_Y|L]) :- member(X,L).

End of aside.)

As a final example of a simple Prolog list-processing predicate, consider the procedure reverse, which is given a list and returns a list that contains the elements of the input list, but in the reverse order.

reverse([],[]). reverse([X|L],R) :- reverse(L,RL), append(RL,[X],R).

The first clause says that if the input list is empty, then the resulting list is also the empty list. The second clause says that if the input list has head X and tail L, then first reverse the tail L of the input list obtaining RL, and then add X to the end of RL. The predicate append is used to add this element to the end of the reversed sublist. Notice that we must use [X] as the second argument of append, not just X, because append requires a list there, not an element.

An example of executing reverse is:

| ?- reverse([1,2,3],R).R = [3,2,1];no| ?-

exactly as expected. You might reasonably think that we should also be able to ask the following query:

| ?- reverse(X,[1,2,3]).X = [3,2,1];

And it looks as though everything works fine. However, what has really happened is that after the system produced the expected answer, I asked it for another answer. It should have simply said ``no'', but instead it went into an infinite loop and didn't respond at all. To understand why Prolog behaves like this, we have to understand more clearly exactly how it goes about evaluating queries.

[add an example to introduce ; and disjunction.]

---

Next:

David S. Warren
1999-07-31

Next:

Recall that above we described a conceptual model of how Prolog executes nondeterministic programs by talking of a growing and shrinking set of deterministic procedural machines. In order to completely understand how Prolog executes these nondeterministic programs, we must look more carefully at how this growing and shrinking set of machines is actually executed. Clearly Prolog is not executed by actually have a set of hardware machines that grows and shrinks. (While it would be nice, the physics of such machines has not yet been worked out.) Instead these multiple machines must somehow be simulated, or emulated, by a single hardware machine having just one processor.

Next page