Doing OO programming the right way

[CRGreathouse]

I'm trying to do something right in object-oriented programming. It's easy enough to come up with a bad, "non-object-oriented" solution, but I don't want to break the paradigm: it's appropriate, and also there's something to be said for using a language as it's intended.

The problem is one of inheritance. Suppose you want to create a number of children, each of which shares function and semantics from a parent. The parent might be a class, an abstract class, an interface, or something else. The parent has nontrivial functionality which relies on specific methods which will be defined only in children.

A quick mocked-up example should give some meaning to this. The code below is a Java-C# hybrid that should be easy enough for any OO programmer to read.

abstract class Group {
  // Abstract methods, must be overwritten
  public static abstract Group identity();
  public abstract Group add (Group a);
  public abstract Group copy ();

  public static Group + (Group left, Group right) {
    return left.copy().add(right);
  }

  // A real implementation of this function would use a binary ladder
  public Group scalarMult (Group a, int n) {
    Group x = Group.identity();
    for (int i = 0; i < n; ++i)
      x = x.add(a);
    return x;
  }
}


public class ZModN extends Group {
  private int value;
  private int modulus;

  // Overrides for abstract methods
  public static override Group identity() {
    // Code here
  }
  public override Group add (Group a) {
    // Code here
  }
  public override Group copy () {
    // Code here
  }


  // Custom programming
  public static ZModN chineseRemainder (ZModN a, ZModN b) {
    // ...
  }
}


public class Integer extends Group {
  private int value;

  // Overrides for abstract methods
  public static override Group identity() {
    // Code here
  }
  public override Group add (Group a) {
    // Code here
  }
  public override Group copy () {
    // Code here
  }


  // Override general method with a faster version for this type
  public override Group scalarMult (Group a, int n) {
    if (!(a is Integer))
      throw new Exception("...");

    int result = ((Integer)a).value * n;
    return new Integer (result);
  }
}

The big issue is how to deal with types. At best, the above code could be cobbled together but require constant casts and un/boxings. At worst, it won't compile because of conflicting requirements on types. Further, the code will always be ugly because each method will be filled with "X is Y" checks -- or, if C#, "X as Y". Would templates (Group<T>) be better? Is there a way (C#, C++, Java, etc.) to specify "the class itself"?

An obvious alternate method would be to build lightweight structs off an interface, copy/pasting the duplicate functionality. But this seems to be a bad idea... it leads to uneven updates and bug fixes. Also, the purpose here would be to force as many methods as possible to the parent (in this case, generic methods that work for any class) and that would defeat the purpose.

 

[-Job-]

I'm not 100% sure on this but i think that in C# if you don't use the override keyword, then you can redefine the method with a different return type - so for example your ZModN class would have two "add" methods with the same signature, the base one returning type Group and the ZModN one returning type ZModN.

I think that's what is discussed here:
http://en.csharp-online.net/CSharp_...nding_the_Overloaded_Return_Type_and_Property

 

[CRGreathouse]

I could make alternate methods for everything, sure. But then I can't use those methods with a (general) Group:

. . .
Group g;

if (a == 1)
  g = new ZModN (7, 11);
else
  g = new Integer (7);

. . .

g = g.add(g); // Is this 3 mod 11 or 14?

This isn't necessarily even unusual. I've often considered programs that would switch between, say, DoublePrec and QuadPrec classes, where DoublePrec would be a wrapper for double.

 

[CRGreathouse]

OK, I coded an actual C# example.

	public abstract class Group
	{
		public static abstract Group identity();
		public abstract Group inverse();
		public abstract Group copy();
		public abstract Group add(Group a);

		public static Group operator +(Group a, Group b)
		{
			return a.copy().add(b);
		}

		public static Group operator *(Group a, int n)
		{
			Group x;
			if (n <= 0)
			{
				if (n == 0)
					return Group.identity();
				n = -n;
				x = a.inverse();
			} else {
				x = a.copy();
			}

			Group acc = Group.identity();
			while (n > 1)
			{
				if ((n & 1) == 1)
					acc += x;
				x += x;
				n >>= 1;
			}
			return acc + x;
		}
	}

Sensible enough, right? A class implementing this (say, public class IntegerMod97 : Group) would simply define identity, inverse, copy, and add. It could also override operator+ or operator* for performance -- there may be better ways to do this for general groups.*

But static members can't be declared abstract, so public static abstract Group identity() is invalid. Perhaps I can do this:

		public static virtual Group identity()
		{
			throw new Exception("Not implemented!");
		}

but that seems to be something of a hack. Oh wait, I can't even do that -- static methods can't be abstract or virtual. So what now?* Actually this already causes problems without the virtual keyword, but this could be dealt with... probably easiest to choose different signatures for the methods.

 

[Hurkyl]

Solution 1: The thing you're missing is that what you call "Group" shouldn't be a type; it should be a different kind of object! e.g. you should have two types: Group and GroupElement. This way, scalar multiplication would be something like:

GroupElement operator*(size_t n, GroupElement g)
{
   Group G = g.parent();
   GroupElement x = G.identity();
   for(size_t i = 0; i < n; ++i) {
      x += g;
   }
   return x;
}

Both of the magma and sage computer algebra systems take this approach. I imagine most do, although I don't have direct knowledge.



Solution 2: C++ (and Java too, I think), at least, offer means to implement what you're trying, through templates and generics. This might work in java (the idea certainly works in C++), but I haven't played with generics enough to be absolutely sure.

public class GroupElement<G>
{
   // ...
   public GroupElement<G> ScalarMultiplyBy(int n) {
      GroupElement<G> x = G.identity();
      for(int i = 0; i < n; ++i) { x.add(this); }
      return x;
   }
}

The C++ template mechanism offers a different way to achieve polymorphism, and it happens at compile-time to boot! You can do something like this to achieve what you originally wanted (and you can do the Group/GroupElement thing with templates too, which I think is preferable):

template< typename T >
struct GroupTag { };

struct Integers : public GroupTag<Integers>
{
   int n;
   Integers(int n):n(n) {}
   static Integers identity() { return Integers(0); }
};

Integers& operator+=(Integers &a, Integers b) { a.n += b.n; return a;}

// GroupTag 'guards' this template against matching things that aren't group elements
template< typename G >
G operator*(int n, const GroupTag<G> &g_)
{
   const G &g = (const G&) g_;
   G x = G::identity();
   for(int i = 0; i <  n; ++i) { x += g; }
   return x;
}

This style of polymorphism seen in C++ has some signficiant performance advantages; when done properly, it eliminates most (if not all!) of the overhead of polymorphism, while retaining most of the useful design properties. (And you can mix virtuals with this mechanism to regain those remaining properties, if you need them)

Incidentally, note that the class GroupTag doesn't actually need to exist in the above example; it does simplify things when you get into more advanced stuff, though.

 

[CRGreathouse]

I can't get your examples to compile, even adding in stubs and such.

Even this modified C++ fragment throws an error:

class GroupElement
{
public:
	template<class G>
	GroupElement ScalarMultiplyBy(int n) {
		GroupElement x = G.identity();
		for(int i = 0; i < n; ++i)
			x.add(this);
		return x;
	}
}

 

[Hurkyl]

The second snippet was supposed to be java-esque. In C++ it would look like

template< typename G >
class GroupElement
{
public:
   // In class scope, If I don't explicitly indicate
   // the template parameter, it's assumed to be G
   GroupElement scalarMultiplyBy(unsigned int n) {
      GroupElement x = G::identity();
      for(unsigned int i = 0; i < n; ++i) { x.add(*this); }
      return x;
   }
};

And this would be somewhat semantically different; C++ creates a newGroupElement class for each G, whereas java does some other weird thing, whose subtleties I don't yet fully understand.

Of course, I would prefer to do it as in my third code snippet, rather than as in this fashion. The third snippet doesn't compile? That surprises me; I can't spot any problems with it by eye.

 

[Dale]

Instead of templates another thing you might want to look at would be the "Bridge" design pattern. Basically, you want to decouple the things that all groups have in common (like addition) from the implementation. That way you can use the abstract group class to write things like algorithms that use groups or are true for arbitrary groups, and not have to re-compile that stuff when you want to change the type of group.

 

[CRGreathouse]

Oh, I see how I misread that Hurkyl. I thought you meant that the code was for C++ and your comment "This might work in java" meant something like "this can be adapted to work in Java, too". But even though the code was clearly of the Java style I persisted in my original understanding.

The essence of your solution, as I see it, is the use of a non-static method (parent() in your case) to get the information. I suppose that could simply be taken further by implementing identity() directly as a non-static member -- especially if there is no use in the application for a parent class.


I was able to actually make something work (C#, here) though I had to throw much of what I wanted out:

public abstract class GroupElement
{
	public abstract GroupElement inverse();
	public abstract GroupElement copy();
	public abstract GroupElement identity();	// Should really be static...
	public abstract GroupElement add(GroupElement a);

	public virtual GroupElement mult(int n)
	{
		GroupElement x;
		if (n <= 0)
		{
			if (n == 0)
				return this.identity();
			n = -n;
			x = this.inverse();
		}
		else
		{
			x = this.copy();
		}

		GroupElement acc = this.identity();
		while (n > 1)
		{
			if ((n & 1) == 1)
				acc += x;
			x += x;
			n >>= 1;
		}
		return acc + x;
	}


	public static GroupElement operator +(GroupElement a, GroupElement b)
	{
		return a.copy().add(b);
	}

	public static GroupElement operator *(GroupElement a, int n)
	{
		return a.mult(n);
	}

	public static implicit operator string(GroupElement a)
	{
		return a.ToString();
	}
}


public class Z : GroupElement
{
	protected int n;
	public Z(int k)
	{
		n = k;
	}

	public override GroupElement inverse(){
		return new Z(-n);
	}

	public override GroupElement identity()
	{
		return new Z(0);
	}

	public override GroupElement copy()
	{
		return new Z(n);
	}

	public override GroupElement add(GroupElement a)
	{
		Z aa = a as Z;
		if (aa == null)
			throw new ArgumentException("Can't add elements from two different groups: " + this + " + " + a);
		return new Z(aa.n + n);
	}

	public override string ToString()
	{
		return string.Format("[{0}]", n);
	}

}


public class IntMod97 : GroupElement
{
	protected int n;
	public IntMod97(int k)
	{
		n = k;
	}

	public override GroupElement inverse(){
		return new IntMod97(-n);
	}

	public override GroupElement identity()
	{
		return new IntMod97(0);
	}

	public override GroupElement copy()
	{
		return new IntMod97(n);
	}

	public override GroupElement add(GroupElement a)
	{
		IntMod97 aa = a as IntMod97;
		if (aa == null)
			throw new ArgumentException("Can't add elements from two different groups: " + this + " + " + a);
		return new IntMod97((aa.n + n) % 97);
	}

	public override string ToString()
	{
		return string.Format("[{0} mod 97]", n);
	}
}

In particular, each operation requires type-shifting and testing. I would prefer to do this with actual type safety instead -- where the compiler won't let me add a Gaolis1024 and a ZMod101 -- but I guess this isn't possible without writing each class individually (and as such giving up the ability to use them in common).

 

[CRGreathouse]

Instead of templates another thing you might want to look at would be the "Bridge" design pattern. Basically, you want to decouple the things that all groups have in common (like addition) from the implementation. That way you can use the abstract group class to write things like algorithms that use groups or are true for arbitrary groups, and not have to re-compile that stuff when you want to change the type of group.

You've stated my purpose: to write generic group algorithms that work for any group I care to code a class for. The question is how to do this? If you have a reasonable idea I'd love to see it -- feel free to modify any of the examples on this thread.

 

[Dale]

Hmm, the Wikipedia entry for the http://en.wikipedia.org/wiki/Bridge_pattern" book.

Basically, in this case you would make an abstract class that defines a group element. The main data element of this class would be a reference to a group element implementation object which is also an abstract class. All of your algorithms can be members of the group element class, or derived classes, or simply functions which take a group element as an argument. All of your I/O, state, and basic operations are members of the group element implementation class.

As far as I can tell, this differs from the generics approach in one aspect: with the generics approach you have to recompile your algorithm code for each new specialization whereas the Bridge Pattern approach you simply need to link to your algorithm. However, as a result of this type errors can be caught at compile time with the generics approach, but only at run time with the Bridge approach.

 

[CRGreathouse]

Basically, in this case you would make an abstract class that defines a group element. The main data element of this class would be a reference to a group element implementation object which is also an abstract class. All of your algorithms can be members of the group element class, or derived classes, or simply functions which take a group element as an argument. All of your I/O, state, and basic operations are members of the group element implementation class.

I don't follow. Could you give a quick example?

 

[Hurkyl]

To clarify some points:
. Is C# an absolute requirement? Or are java or C++ usable?
. Are you trying to decouple the actual compilation, or merely the implementation?

 

[CRGreathouse]

To clarify some points:
. Is C# an absolute requirement? Or are java or C++ usable?
. Are you trying to decouple the actual compilation, or merely the implementation?

Good questions; I wish I had addressed these earlier.

I'm generally more comfortable with C++ and C# than Java, but any OO language is fine. In fact it might be useful to consider languages beside these two if other OO languages have features that would be better for this, though in the end I'll need something with at least the performance of C# -- no interpreted languages for CPU-intensive tasks!

When the points are generic (applying to most OO languages) it's probably best that everyone uses their personal favorite language -- I'll sort through them. :)

I'm only trying to decouple the implementation. I imagine myself building one very large file with a Group (or AbelianGroup or whatnot) that has many generic algorithms, then a second file with a number of relatively simple classes deriving from it.

 

[Hurkyl]

Are you familiar with C++'s standard template library?

Incidentally, what was the problem you had with my C++ example? I just copied what I wrote into MSVC++, and it compiles fine, and appears to work as expected.


One reason I suggest a design that has separate notions of "group" and "group_element" is that if you're designing an extensive library, you might want to do computations with groups themselves. For example, you might want to be able to do things like compute subgroups or quotient groups or product groups, so it would be convenient to have them as objects. And besides, if you were to have a type representing a family of groups (e.g. "integers_mod_n"), it would be convenient to have a group object containing the defining data, while the group_element objects simply refer back to their parent group.

 

[CRGreathouse]

Are you familiar with C++'s standard template library?

I use the STL, but I'm not sure how you would rate my familiarity with it.

Incidentally, what was the problem you had with my C++ example? I just copied what I wrote into MSVC++, and it compiles fine, and appears to work as expected.

Your code

template< typename G >
class GroupElement
{
public:
   // In class scope, If I don't explicitly indicate
   // the template parameter, it's assumed to be G
   GroupElement scalarMultiplyBy(unsigned int n) {
      GroupElement x = G::identity();
      for(unsigned int i = 0; i < n; ++i) { x.add(*this); }
      return x;
   }
};

worked fine, but it doesn't show how to deal with the conversion/testing/etc. issues that have been causing problems for me. If I have an abstract method GroupElement add (GroupElement a) and I want to implement it with my integer class Z, I'm forced to test both parameters to make sure they a is an instance of Z (since I can't add an integer to an arbitrary group element). Also, the natural result is a member of Z, but the prototype specifies that it's a GroupElement -- is there inefficiency or slicing there?

I'd love if there was some way to code

abstract class GroupElement{
  Your_Class add (Your_Class a) where YourClass : GroupElement;
}

but I don't know of that feature in any language.

 

[Dale]

I don't follow. Could you give a quick example?

I don't really know C# so no guarantees that this works.

public abstract class GroupElementKernel
{
	public abstract GroupElementKernel inverse();
	public abstract GroupElementKernel copy();
	public abstract GroupElementKernel identity();	// Should really be static...
	public abstract GroupElementKernel add(GroupElementKernel a);


	public virtual GroupElementKernel mult(int n)
	{
		GroupElementKernel x;
		if (n <= 0)
		{
			if (n == 0)
				return this.identity();
			n = -n;
			x = this.inverse();
		}
		else
		{
			x = this.copy();
		}

		GroupElementKernel acc = this.identity();
		while (n > 1)
		{
			if ((n & 1) == 1)
				acc += x;
			x += x;
			n >>= 1;
		}
		return acc + x;
	}


	public static GroupElementKernel operator +(GroupElementKernel a, GroupElementKernel b)
	{
		return a.copy().add(b);
	}

	public static GroupElementKernel operator *(GroupElementKernel a, int n)
	{
		return a.mult(n);
	}

	public static implicit operator string(GroupElementKernel a)
	{
		return a.ToString();
	}
}



public abstract class GroupElement
{
	public abstract GroupElement inverse();
	public abstract GroupElement copy();
	public abstract GroupElement identity();	// Should really be static...
	public abstract GroupElement add(GroupElement a);
	public abstract GroupElement setKernel(GroupElementKernel k)
	{
		kernel = k;
	}

	private abstract GroupElementKernel kernel;

	public virtual GroupElement mult(int n)
	{

		return kernel.mult(n);
	}


	public static GroupElement operator +(GroupElement a, GroupElement b)
	{
		return a.kernel + b.kernel;
	}

	public static GroupElement operator *(GroupElement a, int n)
	{
		return a.kernel*n;
	}

	public static implicit operator string(GroupElement a)
	{
		return a.kernel.ToString();
	}
}


public class Z : GroupElementKernel
{
	protected int n;
	public Z(int k)
	{
		n = k;
	}

	public override GroupElementKernel inverse(){
		return new Z(-n);
	}

	public override GroupElementKernel identity()
	{
		return new Z(0);
	}

	public override GroupElementKernel copy()
	{
		return new Z(n);
	}

	public override GroupElementKernel add(GroupElement a)
	{
		Z aa = a as Z;
		if (aa == null)
			throw new ArgumentException("Can't add elements from two different groups: " + this + " + " + a);
		return new Z(aa.n + n);
	}

	public override string ToString()
	{
		return string.Format("[{0}]", n);
	}

}


public class IntMod97 : GroupElementKernel
{
	protected int n;
	public IntMod97(int k)
	{
		n = k;
	}

	public override GroupElementKernel inverse(){
		return new IntMod97(-n);
	}

	public override GroupElementKernel identity()
	{
		return new IntMod97(0);
	}

	public override GroupElementKernel copy()
	{
		return new IntMod97(n);
	}

	public override GroupElementKernel add(GroupElement a)
	{
		IntMod97 aa = a as IntMod97;
		if (aa == null)
			throw new ArgumentException("Can't add elements from two different groups: " + this + " + " + a);
		return new IntMod97((aa.n + n) % 97);
	}

	public override string ToString()
	{
		return string.Format("[{0} mod 97]", n);
	}
}

The GroupElement doesn't do anything but provide a stable interface for developing algorithms. You can extend it with new classes implementing new algorithms, and they will automatically be applicable to all GroupElementKernels. You would not even need to recompile the algorithms, so they could be part of a library (unlike the template approach).

 

[Hurkyl]

I use the STL, but I'm not sure how you would rate my familiarity with it.

The container and algorithm libraries seem to be a shining example of separating algorithms from data types!

Your code ///

Nonono, my other piece of code in post #5. The one that was actually meant to exhibit how templates can be used effectively for this purpose.

(And if, for some reason, you really and truly insist on member functions, note that the scalar multiplication could be moved into the GroupTag<T> class)