PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (09/28/87)
PROLOG Digest Tuesday, 29 Sep 1987 Volume 5 : Issue 68
Today's Topics:
Implementation - Standards & Library & Good Clean Fun
----------------------------------------------------------------------
Date: 27 Sep 87 04:28:45 GMT
From: Lee Naish <munnari!mulga!lee@uunet.uu.net>
Subject: Standard of code
Virtually every time someone posts Prolog code to the network I groan.
I see code like this:
>merge([],[],[]).
>merge([],List2,List2):- !, fail.
>merge(List1,[],List1):- !, fail.
>merge([Head1|Tail1],[Head2|Tail2],[Head1,Head2|R]):- merge(Tail1,Tail2,R), !.
I wince, I tear my hair out, I fall to my knees and bang my head
against the nearest rock crying; is this the Prolog code people write?
What happened to logic programming? Am I wasting my time?
Then I compose myself. I grit my teeth, take hold of my electronic
butchers knife and attack the code. Out with the filth! Out with the
cuts, the dirty negation, the asserts. Wash it clean. Just leave the
essence; pure beautiful logic:
merge([],[],[]).
merge(Head1.Tail1, Head2.Tail2, Head1.Head2.R) :-
merge(Tail1,Tail2,R).
Then I look on it anew. I see it can be run as Prolog. No choice point
will be created! It will be fast! It can be run backwards! It can be
run any way need dictates. I breath a sigh of relief and my confidence
in logic programming and Prolog are restored.
------------------------------
Date: 28 Sep 87 15:54:55 GMT
From: Stanley Shebs <shebs@cs.utah.edu>
Subject: Standard of code
I must be too old and cynical - whenever I see really bad code, my
main regret is that the authors are not in a class I'm teaching, so I
can fail them on that program. (We have used large red stamps saying
"VOMIT" to good effect, also...)
I would like to see next editions of Prolog textbooks flush all the
hype about Prolog being "declarative" (whatever that's supposed to
mean) and replace it with sections on good style. I would like even
more to see cuts disappear from implementations entirely, to be
replaced by meta-level capabilities, but I suppose that's a forlorn
hope, since everybody wants "efficiency".
-- Stan Shebs
------------------------------
Date: Sat, 26 Sep 87 17:36:26 PDT
From: Richard A. O'Keefe <quintus!cresswell!ok@Sun.COM>
Subject: Lagache library.
I'd like to comment on three of the predicates in STDLIST.PRO
sumlist/2
---------
(1) This predicate is in the public-domain library file LISTS.PL
held at Stanford, is it not?
(2) Lagache's definition is not as efficient as it could be.
It does not use tail recursion, so to add up a list of N
numbers it will (temporarily) take up O(N) space on the
stack. Not good. Coding something in tail-recursive
form shouldn't hurt in any bearable Prolog, and it is a
MAJOR improvement in any good Prolog.
His code was
sumlist([], 0).
sumlist([Number|Tail], Result) :-
sumlist(Tail, OldResult),
Result is Number+OldResult.
Better code would be
sumlist(Numbers, Sum) :-
sumlist(Numbers, 0, Sum).
sumlist([], Sum, Sum).
sumlist([Number|Numbers], Sum0, Sum) :-
number(Number),
Sum1 is Sum0+Number,
sumlist(Numbers, Sum1, Sum).
Note that his documentation says that "The predicate will
fail if it is given a list that contains objects that are
not numbers". In most Prolog systems that I know of this
isn't quite true, for one of two opposing reasons:
(a) Some Prolog systems (such as C Prolog or ALS Prolog)
will allow source variables in an arithmetic expression
to be bound to arbitrary arithmetic expressions at run
time. Thus in C Prolog Lagache's code would claim that
| ?- sumlist([1+2,3*4], 15).
But neither 1+2 and 3*4 are compound terms, not numbers.
(b) Some Prolog systems (such as DEC-10 Prolog) will not
allow source variables in an arithmetic expression to
be bound to anything but a number at run time, and will
report violations of this restriction as an error. In
such a system,
| ?- sumlist([a,b,c], X).
will not simply fail, but will do whatever the system
does for errors.
To actually make the code do what Lagache says it does, you
have to insert the number/1 test. The code in LISTS.PL did
not make this test, but the documentation explicitly warned
that the behaviour was undefined on anything but a list of
integers.
One objection to the tail recursive form is that you need
two predicates. Actually, once you get used to it, you'll
very often find that the version with the accumulator is
nearly as useful as the original, because you can "start
the function part-way". For example, if I want to force
the result of sumlist to be a floating-point number even
if all the elements of the list are integers, I can call
sumlist(Numbers, 0.0, Sum)
One of the things which you have to know to be a competent
Prolog programmer is the use of accumulator parameters, of
difference structures (same thing only backwards), and how
to exploit last call optimisation (which is to say, what
the standard transliteration of an iterative loop into the
recursive style of Prolog looks like).
flatten/2
---------
(1) This predicate appears in the public-domain library file FLAT.PL
held at Stanford. However, the version there is an instance of
the generic predicate binary_to_list/5, which means that it is
not as efficient as it might be.
(2) Lagache's code uses neither tail recursion nor difference lists.
His code was
flatten([], []) :- !.
flatten([Head|T], X) :-
listp(Head),
flatten(Head, Y),
flatten(T, Z),
append(Y, Z, X),
!.
flatten([Head|T], [Head|X]) :-
flatten(T, X),
!.
Oy, is this strange! If I recall correctly, Sterling & Shapiro
discuss list flattening in "The Art of Prolog". That is easily
THE best Prolog textbook currently available. If you can only
afford one Prolog book, buy that one.
Here's my code for flatten/2:
% flatten(ConsTree, FlatList)
% flattens out a tree of cons cells into a list.
% Note that it only works that way around: given a List
% there are infinitely many ConsTrees it could have
% come from, including itself.
flatten(ConsTree, FlatList) :-
flatten(ConsTree, FlatList, []).
flatten([], Flat0, Flat) :- !,
Flat0 = Flat.
flatten([Head|Tail], Flat0, Flat) :- !,
flatten(Head, Flat0, Flat1),
flatten(Tail, Flat1, Flat).
flatten(Other, [Other|Flat], Flat).
There is a subtle difference: according to my definition
flatten(a, X) binds X = [a], whereas according to Lagache's
it fails. I consider this to be a bug in Lagache's version:
since flatten([a], X), flatten([[a]], X), flatten([[[a]]], X)
all bind X = [a], why not flatten(a, X)?
There is an important practical difference: this version
makes NO structure that will not appear in the final result,
whereas Lagache's keeps on copying things.
All of this is not really important. I've been writing Prolog
for nearly 8 years and have never yet found a use for flatten/2,
and I've been writing Lisp longer than that and never found a
use for (flatten -) there either. [The other functions in the
public domain FLAT.PL, such as and_to_list/2, HAVE been of use.]
assoc/3
-------
(1) If you want to associate keys with values, you will find two
useful packages in the public-domain DEC-10 Prolog library
held at Stanford: ASSOC.PL (trees) and MAPS.PL (sequences).
You will also find a predicate keys_and_values/3 in PROJEC.PL
which is similar to Lagache's make_assoc_list/3. More about
that shortly.
(2) Lagache's code was
assoc(_,[],error):- !,fail. /* Base recursive case, No such
element found */
assoc(Item,[Pair|_],Pair):- found_item(Pair,Item). /*
Successful match */
assoc(Item,[_|Rest],Pair):- assoc(Item,Rest,Pair). /*
Continue search */
found_item([Item|_],Item). /* test if 'car' of list is
'Item' */
This time I haven't sanitised it.
Some points to note: "base recursive case" contradicts itself. The
base case is not recursive. The first clause is entirely redundant.
This could be coded directly as
assoc(Key, [Cons|_], Cons) :-
Cons = [Key|_].
assoc(Key, [_|Conses], Cons) :-
assoc(Key, Conses, Cons).
or perhaps more lucidly as
assoc(Key, Conses, Cons) :-
Cons = [Key|_],
member(Cons, Conses).
Note that [X|Y] is a cons cell, not a pair.
And [X,Y] is a (two-element) list, not a pair.
X-Y is a pair.
There are two good reasons for using pairs rather than conses.
(a) The result can be type-checked by the Mycroft&O'Keefe type
checker. Source code for that is available in the public-
domain Prolog library at Stanford, see TYPECH.PL & PROLOG.TYP.
The full report from DAI Edinburgh contains a listing.
We would say
:- type list(T) --> [] | .(T,list(T)). % in PROLOG.TYP
:- type pair(K,V) --> K-V. % in PROLOG.TYP
:- pred keysort(list(pair(K,V)), list(pair(K,V))). % "
:- pred assoc(K, list(pair(K,V)), pair(K,V)).
assoc(Key, [Pair|_], Pair) :-
Pair = Key-_Value.
assoc(Key, [_|Pairs], Pair) :-
assoc(Key, Pairs, Pair).
Using conses instead of pairs basically rules out type
checking. (Turbo Prolog victims note.)
(b) The built-in predicate keysort/2 sorts lists of pairs,
not lists of conses. A moderately common idiom is to
write
:- pred sort_by_separate_keys(list(K), list(V), list(K)).
:- pred sort_aux(list(K), list(V), list(pair(K,V)),
list(V), list(pair(K,V))).
sort_by_separate_keys(RawKeys, RawVals, OrdVals) :-
sort_aux(RawKeys, RawVals, RawPairs, OrdVals, OrdPairs),
keysort(RawPairs, OrdPairs).
sort_aux([], [], [], [], []).
sort_aux([K|Ks], [V|Vs], [K-V|Ps], [W|Ws], [_-W|Qs]) :-
sort_aux(Ks, Vs, Ps, Ws, Qs).
As an example of why keysort/2 is useful, suppose that we want
to know whether a given association list is a partial function.
That is, does each key appear at most once in the list?
The obvious way to code this is
non_redundant([]).
non_redundant([K-_|Pairs]) :-
\+ memberchk(K-_, Pairs),
non_redundant(Pairs).
But this takes O(N^2) time for a list of N pairs. It is
better to use keysort/2 thus:
non_redundant(RawPairs) :-
keysort(RawPairs, OrdPairs),
\+ append(_, [K-_,K-_|_], OrdPairs).
make_assoc_list/3 has two redundant clauses. In fact, they are
worse than redundant, because they destroy its logical character.
Lagache's code was
make_assoc_list([], [], []).
make_assoc_list([], List2, List2) :- !, fail.
make_assoc_list(List1, [], List1) :- !, fail.
make_assoc_list([Head1|Tail1], [Head2|Tail2], [[Head1,Head2]|R]) :-
make_assoc_list(Tail1, Tail2, R),
!.
I shouldn't have to point out that the cut in the last clause is
useless. Should I?
Non-redundant code would be
make_assoc_list([], [], []).
make_assoc_list([Key|Keys], [Value|Values], [[Key,Value]|Lists]) :-
make_assoc_list(Keys, Values, Lists).
This is similar to keys_and_values/3 in PROJEC.PL:
keys_and_values([], [], []).
keys_and_values([Key-Value|Pairs], [Key|Keys], [Value|Values]) :-
keys_and_values(Pairs, Keys, Values).
The advantages of my version over Lagache's are several:
-- purity. It doesn't use cuts.
-- clarity. It is instantly clear that there are just two cases
which can lead to success. (An induction on any one of the
arguments leads directly to this code.)
-- correctness. My version does indeed define a relation.
Lagache's doesn't.
This last point may need explanation. Suppose someone gives me an
association list, and I want to have the keys and values as
separate lists. (This is actually the use keys_and_values/3 is
optimised for.) Then I can just call
make_assoc_list(Keys, Values, TheListIWasGiven)
At least, I can do that with my definition. If Keys and Values are
variables, as they would be in this case, Lagache's definition will
FAIL unless TheListIWasGiven is empty. Here is a transcript:
| ?- make_assoc_list([a,b], [1,2], X).
X = [[a,1],[b,2]]
yes
| ?- make_assoc_list(X, Y, [[a,1],[b,2]]).
no
What went wrong? The second clause matched, binding
X = [], List2 = Y = [[a,1],[b,2]], and then cut and failed.
Exercise for the reader: use this idea to see how Lagache's
subst/4 can be broken. (Hint: correct optimised code is
subst([], _, [], _).
subst([A|As], Old, [B|Bs], New) :-
( A = Old -> B = New ; B = A ),
subst(As, Old, Bs, New).
Aside from exploiting indexing, what is diferent?
Second hint: the name of the design principle that Lagache's
code violates is "The Principle of Allowed Prophets".)
General remarks.
---------------
Lagache's STDLIST.PRO library shows a strong Lisp influence.
There's no harm in that: I keep saying that Prolog implementors
should look to Common Lisp for ideas. But Lagache has followed
his Lisp originals too slavishly. The following criticisms
apply to nearly everything in that library, with the exception
of operations like member/2 and append/3 which have previously
been published:
(1) Failure to exploit tail recursion optimisation.
(2) Many of the predicates are defined so that they can only
work one way around. For example, get_head/3 could have
been defined to fail when the list was too short, and in
that case it could have been implemented reversibly.
(3) Many of the predicates are implemented so that they will
only work one way around, when it would be easy to code
them so that they implement a logical relation. A good
example is reverse/2. A trivial change would make it
fully reversible, but as written it is backwards-incorrect.
(4) More generally, many of the predicates don't do exactly
what the documentation says they do: there are unstated
preconditions.
(5) There are a lot of :- !, fail clauses which are harmful.
And so on.
------------------------------
End of PROLOG Digest
********************