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 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 ... > > > > > > 8<---------------------------------------------------------------------- > > > ackermann: make object! [ > > > curr_depth: max_depth: tot_evals: 0 > > > > > > ack: 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 [ > > > ack m - 1 1 > > > ][ > > > ack m - 1 ack m n - 1 > > > ] > > > ] > > > curr_depth: curr_depth - 1 > > > result > > > ] > > > > > > run: func [][ > > > repeat i 8 [ > > > curr_depth: max_depth: tot_evals: 0 > > > if error? try [ > > > print [i ack 3 i max_depth tot_evals] > > > ][ > > > print [ > > > "Failure at depth" curr_depth "/" max_depth > > > "after" tot_evals > > > ] > > > ] > > > ] > > > ] > > > ] > > > > > > 8<---------------------------------------------------------------------- > > > > > > ... and I get these results ... > > > > > > >> 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 > > >
-- ; 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 ]