[REBOL] Re: On ordinal and cardinal numbers...
From: agem:crosswinds at: 9-Jul-2001 15:59
RE: [REBOL] Re: On ordinal and cardinal numbers...
Hi Larry, Joel,
interesting solutions :)
[larry--ecotope--com] wrote:
> Hi Joel
>
> > Nice variation on the theme!
>
> Thanks
>
> > Ah, you sneaky fellow! ;-)
> ;-))
>
> > 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. I can illustrate this in more
> detail if you are interested. But here is a practical example which shows
> that it is not a problem. It also shows we can generally afford to burn
> these cycles, REBOL series current index manipulations are quite fast. And I
> doubt there are many cases where one is interested in a very large skip on a
> small series. Still.. see below.
>
Tail-recursion-elimination drops to loops by some compilers/interpreters.
In that case no overhead. Rebol does not, so Joel prefers iteration. :)
> >> b: make block! 10000
> == []
> >> repeat j 10000 [append b j]
> == [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
> 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4...
> >> t: now/time/precise ring-skip b 10001 now/time/precise - t
> == 0:00
> >> t: now/time/precise ring-skip2 b 10001 now/time/precise - t
> == 0:00:00.06
>
> So the recursion is slightly slower as anticipated. The REBOL internal stack
> for delayed operations is about 1500 deep, so the example shows that it is
> does not come into play.
>
> > 1) There is a peculiar "singularity" that occurs if the series
> > argument is positioned at the tail, but not at the head.
> >
> > >> b: "abcde" == "abcde"
> > >> ring-skip b 5 == "abcde"
> > >> c: tail b == ""
> > >> ring-skip c 0 == ""
> > >> ring-skip c 5 == "e"
> > >> ring-skip c -1 == "e"
> >
> > This could be guarded for at the beginning of either function.
>
> Yes, I knew that and originally had some code to deal with it, but I removed
> it and unfortunately forgot to mention in my post "just don't do that". :-(
>
> 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 -
>
> > 3) The last example you gave
> >
> > >> ring-skip2 b 344
> > == [5]
> >
> > shows that it's possible to burn lots of cycles with a large
> > enough second argument.
>
> True but see above.
> >
> > Combining all of these ideas, we could have the following at the
> > beginning of either the iterative or recursive version:
> >
> > if tail? s [s: head s]
> > if any [0 = length? s 0 = n: n // length? s] [return s]
> >
> > after which the function will never make needless "round trips".
>
> 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 and for the case where the current index is at the tail. This
> signals a problem to the user in an unobtrusive way. The n = 0 case only
> takes one cycle for the iterative version because LOOP falls through (i.e.,
> the code block does not execute).
with tail-check one can remove something with
remove block ring-skip 0
?
round-based game with player drops out for example.
