Prolog factorial predicate

Question

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.

You can also manually "step" through it: fact(3, F) doesn't match fact(0, 1) (since 3 and 0 are not unifiable), so Prolog will match the next clause fact(N, F) with N = 3. It then calls fact(N1, F1) coming up with N1 = 0 and F1 = 1 per the first clause again, and so on. Note that, after finding the solution, it tries to find more and does not terminate, causing a stack overflow. — lurker
I'm curious: how did you go about writing this predicate if you don't know how it works? — lurker
@lurker: That's very understandable: Another version might have produced an instantiation error. — false
@lurker: Well, I started from this version: factorial(0, 1). factorial(N, F):- N > 0, N1 is N - 1, factorial(N1, F1), F is N * F1., and tried until I got that. — zaig

false false · Accepted Answer · 2017-02-21T15:30:25

You can try to go through your program step-by-step to understand what's going on. You will be very slow indeed, and quite unreliable. Or, you instead let Prolog do (part of) the work. So the idea is to modify the program a bit and then look what Prolog thinks of 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, the program will not terminate. And thus the same holds for your original program!

In the original version that was not 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 will end in a loop. Worse, false queries now loop immediately:

?- 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 write instead of is now #=, and you need some restriction like N #>= 1. Can I leave you there?

Prolog factorial predicate

1 Answers