Operator overloading

[crawshaw]

Operator overloading is viewed quite reasonably with skepticism. There are two concrete motivations for it in neugram.

The first is being able to build a user interface to a tool like TensorFlow in neugram that is as compelling (or more) as the standard python user interface. This involves performing a series of arithmetic operations on objects that build up a model of a program to execute.

The second is support for matrices. Not only a single, fixed in-memory model for matrcies, but large sparse matrices, or matrices that exist in GPU memory and whose operations need to be batched and communicated to a different program.

Both of these problems require arithmetic and indexing operations backed by arbitrary computation. Operator overloading can do this.

Proposal

Any type can have specifically-named methods the type checker will notice and use to implement operations on those types. Critically, named interfaces can also have these operator methods.

// Matrix is an n-dimensional float64 matrix.
interface Matrix {
    Dim() []int
    OpIndex(dims ...int) float64         // m[3,4]     => m.OpIndex(3,4)
    OpIndexSet(val float64, dims ...int) // m[3,4] = 0 => m.OpIndexSet(0, 3, 4)
    OpMul(v Matrix) Matrix               // m*n        => m.OpMul(n)
    OpAdd(v Matrix) Matrix               // m+n        => m.OpAdd(n)
    OpSub(v Matrix) Matrix               // m-n        => m.OpSub(n)
}

TODO

• Start method names with non-letter ⨂ instead of Op, to avoid conflicts?
• Allow a concrete type to have both interface ops and concrete ops? For example OpMul(x *Mat2) *Mat2 and OpMul(x Matrix) Matrix?
• Reference num proposal, for how to get the matrix type generic enough.

(The first comment of this issue is kept up-to-date with the current proposal. When commenting on it, quote any relevant sections and respond to the quote.)

[crawshaw]

Some more thinking about this. I no longer see why the methods should be obscure names. In fact, they could be the most obvious names. It would be nice if the operator overloading "just worked" for the gonum matrix types.

That means:

interface {
    At(i, j int) U
}

would translate into [,]U. And the one parameter version of At would mean []U. For a mutable table/slice, there's the extra method:

interface {
    Set(i, j int, v U)
}

(With the similar Set(i int, v U) for slices.)

The arithmetic operators are trickier. In gonum the concrete types implement methods that yield the interfaces:

interface {
    Mul(a, b Matrix)
}

There are two points here. Firstly, this is an in-place modification method. The problem is then to compile c = a * b, we need a concrete type to initialize c. What it is? There is a far more obvious method Mul(a Matrix) Matrix which does not have this problem. (I would be willing to support both if I could think of a solution to this.)

Secondly, and more importantly, the gonum mat64 package does not define this method on the Matrix type. It avoids it for a good reason, a Matrix is not necessarily mutable. But that means we cannot do a static analysis of the multiply. We could do the analysis dynamically, but that means we have to successfully compile all sorts of wishy-washy code and see the failures at runtime.

Concretely, if mat64.Matrix defined what we needed statically, that is:

type Matrix interface {
    Mul(a Matrix) Matrix
}

Then the Neugram code:

func ourmul(a, b mat64.Matrix) mat64.Matrix {
    return a * b
}

would compile into the equivalent Go:

func ourmul(a, b mat64.Matrix) mat64.Matrix {
    return a.Mul(b)
}

But if we were to support the Matrix type without the Mul on it (but on many of the concrete implementations) then the ourmul neugram code would have to compile to this Go:

func ourmul(a, b mat64.Matrix) mat64.Matrix {
    return a.(interface { Mul(a mat64.Matrix) mat64.Matrix }).Mul(b)
}

Gross. I think for now this is off the table.

All of which is unfortunate, because it means the gonum mat64 package won't really work out of the box.