Comment by samdk

Prolog's pattern matching actually isn't much like an if-then-else construct at all, and thinking about it like one will get you into a lot of trouble once you move beyond very very trivial Prolog programs. While it resembles the pattern matching done in Haskell and ML-like languages at first glance, what's actually happening in Prolog is very different.

A look at a simple (although very inefficient) Fibonacci program will illustrate the difference. In Haskell, it'd look something like this: (and work like you might expect)

    fib 0 = 0
    fib 1 = 1
    fib n = fib (n-1) + fib (n-2)

The obvious direct translation to Prolog (I'm using SWI Prolog[0]) is something like this:

    /* fib(N,X): X is the Nth fibonacci number */
    fib(0,0).
    fib(1,1).
    fib(N,X) :-
        N1 is N-1,N2 is N-2,
        fib(N1,A),fib(N2,B),
        X is A+B.

This, however, is going to cause problems if you actually try to run it, and the reason is that Prolog doesn't just do pattern matching: it attempts to unify the query term (the thing you give it) with the program terms (the things on the left in the program above), and instead of just using the first result that matches, it will (if you ask it to do so) return every possible result by doing a left-to-right depth-first search on the solution tree (using a process called SLD resolution[1]). The expected behavior of the above program is something like this:

    ?- fib(0,X).
    X = 0 ;
    false. /* there are no more possible matches */

What's actually going to happen though is this:

    ?- fib(0,X).
    X = 0 ;
    /* runs forever */

When you give it the query fib(0,X), it first unifies that with fib(0,0), and the first answer is what you expect: X = 0. The difference occurs when you ask it for another answer (which you do in the interpreter by typing a semicolon). What you want Prolog to say is that there are no other answers, because there's only one 0th Fibonacci number. What Prolog actually does though is it backtracks[1] and goes back up the resolution tree to see if there are any more program terms the query can be unified with. In this case there are: fib(0,X) can unify with fib(N,X) also. Prolog soon gets into negative numbers (and past the base cases), and so ends up running forever.

One possible corrected version is below:

    fib(0,0).
    fib(1,1).
    fib(N,X) :-
        N > 1,
        N1 is N-1,N2 is N-2,
        fib(N1,A),fib(N2,B),
        X is A+B.

Here, we ensure that we only unify with the third query when N is large enough that we don't match the first two, and so we get the output we'd expect.

[0] http://www.swi-prolog.org/ [1] http://en.wikipedia.org/wiki/SLD_resolution [2] http://en.wikipedia.org/wiki/Backtracking