At the beginning of October, nine weeks ago, I was
inspired1 to start writing a Prolog interpreter in Pascal, aided
and abetted by the AI program CoPilot. This interpreter has been through many
iterations and changes, driven by new Prolog constructions that I was
feeding the interpreter. Some of the functionality was reasonably easy to implement whereas some was very hard. I have spent the past two weekends (that's
somewhere around 16 hours of work) trying to get the intepreter to interpret
the 'append' rules.
append ([], L, L).
append ([H|T], L, [H|R]):- append (T, L, R).
The rules seem - as always - deceptively simple. The first rule really is simple,
saying that appending an empty list to list L will result in list L. This
rule is needed because all recursive rules work by continually simplifying
the query until a base case is reached. I explained this more fully in the
blog2 that tells of the factorial function. The second rule
says that if one is trying to append the list T to list L with the result R,
then one takes the head - aka the first element - of list T and makes
it the head of list R. When the query runs, each time the head is removed
from the list T until there is no head left - this is the first rule.
We worked and worked on geting this right. I admit that about half of that
time was wasted, due to my mistake of not adding the body (append (T, L, R))
to the second rule. I had saved the append rules in a file so that I
wouldn't have to type them all the time, and it took me a long time to
notice that there was no body! Even so, we had to debug almost line by line; a large amount of what is known as scaffolding - statements that do
nothing by themselves but support the rest of the program - was built in order to find
out where we were going wrong. I don't claim to have understood all the
nuances of the many log files. CoPilot added a few extra fields to the basic
term structure then during the course of the program (i.e. solving the
query), these fields would receive values that showed what was
happening.
To use a metaphor, several times the scaffolding was erected only to be
removed later. Although most of the bits of code that I wrote myself were buggy,
a great deal of CoPilot's code was also problematic. A function would be
added - code courtesy of CoPilot - only for us to discover later that the
function was doing something wrong. Unfortunately, CoPilot doesn't retain my
comments for too long, so I can't quote here an exact exchange between us. At one
stage, I was told to add an index to variable terms where this index should
be maintained on a per-clause basis. Many hours later, it turned out that
this index should be on a per-query basis (there is a difference between the
two: per clause means effectively one line of the program, whereas per query
means an entire run). Much time was spent trying to nail down an extra
recursive call in Unify that was causing a major problem; CoPilot said that
an important function called BindVariable should not have a recursive call
to Unify - but it did; a version dated 22/11/25 already had such a recursive
call. Despite my uploading the unit containing this function to CoPilot, I
had to point out this call - and it wasn't me who put it there initially!
Once this was fixed, 'append' worked properly.
?- append ([a], [b], Result).
Result = [a, b].
This may not seem much but it was a huge step forward. Going back to the
'member' rules that I showed3
before, I wondered what the interpreter would make of the query
?- member (X, [a, b, c, d];
I received four solutions: X = a, X = b, X = c, X = d, which is correct.
This shows that the interpreter is robust.
I have already learnt that it's not enough to sweat and strain and get the
interpreter to solve a new type of query; one must check that previous
queries also succeed. At first I thought that the interpreter could not
solve the factorial function but that was my fault; I had written ?-
factorial (3), instead of ?- factorial (3, R). Once I wrote the correct query, the code worked perfectly. The
family tree 'database' didn't work properly at first either, but that was because
of some scaffolding code that was interfering; I commented out some five
lines, and the 'grandparent' query worked. I checked that 'append' was also
still working.
The addition of a numerical type caused the 'time_in_minutes' query4 to crash; the parser complained correctly that 03:30
is not a number. This is because the check was made on the first character only and because it
was 0, the parser assumed that it was a number and not an atom. I suggested
what the change should be; my code was better than that of CoPilot and also
worked first time.
So now I've exhausted all the goals that I originally wanted from a Prolog
interpreter. It can solve the following queries (or parse the statements), each of which exercises a
different part of the syntax as well as including goals that include
multiple clauses.
grandparent (X, Y):- parent (X, Z), parent (Z, Y).
grandfather (X, Y):- male (X), grandparent (X, Y).
sisters (X, Y):- female (X), female (Y), X \= Y, parent (Z, X), parent (Z, Y).
factorial (N, F):- N > 0, N1 is N - 1, factorial (N1, F1), F is N * F1.
factorial (0, 1).
add (Operand1, Operand2, Result):- Result is Operand1 + Operand2.
owns (noam, cd ('Unhalfbricking', 'Fairport Convention')).
time_in_minutes(TimeAtom, Minutes) :-
atomic_list_concat(TimeAtom, ':', [HStr| MStr]),
atom_number(HStr, H),
atom_number(MStr, M),
Minutes is H * 60 + M.
p ([the,cat,sat,[on,the,mat]]).
member (X, [X|_]).
member (X,[_|Y]):- member(X,Y).
append ([], L, L).
append ([H|T], L, [H|R]):- append (T, L, R).
Do I want to continue with the Prolog interpreter? It will only come about
if I read some text about Prolog (and I have several), get enthused
enough to try some statement from the book in my interpreter and discover
that it doesn't work. For example, 'Prolog programming in depth' by
Covington, Nute and Vellino has queries like ?- located_in (X, texas), write (X), nl, fail.
First of all, I am fairly sure that my interpreter won't accept multiple
clauses written in that way although it will accept them if the whole thing
was bundled as a rule. As the book says, the special predicate 'write' causes each value of X to be written out;
'nl' starts a new line after each value is written and 'fail' forces the
computer to backtrack to find all solutions. If my interpreter could parse this line, it would print 'X = ....', then
wait for the user to say whether another solution is desired. Do I want
this? Probably not, although the capability of solving several consecutive
clauses is something that should be added (this is probably very simple to
add in terms of what I already have).
Another standard, intrinsic, function is 'not', although I'm not sure quite what
the use of this would be. For example, if the query ?- father (noam, netta)
returns 'Yes', then ?- not father (noam, netta) would return 'No'. Apart
from the parsing problem presented by this query, I am dubious as to its
value.
A side issue: I should point out that despite the current demise of my XP
computer, I am still managing to develop with Delphi 7 even though this
version doesn't work on my mobile computer (actually, I'm not sure about
that; did I ever try?). I managed this feat by building a virtual computer
running XP - the software is the Oracle Virtual Box. At first, I couldn't
get Delphi 7 to work in this environment; I was installing it from a copy
that I made on a thumb drive and every time I would get a run-time error
when I tried to run the compiler. In a moment of inspiration/frustration, I
tried installing from the cd (the virtual computer can access the real
computer's cd drive) and this worked perfectly.
In real life, at the moment I am waiting for a new solution to the
grandparent rule.
Internal links
[1] 2010
[2] 2033
[3] 2043
[4] 2029
This day in blog history:
