I meet some problem when I try to implement

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

```

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

it ends up from the local stack.

``````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?

+3

source to share

First, two assumptions:

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

``````friends(mia,ellen).
friends(mia,lucy).
friends(X,Y) :-
friends(X,Z),
friends(Z,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.

# Fix

They have two predicates:

• `known_friends/2`

which gives a direct relationship.
• `friends/2`

which also encodes transitivity

``````known_friends(mia,ellen).
known_friends(mia,lucy).

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`

because:

• `known_friends(mia,ellen)`

is executed, and
• `friends(ellen,bishop)`

found recursively.

# roundness

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.

+2

source

This section `friends/2`

``````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?

+2

source

All Articles