CODEWITHSUNDEEP
prolog
Pooty Lim
Pooty Lim

Reputation: 69

Prolog recursion - why do I need to declare an extra variable

One thing I don't understand is why must we declare another variable during recursion. For example:

fact(0,1).
fact(N,M):- N>0, N1 is N-1, M is M1 * N, fact(N1, M1).

Why can't we just do:

fact(0,1).
fact(N,M):- N>0, M is M1 * N, fact(N - 1, M1).

On certain recursions, the latter will give a stack overflow error. What is the difference between the 2?

Upvotes: 0

Views: 49

Answers (1)

Peter Ludemann
Peter Ludemann

Reputation: 1005

If you're used to Lisp -- or almost any "conventional" programming language -- you need to explicitly quote things to prevent them from being executed. Prolog is the opposite: everything is implicitly quoted and you need to explicitly mark things that are executable, either by them being a goal or by being the argument to a predicate that interprets (evaluates) them.

So, let's look at your 2nd clause:

fact(N,M):- 
    N>0,              % 1
    M is M1 * N,      % 2
    fact(N - 1, M1).  % 3

In item #1, N>0 (which is the same as '>'(N,0)) is in an executable context (a goal on the right-hand side) and therefore the predicate '>'/2 is called (more on this later).

In item #2, M is M1 * N is the same as is(M, '*'(M1,N)) ... the is(...,...) is in an executable context but the M1*N is not: it's just a structure (or "term"). The is/2 predicate interprets the 2nd argument and unifies the result with the 1st argument.

In item #3, it's similar -- equivalent to fact('-'(N,1), M1) -- and the '-'(N,1) is a structure that isn't interpreted further. So, N-1 will be passed as an uninterpreted argument (the N1 will, of course` be whatever value that it's been instantiated to).

Now, the confusing part is that the '>'/2 predicate interprets its arguments. So, if it gets called, for example, with 1+2 > 0, it interprets the 1+2 (resulting in 3) and also the 0 (resulting in 0) and then does the comparison.

Here's another way of defining fact/2, which might make things clearer:

fact(N, 1) :- 0 is N . % Need is/2 to force evaluation of N
fact(N, Fac) :- 
    N > 0,         % evaluates N 
    fact(N-1, F0), % does *not* evaluate N-1 
    Fac = N*F0.    % does *not* evaluate N*F0 ... Fac is N*F0 would evaluate

And this query:

?- fact(3,X), X2 is X.
X = 3*((3-1)*((3-1-1)*1)),
X2 = 6 .

You might find it instructive to try the query trace, fact(2,X); and also change the last goal (Fac = N*F0) to Fac is N*F0.

Upvotes: 1

Related Questions