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].
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
| Title | Tags | ||
|---|---|---|---|
| 1565 | Mint chocolate ice cream | Peppermint |
No comments:
Post a Comment