Making a predicate work in all directions idiomatically

[bakaq]

One thing that is often really useful to have in a Prolog program is to make a predicate work in all directions. Making a predicate monotonic is quite easy, but usually that means it will "not work" in some modes, and by this I mean non-termination or instantiation errors, which while not actually wrong aren't really a useful answer. This problem is a great part of why I started making the constraint predicates in constrained.pl. The predicate I will be using here is an real use case I stumbled into of relating a list to a string representation of it's length.

:- use_module(library(lists)).
:- use_module('constrained.pl').

% This doesn't terminate if List is not instantiated, because length/2 will
% generate and test lists of all lengths, even after the result was found.
%
% ?- length_chars_1(Ls, Len).
%    Ls = [], Len = "0"
% ;  Ls = [_A], Len = "1"
% ;  Ls = [_A,_B], Len = "2"
% ;  ... . % non-termination, expected because it generates all answers
% ?- length_chars_1([1,2,3], Len).
%    Len = "3". 
% ?- length_chars_1(Ls, "3").
%    Ls = [_A,_B,_C]
% ;  % non-termination, unwanted
length_chars_1(List, LengthChars) :-
    length(List, Length),
    number_chars(Length, LengthChars).

% Changing the order makes the predicate work if List isn't instantiated, but
% now it throws an instantiation error if LengthChars isn't instantiated,
% because when we reach number_chars/2, neither of it's arguments are
% instantiated, and it doesn't work in this mode.
%
% ?- length_chars_2(Ls, Len).
%    error(instantiation_error,number_chars/2). % unwanted
% ?- length_chars_2([1,2,3], Len).
%    error(instantiation_error,number_chars/2). % unwanted
% ?- length_chars_2(Ls, "3").
%    Ls = [_A,_B,_C]. % now terminates
length_chars_2(List, LengthChars) :-
    number_chars(Length, LengthChars),
    length(List, Length).

% Putting a cut makes this predicate work correctly in both directions, but
% then it stops being monotonic, and it still needs to generate and test until
% it finds a correct solution.
%
% ?- length_chars_cut(Ls, Len).
%    Ls = [], Len = "0". % misses answers, plain wrong!!!
% ?- length_chars_cut([1,2,3], Len).
%    Len = "3".
% ?- length_chars_cut(Ls, "3").
%    Ls = [_A,_B,_C].
length_chars_cut(List, LengthChars) :-
    length(List, Length),
    number_chars(Length, LengthChars),
    !.

% Using var/1, nonvar/1 and (->)/2 to change the order when necessary works in
% all ways! The caveat is that those 3 predicates are all non-monotonic, so you
% have to be careful. Having those "low level" predicates in what should be
% high level code seems wrong to me, and it's also quite long and verbose. This
% probably indicates that there should be a higher level construct for things
% like this.
%
% ?- length_chars_var(Ls, Len).
%    Ls = [], Len = "0"
% ;  Ls = [_A], Len = "1"
% ;  Ls = [_A,_B], Len = "2"
% ;  ... . % non-termination, expected because it generates all answers
% ?- length_chars_var([1,2,3], Len).
%    Len = "3".
% ?- length_chars_var(Ls, "3").
%    Ls = [_A,_B,_C].
length_chars_var(List, LengthChars) :-
    % Very verbose and fragile code.
    (   (
            var(List), var(LengthChars)
        ;   nonvar(List)
        ) ->
        length(List, Length),
        number_chars(Length, LengthChars)
    ;   number_chars(Length, LengthChars),
        length(List, Length)
    ).

% Using length_c/2 from constrained.pl makes this work both ways, but it still
% throws an instantiation error in the general case. This can be enough for a
% lot of cases, but not having the general case is unfortunate. I think that if
% I can implement number_chars_c/2 maybe this could work in all cases.
%
% ?- length_chars_c(Ls, Len).
%    error(instantiation_error,number_chars/2). % unwanted, but at least not wrong
% ?- length_chars_c([1,2,3], Len).
%    Len = "3". 
% ?- length_chars_c(Ls, "3").
%    Ls = [_A,_B,_C].
length_chars_c(List, LengthChars) :-
    length_c(List, Length),
    number_chars(Length, LengthChars).

Making constraints like length_c/2 helps a lot to make code look more idiomatic and logical, but is not as general as the var/1 and friends approach because you will probably not have all constraints that you need implemented, and implementing a constraint is in general much harder, low level and error prone than using var/1 and (->)/2.

I feel that the var/1 approach is a bit mechanical and can be implemented in a predicate using term_expansion/2 or even just a normal predicate. I will call this hypothetical predicate permute_predicates here, not sure about the arity. The problem with this is that it probably wouldn't skip the hardest part of ensuring that the instantiation conditions of the arguments make sense with the permutations.

An idea is to give a description of valid modes of all the predicates that are used in a section, and so permute_predicates could generate an ideal (->)/2 chain so that the resulting section is the most general possible. A problem with that is that I think it would be ambiguous what the "best" general configuration would be in many cases, and that not every predicate's behavior can be easily described with just modes (for example, a predicate that gives a differently instantiated second argument based on the value (not instantiation) of the first argument). On the positive side, it seems that it's planned for Scryer to have a mode annotation system for predicates in the future, and so permute_predicates could maybe integrate with that.

Have I missed an obvious way to do this currently?

[UWN]

Making a predicate monotonic is quite easy

Not in your example.

number_chars/2 is not a very suitable built-in to make it work in all directions, after all it is non-relational in itself. And this is also a frequent challenge with parsers because this is not a one-to-one relation.

?- number_chars(1,Chs).
   Chs = "1".
?- number_chars(1,[Ch]).
   Ch = '1'.
?- number_chars(1,[S,Ch]).
   false.
?- number_chars(1," 1").
   true. % how can that be

The last query shows that there is another textual representation for the number one, in fact there are infinitely many. On the other hand the query above which asks about two-character representations for one is denied. So number_chars/2 is not a relation in itself which makes reasoning about it more fragile since also some of your predicates inherit that property. In some sense it is two relations bolted together. In one, there is only a canonical textual representation, and in the other all valid textual representations are present. This second version is only used if the second argument is ground, thus the text is present completely.

?- length_chars_1([],Chs), Chs = " 0".
   false.
?- length_chars_1([],"  0").
   true.

number_canonicchars(N, Chs) :-
   number_chars(N, Chs),
   number_chars(N, ChsC),
   Chs = ChsC.

And then there are cases of unexpected non-termination

?- length_chars_var(Es,"2").
   Es = [_A,_B].
?- Es = [_|_], length_chars_var(Es,"2").
   Es = [_A,_B]
;  loops.

This is particularly problematic as we commonly assume that if a query does terminate, also every instance of it will terminate.

People have searched for better ways of expressing such relations, and this is still an open area. Think of just queries consisting of a sequence of append/3-goals. A significant subset of it is the word problem over free monoids solved by Makanin in 1977. There have been several attempts to implement these, but none have gotten beyond the borders of research papers.

[bakaq]

I knew that number_chars/2 was not actually monotonic, but didn't know why. Thanks for the examples.

Also, is the number_canonicchars/2 predicate you defined monotonic? I can't see any counter example for monotonicity.

[bakaq]

And then there are cases of unexpected non-termination

Yeah, this isn't ideal, but it seems that it's also impossible to solve this one with just predicate reordering. Maybe it's possible with constraints? Maybe not even custom ones, just something like freeze/2. But that would probably just solve this case of non-termination. Making this predicate terminate for all arguments is possibly really non trivial.

My point is making a predicate as general as possible without making it non-monotonic. My predicate above is not actually monotonic as you showed, but if it was then length_chars_var/2 is the best generalization I can think without making it wrong or implementing more constraints. The fact that it doesn't terminate for some arguments is unfortunate, but at least not wrong. It's way better than length_chars_1/2 that can't even do the 2 "easy" cases.

[UWN]

Also, is the number_canonicchars/2 predicate you defined monotonic?

Syntax errors behave a bit odd. Think of

?- number_canonicchars(1,[a|L]).
   false.
?- number_chars(1,[a|L]).
   false.

In both cases there is no substitution for L that does not result in a syntax error, still this definition fails silently. But apart from that I think it is OK. Maybe a nicer name.

[UWN]

What exactly is going on ...

The second goal number_chars(N, ChsC) has ChsC as an uninstantiated variable, and thus the canonical representation of N is used. That is, only one such representation is used. number_chars/2 is two pure relations bolted together.

Would it be feasible to rename number_chars/2 and replace its body with the definition of ...

Oh please, number_chars/2 has been the theater of so many battles. Changing it again just makes things worse. It is defined like that.

In stead, a better fitting name than number_canonicchars/2 would be interesting.

[triska]

Could you please consider adding Scryer Prolog to the table with number_chars/2 test cases? As far as I know, Scryer correctly handles all cases and can be used as a reference implementation for other implementors.

[infogulch]

Changing it again just makes things worse.

Fair enough. I guessed you'd reference the spec.

If we're making a new predicate anyways, could we change it to disallow spaces to make it (more?) monotonic?

[UWN]

Could you please consider adding Scryer Prolog to the table

This table represents exactiter the decisions for Cor.2.

[bakaq]

In stead, a better fitting name than number_canonicchars/2 would be interesting.

I propose number_canonchars/2. It's a bit shorter, has the same meaning, doesn't have the weird cc in the name, and still follows the "arg1_arg2" convention that I think is useful in relations.