Factorial calculation without using recursion

Question

I'm trying to implement a solution for the factorial calculation (n!) without using recursion, only using the retroaction of prolog. For example:

factorial(0, 1).
factorial(1, 1).
factorial(2, 2).

retroaction(X, Y) :-
factorial(K, Y),
not(K = X),
fail.

retroaction(K, Y) :- factorial(K, Y).   

With fixed facts factorial, if I call the predicate retroaction to discover the factorial of 2, for example, I'll receive the correct answer:

?- retroaction(2, X).
X = 2.

The solution that I'm trying to implement is:

factorial_ret(Number, _) :-
    retractall(factorial(_, _)),
    assertz(factorial(0,1)),
    factorial(X, Y),
    not(X = Number),
    NewNumber is X + 1,
    Factorial is Y * NewNumber,
    retractall(factorial(_, _)),
    assertz(factorial(NewNumber, Factorial)),
    fail.

factorial_ret(Number, Y) :- 
    factorial(Number, Y).

If I try get the factorial of a number greater than 1, doesn't works. Someone have any idea of the why?

Answer 1

As @lurker pointed out, you're confusing the 'storage predicate' with the 'definition predicate'. You need the factorial/2 definition, so it makes little sense to retractall(factorial(_,_)).

Below, I use retract(mem(N, F)) to retrieve the temporaries values and prepare the DB for an eventual update. There should be always only an instance of mem/2.

% replace recursion with a failure driven loop
:- dynamic mem/2.
factorial(X, Y) :-
    assert(mem(0, 1)),
    repeat,
    retract(mem(N, F)),
    (  X == N % done ?
    -> Y = F, % yes, succeed
       !      % but be sure to avoid 'external' backtracking...
    ;  N1 is N + 1,
       F1 is N1 * F,
       assert(mem(N1, F1)),
       fail   % loop: 'goto repeat'
    ).

Note that all builtins in the branch between repeat,...,fail are non backtrackable (well, except retract/1).

Please note also that such code will be much slower of a recursive definition (and will not work in multithreaded SWI-Prolog).

I think that assert/retract were made available early to Prolog programmers as required to handle 'knowledge bases', not to serve as global variables. Several Prologs have specialized library predicate for global variables, since there are legitimate uses of them: for instance, see memoization.

PS: 'retroactive' is a term used in linear systems stability theory, I've never seen it used about programming

edit Could be instructive to see how the bug reported by @repeat can be solved: just swap the unification and the cut. Well, we also need an test that X is a positive integer. Sincerely, I think this is actually irrelevant for the question at hand.

...
    (  X == N % done ?
    -> !,     % yes, be sure to avoid further backtracking
       Y = F  % unify with the computed factorial
    ;  N1 is N + 1,
...

Answer 2

You've got a lower-case k in your not clause.

Answer 3

Assuming that by "retroaction" you actually mean "memoization", one way to go about this would be:

As long as you don't find the factorial you need, find the largest one so far, calculate the next, rinse and repeat.

I am writing this answer because it has a bit less unnecessary code than the otherwise correct answer by @CapelliC.

You need only one starting fact for this, the factorial of 0:

You then can use a repeat loop to do the "as long as". Then, if you always add new factorials to the top of the stack of pre-calculated factorials and you always look only once, you can be sure that you find the biggest one so far:

:- dynamic factorial/2.
factorial(0, 1).

factorial_memoize(N, F) :-
    repeat,
        (   factorial(N, F0)
        ->  !, F = F0
        ;   once(factorial(N0, F0)),
            succ(N0, N1),
            F1 is N1 * F0,
            asserta(factorial(N1, F1)),
            fail
        ).

Here is how the program works:

?- listing(factorial/2).
:- dynamic factorial/2.

factorial(0, 1).

true.

?- factorial_memoize(0, F).
F = 1.

?- listing(factorial/2).
:- dynamic factorial/2.

factorial(0, 1).

true.

?- factorial_memoize(5, F).
F = 120.

?- listing(factorial/2).
:- dynamic factorial/2.

factorial(5, 120).
factorial(4, 24).
factorial(3, 6).
factorial(2, 2).
factorial(1, 1).
factorial(0, 1).

true.

Answer 4

無! My conscience forces me to un-ask your question.

For what you seek is a no-no—even in imperative-programming—and more so in Prolog.

prolog-assert surely can be very useful in some circumstances; I usually see it as a "weapon of last resort", not as the "first weapon of choice". IMO the likely consequences of using it include:

• declarative-programming is left behind.
• logical-purity is easily lost.
• debugging gets a lot harder.
• code-complexity rises.
• performance drops.
• smells like global-variables.

Case in point? Take the answers by @CapelliC and by @Boris. Quoting @Boris:

I am writing this answer because it has a bit less unnecessary code than the otherwise correct answer by @CapelliC.

Let's run some queries and put that assessment to the test!

?- factorialBoris(0,0).
**LOOPS**

?- factorialBoris(0,2).
**LOOPS**

?- factorialBoris(1,2).
**LOOPS**

?- factorialCapelliC(0,0).
**LOOPS**

?- factorialCapelliC(0,2).
**LOOPS**

нет!

Please do not get me wrong! I do not want to put down the work and effort by @CapelliC and by @Boris, two Prolog topusers on SO, in any way, shape or form.

---

Bottom line:

Using a imperative-programming style when coding in Prolog can easily backfire!

Rigorous testing of code using prolog-assert is much harder than testing logically-pure code—and even that can be quite a lot, believe me!

In cases of uncertainty, choose the wise path: simply do that which is right:)

Preserve logical-purity whenever possible—don't trade it in for nothing in return.