List of integers and infinite loop in Prolog CLPFD

Question

Suppose I want to represent integers like so: integer:Sign:[FirstDigit,SecondDigit,...]. For instance, 42 would be represented as integer:positive:[4,2].

I need a predicate that generates the value of the integer based on this representation and vice versa.

Here is what I came up with:

integer_value_('integer':Sign:[H],E) :-
    H in 0..9,
    (
        Sign = 'positive',
        E #= H
        ;
        Sign = 'negative',
        E #= -H
    ).
integer_value_('integer':Sign:[H,I|T],E) :-
    H in 0..9,
    length([I|T],L),
    (
        Sign = 'positive',
        E #= F + H * 10^L
        ;
        Sign = 'negative',
        E #= F - H * 10^L
    ),
    integer_value_('integer':Sign:[I|T],F).

This works as expected. However, it has the unfortunate property of accepting things like integer:positive:[0,1], that is, leading zeroes at the beginning of the list. This is especially problematic when I enumerate all possible integers using integer_value_(I,J), label([J]).: the ones with leading zeroes also show up.

I then attempted to correct this by using integer_value_ only for all but the first digit, and using integer_value for the first one (keeping in mind that we need to accomodate for 0 being represented with a list containing only 0):

integer_value('integer':Sign:[H],E) :-
    abs(E) #< 10,
    abs(E) #> -1,
    integer_value_('integer':Sign:[H],E).
integer_value('integer':Sign:[H,I|T],E) :-
    H in 1..9,
    length([I|T],L),
    (
        Sign = 'positive',
        E #= F + H * 10^L
        ;
        Sign = 'negative',
        E #= F - H * 10^L
    ),
    integer_value_('integer':Sign:[I|T],F).

However now it does not behave properly. For example, integer_value(I,-19). returns I = integer:negative:[1, 9], but if we ask for another answer Prolog goes into an infinite loop for reasons I don't understand (it should say false, or already know there are no other answers).

This problem does not occur with the "opposite" query integer_value(integer:negative:[1,9],Z). which returns Z = 19 and then false, nor does it occur when both arguments are Variables (it enumerates numbers properly, with no leading zeroes), which is surprising to me.

Any idea what that infinite loop occurs, and if there's an easy way to fix it?

Chancre

+1 for a very interesting and appropriate use case of CLP(FD) constraints! I have one small comment regarding the single quotes: You can omit the ' for all atoms that do not need such quotes, like positive, negative, integer etc. You can simply write all these atoms down directly, such as Sign = positive, Sign = negative and integer:Sign:[I|T]. – Cheek

@Cheek I know, but since I'm not a Prolog programmer I find it quite ugly to have atoms like that :p – Chancre

Answer 1

To see the problem, it is sufficient to look at a tiny fraction of your program. In fact the following failure-slice is sufficient:

integer_value('integer':Sign:[H],E) :- false,
    abs(E) #< 10,
    abs(E) #> -1,
    integer_value_('integer':Sign:[H],E).
integer_value('integer':Sign:[H,I|T],E) :-
    H in 1..9,
    length([I|T],L), false,
    (   Sign = 'positive',
        E #= F + H * 10^L
        ;
        Sign = 'negative',
        E #= F - H * 10^L
    ),
    integer_value_('integer':Sign:[I|T],F).

L occurs here for the first time, so any length is possible. You will have to modify the length-goal somehow.

Sorrel

@Fatalize: See this for a related problem. – Sorrel

Answer 2

I managed to solve my problem using this other answer pointed out by @false

One of the catch is to decide of the sign of the number as the last step, so that when iterating through possible integers we get alternating answers between positive and negative numbers: after reaching 9 (1 digit), it will unify with -9, then -8, etc. After -1, it will unify with 10, 11, etc. After 99, it will unify with -99, -98, etc. You get the point.

integer_value('integer':Sign:I,E) :-
    integer_value('integer':Sign:I,0,E,E).

integer_value('integer':Sign:[H],N0,N,M) :-
    H in 0..9,
    N1 #= H + N0 * 10,
    abs(M) #>= abs(N1),
    integer_value_('integer':Sign:[],N1,N,M).
integer_value('integer':Sign:[H,I|T],N0,N,M) :-
    H in 1..9,
    N1 #= H + N0 * 10,
    abs(M) #>= abs(N1),
    integer_value_('integer':Sign:[I|T],N1,N,M).

integer_value_('integer':Sign:[],N0,N,_) :-
    (
        Sign = 'positive',
        N #= N0
        ;
        Sign = 'negative',
        N #\= 0,
        N #= - N0
    ).
integer_value_('integer':Sign:[H],N0,N,M) :-
    H in 0..9,
    N1 #= H + N0 * 10,
    abs(M) #>= abs(N1),
    integer_value_('integer':Sign:[],N1,N,M).
integer_value_('integer':Sign:[H,I|T],N0,N,M) :-
    H in 0..9,
    N1 #= H + N0 * 10,
    abs(M) #>= abs(N1),
    integer_value_('integer':Sign:[I|T],N1,N,M).

Chancre