Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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:gmai:l 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:g:mail 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:g:mail 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