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

[REBOL] Re: Ackermann (was Re: language shoot-out)

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 ]