Static Shunting is even better [Dogelog Player] (Was: Smarter Partial Strings would use Program Sharing ['$append'/3])

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Static Shunting is even better [Dogelog Player] (Was: Smarter Partial Strings would use Program Sharing ['$append'/3])
Date	2025-08-18 15:49 +0200
Message-ID	<107vb1v$7sd2$1@solani.org> (permalink)
References	<107t0fi$6bgl$1@solani.org> <107v7mv$7pr2$1@solani.org> <107v8gs$7qee$1@solani.org> <107vakb$7s17$1@solani.org>

Show all headers | View raw

Hi,

In Dogelog Player I don't need to introduce
'$append'/3, since in this code there is
anyway an attempt to do static shunting:

p(C, B) :- C = [a,b,c|A], q(A, B).

It is handled as if it were:

p([a,b,c|A], B) :- q(A, B).

This means [a,b,c|A] is anyway program shared (PS),
and a matching happens so that we can ultimately
omit the creation of a real Prolog variable for

A. It will get a special place holder that is
not trailed. Maybe I will find a test case
to illustrate this form of program sharing,

which I have temporarily termed static shunting,
whereas WebPL paper shunting, I would rather
call dynamic shunting. Unfortuantely WebPL

does not support DCG parsing, the (-->)/2
clauses don't work. So will take me more time
to test whether there is something in WebPL,

concerning this type of program sharing as well,
or whether it was botched.

Bye

Mild Shock schrieb:
> Hi,
> 
> Smarter Partial Strings would use Program
> Sharing. Take the invention of Scryer
> Prolog and think about it from a Program
> 
> Sharing prespective:
> 
> p --> "abc", q
> 
> Translates to with Partial Strings:
> 
> p(C, B) :- C = "abc"||A, q(A, B).
> 
> Unfortunately straight forward Program
> Sharning of the partial string doesn't
> work anymore, since it is not ground:
> 
> p(C, B) :- C = [a,b,c|A], q(A, B).
> 
> But we could translate the DCG also to:
> 
> p(C, B) :- '$append'([a,b,c],A,C), q(A, B).
> 
> Where '$append'/3 is a mode (+,-,-) specialization
> of append/3. Could be natively implemented.
> The mode (+,-,-) will be more clever
> 
> then the failed programm sharing. The program
> sharing can share the string "abc", since with
> '$append'/3, the DCG is basically:
> 
> p(C, B) :- '$append'("abc",A,C), q(A, B).
> 
> Now '$append'/3 would do a copying of the string,
> if A is unbound, this is usually the "DCG used for
> text generation" mode. But if A is bound, the
> 
> '$append'/3 would not do some copying, but it
> would actually match the prefix. So it gives
> a much better DCG for parsing, since this is
> 
> "DCG used for text parsing" mode.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Ok lets run the test case on the desktop,
>> and not on the web. What do we get? Its almost
>> constant for Trealla Prolog as well, in
>>
>> WebPL it was perfectly constant, but here
>> its only almost constant:
>>
>> /* Trealla Prolog 2.82.14 */
>>
>> ?- time(test2(10)).
>> % Time elapsed 0.188s, 3004002 Inferences, 16.014 MLips
>>     true.
>>
>> ?- time(test2(30)).
>> % Time elapsed 0.210s, 3004002 Inferences, 14.321 MLips
>>     true.
>>
>> ?- time(test2(90)).
>> % Time elapsed 0.228s, 3004002 Inferences, 13.147 MLips
>>     true.
>>
>> Scryer Prolog fails the test horribly. Which
>> is amazing, since it is a Rust Prolog system just
>> like WebPL. But they are too traditional in
>>
>> following the stupid WAM design:
>>
>> /* Scryer Prolog 0.9.4-599 */
>>
>> ?- time(test2(10)).
>>     % CPU time: 0.714s, 7_049_076 inferences
>>     true.
>>
>> ?- time(test2(30)).
>>     % CPU time: 1.284s, 7_049_099 inferences
>>     true.
>>
>> ?- time(test2(90)).
>>     % CPU time: 2.984s, 7_049_099 inferences
>>     true.
>>
>> Bye
>>
>> Mild Shock schrieb:
>>> Hi,
>>>
>>> Heap/Stack Prolog systems could solve some Prolog
>>> String Problems, especially in connection with a FFI, but I am
>>> not showing that. More a general design limitation of the common
>>>
>>> take of WAM resp. ZIP. The new WebPL Prolog describes itself as a
>>> merged Heap/Stack architecture Prolog system. And has a reference
>>> in its escorting paper to an academic work by Xining Li (1999):
>>>
>>> A new term representation method for prolog
>>> Xining Li - 1999
>>> https://www.sciencedirect.com/science/article/pii/S0743106697000629
>>>
>>> Besides that Program Sharing (PS), as it is called in the paper,
>>> is nothing new, WebPL also shows a more modern take, in that
>>> it already uses compound data types from Rust. Can we
>>>
>>> replicate some of the performance advantages of a PS system
>>> versus the more traditional WAM resp. ZIP based systems? Here
>>> is a simple test in the WebPL Playground, for Web PL without GC:
>>>
>>> /* WebPL NoGC */
>>> ?- test2(10).
>>> (1795.6ms)
>>>
>>> ?- test2(30).
>>> (1785.5ms)
>>>
>>> ?- test2(90).
>>> (1765.6ms)
>>> Then SWI-Prolog WASM as found in SWI-Tinker:
>>>
>>> /* SWI-Prolog WASM */
>>> ?- test2(10).
>>> (1239.3ms)
>>>
>>> ?- test2(30).
>>> (2276.1ms)
>>>
>>> ?- test2(90).
>>> (5372.3ms)
>>>
>>> https://webpl.whenderson.dev/
>>>
>>> Bye
>>>
>>> The test case:
>>>
>>> data(10, [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]).
>>>
>>> data(30, [30, 29, 28, 27, 26, 25, 24, 23,
>>>     22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
>>>     12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]).
>>>
>>> data(90, [90, 89, 88, 87, 86, 85, 84, 83,
>>>     82, 81, 80, 79, 78, 77, 76, 75, 74, 73,
>>>     72, 71, 70, 69, 68, 67, 66, 65, 64, 63,
>>>     62, 61, 60, 59, 58, 57, 56, 55, 54, 53,
>>>     52, 51, 50, 49, 48, 47, 46, 45, 44, 43,
>>>     42, 41, 40, 39, 38, 37, 36, 35, 34, 33,
>>>     32, 31, 30, 29, 28, 27, 26, 25, 24, 23,
>>>     22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
>>>     12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]).
>>>
>>> test(N) :- between(1,1000,_), data(N,_), fail.
>>> test(_).
>>>
>>> test2(N) :- between(1,1000,_), test(N), fail.
>>> test2(_).
>>>
>>> between(Lo, Lo, R) :- !, Lo = R.
>>> between(Lo, _, Lo).
>>> between(Lo, Hi, X) :- Lo2 is Lo+1, between(Lo2, Hi, X).
>>>
>>>
>>>
>>> Mild Shock schrieb:
>>>> Hi,
>>>>
>>>> WebPL is already outdated I guess. It doesn't
>>>> show the versions of the other Prolog systems
>>>> it is using. While I had these results for
>>>>
>>>> the primes example in the WebPL playground:
>>>>
>>>> /* Trealla Prolog WASM */
>>>> (23568.9ms)
>>>>
>>>> When I run the example here:
>>>>
>>>> https://php.energy/trealla.html
>>>>
>>>> I get better results:
>>>>
>>>> /* trealla-js 0.27.1 */
>>>>
>>>> ?- time(test).
>>>> % Time elapsed 9.907s, 11263917 Inferences, 1.137 MLips
>>>>
>>>> Bye
>>>
>>
>

Thread

WebPL is already outdated Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:37 +0200
  Heap/Stack versus WAM resp. ZIP (Was: WebPL is already outdated) Mild Shock <janburse@fastmail.fm> - 2025-08-18 14:52 +0200
    Trealla knows Program Sharing (PS) Tricks ? (Was: Heap/Stack versus WAM resp. ZIP) Mild Shock <janburse@fastmail.fm> - 2025-08-18 15:06 +0200
      Smarter Partial Strings would use Program Sharing ['$append'/3] (Was: Trealla knows Program Sharing (PS) Tricks ?) Mild Shock <janburse@fastmail.fm> - 2025-08-18 15:42 +0200
        Static Shunting is even better [Dogelog Player] (Was: Smarter Partial Strings would use Program Sharing ['$append'/3]) Mild Shock <janburse@fastmail.fm> - 2025-08-18 15:49 +0200
  The Artificial Intelligence Flip: Acer Swift Go! (Was: WebPL is already outdated) Mild Shock <janburse@fastmail.fm> - 2025-08-31 23:56 +0200
    2025 will be last year we hear of Python (Re: The Artificial Intelligence Flip: Acer Swift Go!) Mild Shock <janburse@fastmail.fm> - 2025-09-01 00:45 +0200
      Apertus: With love, from Switzerland [02 Sept 2025] (Re: 2025 will be last year we hear of Python) Mild Shock <janburse@fastmail.fm> - 2025-09-05 00:36 +0100
      Don't try this (Was: Apertus: With love, from Switzerland [02 Sept 2025] ) Mild Shock <janburse@fastmail.fm> - 2025-09-05 01:03 +0100
      AI means ambracing Non-Linearity (Was: 2025 will be last year we hear of Python) Mild Shock <janburse@fastmail.fm> - 2025-09-19 10:01 +0200
        AI soaked PCs: Is there a Copilot+ Prolog? (Was: AI means ambracing Non-Linearity) Mild Shock <janburse@fastmail.fm> - 2025-09-19 10:10 +0200
          The morning coffee incident [Prolog Community] (Was: AI soaked PCs: Is there a Copilot+ Prolog?) Mild Shock <janburse@fastmail.fm> - 2025-09-19 14:38 +0200
            Root Cause Prediction for Your Brain (Was: The morning coffee incident [Prolog Community]) Mild Shock <janburse@fastmail.fm> - 2025-09-19 18:22 +0200
              Please delete my account and all my posts on SWI-Prolog discourse (Re: Root Cause Prediction for Your Brain) Mild Shock <janburse@fastmail.fm> - 2025-09-19 18:38 +0200
                I will consult a Lawyer of mine (Was: Please delete my account and all my posts on SWI-Prolog discourse) Mild Shock <janburse@fastmail.fm> - 2025-09-19 18:42 +0200
  Scryer Prolog unify_with_occurs_check/2 doesn't scale (Was: WebPL is already outdated) Mild Shock <janburse@fastmail.fm> - 2025-09-19 16:08 +0200
    How bad is Rust, can JavaScript beat it? (Was: Scryer Prolog unify_with_occurs_check/2 doesn't scale) Mild Shock <janburse@fastmail.fm> - 2025-09-19 16:18 +0200
    unify_with_occurs_check/2 might have been fixed (Was: Scryer Prolog unify_with_occurs_check/2 doesn't scale) Mild Shock <janburse@fastmail.fm> - 2025-09-25 01:50 +0200
      Had to Rollback my Jaffar Unification (Was: unify_with_occurs_check/2 might have been fixed) Mild Shock <janburse@fastmail.fm> - 2025-09-25 01:59 +0200
        Trealla Prolog might apply "frozeness" to cyclic terms (Was: Had to Rollback my Jaffar Unification) Mild Shock <janburse@fastmail.fm> - 2025-09-25 02:06 +0200
          Non-intrusive through "frozen" subcategories (Was: Trealla Prolog might apply "frozeness" to cyclic terms) Mild Shock <janburse@fastmail.fm> - 2025-09-25 02:21 +0200
    Scryer Prolog occurs check cannot do hydra (Was: Scryer Prolog unify_with_occurs_check/2 doesn't scale) Mild Shock <janburse@fastmail.fm> - 2025-09-26 12:19 +0200
  WebPL and Scryer Prolog are bad examples (Was: WebPL is already outdated) Mild Shock <janburse@fastmail.fm> - 2025-10-13 09:49 +0200
    Who will win Shift-Reduce or Tabled DCG? [AI Boom] (Was: WebPL and Scryer Prolog are bad examples) Mild Shock <janburse@fastmail.fm> - 2025-10-13 15:09 +0200
  primes.pl mainly tests the Prolog ALU [mod/2 vs rem/2] (Was: WebPL is already outdated) Mild Shock <janburse@fastmail.fm> - 2025-10-15 02:38 +0200
    25-30% is insane, Neural Network Branch Prediction? (Was: primes.pl mainly tests the Prolog ALU) Mild Shock <janburse@fastmail.fm> - 2025-10-15 04:33 +0200
      NPUs (Neural Processing Units) are the new normal (Was: 25-30% is insane, Neural Network Branch Prediction?) Mild Shock <janburse@fastmail.fm> - 2025-10-15 16:04 +0200
        Ask Phind: AI inflection point right now [End 2025] (Was: NPUs (Neural Processing Units) are the new normal) Mild Shock <janburse@fastmail.fm> - 2025-10-15 16:10 +0200
          Eat Tteokbokki before SkyNet kills you [$100 ChatGPT] (Was: Ask Phind: AI inflection point right now [End 2025]) Mild Shock <janburse@fastmail.fm> - 2025-10-18 15:57 +0200
            Give Julio Di Egidio the bloody money [3 RMB¥ MiniMind] (Re: Eat Tteokbokki before SkyNet kills you [$100 ChatGPT]) Mild Shock <janburse@fastmail.fm> - 2025-10-18 16:19 +0200
              Vertex AI Training is more expensive? (Was: Give Julio Di Egidio the bloody money [3 RMB¥ MiniMind]) Mild Shock <janburse@fastmail.fm> - 2025-10-21 00:32 +0200
        The Love Affair: OpenAI and AMD (Was: NPUs (Neural Processing Units) are the new normal) Mild Shock <janburse@fastmail.fm> - 2025-10-18 18:59 +0200
        The NPU in your Browser [WebNN by W3C] (Was: NPUs (Neural Processing Units) are the new normal) Mild Shock <janburse@fastmail.fm> - 2025-10-26 08:39 +0100
          Fuzzy Alert: Boris the Loris on the Dancefloor (Was: The NPU in your Browser [WebNN by W3C]) Mild Shock <janburse@fastmail.fm> - 2025-10-26 11:33 +0100

csiph-web