Prolog Out of local stack error

Question

I tried some basic example from a book and it makes "Out of local stack" error (I'll tell more after the code). here is the code:

edge(a,b).
edge(a,e).
edge(b,d).
edge(b,c).
edge(c,a).
edge(e,b).
tedge(Node1,Node2) :-
    edge(Node1,SomeNode),
    edge(SomeNode,Node2).
edge(X,Y) :- tedge(X,Y).

I tried for example to write query edge(a,b) and it returned true and then I entered ';' and it made the error. What's the problem here?

The short answer is that it went into infinite recursion. If you do a trace, you'll see what's happening. Why did you defined edge(X,Y) :- tedge(X,Y).? It's bound to create a loop scenario since edge/2 also defines facts which tedge/2 refers to. Just leave it at tedge/2 and query tedge(a,b).. — lurker

Wouter Beek Wouter Beek · Accepted Answer · 2014-12-30T18:27:43

The problem is that you have defined what an edge is in a cyclic way. While looking for a second path from a to b Prolog is looping through tedge(a,VAR), edge(a,VAR), tedge(a,VAR), etc.

Notice that Prolog would loop even if you had not defined your edges to be symmetric, namely due to the cycle a -> b -> c -> a.

The solution is to keep track of vertices and/or edges that have been visited before. Checking for non-recurring vertices can be straightforwardly implemented using closure0/3 (a predicate I learned from SO user false). If you use that predicate, you only need your edge/2 facts and the following query:

?- closure0(edge, a, b).

Prolog Out of local stack error

1 Answers