# CLP(FD) labeling on possibly infinite domains

As a follow-up to this SO question, I implemented, for my Prolog-based language Brachylog, my own labeling predicate brachylog_equals/2 which is not guaranteed to terminate but works for infinite domains:

brachylog_equals(Z,Z) :-
brachylog_equals_('init',10,Z).

brachylog_equals_(I,J,'integer':Z) :-
fd_inf(Z,'inf'),
fd_sup(Z,'sup')
-> (
(
I = 'init'
;
I \= 'init',
abs(Z) #>= I
),
abs(Z) #< J,
label([Z])
;
I2 is J,
J2 is J*10,
brachylog_equals_(I2,J2,'integer':Z)
)
;
fd_inf(Z,'inf')
-> (
(
I = 'init'
;
I \= 'init',
Z #=< -I
),
Z #> -J,
label([Z])
;
I2 is J,
J2 is J*10,
brachylog_equals_(I2,J2,'integer':Z)
)
;
fd_sup(Z,'sup')
-> (
(
I = 'init'
;
I \= 'init',
Z #>= I
),
Z #< J,
label([Z])
;
I2 is J,
J2 is J*10,
brachylog_equals_(I2,J2,'integer':Z)
)
;
label([Z]).


• This predicate is supposed to be used in automatically generated Prolog code, therefore its name does not describe its function but rather follows a convention.
• 'integer':Z rather than simply Z is simply here to comply with the rest of the project (it is used to check easily the type of arguments in some other predicates)

Here are my worries:

• Is this the most idiomatic solution? (i.e. impose a finite bound on the variable where it has an infinite bound, and increase it recursively if backtracking occurs?)
• Is this actually correct in all cases? (From what I tested it is, but I'm wondering if I missed some odd domains where it would break)
• Is this computationally efficient?

Of course comments on code style (which I know does not respect usual conventions) or code simplication are also welcome.

• Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Vogel612 Jun 2 '16 at 12:12
• The problem is mainly that the CLP(FD) providers are possibly too uninteressted and thus too lazy to provide fair enumeration. See also stackoverflow.com/a/37952138/502187 – Mostowski Collapse Jun 21 '16 at 18:41

Generally, a very good guidline when coding in Prolog is:

Everything that can be expressed by pattern matching should be expressed by pattern matching.

By this I mean that it is good practice to distinguish different cases symbolically in clause heads instead of using if-then-elses within bodies.

Unfortunately, this guideline is hard to apply in this case because, alas, fd_inf/2 and fd_sup/2 use a so-called defaulty representation for their arguments. Basically, there are two fundamentally different cases to distinguish:

• infinities (inf and sup)
• concrete integers.

A clean representation would for example be to use:

• inf and sup for infinities
• n(N) to denote the integer N

This would help a lot in this example to symbolically distinguish the cases that must be handled, and one day we may have more such predicates. As it stands, we must deal with the defaulty representation, which always requires the use of impure constructs (!/0, if-then-else etc.) to distinguish the cases.

Nevertheless, we can at least approximate the guideline by putting more decisions into clause heads. This saves a few variables and lets us test the cases more easily in isolation.

Consider for example:

unsafe_indomain(X) :-
fd_inf(X, Inf),
fd_sup(X, Sup),
unsafe_indomain_(Inf, Sup, X).

unsafe_indomain_(inf, Sup, X) :- !, % greetings from defaultyness
infinite_down(Sup, X).
unsafe_indomain_(Low, Sup, X) :-
unsafe_up_(Sup, Low, X).

infinite_down(sup, X) :- !,  % greetings from defaultyness
(   X = 0
;   positive_integer(N),
(   X #= N ; X #= -N )
).
infinite_down(Up, X ) :-
(   between(0, Up, X)
;   length([_|_], N),
X #= -N
).

unsafe_up_(sup, Low, X) :- !,   % greetings from defaultyness
(   between(Low, 0, X)
;   positive_integer(X)
).
unsafe_up_(Up, Low, X) :- between(Low, Up, X).

positive_integer(N) :- length([_|_], N).


If fd_inf/2 and fd_sup/2 were using a clean representation, no !/0 would be necessary to distinguish the different cases, and we could use the above predicates in more directions! Think about how convenient and elegant this would be. In your own programs, always aim for clean representations, so that you can distinguish different cases by pattern matching alone!

Note that I am conciously avoiding the SWI-specific extension of using infinite in the second argument of between/3, since this feature destroys some important desirable properties of this predicate. You can use patterns like length(_, N) to produce arbitrarily large integers on backtracking.

Here are a few example queries:

?- unsafe_indomain(X).
X = 0 ;
X = 1 ;
X = -1 ;
X = 2 .

?- X in -1..2, unsafe_indomain(X).
X = -1 ;
X = 0 ;
X = 1 ;
X = 2.

?- X in 5..sup, unsafe_indomain(X).
X = 5 ;
X = 6 ;
X = 7 .

?- X in inf..1, unsafe_indomain(X).
X = 0 ;
X = 1 ;
X = -1 ;
X = -2 ;
X = -3 .


I am calling this "unsafe" indomain because there are cases where it may not terminate.

The more you work with unclean representations, the more you will benefit from first converting them to cleaner ones. This keeps the most important predicates of your programs pure and usable in all directions, and the defaulty representations are confined to a small interface layer to interact with users or libraries that use them.

For example:

unsafe_indomain(X) :-
fd_inf(X, Inf0),
fd_sup(X, Sup0),
maplist(defaulty_clean, [Inf0,Sup0], [Inf,Sup]),
unsafe_indomain_(Inf, Sup, X).

defaulty_clean(inf, inf) :- !.
defaulty_clean(sup, sup) :- !.
defaulty_clean(N, n(N)).

unsafe_indomain_(inf, Sup, X) :-
infinite_down(Sup, X).
unsafe_indomain_(n(Low), Sup, X) :-
unsafe_up_(Sup, Low, X).

infinite_down(sup, X) :-
(   X = 0
;   positive_integer(N),
(   X #= N ; X #= -N )
).
infinite_down(n(Up), X ) :-
(   between(0, Up, X)
;   length([_|_], N),
X #= -N
).

unsafe_up_(sup, Low, X) :-
(   between(Low, 0, X)
;   positive_integer(X)
).
unsafe_up_(n(Up), Low, X) :- between(Low, Up, X).


Note how impure constructs like !/0 are now only needed in the initial conversion step. The rest is quite pure and general.

Before discussing correctness, efficiency and alternative approaches, I first have three smaller suggestions to simplify the predicate a bit:

• Its seems I2 is nowhere really needed, you can always simply use J instead.

• for J2, I would stick to CLP(FD) constraints like: J2 #= J*10.

• instead of (\=)/2, I recommend to use dif/2.

These changes make the code a bit easier to read and more uniform, and put us into a better position to discuss the remaining issues.

• As far is I can tell,I2 is J, so instead of writing I2 is J, you can simply use J itself. – mat Jun 2 '16 at 11:44
• Right nevermind, I'm stupid! – Fatalize Jun 2 '16 at 11:45