Recursive link in prologue

I meet some problem when I try to implement

friends(mia, ellen).
friends(mia, lucy).
friends(X,Y) :-


and when I ask ?- friends(mia, X).

it ends up from the local stack.

Then I add

friends(ellen, mia) friends(lucy, mia) 


I ask ?- friends(mia, X).

, he keeps on answering X = mia


I can't figure out why is it recursive?


source to share

2 answers

First, two assumptions:

  • the actual code you want to write is the following, with the corresponding dots:

    friends(X,Y) :- 

  • The presence of friends: friends of friends are also my friends (I would prefer to model friendship as distance: "A is close to B" and "B is close to C" does not mean that "A is near C"), repeating the answer is a correct definition of what you want to simulate.

Now let's see why we are moving to infinite recursion.

Step by step

So what happens when we ask friends(mia,X)


  • The first suggestion gives Y=ellen

    (you are asking for more solutions)
  • The second suggestion gives Y=lucy

    (you are asking for more solutions again)
  • Stack overflow!

Detailed description of the third sentence:

  • I want to know if friends(mia,Y)

    for some variable exists Y

  • Is there a variable Z

    such that it friends(mia,Z)

    gets executed?

    Note that apart from renaming from Y

    to Z

    , we are asking the same question as step 1 above? It smells like endless recursion , but let's see ...

  • We try the first two sentences friends

    , but then we fail because we don't, friends(ellen,Y)

    and friends(lucy,Y)

    so ...
  • We call the third clause to find if a transitive friendship exists and we go back to step 1 without reaching further infinite recursions.

This problem is similar to infinite left recursion in context-free grammars.


They have two predicates:

  • known_friends/2

    which gives a direct relationship.
  • friends/2

    which also encodes transitivity

    friends(X,Y) :- known_friends(X,Y).
    friends(X,Y) :- known_friends(X,Z), friends(Z,Y).

Now, when we ask friends(mia,X)

, friends/2

gives the same answer as the two sentences known_friends/2

, but finds no answer for a transitive sentence: the difference is what known_friends

will make little progress, namely find a known friend mia

(no recursion) and try to find (recursively) if this one is a friend of some people.

Friends of friends

If we add known_friends(ellen, bishop)

: -) that friends

also will Y=bishop


  • known_friends(mia,ellen)

    is executed, and
  • friends(ellen,bishop)

    found recursively.


If you add circular dependencies in the friendship graph (c known_friends

), you get an infinite traversal of that graph with friends

. Before you can fix this, you must consider the following questions:

  • Does it work friends(X,Y) <=> friends(Y,X)

    for everyone (X,Y)

  • What about friends(X,X)

    , for everyone X


Then, when you evaluate friends

, you should keep a set of all the people seen to detect when you go through known_friends

, taking the above properties into account. It shouldn't be too hard if you want to try it.



This section friends/2

has disadvantages:

friends(X,Y) :- friends(X,Z),friends(Y,Z).


Translate this into English: "If X

and Y

have a common friend Z

, then X

and Y

are friends."

Or, let it specialize, let it X

be "I", let it Y

be my neighbor "FooBert", and let it Z

be "you": So if I am your friend and FooBert is your friend ... does that make me and FooBert friends? I don't think so, I hate this guy - he always slams the door when he comes home. :)

I invite you to consider the algebraic properties that should be relevant friends/2

, those that it may have and those that it shouldn't. What about reflexivity, symmetry, antisymmetry, transitivity?



All Articles