ok@quintus (07/25/88)
@Book{ohdearohdearohdear
, Title "Logic Programming and Knowledge Engineering"
, Author "Tore Amble"
, Publisher Addison-Wesley
, Year 1987
, ISBN 0-201-18043-X
, Price "US$24.95"
}
The back of the book says, amongst other things
"Tore Amble, an Assistant Professor of Computer Science at the
University of Trondheim in Norway, has drawn upon a wealth of
teaching and research experience to provide a text which is
both lucid and practical."
I hope Edouard Lagache is reading this. If you are, Edouard, rejoice!
You can now say that your library is _better_ than the code in a
published Prolog textbook!
You'll gather from that remark that I wasn't impressed. There are one
or two nice things in the book, but on the whole it makes Bratko's book
look good. If you ever have to choose between the two, choose Bratko's.
(Better still, choose Sterling & Shapiro.)
Let's start with page 190.
"Prolog is superbly adapted to the task of natural language
processing in all its main aspects:
* as a grammar formalism
* as a formalism for meaning representation
* as a knowledge-base query language."
I should point out that he is using C Prolog as his base, which has
always included DCG (actually, MG) translation. It comes as rather a
surprise then, that having said that "Prolog is superb[... ] as a
grammar formalism", Amble doesn't actually use it. Instead, he writes
his own interpreter of grammar rules, with a whole new syntax (the
differences are only cosmetic). Perhaps this is because he doesn't
really know what the DCG translator does, for he goes on to say that
"In addition, DCG automatically corrects left recursion in grammars,
making them right recursive."
It would be nice if the grammar rule translator did this, but it doesn't.
Certainly the one in C Prolog doesn't. (Come to think of it, if you have
C Prolog, you have *source code* for the grammar rule translator. How
could he have thought this?)
Or we could look at page 100, where Amble describes a data structure he
is extremely fond of.
"6.9.2 Round lists
The list structures described earlier apply square brackets as the
standard list notations (sic) in Prolog. However, there are two
other kinds of list structures that should be mentioned:
(1) 'ROUND' LISTS, which are standard Prolog notation with round
parentheses, ();
(2) 'LISP' LISTS, which use round parentheses with the same
semantics as Prolog square brackets, but are incompatible
with Prolog syntax.
A round list is, in fact, an operator expression, using the comma
as the operator (see Chapter 5). ... Round lists are very
important ...
The syntax of round lists allows the construction of data structures
which are usually called ELEMENTARY LISTS. An elementary list is
uniquely defined by the sequence of innermost elements that are not
elementary lists themselves.
The principle can be implemented by square or round lists, but it is
shown here for the altter. Since there is no standard empty list
concept, such as [] for square lists, nil must be used. A
predicate to find the innermost elements may be given:
element(X,Y) :-
var(Y), % If Y is a variable
!, % avoid trap
X = Y.
element(X,(U,V)):-!,
(element(X,U);
element(X,V)).
element(X,X):-not X = nil.
"
This is an example of what I call a "defaulty" representation.
That is, one of the cases is defined only by not being any of the
others. That is a very bad way of designing data structures in
Prolog. Amble has picked up one of the nastiest aspects of Prolog
syntax (it is defaulty, in that user goals are identified only by
not being recognised as anything else) and adopted it as a principle.
I have to admit that some defaulty representations are attractive
for input purposes (such as Prolog syntax), but with all the earnestness
I possess, I urge you to translate such things to an explicit representation
before doing any other computing with them. For example, Amble says that
"round lists" are good because that's what a conjunction looks like in
Prolog, but a Prolog-in-Prolog interpreter can be quite a lot faster if
it works on clean data structures. DEC-10 Prolog, for example, converted
clauses to a quite different representation when they were asserted, which
representation was carefully designed for the benefit of the interpreter.
I have not read every page of Amble's book yet. But every code example
I have seen where he uses "round lists" would have been better with some
other method.
Quicksort is a pet peeve of mine, so I was pleased to see that section
6.8 (pages 97-99) presents merge sort first, then quick sort. Since
Amble actually cites one of my papers in this section, I'll not tear into
it as much as I'd like to. Suffice it to say that it would be better to
code the list splitting routine as
split(List, Front, Back) :-
split(List, List, Front, Back).
split([_,_|Counter], [Head|List], [Head|Front], Back) :- !,
split(Counter, List, Front, Back).
split(_, Back, [], Back).
With that definition (and a minor change to merge/3), merge sort would
be stable, but his version of it is not stable.
On page 100, Amble says
"As Prolog does not know if a list of numbers is meant to be a string
or not, the programmer uses a predicate to print out strings:
printstring(Xs):-name(Xc,Xs),print(Xc)."
Unfortunately, this won't work, for at least three reasons:
- if the list of character codes is too long, name/2 will probably print
an error message and abort the computation
- if the list of character codes looks like a name of a number, name/2
will generate that number, but the canonical printed representation of
that number may not be the same sequence of characters (e.g. "00" will
cause "0" to be printed)
- print/1 is used instead of write/1 to give the user's definition of
portray/1 a chance to do something different. For example, if you have
portray([]) :- write(nil).
then printstring("[]") will write "nil" not "[]".
If the task is to write a sequence of character codes, why not just DO that?
put_chars([]).
put_chars([Char|Chars]) :-
put(Char),
put_chars(Chars).
C Prolog being an interpreter, with name/2 built in, Amble's definition
may in some cases run faster. No matter: it doesn't *work*.
You'll recall that I use "all solutions predicates" as the touch-stone
for Prolog books. Here's the code from Amble's "Predicate Library".
% findall(X,Y,Z) Z becomes set of unique X such that Y
findall(X,Y,Z):-
construct(new(X),Y),
reap(Z).
listof(X,Y,Z):- % find list of X so that
for(Y,assert(new(X)), % Y is true, and put them into Z
reap(Z).
construct(X,Y):- % create tuples of form X for all solutions
for(Y,remember(X)). % of the predicate Y [RAOK: Y is a *goal*]
for(X,Y):-X,Y,fail. % iteration by backtracking
for(X,Y). % do Y for all solutions of X
remember(X):-X,!. % asserts a fact if it is not
remember(X):-assert(X). % already known
% reap is an auxiliary predicate to make
% the solution of the predicate 'new' into a list
reap([X|Y]):-
retract(new(X)),
!,
reap(Y).
reap([]).
If we unfold a couple of times, we get
findall(Template, Generator, _) :-
call(Generator),
( new(Template) -> true
; assert(new(Template))
),
fail.
findall(_, _, Set) :-
reap(Set).
listof(Template, Generator, _) :-
call(Generator),
assert(new(Template)),
fail.
listof(_, _, Bag) :-
reap(Bag).
(1) He has renamed findall/3 to listof/3 and given the name findall/3 to
quite a different operation. Since he cites Clocksin & Mellish, this
is as puzzling as it is regrettable. He also cites David Warren's
"Higher-order extensions to Prolog, are they needed?", where setof/3
and bagof/3 were introduced, but that doesn't appear to have
influenced the text.
(2) Of course it isn't steadfast. For example,
findall(X, member(X, [a,b]), [])
and listof(X, member(X, [a,b]), [])
will both succeed. [I just tried it.]
(3) It doesn't nest. Again, since Amble cites Clocksin & Mellish, this is
a regrettable puzzle. An even bigger puzzle is the suggested hint in
exercise 6.10 on page 103: if Amble has read Clocksin & Mellish he
must _know_ that there is a simpler method.
(4) Consider the query findall(X, member(X, [L,a,b]), Ans).
Exercise, why does Ans come back as a one-element list?
(By permuting the list, you can get three different answers.
More can be obtained thanks to (2)...)
(5) In most Prolog systems, Amble's findall/3 will spend O(|Set|*|Bag|)
time in remember/1 (|Bag| being the number of proofs found and |Set|
the number of distinct solutions). The usual version of setof/3
spends O(|Bag|*log(|Bag|)) time in sorting.
It can be argued in Amble's favour that (4) and (5) arise because sort/2
and term comparison are not in the subset of C Prolog that he has chosen
to describe, but that was _his_ choice. He does describe sorting, and
how hard is it to understand term comparison?
Amble defines his own versions of a lot of built in predicates,
such as ','/2, length/2, (_->_;_), and others. He has an excessive
fondness for operators in his code and lists in his data.
Get Bratko (-), Clocksin & Mellish (0), or Sterling & Shapiro (+) instead.