Prolog routing routine

Question

Hi,

I am trying to write a routing function but I cannot seem to get the result needed. This is the code so far. Predecessor finds the node that is linked to N and returns it as P.

traceroute(_,L) :- member((A,A),L).

traceroute(N,L) :- predecessor(N,P), append(N,L,L1), traceroute(P,L1).

When I run my traceroute(placeA, Y). it returns this data.. Y = [ (_G575, _G575)|_G579] .

Basically for the first line of traceroute I am trying to terminate the recursion if any member is a predecessor of itself. The second part should be loop through all the nodes and add them to the list (L).

The nodes are stored like [(placeA,placeB),(placeB,placeC)] and the list should store like [placeA,placeB,placeC]

I can't understand why I am getting these results.

Help! :)

Answer 1

A solution that looks like this (when it's incorrect) usually means that you haven't ground (ie instantiated) a term somewhere where you should have.

I'm not completely sure how your code is meant to work, but it looks like your main trouble is that you're passing a nonground variable for the second argument of traceroute.

In the member call, since L is nonground, you're actually asking prolog to return an item of the form (A,A) which is an element of a completely uninstantiated list. While this doesn't make all that much sense there are times when doing this sort of thing is useful, so prolog dutifully complies and will (upon backtracking) generate lists of increasing length (since you haven't specified the length anywhere) of nonground variables that has an item (A,A) at some point. ie:

?- traceroute(placeA, Y).
Y = [ (_G271, _G271)|_G275] ;
Y = [_G274, (_G271, _G271)|_G278] ;
Y = [_G274, _G277, (_G271, _G271)|_G281] ;
Y = [_G274, _G277, _G280, (_G271, _G271)|_G284] ;

You need to either pass a value for Y which is ground or further constrain the values that it takes inside your predicate or possibly even both.

Also even though the second clause isn't actually executed, you have a similar problem there: L which is again nonground is appended onto N to yield L1 which is then also nonground. Since this predicate does this recursively, the final list is always always going to be nonground.