Path: utzoo!attcan!uunet!husc6!mailrus!ames!joyce!sri-unix!quintus!ok
From: ok@quintus (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: KS&P, chapter 3, part 2.
Message-ID: <154@quintus.UUCP>
Date: 4 Jul 88 01:14:29 GMT
Sender: news@quintus.UUCP
Reply-To: ok@quintus (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 399

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.