Ackermann (was Re: language shoot-out)
[1/9] from: joel:neely:fedex at: 5-Nov-2002 10:06
Hi, Carl, et al,
> >
> > On Mon, 4 Nov 2002, Carl at REBOL wrote:
> >
> > > How deep is the stack at 7?
> > >
>
FWIW I get the same results with w2k:
>> 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
but a more depressing set of results with Mac OS X:
>> ackermann/run
1 13 15 106
2 29 31 541
3 61 63 2432
4 125 127 10307
5 253 255 42438
Failure at depth 322 / 322 after 51405
Failure at depth 322 / 322 after 50887
Failure at depth 321 / 322 after 50886
which leads me to wonder why the stack depth limit is less than half
of that on wxx?
-jn-
Joel Neely wrote:
> Hi, Tom,
> Could you please post the code which you used to generate that
<<quoted lines omitted: 44>>
> Failure at depth 709 / 709 after 249577
> (on w95, but YMMVDOP!)
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[2/9] from: carl::s::rebol::com at: 5-Nov-2002 16:08
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.
At 10:06 AM 11/5/02 -0600, you wrote:
[3/9] from: lmecir:mbox:vol:cz at: 6-Nov-2002 8:57
Hi Carl and Joel,
> 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.
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.
Regards
-L
[4/9] 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 ...
> > >
<<quoted lines omitted: 47>>
> > > 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 ]
[5/9] 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 ]
[6/9] from: rotenca:telvia:it at: 6-Nov-2002 22:24
What i do not understand well is why this stops at 1374:
ack41: func [m [integer!] n [integer!] /local result f2][
md: max md cd: cd + 1
tot: tot + 1
if m = 0 [cd: cd - 1 return n + 1]
if n = 0 [result: ack41 m - 1 1 cd: cd - 1 return result]
result: ack41 m - 1 ack41 m n - 1
cd: cd - 1
result
]
and this stops at 2181 (ack41 3 9)
ack41: func [m [integer!] n [integer!] /local result f2] [
md: max md cd: cd + 1
tot: tot + 1
if m = 0 [cd: cd - 1 return n + 1]
if n = 0 [result: ack41 m - 1 1 cd: cd - 1 return result]
f2: ack41 m n - 1
result: ack41 m - 1 f2
cd: cd - 1
result
]
---
Ciao
Romano
[7/9] from: joel:neely:fedex at: 6-Nov-2002 16:32
Hi, Romano,
WARNING: Uneducated guess ahead...
Romano Paolo Tenca wrote:
> What i do not understand well is why this stops at 1374:
>
...
> result: ack41 m - 1 ack41 m n - 1
...
> and this stops at 2181 (ack41 3 9)
>
...
> f2: ack41 m n - 1
> result: ack41 m - 1 f2
I might guess that in the earlier case, the left-hand eval of ACK41
is in some sense pending while the right-hand eval is being pursued,
and thereby consuming some resources.
In the second case, the eval of ACK41 M N - 1 is allowed to complete
(with the result cached) prior to initiating the second eval of ACK41.
Concurrent vs. serial.
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[8/9] from: g:santilli:tiscalinet:it at: 7-Nov-2002 0:41
Hi Romano,
On Wednesday, November 6, 2002, 10:24:44 PM, you wrote:
RPT> What i do not understand well is why this stops at 1374:
[...]
RPT> and this stops at 2181 (ack41 3 9)
[...]
The intepreter is probably consuming stack while collecting
arguments. So, in the first case ack is called while processing
the arguments for another call to ack; in the second, the two
calls are distinct.
Regards,
Gabriele.
--
Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer
Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r
[9/9] from: joel:neely:fedex at: 8-Nov-2002 10:36
Hello, all,
For the sake of complete-(er)-ness, I've rerun the same test on my
Sun E4500 account, with the following results:
>> ackermann/run
1 13 15 106
2 29 31 541
3 61 63 2432
4 125 127 10307
5 253 255 42438
Failure at depth 274 / 274 after 43341
Failure at depth 274 / 274 after 43272
Failure at depth 274 / 274 after 43207
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 616 / 616 after 193963
Failure at depth 616 / 616 after 193554
1 13 15 106
2 29 31 541
3 61 63 2432
4 125 127 10307
5 253 255 42438
Failure at depth 379 / 379 after 72951
Failure at depth 379 / 379 after 71977
Failure at depth 379 / 379 after 71977
1 13 15 106
2 29 31 541
3 61 63 2432
4 125 127 10307
5 253 255 42438
Failure at depth 415 / 415 after 92622
Failure at depth 415 / 415 after 92622
Failure at depth 415 / 415 after 91993
1 13 15 106
2 29 31 541
3 61 63 2432
4 125 127 10307
5 253 255 42438
Failure at depth 478 / 478 after 140375
Failure at depth 477 / 478 after 139495
Failure at depth 478 / 478 after 138617
>> ackermann/stress
** Internal Error: Stack overflow
** Near: recur curr_depth: n + 1
>> ackermann/curr_depth
== 1277
The results from running this test on w2k, w95, OS X, and Solaris
leave me with the impression that the "stack" we're instrumenting
here may not be a data structure managed by the interpreter, but
rather an artifact of C implementation on a platform-specific
basis.
Someone with more inside info care to confirm or deny?
-jn-
Joel Neely wrote:
... [running on w2k and w95] ...
> >> ackermann/run
> 1 13 15 106
<<quoted lines omitted: 43>>
> >> ackermann/curr_depth
> == 3148
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted