I am just sifting through my old formerly
Jekejeke Prolog code, and find this dynamic
condition for `unify_with_occurs_check/2`
speed-up. Interesting application of so called
**weighted reference counting**. Namely this
program code one-liner in hasVar():
public boolean hasVar(Object m, Display d, Display d2) {
[...]
if ((refs & MASK_VAR_FRSH) == 0 && d != d2)
return false;
[...]
It basically checks the reference count. If the
variable V is not referenced, it can also not appear
in a term t, so checking V ∈ t is not necessarely.
Why do I mention that, because above condition is
"dynamic". Means its more situation specific.
Why the d!=d2 and the MASK_VAR_FRSH, well because
variables appearing in a clause, do not have really
a reference count zero, as long as the clause is used.
Since clauses are usually initially acyclic, and
the clause variables sooner or later act as conductors,
to the head arguments or goal results, so
that d!=d2 happens quite quickly, and there
is not much loss by the additional conditions.
Mild Shock schrieb:
Hi,
Take these definitions:
test1(X) :- X = f(g(X,_B),_A).
test2(X) :- Y = g(f(Y,A),_B), X = f(Y,A).
Then you get:
/* Scryer Prolog 0.9.4-417 */
?- test1(X), numbervars(X,0,_).
X = f(g(X,'$VAR'(0)),'$VAR'(1)).
?- test2(X), numbervars(X,0,_).
X = f(g(f('$VAR'(0),'$VAR'(1)),g(f(g('$VAR'(1),'$VAR'(0)), f(g(f('$VAR'(0),'$VAR'(1)),g(f(g('$VAR'(1),'$VAR'(0)), f(g(f('$VAR'(0),'$VAR'(1)),g(f(g('$VAR'(1),'$VAR'(0)), f(g(f('$VAR'(0),'$VAR'(1)),g(f(g('$VAR'(1),'$VAR'(0)), f(g(f('$VAR'(...),'$VAR'(...)),g(f(g(...),'$VAR'(...)), '$VAR'(...))),'$VAR'(0))),'$VAR'(1))),'$VAR'(0))),'$VAR'(1))), '$VAR'(0))),'$VAR'(1))),'$VAR'(0))),'$VAR'(1))),'$VAR'(0)).
What the heck is the '$VAR'(0) after the f(g(f( ?
Bye
Mild Shock schrieb:
Hi,
Having fun with Bisimulation, and a new test
suite of nasty circular pairs. But how store
circular pairs, if clauses do not support
circular terms. Well chop it up into equations,
I create 1000 such equation pairs:
test([A = c(A, B), C = c(A, D), E = n, _ = c(F, B),
F = c(C, C), G = c(G, D), D = c(E, C), B = n],
[H = c(H, I), J = c(K, I), L = c(L, I), I = c(M, N),
O = c(K, J), N = n, K = c(K, J), M = c(K, O)]).
Etc..
The pairs are nasty because the usual compare_with_stack/2
chokes on them. Here some results:
/* SWI-Prolog 9.3.26 */
?- time((between(1,30,_), part, fail; true)).
% 540,118 inferences, 0.047 CPU in 0.041 seconds (115% CPU, 11522517
Lips)
true.
/* Trealla Prolog 2.78.40 */
?- time((between(1,30,_), part, fail; true)).
% Time elapsed 0.113s, 1143903 Inferences, 10.157 MLips
true.
/* Scryer Prolog 0.9.4-417 */
?- time((between(1,30,_), part, fail; true)).
% CPU time: 0.226s, 1_117_809 inferences
true.
/* Dogelog Player 1.3.5 */
?- time((between(1,30,_), part2, fail; true)).
% Zeit 309 ms, GC 0 ms, Lips 8693718, Uhr 25.07.2025 13:47
true.
The amazing thing is, I compared a 100% Prolog
implementation, so there is a lot of head room
for improvement:
part2 :-
bitest(X,Y), X ~~ Y, fail; true.
The operator (~~)/2 is part of library(math),
and has been implemented with same_term/2 so far.
Bye
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)