Does REBOL cons?
[1/13] from: massung:gm:ail at: 15-Mar-2006 16:15
Okay, so, I've been trying something out, comparing REBOL to Lisp. The
functions in REBOL make it appear as though the lists (series!) in REBOL are
just your average conses (first, next, associations, etc). Because of this
and constant data optimizations, etc, this function in REBOL makes sense:
foo: func [/local a] [
a: [a b c]
append a [d]
]
>> foo
== [a b c d]
>> foo
== [a b c d d]
This makes sense, at least, until after the second call. The above function
would be akin to the following Lisp code, which does *almost* the same
thing:
(defun foo ()
(let ((a '(a b c)))
(nconc a '(d))))
The main difference being that the second call to (foo) will result in an
infinite list, because '(d) is scoped data, just like '(a b c), and the
second call will cons '(d) with itself, giving us '(a b c d d d d d ...).
In REBOL, everything seems to match up, except that [d] doesn't cons with
itself. Now, IMO, this is good, desired behavior (not generating an infinite
list). However, what this implies "under-the-hood" is that REBOL doesn't use
traditional consing for lists, but does something else instead.
I was wondering if anyone could shed a little light on this. If REBOL does
use consing, then why don't I end up with an infinite, self-referencing
list? If it doesn't using consing, what does it use (not that it matters,
I'm just curious)? This is actually a little exciting to me, because if it
isn't using your typical consing, then that means REBOL's associated lists
could potentially be a lot faster than Lisp's (which, of course, have O(n)
access times).
Jeff M.
--
massung-gmail.com
[2/13] from: Izkata:Comcast at: 15-Mar-2006 16:29
This goes back to the "everything is data" idea:
>> foo: func [/local a][
[ a: [a b c]
[ append a [d]
[ ]
>> foo
== [a b c d]
>> foo ;Your function and it's two calls
== [a b c d d]
>> source foo ;Look at the source
foo: func [/local a][
a: [a b c d d] ;Assigning that block to 'a didn't copy it; it pointed
at it (using C/C++ terms)
append a [d]
]
>> foo
== [a b c d d d]
>> source foo
foo: func [/local a][
a: [a b c d d d] ;Every time 'foo is called, the list gets another
addition...
append a [d]
]
Now, had it been "a: copy [a b c]" instead, 'a wouldn't be pointing at the
block in the function, it would be pointing at a new block that looks
exactly the same, each time the function is called.
Any series (like string!) works the same way.
-Izzy
[3/13] from: massung::gmail at: 15-Mar-2006 16:32
Yes. I know. Sorry, I don't mean to be rude or curt, and I do thank you for
your reply, but it in no addressed my question. :-)
I understand "everything is data" (I come from Lisp, which has been doing
this for a very long time). And that, as in Lisp, is what gives REBOL its
power.
My question was more fundamental: "Does REBOL use consing for its lists
internally?"
Jeff M.
--
massung-gmail.com
[4/13] from: Izkata:Comcast at: 15-Mar-2006 16:36
I have no idea, I was trying to explain your "This makes sense, at least,
until after the second call. "
I've only ever even seen one example of Lisp code.. ='^.^=
[5/13] from: massung::gmail at: 15-Mar-2006 16:48
Hehe. Let me explain why I'm a bit confused and maybe that will help. I just
want to build off what you originally replied with.
Okay, so, the definition of a cons, of course, is just a trivial,
uni-directional, linked-list:
(A . (B . (C . NIL))) -> (A B C)
(D . NIL) -> (D)
The reason that the original list in FOO changes (assuming that REBOL uses
conses) is that the cons holding 'C' is modified to also include the D cons:
(A . (B . (C . (D . NIL)))) -> (A B C D)
And, of course, since the function FOO just makes use of that pre-allocated
list in bytecode (or whatever REBOL uses for interpretation of data), the
source
of FOO changes with each call.
However, [d] is no different from [a b c] in the source (meaning that both
are "pre-allocated data" - for lack of a better term - they aren't recreated
each call). Suppose I wrote the function like this:
foo: func [/local a b] [
a: [a b c]
b: [d]
append a b
]
Now, after the first call, the function's source is now:
foo: func [/local a b] [
a: [a b c d]
b: [d]
append a b
]
Simple enough. But, the last cons in the list that 'a' points to is the same
cons that 'b' points to (if REBOL is consing). So, after the second call, we
should have an infinite list:
foo: func [/local a b] [
a: [a b c d d d d d ... ]
b: [d d d d d d ... ]
append a b
]
This is what Lisp does, and if REBOL conses, is what I would expect that it
would do as well.It could also be that APPEND has a built-in safe guard, in
that maybe it copies the second argument to prevent self-referencing
objects?
Anyway, perhaps this better explains my question. :-)
Jeff M.
--
massung-gmail.com
On 3/15/06, Izkata <Izkata-comcast.net> wrote:
[6/13] from: volker:nitsch:gm:ail at: 16-Mar-2006 0:06
Blocks are areas, not lists.
On 3/15/06, Jeff Massung <massung-gmail.com> wrote:
> Okay, so, I've been trying something out, comparing REBOL to Lisp. The
> functions in REBOL make it appear as though the lists (series!) in REBOL are
<<quoted lines omitted: 34>>
> To unsubscribe from the list, just send an email to
> lists at rebol.com with unsubscribe as the subject.
--
-Volker
Any problem in computer science can be solved with another layer of
indirection. But that usually will create another problem.
David
Wheeler
[7/13] from: Izkata::Comcast::net at: 15-Mar-2006 17:18
Mm, that does help me understand... Sorta.
'append calls 'insert, and no explicit call to 'copy, but 'insert is a
native, so we can't look at it's source....
Unless someone who knows more about it replies, my best guess is that, if
Rebol uses cons, 'insert does copy the second value before inserting it into
the series.
>> source append
append: func [
{Appends a value to the tail of a series and returns the series head.}
series [series! port!]
value
/only "Appends a block value as a block"
][
head either only [
insert/only tail series :value
] [
insert tail series :value
]
]
>> source insert
insert: native [
{Inserts a value into a series and returns the series after the insert.}
series [series! port! bitset!] "Series at point to insert"
value [any-type!] "The value to insert"
/part "Limits to a given length or position."
range [number! series! port! pair!]
/only "Inserts a series as a series."
/dup "Duplicates the insert a specified number of times."
count [number! pair!]
]
[8/13] from: tim-johnsons::web::com at: 15-Mar-2006 14:52
* Jeff Massung <massung-gmail.com> [060315 13:48]:
> My question was more fundamental: "Does REBOL use consing for its lists
> internally?"
the lisp cons is *not* internal, it is produced by a C code that
adds an item to a linked (I think) list.
The rebol 'insert action value is produced by C code that resizes
a contiguous block of memory with the value as the first item.
I think that rebol lists are linked lists tho' and I *believe*
that 'insert acts on them too. But take note of the return value
(cons CAR CDR) returns new list.
'insert returns the insertion point.
Here's a nother quick rebol console session:
>> test: [2 3 4]
== [2 3 4]
>> res: insert test 1
== [2 3 4]
>> res
== [2 3 4]
>> test
== [1 2 3 4]
>> help insert ;; see the underscored line
USAGE:
INSERT series value /part range /only /dup count
DESCRIPTION:
Inserts a value into a series and returns the series after the insert.
----------------------------------------------------------------------
^^^^^^^^^^^^^^^^^^^^^^^^^^^
INSERT is an action value.
ARGUMENTS:
series -- Series at point to insert (Type: series port bitset)
value -- The value to insert (Type: any-type)
REFINEMENTS:
/part -- Limits to a given length or position.
range -- (Type: number series port)
/only -- Inserts a series as a series.
/dup -- Duplicates the insert a specified number of times.
count -- (Type: number)
:-) Watch them/thar return values, they will surprise you.
Fortunately, you're familiar with lisp so you will be looking for
return values from loops and conditionals. That's something else I
hand to get used to.
HTH
tim
--
Tim Johnson <tim-johnsons-web.com>
http://www.alaska-internet-solutions.com
[9/13] from: anton:wilddsl:au at: 16-Mar-2006 19:43
Hi Jeff,
I think Volker is right, probably rebol doesn't
use consing as you describe it.
Here is my document to understand rebol values,
words, strings and blocks:
do http://www.lexicon.net/antonr/rebol/doc/rebol-values.r
It reflects my mental model.
Ahh! actually, the confusion may be that you think:
blk: []
insert blk [d]
inserts a block. It does not ! The above is equivalent to:
blk: []
insert blk 'd
That is, only a word was inserted into the blk.
After many iterations, the block is filled with many words
with the same name, "d".
To insert a block, you must use INSERT/ONLY:
blk: []
insert/only blk [d]
This results in:
blk: [[d]]
(Same goes for APPEND/ONLY.)
Regards,
Anton.
[10/13] from: kgozlinski:neokartgis:pl at: 16-Mar-2006 10:34
I found this conversation very useful to explain me how rebol works inside,
http://www.rebol.org/cgi-bin/cgiwrap/rebol/ml-display-thread.r?m=rmlKVVC
since then rebol suprise me very rarly
espacilly this one is very interesting
http://www.rebol.org/cgi-bin/cgiwrap/rebol/ml-display-message.r?m=rmlTGVC
It first time intoduced concept of slot to me which drives rebol machine.
Sorry that it does not answer your question directly.
BTW I think this conversation should be extracted into some document or go
to FAQ
cheers
Karol
[11/13] from: gabriele::colellachiara::com at: 16-Mar-2006 10:38
Hi Jeff,
On Wednesday, March 15, 2006, 11:15:43 PM, you wrote:
JM> Okay, so, I've been trying something out, comparing REBOL to Lisp. The
JM> functions in REBOL make it appear as though the lists (series!) in REBOL are
JM> just your average conses (first, next, associations, etc). Because of this
JM> and constant data optimizations, etc, this function in REBOL makes sense:
You already got many answers, so I guess I'm not saying much news
at this point.
REBOL's blocks are actually "arrays" and not lists. (O(1) random
access, O(N) worst case inserts/removals).
You can picture a REBOL value with a box, that we'll call a value
slot, optionally referring to a data area.
+-----------------+
| |
| value slot |
| |
+-----------------+
|
| + - - - - - - . . . - +
+ - - - - > | data . . . |
+ - - - - - - . . . - +
In the current implementation a value slot is exactly 16 bytes. It
can hold any REBOL value; "scalar" values do not refer to the
optional data area depicted above, while series values do.
As you already know, many value slots can refer to the same series
data.
So, a block value is actually a value slot of block type,
containing info such as the current position, and referring to an
array of value slots.
[block]
|
+--->|[slot1][slot2]...[slotn]|
These arrays are automatically reallocated when needed to make
space for new slots (you can guess there's another level of
indirection involved because of this... but this is irrelevant for
now).
Now let's look at what happens in your insert case, and what would
happen with INSERT/ONLY. Let's assume we have at least one free
slot at the tail of the A block.
a: [block]
|
+--->|[wrd a][wrd b][wrd c]-------|
b: [block]
|
+--->|[wrd d]|
Without the /ONLY refinents, what happens is that the slots are
copied from B to A:
a: [block]
|
+--->|[wrd a][wrd b][wrd c][wrd d]|
b: [block]
|
+--->|[wrd d]|
With /ONLY instead, the slot for the B block is copied into A:
a: [block]
|
+--->|[wrd a][wrd b][wrd c][block]|
|
+-------------------------+
|
b: [block] |
| V
+--->|[wrd d]|
Hope this sheds some light. :)
(Note that LIST! values are liked lists, instead, but they aren't
cons either, i.e. you wouldn't get an infinite list in your case.
However, you should be able to see that's very easy to implement
cons with two-slots blocks.)
Regards,
Gabriele.
--
Gabriele Santilli <gabriele-rebol.com> --- http://www.rebol.com/
Colella Chiara software division --- http://www.colellachiara.com/
[12/13] from: rebol-list2::seznam::cz at: 16-Mar-2006 22:04
Hello Anton,
Thursday, March 16, 2006, 9:43:22 AM, you wrote:
AR> Hi Jeff,
AR> I think Volker is right, probably rebol doesn't
AR> use consing as you describe it.
AR> Here is my document to understand rebol values,
AR> words, strings and blocks:
AR> do http://www.lexicon.net/antonr/rebol/doc/rebol-values.r
AR> It reflects my mental model.
Include: Couldn't load-thru http://www.lexicon.net/anton/rebol/gui/scroll-panel.r
** Script Error: scroll-panel-style has no value
** Where: do-facets
** Near: scroll-panel-style
[13/13] from: anton::wilddsl::net::au at: 17-Mar-2006 13:30
Hi Oldes, it's a long time since you visited View Desktop
Rebol Sites folder, isn't it ?
That's my old website address, so it means you need to
update the index and try again.
load-thru/update http://www.reboltech.com/index.r
do http://www.lexicon.net/antonr/rebol/doc/rebol-values.r
Regards,
Anton.
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted