From Newsgroup: comp.lang.prolog

Hi,

Lee Naish’s idea for an infinite tree syntax:

/* Lee Naish’s idea */
naish(X, Y) :-
naish([], X, Y).

naish(S, X, Y) :- compound(X),
member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
length(S, N),
X =.. [F|L],
maplist(naish([X-'$IDX'(N)|S]), L, R),
Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
naish(X, A),
naish(Y, B),
compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly slow. Much slower
than the native compare/3 which doesn’t use a stack, but a Union
Find structure. So conceptually total order and natural order

compare/3 are easy, the hard part is making them ultra fast!

Bye
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee Naish’s idea for an infinite tree syntax:

/* Lee Naish’s idea */
naish(X, Y) :-
   naish([], X, Y).

naish(S, X, Y) :- compound(X),
   member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
   length(S, N),
   X =.. [F|L],
   maplist(naish([X-'$IDX'(N)|S]), L, R),
   Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
   naish(X, A),
   naish(Y, B),
   compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
   naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly slow. Much slower
than the native compare/3 which doesn’t use a stack, but a Union
Find structure. So conceptually total order and natural order

compare/3 are easy, the hard part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

Now this might come as a shock for this french
philosopher, who had that much problems with
Tennant's logical system called TROLL LOGIC.

Or was it core logic. Don't remember anymore:

Representation based comparison does seem to
work well on everything I’ve tested, e.g.,
“Monkey test” for transitivity and anti-symmetry
with repeat counts of 10,000,000.

Well there is balance between testing and proving
in computer science. You could say there is balance
between Inductive and Deductive science.

https://de.wikipedia.org/wiki/Induktion_(Philosophie)

You don’t need to test transitivity. You can
prove it! Mathematicians usually simply say
if < is a total order, then <′ is a total order:

Theorem on Order Homomorphism

Proof:
Given rep:R→H, then define x<′y:⟺rep(x)<rep(y).
If rep is injective, then <′ is transitive
and anti-symmetric.

Assume towards a contradiction that <′ is not
anti-symmetric. Then we would have x,y such
that x<′y∧x≠y∧¬x<′y. By definition of <′ and
injectivity of rep we would have rep(x)<rep(y)
∧rep(x)≠rep(y)∧¬rep(x)<rep(y). A contradiction
with < being anti-symmetric.

Assume towards a contradiction that <′ is
not transitive. Then we would have x,y,z such
that x<′y∧y<′z∧¬x<′z. By definition of <′ we
would have rep(x)<rep(y)∧rep(y)<rep(z)∧
¬rep(x)<rep(z). A contradiction with <
being transitive.

Q.E.D.

Bye

Mild Shock schrieb:

On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee Naish’s idea for an infinite tree syntax:

/* Lee Naish’s idea */
naish(X, Y) :-
    naish([], X, Y).

naish(S, X, Y) :- compound(X),
    member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
    length(S, N),
    X =.. [F|L],
    maplist(naish([X-'$IDX'(N)|S]), L, R),
    Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
    naish(X, A),
    naish(Y, B),
    compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
    naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly slow. Much slower
than the native compare/3 which doesn’t use a stack, but a Union
Find structure. So conceptually total order and natural order

compare/3 are easy, the hard part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

I hope @kuniaki.mukai will like this post.
Now that we are past this generic type of
compare/3, where rep/2 is some representation:

rep_compare(C, X, Y) :-
rep(X, A),
rep(Y, B),
compare(C, A, B).

We can now switch gears, an leave naish/2
behind us, and turn to Deutsch-Schorr-Waite
marking algorithm, that can give us as well
a numbering of cycle nodes:

deutsch(X, Y) :-
deutsch(X, Y, [], _).

deutsch(X, V, S, S) :- compound(X),
member(v(Z,T,Y,W), S), X == Z, !,
(var(T) -> V = Y; V = T),
W = 1.
deutsch(X, Y, S, T) :- compound(X), !,
length(S, N),
X =.. [F|L],
foldl(deutsch, L, R, [v(X,V,'$IDX'(N),W)|S], T),
Y =.. [F|R],
(var(W) -> V = Y; V = '$IDX'(N)).
deutsch(X, X, S, S).

The Schorr-Waite graph marking algorithm appeared
first in about 1968; it is also attributed to
Peter Deutsch. So I am calling the above predicate
deutsch/2 because it is a shorter name then

schorr_waite/2 or deutsch_schorr_waite/3.

Bye

Mild Shock schrieb:

Hi,

Now this might come as a shock for this french
philosopher, who had that much problems with
Tennant's logical system called TROLL LOGIC.

Or was it core logic. Don't remember anymore:

Representation based comparison does seem to
work well on everything I’ve tested, e.g.,
“Monkey test” for transitivity and anti-symmetry
with repeat counts of 10,000,000.

Well there is balance between testing and proving
in computer science. You could say there is balance
between Inductive and Deductive science.

https://de.wikipedia.org/wiki/Induktion_(Philosophie)

You don’t need to test transitivity. You can
prove it! Mathematicians usually simply say
if < is a total order, then <′ is a total order:

    Theorem on Order Homomorphism

    Proof:
    Given rep:R→H, then define x<′y:⟺rep(x)<rep(y).
    If rep is injective, then <′ is transitive
    and anti-symmetric.

    Assume towards a contradiction that <′ is not
    anti-symmetric. Then we would have x,y such
    that x<′y∧x≠y∧¬x<′y. By definition of <′ and
    injectivity of rep we would have rep(x)<rep(y)
    ∧rep(x)≠rep(y)∧¬rep(x)<rep(y). A contradiction
    with < being anti-symmetric.

    Assume towards a contradiction that <′ is
    not transitive. Then we would have x,y,z such
    that x<′y∧y<′z∧¬x<′z. By definition of <′ we
    would have rep(x)<rep(y)∧rep(y)<rep(z)∧
    ¬rep(x)<rep(z). A contradiction with <
    being transitive.

    Q.E.D.

Bye

Mild Shock schrieb:

On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee Naish’s idea for an infinite tree syntax:

/* Lee Naish’s idea */
naish(X, Y) :-
    naish([], X, Y).

naish(S, X, Y) :- compound(X),
    member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
    length(S, N),
    X =.. [F|L],
    maplist(naish([X-'$IDX'(N)|S]), L, R),
    Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
    naish(X, A),
    naish(Y, B),
    compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
    naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly slow. Much slower
than the native compare/3 which doesn’t use a stack, but a Union
Find structure. So conceptually total order and natural order

compare/3 are easy, the hard part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


Hi,

What can it do? Well it detects sharing and
is thus more resilient to examples such as hydra/2.

Naish has no sharing detection:

?- X = f(g(h(Z))), Y = k(X,X), naish(Y, T).
T = k(f(g(h(Z))), f(g(h(Z)))).

?- X = f(g(h(X))), Y = k(X,X), naish(Y, T).
T = k(f(g(h('$IDX'(1)))), f(g(h('$IDX'(1))))).

Deutsch has sharing detection:

?- X = f(g(h(Z))), Y = k(X,X), deutsch(Y, T).
T = k(f(g(h(Z))), f(g(h(Z)))).

?- X = f(g(h(X))), Y = k(X,X), deutsch(Y, T).
T = k(f(g(h('$IDX'(1)))), '$IDX'(1)).

You can also inspect the results with
'$factorize_term'/3, to see sharing that is
not shown in the top-level. This gives yet
another compare/3 which is a total order

and which is conservative and can deal
with sharing, when combined with the
SWI-Prolog compare/3 in a rep_compare/3.
But still expensive, not for pratical

use, only for educational use.

Bye

Mild Shock schrieb:

Hi,

I hope @kuniaki.mukai will like this post.
Now that we are past this generic type of
compare/3, where rep/2 is some representation:

rep_compare(C, X, Y) :-
    rep(X, A),
    rep(Y, B),
    compare(C, A, B).

We can now switch gears, an leave naish/2
behind us, and turn to Deutsch-Schorr-Waite
marking algorithm, that can give us as well
a numbering of cycle nodes:

deutsch(X, Y) :-
   deutsch(X, Y, [], _).

deutsch(X, V, S, S) :- compound(X),
   member(v(Z,T,Y,W), S), X == Z, !,
   (var(T) -> V = Y; V = T),
   W = 1.
deutsch(X, Y, S, T) :- compound(X), !,
   length(S, N),
   X =.. [F|L],
   foldl(deutsch, L, R, [v(X,V,'$IDX'(N),W)|S], T),
   Y =.. [F|R],
   (var(W) -> V = Y; V = '$IDX'(N)).
deutsch(X, X, S, S).

The Schorr-Waite graph marking algorithm appeared
first in about 1968; it is also attributed to
Peter Deutsch. So I am calling the above predicate
deutsch/2 because it is a shorter name then

schorr_waite/2 or deutsch_schorr_waite/3.

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

@jp-diegidio repeatedly put forward a Prolog
system vision, that does Prolog term minimization
“intrinsically”. Such novel design ideas, just

like E-graphs by Philip Zucker, this CanProlog
by Julio Di Egidio, is probably best discussed in
a new thread. And here you have it, a new thread!

BTW, I think there is some overlap of E-graphs and
CanProlog. For example was researching whether
Hash Consing is possible for cyclic terms. There

is indeed an old proposal by Andre W. Appel from
Princton University, burried in this paper:

Hash-consing Garbage Collection
Appel, A.W. - 1993
https://www.cs.princeton.edu/~appel/papers/hashgc.pdf

The idea is simple just have some “conductor”
elements, where hash consing stops. And loops can go
through these “conductor” elements.

Bye

Mild Shock schrieb:

Hi,

Lee Naish’s idea for an infinite tree syntax:

/* Lee Naish’s idea */
naish(X, Y) :-
   naish([], X, Y).

naish(S, X, Y) :- compound(X),
   member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
   length(S, N),
   X =.. [F|L],
   maplist(naish([X-'$IDX'(N)|S]), L, R),
   Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
   naish(X, A),
   naish(Y, B),
   compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
   naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly slow. Much slower
than the native compare/3 which doesn’t use a stack, but a Union
Find structure. So conceptually total order and natural order

compare/3 are easy, the hard part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

This is applicable to certain Prolog systems since
in Prolog without change_arg/3 loops can ideeded only
go through Prolog variables, making the Prolog

variables the conductor elements. It won’t work so
easily when a “mutator” like change_arg/3 is available,
that bypasses Prolog variables. And also if we don’t

have change_arg/3 the hash consing might be less
effective if we consider all Prolog variables. How
to make a smart and efficient selection of the

right “conductor” elements?

Bye

BTW: There is also some overlap to WebPL and their
recent Heap/Stack architecture and some insuination
about variable shunting. WebPL seems to be still active,

currently trying Scryer chars.

Mild Shock schrieb:

Hi,

@jp-diegidio repeatedly put forward a Prolog
system vision, that does Prolog term minimization
“intrinsically”. Such novel design ideas, just

like E-graphs by Philip Zucker, this CanProlog
by Julio Di Egidio, is probably best discussed in
a new thread. And here you have it, a new thread!

BTW, I think there is some overlap of E-graphs and
CanProlog. For example was researching whether
Hash Consing is possible for cyclic terms. There

is indeed an old proposal by Andre W. Appel from
Princton University, burried in this paper:

Hash-consing Garbage Collection
Appel, A.W. - 1993
https://www.cs.princeton.edu/~appel/papers/hashgc.pdf

The idea is simple just have some “conductor”
elements, where hash consing stops. And loops can go
through these “conductor” elements.

Bye

Mild Shock schrieb:

Hi,

Lee Naish’s idea for an infinite tree syntax:

/* Lee Naish’s idea */
naish(X, Y) :-
    naish([], X, Y).

naish(S, X, Y) :- compound(X),
    member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
    length(S, N),
    X =.. [F|L],
    maplist(naish([X-'$IDX'(N)|S]), L, R),
    Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
    naish(X, A),
    naish(Y, B),
    compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
    naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly slow. Much slower
than the native compare/3 which doesn’t use a stack, but a Union
Find structure. So conceptually total order and natural order

compare/3 are easy, the hard part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2