Search code examples
prologstack-overflow

Why does this simple Prolog example cause a stack overflow?

I'm learning Prolog. I wrote several simple facts and rules:

heavier(X,Y) :- lighter(Y,X).
heavier(horse,mouse).
lighter(X,Y) :- heavier(Y,X).

Then I asked this query:

lighter(mouse,horse).

And I got following error:

Fatal Error: local stack overflow (size: 16384 Kb, reached: 16383 Kb, environment variable used: LOCALSZ)

What's wrong with this program?

Solution

  • I've reproduced your clauses here, numbered for convenience:

    heavier(X,Y) :- lighter(Y,X).  %1
heavier(horse,mouse).          %2
lighter(X,Y) :- heavier(Y,X).  %3

    So let's figure out what the interpreter is going to do.

    1. You asked it lighter(mouse,horse). That matches 3, with X = mouse and Y = horse.
    2. It now needs to know if heavier(horse, mouse) is true. That matches 1, with X = horse and Y = mouse.
    3. It now needs to know if lighter(mouse,horse) is true. That matches 3, with X = mouse and Y = horse. Hey, wait a minute!

    Since the interpreter starts at the top, when evaluating heavier/2, it will always start with the first clause, which makes it want to evaluate lighter/2, which makes it want to evaluate heavier/2, which starts with the first clause... You probably see where that is heading.

    But it's not just the infinite loop. You see, when the interpreter decided to go with the first clause, it knew there was another clause that matched as well. Every time it decided to evaluate the first clause, it remembered that other option as well. The stack of unused options grows and grows and grows... Until the stack flows over.

    So the direct problem is the order of the clauses 1 and 2. If you switch those, it first tries to evaluate the fact heavier(horse, mouse). which succeeds, so your query lighter(mouse,horse). returns true. Great!

    But that's just half of it. Let's reorder those clauses, and ask if lighter(bird, horse).

    Takes a while, doesn't it? That's because that infinite loop is still occurring. Now the fact never matches, because it concerns mice instead of birds, and the interpreter just keeps looping through your circular definition. It doesn't have any options to remember, so the stack never overflows (or at least not as fast), but we're still not getting an answer.

    A solution to this would be to separate your facts from your definition.

    heavier(X, Y) :- is_heavier(X, Y).
heavier(X, Y) :- is_lighter(Y, X).

lighter(X, Y) :- heavier(Y, X).

is_heavier(horse, mouse).
is_lighter(bird, horse).

    And that should do the trick.