ok@quintus (Richard A. O'Keefe) (07/04/88)
Further comments on chapter 3 of "Knowledge Systems and Prolog".
1. "simulate_iterate" (pp 124-125)
No, this comment is not about the dubious grammar of the name.
Page 123 introduces a VM/Prolog construct 'retry', and page 124
gives an example of its use:
simulate_iterate <-
label(come_back_here) &
retrieve_state(State) &
do_another_cycle(State, NewState) &
store(NewState) &
retry(come_back_here).
simulate_iterate <- write(done).
The author says "However, it is better style to write this without
retry/1 as"
simulate_iterate <-
retrieve_state(State) &
do_another_cycle(State, NewState) &
store(NewState) &
simulate_iterate.
simulate_iterate <- write(done).
Beware: the two are _not_ equivalent! On turning this into Prolog and
supplying suitable definitions of the ancillary operations, the query
| ?- simulate_iterate, fail.
produced the following results:
1
2
3
4
done
done
done
done
Not good. Diagnosis and cure left to the reader. This is a recurring
problem with the code in this book, so I shan't mention it again. The
phrase to remember is "backwards correctness".
If you want an iteration, why not just write a plain iteration?
iteration(CurrentValues, Context, Results) :-
continuation_test(CurrentValues, Context),
!,
transformation(CurrentValues, Context, NewState),
iteration(NewState, Context, Results).
iteration(FinalValues, Context, Results) :-
result_calculation(FinalValues, Context, Results).
The Dijkstra-style loop
do G1 -> S1
...
[] Gn -> Sn
od
corresponds directly to the Prolog predicate
iteration(State0, Context, State) :-
<G1>(State0, Context),
!,
<S1>(State0, Context, State1),
iteration(State1, Context, State).
...
iteration(State0, Context, State) :-
<Gn>(State0, Context),
!,
<Sn>(State0, Context, State1),
iteration(State1, Context, State).
iteration(State, _, State).
/* when none of <G1>, ..., or <Gn> is true */
I emphasise that the mapping is _direct_: the State parameters
correspond to the variables which are changed by the loop, and
the Context parameters to the ones which are not changed.
Think of the cuts in this as fixed punctuation, part of the
syntax. The results won't be brilliant, but at least (unlike
simulate_iterate) your code won't go crazy.
2. A potentially misleading statement (p 126)
"IBM Prolog subdivides the constants further into integers,
floating-point numbers, strings, and atoms. .... If all
occurrences of one constant were replaced in all predicates
with another unique constant, the programs [sic] should
still work."
This is true, but unfortunately the hypothesis "if all
occurrences ... were replaced in ALL predicates" is impossible
to achieve. Replacing 1 by 2 is likely to get you in trouble.
There are too many built-in predicates which assign meanings
to constants. So the statement is true, but vacuously so.
{findall/3 has been known to break if you generate the wrong
constant, but I've told you about that one...}
3. Perils of dot notation (p 129)
Concerning the representation of a tree in the data base, the text
says "There are many ways do to this. For example: Each node of
a sentence structure is named by an integer S, or by a pair of
integers S.N. S is the number of the sentence of which the node
is a part, and N represents the occurrence of a particular node
type if there can be more than one. For example, suppose we call
"cats like mice" sentence 1. Then we can represent it as the facts
s(1, np(1.1), vp(1)).
vp(1, v(1), np(1.2)).
v(1, like).
np(1.1, cats).
np(1.2, mice). "
The problem is that elsewhere in the book we find that VM/Prolog has
floating point constants, so guess what 1.1 and 1.2 are? I neither
added spaces to the clauses above, nor took them away.
It is not a good idea to use dot notation (or list notation) for
pairs. It is not at _all_ a good idea. A more economical
representation would be
s(1, np(1,1), vp(1)).
vp(1, v(1), np(1,2)).
v(1, like).
np(1, 1, cats).
np(1, 2, mice).
Quite a few of the uses of dot notation in this book fail to improve
the code's clarity, debuggability, or efficiency. It would be tedious
to illustrate every case, but exercise 17 of chapter 2 is a good bad
example.
4. Wrappers (pp 131-132)
This repeats the "type person = record" example from chapter 2,
with a couple of minor differences. p132 introduces the idea of
field access predicates with this example:
name_of(person(name(N),_,_,_), N).
When you have several record types kicking around, it is better to
adopt a naming convention which makes it clearer what is going on
(for example, I would expect name_of(X,Y) to mean that X is the
name of Y, not the other way around!) and of course it is always
a good idea to get rid of those wretched wrappers. So this would
be better as
person_name(person(Name,_,_,_), Name).
The naming convention here is similar to the convention for type
conversion: <type of first argument>_<type of second argument>, so
once you know the name you know the argument order.
name_of_person(Name, person(Name,_,_,_)).
<field name>_of_<record name>/2 would also be a sensible naming
convention, where again the predicate name reminds you plainly of
the argument order.
5. Operators (p 145, pp161-162)
"To encourage an English-like reading" [p161] some of the examples use
a lot of operators. For example, we find on p145
nil contains_the_same_elements_as_ordered nil.
(A.ListB)
contains_the_same_elements_as_ordered Tree <-
ListB
contains_the_same_elements_as_ordered TreeB &
Tree is_the_same_as TreeB with_element A added.
{This is the layout in the book, I do assure you.} Is the predicate
called in the second clause added/1, with_element/2, or
is_the_same_as/2? I dunno about you, but I find this clearer as
list_to_tree([], empty).
list_to_tree([Item|Items], Tree) :-
list_to_tree(Items, Tree1),
add_item_to_tree(Item, Tree1, Tree).
If we suppose that "... is_the_same_as ..." is to be read as
is_the_same_as(Tree, with_element(TreeB,added(A)))
then there is a term with_element(_,added(_)) being constructed on
every iteration of contains_the_same_elements_as_ordered/2, for no
good reason. Even in a structure-sharing system, this wastes time.
Similarly, we find on p162
deleting P from (P.Clauses) gives Clauses.
deleting P from (*.Clauses) gives NewClauses <-
deleting P from Clauses gives NewClauses.
This is used to define delax(P) in an interpreter. Now since
delax(Head) :-
clause(Head, _Body, Ref),
!,
erase(Ref).
(according to p56 of my copy of the VM/Prolog manual, though I may
have misunderstood what "the predicate of a clause" is--the examples
do not help), this definition has two bugs, not just the obvious one
of deleting all the clauses which happen to precede P in the
simulated data base. The clauses should read
deleting P from (P.Clauses) gives Clauses <- /.
deleting P from (X.Clauses) gives (X.NewClauses) <-
deleting P from Clauses gives NewClauses.
The complaint here is that, assuming the parse to be
deleting(from(P,gives([P|Clauses],Clauses))) :- !.
deleting(from(P,gives([X|Clauses],[X|NewClauses]))) :-
deleting(from(P,gives(Clauses,NewClauses))).
an extraordinary amount of pointless junk is being built up and
dismantled on every call.
If you have a parser which supports distfix operators, such as
the DEC-10 Prolog library file DISTFI.PL, fine. In such a parser
you can arrange for a term with the appearance of
deleting X from Y gives Z
to be read as a plain compound term like
deleting_from_gives(X, Y, Z)
though I think the evidence of this book is that it can make code
rather harder to read, because it is harder to find the name of the
predicate or command. If you haven't got such a parser, don't try
to simulate the style with operators.
6. Control structures (p 149)
The if-then-else construct already has a VM/Prolog form.
In fact it has two of them:
( Test -> WhenTrue ; WhenFalse ) /* As in DEC-10 Prolog */
( Test SOME WhenTrue NONE WhenFalse ) /* "soft cut" version */
For example, ( (X=a | X=b) SOME write(X) NONE write(failed) ) & fail
would write "a" and "b". {A trap for bi-linguals: DEC-10 Prolog is
self-consistent in having (Test->WhenTrue) mean (Test->WhenTrue;fail)
--compare this with guarded-if in Dijkstra's notation--
but VM/PROLOG treats it as (Test->WhenTrue;true).
Anyrate, given that VM/Prolog has no shortage of if-then-elses, it is
strange to find p149 introducing yet another one. It is particularly
surprising to find that "->" is not in the index, and the only mention
of if-then-else in the index points to page 149; surprising because
there is other code in the book which _does_ use (If->Then;Else).
The definition of 'forall' given here is not the usual one.
Recall that the usual definition is
forall(Generator, Test) :- \+ (Generator, \+ Test).
"Test is true for all Generator if there is no proof of Generator
for which Test is unprovable". The version given on p149 is
(forall P do Q) <- P & once(Q) & fail.
(forall P do Q).
which does _not_ have that declarative reading. I'm sure the effect
it produces is exactly what the author intends to do, my point is that
the name may mislead people who are familiar with the version which
resembles a quantifier.
7. "Labels" (pp 150-155)
One feature which was dropped from DEC-10 Prolog at a very early stage
was ancestral cuts. VM/Prolog not only retains this dubious feature,
but extends it. (Actually, I think it copies Waterloo Prolog.) Pages
150-155 describe this area of VM/Prolog. Now, I issued a challenge a
couple of years back: tell me something you can do with ancestral cuts
that can't be done better without them. I'm still waiting. (No, you
_don't_ need ancestral cuts to write a meta-circular interpreter for
Prolog.) I expected to find a warning in the book: "Normal programs
are _extremely_ unlikely to have legitimate uses for these operations.
Use them only in desperation." There may be such a warning, but I have
yet to find it.
The key point is that label(Term) puts a special mark on the stack,
and cut(Term) finds the most recent label(X) for which X unifies
with Term, and discards all choice points made since label(X) was
pushed. There are also retry(Term) and fail(Term), and there is a
query_l(Label[,N]) which just looks at the labels.
Apart from the general moral leprosy of these operations, you can't
even trust them. Suppose I do
p(...) <- label(zwilnik) & q(...) & r(...) & ...
r(...) <- ... & cut(zwilnik) ....
without looking at everything that q does, we cannot tell whether
r cuts the same zwilnik that p mentions, or some other zwilnik.
Suppose q does label(zwilnik). Then r will cut q's zwilnik.
Suppose q does cut(zwilnik). Then r will cut some zwilnik that
existed before p was called. E.E.Smith fans will agree that
zwilniks should be cut, but they should be the _right_ zwilniks (:-).
This is especially pernicious if r(...) is doing a retry(zwilnik)
rather than a cut. If you define control structures with the aid of
these operations, you have to be EXTREMELY careful if you want them
to be nestable. (Think of the trouble Lisp people had writing
mapping functions before lexical binding became the default.)
Telling unsuspecting readers about these operations without warning
about the dangers is not altogether unlike selling cigarettes to minors.
8. Query-the-user interpreter (p 173)
The following interpreter is presented:
succeeds(true) :- !.
succeeds((A, B)) :- !,
succeeds(A),
succeeds(B).
succeeds(A) :-
clause(A, Body),
succeeds(Body).
succeeds(A) :-
query_the_user(A).
The bug should be glaringly obvious. Try finding all the solutions
of append(X,Y,[a,b]) with this interpreter...
9. Where do you put the extra arguments (p 178)?
This occurs near the end of a section on meta-interpreters. The
nice thing about a well-designed interpreter is that you can unfold
it into the rules it interprets and thus "compile it away". The
particular example is extending Prolog to return a proof as well as
a solution. For example, we might have a predicate
append(X, Y, Z)
and it is going to be given another argument to hold a proof which
will be constructed during execution. Now, where do we put that
extra argument? The code given on p178 is
convert_unit(Head, NewHead, BodyProof) <-
(Head =.. P.HeadArgs) &
(NewHead =.. P.BodyProof.HeadArgs).
which will turn append(X,Y,Z) into append(Proof,X,Y,Z).
Now, if you use =.. a lot, this will be so _obvious_! But it is not
only not the right place to put such an argument, it is the worst
possible place. To quote page 150:
"Most Prolog implementations, including IBM Prolog, index on the
***FIRST*** argument of a predicate." (my emphasis)
The rule in Prolog is: INPUTS before OUTPUTS, and that is why it is
the first argument which is indexed on, rather than the last (there
are Prolog systems which do more than just the first argument;
Quintus Prolog has library(indexer) which lets you get independent
indices on any of the separate arguments of a predicate). Since the
proof tree is being constructed during execution, it is guaranteed
to be uninstantiated when expanded predicate is called, so no indexing
at all will be obtained.
No, the thing to do is to imitate the DEC-10 Prolog library predicate
apply/2: apply(p(X1,...,Xm), [Y1,...,Yn]) calls p(X1,...,Xm,Y1,..Yn).
Add the arguments at the end, like DCG rules.
So the thing to do is
convert_unit(Head, NewHead, BodyProof) <-
(Head =.. P.HeadArgs) &
append(HeadArgs, [BodyProof], NewHeadArgs) &
(NewHead =.. P.NewHeadArgs).
A small cost at translation time, a _big_ saving at run time.
[Best of all, in a compiled Prolog, is to forget about univ entirely
and use functor/3 and arg/3. Quintus customers see library(call).]
10. Most-specific Generalisations (pp 209-212)
We are told "Unifying two terms produces the _most-general instance_,
which is an instance of both terms. For some problems, we may be
interested in the dual operation, the _most-specific generalisation_
(MSG) of two terms. Sometimes it is also called the _least-general
generalisation_. This is the dual operation of unification, if we
consider the lattice formed by terms under the _instance_ relation."
They give code on pp211-212. Unfortunately, the code they give does
not implement that operation. For example, when
T1 = f(A+2,A+2)
T2 = f(1+B,1+B)
the msg/3 predicate they define returns
T = f(U+V,W+X)
but T' = f(U+V,U+V) is a generalisation of T1 and T2 which is more
specific than T. [If no variable is repeated in T1 or T2, the
answer is right, but not in the general case.]
CONCLUSION
Just at the moment, I don't intend to write any more of these comments
about this book. I'd like to stress that there is much of value in
the book: if you were thinking of buying it don't let me put you off.
A word of advice to authors: it is a really good idea to run every
example in your text, using software tools to extract _exactly_ the
code that your readers will see. I made the mistake of editing
something once after I'd checked it, and of course introduced an error.