Can this be made tail-recursive in Prolog?

Question

I'm learning Prolog, and as an exercise, I'm experimenting with a simple database that calculates the sum of all numbers up to the given number (i.e. 0=0, 1=1, 2=3, 3=6, 4=10, ...). Easy enough:

counting_sum(0, 0).
counting_sum(Num, Sum) :- Num > 0, PrevNum is Num - 1,
    counting_sum(PrevNum, PrevSum), Sum is Num + PrevSum.

That blows up somewhere around counting_sum(150000, X). with a stack overflow. I understand that Prolog can do tail recursion, but if I move the recursive call to the end of the rule, I get

error(instantiation_error,(is)/2)

which I assume is telling me I can't use PrevSum before it's been unified with counting_sum(PrevNum, PrevSum). Is that correct, and is there any way to make this tail-recursive? I'm using GNU Prolog 1.3.1 if that makes any difference.

P.S. I'm still shaky on the terminology. Let me know if I used the terms incorrectly.

Guendolen

You are right about the cause of the instantiation error. – Ghostwrite

Answer 1

Try something like this (use an accumulator):

counting_sum(Count, Sum):-
  counting_sum(Count, 0, Sum).

counting_sum(0, Sum, Sum).
counting_sum(Num, PrevSum, Sum):- Num > 0, PrevNum is Num - 1,
    NextSum is PrevSum + Num,
    counting_sum(PrevNum, NextSum, Sum).

Caput

Thanks. I hadn't encountered accumulators. It looks like a useful idiom. Having read and understood what an accumulator is, I was able to write a new implementation using one and then check it against your code. I came up with the same thing. Problem: I still get a stack overflow at about counting_sum(350000, X). Any idea why that is? – Guendolen

That's strange. I tried the code I provided with SWI with 3500000 (ten times your figure) and it handles it easily. – Caput

I'm speculating, but GNU Prolog may not do tail optimization in interpreted mode (but SWI Prolog does). @RyanStewart: how about confirming whether you used a compiled gprolog executable, or just the interpreter? – Arroba

@hardmath: Yep, good call. After compiling, it works fine. Thanks guys! – Guendolen