Path: ...!fu-berlin.de!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: variant_term/2 is faster than variant/1 (Was: Request for
 comments, Novacore the sequel to ISO modules)
Date: Sun, 13 Oct 2024 00:54:18 +0200
Message-ID: <veeump$b5p9$1@solani.org>
References: <db8a6771-3e54-485b-b391-310658dd6f52n@googlegroups.com>
 <aa869ef6-7f90-405b-a84a-2c11ac7979a3n@googlegroups.com>
 <vcukob$n3q2$1@solani.org> <veekkd$b9uf$1@solani.org>
 <veeq19$bcbb$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 12 Oct 2024 22:54:17 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="366377"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.19
Cancel-Lock: sha1:Q2PZr0zZLxrq9gUjOQks1WuP+Wo=
In-Reply-To: <veeq19$bcbb$1@solani.org>
X-User-ID: eJwFwQcBwEAIBDBL8HAMOWX5l9AEYmztajDF4arrzgg5spuRKRca1NjXV+bl8DmR9uIJ4i+0nj3y2Cls/mxjFeM=
Bytes: 5033
Lines: 158

Ok, I have to redo my nok/2 test for Scryer Prolog,
since Scryer Prolog doesn't work as per ISO spec:

/* Scryer Prolog Playground */
?- builtins:variant(f(A,B), f(C,D)).
    A = A, B = A, C = A, D = A.

It should not leave some bindings. At least this is
what other Prolog systems do:

/* Trealla Prolog */
?- variant(f(A,B), f(C,D)).
    true.

/* SWI-Prolog */
?- variant(f(A,B), f(C,D)).
true.

The performance tests are not affected, but I guess
it is better to test nok/2 like this:

nok2(L, R) :- length(L, 6), length(R, 6),
      enum_list(_, L), enum_list(_, R),
      boole(variant_term(L, R), A), boole(builtins:variant(L, R), B),
      A \== B.

Besides the binding glitch, it seems to be ok:

?- nok2(L, R).
    false.

Mild Shock schrieb:
> So what can we do with this insight. Here is
> a little performance of a new distinct/1,
> that is eager und non-variant enumerating:
> 
> /* eagerness */
> ?- distinct(repeat), !.
> true.
> 
> d(f(A,A)).
> d(f(a,a)).
> d(f(B,B)).
> 
> /* non-variant enumerating */
> ?- distinct(d(X)).
> X = f(_70321, _70321);
> X = f(a, a);
> fail.
> 
> It is implemented with variant_term/2, since the
> remembered list of archived witnesses so far,
> is anyway copies of terms. So variant_term/2
> 
> is appropriate, we never have to check
> two terms that have variables in common.
> 
> Cool!
> 
> Mild Shock schrieb:
>> How much faster is it?
>>
>> Here some test harness:
>>
>> test :- length(L, 6), length(R, 6),
>>     enum_list(_, L), enum_list(_, R),
>>     variant(L, R), fail; true.
>>
>> test2 :- length(L, 6), length(R, 6),
>>     enum_list(_, L), enum_list(_, R),
>>     variant_term(L, R), fail; true.
>>
>> Here some results:
>>
>> - SWI-Prolog 9.3.11:
>>
>> ?- time(test).
>> % 2,126,498 inferences, 0.734 CPU in 0.752 seconds
>> (98% CPU, 2895657 Lips)
>> true.
>>
>> ?- time(test2).
>> % 2,159,795 inferences, 0.234 CPU in 0.236 seconds
>> (99% CPU, 9215125 Lips)
>> true.
>>
>> - Trealla Prolog 2.57.16:
>>
>> ?- time(test).
>> % Time elapsed 3.128s, 14827949 Inferences, 4.741 MLips
>>     true.
>>
>> ?- time(test2).
>> % Time elapsed 1.079s, 7775516 Inferences, 7.206 MLips
>>     true.
>>
>> - Scryer Prolog :
>>
>> ?- time(test3).
>>     % CPU time: 5.653s, 5_192_831 inferences
>>     true.
>>
>> ?- time(test2).
>>     % CPU time: 1.544s, 6_116_163 inferences
>>     true.
>>
>> Note: test3 is like test, only it uses builtins:variant/2.
>>
>> Mild Shock schrieb:
>>> The ISO core standard probably set the
>>> stage for a couple of performance sins.
>>> In 7.1.6.1 Variants of a term we find
>>>
>>> these test cases:
>>>
>>> - f(A, B, A) is a variant of f(X, Y, X).
>>> - g(A, B) is a variant of g(_, _).
>>> - P+Q is a variant of P+Q.
>>>
>>> What is doubious here, is the last test
>>> case with P+Q. Do we need to test terms
>>> that have common variables?
>>>
>>> Lets assume we have situations where we
>>> don't need variant working with common
>>> variables in the two argument terms, what
>>>
>>> about then using this bootstrapping:
>>>
>>> variant_term(X, Y) :-
>>>     subsumes_term(X, Y),
>>>     subsumes_term(Y, X).
>>>
>>> Here some testing, does it work ok? Take this code:
>>>
>>> enum_arg(_, 1).
>>> enum_arg(_, _).
>>> enum_arg(X, X).
>>>
>>> enum_list(_, []).
>>> enum_list(X, [H|T]) :- enum_arg(X, H), enum_list(X, T).
>>>
>>> boole(G, 1) :- G, !.
>>> boole(_, 0).
>>>
>>> nok(L, R) :- length(L, 6), length(R, 6),
>>>       enum_list(_, L), enum_list(_, R),
>>>       boole(variant(L, R), A), boole(variant_term(L, R), B),
>>>       A \== B.
>>>
>>> Seems to work fine:
>>>
>>> ?- nok(L, R).
>>> false.
>>>
>>>
>>
>