Prolog Code Example: Unification

Question

From an old final for my class:

Here is some prolog code:

mystery(1, 1).
mystery(N, F) :-
    N1 is N-1,
    mystery(N1,F1),
    F is F1*N.

Question 1: What value is unified with P in

mystery(3, P).

Question 2: If a semicolon is pressed after Prolog produces and answer for mystery, and interpreter will eventually report "ERROR: Out of local stack". Why dies this occur, and how could you modify mystery to avoid the error?

---

Question 1: I get

P = 6 ?

Question 2: If I press semi-colon to get all answers, I get an out of local stack error. I'm not sure what this code is trying to accomplish or how to fix it so I don't go out of local stack. Any ideas?

Answer 1

The out of stack error is probably because, when you get down to mystery(1, F1) which resolves to mystery(1, 1) and ask for more solutions, you hit the next clause, which calls mystery(0, F1). At this point, it tries to find a solution, but the only clause that matches calls for mystery(-1, F1), and that calls for mystery(-2, F1) and so forth. This means that there's matches called for until either the first number wraps around to 1 or you get a stack overflow, since each pending match takes stack space.

Answer 2

@David Thornley already explained why searching for more answers blows up your stack. You could fix it by using a cut operator:

mystery(1, F) :- !, F is 1.
mystery(N, F) :-
    N1 is N-1,
    mystery(N1,F1),
    F is F1*N.

The cut here makes it so that if the first argument is 1, the second rule may not be applied.