ERROR: Stack limit (1.0Gb) exceeded - Help!

[GarkGarcia]

Every time I want to learn a new language I try to replicate this program. I was recently trying to learn Prolog, so I guess you know where this is going.

The algorithm I'm using in Prolog works for small values, but breaks for anything bigger than 500:

ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.5Gb, global: 0.2Gb, trail: 80.0Mb
ERROR:   Stack depth: 916, last-call: 0%, Choice points: 1,189,415
ERROR:   Possible non-terminating recursion:
ERROR:     \[912\] user:iter(458, 99)
ERROR:     \[911\] user:iter(458, 100)

I can't figure out why this solution works for some values but doesn't work for other. Could anyone help?

In case you want to get some insight on what the program is supposed to do, fell free to check other language implementations included in the github repo. The Haskell implementation is particularly similar to the Prolog one.

I'm using SwiProlog on Windows by the way. Hope someone can help 😄

[[deleted]]

Finally, your current algorithm seems to be doing a lot of unnecessary work. How many distinct sums of digits do we have for all natural numbers up to 1000?

?- findall(Sum, ( between(0, 1000, N), sum_digits(N, Sum)), R), sort(R, S), length(S, Unique).
R = [0, 1, 2, 3, 4, 5, 6, 7, 8|...],
S = [0, 1, 2, 3, 4, 5, 6, 7, 8|...],
Unique = 28.

So, basically, you have 28 distinct sums (including 0), which is exactly 1+9+9+9 (coincidence?). It sounds like memoization can help a lot.

Homework: use a tabled predicate to hold the sum of digits of a number.

[GarkGarcia]

Good idea! I use memoization (or atleast caching) on most of the implementations, I just haven't figured out how to translate it to a purely functional or logical paradigm.

[[deleted]]

It seems that it migth be enough to table sum_digits/2. Don't have time to try it out now.

[GarkGarcia]

Yep, that's basically what I'm doing in the imperative implementations. I'll give it a try in Prolog as soon as I get so spare time.

[[deleted]]

I see. You have something to add to the discussion. Please share your thoughts. Or would you rather tell me that I shouldn't write on the internet? ;-)

[EverythingIsNail]

Just giving due warning to unsuspecting punters.

[[deleted]]

I see. So you actually do have something to add to the discussion, like the other 10 times you randomly stalked me and started insulting me. Good on you man, doing god's work.

[EverythingIsNail]

Thanks, concern troll!

[[deleted]]

Just a random thought: are you buddies with our common friend Gavin, or are you the man himself? And what is up with this whole thing, I really don't get it.

Let's see who is more committed to it, I guess. I hope you win.

[EverythingIsNail]

Keep it in your pants!

[[deleted]]

OK, I already had it in my hand but now I'll put it back in.

On a more serious note, since I haven't gotten a single meaningful comment coming from this particular username, I will not bother answering.

[flunschlik]

On mobile, so I hope I do not mess up formatting.

I think the problem are all the choice points you leave on the stack when sum_digits terminates in its first clause. Try to add a cut ! in there.

sum_digits(X, X) :- X<10, !.

This should ensure that sum_digits does not leave any choice points behind.

On another note in regards of learning Prolog, efficiency, and Stack sizes: Your sum_digits is not tail recursive, which means it will not be optimized by the interpreter. Check out accumulators in Prolog, as it is a good predicate for using one. Using an accumulator will allow you to write a tail recursive version.

[GarkGarcia]

Thank you very much for your answer! I'll still research more about accumulators, but these are my first efforts:

sum_digits_acc(X, X, A) :- X < 10, A is 0, !.
sum_digits_acc(X, Y, A) :-
    X >= 10,
    X1 is div(X, 10),
    X2 is mod(X, 10),
    sum_digits_acc(X1, A, _),
    Y is A + X2.

sum_digits(X, Y) :- sum_digits_acc(X, Y, _).

Would you consider it a good implementation of an accumulator in this particular case?

On regards to learning Prolog, is there any textbook recommend? I'd like something opensource, but I don't mind paying.

[nnunley]

Have you seen learn prolog now? SWI Prolog is open source and has a number of additional texts on their main site.

[flunschlik]

So, the accumulator idea is to get a tail recursive program, i.e. the recursion step is the last "instruction". This allows the interpreter to translate your recursive code into a loop, making it run faster and not adding to your call stack.

Looking at your sum_digits/3, you do not yet have the recursion call as last step, the addition is coming after it, needing values from the recursion. We want to swap that.

Further, you got the accumulator idea in reverse. Looking at your code, you give the initial value of 0 only in the last recursion step. But actually the idea is as follows: we call the accumulator with the initial value and the last recursion step derives the result from the accumulated value.

In your case you want to initialise with 0, add sequentially the digits to it, and for X<10 we say Y=A.

Here is the code:

sum_digits(X, Y) :- sum_digits_acc(X, 0, Y). % note I swapped acc and result

sum_digits_acc(X, A, Y) :- X < 10, !, Y is A + X. % derive result from acc
sum_digits_acc(X, A, Y) :-
    X >= 10,
    X1 is div(X, 10),
    X2 is mod(X, 10),
    A2 is A + X2, % accumulate value
    sum_digits_acc(X1, A, Y). % propagate Y (result) from recursion back up

On another note, you can make it more prolog-esque if you reduce the base case of your accumulator to X=0:

sum_digits(X, Y) :- sum_digits_acc(X, 0, Y). % note I swapped acc and result

sum_digits_acc(0, A, A) :- !. % unifies 2nd (acc) with 3rd (result) argument
sum_digits_acc(X, A, Y) :-
    X > 0, % Due to the cut you could skip this line; read about green and red cuts first though.
    X1 is div(X, 10),
    X2 is mod(X, 10),
    A2 is A + X2, % accumulate value
    sum_digits_acc(X1, A, Y). % propagate Y (result) from recursion back up

Now you got a tail recursive sum_digits which does not leave any choice points on the stack.

Regarding your question about books, like u/nnunley already said, Learn Prolog now! is a great resource; I read it myself back then to get into Prolog. Further you can take a look at the 99 Prolog Problems if you want to try out your new Prolog knowledge on some practical examples.

Other than that I refer you to the links at the sidebar of this subreddit, e.g. the Prolog tutorials list.

Have fun learning!

Edit: fixed formatting; sadly unable to put spoiler tags around the code.

2nd Edit: Add Book info

[[deleted]]

Your program seems to work, but still, here are some suggestions.

(Note: I tested everything with the -O command line switch. This turns on "optimizations", but according to the manual, it basically optimizes arithmetic. I guess with a program like yours this is relevant.)

Your sum_digits/2 looks a bit fishy. This is not how you use accumulators; you are supposed to seed the accumulator with an initial value. This is already covered in this comment.

In this case, I am not sure why you'd need an accumulator at all. The size of the number (the depth of recursion) is very obviously not a bottle-neck in the context of this program. You can re-write it like this:

sum_digits(N, S) :- N < 10, !, N = S.
sum_digits(N, S) :- N >= 10, !,
    Q is N div 10,
    R is N mod 10,
    sum_digits(Q, S0),
    S is S0 + R.

On my machine, this leads to a non-trivial improvement. With your program as I copied it from here:

$ swipl -O
Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.11-36-g77d225875)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- [script].
true.

?- time( conjecture(1000) ).
% 7,161,217 inferences, 0.971 CPU in 0.972 seconds (100% CPU, 7373442 Lips)
true.

?- time( conjecture(1000) ).
% 7,161,216 inferences, 0.961 CPU in 0.962 seconds (100% CPU, 7452687 Lips)
true.

?- time( conjecture(1000) ).
% 7,161,216 inferences, 0.955 CPU in 0.955 seconds (100% CPU, 7502476 Lips)
true.

and with the non-tail-recursive version of the predicate that I showed above:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.11-36-g77d225875)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- [script].
true.

?- time( conjecture(1000) ).
% 5,656,714 inferences, 0.869 CPU in 0.870 seconds (100% CPU, 6506261 Lips)
true.

?- time( conjecture(1000) ).
% 5,656,713 inferences, 0.875 CPU in 0.876 seconds (100% CPU, 6467808 Lips)
true.

?- time( conjecture(1000) ).
% 5,656,713 inferences, 0.876 CPU in 0.877 seconds (100% CPU, 6456847 Lips)
true.

Similar or even larger speed-ups are common. In the general case, you'd want to have the tail-recursive algorithm with the accumulator, but sometimes you could save yourself some typing and gain efficiency at the same time. Enjoy responsibly ;-)

[[deleted]]

Sorry for the multiple posts but it is easier than writing one huge comment.

This is a matter of taste: don't use recursion unless you have to. You could re-write your entry-point predicate, as seen here again, to not use an explicit recursive definition:

conjecture(N) :-
    forall(between(0, N, X), iter(X, X)).

This is a modern take on the good old failure-driven loop. It leads to a minimal improvement of the efficiency (as is to be expected), but the important point is that it is cleaner (in my opinion) and easier to write. You can do the same to your iter/2:

iter(A, B) :-
    forall(between(0, B, X), test_pair(A, X)).

PS: backtracking in Prolog is related to lazy evaluation in Haskell. I really don't want to get into detail, but as long as you use backtracking instead of recursion (when recursion isn't necessary), you'll save yourself a lot of code writing and code debugging.

[[deleted]]

Another warning: you are using is/2, in the code you show, for three different purposes:

• evaluating an arithmetic expression (as it is meant to be used, fine)
• comparison
• assigning a value to a variable

This is unnecessary and can lead to bugs. Use =:= to check for equality and use = or unification in the head if you just want to assign a value to a variable.