Euclid's Algorithm in Java, Smalltalk and Ruby

Somebody recently told me that they thought computer science was regarded as “a bit of a joke” when they were at university — so what would be an example of quality work taught as part of undergraduate Computer Science?

If I had to pick a single body of work it’d be John Tucker’s “Theory of Programming Languages Notes” or TPL for short. For quite some time now TPL has been a major part of the Swansea CS curriculum.

Several new chapters have been added over the last ten years but the section on Object-Oriented Programming caught my eye and made me wonder what illustrative example I’d use to represent Euclid’s Algorithm written in an object-oriented style.

Euclid’s Algorithm in Java

In the TPL notes we’re given a first attempt at Euclid’s algorithm in Java. Unfortunately, it’s not generally possible to implement Euclid’s algorithm in an object-oriented way in Java because Java doesn’t model integers as objects nor does it perform arithmetic or logic using object-oriented method dispatch.

The best we can do in Java using a plain int or java.lang.Integer is to wrap a conventional imperative implementation of the kind we’d write in ANSI C in a method.

public static int gcd(int x, int y) { 
 while (y != 0) {
  int r = x % y;
  x = y; 
  y = r;
  }
 return x;
}

It’s a program in an object-oriented language but it contains no actual object-oriented programming:

Another attempt at object-orientation in Java

Object-oriented programs involve objects computing by sending messages to other objects, updating the internal (hidden) states of those objects as those messages are executed.

As the TPL notes point out, we could try to create a class called GCDInteger and use it to define a gcd(…) function:

public class GCDInteger extends Integer {

public Integer gcd(Integer a) { 
  int y = a.intValue(); 
  int x = this.intValue();
  while (y != 0) { 
    int r = x % y;
    x = y; 
    y = r;
    } 
  return new Integer(x);
  }
}

This code demonstrates the most important object-oriented concept: work is done by sending messages to objects. Here we see the definition of a binary message .gcd(i) on a GCDInteger rather than a merely a static method with two arguments.

Although this is at least a tiny bit object-oriented it’s not even possible because Integer is a final class so we can’t just add that subclass.

Practical problems with this approach:

Note: It is possible to “cheat” at this by implementing Euclid’s algorithm using BigInteger — an arbitrary magnitude integer implementation. The BigInteger class allows the creation of objects that represent arbitrary magnitude integers with methods that implement basic arithmetic. This of course will carry a performance penalty and means longer, more complicated code.

Object-Oriented implementation in Smalltalk and Ruby

In order to demonstrate integer computation in an object-oriented way we need to use a language that performs arithmetic and logic using object-oriented method dispatch.

For example in Smalltalk we can simply add a new method to the existing Integer class.

greatestCommonDivisor: anInteger
      |x y |
	x := self.
	y := anInteger.
	[(y=0) not] whileTrue: [ |r|  
		r := self rem: y.
		x := y.
		y := r.]
	^ x.

In Smalltalk this is executed as: 42 greatestCommonDivisor:2

There are several curious things about computing with integers and booleans in Smalltalk:

In the more conventional syntax of Ruby we can define:

class Fixnum
  def gcd(y)
    x=self
    while y!=0 do
      r = x%y;
      x = y;
      y = r;
    end
    return x
  end
end

Unlike Smalltalk, ruby implements the while loop in the conventional, imperative manner. The other point to note is that we’re not defining the Fixnum class above, just “re-opening” it to add a new method definition.

The keyword return is optional in ruby but has been included for clarity here. Where return is not present the method returns the value of the last expression computed.

Classless Object-Oriented Programming

The Self language dispensed altogether with the notion of classes. Self is an experimental simplification of Smalltalk-80. Other more common languages to use classless object-oriented programming include Javascript and Ruby. This style of object-oriented programming is often referred to as Prototype-based Programming

Ruby is an interesting example because it takes a hybrid approach to object-oriented representation. Classes exist, but individual method definitions can be attached to objects at runtime. This leads to an interesting strategy for implementing gcd:

What you should be able to do in ruby:

class Fixnum
  def gcd(i)
    r = i % self
    return r.gcd(self)
  end
end

def 0.gcd(i)
  return i
end

Rewriting this code in Self is beyond the scope of this post…

Quick recap of broken Java language concepts causing trouble here

Summary