World: r3wp

Simple cycle detection wouuldn't help there - you would need cycle 
tracing.

that depends on the quantity of marking bits, if you have only one 
marking bit, you can just detect cycle, if you have 32 bits, you 
can detect the index

Cycle detection would be good enough to let you throw an informative 
error though, without getting as far as a stack overflow.

btw, in the Identity article I wrote an equivalent? version, that 
works with cyclic structures

(but it is slow, not having any additional marking data available)

Ladislav, the cyclic structures above are not the same structure, 
but the results would need to be considered EQUAL?. Unless we declare 
that cyclic structures need to have the same structure to be declared 
equal - then we can use a stack of ref/index for the structure detection.

Simple marking wouldn't work, unless we locked the data for the task 
first.

Since that data is complex and has references such marking couuld 
easily deadlock.

It all depends on how sharing of data between tasks is done. It looks 
(currently) like Carl is thinking that PROTECTed series would be 
sharable - this would mean that large swaths of the data in memory 
would be unmodifiable, or duplicated. This makes functional or lock-free 
datastructures even more important for R3.

Updated the comment according to the above discussion.

Simple marking wouldn't work, unless we locked the data for the task 
first.
 - that has to be done for the GC as well as for MOLD etc. anyway

Yeah, buut that would only help for cycle detection, not for structural 
equivalence.

try this in R3


>> do http://www.rebol.org/download-a-script.r?script-name=identity.r
Script: "Identity.r" Version: none Date: 7-May-2009/8:59:07+2:00
Script: "Contexts" Version: none Date: 12-May-2006/15:58+2:00
Script: "Closure" Version: none Date: 11-May-2009/19:13:51+2:00
Script: "Apply" Version: none Date: 7-May-2009/9:25:31+2:00
== make function! [[
    "finds out, if the VALUE is mutable"
    value [any-type!] /local r
][
    parse head insert/only copy [] get/any 'value [

        any-function! | error! | object! | port! | series! | bitset! |
        struct! | set r any-word! (
            either bind? :r [r: none] [r: [skip]]
        ) r
    ]
]]

>> a: [z] append/only a a
== [z [...]]

>> b: [z [z]] append/only second b second b
== [z [...]]

>> c: [z [z]] append/only second c c
== [z [z [...]]]

>> equal-state? a a
== true

>> equal-state? a b
== true

>> equal-state? a c
== true

Apply and Closure not needed, but the script was written for R2

Mere cycle detection is only good enough to throw a good error. To 
determine equivalence you need to compare different cycles to see 
if  they are the same shape. Or topologically equivalent if you are 
ambitious.

as I said: if we have 32 bits available for marking, it *is* enough

(and, said 32 bits are needed only for block-like data values, for 
other values, like objects, one bit is plenty)

You didn't post the relevant code so I can't evaluate what you are 
saying. I'm searching for the code now.

do http://www.rebol.org/download-a-script.r?script-name=identity.r

(it is posted above)

I got the link, but am reading it to find the code.

(R2 code, unadjusted for R3)

There's a lot of code in there, not all of it relavant.

...but this variant does not use Mark bits, since those are available 
only in C

search for EQUAL-STATE?

I'm translating while I read, boith to R3 and C.

LOL

It's not as hard as it sounds :)

Already found some R2-isms, and I'm not just talking about the reflective 
accessors. Assumed case-sensitive equivalence of words, for instance.

yes, lots of those, no adjustment for R3, it is a surprise that it 
works at all

Words in R3 preserve the case they are typed in, but are considered 
equivalent on a case-insensitive basis.

...but that is the case of R2 words too

(the variants having different case are "automatic aliases", as I 
call them)

R2 words preserve the case they are *first* typed in, not the case 
they are  in every time.

I would need to see an example where it differs

I noticed the difference before, but am not able to replicate it 
now :(

nevermind, we will "rediscover" it :-D

In any case, for R3 line 502:
            if strict-not-equal? mold :a mold :b [return false]
should probably be this:
            if not-equal? mold :a mold :b [return false]

well, that is "in transition" still

Probably for R2 as well, if your statement about R2 case-preserving 
is true.

depends on the level of strictness we want to achieve for the said 
EQUAL-STATE? function...

Unless you want
>> equal-state? [A] [a]
== false

yes, that is what I achieved, as it looks

(lots of possibilities, and it was written long ago)

You do topological comparison here, not  marking.

yes, I am actually unable to do marking in Rebol

but, if you want a model, I can write one

do you know how many bits can I use for marking?

(or is it just one bit? - in that case it indeed is a problem)

Well, my point was that marking isn't enough here, and that this 
kind of comparison (the kind in equal-state?) is needed.