PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (09/28/87)
PROLOG Digest Monday, 28 Sep 1987 Volume 5 : Issue 67
Today's Topics:
Implementation - call/N
----------------------------------------------------------------------
Date: Sat, 26 Sep 87 15:40:33 PDT
From: Richard A. O'Keefe <quintus!cresswell!ok@Sun.COM>
Subject: The call/N family.
In the documentation for Lagache's regrettable library, he says of
call/1 that
Older PROLOGs require the 'call' predicate whenever
goals are constructed using '=..'. In order to
maintain compatibility with these old PROLOG[sic]
it is advisable to use 'call' even when it isn't
required by your PROLOG. ... Eventually, as these
older PROLOGs become extinct, this predicate will
be eliminated.
There are several points to note about this.
First, from very early DEC-10 Prolog days, "X" has been accepted as a
goal equivalent to "call(X)". EVERY PROLOG which claims to be in the
"Edinburgh" family should act like this. Certainly, the following
Prologs do:
DEC-10 Prolog
PDP-11 NU7 Prolog
EMAS Prolog
C Prolog (all versions)
POPLOG
LM-Prolog
IF Prolog
BIM Prolog
Arity Prolog
ALS Prolog
Quintus Prolog
Xerox Quintus Prolog
Note that LM-Prolog isn't even in the Edinburgh family. Failure of a
Prolog system to handle the goal "X" as "call(X)" is not a sign of
age: it is a sign that the implementors just couldn't care less about
compatibility.
The second point is that a Prolog programmer who cares about
efficiency will almost NEVER use univ (=..). This piece of advice is
unfortunately system-dependent". In those Prolog systems such as
micro-PROLOG or LM-Prolog where there is only one functor (./2) univ
and = tend to have the same implementation. The LM-Prolog manual
explicitly states that "=.." is equivalent to "=". In interpreted
Prolog systems, univ, though intrinsically inefficient, may be
hand-coded faster than anything you could write in Prolog. But in a
compiled Prolog system such as DEC-10 Prolog, ALS Prolog, or Quintus
Prolog, univ is typically defined in Prolog, using functor/3 and
arg/3.
Thus, if you have a predicate name in the atom P, and two arguments X
and Y, the most efficient way of calling P with those arguments is to
code
functor(Goal, P, 2),
arg(1, Goal, X),
arg(2, Goal, Y),
call(Goal)
A smart compiler (such as the current Quintus Prolog compiler) will
optimise calls to univ with an explicit list, so that
Goal =.. [P,X,Y],
call(Goal)
will produce this effect.
Oh yes, the reason why univ is intrinsically inefficient is that it
involves constructing a list that you don't really want. It takes
time to make the list and more time to garbage collect it. You are
better off not making it in the first place, EXCEPT in those systems
where =.. and = are identical.
But the reason that call/1 isn't going to go away is that far and away
the clearest way of expressing "call P with arguments X and Y"
is to use the predicate call/3, thus:
The public-domain library file ARG.PL held at Stanford defines
call(Pred, Arg1)
call(Pred, Arg1, Arg2)
call(Pred, Arg1, Arg2, Arg3)
call(Pred, Arg1, Arg2, Arg3, Arg4)
Why would one use these?
(1) Clarity.
The details of how the goal is constructed are of no interest to
the reader. Using call/N makes it instantly obvious that what is
going on is a call of a dynamically bound predicate, not the
construction of a data structure.
(2) Implementation independence.
Since the method of constructing the actual goal is concealed,
whatever method is most efficient for the particular Prolog system
can be used. The implementation might use univ, or it might use
the code in the existing APPLY.PL library file, or it might be
built in at micro-code level.
(3) Generality.
I'll get onto this in a minute.
There is one other point, which is whether it is better to write
call(Pred, Arg1, Arg2)
or to write
Pred(Arg1, Arg2)
It is important to realise that this is ONLY a syntax issue. (I am
assuming here a conventional Prolog rather than a sound implementation
TOKENS.PL
+ READ.PL
used to map the source term
Pred(Arg1, Arg2)
for Pred a variable, to the actual term
apply(Pred, [Arg1,Arg2])
To have it produce
call(Pred, Arg1, Arg2)
instead, the first clause of read/5 should read
read(var(Variable,_), ['('|S1], Precedence, Answer, S) :- !,
read(S1, 999, Arg1, S2),
read_args(S2, RestArgs, S3), !,
Term =.. [call,Variable,Arg1|RestArgs],
exprtl0(S3, Term, Precedence, Answer, S).
(This is one of the few occasions where =.. is useful: we do not know
how long RestArgs is.)
I personally find that writing 'call' explicitly is MUCH clearer than
writing a variable in predicate position, especially given the number
of Prolog systems (such as BIM Prolog) which feature upper-case
constants.
But whether one writes call(P,X,Y) or P(X,Y), the operation has to
exist for you to use it, so what harm is there in giving it a name?
To return to point (3): generality. There is a very important
difference between
call(Pred, X, Y)
and Goal =.. [Pred,X,Y], call(Goal).
The difference is that if you use univ explicitly, Pred can ONLY be an
atom! Now that is a very strange and VERY severe restriction. call/1
will accept any callable term as its first argument, not just an atom.
So should EVERY memory of the call/N family. And the public version
of APPLY.PL has always supported this. The rule is that the extra
arguments go at the end.
Let me give you an example to show you how this is useful. Suppose we
have a predicate maplist/3. Here's the definition (which is also in
APPLY.PL):
maplist(_, [], []).
maplist(Pred, [X|Xs], [Y|Ys]) :-
call(Pred, X, Y),
maplist(Pred, Xs, Ys).
Now, suppose I want to reverse all the elements in a list of lists. I
can do
maplist(reverse, Ls, Rs)
That much could have been done with =.. and meta-call. But suppose I
want to check whether all the elements of a list of lists have a
common prefix, and to extract that prefix. I can do
maplist(append(CommonPrefix), Remnants, Lists)
Here's a transcript:
| ?- maplist(append(C), Remnants, [[a,b,c],[a,b,l,e],[a,b,b,o,t]]).
Remnants = [[a,b,c],[a,b,l,e],[a,b,b,o,t]]
C = [] ;
Remnants = [[b,c],[b,l,e],[b,b,o,t]]
C = [a] ;
Remnants = [[c],[l,e],[b,o,t]]
C = [a,b] ;
no
THE ABILITY TO PASS COMPOUND TERMS TO call/N in PROLOG
IS THE EQUIVALENT OF CLOSURES IN LISP.
It is interesting to note that Lagache's quicksort/3 not only violates
the convention of putting meta-arguments first, but is quite
pointlessly restrictive in forcing the meta-argument to be an atom
rather than a closure.
Here is his code, rearranged to be readable:
quicksort(Unsort, Pred, Result) :-
quisort2(Unsort, Pred, Result, []).
quisort2([Item|Tail], Pred, Sort, Partial1) :-
split2(Item, Tail, Pred, Part1, Part2),
quisort2(Part2, Pred, Partial2, Partial1),
quisort2(Part1, Pred, Sort, [Item|Partial2]).
quisort2([], _, Sort, Result) :- !,
Sort = Result.
split2(Item, [Head|List], Pred, Small, [Head|Big]) :-
Test =.. [Pred, Head, Item],
call(Test),
split2(Item, List, Pred, Small, Big).
split2(Item, [Head|List], Pred, [Head|Small], Big) :-
Test =.. [Pred, Head, Item],
not(call(Test)),
split2(Item, List, Pred, Small, Big).
split2(_, [], _, [], []).
[By the way, when WILL people realise that quick sort is NOT a good
sorting method for Prolog? It was included in Clocksin & Mellish as
an example of how to use DIFFERENCE LISTS, not as an example of how to
sort! merge sort is MUCH better for Prolog.]
The following changes should be made.
(1) The convention of putting meta-arguments first should be followed.
This convention applies only to the interface level, not to the
auxiliary predicates.
(2) The comparison predicate should resemble the built-in predicate
compare/3. Indeed, it should be possible to pass compare/3 to the
generalised sorting routine and obtain the special case.
(3) The call/N family should be used rather than univ.
We obtain
quick_sort(Comparison, Input, Output) :-
quick(Input, Comparison, Answer, []),
Output = Answer.
quick([], _, Answer, Answer).
quick([Head|Tail], Comparison, Answer0, Answer) :-
partition(Tail, Head, Comparison, Less, Equal, Answer2, Greater),
quick(Less, Comparison, Answer0, [Head|Equal]),
quick(Greater, Comparison, Answer2, Answer).
partition([], _, _, [], E, E, []).
partition([Head|Tail], Parting, Comparison, L, E0, E, G) :-
call(Comparison, Rel, Head, Parting),
partition(Rel, Parting, Comparison, L, E0, E, G, Head, Tail).
partition(<, Parting, Comparison, [Head|L], E0, E, G, Head, Tail) :-
partition(Tail, Parting, Comparison, L, E0, E, G).
partition(>, Parting, Comparison, L, E0, E, [Head|G], Head, Tail) :-
partition(Tail, Parting, Comparison, L, E0, E, G).
partition(=, Parting, Comparison, L, [Head|E0], E, G, Head, Tail) :-
partition(Tail, Parting, Comparison, L, E0, E, G).
{ Oh yes, this version is STABLE, which Lagache's isn't.
That means that you can use this version to sort by several keys,
but you can't use his version that way. It is rather perverse to
offer for general consumption an unstable quadratic sorting
algorithm when the "native" merge sort is stable and N.lgN.
}
Now suppose we have a predicate compare_padded(Pad, Rel, S1, S2)
which compares two constants using a specified pad character. And
suppose that we would like to have a predicate which sorts a list
of constants using a pad character given as parameter. Then we do
sort_padded(Pad, Input, Output) :-
quick_sort(compare_padded(Pad), Input, Output).
I urge Prolog implementors to provide the call/N family,
and Prolog programmers to demand it from their Prolog vendor.
------------------------------
End of PROLOG Digest
********************dowding@bigburd.UUCP (09/29/87)
>Date: Sat, 26 Sep 87 15:40:33 PDT >From: Richard A. O'Keefe <quintus!cresswell!ok@Sun.COM> >Subject: The call/N family. > I enjoyed this response by O'Keefe very much. I would like to see more advice from the Prolog sages on the net. I do have a few small comments to make: >In those Prolog systems such as >micro-PROLOG or LM-Prolog where there is only one functor (./2) univ >and = tend to have the same implementation. The LM-Prolog manual >explicitly states that "=.." is equivalent to "=". This also used to be true of Symbolics Prolog (it may have been changed in recent releases), and it has caused some compatablity problems, namely when the left-hand-side of "=.." is an atom: foo =.. [foo] but foo should not unify with [foo]. > >Oh yes, the reason why univ is intrinsically inefficient is that it >involves constructing a list that you don't really want. It takes >time to make the list and more time to garbage collect it. You are >better off not making it in the first place, EXCEPT in those systems >where =.. and = are identical. > I think that there are still cases in which you must use "=..". Take, for instance, the program that takes a DCG and produces equivalent Prolog code. This program must add to arguments to the end of every procedure call in the DCG. This cant be done with call/N family because you dont want to execute the procedure call, just create it. Because you dont know in advance how many arguments the nonterminals will have, you must use "=..", not functor and arg. In this case, you really do want to construct this list. John Dowding --