From: "Benjamin J. Tilly" <ben_tilly@...>
Date: 2001-03-10T13:46:37+09:00
Subject: [ruby-talk:12370] Re: Q re looping structures

>===== Original Message From "Christoph Rippel" <crippel@primenet.com> =====
>> From: Benjamin J. Tilly [mailto:ben_tilly@operamail.com]
[...]
>> I remain unconvinced that this scheme stinks.
>Because it breaks current code - big time
>
>p ([1,[1]] == [1,[1,[1]])  # => false current ruby
>
>p ([1,[1]] == [1,[1,[1]])  # => true with Ben's id caching

That has to be a bug..yup.   In Array's eq? method I
loop over 0...(length - 1), I should be looping over
0...length instead.

My apologies for that.

[...]
>Right now at least the interpreter is crashing -
>if a dubious equality notion is introduced some
>scriot will produce garbage because RCO violate
>basic Container axioms (and you know this as well
>as I do).

I already gave the example of a directory structure.
Recursive data structures are widely used, and a
friend verified for me that it is common to use a
caching algorithm like the one I coded.  (Hopefully
without that bug.)

>The basic problem is the following - lets say
>
>a = [1]; a <<a
>b = [1]; bm =[1]; b << bm;  bm << b;
>
>then with any id-caching you will get
>p  a== b  # => true
>
>From this you cleverly conclude that if set
>
>a[0] = 2; b [0] = 2
>
>then  ``a == b'' right?  - but wrong with
>id-caching - admittedly Ruby has a lot of side
>effects but to support something like this is
>just nonsense IMHO.
>
But Ruby already does:

  x = [1]
  a = [x, x]
  b = [[1], [1]]
  p (a == b) # => true
  a[0][1] = 2
  b[0][1] = 2
  p (a == b) # => false

which is the same error.  In other words == does not
currently take into account issues with deep copies vs
shallow copies except when it causes a crash.  With id
caching == does not take into account issues with deep
copies vs shallow copies and it doesn't crash.

Which behaviour is better?

[...]
>> In what you cut out I did construct them I thought.
>I know - I was thinking of [[[..],2],1]
>
Ah, that is a lot harder.  You can do it with streams,
but then you don't use the default array comparisons,
so we need not worry about it. :-)

[...]
>I only added three ``\'' at the ? to make it work ...

This is interesting.  On Linux with 1.6.1 I do not need
those, now I do.  The issue is that Ruby used to understand
that the line extended when you do this:

  return test ?
    this :
    that

but no longer seems to.  One of my (few and in this case it
is far too late to change) irritations is that Ruby lacks a
simple end of expression rule.  I would far prefer always
typing a ;, or having to always use \ for end of line, than
having it be so ambiguous in some cases.

>-----------------
>$ ruby bad_equal.rb
>true
>true
>-----------------
>require 'Ben'
>def cl( a, n)
>   base=loop= [a.clone]
>   (n-1).times { tmp = [a.clone]; loop << tmp; loop = tmp }
>   loop << base
>   base
>end
>
>p (cl("a",1) == cl("a",101))  # all id-cachings have this problem

Is this a problem?

>p ([1,[1]] == [1,[1,[1]]])

And the bug.

[...]
>class Array
[...]
>  def eq? (other, cache)
>    if (other.kind_of? (Array) and length == other.length)
>      if (id != other.id and not cache.visited? (id, other.id))
>        for i in 0...(length - 1) do
                  ^^^^^^^^^^^^^^^^
Make that ".." or remove the "- 1" and try again.

>          return false unless self[i].eq? (other[i], cache)
[...]

Cheers,
Ben

-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------