Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14804 > unrolled thread

The Million Dollar question of Prolog

Back to article view | Back to comp.lang.prolog

Contents

  The Million Dollar question of Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-23 14:54 +0200
    AGI will relieve the community (Was: The Million Dollar question of Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-25 15:11 +0200
      Reflect on Sience not Frog Legs (Was: AGI will relieve the community) Mild Shock <janburse@fastmail.fm> - 2025-08-25 22:55 +0200
        Switching Gears: From Lee Naish to Peter Deutsch (Was: Reflect on Sience not Frog Legs) Mild Shock <janburse@fastmail.fm> - 2025-08-26 11:24 +0200
          Not for pratical use, only for educational use (Re: Switching Gears: From Lee Naish to Peter Deutsch) Mild Shock <janburse@fastmail.fm> - 2025-08-26 11:32 +0200
    Do Prologs Dream of Canonical Sheep? (Was: The Million Dollar question of Prolog) Mild Shock <janburse@fastmail.fm> - 2025-09-05 12:10 +0100
      Electing "conductor" Prolog variables (Was: Do Prologs Dream of Canonical Sheep?) Mild Shock <janburse@fastmail.fm> - 2025-09-05 12:13 +0100

#14804 — The Million Dollar question of 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

[toc] | [next] | [standalone]

#14806 — AGI will relieve the community (Was: The Million Dollar question of 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

[toc] | [prev] | [next] | [standalone]

#14807 — Reflect on Sience not Frog Legs (Was: AGI will relieve the community)

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
> 

[toc] | [prev] | [next] | [standalone]

#14808 — Switching Gears: From Lee Naish to Peter Deutsch (Was: Reflect on Sience not Frog Legs)

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
>>
> 
> 
> 

[toc] | [prev] | [next] | [standalone]

#14809 — Not for pratical use, only for educational use (Re: Switching Gears: From Lee Naish to Peter Deutsch)

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

[toc] | [prev] | [next] | [standalone]

#14815 — Do Prologs Dream of Canonical Sheep? (Was: The Million Dollar question of 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

[toc] | [prev] | [next] | [standalone]

#14816 — Electing "conductor" Prolog variables (Was: Do Prologs Dream of Canonical Sheep?)

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
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.prolog

csiph-web