A week ago, I thought that I would look for material discussing the first
ever implementation of Prolog. It turns out that the
Fortran implementation1 was not the first, as per CoPilot. I found a
paper
written by Alain Colmerauer and Philippe Roussel - actually two versions of
the same paper - that states
During the fall of 1972, the first Prolog system was implemented by
Philippe in Niklaus Wirt's [sic]
language Algol-W ... From June to the end of the year [1973], Gérard
Battani, Henry Meloni, and René Bazzoli, postgraduate students at the time,
wrote the interpreter in FORTRAN and its supervisor in Prolog.
At the end of the paper, a very simple database was shown that contains data
regarding flights from Marseille to Paris and thence to London (there should
have been also flights from London to Edinburgh, so that one could travel
from from Marseille to Edinburgh, the two main locations for Prolog
development). I thought that it would be interesting to see how CP Prolog
would handle this so I created a small text file with a few of the facts and
fed it in. To my surprise, no syntax errors were detected and one could
actually query the facts successfully.
flight (paris, london, 00:30, 03:00).
flight (paris, london, 09:30, 12:00).
flight (marseille, paris, 06:00, 07:00).
route (A, B, Min, T1, T2):- flight (A, B, T1, T2), Min < T1.
route (A, B, Min, T1, T3):- flight (A, X, T1, T2), Min < T1,
route(X, B, T2, T2a, T3), T2 < T2a.
% sample query:
% ?- route (marseille, london, 03:00, Departure, Arrival).
% Departure = 06:00
% Arrival = 12:00
Much later I thought of a few problems with this very simple database. The
first is trivial: CP Prolog is unaware of a 24 hour clock (or indeed of any
clock), so a flight that has a departure time of 22:00 and an arrival time
of 00:30 would appear to arrive before it departs!
The second problem is much deeper: the database does not take into account
the fact that one should be in the airport three hours prior to an
international flight, and that it takes a finite amount of time to get from
wherever (home, university) to the airport. This implies that there should
be a clause in the 'route' rule along the lines of (T1 - Min) > 3.
Unfortunately CP Prolog would have three problems with this: it doesn't know
how to perform arithmetic, the syntax is problematic, and 3 has no meaning
here. Min might be 03:00 and T1 06:00, but we are mentally converting these
string values into interger values before performing the subtraction. So it
seems that a conversion rule such as ClockToMins would be necessary,
although I don't know how to write this in Prolog (easy in Pascal). Then the
two converted values would have to be compared, where the difference would
have to be greater to equal to 180 (that I can do).
I could implement arithmetic without too much trouble, as the first thing
that I wrote with CoPilot was a
simple infix expression parser2. Prolog syntax would have expressions such as X is Y + Z,
where 'is' is the infix operator for assignment. I have seen books that
replace this operator with ':=', which is the Pascal assignment operator; I
could support both with no problem. As Bratko ("Prolog programming for
artificial intelligence", 1986), writes (p. 85),
The following question is a naive attempt to request arithmetic
computation:
?- X = 1 + 2.
Prolog will 'quietly' answer
X = 1 + 2
and not X = 3 as we might possibly expect. The reason is simple: the
expression 1 + 2 merely denotes a Prolog term where + is the functor and 1 and
2 are its arguments. There is nothing in the above goal to force Prolog to
actually activate the addition operation. A special predefined operator, is,
is provided to circumvent this problem. The is operator will force evaluation.
So the right wav to invoke arithmetic is:
? - X is 1 + 2.
Now the answer will be:
X = 3
Do I really want to add this? I suppose the answer to this rhetorical
question is 'why not?'. I estimate that 90% of the code requires already
exists in one form or another. Adding the infix expression parser would be a
good excuse for dividing the monolithic Pascal source file into several
units; apart from speeding compilation, this would also help to separate
logical parts of the program.
The only reason that I hesitate is that yesterday I started work on
implementing lists. These are very much the legacy of Lisp in Prolog,
and once again they are deceptively simple but actually difficult to
implement. A list is a sequence/collection/set of items - Bratko's initial
example has ann, tennis, tom and skiing, whereas my simple test used the
items 1 and 2. They are written like this [1, 2] and one would expect the
'show' command in CP Prolog to display the list in this form. The truth is
more complicated.
In Lisp, a list can either be empty, in which case it is represented
by the value nil, or it consists of a 'cons' cell, in Pascal a
record, that has two fields: a head and a tail. The head 'can be anything' -
in CP Prolog, this means a PTerm, whereas the tail is usually a list - this
also means a PTerm. The very simple list [1] is internally represented as .
(1, nil): here the functor/predicate is '.' (pronounced 'dot', or if one is
a Lisper, 'cons') that has two arguments, where the first is the atom 1 and
the second is the atom 'nil'. As such this is identical to the more normal
Prolog fact parent (noam, netta). But if the list [1, 2] is presented to
Prolog, the following structure will be built: .(1, .(2, nil)). This is not
very easy to parse in CP Prolog and also difficult to display. The following
code is deceptively simple (a phrase that I seem to use frequently when
writing about Prolog) but that is only because each function is recursive.
function ParseList (line: string): PTerm;
var
i: integer;
head, tail: pterm;
args: array of PTerm;
begin
i:= length (line);
if line[1] = '[' then line:= copy (line, 2, i - 1);
dec (i);
if Line[i] = ']' then Delete (Line, i, 1);
i:= pos (',', line);
if i = 0 then
begin // list with one member
SetLength (args, 2);
args[0]:= atom (copy (line, 1, length (line)));
args[1]:= atom ('nil');
result:= compound ('.', args);
end
else
begin
head:= atom (copy (line, 1, i - 1));
tail:= parselist ('[' + copy (line, i + 1, length (line)) + ']');
result:= compound ('.', [head, tail]);
end;
end;
Function PrintList (head: pterm): string;
var
i: integer;
args: ptermarray;
begin
result:= '';
args:= head^.args;
for i:= 0 to length (args) - 1 do
begin
if (args[i]^.kind = tkAtom) and not args[i]^.nilflag
then result:= result + args[i]^.name + ','
else result:= result + printlist (args[i]);
end;
end;
It took quite some time to achieve this code. About an hour after completing
this, when I was in 'contemplation mode', I had several unpleasant insights.
In parsing a line, I had originally said to myself that if the current line
contains the [ character then the line should be handled by the ParseList
function; this test occurs before the test for a rule (does the line contain
the ':-' digram?), as a rule won't contain a list. Unfortunately that
assertation is completely untrue. Both the left hand side of a rule
and the right hand side of a rule can contain lists, otherwise all the
predicates such as 'member', 'cons' and 'append' could not be defined
(Bratko uses slightly different names for these predicates). So whilst
ParseList as it stands is almost correct, I will have to rework ParseRawLine
- this shouldn't be too difficult.
A minor correction but with much greater importance in ParseList is the
replacement of the line
args[0]:= atom (copy (line, 1, length (line)))
with
args[0]:= ParseRawTerm (copy (line, 1, length (line))).
In my tests, I had written [1, 2] but I could have written [X, Y] in which
case the call to 'atom' is absolutely wrong. There's also no need for the
internal begin/end pair in PrintList but that's a stylistic issue without
sytactic meaning.
The next stage will be to update unification so as to allow pattern matching
like:
member (X, [X | _]).
member (X, [_ | T]):- member(X, T).
Here we have a list in a rule as I mentioned earlier. The '_' character is
the anonymous variable, but here it's simply standing for 'nil'. The first
rule means that X is a member of the list [X, nil] (or if one prefers, X is
a member of the term . (X, nil)), whereas the second means that X is a
member of the list where X is somewhere in the tail. At the moment I have no
clue as to how to go about this.
Internal links
[1] 2013
[2] 2010
This day in blog history:
