Type safety with object-oriented methods

Question

I'm trying to think of how to solve this problem correctly using object-oriented methods. The language isn't important—I would actually like to write code, but it's more the general principles I care about.

I want to implement a field: a collection of 'numbers' on which the operations +, -, *, and / operate. Further, I would like to be able to implement higher operations like ^ and cycle-finding which (1) do not need to be defined for a given field but which (2) can be overridden if desired, say for efficiency reasons.

Here's the catch. It's not good enough to declare

FieldElement power (FieldElement base, FieldElement exponent)

because I want type safety: it should not be possible to add, say, a member of a finite field to an integer.

Perhaps what I'm really looking for is a meta-object, or super-interface, or something that ties together different classes (one for integers, one for 7-adics, one for the finite field F_4, etc.). Or maybe there's something better.

N.B. Code is welcome (even encouraged) in answers, if it would be enlightening, but declarations are probably enough: presumably everyone here could write out the obvious methods for at least a few fields.

---

I'll mention other conditions which matter to me but are (apparently) unrelated to the main OO issue: I don't want field elements to carry their type information around, and further I want them to be lightweight (since I may need to deal with large arrays of field elements). These desiderata may not be achievable—though frankly I'm more likely to abandon OO here than efficiency. But an answer would be appreciated regardless, since I'm interested in learning about these issues even apart from the particular problem at hand.

Answer 1

This is called the binary method problem. Quick googling will reveal some (lots of) information. In particular, the article "On binary methods" by Luca Cardelli et al gives the subject a thorough treatment.

You may want to learn some Haskell to see how a practical programming language deals with this problem.

EDIT Loluca → Luca. Damn the tiny phone screen and its tinier keyboard ;)

Answer 2

I have tried to express these concepts in C# before, but I have encountered language barriers: language is not rich enough, or specific enough. For example, if I define an Element of a Field like this:

public abstract class FieldElement 
{
    public abstract FieldElement Add(FieldElement another);
    public abstract FieldElement SumInvert();
    public abstract FieldElement MultiplicationInvert();
    public abstract FieldElement MultiplyBy(FieldElement another);
    public abstract FieldElement One; //Multiplication neutral element
    public abstract FieldElement Zero; //Addition neutral element

    public FieldElement Subtract(FieldElement another)
    {
        return this.Add(another.SumInvert());
    }

    public FieldElement Divide(FieldElement another)
    {
        return this.MultiplyBy(another.MultiplicationInvert());
    }
    public virtual FieldElement Power(uint b)
    {
        if (b == 0)
            return this.One;
        else
        {
            FieldElement result = this;
            for (int i = 0; i < b - 1; i++)
                result = result.MultiplyBy(result);
            return result;
        }
    }
}

Then I define Real Numbers like this:

public class RealNumber : FieldElement
{
    public double Value { get; set; }

    public RealNumber(double value)
    {
        this.Value = value;
    }
    public override FieldElement Power(uint b)
    {
        return new RealNumber(Math.Pow(Value, b));
    }
    public override FieldElement Add(FieldElement another)
    {
        if (another.GetType() != typeof(RealNumber)) //Ugly typecast to enforce type-safety
            throw new ArgumentException("RealNumber expected in Add method");

        return new RealNumber(Value + (another as RealNumber).Value);
    }
}

I can then define generically operations on Field Elements (by using generics):

public class FieldOperations<T> where T: FieldElement 
{
    public T Add(T a, T b)        
    {
        return a.Add(b) as T;
    }
    public T Multiply(T a, T b)
    {
        return a.MultiplyBy(b) as T;
    }
    public T Subtract(T a, T b)
    {
        return a.Subtract(b) as T;
    }
    public T Divide(T a, T b)
    {
        return a.Divide(b) as T;
    }
    public T Power(T a, uint b)
    {
        return a.Power(b) as T;
    }   
}

And I will use it like this in code:

public class TestFieldOperations
{
    public static void TestAddRealNumbers()
    {
        FieldOperations<RealNumber> operations = new FieldOperations<RealNumber>();
        RealNumber a = new RealNumber(0.5);
        RealNumber b = new RealNumber(0.7);
        RealNumber c = operations.Add(a, b);
        RealNumber d = operations.Power(c, 3);
    }
}

Similarly, I could have FieldOperations on Vectors, FieldOperations on InvMatrix...

Being able to abstract the concept of Field operations in a type-safe and object-oriented way can be very powerful: being able to deal with numbers, vectors and (invertible) matrices arithmetic at the same level of abstraction.