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

Groups > comp.lang.prolog > #14815

Do Prologs Dream of Canonical Sheep? (Was: The Million Dollar question of Prolog)

Show all headers | View raw

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

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