[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 ]