Home Page
Site Map
Login/out
Message Board
Download(c) 2005-2025 XLOG Technologies AG
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title editable="nocomment">Example 61</title>
<link rel="stylesheet" href="style.css" type="text/css">
</head>
<!-- Warranty & Liability -->
<!-- To the extent permitted by applicable law and unless explicitly -->
<!-- otherwise agreed upon, XLOG Technologies AG makes no warranties -->
<!-- regarding the provided information. XLOG Technologies AG assumes -->
<!-- no liability that any problems might be solved with the information -->
<!-- provided by XLOG Technologies AG. -->
<!-- -->
<!-- Rights & License -->
<!-- All industrial property rights regarding the information - copyright -->
<!-- and patent rights in particular - are the sole property of XLOG -->
<!-- Technologies AG. If the company was not the originator of some -->
<!-- excerpts, XLOG Technologies AG has at least obtained the right to -->
<!-- reproduce, change and translate the information. -->
<!-- -->
<!-- Reproduction is restricted to the whole unaltered document. -->
<!-- Reproduction of the information is only allowed for non-commercial -->
<!-- uses. Selling, giving away or letting of the execution of the -->
<!-- library is prohibited. The library can be distributed as part of -->
<!-- your applications and libraries for execution provided this comment -->
<!-- remains unchanged. -->
<!-- -->
<!-- Restrictions -->
<!-- Only to be distributed with programs that add significant and primary -->
<!-- functionality to the library. Not to be distributed with additional -->
<!-- software intended to replace any components of the library. -->
<!-- -->
<!-- Trademarks -->
<!-- Jekejeke is a registered trademark of XLOG Technologies AG. -->
<body>
<h1>Example 61: Higher Order</h1>
<h2>Introduction</h2>
<p>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.</p>
<h2>Combinatory Logic</h2>
<p>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:</p>
<pre>
(I x) = x
(K x y) = x
(S x y z) = (x z (y z))
</pre>
<p>The early days of Prolog were inspired by combinatory logic, and
the idea was to have predicate variables and a call <code>P(X1,..,Xn)</code>
would be transformed into <code>apply(P, X1,.., Xn)</code> together
with the idea one would add a couple of clauses for apply:</p>
<pre class="code">
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).
</pre>
<p>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:</p>
<pre class="code">
:- discontiguous apply/3.
apply(apply(C, X), Y, Z) :- apply(C, X, Y, Z).
?- apply('K', foo, X), apply(X, bar, Y).
</pre>
<p>The idea didn't win a lot of hearts and instead <code>apply(P, [X1, ..,
Xn])</code> 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:</p>
<pre class="code">
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).
</pre>
<p>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:</p>
<pre class="code">
curry(C, X, Y, Z) :- apply(C, [X, Y, Z]).
?- apply('K', [foo, X]), apply(X, [bar, Y]).
</pre>
<p>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:</p>
<pre class="code">
'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).
</pre>
<p>And last but not least 'CALL'/n can curry and uncurry itself:</p>
<pre class="code">
?- 'CALL'(k, foo, X), 'CALL'(X, bar, Y).
</pre>
<h2>List Processing</h2>
<p>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:</p>
<pre class="code">
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.
</pre>
<p>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:</p>
<pre>
maplist(_, [], []).
maplist(C, [X|L], [Y|R]) :-
call(C, X, Y),
maplist(C, L, R).
</pre>
<p>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:
<pre>
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).
</pre>
<p>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.</p>
<pre class="code">
:- ensure_loaded(library(lists)).
?- findall(X,between(1,500,X),L), time((between(1,500,_),
maplist(succ,L,_),fail;true)), fail.
</pre>
<p>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.</p>
<h2>Predicate Composition</h2>
<p>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:</p>
<center>
<img src="img001.png" width="496" height="298">
</center>
<p>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:</p>
<pre class="code">
?- findall(X,between(1,500,X),L), time((between(1,500,_),
maplist(succ,L,R),maplist(succ,R,_),fail;true)), fail.
</pre>
<p>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:</p>
<pre class="code">
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.
</pre>
<p>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:</p>
<center>
<img src="img002.png" width="496" height="298">
</center>
<h2>Conclusions</h2>
<p>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.</p>
<script type="module">
import {
notebook_async
} from "../../../../dogelog/player/canned/dogelog.mjs";
await notebook_async();
</script>
</body>
</html>