Performance potential of SSU => vs :-

Help!
1

Hello,

I am reviewing my code and notice many deterministic predicates that could be made into SSU. Currently, various unify in the head and have cuts in the body.

I am curious – given that SSU is now integrated into the VM, could there be performance advantages in revising many predicates to become SSU based.

One aspect I notice is that many are single clause predicates, some have two or more clauses which usually refer to different cases, and various have no guards – they assume correct bindings – assuming that checks have been made – hence, i will likely not add guards (such as integer(X) to them.

Also, some have ground as output – e.g. x_sum([],0).

which would need to become: x_sum([], S) => S=0.

Any thoughts are much appreciated,

Dan

p.s. i do see the value in using SSU to indicate the design intent of a predicate that it is deterministic, which, otherwise, is more implicitly captured.

1 Like
3

I changed ~2000 lines to use => and there’s no obvious performance change; possibly a bit slower (but within “epsilon”, as they say).

It was a bit more work than I had expected; the change isn’t entirely mechanical, as it’s easy to miss situations like p([], X, X). needing to be changed to p([], X0, X) => X0 = X.

In general, I think it makes if-then-else code a bit cleaner (and more compact); it makes clauses that produce an output a bit longer – sometimes it makes the logic a bit more obvious and sometimes a bit less obvious. And it allows me to get rid of “catch-all” clauses that are there just for catching logic errors where I haven’t specified all the possibilities for the arguments.
I wish there were a variant of => that has not only SSU but also raises an error if the r.h.s. fails. (For this, I still use pack(rdet).)

2 Likes
4

Thank you Peter.

So, overall, do you think the additional construct added clarity?

Do you think that => could be transformed back to :- with term or goal expansion, in case of need (i.e run the code with a different prolog)?

Dan

5

Note det/1, $/0 (and $/1 in the current git version). We could opt for a $=> as well. I’m not sure about using the $ sign for this. Neither about turning det into an operator as dynamic, etc. or maybe using a different syntax. Note that these determinism tests are a bit different from the docs: where in the docs det means “succeeds once without choicepoint if the output variables are unbound”, the declaration checks success, regardless of the instantiation. Unlike the wrapper based approach though, these checks comes at practically zero runtime overhead.

No. Well, yes but than at a giant performance price as you need to remove all unification from the head and use ISO subsumes_term/2 before the actual unification. ECLiPSe seems to have ?- to define SSU for the head matching, you can fairly easy rewrite for this system and maybe a few others.

6

Sometimes: you could transform p(X), q(X) => r(X) into p(X) :- q(X), !, r(X), but the semantics are subtly different and that might or might not matter. For example, p(X), X=a => r(X) will error if X is a variable but p(X) :- X=a, !, r(X) will succeed; but if X can never be a variable, then both forms will do the same thing.

So, I wouldn’t want to have a term-expansion that converts => to :- ... ! because each clauses would need to be looked at individually, to validate its assumptions about what’s instantiated.

7

Thanks.

I guess, it would be good to have an expansion that does capture the (subtle) semantics, in order to ensure interoperability with other prolog systems not supporting SSU directly.

Edit:

I am a bit reluctant to revise my code and thereby reduce interoperability – while I don’t foresee switching to a different prolog, having the option seems important in the longer term – even, just for performance benchmark purposes.

Dan

8

I’m still working on my changes and don’t have an answer for you.

I don’t see any reason for changing a single-clause predicate :- to =>:

p(X, Y) :- q(a, X, Y).

vs

p(X, Y) => q(a, X, Y).

Here are some real-world examples … which is clearer?

A predicate used by convlist/3:

is_module_sym_type(Sym-Type, Sym-Type) :-
     memberchk(module_type(_), Type).

vs

is_module_sym_type(Sym-Type, SymType) =>
    SymType = Sym-Type,
    memberchk(module_type(_), Type).

Making an output arg explicit and replacing :- ! with =>:

%! remove_candidate(+Candidate:atom, +Seq:list(atom), -SeqOut:list(atom)) is det.
remove_candidate(Candidate, [Candidate|Seq], Seq) :- !.
remove_candidate(_, Seq, Seq).

vs

%! remove_candidate(+Candidate:atom, +Seq:list(atom), -SeqOut:list(atom)) is det.
remove_candidate(Candidate, [Candidate|Seq], SeqOut) => SeqOut = Seq.
remove_candidate(_, Seq, SeqOut) => SeqOut = Seq.

Replacing an exhaustive listing of patterns and making output args explicit:

add_up_dots([], Path, Path).
add_up_dots([_|Dots], Path, DotsPath) :-
     add_up_dots(Dots, ['..'|Path], DotsPath).

vs

add_up_dots([], Path, DotsPath) => DotsPath = Path.
add_up_dots([_|Dots], Path, DotsPath) =>
    add_up_dots(Dots, ['..'|Path], DotsPath).

Replacing an if-then-else:

simple_path_module_fqn(Path, ModuleFqn) :-
    (   var(ModuleFqn)
    ->  split_path_to_module_parts(Path, ModuleFqnParts),
        join_fqn(ModuleFqnParts, ModuleFqn)
    ;   split_module_atom(ModuleFqn, ModuleFqnParts),
        join_path(ModuleFqnParts, Path)
    ).

vs

simple_path_module_fqn(Path, ModuleFqn), var(ModuleFqn) =>
    split_path_to_module_parts(Path, ModuleFqnParts),
    join_fqn(ModuleFqnParts, ModuleFqn).
simple_path_module_fqn(Path, ModuleFqn) =>
    split_module_atom(ModuleFqn, ModuleFqnParts),
    join_path(ModuleFqnParts, Path).

Replacing an if-then-else with a secondary predicate (this is a bit subtle: include(p, Seqs, []) succeeds if p(X) fails for all X in Seqs):

mro_merge_candidate(Seqs, Candidate) :-
    Seqs = [[Candidate0|_]|SeqsTail],
    (   include(in_tail(Candidate0), Seqs, [])
    ->  Candidate = Candidate0
    ;   mro_merge_candidate(SeqsTail, Candidate)
    ).

vs

mro_merge_candidate(Seqs, Candidate),
        Seqs = [[Candidate0|_]|SeqsTail] =>
    mro_merge_candidate2(Seqs, Candidate0, SeqsTail, Candidate).

mro_merge_candidate2(Seqs, Candidate0, _SeqsTail, Candidate),
        include(in_tail(Candidate0), Seqs, []),
    Candidate = Candidate0.
mro_merge_candidate2(_Seqs, _Candidate0, SeqsTail, Candidate) =>
    mro_merge_candidate(SeqsTail, Candidate).
9

Thank you for the examples:

I think, part of the clarity comes from the use of => – i.e. the expectation that input arguments must be instantiated and that overall the clause must be deterministic. That’s added information not (necessarily) available in the :- versions.

(didnt notice the dash, at first)

10

is this correct?

11

Sorry, something went wrong with my copy&paste (and I’m a terrible proof-reader). Anyway, there are 3 possibilities (hopefully copy&pasted correctly this time):

mro_merge_candidate(Seqs, Candidate) :-
    Seqs = [[Candidate0|_]|SeqsTail],
    (   include(in_tail(Candidate0), Seqs, [])
    ->  Candidate = Candidate0
    ;   mro_merge_candidate(SeqsTail, Candidate)
    ).

vs

mro_merge_candidate(Seqs, Candidate),
        Seqs = [[Candidate0|_]|SeqsTail] =>
    (   include(in_tail(Candidate0), Seqs, [])
    ->  Candidate = Candidate0
    ;   mro_merge_candidate(SeqsTail, Candidate)
    ).

vs

mro_merge_candidate(Seqs, Candidate),
        Seqs = [[Candidate0|_]|SeqsTail] =>
    mro_merge_candidate2(Seqs, Candidate0, SeqsTail, Candidate).

mro_merge_candidate2(Seqs, Candidate0, _SeqsTail, Candidate),
        include(in_tail(Candidate0), Seqs, []) =>
    Candidate = Candidate0.
mro_merge_candidate2(_Seqs, _Candidate0, SeqsTail, Candidate) =>
    mro_merge_candidate(SeqsTail, Candidate).
13

Is there a way to find the predicates that have det/1 declarations, so that library(check) can be enhanced to verify that det/1 declarations are for existing predicates? (to catch mistakes when mis-counting # of args or when modifying a predicate to take one more arg)

15

Here’s an edge case I’ve run up against. This predicate is deterministic if the 2nd argument is a variable:

%! b64_to_utf8_to_atom(+BytesBase64, -Atom) is det.
b64_to_utf8_to_atom(BytesBase64, Atom) :-
    base64_ascii(Utf8, BytesBase64),
    atom_codes(Utf8, Utf8codes),
    phrase(utf8_codes(Codes), Utf8codes),
    atom_codes(Atom, Codes).

However, if it’s called in a “checking” environment (e.g. b64_to_utf8_to_atom('ZmlsZQ==',package),then it’s semidet; therefore, I can’t use the det/1 directive for it.

Of course, I could work around this by b64_to_utf8_to_atom('ZmlsZQ==',MaybePackage),MaybePackage=package, but that defeats one of the nice things about Prolog.

A variant of this: it might be nice to have a semidet/1 directive that verifies there are no choice points if the predicate succeeds, but also allows failure.

16

Note that in the current (git) HEAD, a unification against a head argument used as a guard is moved into the head. Also note that this changes the semantics of =. But … guards are supposed to be tests that do not change any bindings.

As to be expected, there is a predicate_property/2 called det. I only forgot to add it to the manual. Added.

Possibly that will happen. Note that the two are normally different though. A “det” predicate may indeed still fail on a non-unifying output argument. A “semidet” predicate may fail even if the output arguments are unbound. We could of course (as more common), describe this using mode lines, e.g.

b64_to_utf8_to_atom(+BytesBase64, -Atom) is det.
b64_to_utf8_to_atom(+BytesBase64, +Atom) is semidet.

Although this is nice, this is hard to deal with efficiently at runtime and I usually consider this too verbose for documentation as well. Assuming steadfastness, the second mode is implied by the first.

It doesn’t. The body is not considered. SWI-Prolog’s current indexing aims mostly at predicates with large numbers of (fairly uniform) clauses. Clever indexing for small clause sets is still on the radar, but never materialized.

18

Well, p1(X,Y), X = Y => true. should probably be considered misusing Picat. It surely is misusing the intentions of SWI-Prolog’s =>.

I would get worried if two single sided unifications cannot be swapped. That would (for example) change the head semantics if we swap two arguments. We know that tests like nonvar/1 cannot be moved. They are non-logical operations.

20

Could you explain / illustrate what this means

21

is ?- an operator typically available across Prologs

24

Thank you.

I probably (naively) thought that to achieve steadifastness you don’t want structural unifications in the head, and let it occur after the guard.

Although, perhaps, this is an “internal” rewrite at VM level, and is done for indexing rather than to support unification …

Dan

27

thank you.

I find the memberchk comparison very interesting, but also concerning.

It is not intuitive that both versions behave differently – perhaps sharing variables in the head should be forbidden in SSU …

29

I am starting to wonder about the added value of SSU —

One of prolog’s key strength is its simplicity, that it essentially works with one operator :-

It seems that what SSU adds can equally be obtained by a coding discipline (as outlined by O’Keefe’s max example) and, perhaps augmented unification checks, like in you libraries. All this makes the semantics unequivocal.

I will need to think whether its worth at this stage to revise deterministic code with SSU – currently, i am using rdet to check expected behavior – and could perhaps replace it with the new det directive – to gain performance.

31

Is there a way to check that the det/1 directives match existing predicates?

For example, I want to catch this typo:

:- det(p/2).
p(A) :- format('qqsv: ~q~n', [A]).

I can check whether p/2 has been defined as det; but there doesn’t seem to be a way to find the det/1 directives and verify that each matches a predicate definition.