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

Groups > comp.lang.prolog > #14832

Wikipedia is clueless about cyclic terms (Was: Cyclic terms are missing from "Fifty Years of Prolog and Beyond (TPLP 2022)")

Show all headers | View raw

Hi,

They write nonsense like:

> Modern implementations, based on Colmerauer's Prolog II, [4] [5] [6] 
[7] use rational tree unification to avoid looping.
However it is difficult to keep the complexity time
linear in the presence of cyclic terms. Examples
where Colmerauers algorithm becomes quadratic [8] can
be readily constructed, but refinement proposals exist.
https://en.wikipedia.org/wiki/Occurs_check

Nobody uses Colmerauers algorithm , in the sense of equation
saturation. I didn't find a single Prolog system that would use
it. Its not clear what Colmerauers algorithm should be? The
paper by Alberto Martelli and Gianfranco Rossi

does also not reflect modern implementations. Modern
implementations are simply variantes of Hopecroft & Karp (1971).
Which has linear complexity of (==)/2 cases. Non (==)/2
cases of (=)/2 can anyway get exponential, right? (**)

At lest checking modern implementation I find nowhere,
Martelli & Rossi used. Its all Hopecroft & Karp (1971)
labeled as Folklore by Bart Demoen. But easy to recognize
as Union Find data structure.

Bye

(**) Maybe I should construct such an example.
I am not anymore sure about that, since Union Find
detects structure sharing. But I doubt the bad cases
are only quadratic, at least there are some easy

example of exponential behaviour of unifiction
already published. But I don't remember what kind
of unification they assume. So have to double check.

Mild Shock schrieb:
> Hi,
> 
> The diagram figure 2 here:
> 
> Fifty Years of Prolog and Beyond (TPLP 2022)
> KÖRNER P, LEUSCHEL M, BARBOSA J, et al. Fifty Years of Prolog and 
> Beyond. Theory and Practice of Logic Programming.
> 2022;22(6):776-858. doi:10.1017/S1471068422000102
> 
> And reproduced here:
> 
> Comparison of Prolog implementations
> The page has also missing Scryer Prolog, which
> I think is an important Prolog system written in
> Rust, because it also pays tribute to Prolog II.
> https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations
> 
> Is pretty much brainwashed nonsense. Most Prolog
> systems, that have cyclic terms, are derived from
> Prolog II.  Adopting a non-canonical rational tree
> 
> term approach. This includes:
> 
> - SICStus Prolog
> - Ciao Prolog
> - YAP Prolog
> - SWI-Prolog
> - Scryer Prolog
> - Trealla Prolog
> - Dogelog Player
> - What else?
> 
> SICStus Prolog is possibly the most advanced, (*)
> it also supports asserts and copying, whereas I found
> not all Prolog systems listed above can even
> 
> copy cyclic terms, despite they can unify them.
> Basically the philogeny of Prolog systems is
> not some "single inheritance" tree. Cyclic terms
> 
> algorithm have nice side effect that they might
> speed up acyclic term arguments as well. But
> cyclic terms is one of the topics that is very
> 
> badily  covered, for some individuals difficult (**)
> to understand and sometimes even completely ignored.
> 
> Bye
> 
> (*)
> SICStus Prolog unifies, compares (see ref-lte-cte),
> asserts, and copies cyclic terms without looping.
> The write_term/[2,3] built-in predicate can
> optionally handle cyclic terms.
> https://sicstus.sics.se/sicstus/docs/4.6.0/html/sicstus/ref_002dsem_002docc.html 
> 
> 
> (**)
> Because of the infinite looping, their brains might
> also get into infinite loops. Even fuzzy testing does
> not help anymore breaking these loops.

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

Thread

Cyclic terms are missing from "Fifty Years of Prolog and Beyond (TPLP 2022)" Mild Shock <janburse@fastmail.fm> - 2025-09-22 14:54 +0200
  Wikipedia is clueless about cyclic terms (Was: Cyclic terms are missing from "Fifty Years of Prolog and Beyond (TPLP 2022)") Mild Shock <janburse@fastmail.fm> - 2025-09-22 15:05 +0200
  Wikipedia is clueless about cyclic terms (Was: Cyclic terms are missing from "Fifty Years of Prolog and Beyond (TPLP 2022)") Mild Shock <janburse@fastmail.fm> - 2025-09-22 15:07 +0200
    Can Ulrich Neumerkel or Markus Triska fix that? (Was: Wikipedia is clueless about cyclic terms) Mild Shock <janburse@fastmail.fm> - 2025-09-22 15:14 +0200
      Quadratic Bound true, and Exponential false (Was: Can Ulrich Neumerkel or Markus Triska fix that?) Mild Shock <janburse@fastmail.fm> - 2025-09-22 15:36 +0200
        Jaxon Jaffar might be the inventor of Union Find Unification (Was: Quadratic Bound true, and Exponential false) Mild Shock <janburse@fastmail.fm> - 2025-09-22 23:01 +0200
          Conclusion quasi-linear time and linear space (Was: Jaxon Jaffar might be the inventor of Union Find Unification) Mild Shock <janburse@fastmail.fm> - 2025-09-22 23:34 +0200

csiph-web