Search code examples
exceptionprologclpfd

Why is length/2 getting me out of global stack?

when i commit the query:

?- X in 1..2, length(List,X).

the returning results are:

X = 1, List = [_1260];
X = 2, List = [_1260, _1266];
ERROR: Out of global-stack.
ERROR: No room for exception term. Aborting.
% Execution Aborted

i thought this happened cause X isn't grounded, so i ran 3 more queries to see how length/2 bahaves with non-instantiated variables as length:

?- X in inf..sup, length(List,X).
?- length(List,_).
?- length(List,_X).

and all work properly. Thus, if X isn't grounded, after reaching domain's supremum, length/2 crashes. Why is this happening? Shouldn't it return false instead?

Solution

  • Why is this happening? Shouldn't it return false instead?

    No, since length/2 is not aware of these bounds, it simply suggests values, and the frozen constraint check each time rejects these values.

    The length/2 [swi-doc] can be used in a "constructive" way. Indeed we can generate lists with their corresponding length like:

    ?- length(L, N).
L = [],
N = 0 ;
L = [_2316],
N = 1 ;
L = [_2316, _2322],
N = 2 ;
L = [_2316, _2322, _2328],
N = 3
...

    Now you defined a constraint on N, which means that if you set N to a certain value, the Prolog interpreter will check if that value is in the 1..2 range. For each value with N > 2, that will thus fail. But length/2 of course does not understand this range. It will keep suggesting lists and their corresponding lengths, and that will each time fail.

    It is equivalent to:

    ?- length(L, N), member(N, [1, 2]).
L = [_2304],
N = 1 ;
L = [_2304, _2310],
N = 2 ;
ERROR: Out of global-stack.
ERROR: No room for exception term. Aborting.

    Here it makes more sense to do this in reverse, like:

    ?- member(N, [1,2]), length(L, N).
N = 1,
L = [_3372] ;
N = 2,
L = [_3372, _3378].

    Or in case that is not an option try to freeze/2 [swi-doc] the construction of the list until N is known.