[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
