[ruby-talk:11557] Re: Array bugs?

"Christoph Rippel" <[e-mail]>  wrote:
> > From: ts [mailto:[e-mail]]
[...]
>Since ruby's equality algorithm  (for non-recursive array's-
>the  ``id-sanity check'' should be added so) never terminates
>for RCO's, recursive container Objects (or whatever you want
>to call them) it seems to me that you are basically free to
>choose between ``a == b''  and ``a != b''. (The ladder
>scheme basically boils down to infinite loop protection -
>see below.)

I have not been following this discussion, but here is a
possible solution:

    class Array
      attr :other_id

      def == (other)
        if @other_id.nil?
          return false unless other.kind_of? Array
          return false unless length == other.length
          begin
            @other_id = other.id
            each_index do |i|
              return false if not self[i] == other[i]
            end
          ensure
            @other_id = nil
          end
          return true
        else
          return @other_id == other.id
        end
      end
    end

Any feedback other than the obvious point that it
isn't threadsafe?  (I went to the extent of making
sure that exceptions wouldn't leave it in an
inconsistent state though - guess who does very
little threaded programming...?)

OK, there are some decisions that it makes which I
do not totally agree with, but there are none that
I think unreasonable either.

>(Besides their entertaining curiosity value for me;-)  RCO's
>seem like very bad  ``type citizens'' - in many computer
>languages you cannot form them and in math they are strictly
>forbidden since they let to inconsistencies.

Actually in many areas of math they are allowed.  But
not in set theory.

>On the practical side the infinite recursion problem is
>a consequence that you are performing an unsupported
>operation (that includes asking for equality! - if the
>objects are unequal you are still fine) and throwing an
>exception actually seems like the right thing to-do - a
>''catchable'' ``SystemStackError'' exception is as good as
>any other exception IMO.

As shown above, I do not see why equality should not be
allowed.

>Ideally the formation of an RCO would be flagged with an
>exception at creation time but such a scheme would bring
>the language to a crawl (that's a problem with liberal
>languages like ruby that they cannot be practically
>defended against all abuses at runtime).

Why is this ideal?

Your basic directory structure is in your terms an RCO
- both . and .. point recursively at things which the
current directory can be reached from!

Self-recursive structures arise in practical
situations, and I would like it if Ruby treated them
right.  Disallowing them (even if it were practical)
would leave a bad taste in my mouth.

[...]
> > C> ##########################
> > C> def f(x); [x,x]; end
> > C> def g(x); f f f f f f f f x; end
> > C> def h(x); g g g g g g g g x; end
> > C> def i(x);  h h h h h h h h x; end
> > C> def j(x); i i i i  i i i   x;end
> >
> > C> p (j(1) == j(1))
> >
> >  Here it take too long time to compute it.
>
>it would take 2**(8*8*8*7 +1) - 1 = 2**3585 - 1 Object
>comparisons (not counting the length comparisions and
>type check) - note who ever that the memory usage in
>contrast to a true RCO won't go through the roof -
[...]

Examples like the above do not often arise in
practice.  The fact that you can eat CPUs with
a simple script I don't mind in the slightest.

Now in fact it would be possible to solve the
above problem very easily with class data.  Again
not thread-safe, but consider:

    class Array
      @@other_id = nil

      def == (other)
        if @@other_id.nil?
          begin
            @@other_id = Hash.new( nil )
            return self == other
          ensure
            @other_id = nil
          end
        else
          return false unless other.kind_of? Array
          return false unless length == other.length
          other_id = @@other_id[self.id]
          if other_id.nil?
            @@other_id[self.id] = other.id
            each_index do |i|
              return false if not self[i] == other[i]
            end
            return true
          else
            return other_id == other.id
          end
        end
      end
    end

(I actually like the way this one works slightly
better, and thread-safe can be arranged more easily
for this design.)

Unfortunately the fact that it is depth first still
gives a problem on your pathological case, but it is
able to handle testing i() OK.

Cheers,
Ben
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com