Appeared in Volume 10/1, February 1997

**lee@cs.mu.oz.au
Lee Naish
10th November 1996**

If people still think that call/N or, heaven forbid, even less expressive
primitives are the right way to do higher order logic programming,
*please* take a look at:

http://www.cs.mu.oz.au/~lee/papers/ho.

The abstract:

**Higher-order logic programming in Prolog **

Lee Naish

This is yet another paper which tells logic programmers what functional
programmers have known and practiced for a long time: "higher order"
programming is the way to go. How is this paper different from some of the
others? First, we point out that call/N is not the way to go, despite its
recent popularity as the primitive to use for higher order logic programming.
Second, we use standard Prolog rather than a new language. Third, we compare
higher order programming with the skeletons and techniques approach. Fourth, we
present solutions to some (slightly) more challenging programming tasks. The
interaction between higher order programming and some of the unique features of
logic programming is illustrated and some important programming techniques are
discussed. Finally, we examine the efficiency issue.

**ok@goanna.cs.rmit.edu.au
Richard A. O'Keefe
11th November 1996**

After looking at Lee's excellent paper, there are a number of things that I would like to point out:

(1) Alan Mycroft and I invented call/N together. No-one else was involved.

(2) Of course, what that *really* means is that we *reinvented*
'funcall'.

(3) Our chief concern was that the primitive should lend itself to Milner-style typechecking.

(4) We wanted a *small* set of changes to Prolog to get a typable
language.

(5) For that reason we *couldn't* adopt the apply/3 primitive that Lee's
paper describes. In particular, the intention is that:

`apply(plus(2), X, Y)` calls `plus(2, X, Y)`

*but:*

`apply(plus, 2, X)` binds X to a representation of
`lambda Y. plus(2, X, Y)`.

This *could* not be done in a system where plus/3 and plus/2 were
completely unrelated predicates; call(plus, 2, X) tries to call plus(2, X) and
sometimes it will work because there will be a plus/2 predicate for it to
call.

(6) call/N lends itself to extremely efficient implementation. (I worked out, implemented, and tested a call/N implementation at Quintus, but was over-ruled about including it in the language.)

Lee's main criticism of call/N appears to be that it allows closures to be
*called* *but* not to be *returned* as results. This criticism
is accurate and fair. His example 12 is an example of this limitation.

However, the problem with example 11 is not any limitation of call/N, but
simply a consequence of the fact that the example is ill-typed and makes no
sense. In common-sense terms: 'map' returns *one* list result, but
'append' wants *two* lists.

What's actually wanted here is a different composition operation. We want:

so we need:

:- pred compose_2(void(U, V, W), void(X, U), X, V, W) % ( ( U x V -> W) x (X -> U) x X x V -> W) compose_2(F, G, X, V, W) :- call(G, X, U), call(F, U, V, W). ex_11_done_right(Xs) :- foldr(compose_2(append, map(plus(1))), [[2], [3,4], [5]], [], Xs).Load the type-correct code into NU Prolog and it runs like a charm. The analogous code in Clean would fail in type checking, just as example 11 fails in the DEC-10 Prolog type checker.

In fairness to the call/N approach, it should have been noted that that much of
the "skeletons and techniques" stuff in section 7 not only *can* be done,
but *has* been done using call/N.

The paper basically says:

call(P(X1,...,Xm), Y1,...,Yn) :- P(X1,...,Xm, Y1,...,Yn)That's fine, but it requires

Let's see what we _can_ do with call/N, without apply/3.

We turn to Lisp, with its funcall primitive exactly similar to call/N. How does Lisp avoid the problem with example 12?

ex_12(Xs) :- map(plus, [2,3,4], Xs).This fails in type checked Prolog because

In the same way, if the following is given:

(defun plus-1 (X Y) (+ X Y)) (defun map-1 (F L) (if (null L) '() (cons (funcall F (car L)) (map-1 F (cdr L)) )) )Then the call:

fails in Lisp. Here's the message:

`Error: PLUS-1 [or a callee] requires two arguments, but only one was
supplied.`

What should we do to fix it? Write:

(map-1 #'(lambda (x) #'(lambda (y) (plus-1 x y))) '(2 3 4))which in GNU Common Lisp (gcl) prints:

((LAMBDA-CLOSURE ((X 2)) () () (Y) (PLUS-1 X Y)) (LAMBDA-CLOSURE ((X 3)) () () (Y) (PLUS-1 X Y)) (LAMBDA-CLOSURE ((X 4)) () () (Y) (PLUS-1 X Y)))This is nothing more nor less than explicit Currying, so Lee's attack on call/N amounts to "call/N requires explicit Currying, while apply/3 does it implicitly".

Here's what we want. We want to take:

<some term>[ plus ] Xand obtain a partially applied closure, for which:

will do fine. Here's a suitable method:

:- pred curry(void(X, Y, Z), X, void(Y, Z)). curry(P, X, call(P, X)).Now:

ex_12(Xs) :- map(curry(plus), [2,3,4], Xs). demo(X) :- % requires map/4 ex_12(P),> map(call, P, [4,3,2], X).What apply/3 can do, so can call/N, with a suitable small set of combinators.

We can debate which of the two approaches is to be preferred on grounds of
style, readability, maintainabilty, efficiency, type checking, etc. However, it
would be absurd to suggest that apply/3 is more *powerful* than call/N.
(A number of Lee's examples look as though they would be simpler with call/N;
his use of apply4/4 makes me wonder.)

**Points of long standing agreement:**

- Higher-order programming in Prolog is possible;
- Higher-order programming in Prolog is relatively easy;
- Higher-order programming in Prolog is desirable;
- call/N is easy to type check (not
*easier*than anything in particular, just*easy*); - call/N
*can*be implemented very efficiently, but often isn't; - call/N requires
*explicit*currying and never*returns*a closure of its own accord; - apply/3 (and the several relatives that Lee develops)
*does*return a closure of its own accord, bringing it closer to the "every function has exactly one argument" style of Haskell; - apply/3 (and its several relatives) can be used effectively to do higher-order
programming in Prolog.

**Points where I think we would agree, but I'm not sure:**

- call/N + curry/2, or at most a small fixed set of combinators, is just as
powerful as apply/3;
- Unifying non-variable closures is at best confusing, and certainly doesn't work
the way 2nd-order logic
*should*work; - Applying a function F to two arguments with call/N as in:

`call(F, X1, X2, Result)`

need not construct any intermediate data structures, and does not need extensive support in the compiler. Without powerful analysis in the compiler, doing this with apply/3, as in:

`apply(F, X1, F_of_X1),`

apply(F_of_X1, X2, Result)

will be less efficient because of the building of the intermediate F_of_X1.

**Points of disagreement:**

- call/N is not the way to go (it's
*one*good way in my view); - apply/3 is
*better*than call/N.

**Points left completely open by the paper and this article:**

- How do apply/3 and its relatives interact with Hindley/Milner-style type
checking (e.g. the Mycroft/O'Keefe type checker) or with any other type
checker?
- apply/3 is more strongly "directional" than call/N. How does this interact with
NU-Prolog-style coroutining, or Mercury-style mode analysis?

**lee@cs.mu.oz.au
Lee Naish
12th November 1996**

Richard A. O'Keefe writes:

*(4) We wanted a small set of changes to Prolog to get a typable
language.*

I certainly understand the difficulty of this. For example, the type checker treats integers and integer expressions as the same type because of (I assume) the difficulty of distinguishing them in a Milner-style type checker for Prolog. This is a pity, as confounding numbers and expressions is an important class of bugs for beginners.

He continues:

*(5) For that reason we couldn't adopt the apply/3 primitive
that...
This could not be done in a system where plus/3 and plus/2 were
completely unrelated predicates*

This is (mostly) a problem of the adopted Prolog programming style: i.e., the decision to often use the same procedure name with different number of arguments. The main advantage of this style, I believe, is that the name space is less cluttered. However, it makes some bugs difficult to detect (e.g., calling the wrong version of a predicate because you missed an argument). The NU-Prolog style checker therefore complains about it. When you are using higher order there is another reason to avoid it. It's nice to have an unambiguous interpretation of plus(2) rather than several possible interpretations depending on how many arguments may be added later.

He continues:

*(6) call/N lends itself to extremely efficient implementation.
(I worked out, implemented, and tested a call/N implementation a Quintus,
but was over-ruled about including it in the language.)*

A pity - it might have encouraged people to use it. It is implemented efficiently in NU-Prolog. However, apply/3 can be implemented just as efficiently as call/3. For a dumb compiler, I admit that call/3+k is faster. Is this important now (as opposed to when call/N was introduced)? I think not. The main point of higher order facilities, surely, is to allow the programmer to think and code at a higher level and to reuse procedural abstractions. It's the job of the implementation to make this acceptably efficient. We should be serious about higher order programming; serious enough for every compiler writer to spend a few days implementing specialisation of higher order code. Without this, higher order coding will be significantly slower using call/N or apply/3, especially if the argument ordering convention advocated by Richard is used. Let's look at his map/3:

map(P, [], []). map(P, [X|Xs], [Y|Ys]) :- call(P, X, Y), map(P, Xs, Ys).Without specialisation this will leave choice points. This is much more significant than the difference between call/N and apply/3, or whether these primitives are implemented in the most efficient way.

He continues:

*so we need
:- pred compose_2(void(U, V, W), void(X, U), X, V, W)*

This is the beautiful illustration of why currying is *a good thing*. With
currying you only need one version of compose. Without currying you need N.
Just as higher order programming allows you to write map once instead of a
thousand different instances of it, currying allows you to have more general
higher order abstractions.

He continues:

*This is nothing more nor less than explicit Currying, so Lee's attack on
call/N amounts to "call/N requires explicit Currying, while apply/3 does it
implicitly".*

I guess my paper says this implicitly, but it should say it explicitly :-). I think that "implicit currying" is a great thing, and the way to go.

He continues:

`:- pred curry(void(X, Y, Z), X, void(Y, Z)).
curry(P, X, call(P, X)).`

In general you need N of these.

He continues:

*What apply/3 can do, so can call/N, with a suitable small set of
combinators.*

Sure, but we can (and do) write it all in first order also. The question is, given a choice of a decent implentation of higher order facilities using call/N or apply/3, which would you choose? I would say the answer is clear.

He continues:

**Points of long standing agreement:**

Agreed!

He continues:

*call/N + curry/2, or at most a small fixed set of combinators, is just as
powerful as apply/3;*

There are both as powerful as Horn clauses; it's an issue of how nice the programs are.

He continues:

*Unifying non-variable closures is at best confusing, and certainly doesn't
work the way 2nd-order logic should work;*

Agreed. You also get this with call/N. The problem (mentioned in the workshop version of my paper) is that the intuitive intended interpretation (plus is a certain function) is at odds with the Clark equality axioms.

He continues:

*Applying a function F to two arguments with call/N as in
call(F, X1, X2, Result)
need not..*.

Agreed. However, let me counter with the following: compilers should optimise higher order code. This can be done easily so that, in most cases, the higher order overheads are completely avoided.

He continues:

*call/N is not the way to go (it's one good way in my view);*

I agree it's one good way to go, but I also think there is a better way.

He continues:

*apply/3 is better than call/N;*

I still believe this.

He continues:

*How do apply/3 and its relatives interact with Hindley/Milner-style type
checking (e.g. the Mycroft/O'Keefe type checker) or with any other type
checker?*

I did not discuss this in the paper. However, the higher order part works in exactly the same way as curried functional languages such as Haskell. Type checking should be no problem at all. The type of apply/3 is (a->b) -> a -> b, which is the same as (a->b) -> (a->b), i.e., apply/3 is a specialised version of the identity function.

He continues:

*apply/3 is more strongly "directional" than call/N; how does this interact
with NU-Prolog-style coroutining, or Mercury-style mode analysis?*

If the predicate is specified I don't think it makes a significant difference. I have done a fair bit of thinking about how higher order interacts with modes (particularly the declarative view of modes I have been advocating). Currently the interaction in Mercury is a bit messy and it would be really nice to clean it up a bit. Unfortunately, there seem to be some unavoidable complications with some cases of higher order functions using parametric polymorphism.

For your enjoyment I'll include a higher order version of nrev which is reversible (using NU-Prolog coroutining). It was cooked up as a benchmark for Maria de la Banda's abstract interpretation analysis system.

% one line higher order version of nrev % nrev = foldr ((converse (++)).(:[])) [] % nrev(As, Bs) :- foldr(compose(converse(app), converse(cons,[])), [], As, Bs). % uses special reversible version of foldr, so its reversible % rnrev(As, Bs) :- rfoldr(compose(converse(app), converse(cons,[])), [], As, Bs). % Ye Olde append :- app(A, B, C) when A or C. app([], A, A). app(A.B, C, A.D) :- app(B, C, D). % Ye Olde cons cons(H, T, H.T). % :- pred foldr(void(A, B, B), B, list(A), B). :- foldr(_, _, As, _) when As. % conservative foldr(F, B, [], B). foldr(F, B, A.As, R) :- foldr(F, B, As, R1), my_apply(F, A, FA), my_apply(FA, R1, R). % :- pred foldr(void(A, B, B), B, list(A), B). :- rfoldr(_, B, As, R) when As or B and R. % risky rfoldr(F, B, [], B). rfoldr(F, B, A.As, R) :- my_apply(F, A, FA), my_apply(FA, R1, R), rfoldr(F, B, As, R1). % made tail recursive to aid termination % "function" composition: F(G(A0)) % called '.' in Miranda %:- pred compose(void(B, C), void(A, B), A, C). compose(F, G, A0, A) :- my_apply(G, A0, A1), my_apply(F, A1, A). %:- pred converse(void(A, B, C), B, A, C). converse(F, A, B, C) :- my_apply(F, B, FB), % could optimize this my_apply(FB, A, C). % apply/3 explained using Horn Clauses % should be builtin! % :- my_apply(F, A, B) when F. % needed for coroutining version (?!) my_apply(app, As, app(As)). my_apply(app(As), Bs, Cs) :- app(As, Bs, Cs). % my_apply(cons, As, cons(As)). my_apply(cons(As), Bs, Cs) :- cons(As, Bs, Cs). % my_apply(foldr, A, foldr(A)). my_apply(foldr(A), B, foldr(A,B)). my_apply(foldr(A,B), C, D) :- foldr(A, B, C, D). % my_apply(compose, A, compose(A)). my_apply(compose(A), B, compose(A,B)). my_apply(compose(A,B), C, D) :- compose(A, B, C, D). % my_apply(converse, A, converse(A)). my_apply(converse(A), B, converse(A,B)). my_apply(converse(A,B), C, D) :- converse(A, B, C, D). % my_apply(my_apply, As, my_apply(As)). my_apply(my_apply(A), B, C) :- my_apply(A, B, C). % Sample goals % % nrev([1, 2, 3], A) % nrev(A, [1, 2, 3]) % rnrev([1, 2, 3], A) % rnrev(A, [1, 2, 3])

**fjh@cs.mu.oz.au
Fergus Henderson
12th November 1996**

Lee Naish writes:

*However, apply/3 can be implemented just as efficiently as call/3. For a
dumb compiler, I admit that call/3+k is faster.*

Note that the best functional language implementations, such as the Clean compiler, still use "dumb" methods. In theory, apply/3 can be implemented just as efficiently as call/3, but I think that in practice the additional degree of difficulty means that the optimization is probably not economical at the current time.

He continues:

*Is this important now (as opposed to when call/N was introduced)? I think
not.*

I don't think it is crucial, but I do think that it is something that should be considered.

He continues:

`map(P, [], []).
map(P, [X|Xs], [Y|Ys]) :- call(P, X, Y), map(P, Xs, Ys).`

You don't need specialisation to avoid choice points here, better indexing would be sufficient. For example, the Mercury implementation won't create any unnecessary choice points for that example.

He continues:

*Type checking should be no problem at all. The type of apply/3 is
(a->b) -> a -> b, which is the same as (a->b) -> (a->b),
i.e., apply/3 is a specialised version of the identity function.*

apply/3 has a pretty basic flaw if you want to use it as the *only*
higher-order primitive: you can't call a predicate with arity zero or one using
apply/3. Similarly, you can't curry all of the arguments of a predicate, or all
except one, and then call it later using apply/3.

**lee@cs.mu.oz.au
Lee Naish
13th November 1996**

Fergus Henderson writes:

*In theory, apply/3 can be implemented just as efficiently as call/3, but I
think that in practice the additional degree of difficulty means that that
optimization is probably not economical at the current time.*

I disagree. Now that higher order code in Mercury is specialised, how often is call/N actually called? My guess: extremely rarely. Code specialisation is a good thing and easy to implement (I would be surprised if the best FP implementations didn't do it) and it means that in nearly all cases the overheads of the higher order primitive - call/N or apply/3 are zero because all instances are specialised away. As an example, the higher order nrev code I posted earlier (which used apply/3), as optimised by Dan Sahlin's Mixtus:

| ?- pe(nrev(A,B)). nrev(A, B) :- nrev1(A, B). % nrev1(A,B):-nrev(A,B) nrev1(A, B) :- foldrcomposeconverseapp1(A, B).I would say that:%foldrcomposeconverseapp1(A,B) :- % foldr(compose(converse(app),converse(cons,[])),[],A,B) foldrcomposeconverseapp1([], []). foldrcomposeconverseapp1([B|D], C) :- foldrcomposeconverseapp1(D, A), app1(A, B, C). % app1(A,B,C):-app(A,[B],C) app1([], A, [A]). app1([D|A], B, [D|C]) :- app1(A, B, C).

is a non-trivial example of higher order code. The difference between apply/3 and call/N: zero. The difference between the higher order version and the hand coded first order version: two jumps (perhaps zero in Mercury?).

He continues:

*You don't need specialisation to avoid choice points here better indexing
would be sufficient. For example, the Mercury...*

I was talking about Prolog. As for the relative importance of multi-argument indexing and decent higher order facilities, in my opinion the latter is more important.

He continues:

*apply/3 has a pretty basic flaw if you want to use it as the only
higher-order primitive:*

Page 7 of my tech report discusses this point. apply/3 is sufficient for everything the functional programmers do. If you want to do more that them, something equivalent to call/2 is useful.

**fjh@cs.mu.oz.au
Fergus Henderson
13th November 1996**

Lee Naish writes:

*I disagree. Now that higher order code in Mercury is specialised, how
often is call/N actually called? My guess: extremely rarely.*

I think you misunderstood what I was saying. There are two optimizations that one can use to improve the performance of apply/3, or its equivalent, in functional languages. One is specialization, which I definitely agree is worthwhile. The other involves optimizing the representations of the closures that you can't optimize away using specialization, so that they correspond to the sort of representation that one would use for call/N. That is the optimization I think is probably not economical at the current time.

If you use cross-module optimization (which is not *always* desirable,
since it means giving up some of the flexibility of shared libraries), then
specialization will be able to entirely eliminate the run-time use of closures
for certain styles of usage, such as is common for things like 'map',
'compose', etc.

However, there are other styles of programming for which specialization can't be applied. In particular, if you put closures inside data structures - which is what you need to do if you want OOP-style dynamic binding - then specialization won't help. Hence, it is important to consider efficiency in cases where specialization can't or won't be used.