|
|
|
|
|
|
|
|
call/NAppeared 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:
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:
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?
In the same way, if the following is given:
fails in Lisp. Here's the message:
What should we do to fix it? Write:
Here's what we want. We want to take:
will do fine. Here's a suitable method:
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:
Points where I think we would agree, but I'm not sure:
Points of disagreement:
Points left completely open by the paper and this article:
Richard A. O'Keefe writes:
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:
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:
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:
He continues:
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:
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:
In general you need N of these.
He continues:
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:
Agreed!
He continues:
There are both as powerful as Horn clauses; it's an issue of how nice the
programs are.
He continues:
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:
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:
I agree it's one good way to go, but I also think there is a better way.
He continues:
I still believe this.
He continues:
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:
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.
Lee Naish writes:
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:
I don't think it is crucial, but I do think that it is something that should be
considered.
He continues:
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:
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.
Fergus Henderson writes:
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:
%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:
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:
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.
Lee Naish writes:
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.
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.
call(P(X1,...,Xm), Y1,...,Yn) :- P(X1,...,Xm, Y1,...,Yn)
That's fine, but it requires all the arguments to be present before you
can use it. This is no good; higher-order languages like Haskell let you apply
functions to some of their arguments via currying, and call/N doesn't
let you do that, so you should use apply/3 which does.
ex_12(Xs) :-
map(plus, [2,3,4], Xs).
This fails in type checked Prolog because
NOT(plus : void(integer,T)).
(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:
(map-1 #'plus-1 '(2 3 4))
Error: PLUS-1 [or a callee] requires two arguments, but only one was
supplied.
(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".
<some term>[ plus ]
X
and obtain a partially applied closure, for which:
call(plus, X)
:- 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.
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.
lee@cs.mu.oz.au
Lee Naish
12th November 1996
(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...
This could not be done in a system where plus/3 and plus/2 were
completely unrelated predicates
(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.)
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.
so we need
:- pred compose_2(void(U, V, W), void(X, U), X, V, W)
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".
:- pred curry(void(X, Y, Z), X, void(Y, Z)).
curry(P, X, call(P, X)).
What apply/3 can do, so can call/N, with a suitable small set of
combinators.
Points of long standing agreement:
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...
call/N is not the way to go (it's one good way in my view);
apply/3 is better than call/N;
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?
% 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
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.
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.
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.
lee@cs.mu.oz.au
Lee Naish
13th November 1996
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.
| ?- 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:
foldr(compose(converse(app),converse(cons,[])),[],A,B)
You don't need specialisation to avoid choice points here better indexing
would be sufficient. For example, the Mercury...
apply/3 has a pretty basic flaw if you want to use it as the only
higher-order primitive:
fjh@cs.mu.oz.au
Fergus Henderson
13th November 1996
I disagree. Now that higher order code in Mercury is specialised, how
often is call/N actually called? My guess: extremely rarely.