Fun with blocks of words (a tad longish)
[1/10] from: joel:neely:fedex at: 10-Oct-2001 7:39
Hello, all,
I found the following little explorations instructive while thinking
about words and contexts. I hope they are of interest/value to
someone else.
Let's make a block of words:
>> bow: []
== []
>> repeat i 5 [append bow i]
== [1 2 3 4 5]
Woops! That gave me a block of integers, not a block of words.
Besides which, I hate using variables unless necessary.
I can get rid of the variable BOW (since REBOL is a very literal
language) like this:
>> repeat i 5 [append [] i]
== [1 2 3 4 5]
Now let's get a block of words instead of a block of integers:
>> repeat i 5 [append [] [i]]
== [i i i i i]
But is that a block of five homographs (distinct words whose names
are all spelled the same), or is it a block with five references
to the same word?
>> reduce repeat i 5 [append [] [i]]
== [6 6 6 6 6]
It's five references to the same word.
Thought 1: REPEAT creates a context when executed.
Within the block that is evaluated REPEATedly,
the word that is the first argument to REPEAT is in that
new context. (* Not considering the use of nested words
that also create contexts, e.g. USE, etc...)
But what if I *really* want a block of homographs? Hmmmm.
Let's try sticking another context-creating word in there.
>> reduce repeat i 5 [use [.i] [.i: i append [] [.i]]]
== [5 5 5 5 5]
Again we get five references to the same word!
Thought 2: USE creates a context when executed. When
word(s) in the first argument appear in the
second argument, they are words in that context. It
appears that there's a side-effect of "remembering" that
fact so that subsequent USEs of the same block are still
involved with that context.
Hmmm. If I give USE a fresh second block every time, then I can
avoid the side-effect.
>> reduce repeat i 5 [use [.i] copy [.i: i append [] [.i]]]
== [5 5 5 5 5]
Duh! A simple COPY doesn't get to the .I that's in an additional
layer
of block nesting.
>> reduce repeat i 5 [use [.i] copy/deep [.i: i append [] [.i]]]
== [5]
Double-duh! Now there's a fresh empty block for every evaluation
of USE. Sigh... The only way I can think of to get around that is
to re-introduce a word to serve as a "variable".
>> b: []
== []
>> reduce repeat i 5 [use [.i] copy/deep [.i: i append b [.i]]]
== [1 2 3 4 5]
Aha! It looks like I (finally!) have five homographs! I'd really
like to look at them, though...
>> repeat i 5 [use [.i] copy/deep [.i: i append b [.i]]]
== [.i .i .i .i .i .i .i .i .i .i]
Rats! That's why I hate using "variables". Side-effects accumulate!
While I'm at it, I'll keep the result this time so that I can look
at the "raw" block and also REDUCE it:
>> b: []
== []
>> c: repeat i 5 [use [.i] copy/deep [.i: i append b [.i]]]
== [.i .i .i .i .i]
>> reduce c
== [1 2 3 4 5]
Yes! Five homographs! Just what I wanted!
Thought 3: COPY/DEEP is a way to avoid the side-effect
that USE has on its second block. However,
I have to remember that COPY/DEEP also blows away any
side-effects on literal values!
I wonder -- is there any way to get homographs without losing the
ability to have literal values? How else can we create contexts?
How about with a function?
>> apparg: func [b x] [append b [x]]
>> c: repeat i 5 [apparg [] i]
== [x x x x x]
>> reduce c
== [5 5 5 5 5]
Hmmmph! (Insert appropriate numbers of "duh" ;-) I'm back to
getting five occurrences of the same word. Oh yeah...
Thought 4: The context of a function is persistent.
Subsequent uses of the function are using
the same context. This isn't like ___ (insert name of
commonly-used language here) which creates a new frame
or environment for each invocation of a function.
I suspect that this might be a performance choice. Create the
context when the function is defined, and keep it around to avoid
repeating that work every time the function is evaluated.
Errrk? What about recursion?
>> rapparg: func [b i x] [
[ either i > x [b] [rapparg append b [i] i + 1 x]
[ ]
>> c: rapparg [] 1 5
== [i i i i i]
>> reduce c
== [1 1 1 1 1]
Well, it *looks like* I is getting saved and restored for the
recursive calls, but let's make sure (by using some fairly
gnarly-looking before-and-after tracing):
>> rapparg: func [b i x /local r] [
[ print b
[ r: either i > x [b] [rapparg append b [i] i + 1 x]
[ print r
[ r
[ ]
>> c: rapparg [] 1 5
2
3 3
4 4 4
5 5 5 5
6 6 6 6 6
6 6 6 6 6
5 5 5 5 5
4 4 4 4 4
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1
== [i i i i i]
>> reduce c
== [1 1 1 1 1]
Yup! The argument block is accumulating a bunch of references
to the same word (an argument) whose value is being saved and
restored to make the recursive call behave like one would
expect it to.
Thought 5: I suspect that means that there's a time
penalty for using recursion (compared to
repeatedly calling the same function within an iteration)
but that benchmark will have to wait for another day.
Wait a minute! My attention is wandering! I wanted to make a
block of homographs. How else can I make new contexts? Whoa!
I can make a new function everytime I iterate!
>> c: repeat i 5 [do func [b x] [append b [x]] [] i]
== [x x x x x]
>> reduce c
== [1 2 3 4 5]
Yeehah! Now I get a fresh context (and therefore a fresh word)
every time.
Thought 6: FUNC appears *not* to have the side-effect
of altering its second block (in the way
that USE does). Subsequent uses of FUNC ... ... really
get me a new context for each evaluation.
Of course, being stubborn as well as simple-minded, I can't help
but think about the idea of USE inside the body of a function.
Since USE seems to have a side-effect on its second (literal)
argument, I would expect to get the same word over and over.
Let's try it...
>> appuse: func [b x] [use [.x] [.x: x append b [.x]]]
>> c: repeat i 5 [appuse [] i]
== [.x .x .x .x .x]
>> reduce c
== [1 2 3 4 5]
Wot??? I got five homographs! Does USE inside a function body
behave differently than USE at the console level?
>> repfun: func [b x] [repeat i x [use [.x] [.x: i append b [.x]]]]
>> c: repfun [] 5
== [.x .x .x .x .x]
>> reduce c
== [1 2 3 4 5]
It does! We're back to five homographs, even though the body of REPFUN
is essentially the same as the unsucessful attempt from the console
prompt earlier (except for using an argument instead of a literal as
the object of the APPEND).
Thought 7: There's more going on here than meets the eye.
I need another cup of coffee.
As usual, feedback/comments/corrections/coffee are welcome! ;-)
-jn-
--
joelDOTneelyATfedexDOTcom
[2/10] from: giesse::writeme::com at: 10-Oct-2001 15:40
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... ;-)
> >> reduce repeat i 5 [use [.i] copy/deep [.i: i append b [.i]]]
> == [1 2 3 4 5]
Non need for copy/deep this way.
> >> apparg: func [b x] [append b [x]]
> >> c: repeat i 5 [apparg [] i]
<<quoted lines omitted: 3>>
>> apparg: func ['x] [append [] x]
>> c: repeat i 5 [use [j] [j: i apparg j]]
== [j j j j j]
>> reduce c
== [1 2 3 4 5]
> I suspect that this might be a performance choice. Create the
> context when the function is defined, and keep it around to avoid
> repeating that work every time the function is evaluated.
Yup.
> Errrk? What about recursion?
Value stack. ;-)
> Wot??? I got five homographs! Does USE inside a function body
> behave differently than USE at the console level?
Nope. See above. :-)
> Thought 7: There's more going on here than meets the eye.
> I need another cup of coffee.
It's just that you were using a literal block before!
> As usual, feedback/comments/corrections/coffee are welcome! ;-)
Heh. :)
Being brief,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[3/10] 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]]]
<<quoted lines omitted: 6>>
> 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
[4/10] from: lmecir:mbox:vol:cz at: 10-Oct-2001 23:57
Hi Joel,
if I understood what you were after, you wanted to have:
probe reduce probe repeat i 5 [append [] use [.i] [.i: i '.i]]
Coffee
Ladislav
[5/10] from: rotenca:telvia:it at: 11-Oct-2001 0:35
Hi all,
> Hi Joel,
>
> if I understood what you were after, you wanted to have:
>
> probe reduce probe repeat i 5 [append [] use [.i] [.i: i '.i]]
or this:
probe reduce probe repeat i 5 [append [] in context [.i: i] '.i]
which asks a little more memory, is a little more slow, but aren't contexts
made to be used outside their bodies?
> Ladislav
---
Ciao
Romano
[6/10] from: lmecir:mbox:vol:cz at: 11-Oct-2001 0:49
Hi Joel,
one comment:
...
> Thought 2: USE creates a context when executed. When
> word(s) in the first argument appear in the
> second argument, they are words in that context. It
> appears that there's a side-effect of "remembering" that
> fact so that subsequent USEs of the same block are still
> involved with that context.
The above is incorrect. The only problem of USE is not the fact, that USE
can "remember" something, but the fact, that USE doesn't "remember"
anything. The worst about it is, that USE modifies its second argument,
which can deeply confuse users...
Cheers
Ladislav
[7/10] from: g:santilli:tiscalinet:it at: 11-Oct-2001 11:09
Joel Neely wrote:
> > > Again we get five references to the same word!
> >
<<quoted lines omitted: 4>>
> >
> (Nor do I, but if "same" means indistintuishable... ;-)
[...]
> which makes me think that words with identically-spelled names bound
> to one context are (or become, or whatever...) the "same" word.
But I think there's difference between "five references to the
same word" and "five words wich are the same". Anyway, probably we
should not worry about these implementation details...
> 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 ...
Indeed, but recursion is implemented without rebinding too, so it
is quite fast.
> shows that the recursive version takes about 20% more time than
> the iterative version.
Your benchmarks are always very valuable! Thanks!
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[8/10] from: lmecir:mbox:vol:cz at: 11-Oct-2001 19:28
Hi Gabriele,
...
> Five different words, but bound to the same context and thus
> referring to the same value.
I do not understand... Have you got any reason for telling us, that the
words are "different"?
Cheers
Ladislav
[9/10] from: g:santilli:tiscalinet:it at: 12-Oct-2001 23:24
Hello Ladislav!
On 11-Ott-01, you wrote:
LM> I do not understand... Have you got any reason for telling
LM> us, that the words are "different"?
Ok, maybe I shouldn't have said that. :-)
The difference is in that they are on different memory locations
(each value in a block is in a different 6 byte "slot"). But this
is an implementation issue so it is probably irrelevant.
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[10/10] from: lmecir:mbox:vol:cz at: 13-Oct-2001 9:47
Hi Gabriele,
you have got the right to see it like that. The biggest problem with it is,
that it isn't useful for decribing BLOCK1 and BLOCK2 below:
element: copy []
block1: reduce [element element]
block2: reduce [element copy element]
I would prefer to say, that: "BLOCK1 contains two identical elements".
Another possibility is to say, that: "The values at the first and the second
place of BLOCK1 are identical".
As opposed to that: "BLOCK2 contains two discernible elements", or : "The
values at the first and the second place of BLOCK2 are discernible".
That doesn't mean, that I am saying, that the first and the second place of
BLOCK1 or BLOCK2 are identical. They aren't (see
http://www.rebolforces.com/articles/series.html ).
This terminology looks more useful to me.
Ciao
Ladislav
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted