Cyclic Term Unification is Accounted (Was: SWI-Prolog is still the OG of GC)

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Cyclic Term Unification is Accounted (Was: SWI-Prolog is still the OG of GC)
Date	2025-08-16 11:59 +0200
Message-ID	<107pkpt$4egd$1@solani.org> (permalink)
References	(1 earlier) <107fqjo$3m3hh$1@solani.org> <107kduo$10b9$1@solani.org> <107pik3$4csp$1@solani.org> <107pjag$4dc8$1@solani.org> <107pk1o$4e0v$1@solani.org>

Show all headers | View raw

Hi,

In the newest test results below, Cyclic
Term Unification of Clause Heads is already
Accounted. Means I tested versions that

have Cyclic Term Unification deep in the
Prolog interpreter. Why does it not slow down
the Prolog system? Because Cyclic Term

Unification doesn't kick in for certain Prolog
system designs under certain conditions:

- If the head is linear no cyclic unification
   happens. Since the machine code for head
   unification is executed in write-unification
   mode. All variables are "first_var" instructions.

- Even if the the calling goal is smaller than
   the head, means if a switch happens to
   read-unification mode, again cyclic unification
   doesn't happen for linear patterns.

You can check yourself whether a head is linear
or not. Just define:

term_linear(X) :-
    term_variables(X, L),
    term_singletons(X, R),
    L == R.

?- term_linear(fun(X, Y, Z, A)).
true.

The bad thing is this holds only for Dogelog Player
which has the smarter head unification. While it
doesn't hold for formerly Jekejeke Prolog,

which has an ancient PLM design. So Jekejeke Prolog
got indeed a little slower with Cyclic Term Unification
and I don't know much what I could do against it.

I had old versions of Jekejeke Prolog which did
indeed special head linear compilation, and linear
head unification execution, as some experiment in

occurs check. But I wont resurrect this special
compilation. I am more preparing the final graveyard
for Jekejeke Prolog. But there are still a few things

to harvest from formerly Jekejeke Prolog,
so the final stab might come in 1-2 years.

Bye

Mild Shock schrieb:
> Hi,
> 
> BTW: Here a test without WASM:
> 
> /* Trealla Prolog 2.82.12 WSL2 */
> ?- time(mtak).
> % Time elapsed 0.734s, 8873504 Inferences, 12.091 MLips
>     true.
> 
> /* SWI Prolog 9.0.4 WSL2 */
> ?- time(mtak).
> % 3,943,790 inferences, 0.210 CPU in 0.217 seconds
> (97% CPU, 18777906 Lips)
> true.
> 
> /* Dogelog Player 1.3.6 Windows 11 */
> ?- time(mtak).
> % Zeit 412 ms, GC 0 ms, Lips 20341271, Uhr 16.08.2025 11:40
> true.
> 
> /* Jekejeke Prolog 1.7.3 Windows 11 */
> ?- time(mtak).
> % Zeit 664 ms, GC 3 ms, Uhr 16.08.2025 11:41
> true.
> 
> I didn't test Scryer Prolog because it has no GC.
> I keep testing Jekejeke Prolog because it has
> reference counting. But Dogelog Player without
> 
> reference counting and true garbage collection,
> seems to be more speedy. Not as fast as SWI-Prolog.
> But faster than Trealla Prolog.
> 
> So SWI-Prolog is still the Orginal Gangster (OG)
> of garbage collection (GC). Some Prolog systems
> like Ciao Prolog, ECLiPSe Prolog or SICStus Prolog
> 
> might be even faster, since it seems to me they use
> native backend compilation schemes, AOT or JIT. The
> tested systems above are all more of the
> 
> interpreter type Prolog systems.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> It seems the gist of WebPL is to examine
>> dynamic variable shunting as part of a
>> garbage collection strategy, as found here:
>>
>> Variable Shunting for the WAM
>> Sahlin, D. and Carlsson, M. - 1991
>> https://www.diva-portal.org/smash/get/diva2:1041385/FULLTEXT01.pdf
>>
>> Does it pay off? I am testing
>> Version II of mtak:
>>
>> /* WebPL GC Rust-WAMS */
>> True
>> (1875.2ms)
>> No more results
>>
>> /* Trealla Prolog C-WASM */
>> True
>> (1269.5ms)
>> No more results
>>
>> /* SWI-Prolog C-WASM */
>> True
>> (1368.9ms)
>> No more results
>>
>> The 1875.2ms are worse than my 1489 ms. The
>> 1269.5ms and 1368.9ms are only slightly better
>> than my 1489 ms.
>>
>> I would say static shunting is the secret ingredient
>> of Dogelog Player, that makes it fast sometimes!
>> Just think about it, in the above JavaScript is
>>
>> compared to WASM. Whats going on? Of course
>> one should repeat the test with newest and newest
>> SWI-Prolog and Trealla Prolog. Don't know
>>
>> whether there is a site that does all the updates.
>>
>> Bye
>>
>> BTW: For between/2 was using:
>>
>> between(Lo, Lo, R) :- !, Lo = R.
>> between(Lo, _, Lo).
>> between(Lo, Hi, X) :- Lo2 is Lo+1, between(Lo2, Hi, X).
>>
>> Mild Shock schrieb:
>>> There is a difference between this:
>>>
>>> /* Version I */
>>> fun(X, Y, Z, A) :-
>>>      X =< Y, !,
>>>      Z = A.
>>> fun(X, Y, Z, A) :-
>>>      X1 is X - 1,
>>>      fun(X1, Y, Z, A1),
>>>      Y1 is Y - 1,
>>>      fun(Y1, Z, X, A2),
>>>      Z1 is Z - 1,
>>>      fun(Z1, X, Y, A3),
>>>      fun(A1, A2, A3, A).
>>>
>>> And this in Dogelog Player:
>>>
>>> /* Version II */
>>> fun(X, Y, Z, A) :-
>>>      X =< Y, !,
>>>      Z = A.
>>> fun(X, Y, Z, A) :-
>>>      X1 is X - 1,
>>>      Y1 is Y - 1,
>>>      Z1 is Z - 1,
>>>      fun(X1, Y, Z, A1),
>>>      fun(Y1, Z, X, A2),
>>>      fun(Z1, X, Y, A3),
>>>      fun(A1, A2, A3, A).
>>>
>>> Usually I am benchmarking Version I, but Version II
>>> gives Dogelog Player the opportunity to do more
>>> static Variable Shunting. Which is seen in the
>>>
>>> performance. Not its JavaScript not WASM:
>>>
>>> /* Version I */
>>> % Zeit 1723 ms, GC 6 ms, Lips 4863960, Uhr 16.08.2025 11:21
>>>
>>> /* Version II */
>>> % Zeit 1489 ms, GC 2 ms, Lips 5628343, Uhr 16.08.2025 11:21
>>>
>>> Was resting:
>>>
>>> mtak :- between(1,31,_), fun(18, 12, 6, _), fail.
>>> mtak.
>>>
>>> :- time(mtak).
>>
>

Thread

Prolog Education Group clueless about the AI Boom? Mild Shock <janburse@fastmail.fm> - 2025-03-03 14:18 +0100
  Re: Prolog Education Group clueless about the AI Boom? Mild Shock <janburse@fastmail.fm> - 2025-03-03 14:20 +0100
    Salary Templates if you "Grok" ML / AI [PhDs Negotiate Salaries] (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-03 18:03 +0100
  ILP is still dreaming of higher order (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-07 23:58 +0100
    Re: ILP is still dreaming of higher order (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-08 00:00 +0100
  FYI: Philip Zucker’s Co-Egraphs (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-08-12 18:37 +0200
    Using Hopcroft & Karp (HK) everywhere (Was: FYI: Philip Zucker’s Co-Egraphs) Mild Shock <janburse@fastmail.fm> - 2025-08-14 12:31 +0200
      Confusing "decidable problem" and "complete algorithm" (Was: Using Hopcroft & Karp (HK) everywhere) Mild Shock <janburse@fastmail.fm> - 2025-08-14 14:31 +0200
        DFA algorithms in a Python library (Re: Confusing "decidable problem" and "complete algorithm") Mild Shock <janburse@fastmail.fm> - 2025-08-14 15:14 +0200
      Static Variable Shunting in Dogelog Player (Was: Using Hopcroft & Karp (HK) everywhere) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:22 +0200
        Dynamic Variable Shunting in WebPL (Was: Static Variable Shunting in Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:34 +0200
          SWI-Prolog is still the OG of GC (Was: Dynamic Variable Shunting in WebPL) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:46 +0200
            Cyclic Term Unification is Accounted (Was: SWI-Prolog is still the OG of GC) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:59 +0200
            WebPL is an interesting project (Was: SWI-Prolog is still the OG of GC) Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:00 +0200
              Head to Head Race with Scryer Prolog (Was: WebPL is an interesting project) Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:24 +0200
                Does Variable Age make Sense? [Prolog Unification] (Was: Head to Head Race with Scryer Prolog) Mild Shock <janburse@fastmail.fm> - 2026-02-10 12:05 +0100
                Type systems for non-deterministic concurrency [Amir Pnueli] (Was: Does Variable Age make Sense? [Prolog Unification]) Mild Shock <janburse@fastmail.fm> - 2026-07-20 12:20 +0200
                Robin Milners fickle gives non-determinism in practice [Parallel π-WAM] (Was: Type systems for non-deterministic concurrency [Amir Pnueli]) Mild Shock <janburse@fastmail.fm> - 2026-07-20 12:34 +0200
  Sleepy Joe and the Poor South (Local AI Emacs Mode) (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-11-12 12:59 +0100
    Beyond Sleepy Joe around the World (Was: Sleepy Joe and the Poor South (Local AI Emacs Mode)) Mild Shock <janburse@fastmail.fm> - 2025-11-12 13:12 +0100
  GENESIS MISSION: Loosing it over Deep Pokets [Business wants A-Life] (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-11-26 18:07 +0100
  Vanilla Prolog: semi-decidable =\= decidable (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2026-03-14 20:40 +0100
    Its on the Internet, so it must be true? (Was: Vanilla Prolog: semi-decidable =\= decidable) Mild Shock <janburse@fastmail.fm> - 2026-03-16 11:01 +0100
    Hack + Computed Goto = Leightweigh C_OR (Was: Vanilla Prolog: semi-decidable =\= decidable) Mild Shock <janburse@fastmail.fm> - 2026-07-04 16:58 +0200
      The stack and choice points as an after match (Re: Hack + Computed Goto = Leightweigh C_OR) Mild Shock <janburse@fastmail.fm> - 2026-07-04 17:07 +0200
        Introduction to AI Accelerator Prolog [π-WAM of Dogelog] (Was: The stack and choice points as an after match) Mild Shock <janburse@fastmail.fm> - 2026-07-17 10:49 +0200
          Not praying to the god of lambda calculus [π beats α] (Was: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-17 11:13 +0200
          pi in pi-WAM refers to pi-calculus (Re: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 01:22 +0200
            Milners fickle() in pi-WAM [For fun and profit] (Re: pi in pi-WAM refers to pi-calculus (Re: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 01:49 +0200
              Robin Milners pi calculus is typeless (Re: Milners fickle() in pi-WAM [For fun and profit]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 11:00 +0200
                Can the Church Turing hypotheses be refuted? [TLo @ FOM] (Re: Robin Milners pi calculus is typeless) Mild Shock <janburse@fastmail.fm> - 2026-07-18 11:10 +0200
          Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC] (Was: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-19 16:06 +0200
            ANN: Library Pegg, for π-E-graphs [Not EXWM] (Was: Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC]) Mild Shock <janburse@fastmail.fm> - 2026-07-19 16:21 +0200

csiph-web