How to implement the factorial sequence in successor arithmetics for all argument modes?

Question

The following Prolog program defines a predicate fact/2 for computing the factorial of an integer in successor arithmetics:

fact(0, s(0)).
fact(s(X), Y) :-
  fact(X, Z),
  prod(s(X), Z, Y).

prod(0, _, 0).
prod(s(U), V, W) :-
  sum(V, X, W),
  prod(V, U, X).

sum(0, Y, Y).
sum(s(X), Y, s(Z)) :-
  sum(X, Y, Z).

It works with queries in this argument mode:

?- fact(s(0), s(0)).
   true
;  false.

It also works with queries in this argument mode:

?- fact(s(0), Y).
   Y = s(0)
;  false.

It also works with queries in this argument mode:

?- fact(X, Y).
   X = 0, Y = s(0)
;  X = Y, Y = s(0)
;  X = Y, Y = s(s(0))
;  X = s(s(s(0))), Y = s(s(s(s(s(s(0))))))
;  …

But it exhausts resources with queries in this argument mode:

?- fact(X, s(0)).
   X = 0
;  X = s(0)
;
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 4Kb, global: 0.2Gb, trail: 0Kb
  Stack depth: 2,503,730, last-call: 100%, Choice points: 13
  In:
    [2,503,730] sum('<garbage_collected>', _1328, _1330)
    [38] prod('<garbage_collected>', <compound s/1>, '<garbage_collected>')
    [33] fact('<garbage_collected>', <compound s/1>)
    [32] fact('<garbage_collected>', <compound s/1>)
    [31] swish_trace:swish_call('<garbage_collected>')

How to implement the factorial sequence in successor arithmetics for all argument modes?

@false Does not generate ‘Stack limit exceeded’ like the last query. — Géry Ogam, Aug 19 '21 at 16:50

false · Accepted Answer · 2021-08-25T14:16:48.137

3

The first question must be why? A failure-slice helps to understand the problem:

fact(0, s(0)) :- false.
fact(s(X), Y) :- fact(X, Z), false, prod(s(X), Z, Y).

This fragment alone terminates only if the first argument is given. If it is not, then there is no way to prevent non-termination, as Y is not restricted in any way in the visible part. So we have to change that part. A simple way is to observe that the second argument continually increases. In fact it grows quite fast, but for the sake of termination, one is enough:

fact2(N, F) :-
   fact2(N, F, F).

fact2(0, s(0), _).
fact2(s(X), Y, s(B)) :- fact2(X, Z, B), prod(s(X), Z, Y).

And, should I add, this can be even proved.

fact2(A,B)terminates_if b(A);b(B).
    % optimal. loops found: [fact2(s(_),s(_))]. NTI took    0ms,73i,73i

But, there is a caveat...

If only F is known, the program will now require temporally space proprotional to |F|! That is not an exclamation point but a factorial sign...

edited Aug 25 '21 at 14:16

answered Aug 19 '21 at 17:00

false

10,264
13
101
209

@Maggyero: see above. – false Aug 20 '21 at 19:21
Didn’t you mean *temporary* space? And is there a more efficient solution? – Géry Ogam Aug 20 '21 at 19:42
That sounds right to me, it is an adverb... As for a more efficient solution, I don't think anyone tried. Successor arithmetics are a good way to get acquainted to Prolog's termination properties. Always keep in mind that you want to ensure that the other direction works as well. In this case, it works just as fast as before. – false Aug 20 '21 at 19:55
Okay, so in the caveat you are referring to [time complexity](https://en.wikipedia.org/wiki/Time_complexity), not [space complexity](https://en.wikipedia.org/wiki/Space_complexity), right? And if I understood correctly, `fact2/2` runs in O(`F`!) if *only* `F` is known. But it runs in O(`N`) if `N` is known. By the way, I did not know that predicates can be overloaded in Prolog (`fact2/2` and `fact2/3`). – Géry Ogam Aug 20 '21 at 20:53
In the rule of `fact2/3`, the 3rd argument is the same as the 1st so it has exactly the same influence on the number of inferences which means, if only `F` is given you are effectively computing `fact(F,_)` and thus there will be a moment where that big number is present. If `N` is known, it will compute a result that is |`N`|! With successor-arithmetics (as it is implemented), the cost to represent just a number `N` is O(`N`) and not ld('N'). – false Aug 21 '21 at 03:49
Okay. [tiffy’s answer](https://stackoverflow.com/a/68860765/2326961) uses a cut. In comments I linked your answer on red cuts and green cuts to explain that his program uses a red cut, which should be avoided. He does not agree. What do you think? – Géry Ogam Aug 21 '21 at 11:04

score 1 · Answer 2 · edited Aug 29 '21 at 13:20

1

I think you can use cut to avoid backtracking when the second argument is a ground term.

fact(0, s(0)).
fact(s(X), Y) :-
  fact(X, Z),
  prod(s(X), Z, W),
  (ground(Y) ->
    !,
    Y = W
  ; Y = W).

prod(0, _, 0).
prod(s(U), V, W) :- sum(V, X, W), prod(V, U, X).

sum(0, Y, Y).
sum(s(X), Y, s(Z)) :- sum(X, Y, Z).

Examples:

?- fact(N, 0).
   false.

?- fact(N, s(s(s(0)))).
   false.

?- fact(X, s(0)).
   X = 0
;  X = s(0)
;  false.

?- fact(s(s(s(0))), s(s(s(s(s(s(0))))))).
   true
;  false.

?- fact(s(s(s(0))), s(s(s(s(s(0)))))).
;  false.

?- fact(s(s(s(0))), Y).
   Y = s(s(s(s(s(s(0))))))
;  false.

?- fact(X, Y).
   X = 0, Y = s(0)
;  X = Y, Y = s(0)
;  X = Y, Y = s(s(0))
;  …

?- fact(s(s(X)), s(s(Y))).
   X = Y, Y = 0
;  X = s(0), Y = s(s(s(s(0))))
;  …

edited Aug 29 '21 at 13:20

Géry Ogam

6,336
4
38
67

answered Aug 20 '21 at 14:48

slago

5,025
2
10
23

Thanks for the cut solution, though [cuts should be avoided](https://stackoverflow.com/a/14556019/2326961). – Géry Ogam Aug 20 '21 at 21:55
1

`fact(N,0)` already loops, idem `fact(N, s(s(s(0))))`. The role of the cut is not evident for me. – false Aug 21 '21 at 13:12
It was a typo, which has now been fixed as ```!, Y=W```. Thanks! – slago Aug 21 '21 at 15:37
1

@Maggyero You're welcome! And yes, we must avoid to use cuts; however, I think we also need to know when we should to use them. – slago Aug 21 '21 at 15:48

How to implement the factorial sequence in successor arithmetics for all argument modes?

2 Answers2

Linked