Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Ackermann (was Re: language shoot-out)

 [1/9] from: joel:neely:fedex at: 5-Nov-2002 10:06


Hi, Carl, et al,
> > > > On Mon, 4 Nov 2002, Carl at REBOL wrote: > > > > > How deep is the stack at 7? > > > >
FWIW I get the same results with w2k:
>> ackermann/run
1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 Failure at depth 709 / 709 after 250362 Failure at depth 709 / 709 after 249577 but a more depressing set of results with Mac OS X:
>> ackermann/run
1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 Failure at depth 322 / 322 after 51405 Failure at depth 322 / 322 after 50887 Failure at depth 321 / 322 after 50886 which leads me to wonder why the stack depth limit is less than half of that on wxx? -jn- Joel Neely wrote:
> Hi, Tom, > Could you please post the code which you used to generate that
<<quoted lines omitted: 44>>
> Failure at depth 709 / 709 after 249577 > (on w95, but YMMVDOP!)
-- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446

 [2/9] from: carl::s::rebol::com at: 5-Nov-2002 16:08


Are you saying that the stack frame was only 709 deep? That's hard to believe, because recursion in REBOL is only 3 C frames per REBOL frame. At 10:06 AM 11/5/02 -0600, you wrote:

 [3/9] from: lmecir:mbox:vol:cz at: 6-Nov-2002 8:57


Hi Carl and Joel,
> Are you saying that the stack frame was only 709 deep? That's hard to > believe, because recursion in REBOL is only 3 C frames per REBOL frame.
The trouble is, that Rebol uses stack when calling the EITHER function, which can make the stack roughly thrice as deep as computed using only Ackermann call counting. Regards -L

 [4/9] from: joel:neely:fedex at: 6-Nov-2002 6:33


Hi, Carl, Carl at REBOL wrote:
> Are you saying that the stack frame was only 709 deep? That's > hard to believe, because recursion in REBOL is only 3 C frames > per REBOL frame. >
I really can't comment on that point, as I don't have access to the source for the REBOL interpreter! ;-) That's why I included the source for the version of ackermann that generated those numbers; if there's anything wrong with the source (or my interpretation of the results) I'd be delighted to have any corrections. I'm simply initializing a counter (CURR_DEPTH) to 0 prior to evaluating the ACK function, adding 1 immediately upon entry to ACK, and subtracting 1 immediately before the final (result) expression. When the interpreter throws an error
>> ackermann/ack 3 7
** Internal Error: Stack overflow ** Near: result: either m = 0 I interpret the current value of CURR_DEPTH as the net number of times that ACK has been entered but not exited. Of course I'll be grateful for any additional light you can shed on this! -jn- PS: /View produced exactly the same result on my w95 test box.
> > > Here's my test harness ... > > >
<<quoted lines omitted: 47>>
> > > Failure at depth 709 / 709 after 249577 > > >
-- ; Joel Neely joeldotneelyatfedexdotcom REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] { | e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]

 [5/9] from: joel:neely:fedex at: 6-Nov-2002 7:42


Hi, Ladislav, Carl, et al. Thank you, Ladislav! Ladislav Mecir wrote:
> The trouble is, that Rebol uses stack when calling the EITHER > function, which can make the stack roughly thrice as deep as > computed using only Ackermann call counting. >
Here is a revised version of my tester ... 8<---------------------------------------------------------------- REBOL [] ackermann: make object! [ curr_depth: max_depth: tot_evals: 0 ack1: func [m [integer!] n [integer!] /local result] [ max_depth: max max_depth curr_depth: curr_depth + 1 tot_evals: tot_evals + 1 result: either m = 0 [ n + 1 ][ either n = 0 [ ack1 m - 1 1 ][ ack1 m - 1 ack1 m n - 1 ] ] curr_depth: curr_depth - 1 result ] ack2: func [m [integer!] n [integer!] /local result] [ max_depth: max max_depth curr_depth: curr_depth + 1 tot_evals: tot_evals + 1 if m = 0 [ curr_depth: curr_depth - 1 return n + 1 ] if n = 0 [ result: ack2 m - 1 1 curr_depth: curr_depth - 1 return result ] result: ack2 m - 1 ack2 m n - 1 curr_depth: curr_depth - 1 result ] ack3: func [m [integer!] n [integer!] /local result] [ max_depth: max max_depth curr_depth: curr_depth + 1 tot_evals: tot_evals + 1 either all [m > 0 n > 0] [ result: ack3 m - 1 ack3 m n - 1 ][ either m = 0 [ result: n + 1 ][ result: ack3 m - 1 1 ] ] curr_depth: curr_depth - 1 result ] ack4: func [m [integer!] n [integer!] /local result] [ max_depth: max max_depth curr_depth: curr_depth + 1 tot_evals: tot_evals + 1 result: any [ all [m = 0 n + 1] all [n = 0 ack4 m - 1 1] ack4 m - 1 ack4 m n - 1 ] curr_depth: curr_depth - 1 result ] ack5: func [m [integer!] n [integer!] /local result] [ max_depth: max max_depth curr_depth: curr_depth + 1 tot_evals: tot_evals + 1 if m = 0 [ curr_depth: curr_depth - 1 return n + 1 ] result: either n = 0 [ 1 ][ ack5 m n - 1 ] result: ack5 m - 1 result curr_depth: curr_depth - 1 result ] ackfuncs: [ack1 ack2 ack3 ack4 ack5] run: func [/local ackfunc][ foreach ackword ackfuncs [ ackfunc: get ackword repeat i 8 [ curr_depth: max_depth: tot_evals: 0 if error? try [ print [i ackfunc 3 i max_depth tot_evals] ][ print [ "Failure at depth" curr_depth "/" max_depth "after" tot_evals ] ] ] ] ] recur: func [n [integer!]] [ recur curr_depth: n + 1 ] stress: func [] [ recur curr_depth: 1 ] ] 8<---------------------------------------------------------------- ... and the results from it ...
>> ackermann/run
1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 Failure at depth 709 / 709 after 250361 Failure at depth 708 / 708 after 248795 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 7 1021 1023 693964 Failure at depth 1376 / 1376 after 942795 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 Failure at depth 935 / 935 after 530602 Failure at depth 936 / 936 after 528914 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 Failure at depth 973 / 973 after 595945 Failure at depth 972 / 972 after 594107 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 7 1021 1023 693964 Failure at depth 1250 / 1251 after 797140
>> do %ack.r >> ackermann/stress
** Internal Error: Stack overflow ** Near: recur curr_depth: n + 1
>> ackermann/curr_depth
== 3148 ... showing that "user code" recursion depth is clearly very dependent on internal expression structure. Thanks again, Ladislav, for this valuable lesson! -jn- NOTE: that ACK5 is *not* a valid entry to the shootout, as it does not conform to the "same design" requirement. -- ; Joel Neely joeldotneelyatfedexdotcom REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] { | e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]

 [6/9] from: rotenca:telvia:it at: 6-Nov-2002 22:24


What i do not understand well is why this stops at 1374: ack41: func [m [integer!] n [integer!] /local result f2][ md: max md cd: cd + 1 tot: tot + 1 if m = 0 [cd: cd - 1 return n + 1] if n = 0 [result: ack41 m - 1 1 cd: cd - 1 return result] result: ack41 m - 1 ack41 m n - 1 cd: cd - 1 result ] and this stops at 2181 (ack41 3 9) ack41: func [m [integer!] n [integer!] /local result f2] [ md: max md cd: cd + 1 tot: tot + 1 if m = 0 [cd: cd - 1 return n + 1] if n = 0 [result: ack41 m - 1 1 cd: cd - 1 return result] f2: ack41 m n - 1 result: ack41 m - 1 f2 cd: cd - 1 result ] --- Ciao Romano

 [7/9] from: joel:neely:fedex at: 6-Nov-2002 16:32


Hi, Romano, WARNING: Uneducated guess ahead... Romano Paolo Tenca wrote:
> What i do not understand well is why this stops at 1374: >
...
> result: ack41 m - 1 ack41 m n - 1
...
> and this stops at 2181 (ack41 3 9) >
...
> f2: ack41 m n - 1 > result: ack41 m - 1 f2
I might guess that in the earlier case, the left-hand eval of ACK41 is in some sense pending while the right-hand eval is being pursued, and thereby consuming some resources. In the second case, the eval of ACK41 M N - 1 is allowed to complete (with the result cached) prior to initiating the second eval of ACK41. Concurrent vs. serial. -jn- -- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446

 [8/9] from: g:santilli:tiscalinet:it at: 7-Nov-2002 0:41


Hi Romano, On Wednesday, November 6, 2002, 10:24:44 PM, you wrote: RPT> What i do not understand well is why this stops at 1374: [...] RPT> and this stops at 2181 (ack41 3 9) [...] The intepreter is probably consuming stack while collecting arguments. So, in the first case ack is called while processing the arguments for another call to ack; in the second, the two calls are distinct. Regards, Gabriele. -- Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r

 [9/9] from: joel:neely:fedex at: 8-Nov-2002 10:36


Hello, all, For the sake of complete-(er)-ness, I've rerun the same test on my Sun E4500 account, with the following results:
>> ackermann/run
1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 Failure at depth 274 / 274 after 43341 Failure at depth 274 / 274 after 43272 Failure at depth 274 / 274 after 43207 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 6 509 511 172233 Failure at depth 616 / 616 after 193963 Failure at depth 616 / 616 after 193554 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 Failure at depth 379 / 379 after 72951 Failure at depth 379 / 379 after 71977 Failure at depth 379 / 379 after 71977 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 Failure at depth 415 / 415 after 92622 Failure at depth 415 / 415 after 92622 Failure at depth 415 / 415 after 91993 1 13 15 106 2 29 31 541 3 61 63 2432 4 125 127 10307 5 253 255 42438 Failure at depth 478 / 478 after 140375 Failure at depth 477 / 478 after 139495 Failure at depth 478 / 478 after 138617
>> ackermann/stress
** Internal Error: Stack overflow ** Near: recur curr_depth: n + 1
>> ackermann/curr_depth
== 1277 The results from running this test on w2k, w95, OS X, and Solaris leave me with the impression that the "stack" we're instrumenting here may not be a data structure managed by the interpreter, but rather an artifact of C implementation on a platform-specific basis. Someone with more inside info care to confirm or deny? -jn- Joel Neely wrote:
... [running on w2k and w95] ...
> >> ackermann/run > 1 13 15 106
<<quoted lines omitted: 43>>
> >> ackermann/curr_depth > == 3148
-- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted