Mailing List Archive: 49091 messages

## [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
```