USING G-PROLOG
I. OVERVIEW
G-Prolog is designed for easy use so that a user can spend as
little time as possible learning about this particular interpreter,
and as much time as possible learning about Prolog. For an overview
of the language and how this interpreter works read the file
INTERP.DOC.
The first step in using the interpreter is finding or writing a
database file. This file is an ordinary ASCII file, and can be
created on any text editor. A number of sample database files are
included on your disk, and should give you a good idea of what
G-Prolog looks like. Read the file SAMPLES.DOC for an explanation of
what the files are and how they work.
Once you've got your hands on a source file, G-Prolog can be
invoked to interpret the file. Double-click on GPROLOG.PRG and select
which database you want to work on from the file selector box. Note:
Both G-PROLOG and the Prolog database must be in the root directory of
the drive you are running the program from.
Once invoked, G-Prolog will go to work, trying to prove the body
of the first clause in the database. If you've asked for a trace, the
interpreter will give you a blow-by-blow account of what it's doing.
Otherwise, it will simply go about its business, asking for input or
writing something on the screen when required to do so, and finally,
reporting either success or failure.
II. IDENTIFIERS
Identifiers in G-Prolog are very free-form. An identifier can be
any string of legitimate ASCII characters, and is delimited by one of
nine characters: double quote, "(", ")", space, "[", "]", comma, tab,
and period. This means that
x, y, identifier, arg_1
are all legal identifiers, as you'd expect, and so are
___, &, #!#, and }}}}}}
albeit funny-looking ones.
Finally, keep in mind that G-Prolog is completely case-sensitive:
"name," "Name," and "NAME" are all entirely different identifiers.
III. COMMENTS
Comments must be placed on a line by themselves and are preceeded
by a "%." So the following is a comment, and is ignored by the
interpreter:
%This line is a comment.
IV. SYNTACTIC CONVENTIONS
Aside from two system commands to be explained momentarily, there
is only one construct in G-Prolog -- the clause. A clause looks like
this:
term [:- term1,term2,...,lastterm].
(In this and all explanations of syntax, the parts in square
brackets are optional.) Terms in the clause can be separated by any
number of spaces and tabs; commas aren't actually necessary, but they
look nice. The terms can be distributed over any number of lines.
However, individual identifiers can't be split between two lines.
Notice that clauses are terminated by a period.
An individual term looks like this:
predicate[(arg1,arg2,...,lastarg)]
Again, the part in parentheses -- the arguments -- is optional,
since some predicates don't have arguments. As with terms, arguments
can be separated by blanks, tabs, or commas, and can be distributed
over several lines. The left parenthesis must immediately follow the
predicate name.
Finally, the arguments may be one of three types. First, they
may be terms themselves, either with or without arguments.
Second, they may be strings, which are sequences of ASCII
characters and screen control characters delimited by double quotes
("). So, for example, the following is a legitimate string:
"this is a string\n"
The screen control characters are borrowed from the C language,
and are described below:
Control characters Meaning
\nnn sends the decimal number nnn to the console
\a beep
\b backspace
\t tab
\n line feed
\v vertical tab
\f form feed
\r carriage return
\" double quote
\' single quote
\\ backslash
The third type of argument is a list, which is just what it
sounds like. A list is a sequence of identifiers delimited by square
brackets. The following are all legal lists:
[a,b,c], [1,2,3] [tree apple pear] []
Notice that, once again, simple spaces are legitimate separators,
and that "[]", the empty list, is a legitimate list.
V. VARIABLES
G-Prolog needs to know which identifiers are variables and which
are constants. An identifier is assumed to be a constant unless it is
declared to be a variable. Identifiers can be declared as variables
either explicitly or implicitly. An explicit declaration is made with
the VARIABLES system command. The word VARIABLES (all capitals) must
be the first word on a line, and must be followed immediately by a
left parenthesis. All identifiers between the left and right
parentheses are then declared to be variables. The following is an
example of a legitimate VARIABLES declaration:
VARIABLES(x,y,z)
In this case, x, y, and z are all declared as variables.
An implicit declaration arises from the identifier itself. All
identifiers beginning with a "_" are treated as variables, and don't
need to be declared. So, the following are all variables, even though
no VARIABLES declaration is made:
_head, _name, _x
VI. TRACE
G-Prolog includes a trace feature which allows the user to follow
the interpreter's progress. It is invoked by placing somewhere in the
source file the system command "TRACE" as the first item on a line.
If trace is invoked, the interpreter will report at each stage in its
progress the goals remaining to be proven, the clauses with which it
is unifying, and the times when it back-tracks.
Notice, incidentally, that the output of trace doesn't look quite
like the source file. The ":-" is eliminated, and the first
parenthesis of a term occurs before the predicate, not after it.
These slight changes are due to the way G-Prolog stores clauses
internally.
VII. BUILT-INS
G-Prolog includes nineteen built-in predicates. Each is
described below.
A. head(variable,list)
Returns the first element of a list, either an atom or another
list. If the variable is unbound, it is bound to the head.
Otherwise, it is compared to the head, and the clause succeeds or
fails based on this comparison.
Example: head(x,[this is a list]) binds x to "this."
B. tail(variable,list)
Returns the tail of a list, the part remaining when the head is
removed. If the variable is unbound, it is bound to the tail.
Otherwise, it is compared to the tail, and the clause succeeds or
fails based on this comparison.
Example: tail(x,[this is a list]) binds x to [is a list].
C. read(variable)
Puts a "?" on the screen, waits for the user to enter a string
followed by a , and binds the variable to the string. Notice
that lines read from the console are parsed exactly like lines read
from the database file, and must be entered in exactly the same form.
Example: see "write" below.
D. write(variable|string,variable|string...variable|string)
Writes the sequence of variables/strings to the screen. If a
variable is bound to something, its value is printed; otherwise, the
variable itself is printed. Strings are printed exactly as they
appear, and are not interpreted (except insofar as the screen control
characters described above are interpreted and not printed out
literally).
Examples: write("this is a string") -> this is a string
write("this \tis a string") -> this is a string
write("the answer is ",x) -> the answer is 3 (assuming, of
course, that x is bound to 3)
read(x),write(x) -> "whatever the user typed in"
E. true
A predicate that always succeeds.
F. fail
A predicate that always fails.
G. exit
Exits back to TOS.
H. call(variable)
Calls as a goal whatever "variable" is bound to.
I. =(variable1|number,variable2|number)
Succeeds if the numeric value of the first value equals the
numeric value of the second. Numbers in G-Prolog are signed longs, so
a number's range is about -2 billion to 2 billion.
J. <(variable1|number,variable2|number)
Succeeds if the numeric value of the first value is less than the
numeric value of the second. Numbers in G-Prolog are signed longs, so
a number's range is about -2 billion to 2 billion.
K. <>(variable1|number,variable2|number)
Succeeds if the numeric value of the first value doesn't equal
the numeric value of the second. Numbers in G-Prolog are signed
longs, so a number's range is about -2 billion to 2 billion.
L. >(variable1|number,variable2|number)
Succeeds if the numeric value of the first value exceeds the
numeric value of the second. Numbers in G-Prolog are signed longs, so
a number's range is about -2 billion to 2 billion.
M. >=(variable1|number,variable2|number)
Succeeds if the numeric value of the first value equals or
exceeds the numeric value of the second. Numbers in G-Prolog are
signed longs, so a number's range is about -2 billion to 2 billion.
N. <=(variable1|number,variable2|number)
Succeeds if the numeric value of the first value is less than or
equals the numeric value of the second. Numbers in G-Prolog are
signed longs, so a number's range is about -2 billion to 2 billion.
Examples of numeric comparisons:
=(4,5) fails
>(5,2) succeeds
>=(8,x) succeeds if x is bound to a value less than or equal to 8
O. is(variable1 variable2|number operator variable3|number)
The "is" built-in first calculates the value of the binary infix
operation defined by "variable2|number operator variable3|number,"
where "operator" can be "+","-","*","/", or "%" (the MOD function).
If variable1 is unbound, it is bound to the result of the computation.
Otherwise, it is compared to the result, and the clause succeeds or
fails based on this comparison.
Examples: is(x 2 * 2) binds x to 4 (assuming x is unbound)
is(x 5 % 2) compares x with 1 (assuming x is bound)
P. cons(newlist,element,oldlist)
Cons constructs a new list which has the single element (atom or
list) "element" as its head and "oldlist" as its tail. If "newlist"
is unbound, it is bound to the result of the consing. Otherwise, it
is compared to the result, and the clause succeeds or fails based on
this comparison.
Example: cons(x,a,[b,c,d]) binds x to [a,b,c,d] (assuming x is
unbound)
cons(x,[a,b],[b,c,d]) binds x to [[a,b],b,c,d] (assuming x
is unbound)
cons(x,truck,[car,boat] compares x to [truck,car,boat]
(assuming x is bound)
Q. same(item1,item2)
Compares item1 and item2, both of which may be atoms or lists,
and succeeds if they are identical.
Examples: same([bird,lizard],[bird,lizard]) succeeds
same([bird,lizard],[bird,dog]) fails
R. different(item1,item2)
Compares item1 and item2, both of which may be atoms or lists,
and succeeds if they are not identical.
Examples: different([bird,lizard],[bird,lizard]) fails
different([bird,lizard],[bird,dog]) succeeds
VIII. THE CUT
It has been stressed that Prolog is a declarative language. This
is certainly true, but there are occasions when it is helpful -- or
even necessary -- to tell Prolog what course to take in solving a
problem. The facility provided for this function is the cut,
represented as the goal "!". The cut is a special predicate which
always succeeds, and which commits the interpreter to using only the
current clause in attempting to prove the current goal. There are
really two reasons for using a cut: improving a program's efficiency
and actually altering its behavior. The following examples illustrate
both uses.
Consider first the program,
far_apart(x,y) :- >(x,y),
is(difference x - y),
>(difference,1000).
far_apart(x,y) :- >(y,x),
is(difference y - x),
>(difference,1000).
This program succeeds if x and y differ by more than 1000. There is
nothing at all wrong with this program, as you can determine yourself
by hand-tracing its execution. But notice something: if Prolog is
given the goal
far_apart(4,2)
it will first try to unify with the first rule and will, of course
fail, since the difference between 4 and 2 is much less than 1000.
Prolog will then move on to the next rule and try to unify with that
one, even though the rules of arithmetic guarantee that it will fail
to unify there, as well, since y can't possibly be greater than x if x
is greater than y. The point is that because of some extra-logical
information, Prolog is wasting its time in this branch of the search
tree. A cut will, as the name implies, cut off a part of the search
tree to improve the efficiency of the search. The preceding program
could be written with cuts as follows:
far_apart(x,y) :- >(x,y),
!,
is(difference x - y),
>(difference,1000).
far_apart(x,y) :- >(y,x),
is(difference y - x),
>(difference,1000).
The cut guarantees that the interpreter won't search any more of the
search tree than it needs to. After the attempt at unifying with the
first rule fails, it won't attempt to unify with the second.
In the previous example, the cut didn't actually change the
outcome of the program; it would have worked in any case. In the
following example, the cut actually changes the program's behavior.
Consider the following program:
sum(0,x,y) :- =(x,y).
sum(X,y,Z) :- is(x X - 1),is(z Z - 1),sum(x,y,z).
The point of the program is to verify that the third argument is
the sum of the first two. Notice that this is a recursive Prolog
program -- that is, a program that calls itself. Like most recursive
programs, this one works by breaking down the problem to a trivial
case. Specifically, it is based on the sample algebraic fact that x +
y = z if and only if (x - 1) + y = (z - 1), which is in turn true if
and only if (x - 2) + y = (z - 2), and so on. The recursion stops
when the first argument has been reduced to 0, at which point the
problem becomes the trivial sub-problem of comparing the last two
arguments. To illustrate, assume that Prolog was asked to prove the
assertion
sum(2 2 4).
It would break this down to the sub-problem "sum(1 2 3)," and
this in turn to "sum(0 2 2)." The first rule would then verify the
trivial case, and the goal would succeed. But now assume that Prolog
is asked to verify that
sum(2 2 3).
As before, the problem would be reduced to the trivial case. But
this time, the case would be sum(0 2 1), which would not unify with
the first rule. Now what? We know perfectly well that there's no
point in going on, because the goal must necessarily fail, but Prolog
doesn't know this. It doggedly continues, unifying with the next
clause and trying to prove sum(-1 2 0). The recursion wouldn't stop
until the computer ran out of memory and the whole program bombed.
The program with cut which would avoid this would look like this:
sum(0,x,y) :- !, =(x,y).
sum(X,y,Z) :- is(x X - 1),is(z Z - 1),sum(x,y,z).
The cut tells the interpreter that if the first rule fails (that is,
if the arguments aren't equal), it shouldn't bother to backtrack and
try to unify with any other rules. It should simply give up and
report failure.