There hasn't been a Prolog blog for nearly two weeks, not because there was nothing to write about, but because I felt that there had been too many blogs about Prolog in a short span of time, and also I had hit a stumbling block that was causing many problems.
I wrote1 a few weeks ago length returns the length of a list, so a list like [a, b, c] has length 3 as does as a list like [a, [b, c], [d, e]]; this latter has only three elements, even though some of those elements are themselves lists. At the moment, I can't see what one would do with this predicate although presumably there is some reason. Later I was researching the farmer/wolf/goat/cabbage problem, and I saw in one of the solutions the statement length (List, 7). This didn't correspond to what I knew about this predicate.
It turns out that there are two completely different usages for 'length': the first, which I had already encountered, returns the length of a list, whereas the second returns a list of n unbound variables, where n is the second argument to the function (i.e. length (List, 7) creates a list of seven unbound variables). It was clear that the code that I had for calculating the length of a list would not function at all for the second usage.
So CoPilot started working on what would provide this solution; during this period, we discovered here and there edge cases that had to be changed in order that length might create a list. At one time during this process, it seemed that the interpreter had entered an infinite loop. After analysing this, CoPilot informed me that the function (which was now implemented in Prolog and not built-in) was working correctly, but because of the design of my interpreter, it was creating an infinite number of solutions. After several more hours of struggle, the Prolog code managed to create a list as defined, but the original functionality had been lost. I decided to remove the 'length' code from the startup Prolog code and reconsider.
The infinite loop is due to the fact that the interpreter implements what might be termed eager solution generation, where all the solutions are generated before being displayed to the user, who can choose whether to display only one solution or more. This is fine when there is a finite number of solutions, as with the family database, but not in other cases, such as length (List, 7), despite the fact that one might think that it is not a problem to create a list of seven unbound variables.
CoPilot informs me: Lazy answer generation is about when the interpreter produces the next solution. For example:
?- parent(X, Y). X = john, Y = mary. More? y X = john, Y = david. More? y ...
This is the classic Prolog REPL behavior:
- Generate one solution.
- Pause.
- Only generate the next solution if the user asks.
I decided that implementing 'length', as well as other tricky predicates such
as '!', 'not', 'fail' and 'true' should wait until we implement lazy answer
generation, probably later today.
In the mean time, I had been considering the 'length' predicate and its two capabilities. It occurred to me that I could implement it in Pascal without getting into all the problems that the Prolog code creates. If the first argument is a list, then the function should return the length of the list, and if the first argument is a variable then the function should return a populated list. My Pascal code as shown below derives a little from the original CoPilot implementation (the first two lines), but most of it is mine.
function ResolveLengthPredicate (goals: PTermArray; var env: TEnvironment): TArrEnvironment; var n: Integer; listTerm, lenTerm, head: PTerm; begin listTerm:= resolve (goals[0]^.args[0], env); lenTerm:= goals[0]^.args[1]; if listterm^.kind = tkCompound then begin // iterative length n:= 0; while (listterm^.kind = tkCompound) and (listterm^.name = '.') do begin inc (n); listterm:= listterm^.args[1]; end; if unify (lenTerm, number(n), env) then result:= ContinueSolving (goals, env) else setlength (result, 0) end else if listterm^.kind = tkVariable then begin // create list of variables according to lenterm head:= atom ('[]'); for n:= lenterm^.num downto 1 do head:= compound ('.', [variable ('_'), head]); if unify (listterm, head, env) then result:= ContinueSolving (goals, env) else setlength (result, 0) end else setlength (result, 0) end;
Once I had cleared the syntax problems, this code worked first time for
both usages. I showed it to CoPilot who wrote: I think you made a very smart engineering call, Noam — and
honestly, it’s the same call that many Prolog implementers eventually make
when they want length/2 to behave relationally without
dragging in a full constraint solver. Let me break down why your Pascal
implementation is not only reasonable, but actually elegant for the engine
you’ve built.
[I'm omitting the breakdown]. What CoPilot didn't mention what that 'his'
original solution for calculating the length was recursive, in the same way
that calculating the
factorial2 is recursive. My implementation is iterative and much simpler as
it simply steps through the array of terms.
During the night, it rained a lot; I awoke and listened to it for a while. My code for 'length' was running through my head, and I wondered whether there was a predicate for calculating the sum of the numbers in a list. For example, the sum of the list [1, 2, 3] would be 6. This should be quite easy to do using the paradigm of the 'length' code. When I got up, I googled 'prolog predicate calculate sum list', and discovered that in Prolog, the standard built-in predicate for calculating the sum of a list is called sum_list/2. If one's version of Prolog doesn't have this predicate, it can be implemented as follows, normally using an accumulator for efficiency.
% Main predicate: initializes the accumulator to 0 and calls the helper. sum_list_acc(List, Sum) :- sum_list_helper(List, 0, Sum). % Helper predicate base case: when the list is empty, the final Sum is the Accumulator. sum_list_helper([], Acc, Acc). % Helper predicate recursive case: % Calculate NewAcc, then recurse with the Tail and NewAcc. sum_list_helper([Head|Tail], Acc, Sum) :- NewAcc is Acc + Head, % Calculate the new accumulator value sum_list_helper(Tail, NewAcc, Sum). % Recurse with the new accumulator
But I'm doing this in Pascal and in doing so, I am avoiding any problems that the Prolog implementation might create. There are another two very similar predicates, each of which I implemented in about a minute: 'min_list' and 'max_list'. To be honest, these predicates are 'nice to have', but I can't imagine where they would be used. I also feel that this kind of predicate is leading me towards programming in a procedural style and not in a logical style, which is the whole point of Prolog. So I think that the next steps are to implemented easy solution generation and then handle those tricky predicates that I mentioned earlier.
Part of the discussion with CoPilot that seems to have disappeared is about existential variables. To quote the AI that Google displays: In Prolog, "existential variable" is not a standard built-in concept for general programming, as all variables in a standard clause are considered universally quantified by default. The term is specifically used in the context of certain built-in predicates like bagof/3 and setof/3 to perform existential quantification over a goal. In standard first-order logic, an existential quantifier means "there exists at least one value" for which a statement is true. I don't claim to completely understand that but it does bring memories back of French O-level studies in 1971.
The O-level exam was split into two parts (held on different days): the first part was written, a normal exam paper, but the second part was oral, where one of our teachers would interview us whilst recording the conversation so that an external examiner could evaluate our ability to converse in French. We had a little freedom in terms of the topic to be discussed: there would be four options available, but only two would be chosen, from which we had to chose one topic on which to talk. This meant that in practice we only had to prepare three topics.
The well-named Jonathan Blaise Duke-Evans (aka "The Duke") [years ago I discovered that he was a senior official in the Home Office] sat in front of me in class and was always the source of interesting topics for discussion. He suggested apropos of nothing that I prepare a topic about Jean-Paul Sartre; this seemed off-the-wall enough that I took him up on this and learnt all about JPS, Simone de Beauvoir and existentialism. I don't remember now what my second topic was; the third was food but again I don't remember what the fourth topic was, for which I didn't prepare anything. In the exam, I had to chose between food and the non-existent fourth topic, so of course I talked about food. The only thing that I remember about this was that I couldn't remember what potatoes are called in French (pomme de terre); the teacher tried to help me by suggesting alternatives but I stuck to condemning myself. I still passed the exam. Anyway, whenever I hear about existential qualifiers, I always think of Jean-Paul Sartre.
Internal links
[1] 2050
[2] 2033
| Title | Tags | ||
|---|---|---|---|
| 226 | Neat tricks in the 'management' program/2 - MDI | Programming, Delphi, MDI | |
| 227 | Does Satie have friends in Hollywood? | Satie | |
| 322 | Suite: Judy Blue Eyes | CSN | |
| 440 | The difficult negotiator | Negotiation | |
| 792 | Painting with numbers | Statistics | |
| 1701 | Back to squabbling | Israel |
