Somehow we shied away from implementing call/n for our Prolog system. We thought our Prolog system has only monomorphic predicate lookup caches and therefore we kept a distance. This changed when we had the idea to dynamically add a cache for the duration of a higher order loop.

A well known higher order calculus is found in combinatory logic. When the combinators obey some type system, we quickly see that they are not simply functions but rather functionals, that they can take other functions as their arguments or give as a result. Some famous combinators are:

    (I x) = x
    (K x y) = x
    (S x y z) = (x z (y z))

The early days of Prolog were inspired by combinatory logic, and the idea was to have predicate variables and a call P(X1,..,Xn) would be transformed into apply(P, X1,.., Xn) together with the idea one would add a couple of clauses for apply:

apply('K', X, apply('K', X)).  % currying
apply('K', X, _, X).
apply('S', X, Y, Z, T) :- apply(Y, Z, H), apply(X, Z, H, T).

?- apply('S', 'K', 'K', X, Z).

Although we have defined rule that suspends (K x), only this way we could make the (S K K) example work. We would still need an extra rule to uncurry the currying. Only then can we really use the combinator 'K' curried:

:- discontiguous apply/3.

apply(apply(C, X), Y, Z) :- apply(C, X, Y, Z).

?- apply('K', foo, X), apply(X, bar, Y).

The idea didn't win a lot of hearts and instead apply(P, [X1, .., Xn]) made it into some Prolog systems. Prolog systems had already a little higher order device. Through homoiconicity it was permitted that arbitrary Prolog terms were interpreted as Prolog goals:

apply(P, L) :- P =.. [F|R],
   append(R, L, H),
   Q =.. [F|H], Q.

'K'(X, curry('K', X)).  % currying
'K'(X, _, X).
'S'(X, Y, Z, T) :- apply(Y, [Z, H]), apply(X, [Z, H, T]).

?- 'S'('K', 'K', X, Z).

Unfortuntely we would still need an extra rule to uncurry the currying. The benefit of definitions of the combinators 'K' and 'S' in their own predicates gets dimished in that we need to have again some extra rules:

curry(C, X, Y, Z) :- apply(C, [X, Y, Z]).

?- apply('K', [foo, X]), apply(X, [bar, Y]).

There were voices that propagated the best of the two worlds. Ultimately a predicate call/n made it into the ISO core standard. For demonstration we define it as 'CALL'/n here. It now shares the property with apply/2 that we can give the combinators defintions in their own predicates:

'CALL'(P, X) :- P =.. [F|R],
   append(R, [X], H),
   Q =.. [F|H], Q.
'CALL'(P, X, Y) :- P =.. [F|R],
   append(R, [X, Y], H),
   Q =.. [F|H], Q.
'CALL'(P, X, Y, Z) :- P =.. [F|R],
   append(R, [X, Y, Z], H),
   Q =.. [F|H], Q.

k(X, 'CALL'(k, X)).  % currying
k(X, _, X).
s(X, Y, Z, T) :- 'CALL'(Y, Z, H), 'CALL'(X, Z, H, T).

?- s(k, k, X, Z).

And last but not least 'CALL'/n can curry and uncurry itself:

?- 'CALL'(k, foo, X), 'CALL'(X, bar, Y).

We recently got friend with the idea of providing call/n for our Prolog system. Our change of mind came in two steps. First we implemented call/n in a straight forward fashion as a new native built-in provided by our library(compat). We were looking into list predicates such as:

succ(X, Y) :- Y is X+1.

succ_list([], []).
succ_list([X|L], [Y|R]) :-
   succ(X, Y),
   succ_list(L, R).

?- findall(X,between(1,500,X),L), time((between(1,500,_),
   succ_list(L,_),fail;true)), fail.

The above can be realized with maplist/3 defined as follows. If call/n is implemented as a native built-in, it will be less subject to the overhead of calling append/3 and (=..)/2, since the native built-in can directly operate on native Prolog compounds:

maplist(_, [], []).
maplist(C, [X|L], [Y|R]) :-
   call(C, X, Y),
   maplist(C, L, R).

Still we had two reservations regarding the above implementation. Our Prolog system has only first argument indexing, so to profit from it, we would need to reorder the arguments. Second call/n would be called repeatedly with the same closure C resulting in a predicate table lookup:

maplist(C, L, R) :-
   ir_call_site(C, D),
   sys_maplist(L, D, R).

sys_maplist([], _, []).
sys_maplist([X|L], C, [Y|R]) :-
   call(C, X, Y),
   sys_maplist(L, C, R).

To make the predicate lookup more efficient we introduced the new built-in ir_call_site/2. It will create a shallow copy of the given closure and create a Prolog compound with a predicate table lookup cache.

:- ensure_loaded(library(lists)).

?- findall(X,between(1,500,X),L), time((between(1,500,_),
   maplist(succ,L,_),fail;true)), fail.

We also experimented in creating the cachable callable during compile time, but this has a blind spot, since not all maplist/n arguments are immediate. Also we didn't want to introduce meta_predicate/1 directive, which would give a compilation hint.

We did some Prolog system comparison. We found that SWI-Prolog performs the list processing fastest. Among the newer Prolog systems Trealla Prolog is lacking a little bit behind, whereas Scryer Prolog is an itch faster than our Prolog system:

Knowing that the callable cache approach is limited. we made some further testing. As a baseline we checked on calling maplist/3 twice so as to apply succ/2 twice:

?- findall(X,between(1,500,X),L), time((between(1,500,_),
   maplist(succ,L,R),maplist(succ,R,_),fail;true)), fail.

We then compared it to a version using predicate composition. In this version the intermediate list R is not anymore computed. But some pressure is put on the predicate compose/4:

compose(C2, C1, X, Y) :-
   call(C1, X, H),
   call(C2, H, Y).

?- findall(X,between(1,500,X),L), time((between(1,500,_),
   maplist(compose(succ,succ),L,_),fail;true)), fail.

The results show a similar ranking again. Except that Dogelog Player seems the only Prolog system where the compose/3 based solution runs faster on the Java target. Need not be an indicator that call/n is fast, could also mean that our lists are slow:

We could provide a new builtin call/n for our Prolog system. Testing some list processing from different angles we conclude our performance is middle field, comparable to Scryer Prolog. This makes it feasible to bring call/n and predicates such as maplist/n to the upcoming release of Dogelog Player.