Since my last blog1 on the topic, we (that's CoPilot) and I have implemented lazy solution generation (LSG) in my Prolog interpreter. We spent many hours on this, including several over the weekend, until this was working properly, to the best of our knowledge. This was hard work and at times quite frustrating as the solutions received for the same query (eg parent (noam, X)) varied from none to the same solution being displayed infinitely. Nevertheless, by Saturday afternoon, all the bugs seemed to have been ironed out and LSG worked properly.
After resting a little, I took the dog for a walk, and during this time considered that it would be good to implement a high-level tracing capability. Until now, there's been an internal interface for debugging but this is not suitable for 'the user'. So I put this to CoPilot and was told that now the LSG works properly, adding high-level tracing would be easy. Even so it took about an hour to get this working as I want it to be. Below is shown the trace of the above 'grandparent' query.
Call: grandparent (noam, X) Unify: grandparent (noam, X) Call: parent (noam, Z) Unify: parent (noam, netta) Call: parent (netta, X) Unify: parent (netta, shaked) Exit: parent (netta, shaked) Exit: parent (noam, netta) Exit: grandparent (noam, shaked) Redo: grandparent (noam, X) Redo: parent (noam, Z) Redo: parent (netta, X) Unify: parent (netta, lior) Exit: parent (netta, lior) Redo: grandparent (noam, X) Redo: parent (noam, Z) Redo: parent (netta, X) Fail: parent (netta, X) Unify: parent (noam, nir) Call: parent (nir, X) Unify: parent (nir, romi) Exit: parent (nir, romi) Exit: parent (noam, nir) Redo: grandparent (noam, X) Redo: parent (noam, Z) Redo: parent (nir, X) Unify: parent (nir, maor) Exit: parent (nir, maor) Redo: grandparent (noam, X) Redo: parent (noam, Z) Redo: parent (nir, X) Fail: parent (nir, X) Fail: parent (noam, Z) Fail: grandparent (noam, X)
Yesterday I spent some time reading what used to be (and maybe still is) the bible to Prolog: 'Programming in Prolog' by Clocksin and Mellish (aka C&M). I used to own a copy of this book but it disappeared in the great book purge from at least 10 years ago. Now I have it in PDF form which is not the most convenient format but I can live with it. I was looking for a 'real' program instead of the toy queries that I've been running and found a program for the Tic-Tac-Toe game. I looked through this program for built-in predicates that I have yet to implement. There were two: var, which is very simple, and arg which is far from simple. Like the tricky length predicate, arg comes in two flavours, as shown below.
Type A: ?- arg (2, parent (noam, netta), R). Type B: ?- arg (X, parent (noam, netta), R).
Seemingly, the only difference between these two types is that in type A, the first argument is a number whereas in type B, the first argument is an uninstantiated variable. In type A, the number 2 means 'return the second argument to the term parent (noam, netta) in the variable R'. In this case, R = netta. This was fairly simple to program, although it requires accuracy.
Type B however means something different and requires LSG to work properly. The number of answers depends upon the number of arguments in the given term; thus for parent (noam, netta), there should be two solutions, X = 1, R = noam, and X = 2, R = netta. This was extremely hard to program and was extra-tricky. There were two (actually three) difficult tasks to be achieved and I have to say that I had the insights to achieve them correctly.
CoPilot came up with the idea of entering temporary facts into the database then solving them with a temporay goal, but implementing this was far from simple. CP 'went down the rabbit hole' and made this much more complicated than it actually needed to be; I realised at one stage that all that was needed was two facts to be entered into the database - $arg_internal (1, noam) and $arg_internal (2, netta) - then a 'synthetic' goal needed to be inserted into the goal list, $arg_internal (X, Y), which would solve these facts for the required output. A user cannot enter this predicate because the functor name begins with the dollar sign which is illegal in the parser, but the interpreter can add these facts because it adds them directly without going through the parser. I verified that the goal could be solved with these facts.
The second task to be achieved was inserting the synthetic goal into the goal list. This again went through several unsuccessful iterations until I realised that we were inserting this goal into a copy of the goal list and not into the real goal list that was being solved. As soon as this was understood, the task was easily achieved. Once the query is completed, the synthetic facts are removed from the knowledge base. I think that this removal can be optimised slightly but that will wait for another time.
This insertion of facts and goals is an intriguing technique, and now that it's been ironed out, it can be used again. I am not currently aware of any other predicate that does require this, but now the tool exists.
The third difficult task came about when I was trying to list the synthetic facts - although the clause itself existed, none of the terms within the clause were shown. As soon as I walked away from the computer for lunch, I realised why this is so. This actually is the same bug that happened a few weeks ago that occurs when the interpreter adds clauses to the interpreter when it is solving a query. This is connected to garbage collection; I won't go into details, but again this insight came from me and not from CP.
So CP may have the general idea of how to implement various predicates, but when things don't work, it doesn't have the insight to realise what is wrong. So CP and I make a good team.
Internal links:
[1] 2056
| Title | Tags | ||
|---|---|---|---|
| 532 | Play it again, Sam | Woody Allen | |
| 796 | Removing the blinkers (Research questionnaire 6) | DBA | |
| 797 | Reinventing the wheel | DBA | |
| 913 | Sending complex emails via Priority | Programming, Priority tips | |
| 1887 | Recording "Life as a bell pepper" | Home recording |
No comments:
Post a Comment