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

Groups > comp.lang.prolog > #14809

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

Show all headers | View raw

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

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web