From Newsgroup: comp.lang.prolog

Hi,

So VIP0909 will contain all things related to
Cyclic terms. Especially gather what is known
concerning space and time complexity.

So that non-functional requirements are
documented. One could make non-functional
requiremets even mandatory. This is for

example found in JavaScript when they write:

"The specification requires maps to be
implemented "that, on average, provide access
times that are sublinear on the number of
elements in the collection". Therefore, it
could be represented internally as a hash
table (with O(1) lookup), a search tree
(with O(log(N)) lookup), or any other data
structure, as long as the complexity
is better than O(N)." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

This would catapult standards from "correctness"
pamphlets into the new age of "performance"
pamphlets. My research shows that some

unary algorithms in conncetion with cyclic
terms and some binary algorithms in connection
with cyclic terms have obvious linear or

quasi linear bounds.

Bye


Mild Shock schrieb:

Hi,

Functional requirement:

?- Y = g(_,_), X = f(Y,C,D,Y), term_singletons(X, L),
   L == [C,D].

?- Y = g(A,X,B), X = f(Y,C,D), term_singletons(X, L),
   L == [A,B,C,D].

Non-Functional requirement:

?- member(N,[5,10,15]), time(singletons(N)), fail; true.
% Zeit 1 ms, GC 0 ms, Lips 4046000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1352000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1355333, Uhr 11.08.2025 01:36
true.

Can your Prolog system do that?

P.S.: Benchmark was:

singletons(N) :-
   hydra2(N,Y),
   between(1,1000,_), term_singletons(Y,_), fail; true.

hydra2(0, _) :- !.
hydra2(N, s(X,X)) :-
   M is N-1,
   hydra2(M, X).

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

It,

It turns out that Jaffar's Unification is ultra fast,
we even beat Scryer Prolog with our JavaScript target.
Nevertheless we rejected it, since it intrudes frozen

Prolog terms. We then speculated that we need a hybrid
algorithm, that combines intrusion and non-intrusion,
possibly by braching into non-intrusion, from intrusion.

But a possible solution is simpler, we could change
Jaffar's Unification, exemplified by union_find():

public static Compound union_find2(Compound obj) {
while (is_compound(obj.functor))
obj = (Compound)obj.functor;
return obj;
}

Into this here making it hybrid, union_add() and
log_add() would receive similar changes:

public static Compound union_find2(Compound obj) {
if (is_frozen(obj)
return obj;
while (is_compound(obj.functor))
obj = (Compound)obj.functor;
return obj;
}

Let's see how it turns out...

Bye

Mild Shock schrieb:

Hi,

So VIP0909 will contain all things related to
Cyclic terms. Especially gather what is known
concerning space and time complexity.

So that non-functional requirements are
documented. One could make non-functional
requiremets even mandatory. This is for

example found in JavaScript when they write:

"The specification requires maps to be
implemented "that, on average, provide access
times that are sublinear on the number of
elements in the collection". Therefore, it
could be represented internally as a hash
table (with O(1) lookup), a search tree
(with O(log(N)) lookup), or any other data
structure, as long as the complexity
is better than O(N)." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

This would catapult standards from "correctness"
pamphlets into the new age of "performance"
pamphlets. My research shows that some

unary algorithms in conncetion with cyclic
terms and some binary algorithms in connection
with cyclic terms have obvious linear or

quasi linear bounds.

Bye

Mild Shock schrieb:

Hi,

Functional requirement:

?- Y = g(_,_), X = f(Y,C,D,Y), term_singletons(X, L),
    L == [C,D].

?- Y = g(A,X,B), X = f(Y,C,D), term_singletons(X, L),
    L == [A,B,C,D].

Non-Functional requirement:

?- member(N,[5,10,15]), time(singletons(N)), fail; true.
% Zeit 1 ms, GC 0 ms, Lips 4046000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1352000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1355333, Uhr 11.08.2025 01:36
true.

Can your Prolog system do that?

P.S.: Benchmark was:

singletons(N) :-
    hydra2(N,Y),
    between(1,1000,_), term_singletons(Y,_), fail; true.

hydra2(0, _) :- !.
hydra2(N, s(X,X)) :-
    M is N-1,
    hydra2(M, X).

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

The Union Find modification proposed below,
not only assumes that we don't need full
Union Find for frozen terms, the same terms

we use in program sharing, because they currently
don't have cycles. What we should highlight here,
they also don't have sharing. So both motivations

for Union Find fall short, we will not find
frozen Hydras as program sharing. At least currently
there is this invariant. It might change though,

but it is worth exploring it while it stands.
Just imaging a program shared long list:

data([0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,5,6,7,8,9]).

A Union Find will create a Union Find linkage,
of the size N = 30 times, if we for example issue
the following Prolog query:

?- length(X,30), data(X).

Then on the other hand the cheap hybrid trick will
not create any Union Find linkage, and mostlikely
allow to regain some speed.

Bye

Mild Shock schrieb:

It,

It turns out that Jaffar's Unification is ultra fast,
we even beat Scryer Prolog with our JavaScript target.
Nevertheless we rejected it, since it intrudes frozen

Prolog terms. We then speculated that we need a hybrid
algorithm, that combines intrusion and non-intrusion,
possibly by braching into non-intrusion, from intrusion.

But a possible solution is simpler, we could change
Jaffar's Unification, exemplified by union_find():

    public static Compound union_find2(Compound obj) {
        while (is_compound(obj.functor))
            obj = (Compound)obj.functor;
        return obj;
    }

Into this here making it hybrid, union_add() and
log_add() would receive similar changes:

    public static Compound union_find2(Compound obj) {
         if (is_frozen(obj)
             return obj;
        while (is_compound(obj.functor))
            obj = (Compound)obj.functor;
        return obj;
    }

Let's see how it turns out...

Bye

Mild Shock schrieb:

Hi,

So VIP0909 will contain all things related to
Cyclic terms. Especially gather what is known
concerning space and time complexity.

So that non-functional requirements are
documented. One could make non-functional
requiremets even mandatory. This is for

example found in JavaScript when they write:

"The specification requires maps to be
implemented "that, on average, provide access
times that are sublinear on the number of
elements in the collection". Therefore, it
could be represented internally as a hash
table (with O(1) lookup), a search tree
(with O(log(N)) lookup), or any other data
structure, as long as the complexity
is better than O(N)."
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map


This would catapult standards from "correctness"
pamphlets into the new age of "performance"
pamphlets. My research shows that some

unary algorithms in conncetion with cyclic
terms and some binary algorithms in connection
with cyclic terms have obvious linear or

quasi linear bounds.

Bye


Mild Shock schrieb:

Hi,

Functional requirement:

?- Y = g(_,_), X = f(Y,C,D,Y), term_singletons(X, L),
    L == [C,D].

?- Y = g(A,X,B), X = f(Y,C,D), term_singletons(X, L),
    L == [A,B,C,D].

Non-Functional requirement:

?- member(N,[5,10,15]), time(singletons(N)), fail; true.
% Zeit 1 ms, GC 0 ms, Lips 4046000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1352000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1355333, Uhr 11.08.2025 01:36
true.

Can your Prolog system do that?

P.S.: Benchmark was:

singletons(N) :-
    hydra2(N,Y),
    between(1,1000,_), term_singletons(Y,_), fail; true.

hydra2(0, _) :- !.
hydra2(N, s(X,X)) :-
    M is N-1,
    hydra2(M, X).

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2