The Million Dollar question of Prolog

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	The Million Dollar question of Prolog
Date	2025-08-23 14:54 +0200
Message-ID	<108cdlo$fqbc$1@solani.org> (permalink)

Show all headers | View raw

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