Path: ...!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: DCG Translation with Unification Spillling (Was: Is old school
 mode directed compilation dead?)
Date: Sat, 25 Jan 2025 20:44:46 +0100
Message-ID: <vn3evd$fmq0$2@solani.org>
References: <b406aa35-c39b-46f3-862f-1cc4b75143ae@googlegroups.com>
 <1b7ce2bd-722b-4c2e-b853-12fc2232752bn@googlegroups.com>
 <vb2jba$202pl$1@solani.org> <vc7mjb$9ptr$1@solani.org>
 <vcelid$b5f1$3@solani.org> <vihokt$lrea$1@solani.org>
 <vn0gpc$dlcd$1@solani.org> <vn0gqt$dlcd$2@solani.org>
 <vn3eu1$fmq0$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 25 Jan 2025 19:44:45 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="514880"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:128.0) Gecko/20100101
 Firefox/128.0 SeaMonkey/2.53.20
Cancel-Lock: sha1:053Inv3q4fSKkGIMKfrw8f7hYG4=
X-User-ID: eJwFwQkBwDAIA0BLhCcrcigF/xJ2F0awP2fQY2P3wW4JfOq1MWNFPHoI1yW0WufhHE30mUGMZG7j8lo9yx9bChWy
In-Reply-To: <vn3eu1$fmq0$1@solani.org>
Bytes: 3857
Lines: 89


I made a little experiment introducing both
left spilling and right spilling into a DCG
translator, which previously had neither:

/* Dogelog Player 1.3.0 */
?- listing(p/2).
p([a|A], B) :-
    !,
    A = [b|B].

Now my benchmark suite DCG calculator runs 25% faster!

Mild Shock schrieb:
> Hi,
> 
> Lets say there are at least two unification
> spilling rewriting techniques in a Prolog system
> that would eliminate a (=)/2 call:
> 
> /* Left Spilling into the Head */
> p(V, Q) :- V = T, ...         ~~>            p(T, Q) :- ...
> 
> /* Right Spilling into a Goal */
> ..., V = T, p(V, Q), ...      ~~>            ..., p(T, Q), ...
> 
> Maybe the head movement and the indexing benefit
> in SWI-Prolog was discovered because of DCG translation
> and not to eliminate mode directed compilation.
> 
> Take this DCG rule:
> 
> p --> [a], !, [b].
> 
> I find that SWI-Prolog does left spilling:
> 
> /* SWI-Prolog 9.3.19 */
> ?- listing(p/2).
> p([a|A], B) :-
>      !,
>      C=A,
>      C=[b|B].
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> Would need more testing but the
>> present example is immune:
>>
>> /* SWI-Prolog 9.3.19 */
>> ?- X = f(g(1),h(2)), time((between(1,1000000,_), test1(X, Y), fail; 
>> true)).
>> % 1,999,998 inferences, 0.094 CPU in 0.100 seconds (93% CPU, 21333312 
>> Lips)
>>
>> ?- X = f(g(1),h(2)), time((between(1,1000000,_), test2(X, Y), fail; 
>> true)).
>> % 1,999,998 inferences, 0.094 CPU in 0.100 seconds (93% CPU, 21333312 
>> Lips)
>>
>> ?- Y = j(1,2), time((between(1,1000000,_), test1(X, Y), fail; true)).
>> % 1,999,998 inferences, 0.109 CPU in 0.100 seconds (109% CPU, 18285696 
>> Lips)
>>
>> ?- Y = j(1,2), time((between(1,1000000,_), test2(X, Y), fail; true)).
>> % 1,999,998 inferences, 0.094 CPU in 0.102 seconds (92% CPU, 21333312 
>> Lips)
>>
>> Not all Prolog systems are that lucky:
>>
>> /* Scryer Prolog 0.9.4-286 */
>> ?- X = f(g(1),h(2)), time((between(1,1000000,_), test1(X, Y), fail; 
>> true)).
>>     % CPU time: 1.163s, 11_000_108 inferences
>>
>> ?- X = f(g(1),h(2)), time((between(1,1000000,_), test2(X, Y), fail; 
>> true)).
>>     % CPU time: 1.248s, 11_000_131 inferences
>>
>> ?- Y = j(1,2), time((between(1,1000000,_), test1(X, Y), fail; true)).
>>     % CPU time: 0.979s, 11_000_131 inferences
>>
>> ?- Y = j(1,2), time((between(1,1000000,_), test2(X, Y), fail; true)).
>>     % CPU time: 1.338s, 11_000_131 inferences
>>
>> Bye
>