[SOLVED] Prolog factorial predicate

Prolog factorial predicate

I have a factorial predicatefact(N,F), where either N or F or both are bounded to a number.

For example I can have fact(3,F) or fact(N,6). Here is my predicate, which works but I don't really understand how. I used trace but still have problems understanding it.

fact(0,1).
fact(N,F) :-
        fact(N1,F1),
        N is N1 + 1,
        F is N * F1.

Solution

You can try to go through your program step-by-step to understand what's going on. This will be very slow indeed, and quite unreliable. Or, you can instead let Prolog do (part of) the work. So the idea is to modify the program a bit and then look what Prolog thinks about it.

This is what I see when I look at your program - this is called a failure-slice

fact(0,1) :- false.
fact(N,F) :-
        fact(N1,F1), false,
        N is N1 + 1,
        F is N * F1.

When will this fragment terminate? Look at the remaining visible part! The N only occurs once in the head: nobody is interested in the first argument! Same for the F. Therefore: No matter what arguments you have, this program will not terminate. And thus the same holds for your original program!

In the original version this wasn't that clear. Watch out:

?- fact(29,F).
   F = 8841761993739701954543616000000

At first this looks nice, but if you ask for the next answer (with SPACE or ;), you end up looping, i.e. waiting for an answer that never comes. Worse, false queries loop right away:

?- fact(29,1).
   loops.

So how can you find these problems, without understanding precisely what is going on? This is what false is for. A goal that is never true. If you add it like fact(29,F), false. you will never be distracted by beautiful answers.

Why have you put all your arithmetics at the end? I suspect because you got some errors before. There is an easy way out to avoid all such errors:

:- use_module(library(clpfd)).

You can now write #= instead of is, and you need some restriction like N #>= 1. Can I leave you there?