CODEWITHSUNDEEP
prolog
llamagish
llamagish

Reputation: 209

PROLOG Stack overflow recursive multiply

multiply(A,0,0).
multiply(A,B,C) :- D is B-1, multiply(A,D,E), C is E+A.

After using this rule once and Prolog returns an answer, if I want it to continue searching (prompts A = 5 ? and I hit ;), Prolog crashes. I don't understand why? Would anyone be able to explain. Thank you.

Upvotes: 3

Views: 778

Answers (2)

User9213
User9213

Reputation: 1316

Here is how you can make an endless loop easily:

?- [user].
|: loop(0). 
|: loop(X) :- X0 is X - 1, loop(X0).
|: ^D% user://1 compiled 0.01 sec, 2 clauses
true.

?- loop(3).
true ;

After you redo (when you press ;) you backtrack into the second clause with a 0.

Then X0 becomes -1, you go into the recursive loop(X0), and from here on the first clause will never again match.

Try for example querying:

?- loop(-1).

Your version of the infinite loop is not tail-recursive, which means that it will use up the stack eventually. Here is a minimal example:

?- [user].
|: out_of_stack(0, 0).
|: out_of_stack(X, Y) :- X0 is X - 1, out_of_stack(X0, Y0), Y is Y0 + 1.
|: ^D% user://1 compiled 0.01 sec, 2 clauses
true.

?- out_of_stack(3, R).
R = 3 ;
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 1.0Gb, global: 19Kb, trail: 1Kb
ERROR:   Stack depth: 11,183,864, last-call: 0%, Choice points: 3
ERROR:   Possible non-terminating recursion:
ERROR:     [11,183,864] user:out_of_stack(-11183853, _5046)
ERROR:     [11,183,863] user:out_of_stack(-11183852, _5066)

So this is what is happening and why Prolog crashes.

To get rid of the problem, do as other have suggested. The other solution is to use 0, s(0), s(s(0)), ... to represent natural numbers.

Upvotes: 1

Koralp Catalsakal
Koralp Catalsakal

Reputation: 1124

The problem is,

multiply(A,B,C) :- D is B-1, multiply(A,D,E), C is E+A.

This code does not have the constraint B > 0 that would prevent the stack overflow from occurring.

You can modify the code as,

multiply(A,B,C) :- B > 0, D is B-1, multiply(A,D,E), C is E+A.

Also, this line multiply(A,0,0). gives a singleton warning, so you can possibly change it into multiply(_,0,0)

Note : I wrote the constraint B > 0 thinking that you call the predicate as multiply(5,1,A).

Upvotes: 5

Related Questions