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

Groups > comp.lang.prolog > #14835

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

Show all headers | View raw

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

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