Reading 19: Writing a Program with Abstract Data Types

Let’s call this a MatrixExpression. To make the definitions easier to read, we’ll abbreviate that to MatExpr.

Let’s define some operations:

And the one we really want:

This problem is a natural one for a recursive datatype.

MatExpr = Identity + Scalar(value:double) + Matrix(array:double[][]) + Product(m1:MatExpr, m2:MatExpr)

/** Represents an immutable expression of matrix and scalar products. */
public interface MatrixExpression {
    // Datatype definition:
    //   MatExpr = Identity + Scalar(value:double)
    //             + Matrix(array:double[][]) + Product(m1:MatExpr, m2:MatExpr)
    // ...
}

class Identity implements MatrixExpression {
    public Identity() {
    }
}

class Scalar implements MatrixExpression {
    private final double value;
    // RI: true
    // AF(value) = the real scalar represented by value

    public Scalar(double value) {
        this.value = value;
    }
}

class Matrix implements MatrixExpression {
    private final double[][] array;
    // RI: array.length > 0, and all array[i] are equal nonzero length
    // AF(array) = the matrix with array.length rows and array[0].length columns
    //             whose (row,column) entry is array[row][column]

    public Matrix(double[][] array) {
        this.array = array; // note: danger!
    }
}

class Product implements MatrixExpression {
    private final MatrixExpression m1;
    private final MatrixExpression m2;
    // RI: m1's column count == m2's row count, or m1 or m2 is scalar
    // AF(m1, m2) = the matrix product m1*m2

    public Product(MatrixExpression m1, MatrixExpression m2) {
        this.m1 = m1;
        this.m2 = m2;
    }
}

It’s always good to have a value in the datatype that represents nothing, so that we can avoid using null. For a matrix product, the natural choice is the identity matrix — an empty product expression is just the identity anyway. So let’s define that:

/** Identity for all matrix computations. */
public static final MatrixExpression I = new Identity();

Unfortunately, we’ll see that this is not a perfect situation: other MatExprs might also be the identity.

Let’s start implementing, starting with the make() creators.

We don’t want to expose our concrete rep classes Scalar, Matrix, and Product, so that clients won’t depend on them and we’ll be able to change them later (being ready for change).

So we’ll create static factory methods in MatrixExpression to implement make():

/** @return a matrix expression consisting of just the scalar value */
public static MatrixExpression make(double value) {
return new Scalar(value);
}

/** @return a matrix expression consisting of just the matrix given */
public static MatrixExpression make(double[][] array) {
return new Matrix(array);
}

Now let’s implement the isIdentity observer. Here’s a bad way to do it:

// don't do this
public static boolean isIdentity(MatrixExpression m) {
    if (m instanceof Scalar) {
        return ((Scalar)m).value == 1;
    } else if (m instanceof Matrix) {
        // ... check for 1s on the diagonal and 0s everywhere else
    } else ... // do the right thing for other variant classes
}

In general, using instanceof in object-oriented programming is a bad smell. Break the operation down into pieces that are appropriate for each class, and write instance methods instead:

class Identity implements MatrixExpression {
    // no fields
    ...
    public boolean isIdentity() {
(missing answer)
    }
}

class Scalar implements MatrixExpression {
    private final double value;
    // RI: true
    // AF(value) = the real scalar represented by value
    ...
    public boolean isIdentity() {
(missing answer)
    }
}

class Matrix implements MatrixExpression {
    private final double[][] array;
    // RI: array.length > 0, and all array[i] are equal nonzero length
    // AF(array) = the matrix with array.length rows and array[0].length columns
    //             whose (row,column) entry is array[row][column]
    ...
    public boolean isIdentity() { 
        if (array.length != array[0].length) {
(missing answer)
        }
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[row].length; col++) {
                double expected = (row == col) ? 1 : 0;
                if (array[row][col] != expected) {
(missing answer)
                }
            }
        }
(missing answer)
    }
}

class Product implements MatrixExpression {
    private final MatrixExpression m1, m2;
    // RI: m1's column count == m2's row count, or m1 or m2 is scalar
    // AF(m1, m2) = the matrix product m1*m2
    ...
    public boolean isIdentity() { 
        return m1.isIdentity() ❓ m2.isIdentity();
    }
}

Implementing isIdentity exposes an issue that we should have first discovered by writing test cases: we will not always return true for a Product whose value is the identity matrix (e.g. A × A⁠^-1). We probably want to resolve this by weakening the spec of isIdentity, so that it doesn’t guarantee to identify every multiplicative identity:

Let’s implement optimize(). Again, here’s a bad way to do it, which will quickly get us mired in weeds:

// don't do this
class Product implements MatrixExpression {
    public MatrixExpression optimize() {
        if (m1 instanceof Scalar) {
            ...
        } else if (m2 instanceof Scalar) {
            ...
        }
        ...
    }
}

If you find yourself writing code with instanceof checks all over the place, you need to take a step back and rethink the problem.

In particular, to optimize the scalars, we’re going to need two recursive helper operations, so we’ll add them to our abstract datatype:

These expressions will allow us to pull the scalars out of an expression and move them together in a single multiplication expression.

/** Represents an immutable expression of matrix and scalar products. */
public interface MatrixExpression {

    // ...

    /** @return the product of all the scalars in this expression */
    public MatrixExpression scalars();

    /** @return the product of all the matrices in this expression in order.
     * times(scalars(), matrices()) is equivalent to this expression. */
    public MatrixExpression matrices();
}

Now we’ll implement them as expected:

class Identity implements MatrixExpression {
    // no fields
    ...
    public MatrixExpression scalars() { return this; }
    public MatrixExpression matrices() { return this; }
}

class Scalar implements MatrixExpression {
    private final double value;
    ...
    public MatrixExpression scalars() { return this; }
    public MatrixExpression matrices() { return I; }
}

class Matrix implements MatrixExpression {
    private final double[][] array;
    ...
    public MatrixExpression scalars() { return I; }
    public MatrixExpression matrices() { return this; }
}

class Product implements MatrixExpression {
    private final MatrixExpression m1, m2;
    ...
    public MatrixExpression scalars() {
        return times(m1.▶▶A◀◀, m2.▶▶B◀◀);
    }
    public MatrixExpression matrices() {
        return times(m1.▶▶C◀◀, m2.▶▶D◀◀);
    }
}

Recall that MatrixExpression.I is the constant we defined to represent the identity matrix. The implementations of Scalar.matrices() and Matrix.scalars() return I to represent an empty product. We could also have returned new Identity() here, but there is no need to create a new object when we already have an immutable constant I.

With these helper functions, optimize() can just separate the scalars and the matrices:

class Identity implements MatrixExpression {
    ...
    public MatrixExpression optimize() { return this; }
}

class Scalar implements MatrixExpression {
    ...
    public MatrixExpression optimize() { return this; }
}

class Matrix implements MatrixExpression {
    ...
    public MatrixExpression optimize() { return ▶▶A◀◀; }
}

class Product implements MatrixExpression {
    ...
    public MatrixExpression optimize() {
        return times(▶▶B◀◀);
    }
}