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.
This is incremental backtracking or solution streaming. Your current
interpreter does not do this. It computes all solutions first, stores them,
and then prints them one by one. That’s eager answer generation.
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
This day in blog history:
