Some Things You Need to Know About Prolog

(that are not in Sebesta)

You can install Prolog on your own computer: either download the installer file "w32pl5010.exe" from the CIS3353 folder on the G:\ drive, or else get the latest version from the SWI-Prolog web site. The accompanying user manual is largely worthless unless you really want to exploit all the non-Prolog-like features in this implementation, such as access to C library code and system calls and the like. This version is also installed in the small Lab upstairs.

There are two important things to remember about Prolog in order to be successful in programming it:

1.  Prolog is intended to be a descriptive language, not prescriptive such as the procedural languages you are familiar with (Java, for example). That means, in principle, that you should be describing the mathematical relationships which describe the results you want, not how to get there. Recursive definitions work very well, just as they do in Scheme.

2.  Prolog is not really a pure descriptive language, it really does its search in a specific order. That means you need to be a little careful how you define those relationships. In a recursive definition, put the base case first: if that one fires, it won't even try the other cases. Mostly. Similarly, when you see (or write) a line with several assertions [like "doSomething(I), Ip1 is I+1, myforloop(Ip1, Mymax)" in the example below], the assertions are evaluated in order, left-to-right. The first one that fails causes it to backtrack to the last good assertion and try some other value if possible. Thus if "doSomething(I)" succeeds (is true), then it tries "Ip1 is I+1" (which will succeed unless the variable Ip1 already has some other value), then it tries the recursive call, and so on.

All that said, you still can think about solving your problem in terms of the same elemental concepts that work in every other language, but particularly the Lisp-like languages you now understand:

3.  Prolog has lists that you can disassemble and rebuild to effect recursion, just as in Lisp/Scheme. These are described in Sebesta.

4.  Iteration is accomplished by recursion. A Java for-loop

for (i=0; i<76; i++) {doSomething(i);}
would look like this in Prolog, where the last line represents how the loop is started by a "function call" somewhere else in your code (be sure to capitalize your variables):
myforloop(I, Mymax) :- I<Mymax, doSomething(I), myforloop(I+1, Mymax). %% recursive call.
myforloop(I, Mymax) :- I>=Mymax. %% loop termination condition
... myforloop(0,76)... %% initial call
5.  Assignment (if you can call it that, but it's not really), is permanent for a particular instantiation of a "function call" which is a rule. This version of Prolog does not evaluate arithmetic expressions where they are coded, it waits until you need to use the values. The obvious equality tests also don't evaluate these expressions, so if you had coded the termination condition above as  I=Mymax  it would have failed, because (as a trace would show, see below) your would be comparing (for example) "0+1+1+1=9" as strings. You can eliminate this hazard by assigning the arithmetic operation to a new local variable, thus:
myforloop(I, Mymax) :- I<Mymax, doSomething(I), Ip1 is I+1, myforloop(Ip1, Mymax).
because the assignment operator "is" does do the evaluation before assigning. The inequality relations (including ">=" as above) also evaluate their operands, but simple "=" does not. Go figure.

6.  Conditionals are built into the way the language evaluates rules: just put them in the order you want the conditions tested, as in the example above. Each separate rule line (with the same name) is tried in turn, until something works; all the previous lines that failed are as if they never executed at all. So the Java line

if(a<b) doThenPart(x); else doElsePart(y);
would be correspondingly coded in Prolog more like this (except with a more descriptive rule name and possibly a different choice of parameters):
myIfThenElse(A,B,X,Y) :- A<B, doThenPart(X).
myIfThenElse(A,B,X,Y) :- A>=B, doElsePart(Y).
Notice that the proliferation of if-then-else constructs in your code will make your Prolog program verbose and hard to read; you might consider rethinking your algorithm to reduce the number of them.

Finally, you need to be aware that Prolog will run your program until it finds a single solution, then stop (and display that answer if appropriate). To get a list of results requires some extra work. For one thing, the  is_integer(X)  function in Sebesta is not in SWI-Prolog, you must use the  between(Lo,Hi,P)  function, which does essentially the same thing without going on forever if it never succeeds. But to get more than one solution, you need to use the  findall(...)  function as a wrapper around the goal (think "function") that produces each result. Both of these are documented in the on-line help system. Here is an example of a Prolog program to generate a list of odd numbers between 0 and 8:

oddly(X) :- between(0,8,X), X mod 2 >0.
alloddnums(L) :- findall(N,oddly(N),L).
To make this work, I typed it into a text file with a name like "" and double-clicked it. You can then test this by typing in the line
Your programs won't work the first time, so type in
on a line by itself first before testing. Then hit the return key for each trace line to watch it go by.

Rev. 2003 April 15