Dogelog Player is a Prolog system written in 100% Prolog for the target platforms JavaScript, Python and Java. We recently introduced the display of cyclic terms in the top-level.
As a next iteration we turned all built-ins upside down, gave it either a visitor pattern or union find, so that they can deal with cyclic terms. The final step is then to untie Landin's Knot.
Landin's Knot
To motivate what we did, we will first give a brief introduction to Landin's Knot. And how it could be modelled in Prolog. The modelling will naturally lead to cyclic term. Landin's Knot refers to the production of a closure, with a placeholder.
The placeholder is later updated by the closure itself, leading to a self referential closure. In an imperative language like JavaScript this is readily done, by first defining f, which internally refers to r. We will then update r by the value of f. Calling f(0) loops:
let r;
let f = (n) => r(n);
r = f;
f(0);
%%% hangs or stack overflows
In Prolog we can replicate the JavaScript example by simulating λ abstraction by a ternary predicate lambda/3, and then doing everything in the top-level. We see that the unification R = F gives a Prolog closure that is a rational tree, and we see that goal call(F,0) indeed loops:
lambda(X,G,Y) :- copy_term(X-G, Y-H), H.
? = lambda(X,call(R,X)), R = F.
F = R, R = lambda(X, call(R, X)).
?- F = lambda(X,call(R,X)), R = F, call(F,0).
%%% hangs or stack overflows
Untying Knots
Some built-ins resist fixing for cyclic terms in a recursive manner. The way to go is to untie knots before further proceeding. We developed an according routine already internally for the top-level. We decided to make it a first class citizen of the library(lists). The 100% Prolog implementation reads as follows:
term_decompose(X, Y, L) :-
sys_term_decompose(X, Y, []-L, _-[]).
sys_term_decompose(X, Z, L-E, L-E) :- compound(X),
member(v(Y,W,Z),L), same_term(X, Y), !,
W = 1.
sys_term_decompose(X, Y, L-E, R-K) :- compound(X), !,
X =.. [F|P],
foldl(sys_term_decompose, P, Q, [v(X,W,Y)|L]-E, R-J),
(var(W) ->
Y =.. [F|Q], J = K;
H =.. [F|Q], J = [Y=H|K]).
sys_term_decompose(X, X, L, L).
Similar predicates are found in other Prolog systems. What is common among the implementations, is that the predicate takes an acyclic or cyclic term X, and produces a skeleton Y and a substution list L. The main benefit is then, that the skeleton and the substituted terms are all acyclic terms.
SWI-Prolog offers $factorize_term'/3, which reports all sharing:
/* SWI-Prolog 9.3.28 */
?- X = f(f(f(X))), Y = g(A), Z = h(X,Y,Y), '$factorize_term'(Z, T, L).
T = h(X, Y, Y),
L = [X=f(f(f(X))), Y=g(A)].
Where as we only reports loops and breaks cycles as well:
/* Dogelog Player 1.3.6 */
?- X = f(f(f(X))), Y = g(A), Z = h(X,Y,Y), term_decompose(Z, T, L).
T = h(_A, g(A), g(A)),
L = [_A = f(f(f(_A)))].
Structural Comparison
The fresh library(lists) member term_decompose/2 has found applications in library(sequence) and library(aggregate). We make use of the fact that term_decompose/3 returns an empty substitution list for an acyclic argument, so that we can retain the same behaviour as before.
Otherwise we exercise the same idea as is already found in the SWI-Prolog implementation of distinct/3. The recent implementation makes use of a predicate trieable/2. In our case we will just throw in term_decompose/3. The distinct/3 predicate without term_decompose/2 reads as follows:
distinct(Goal) :-
term_variables(Goal, Key),
hash_new(Hash),
Goal,
sys_distinct(Hash, Key).
To be able to handle cyclic terms we use:
distinct(Goal) :-
term_variables(Goal, Key),
hash_new(Hash),
Goal,
term_decompose(Key, Skel, Subst),
sys_distinct(Hash, [Skel|Subst]).
The result is a structural compare between (==)/2 and same_term/2. The term_hash/2 doesn't need to be able to handle cycles, since what the hash table receives is an acyclic skeleton and acyclic substituted terms. Similar there is no pressure on (==)/2:
p(X) :- X = f(f(f(X))).
p(X) :- X = f(f(X)).
p(X) :- X = f(f(f(X))).
?- distinct(p(X)).
X = f(f(f(X)));
X = f(f(X));
fail.
?- aggregate(count,p(X),C).
X = f(f(X)), C = 1;
X = f(f(f(X))), C = 2.
Canonical Comparison
There might be applications, where structural comparison is too weak. We decided to only offer structural comparison inside library(sequence) or library(aggregate). As an alternative option the end-user can manifcature canonical terms via a further predicate term_canonical/2 inside library(lists):
term_canonical(X, Y) :-
sys_term_canonical(X, Y, [], _).
sys_term_canonical(X, Z, L, L) :- compound(X),
member(Y-Z, L), X == Y, !.
sys_term_canonical(X, Y, L, R) :- compound(X), !,
X =.. [F|P],
foldl(sys_term_canonical, P, Q, [X-Y|L], R),
Y =.. [F|Q].
sys_term_canonical(X, X, L, L).
The structural comparison for canonical terms, then amounts to a canonical comparison. The order is again conservative since acyclic terms are not changed by forming canonical terms and structural comparison sees acyclic terms like (@<)/2. For cyclic terms we can demonstrate it as follows:
q(Y) :- p(X), term_canonical(X, Y).
?- distinct(q(X)).
X = f(X);
fail.
?- aggregate(count,q(X),C).
X = f(X), C = 3.
What we wish for the future are two things. Give term_decompose/3 a native implementation. We could profit from the many other predicates that have a visitor pattern implementation. And find a faster algorithm for term_canonical/2, which then might need some native support. Native support could come in noval data structures tightly integrated.
Conclusions
The new predicates term_decompose/2 and term_canonical/2 have found applications in library(sequence) and library(aggregate). The result is primarily a structural compare among cyclic terms, which the end-user can lift to a canonical compare.