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