1

I'm using Prolog's integer constraint libraries (clpfd) and I'm having some difficulty getting it to reliably answer queries using range information. As an example program:

puzzle(X, Y) :-
  X in 1..5,
  X #>= Y.

The following query can then be answered in constant time: puzzle(2, -10000000000000000000000). This query is constant regardless of the size of Y.

I'm trying to get this same behavior, but in a recursive setup (which is closer to the problem I am actually trying to solve). However, clpfd doesn't seem able to deduce the range information in this case:

recursive(0).
recursive(X) :-
    X1 #= X - 1,
    recursive(X1).

With this setup, the query recursive(10000000000000) takes a large amount of time (seemingly searching linearly down to 0).

Is there a way I can get constant time evaluation with the second example?

It seems like clpfd is only smart enough to make this constant time step when the variables span a single predicate. But it seems like there should be some way to hint to prolog about the induction happening in the recursive setup, or is that too much to ask?

false
  • 10,264
  • 13
  • 101
  • 209
Kleptine
  • 5,089
  • 16
  • 58
  • 81
  • It might be possible to implement the `recursive/1` predicate using a ["lazy" infinite list](https://stackoverflow.com/questions/8869485/lazy-lists-in-prolog). – Anderson Green Feb 24 '19 at 03:14
  • 3
    If you replace all the clpfd stuff with `true` or traditional Prolog analogs in your two examples, you get an O(1) predicate that does nothing for your first example and an O(N) predicate that does nothing in your second example. clpfd doesn't fundamentally alter the way Prolog evaluates predicates. So I think your expectations are a little high for a library, but I also think if we saw your _actual_ problem, we might be able to help you find a solution. – Daniel Lyons Feb 24 '19 at 06:55
  • 2
    The cost of comparison is O(ld N) of the smaller number. – false Feb 24 '19 at 10:02
  • 1
    `recursive(-1)` does not terminate - due to the same reason – false Feb 24 '19 at 10:23
  • @DanielLyons Hmm.. good point. The actual problem I am trying to solve is a reachability query on an extremely large, but regular, graph. The graph contains ~100,000 subgraphs that are all precisely the same, (except along a couple of edges that link them together). I'd like to find a way to execute queries taking advantage of induction, ie. if X_1 is reachable from X_2, then because the graph is regular, we know X_1 is reachable by all X_*. I can elaborate more in the question if this is helpful. – Kleptine Feb 25 '19 at 17:57
  • 1
    I think you'd probably have better results just asking a new question with this problem. – Daniel Lyons Feb 25 '19 at 17:59
  • I'll do that, then, thanks! – Kleptine Feb 25 '19 at 21:55

0 Answers0