Talk Like A Duck

Power, Responsibility and Tricksy VM Implementers

Posted by Rick DeNatale Thu, 15 Mar 2007 12:05:00 GMT

 Fixnum.class_eval do
   def +(number)
     self - number
   end
 end

The result: It blew up his irb.

Ruby certainly gives a lot of power. A little, and in some cases a lot, more than most popular OO languages. Read on..

Dave Ungar, who analysed and ‘optimized’ the Berkley implementation of Smalltalk-80 for his PhD dissertation, and then went on to invent the Self language used to go around and try to torment Smalltalk implementers by asking them to add an instance variable to the Object class, something which either was disallowed or would blow up. Keep in mind that Smalltalk is a dynamic language like Ruby and such changes happen while the code is running.

Ruby survives this test. Actually, it redefines it in a way similar to the way Self did. In Smalltalk, and most OO languages, instance variables are declared in classes and the classes define a template for the memory layout of the classes instances, a given instance variable is kept in a slot at a known distance from the beginning of the object. When a class is redefined all it’s instances, and the instances of all it’s subclasses need to be re-mapped.

In Ruby, classes in general don’t actually know about their instances instance variables. Instance variables are represented as an individual hash which maps the instance variable name to its value. The instance variables only come about when an instance method is executed which defines it by mention. This means that you might well have two instances of a class, one of which has a given instance variable and one which doesn’t.

This highly dynamic nature of ruby gives it a great deal of power which is put to use by advanced Rubyists and leads to nice results like Ruby on Rails.

With great power comes great responsibility!

Tricksy VM Implementers

It might be the case in some future implementations that patching FixNum#+ might be ineffective, or intermittently effective.

For example, some Smalltalk implementations, would handle a + b under the covers as an integer add of the two object pointers and a little adjustment, followed by a quick check to see if the result were a fixnum, and only send the + message if it wasn’t. This check can be done relatively inexpensively due to the way in which references to FixNums (or SmallIntegers as Smalltalk called them) are encoded.

If a number x is in FixNum range, i.e it’s twos-complement representation will fit into a bitstring of length one less than a pointer, then it’s encoded as a ‘pointer’ with the binary value x*2+1 This means that, if the low-order bit set it’s a Fixnum otherwise it isn’t. So if we have two object pointers xp and yp, referring to the objects x and y respectively we can implement x + y as something like this pseudo-C code:

   result = xp + yp - 1;  
   if (arithmetic overflow || !(result && 1) ) {
        result = send(xp,:+,yp)
   }

Note that, if xp and yp refer to Fixnums:

   xp + yp - 1 
   = (x*2+1)+(y*2+1) - 1 
   = x*2 + y*2 + 1
   = (x+y)*2 + 1

which is the correct representation for the FixNum x+y

If we don’t get an overflow, and the low-order bit is set when we compute result, we’ve got our FixNum result and we can move on. Otherwise we need to do it the old-fashoned way.

I don’t know whether YARV already does this or might in the future. This is one of the things which VM implementers tend to look for, they ‘cheat’ and try not to get caught in the interest of performance.

Now Matz and his team might reject some of these tricks since the dynamic nature of ruby might make it harder not to be caught, but in some of these edge cases, I think that case can be made that it’s probably OK since it’s unlikely that anyone will actually redefine basic arithmetic operations on core classes such as FixNum and live to tell about it without blowing up irb or worse.