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

[REBOL] Re: language shoot-out :-)

From: jan:skibinski:sympatico:ca at: 5-Nov-2002 9:38

[Joel Neely complained: " I started to work up REBOL versions to submit a while back; I got frustrated when the ackermann blew up with stack overflow at 7 (the test calls for 8)." Carl at Rebol asked how deep the stack was, then Tom Conlin wrote:
> I would geuss ack 3 7 blows up close to where ack 3 8 does > > %ack 3 8 > ... > 323990 > 323991 > 323992 > 323993 > 323994 > 323995 > ** Internal Error: Stack overflow > ** Near: ack (x - 1) 1
] ============================================= Cheating and passing with flying colors: {Ackerman function for m = 3} a3: func[n][either n = 0 [5][2 ** (n + 2) + a3 (n - 1)]] a3 8 == 2045 Jan P.S. See the longer explanation below ============================================== Well, the Ackerman function is a sick function, specificly designed to defeat the tail recursion elimination.. But the problem is that sooner or later something will overflow - not necessarily stack ... it can be a "number overflow" - unless some Big Number library is used instead of floats. One can easily sail by the dangerous waters of ack 3 7 by redesigning the 'ack a bit: a0: func[n][ n + 1] ; -- [1 2 3... a1: func[n][ n + 2] ; -- [2 3 4.. a2: func n][2 * n + 3] ; -- [3 5 7 9.. a3: func[n][either n = 0 [5][2 ** (n + 2) + a3 (n - 1)]] map :a3 ..[0 13] == [5 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765 65533] a3 1020 == 8.98846567431158E+307 That's as far as we can go with 'a3 before we hit 2 ** 1023 limit. But look how perverse ack becomes for m = 4; this has nothing to do with the stack problem, but with the math overflow problem: From recursive definition (in Haskell): ---------------------------- ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack m n = ack (m-1) (ack m (n-1)) ---------------------------------- Few first entries from a4 family: ack 4 0 = ack 3 1 = 13 ; from the list produced above ack 4 1 = ack 3 (ack 4 0) = ack 3 13 = 65533 ack 4 2 = ack 3 (ack 4 1) = ack 3 65533 ; $%^$^$!!! .. And obviously it will blow up here: number overwflow happens much sooner - for ack 3 1021 ------------------------------------------------------------- Do not be discouraged by Rebol's difficulties here. The first two best performers in Ackerman category, Ocaml and GHC (Glassgow Haskell Compiler) are specificly well fitted for such tasks as tail recursion elimination. But Haskell interpreter Hugs, a tool used for teaching and prototyping, does not do much better than Rebol does:
> ack 3 6
509
> ack 3 7
1021
> ack 3 8
... I did not have enough patience to wait for the answer. Jan