🚀 go-pugleaf

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
********************