Higher Order in Dogelog Player

Last updated at 2025-03-13Posted at 2025-03-13

Introduction

Tired of pounding out the same old boring boilerplate code over and over and over again. I'll show you how to eliminate the boilerplate by using higher-order programming: functions that take other functions as arguments; or in Prolog, predicates that take other predicates as arguments.

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.

Combinatory Logic

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.

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.

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).
X = Z.

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

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

List Processing

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).

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_callable_cacheable(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_callable_cacheable/2. It will create a shallow copy of the given closure and create a Prolog compound with a predicate table lookup cache.

Predicate Composition

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. We then compared it to a version using predicate composition.

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

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:

Conclusions

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.