Path: utzoo!attcan!uunet!husc6!mailrus!ames!joyce!sri-unix!quintus!ok From: ok@quintus Newsgroups: comp.lang.prolog Subject: Book Review: Tore Amble Message-ID: <192@quintus.UUCP> Date: 25 Jul 88 05:44:08 GMT Sender: news@quintus.UUCP Reply-To: ok@quintus () Organization: Quintus Computer Systems, Inc. Lines: 226 @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.