PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (09/30/87)
PROLOG Digest Thursday, 1 Oct 1987 Volume 5 : Issue 70
Today's Topics:
Implementation - Sour Persimmons,
& List Syntax & Argument Order
----------------------------------------------------------------------
Date: 29 Sep 87 18:05:24 GMT
From: Edouard Lagache <violet.berkeley.edu!lagache@jade.Berkeley.EDU>
Subject: Thanks for the sour persimmons cousins
Well I am certainly glad that at least someone went to the trouble of
actually reading my PROLOG library code (on second thought, maybe it
would have been better otherwise ....)
To be quite honest, I thought that nit-pickers were only to be found in
model railroading and other "precision" hobbies, but I guess the PROLOG
net has its own set, and regrettably, I didn't put a "no nit-picking"
sign on my documentation.
So on to the nit-picks: First, the highly optimal code of Lee Naish
i.e.
merge([],[],[]).
merge(Head1.Tail1, Head2.Tail2, Head1.Head2.R) :-
merge(Tail1,Tail2,R).
does not run on the A.D.A. VML PROLOG interpreter. It complains about
finding "unexpected period on line 2". While I believe the dot
notation for cons cells is part of the original language specification,
it isn't mentioned in Clocksin and Mellish, and thus, is missing from
at least one PROLOG implementation.
As to the complaints on '!,fail' clauses. I too am fully aware that
they are redundant. However, what a computer can easily deduce from
the code, may be difficult for humans to discern, particularly for
those new to PROLOG. While A.I. researchers seem determined to make
their code as cryptic as possible, the rest of the programming world is
still in the midst of a "readability revolution". Given the terseness
of some of the code touted as "improvements" over my work, it may be
time for some people on this net to go back and take a course in
structured Pascal!
Finally, there were a number of important comments that I will keep and
attempt to implement after I complete my Master's Thesis this fall. I
am not a PROLOG guru, and never claimed that I was. Nor was I aware of
what other sorts of public domain PROLOG libraries already existed.
My entire objective was to produce a clean, well documented package of
basic predicates in order to save other programmers from having to re-
invent the wheel. With the help of everyone on the net, these
libraries can be made optimal, and the documentation can be made both
more readable and accurate. However, unless people take a more
constructive and less antagonistic attitude toward contributions, not
only will these libraries die of neglect, but people will simply not
contribute valuable materials to avoid the grief that I have had the
pleasure of enduring!
Edouard Lagache
School of Education
U.C. Berkeley
------------------------------
Date: 30 Sep 87 05:22:46 GMT
From: Lee Naish <munnari!mulga!lee@uunet.uu.net>
Subject: Thanks for the sour persimmons cousins
I think it is unfortunate that there has been so much negative
feedback for Lagache's code. There have been other collections of
code posted to the net (worse than the recent posting, I think) which
people have quietly ignored. Recent postings are a result of long
term frustration, and are not personal attacks. Hopefully people will
learn from these postings (I have).
> merge([],[],[]).
> merge(Head1.Tail1, Head2.Tail2, Head1.Head2.R) :-
> merge(Tail1,Tail2,R).
> does not run on the A.D.A. VML PROLOG interpreter. It complains about
> finding "unexpected period on line 2". While I believe the dot
> notation for cons cells is part of the original language specification,
> it isn't mentioned in Clocksin and Mellish, and thus, is missing from
> at least one PROLOG implementation.
It can be made to run on some Prolog systems which object to it at
first by declaring . as an operator. One thing which has always
puzzled me is why people (even the best Prolog programmers in the
civilized world), insist on using [H|T] instead of H.T and why
implementors support the first syntax more.
H.T is more readable
H.T says the functor is '.' and there are two arguments, H and T
H.T is one less character
H.T doesn't use 'funny' characters used for letters in Europe
H.T is not a syntactic special case (well,.. less so)
[H|T] confuses people. It has confused Prolog implementors! There are
Prolog implementations in which lists are not normal terms, due to this.
Of course it is a shame that '.' and ',' are so overloaded in Prolog,
but since '.' IS the list constructor functor, we may as well get it
out in the open for all to see.
Readability is in the eye of the beholder (see my previous comment).
However, I think it is generally agreed that cut does not aid readability.
An advantage that (clean) Prolog has over Pascal (no matter how structured)
is that it has declarative semantics. People should rediscover this every
few months; one tends to forget.
-- Lee Naish
------------------------------
Date: Tue, 29 Sep 87 00:08:04 PDT
From: Richard A. O'Keefe <quintus!cresswell!ok@Sun.COM>
Subject: Argument order
I have been asked to clarify what I meant by
"the convention of putting meta-arguments first".
One of the problems with Prolog is that a typical predicate
needs rather more arguments than the corresponding function in
Pascal, Lisp, or other imperative languages. The reason for
this is that each non-local constant corresponds to an extra
argument, and each variable updated in a loop corresponds to a
pair of extra arguments. Thus where in C you might write
s = 0;
for (i = N; --i >= 0; ) s += L[i]
in Prolog you would write
p(L, 0, S)
where
p([], S, S).
p([X|Xs], S0, S) :-
S1 is S0+X,
p(Xs, S1, S).
Viewed from a sufficiently great height, these are the same
piece of code.
The more arguments you have, the easier it is to get
confused. So you need some systematic convention for keeping
track of what goes where. This is especially important for the
interfaces of modules or library packages, or in general for
anything that other people are supposed to see.
The fundamental argument order convention in Prolog is
+----------------------------+
| INPUTS BEFORE OUTPUTS |
+----------------------------+
This used to be almost but not quite arbitrary. Given that
people will be reading your code from left to right, pattern
matching on inputs will be seen first, and it will be easier for
someone reading your code to determine how it works if you
follow this convention. Pop-2 programmers will of course agree
totally with this convention, and APL programmers have always
followed it, though they interpret "before" as "to the right
of". However, whether you prefer this order or not, the fact is
that most Prolog systems that provide any kind of indexing
provide it on the first argument (yes, better indexing is
needed) so that if you put inputs before outputs, indexing is
more likely to help you.
But there are other things going on than just simple inputs
and outputs. For example, there are difference lists. More
generally, you may have several arguments that correspond to
positions in a physical or logical sequence. The convention is
that they will be named Foo0, Foo1, ..., Foo (for your choice of
name Foo), and that such of these variables as appear in the
clause head will appear together in logical order. The usual
example of this is DCG rules, where the translation of
p --> q, r.
is
p(S0, S) :- q(S0, S1), r(S1, S).
It usually helps to think of such positions as a single output
which happens to occupy several argument positions.
In the p/3 example above (the guts of sumlist/2), the last
two arguments are an accumulator pair, which should be thought
of as a single output (the number S-S0) which is realised as two
arguments. p/3 thus has its input preceding its output, as it
should.
But inputs come in several flavours. The basic rule is that
they are ordered by degree of inputness. This was how we
originally understood arg/3.
arg(N, Term, Arg)
The third argument is usually thought of as an output. The
first argument must be completely ground, whereas the second
argument need only be instantiated. So the first argument is a
"harder" input than the second. In fact we often use arg/3 to
fill in an argument of a term, so the second argument is a bit
like an output.
A special case of this rule is that I/O operations which take
a parameter identifying the "stream" to be used always have this
parameter first. Such an argument must always be ground, so
this is an instance of "strict inputs before other inputs".
What happens if you have several stream arguments to a single
procedure? (One is bad enough, in all conscience. That could
be the topic of another note.) Well, we can apply the
fundamental rule again, with tongue in cheek.
Input stream arguments come first, then
Output stream arguments, next, then
all the other arguments.
arg/3 has served as the model for a large family of
predicates that notionally fetch some element out of a
collection, or update a collection. The general scheme is
Index < Collection < Element
Hence we have
arg(Index, Term, Argument)
fetch(Index, Array, Element)
get_assoc(Key, AssociationTree, Value)
This even explains member/2
member(Pattern, Collection /* -> true or false */)
What should we do when we are updating a data structure (or
rather, when we are computing a modified one)? Follow the
rules: inputs before outputs, otherwise like selection. So you
might expect
change_arg(Index, OldTerm, NewArgument, NewTerm).
That would make a lot of sense. But it is better to look for a
scheme which is more generally consistent. A point to bear in
mind is that it is useful to think in terms of groups of
arguments. So it is useful to think of a Collection+Element
group, and to try to put a collection and its related element
always in the same order. So we think of it as
change_arg(Index, <old group>, <new group>)
and arrive at
change_arg(Index, OldTerm, NewTerm, NewArg)
and, when you want to express the transformation by pattern
matching on the elements,
change_arg(Index, OldTerm, OldArg, NewTerm, NewArg).
Isn't this a bit artificial? Yes, the whole idea of any sort
of convention is artificial. But remember difference groups.
It is very often useful to think of the Collection and Element
as "positions" in a tree. We think of the entire GROUP
consisting of the Collection and its Element as a single input
or output. The Collection preceding the Element is just like
the Front of a difference list preceding the Back. To point up
the parallel:
path_arg([], Term, Term).
path_arg([Index|Indices], Term0, Term) :-
arg(Index, Term0, Term1),
path_arg(Indices, Term1, Term).
has EXACTLY the same logical structure as
append2([], List, List).
append2([X|Xs], List0, List) :-
List0 = [X|List1],
append2(Xs, List1, List).
What about meta-arguments, though?
A meta-argument is a (possibly incomplete) goal.
Examples are
\+(G), G
setof(T, G, S) G
once(G) G
forall(G1, G2) G1, G2
maplist(P, Xs, Ys) P {will have 2 more arguments}
Now meta-arguments have very much the character of an input. A
Prolog system which could solve for the P argument in a call to
maplist(P, Xs, Ys) would be a very clever system indeed. So
they are a pretty strong sort of input.
maplist/3 CAN solve for its second argument given its third.
But it can't solve for its first. So the meta-argument is
stricter than the list, even though we might be tempted to think
of the second argument as only an input.
It is easily observed that most predicates with a meta-
argument really should put it first by the rules we have already
given. For example, consider a sorting routine.
some_sort(Comparison, Unordered, Ordered)
If the sorting routine resembles keysort/2 rather than sort/2,
we could in principle enumerate the permutations of Ordered and
generate Unordered if we had to. If you think about it, you'll
see that it is easy to compute Ordered given Unordered and
Comparison, easy but impractical to computer Unordered given
Ordered and Comparison, and quite out of the question to solve
for Comparison at all. This observation is generalised to the
convention of putting meta-arguments first.
In fact, I lied to you before. Meta-arguments come even
before streams. A Prolog system has only a smallish number of
streams open at one time, so it could enumerate them. In most
cases, it wouldn't be a good idea, but it could be done. So we
get operations like
Goal with_output_to Stream
Goal with_input_from Stream
One final step will give us all the conventions I know of.
How do setof/3, bagof/3, findall/3, aggregate/3, and so on fit
in? They appear to be exceptional.
This is an arbitrary rule: a Template argument comes first
in its group. We should think of the input to bagof/3 &c as the
group <Template, Generator>. Suppose we had a predicate
modify(OldPattern, Filter, NewPattern, Generator)
which was supposed to replace each instance of OldPattern in the
data base which satisfies Filter by all the instances of
NewPattern that the corresponding instance of Generator
enumerates. This operation has two input groups, in each of
which a Template precedes its Generator.
Templates are meta-arguments in another sense: the effect of
the predicate depends on the instantiation state of the
Template, but the Template will not end up further instantiated
by the call.
So we end up with the convention
+----------------------------------------------------------------+
| Meta-arguments < Streams < Ground inputs < Inputs < Outputs |
+----------------------------------------------------------------+
applying at the group level, and
+----------------------------------------------------------------+
| Selector < Collection < Element |
| Template < Goal |
| Foo0 < Foo1 < ... < Foo |
+----------------------------------------------------------------+
applying within the group level.
These conventions came about the way that the principles of
Jurisprudence came about: trying to make sense of the cases
that already existed. They express the idea "inputs before
outputs" in much the way that the legal system expreses the idea
of justice: imperfectly, but better than nothing.
The advantage of using these conventions is that it makes
coding AND using a package so much easier. As designer, you do
not have to invest a lot of effort in trying to work out which
of 5! argument orders to use (often there will only be one
permitted by the conventions). As coder, you will be able to
remember the order you chose. And as package user, you will not
have to keep referring back to the manual to discover what
argument order the designer chose.
For example, suppose you want an operation which takes a data
structure BigThing, a list of items within it WhichOnes, and a
stream WhereToPutThem, and writes the selected items to the
stream. These conventions don't tell you what it it is called,
but they DO tell you that the order must be
WhereToPutThem, WhichOnes, BigThing
That's (3!-1) cases you didn't need to consider as a designer,
5 mistakes you won't make as a user.
It is worth repeating that it isn't quite so important to
follow these convensions within a package. Shifting the
meta-arguments out of the way so that you can index on something
interesting is a particularly valuable thing to do. But you do
NOT make the users of your package have to guess which way round
you found it most efficient to put things. Don't be afraid of
adding interface predicates such as
quick_sort(Comparison, Input, Output) :-
qs1(Input, Comparison, Output).
It's only a variable shuffle and a jump after all, and it is a
wonderful opportunity to put some error checking code in.
------------------------------
End of PROLOG Digest
********************