A recursion ends unexpectedly.

[schwidom]

Is this a bug or normal?

https://stackoverflow.com/questions/79314787/i-am-encountering-an-early-recursion-termination-in-clingo

Thanks in advance.

[rkaminsk]

Your program can choose between 1 and 2 moves; 1 from the first rule and up to one from the second rule. So the output looks correct.

Maybe you are aiming for something more like this?

time(1..3).
move( a, b).
move( b, c).
move( c, d).

{ p( 0, A, B) : move( A, B) } = 1 .

0 { p( T, B, C) : p( T-1, A, B), move( B, C) } 1 :- time(T).

If your graph is acyclic, you can also write

move(a, b).
move(b, c).
move(c, d).

{ p(0, A, B) : move(A, B) } = 1 .

0 { p(T, B, C) : move(B, C) } 1 :- p(T-1, A, B).

Grounding will not terminate if there is a cycle, though.

[schwidom]

Thanks for the solutions.

btw. this also seems to work:

move( a, b).
move( b, c).
move( c, d).

{ p( 0, A, B) : move( A, B) } = 1 .

0 { p( T, B, C) : p( T-1, A, B)} 1 :- move( B, C).

But this doesn't really explain why the first variation did't recurse properly. Where can I find an explanation for this behaviour?

[MaxOstrowski]

You have to move your p/3 condition from inside the choice rule to the body of the rule. Otherwise you will restrict the whole set of all predicates p(N+1,*,*) for all N to atmost 1.  But you want to have this restriction for each N. So at most one move p(N+1,*,*) for each N. Also use the --text option of clingo to get a better understanding of the grounding of your rule (like you tried manually).

[rkaminsk]

But this doesn't really explain why the first variation did't recurse properly. Where can I find an explanation for this behaviour?

I tried to explain here:

Your program can choose between 1 and 2 moves; one from the first rule and up to one from the second rule. So the output looks correct.

One move here:

{ p( 0, A, B) : move( A, B) } = 1 .

Up to one move here:

0 { p( N+1, B, C) : p( N, A, B), move( B, C) } 1.

So there can be at most two moves in a solution.

The rule

0 { p( T, B, C) : p( T-1, A, B)} 1 :- move( B, C).

will work. In practice, it is often best to keep conditions of head aggregates domain.

[schwidom]

I think I get it. The choise operator don't seem to recurse on its own created facts. At least in the aforementioned examples.

But this here don't stop recursing:

p(1).

0 { p(N+1) : p(N) } 1 .

So it seems to be that it can under some circumstances reprocess its own output.

I am not 100% sure because this also cannot finish:

p(1).

0 { p(N+1) : p(N) } 0.

And here is no new fact created.

And btw. There is another solution for my example:

move( a, b).
move( b, c).
move( c, d).

{ p( 0, A, B) : move( A, B) } = 1 . 

{ p( T, B, C) : move( B, C), p( T-1, A, B)  }.           

I assume the choice operator gets reprocessed when the cardinality has changed.

As soon it is prolog like I can understand it easily but this choice operator needs more exercises.

[rkaminsk]

Maybe check #504 (comment) for some introductory material to ASP. While Prolog and ASP share some similarities, they are still very different languages.