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

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

Cyclic terms are missing from "Fifty Years of Prolog and Beyond (TPLP 2022)"

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

Contents

  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

#14830 — Cyclic terms are missing from "Fifty Years of Prolog and Beyond (TPLP 2022)"

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.

[toc] | [next] | [standalone]

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

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.

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

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

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.

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

#14833 — Can Ulrich Neumerkel or Markus Triska fix that? (Was: Wikipedia is clueless about cyclic terms)

Hi,

In case Scryer Prolog tries the this here:

Wikipedia entry for Scryer Prolog
https://github.com/mthom/scryer-prolog/discussions/3074

And considers these articles:

https://en.wikipedia.org/wiki/Occurs_check
https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations
https://en.wikipedia.org/wiki/Prolog

They might probably draw the same conclusion,
namely that there are some gaps or that
certain articles are a little dusty.

Again I think covering Scyer Prolog is
important for two reasons:

- Its not the C spaghetti code mess like SWI-Prolog
   which uses goto and macros to no end.

- It is not a Heap/Stack Prolog system, it even has
   no GC, still the Heap plays a role in the cyclic term algorithms

The later point is amazing, and its interesting to
see how Scryer Prolog fares performance wise.
They simply use Vec<> in some places to eliminate

the use of native stack. Is this "bold" , or only
the best thing one would anyway do inside a programming
language like Rust, that might have tread affine fast

malloc() and free(). So that bothering with placing
things on artificially created stack is not needed.
Just go with the ADT (Abstract Data Type) Vec<>.

Bye

Mild Shock schrieb:
> 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.
> 

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

#14834 — Quadratic Bound true, and Exponential false (Was: Can Ulrich Neumerkel or Markus Triska fix that?)

Hi,

The quadratic bound could be also a trivial
corollary from Union Find structure? Not sure.

And the exponential explosion example, similar
to my hydra testing, only show bad algorithmic

implementations ignoring Hopecroft & Karp (1971).
That could also be the case.

Bye

Mild Shock schrieb:
> Hi,
> 
> In case Scryer Prolog tries the this here:
> 
> Wikipedia entry for Scryer Prolog
> https://github.com/mthom/scryer-prolog/discussions/3074
> 
> And considers these articles:
> 
> https://en.wikipedia.org/wiki/Occurs_check
> https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations
> https://en.wikipedia.org/wiki/Prolog
> 
> They might probably draw the same conclusion,
> namely that there are some gaps or that
> certain articles are a little dusty.
> 
> Again I think covering Scyer Prolog is
> important for two reasons:
> 
> - Its not the C spaghetti code mess like SWI-Prolog
>    which uses goto and macros to no end.
> 
> - It is not a Heap/Stack Prolog system, it even has
>    no GC, still the Heap plays a role in the cyclic term algorithms
> 
> The later point is amazing, and its interesting to
> see how Scryer Prolog fares performance wise.
> They simply use Vec<> in some places to eliminate
> 
> the use of native stack. Is this "bold" , or only
> the best thing one would anyway do inside a programming
> language like Rust, that might have tread affine fast
> 
> malloc() and free(). So that bothering with placing
> things on artificially created stack is not needed.
> Just go with the ADT (Abstract Data Type) Vec<>.
> 
> Bye
> 
> Mild Shock schrieb:
>> 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.
>>
> 

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

#14835 — Jaxon Jaffar might be the inventor of Union Find Unification (Was: Quadratic Bound true, and Exponential false)

Hi,

Now I found out who invented union find for unification
in Prolog via Bart Demoens trick. It was Jaxon Jaffar
possibly ? In his 1984 paper he used circular lists ,
probably derived from multiequation approach by Rossi.

He states The non-variable terms in a class shall be linked
together as a circular list via the "term" links within
each root term node. Its not a big step to do it slightly
different, like sparing the term field, and use the

functor itself. As many Prolog systems do. The result is
not anymore a circular list, but rather the Union Find
structure where one follows a chain. The 1984 paper has
also a test suite, with 4 different scenarios:

Efficient Unification over Infinite Terms
Joxan JAFFAR
New Generation Computing, 2 (1984) 207-219
OHMSHA, LTD. and Springer-Verlag

He uses the test suite to compare against among other
algorithms COL and MUK. And guess what COL is Alain
Colmerauers Algorithm, and MUK is ( Kuniaki ?) Mukai
algorithm. Might explore the test suite as well,

it has tests with N=10, 25, 50. But today we typically
test with N=1000000, not only N=1000.

LoL

Bye

Mild Shock schrieb:
> Hi,
> 
> The quadratic bound could be also a trivial
> corollary from Union Find structure? Not sure.
> 
> And the exponential explosion example, similar
> to my hydra testing, only show bad algorithmic
> 
> implementations ignoring Hopecroft & Karp (1971).
> That could also be the case.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> In case Scryer Prolog tries the this here:
>>
>> Wikipedia entry for Scryer Prolog
>> https://github.com/mthom/scryer-prolog/discussions/3074
>>
>> And considers these articles:
>>
>> https://en.wikipedia.org/wiki/Occurs_check
>> https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations
>> https://en.wikipedia.org/wiki/Prolog
>>
>> They might probably draw the same conclusion,
>> namely that there are some gaps or that
>> certain articles are a little dusty.
>>
>> Again I think covering Scyer Prolog is
>> important for two reasons:
>>
>> - Its not the C spaghetti code mess like SWI-Prolog
>>    which uses goto and macros to no end.
>>
>> - It is not a Heap/Stack Prolog system, it even has
>>    no GC, still the Heap plays a role in the cyclic term algorithms
>>
>> The later point is amazing, and its interesting to
>> see how Scryer Prolog fares performance wise.
>> They simply use Vec<> in some places to eliminate
>>
>> the use of native stack. Is this "bold" , or only
>> the best thing one would anyway do inside a programming
>> language like Rust, that might have tread affine fast
>>
>> malloc() and free(). So that bothering with placing
>> things on artificially created stack is not needed.
>> Just go with the ADT (Abstract Data Type) Vec<>.
>>
>> Bye
>>
>> Mild Shock schrieb:
>>> 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.
>>>
>>
> 

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

#14836 — Conclusion quasi-linear time and linear space (Was: Jaxon Jaffar might be the inventor of Union Find Unification)

Hi,

How difficult would it be to get hold of the original
implementation back then. The paper says Our results
are in Fig. 7. They are obtained by implementations
in the programming language C on a VAX 11/780

running UNIX 4.1 BSD. But the pseudo code inside
the paper looks more Pascal than C, like using ^
instead *. The paper ultimately states in an Analysis
chapter the complexities:

- Space complexity: Linear O(N)
- Time complexity: Quasi-linear O(N*F(N))

BTW: The algorithm is also a no-stack algorithm.
Using some common_frontier and a queue. But since
it looks much more complicated than what can be
done in a few lines as well, it would be also

interesting to see what the constant factor is,
compare to some alternative implementation.

Bye

Mild Shock schrieb:
> Hi,
> 
> Now I found out who invented union find for unification
> in Prolog via Bart Demoens trick. It was Jaxon Jaffar
> possibly ? In his 1984 paper he used circular lists ,
> probably derived from multiequation approach by Rossi.
> 
> He states The non-variable terms in a class shall be linked
> together as a circular list via the "term" links within
> each root term node. Its not a big step to do it slightly
> different, like sparing the term field, and use the
> 
> functor itself. As many Prolog systems do. The result is
> not anymore a circular list, but rather the Union Find
> structure where one follows a chain. The 1984 paper has
> also a test suite, with 4 different scenarios:
> 
> Efficient Unification over Infinite Terms
> Joxan JAFFAR
> New Generation Computing, 2 (1984) 207-219
> OHMSHA, LTD. and Springer-Verlag
> 
> He uses the test suite to compare against among other
> algorithms COL and MUK. And guess what COL is Alain
> Colmerauers Algorithm, and MUK is ( Kuniaki ?) Mukai
> algorithm. Might explore the test suite as well,
> 
> it has tests with N=10, 25, 50. But today we typically
> test with N=1000000, not only N=1000.
> 
> LoL
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> The quadratic bound could be also a trivial
>> corollary from Union Find structure? Not sure.
>>
>> And the exponential explosion example, similar
>> to my hydra testing, only show bad algorithmic
>>
>> implementations ignoring Hopecroft & Karp (1971).
>> That could also be the case.
>>
>> Bye
>>
>> Mild Shock schrieb:
>>> Hi,
>>>
>>> In case Scryer Prolog tries the this here:
>>>
>>> Wikipedia entry for Scryer Prolog
>>> https://github.com/mthom/scryer-prolog/discussions/3074
>>>
>>> And considers these articles:
>>>
>>> https://en.wikipedia.org/wiki/Occurs_check
>>> https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations
>>> https://en.wikipedia.org/wiki/Prolog
>>>
>>> They might probably draw the same conclusion,
>>> namely that there are some gaps or that
>>> certain articles are a little dusty.
>>>
>>> Again I think covering Scyer Prolog is
>>> important for two reasons:
>>>
>>> - Its not the C spaghetti code mess like SWI-Prolog
>>>    which uses goto and macros to no end.
>>>
>>> - It is not a Heap/Stack Prolog system, it even has
>>>    no GC, still the Heap plays a role in the cyclic term algorithms
>>>
>>> The later point is amazing, and its interesting to
>>> see how Scryer Prolog fares performance wise.
>>> They simply use Vec<> in some places to eliminate
>>>
>>> the use of native stack. Is this "bold" , or only
>>> the best thing one would anyway do inside a programming
>>> language like Rust, that might have tread affine fast
>>>
>>> malloc() and free(). So that bothering with placing
>>> things on artificially created stack is not needed.
>>> Just go with the ADT (Abstract Data Type) Vec<>.
>>>
>>> Bye
>>>
>>> Mild Shock schrieb:
>>>> 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.
>>>>
>>>
>>
> 

[toc] | [prev] | [standalone]

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

csiph-web