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))).
The next stage will be to update unification so as to allow pattern matching
like:
member (X, [X | _]).
member (X, [_ | T]):- member(X, T).
Internal links
[1] 2013
[2] 2010
| Title | Tags | ||
|---|---|---|---|
| 296 | Mocha too goes on holiday | Dog | |
| 418 | Dennis Ritchie: The man who created Unix | Obituary, RIP | |
| 1179 | Conditional choose-field trigger (2) | Priority tips | |
| 1841 | Completing the auxiliary program | Programming, Delphi |
No comments:
Post a Comment