[REBOL] Re: On ordinal and cardinal numbers...
From: joel:neely:fedex at: 9-Jul-2001 8:11
Larry Palmiter wrote:
> > Absent tail-recursion elimination, I'd always use the
> > iterative version myself (but that's just a personal
> > opinion, and certainly not something I'd force on anyone
> > else).
>
> Good point. Actually this recursion is tail recursive,
> If a function just calls itself there is no problem with
> the recursion stack, that only happens if there is a delayed
> expression evaluation, which there is not in this case
> because the args s and b carry the state...
>
Are you defining "tail recursion", or actually stating that
REBOL does tail recursion elimination? (See below...)
> The REBOL internal stack for delayed operations is about
> 1500 deep, so the example shows that it is does not come
> into play.
>
How do you know that? I'm not arguing, just asking -- this
is exactly the kind of performance-related information I've
been hoping for, and I'd love to find an authoritative source
(preferably based on documentation rather than experimentation,
but beggars can't be choosers ;-).
> I can illustrate this in more detail if you are interested.
>
Yes. I'm extremely interested. I recently tried running some
benchmarks which foundered on stack overflow, but I didn't have
the time or patience to do the detailed trial and error to find
out the depth limit.
A quick check with View 1.2 still leaves me puzzled on this point:
count-tr: func [target [integer!] /local -count-tr] [
-count-tr: func [current [integer!]] [
either current = target [current] [-count-tr 1 +
current]
]
-count-tr 0
]
>> count-tr 10 ;== 10
>> count-tr 100 ;== 100
>> count-tr 1000 ;== 1000
>> count-tr 10000
** Internal Error: Stack overflow
** Near: -count-tr 1 + current
Hmmmm... Maybe the nesting of the invocation?
count-tr: func [target [integer!] /local -count-tr] [
-count-tr: func [current [integer!]] [
if current = target [return current]
-count-tr 1 + current
]
-count-tr 0
]
>> count-tr 10 ;== 10
>> count-tr 100 ;== 100
>> count-tr 1000 ;== 1000
>> count-tr 10000
** Internal Error: Stack overflow
** Near: -count-tr 1 + current
Well... Maybe the state needs to be all in the arguments????
count-tr: func [target [integer!] /local -count-tr] [
-count-tr: func [current [integer!] target [integer!]] [
if current = target [return current]
-count-tr 1 + current target
]
-count-tr 0 target
]
>> count-tr 10 ;== 10
>> count-tr 100 ;== 100
>> count-tr 1000 ;== 1000
>> count-tr 10000
** Internal Error: Stack overflow
** Near: if current = target [return current]
> BTW ring is also not too happy with series at the tail.
>
> >> r: make ring []
> >> r/data tail [1 2 3]
> ** Math Error: Attempt to divide by zero
> ** Where: skip
> ** Near: pick _data _pos: _pos -
>
Thanks for catching that one! With programming, as with music,
composing at the keyboard
risks dissonance! ;-)
Perhaps I'll just redefine RING in terms of the updated RING-SKIP...
> I think I would prefer to just return an empty series for both
> the case of an actually empty series (i.e., empty? head s returns
> true) which is already handled ...
>
Certainly makes sense to me.
> ... and for the case where the current index is at the tail.
> This signals a problem to the user in an unobtrusive way.
>
I guess tastes differ. Since RING-SKIP TAIL does the wrapping
if tail? s [s: head s]
for any non-zero number of iterations -- treating the original
if tail? s: next s [s: head s]
as a refactoring of
s: next s
if tail? s [s: head s]
-- it seemed consistent to do it for zero iterations as well.
That way the occurrence of an empty result signals the distinct
case of a totally empty argument.
But YMMV, of course!
-jn-
---------------------------------------------------------------
There are two types of science: physics and stamp collecting!
-- Sir Arthur Eddington
joel-dot-neely-at-fedex-dot-com
