Re: variant_term/2 is faster than variant/1 (Was: Request for comments, Novacore the sequel to ISO modules)

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

>