[REBOL] Re: Fun with blocks of words (a tad longish)
From: joel:neely:fedex at: 10-Oct-2001 13:49
Thanks, Gabriele, for the insights!
Gabriele Santilli wrote:
> Joel Neely wrote:
>
> > >> reduce repeat i 5 [use [.i] [.i: i append [] [.i]]]
> > == [5 5 5 5 5]
>
> Actually, this is a side effect of SMC. USE rebindes its block at
> each iteration, so it rebinds your growing [] at each iteration.
>
> > Again we get five references to the same word!
>
> Five different words, but bound to the same context and thus
> referring to the same value. (Well, maybe this makes them "the
> same" to you... I don't want to start a new thread on mutability
> and sameness... ;-)
>
(Nor do I, but if "same" means indistintuishable... ;-)
Illustrating the point:
>> d: repeat i 5 [use [.i] [.i: i append [] [.i]]]
== [.i .i .i .i .i]
>> foreach p d [foreach q d [prin [same? :p :q " "]] print ""]
true true true true true
true true true true true
true true true true true
true true true true true
true true true true true
which makes me think that words with identically-spelled names bound
to one context are (or become, or whatever...) the "same" word.
> > Errrk? What about recursion?
>
> Value stack. ;-)
>
Meant as a rhetorical questions. Sorry if I was too obscure.
I was setting up to make the point that taking out the overhead for
non-recursive cases simply means that there's an overhead delta for
using recursion. For instance ...
bumpfirst: func [b] [change b 1 + first b]
bumpall: func [bb] [head forall bb [bumpfirst bb]]
... increments every number in a block, using a function for
incrementing but using iteration for traversal, while ...
rbumpall: func [bb] [
either empty? bb
[head bb]
[change bb 1 + first bb rbumpall next bb]
]
... increments every number in a block, using a recursive function
for both incrementing and traversal. IOW, the number of function
evaluations in both cases is linear to the length of the argument
block. Now the iterative traversal ...
boz: array/initial 1000 0
== [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
t0: now/time
repeat i 10000 [boz: bumpall boz]
t1: now/time
print t1 - t0
0:01:04
... versus the recursive traversal ...
boz: array/initial 1000 0
== [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
t0: now/time
repeat i 10000 [boz: rbumpall boz]
t1: now/time
print t1 - t0
0:01:17
shows that the recursive version takes about 20% more time than
the iterative version.
-jn-
--
This sentence contradicts itself -- no actually it doesn't.
-- Doug Hofstadter
joel<dot>neely<at>fedex<dot>com
