From: Christoph Rippel <crippel@...>
Date: 2001-03-10T09:06:46+09:00
Subject: [ruby-talk:12363] Re: Q re looping structures

> From: Benjamin J. Tilly [mailto:ben_tilly@operamail.com]
[...]
> >If the comparison is topological, the answer is obviously "false", but I
> >don't think == should compare topology: only values should be compared, so
> >that a=[[42]];a<<a[0] and [[42],[42]] stay equal.
> 
> This is true.
Actually,

they would not be equal in an almost identical situation
if you set
x =[42]
s = [[42]]; s << s[0]
and 

t = [[42],[42]]
u = [x,x];

you will get

p (s == t), (t == u), (u != s )  # true,  true, false


i.e. the whole scheme stinks (I tested with your, mine
and implemetation and Guys C extension  of id-bag/cache) 
- unfortunately we kept a bit of the level-unaware id-bag
around so the current version of tangle as the same problem
 - i.e. it will conclude that  "s == t" before realizing 
that "s" is tangled - the good thing is that the corrected
algorithm is even simpler and it can still handle the 
infamous example;-)

def f(x); [x,x,x,x,x,x,x]; end
def g(x); f f f f f f f f x; end
def h(x); g g g g g g g g x; end
def i(x);  h h h h h h h h x; end
def j(x); i i i i  i i i i  x;end

p j(34) == j(34)

(Guy C-implementation of id-caching was unbelievable fast on
this example) - with the new scheme it will still detect equality
it just takes a little longer. Basically level-id caching - this
causes on theoretically problems - only kicks in after you 
reached a certain recursion depth. 
Our current scheme (after this bug is fixed) will not detect 
``tangledness'' in all cases if one of the two sides is not 
``tangled'' - that is might conclude that both side are not
equal before figuring out that one of them is ``tangled".

This scheme is faster, keeps the interpreter from crashing and
still protects the user from the most of the terrible side effects
a graph based equality notion would introduce ...

> The problem is that this looks like:
> 
>     a == c == [[[[...], 2], 1], 2], 1]
> 
> and
> 
>     b == d == [[[[...], 1], 2], 1], 2]

it is actually a fun problem to construct
these two arrays

> 
> and with a depth-first search, there is no meaningful
> resolution of what <=> should do.  The best that you can
> do is have some test for having mismatched on a left
> recursive data structure (right-recursive ones not posing
> a problem) and raise an exception.

an untangle (if we ever get the no bang version to work)
could solve this problem but you alright know my opinion
about this  ...

Christoph