•    Free Pascal
• Website
• Downloads
• Wiki
• Bugtracker
• Mailing List
•    Lazarus
• Website
• Downloads (Laz+FPC)
• Packages (OPM)
• FAQ
• Wiki
• Bugtracker
• IRC channel
• Developer Blog
• Follow us on Twitter
• Latest SVN
• Mailing List
• Other languages
•    Foundation
• Website
• Project Roadmap
• Getting the Source
• Screenshots

### Bookstore Computer Math and Games in Pascal (preview) Lazarus Handbook (preview only)

### Author Topic: Controlled Stack overflow?  (Read 1778 times)

#### alfware17

• New member
• • Posts: 29 ##### Controlled Stack overflow?
« on: December 29, 2018, 02:21:31 pm »
Hallo,
in the example shown I can see for acker(4,1) the awaited 777 but then it crashes probably in acker(4,2) and because of really confusion in stack and/or memory lack How can I clear that memory and kill all the recursive death bodies I guess?
The optimal would be, it writes also acker(4,2)=777 and so on.

This is a example for a more complex program, that should stay alive also after
a possible stack overflow and save some results and try again recursion with lower deep.

For nmax=3 and mmax=14 it worked so the function seems to be ok. Well and the strings
are only to provoke stack overflow to come some earlier (normally acker(4,1) is done but
to wait for the exception is to long)

Code: Pascal  [Select]
1. program ackermann;
2. {\$mode objfpc}
3. const nmax = 4;
4.       mmax = 4{15};
5. var a,n,m:int64;
6. function acker(n,m: int64):int64;
7. var provoke: array[1..4] of string;
8. begin
9.    if n = 0
10.       then acker:= m + 1
11.       else if m = 0
12.               then acker:= acker( n-1, 1)
13.               else acker:= acker( n-1, acker( n, m-1))
14. end;
15. begin
16.    n:=0; m:=0;
17.    while (n <= nmax) do begin
18.       while (m <= mmax) do begin
19.          try
20.             begin
21.                a:= acker( n, m );
22.             end;
23.          except
24.             begin
25.                a:= 777;
26.             end;
27.          end;
28.          writeln('n=',n,' m=',m,' acker(',n,',',m,')=',a);
29.          inc(m);
30.       end;
31.       inc(n); m:=0;
32.    end;
33. end.

#### jamie

• Hero Member
•     • Posts: 1656 ##### Re: Controlled Stack overflow?
« Reply #1 on: December 29, 2018, 03:02:40 pm »
Use a writable constant at the start of the function, this constant should be inside the function not outside so that
it belongs to the function...

Function Acker(n,m:int64):int64;
Const Nested_Counter:integer = 0;

….
Begin
inc(Nested_Count);
If Nested_Count > ???? Then "Raise an exception"';

//Existing code...
Dec(Nested_Count);
End; ##### Re: Controlled Stack overflow?
« Reply #2 on: December 29, 2018, 05:22:58 pm »
The exception should be done outside of the two while loops, otherwise they can keep repeating and that is slow indeed... so try while while will help a lot.

But there is a huge error in that code nmax = 5 not 4 loops and mmax has the same issue. real programmers start at zero:
Code: Pascal  [Select]
1.    n:=0; m:=0;
2.    while (n <= nmax) do begin
3.       while (m <= mmax) do begin

That is silly code.
Should be:
Code: Pascal  [Select]
1.    n:=0; m:=0;
2.    while (n < nmax) do begin
3.       while (m < mmax) do begin

« Last Edit: December 29, 2018, 05:49:47 pm by Thaddy »
Read the manuals and if you are a professional get a proper education in computer science. Makes the forum a lot cleaner. ##### Re: Controlled Stack overflow?
« Reply #3 on: December 29, 2018, 06:16:34 pm »
Ah, I see. Indeed I suspect a bug here. Valid code (except the loop) but stack corruption. I can reproduce that.
Read the manuals and if you are a professional get a proper education in computer science. Makes the forum a lot cleaner.

#### alfware17

• New member
• • Posts: 29 ##### Re: Controlled Stack overflow?
« Reply #4 on: December 29, 2018, 06:28:57 pm »
The exception should be done outside of the two while loops, otherwise they can keep repeating and that is slow indeed... so try while while will help a lot.

But there is a huge error in that code nmax = 5 not 4 loops and mmax has the same issue. real programmers start at zero:
Code: Pascal  [Select]
1.    n:=0; m:=0;
2.    while (n <= nmax) do begin
3.       while (m <= mmax) do begin

That is silly code.
Should be:
Code: Pascal  [Select]
1.    n:=0; m:=0;
2.    while (n < nmax) do begin
3.       while (m < mmax) do begin

May be a misunderstanding? It should not run 4 times but for all values from 0 to 4, 0 to 4
and it does. Look my output in answer to Jamie. FOR should have been more clear. But ok.

The STOFL should raised more than once because wanted to see, if the programm keeps living,
therefore try for 4,1 and 4,2 and so on.
The reason for crash I found. It was not runtime 202 but runtime 5 - I dont unterstand at all.
Nor understand the fixing by {\$h+}. Seems something wrong with the string without {\$h+}.

Thanks

#### alfware17

• New member
• • Posts: 29 ##### Re: Controlled Stack overflow?
« Reply #5 on: December 29, 2018, 06:43:43 pm »
Use a writable constant at the start of the function, this constant should be inside the function not outside so that
it belongs to the function...

Function Acker(n,m:int64):int64;
Const Nested_Counter:integer = 0;

….
Begin
inc(Nested_Count);
If Nested_Count > ???? Then "Raise an exception"';
//Existing code...
Dec(Nested_Count);
End;

Hi Jamie,
thanks, now it runs   - look my protocol.

Code: Pascal  [Select]
1. Running "c:\bernd\pascal\acker.exe "
2. n=0 m=0 acker(0,0)=1
3. n=0 m=1 acker(0,1)=2
4. n=0 m=2 acker(0,2)=3
5. n=0 m=3 acker(0,3)=4
6. n=0 m=4 acker(0,4)=5
7. n=1 m=0 acker(1,0)=2
8. n=1 m=1 acker(1,1)=3
9. n=1 m=2 acker(1,2)=4
10. n=1 m=3 acker(1,3)=5
11. n=1 m=4 acker(1,4)=6
12. n=2 m=0 acker(2,0)=3
13. n=2 m=1 acker(2,1)=5
14. n=2 m=2 acker(2,2)=7
15. n=2 m=3 acker(2,3)=9
16. n=2 m=4 acker(2,4)=11
17. n=3 m=0 acker(3,0)=5
18. n=3 m=1 acker(3,1)=13
19. n=3 m=2 acker(3,2)=29
20. n=3 m=3 acker(3,3)=61
21. n=3 m=4 acker(3,4)=125
22. n=4 m=0 acker(4,0)=13
23. 1000000 x y
24. 2000000 xx y
25. 3000000 xxx y
26. 4000000 xxxx y
27. n=4 m=1 acker(4,1)=777
28. 5000000 xxxxx y
29. 6000000 xxxxxx y
30. 7000000 xxxxxxx y
31. 8000000 xxxxxxxx y
32. n=4 m=2 acker(4,2)=777
33. 9000000 xxxxxxxxx y
34. 10000000 xxxxxxxxxx y
35. 11000000 xxxxxxxxxxx y
36. 12000000 xxxxxxxxxxxx y
37. n=4 m=3 acker(4,3)=777
38. 13000000 xxxxxxxxxxxxx y
39. 14000000 xxxxxxxxxxxxxx y
40. 15000000 xxxxxxxxxxxxxxx y
41. 16000000 xxxxxxxxxxxxxxxx y
42. n=4 m=4 acker(4,4)=777
43.

And my changed code:
Code: Pascal  [Select]
1. program ackermann;
2. {\$mode objfpc} {\$h+}
3. uses sysutils;
4. type EMyError = class (Exception)
6.      end;
7. constructor EMyError.Create;
8. begin
9.    inherited Create('Provoziere STOFL');
10. end;
11. const nmax = 4;
12.       mmax = 4{15};
13. var a,n,m:int64;
14. function acker(n,m: int64):int64;
15. const zahl: int64 = 0;
16. const abbruch: int64 = 0;
17. const kette: string = '';
18. var   feld: array[1..200] of string;
19. begin
20.    inc(zahl); {feld:='';}
21.    if abbruch > 3 then begin
22.       abbruch:=0; raise EMyError.Create;
23.    end;
24.    if zahl mod 1000000 = 0
25.       then begin
26.          inc(abbruch);
27.          kette:=kette+'x';
28.          feld:= feld + 'y';
29.          writeln(zahl,' ',kette,' ',feld);
30.       end;
31.    if n = 0
32.       then acker:= m + 1
33.       else if m = 0
34.               then acker:= acker( n-1, 1)
35.               else acker:= acker( n-1, acker( n, m-1))
36. end;
37. begin
38.    n:=0; m:=0;
39.    while (n <= nmax) do begin
40.       while (m <= mmax) do begin
41.          try
42.             begin
43.                a:= acker( n, m );
44.             end;
45.          except
46.             begin
47.                a:= 777;
48.             end;
49.          end;
50.          writeln('n=',n,' m=',m,' acker(',n,',',m,')=',a);
51.          inc(m);
52.       end;
53.       inc(n); m:=0;
54.    end;
55. end.
56.

BUT I dont understand that typed const.
They live forever and never die? I assumed they should only belong to a special Acker function? Why to all zahl and kette will never be reset? For me this a global behaviour, I dont understand.
The strings feld declared by VAR will only exist in a special Acker functions as it should. Anyway.

BTW. The reason for the crash was a runtime 5. Probably nothing with garbage. I fixed it now by adding
{\$h+} randomly by experimenting with the strings. Without the compiler switch Pascal String and runtime error.
With {\$h+} no crash and additionally no assumed STOFL (had to build my own on your proposal)

« Last Edit: December 29, 2018, 06:45:56 pm by alfware17 »

#### lucamar ##### Re: Controlled Stack overflow?
« Reply #6 on: December 29, 2018, 07:11:27 pm »
BUT I dont understand that typed const.
They live forever and never die? I assumed they should only belong to a special Acker function? Why to all zahl and kette will never be reset? For me this a global behaviour, I dont understand.

From the Language Reference Guide (section 2.2 Typed Constants):
Quote
Local typed constants are also initialized at program start. If their value was changed during previous invocations of the function, they will retain their changed value, i.e. they are not initialized each time the function is invoked.

Effectively, they behave as if they were global but their scope is local.
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) Lazarus 1.8.4 & 2.0.2 w/FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

#### Bart

• Hero Member
•     • Posts: 3452 ##### Re: Controlled Stack overflow?
« Reply #7 on: December 30, 2018, 05:17:37 pm »
Here's how far I got:

Code: Pascal  [Select]
1. program ack;
2. //{\$MAXSTACKSIZE \$7FFFFFFF} //Windows cannot run the program then (32-bit)
3. {\$mode objfpc}
4.
5. uses
6.   SysUtils;
7.
8. var
9.   Calls: UInt64;
10.   MaxDepth: UInt64;
11.   Depth: UInt64;
12.
13. function Ackerman(m,n: Integer): UInt64;
14. begin
15.    Inc(Depth);
16.    Inc(Calls);
17.    if (Depth > MaxDepth) Then MaxDepth := Depth;
18.    if m = 0 then
19.      Result := UInt64(n) + 1
20.    else
21.    begin
22.      if n = 0 then
23.        Result := Ackerman(m-1, 1)
24.      else
25.        Result := Ackerman(m-1, Ackerman(m, n-1));
26.    end;
27.    Dec(Depth);
28. end;
29.
30. const
31.   mMax = 4;
32.   nMax = 17;//15;
33.
34. var
35.   m,n: integer;
36.   Res: Int64;
37.   T0: TDateTime;
38. begin
39.   for m := 4 to mMax do
40.   begin
41.     for n := 2 to nMax do
42.     begin
43.       Calls := 0;
44.       MaxDepth := 0;
45.       Depth := 0;
46.       T0 := Now;
47.       repeat until (Now > T0); //wait until next clock-tick
48.       T0 := Now;
49.       try
50.         Res := Ackerman(m,n);
51.         writeln(format('Ackerman(%d,%2d) = %10u  [Calls = %14u,  MaxDepth = %8u,  Time = %s]',[m,n,Res,Calls,MaxDepth,TimeToStr(Now-T0)]));
52.       except
53.         on E: Exception do
54.         begin
55.           writeln(format('Ackerman(%d,%2d) raised exception with:  Calls = %14u,  MaxDepth = %8u, after %s.',[m,n,Calls,MaxDepth,TimeToStr(Now-T0)]));
56.           writeln(format('%s: %s',[E.ClassName,E.Message]));
57.           Break;
58.         end;
59.       end;
60.     end;
61.     writeln;
62.   end;
63. end.

Output:
Code: [Select]
`C:\Users\Bart\LazarusProjecten\ConsoleProjecten\fun\ackerman>ackAckerman(0, 0) =          1  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 1) =          2  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 2) =          3  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 3) =          4  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 4) =          5  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 5) =          6  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 6) =          7  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 7) =          8  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 8) =          9  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0, 9) =         10  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,10) =         11  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,11) =         12  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,12) =         13  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,13) =         14  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,14) =         15  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,15) =         16  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(0,16) =         17  [Calls =              1,  MaxDepth =        1,  Time = 00:00:00]Ackerman(1, 0) =          2  [Calls =              2,  MaxDepth =        2,  Time = 00:00:00]Ackerman(1, 1) =          3  [Calls =              4,  MaxDepth =        3,  Time = 00:00:00]Ackerman(1, 2) =          4  [Calls =              6,  MaxDepth =        4,  Time = 00:00:00]Ackerman(1, 3) =          5  [Calls =              8,  MaxDepth =        5,  Time = 00:00:00]Ackerman(1, 4) =          6  [Calls =             10,  MaxDepth =        6,  Time = 00:00:00]Ackerman(1, 5) =          7  [Calls =             12,  MaxDepth =        7,  Time = 00:00:00]Ackerman(1, 6) =          8  [Calls =             14,  MaxDepth =        8,  Time = 00:00:00]Ackerman(1, 7) =          9  [Calls =             16,  MaxDepth =        9,  Time = 00:00:00]Ackerman(1, 8) =         10  [Calls =             18,  MaxDepth =       10,  Time = 00:00:00]Ackerman(1, 9) =         11  [Calls =             20,  MaxDepth =       11,  Time = 00:00:00]Ackerman(1,10) =         12  [Calls =             22,  MaxDepth =       12,  Time = 00:00:00]Ackerman(1,11) =         13  [Calls =             24,  MaxDepth =       13,  Time = 00:00:00]Ackerman(1,12) =         14  [Calls =             26,  MaxDepth =       14,  Time = 00:00:00]Ackerman(1,13) =         15  [Calls =             28,  MaxDepth =       15,  Time = 00:00:00]Ackerman(1,14) =         16  [Calls =             30,  MaxDepth =       16,  Time = 00:00:00]Ackerman(1,15) =         17  [Calls =             32,  MaxDepth =       17,  Time = 00:00:00]Ackerman(1,16) =         18  [Calls =             34,  MaxDepth =       18,  Time = 00:00:00]Ackerman(2, 0) =          3  [Calls =              5,  MaxDepth =        4,  Time = 00:00:00]Ackerman(2, 1) =          5  [Calls =             14,  MaxDepth =        6,  Time = 00:00:00]Ackerman(2, 2) =          7  [Calls =             27,  MaxDepth =        8,  Time = 00:00:00]Ackerman(2, 3) =          9  [Calls =             44,  MaxDepth =       10,  Time = 00:00:00]Ackerman(2, 4) =         11  [Calls =             65,  MaxDepth =       12,  Time = 00:00:00]Ackerman(2, 5) =         13  [Calls =             90,  MaxDepth =       14,  Time = 00:00:00]Ackerman(2, 6) =         15  [Calls =            119,  MaxDepth =       16,  Time = 00:00:00]Ackerman(2, 7) =         17  [Calls =            152,  MaxDepth =       18,  Time = 00:00:00]Ackerman(2, 8) =         19  [Calls =            189,  MaxDepth =       20,  Time = 00:00:00]Ackerman(2, 9) =         21  [Calls =            230,  MaxDepth =       22,  Time = 00:00:00]Ackerman(2,10) =         23  [Calls =            275,  MaxDepth =       24,  Time = 00:00:00]Ackerman(2,11) =         25  [Calls =            324,  MaxDepth =       26,  Time = 00:00:00]Ackerman(2,12) =         27  [Calls =            377,  MaxDepth =       28,  Time = 00:00:00]Ackerman(2,13) =         29  [Calls =            434,  MaxDepth =       30,  Time = 00:00:00]Ackerman(2,14) =         31  [Calls =            495,  MaxDepth =       32,  Time = 00:00:00]Ackerman(2,15) =         33  [Calls =            560,  MaxDepth =       34,  Time = 00:00:00]Ackerman(2,16) =         35  [Calls =            629,  MaxDepth =       36,  Time = 00:00:00]Ackerman(3, 0) =          5  [Calls =             15,  MaxDepth =        7,  Time = 00:00:00]Ackerman(3, 1) =         13  [Calls =            106,  MaxDepth =       15,  Time = 00:00:00]Ackerman(3, 2) =         29  [Calls =            541,  MaxDepth =       31,  Time = 00:00:00]Ackerman(3, 3) =         61  [Calls =           2432,  MaxDepth =       63,  Time = 00:00:00]Ackerman(3, 4) =        125  [Calls =          10307,  MaxDepth =      127,  Time = 00:00:00]Ackerman(3, 5) =        253  [Calls =          42438,  MaxDepth =      255,  Time = 00:00:00]Ackerman(3, 6) =        509  [Calls =         172233,  MaxDepth =      511,  Time = 00:00:00]Ackerman(3, 7) =       1021  [Calls =         693964,  MaxDepth =     1023,  Time = 00:00:00]Ackerman(3, 8) =       2045  [Calls =        2785999,  MaxDepth =     2047,  Time = 00:00:00]Ackerman(3, 9) =       4093  [Calls =       11164370,  MaxDepth =     4095,  Time = 00:00:00]Ackerman(3,10) =       8189  [Calls =       44698325,  MaxDepth =     8191,  Time = 00:00:00]Ackerman(3,11) =      16381  [Calls =      178875096,  MaxDepth =    16383,  Time = 00:00:00]Ackerman(3,12) =      32765  [Calls =      715664091,  MaxDepth =    32767,  Time = 00:00:03]Ackerman(3,13) =      65533  [Calls =     2862983902,  MaxDepth =    65535,  Time = 00:00:15]Ackerman(3,14) =     131069  [Calls =    11452590817,  MaxDepth =   131071,  Time = 00:02:04]Ackerman(3,15) =     262141  [Calls =    45811673828,  MaxDepth =   262143,  Time = 00:06:41]Ackerman(3,16) =     524285  [Calls =   183249316583,  MaxDepth =   524287,  Time = 00:36:36]Ackerman(3,17) raised exception with:  Calls =   194331574808,  MaxDepth =   598725, after 00:40:43.EStackOverflow: Stack overflowAckerman(4, 0) =         13  [Calls =            107,  MaxDepth =       16,  Time = 00:00:00]Ackerman(4, 1) =      65533  [Calls =     2862984010,  MaxDepth =    65536,  Time = 00:00:16]Ackerman(4, 2) raised exception with:  Calls =   186272023197,  MaxDepth =   598725, after 00:38:44.EStackOverflow: Stack overflow`
Calls is the tocal calls to Ackerman() made, MaxDepth is the maximum recursive depth in that calculation.
It fails after 598725 copy's on the stack.

For n=3 the MaxDepth seems to be 2^(n+3)-1, so Ackerman(3,18) should need at some point have (2^20)-1 = 1048575 copies on the stack ...

What would be the rule for MaxDepth for Ackerman(4,n)?

Bart
« Last Edit: December 30, 2018, 05:24:06 pm by Bart »

#### Bart

• Hero Member
•     • Posts: 3452 ##### Re: Controlled Stack overflow?
« Reply #8 on: December 31, 2018, 02:00:30 pm »
I was wondering if changing stacksize would help.
Does anybody know the largest stacksize allowed on win32, and waht the default setting is?

Bart

#### marcov ##### Re: Controlled Stack overflow?
« Reply #9 on: December 31, 2018, 02:05:13 pm »
I was wondering if changing stacksize would help.
Does anybody know the largest stacksize allowed on win32, and waht the default setting is?

Default is 16MB (see compiler/systems/i_win.pas, most OS specific settings are there in i_ files  or t_ files for more linker script stuff)

The trouble is that stack overflow checking is meant for graceful exits, not full recovery. ##### Re: Controlled Stack overflow?
« Reply #10 on: December 31, 2018, 02:13:08 pm »
[The trouble is that stack overflow checking is meant for graceful exits, not full recovery.
Indeed. It indicates something very wrong with your design. Even raising the stack limits would possibly get you into trouble at some point.
The nasty bit of recursion without bail-out.(Known and taught)
« Last Edit: December 31, 2018, 02:17:28 pm by Thaddy »
Read the manuals and if you are a professional get a proper education in computer science. Makes the forum a lot cleaner.

#### Bart

• Hero Member
•     • Posts: 3452 ##### Re: Controlled Stack overflow?
« Reply #11 on: December 31, 2018, 03:03:08 pm »
Default is 16MB (see compiler/systems/i_win.pas, most OS specific settings are there in i_ files  or t_ files for more linker script stuff)

The trouble is that stack overflow checking is meant for graceful exits, not full recovery.

I just wanted to see if I can get the stacksize big enough to get one extra answer (Ackerman(3,17)?).

Bart

#### marcov ##### Re: Controlled Stack overflow?
« Reply #12 on: December 31, 2018, 03:25:21 pm »
I just wanted to see if I can get the stacksize big enough to get one extra answer (Ackerman(3,17)?).

Just try then. WIth win32 and win64.

Or spend the 5 minutes on the internet to find an iterative algorithm?

#### Bart

• Hero Member
•     • Posts: 3452 ##### Re: Controlled Stack overflow?
« Reply #13 on: December 31, 2018, 05:11:01 pm »
Or spend the 5 minutes on the internet to find an iterative algorithm?

That's going to be a challenge: https://en.wikipedia.org/wiki/Ackermann_function#Proof_that_the_Ackermann_function_is_not_primitive_recursive Bart @Bart... you made me smile.  and what I was pointing to.