World: r3wp

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.

so, the question is, how many marking bits are available

Only Carl has that answer. Still reading...

You would have to do something similar to a simplified EQUAL-STATE? 
even in a C version. There will never be enough bits for marking 
because every concurrent instance of your comparison would need its 
own set. Having thread-local done lists would work though.

concurrent instance of your comparison
 -> "concurrently running instance of your comparison function"

concurrently running instance of EQUAL? - yes, understood, that would 
be impossible, but such a thing can be made "atomic/protected", can't 
it?

No.