Josh's blog

Algebra with Go generics

I have been playing with the Go 1.18 beta. 1.18 is the version they are adding generics, so this is a good time to get up to speed with the changes. So far, I am reasonably fond of it, so here I am blogging about my experimentation.

Here’s a problem related to interfaces in pre-generics Go. Suppose we want an interface that captures the idea of a type where a value can make copies of itself. Since the copy of a value should have the same type as the original, it too can be copied. Thus, a first draft of Copier:

1
2
3
type Copier interface {
    Copy() Copier
}

And an example implementation:

1
2
3
4
5
6
7
8
9
type Foo struct {
    // ...some fields here...
}

func (f *Foo) Copy() Copier {
    // A shallow copy
    g := *f
    return &g
}

Note that Foo basically must be defined in the same package as Copier. This is a problem because interfaces are best defined where they are used (that is, there is some code that uses the methods defined by the interface), not where there happens to be some type that implements the interface - see code review comments. What happens when we try to separate Foo from Copier?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// .../usescopy/uses.go
package usescopy

// Copier defined here because Process needs to make copies
// of its input (for some reason).
type Copier interface {
    Copy() Copier
}

// Process makes a copy of x and then does something to it.
func Process(x Copier) {
    y := x.Copy()
    // ...
}

// .../foo/foo.go
package foo

import "usescopy"

type Foo struct { ... }

func (f *Foo) Copy() usescopy.Copier {
    g := *f
    return &g
}

To implement Copier, Foo has to return a Copier from Copy. In order for Copier to make sense in foo.go, the package defining it has to be imported. But the usescopy package defines Copier only in order to use it, and foo still has to be aware of the interface it is implementing! Heaven forbid usescopy also needs to refer to anything in foo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
package usescopy

import "foo" // but foo imports usescopy in order to implement Copier...

func Process(x Copier) {
    switch x.(type) {
    case *foo.Foo:
        //...
    }
}

The usual way around this issue is to let Copier be significantly weaker:

1
2
3
type Copier interface {
    Copy() interface{}
}

Now Foo just has to return interface{}. This is acceptable (Process can use a type switch or type assertion to recover the original type from the copy) but is unnatural for Foo. Surely foo’s Copy should return a *Foo?

We can! With generics. Let’s make Copier generic:

1
2
3
4
5
package usescopy

type Copier[T any] interface {
    Copy() T
}

It might look like this Copier is as weak as the one where Copy returns interface{}. Any method called Copy, with no arguments, that returns anything at all will satisfy some Copier, when what we want is for Copy to return the same type as the receiver. But this is about as good as we can do in the interface, because Copier can’t be used as a constraint on its own type parameter.

We probably want to use Copier generically too, so here is the genericised Process:

1
2
3
4
func Process[T Copier[T]](x T) {
    y := x.Copy()
    // ...
}

What nonsense is that? Actually it’s not - it’s totally fine.

Here, Copier[T] is being used as a constraint on the type argument T. A constraint that refers to the type being constrained? Yes, this works! What does it mean? It means T has to satisfy Copier[T], i.e. T has a Copy method that returns values of type T.

Since Process can only be called with things of any type T so long as T implements a Copy method that returns values of that same type T, the issue of Copier being apparently weak is a non-issue. Process gets a value of type T, and Copy returns another value of type T. Which was what we wanted.

This also solves the interface-implementation separation problem. The foo package can be completely unaware of Copier, and Copy can return the more useful and specific type *Foo instead of some interface:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
package foo

// Look ma, no imports!

type Foo struct { ... }

// Copy returns a pointer to a shallow copy of *f.
func (f *Foo) Copy() *Foo {
    g := *f
    return &g
}

Here’s a Go playground showing this in action.

What was that about algebra?

With that taster out of the way, I thought it might be nice to write some generic types that implement some ideas from algebra. This is going to use the “constraints referencing the type arguments being constrained” technique from above.

Go has a variety of inbuilt numeric types (int, float64, complex128, etc), and these can be fashioned into good examples. I like quite complex128, even though I rarely have a use for it. This built-in type implements complex numbers with floating-point components.

But suppose we only care about complex numbers that have integer real and imaginary components, and complex128 is for whatever reason unsuitable - maybe there is a need for exact integer precision but no need for range. There’s no inbuilt complexWithIntParts, so let’s implement it (and call it by its more traditional name):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
type GaussianInteger struct {
    Real, Imag int
}

// Add returns z+w.
func (z GaussianInteger) Add(w GaussianInteger) GaussianInteger {
    return GaussianInteger{
        Real: z.Real + w.Real,
        Imag: z.Imag + w.Imag,
    }
}

// Neg returns -z.
func (z GaussianInteger) Neg() GaussianInteger {
    return GaussianInteger{
        Real: -z.Real,
        Imag: -z.Imag,
    }
}

// Mul returns z*w.
func (z GaussianInteger) Mul(w GaussianInteger) GaussianInteger {
    return GaussianInteger{
        Real: z.Real*w.Real - z.Imag*w.Imag,
        Imag: z.Real*w.Imag + z.Imag*w.Real,
    }
}

and so on.

I’ve used Neg and Mul instead of Negation and Multiply because expressions with these methods can get verbose. Go (even 1.18) does not have operator overloading (I think this is a good thing!) so we must do with reasonably short method names. Hopefully they are still clear. (math/big uses the same names for the same operations.)

But! These methods would be exactly the same if we substituted for int any other arithmetic type like uint8, int32, float64 or, heck, even complex64 or complex128 (Complex numbers with complex parts! 😏😏😏) Good candidate for being generic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Arithmetic matches any of the built-in numeric types,
// as well as types whose underlying types are any of the
// built-in numeric types.
type Arithmetic interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ...
    ... | ~float32 | ~float64 | ~complex64 | ~complex128
}

// Complex implements complex numbers with real and imaginary
// parts of type T.
type Complex[T Arithmetic] struct {
    Real, Imag T
}

// Add returns z+w.
func (z Complex[T]) Add(w Complex[T]) Complex[T] {
    return Complex[T]{
        Real: z.Real + w.Real,
        Imag: z.Imag + w.Imag,
    }
}

// Neg returns -z.
func (z Complex[T]) Neg() Complex[T] {
    return Complex[T]{
        Real: -z.Real,
        Imag: -z.Imag,
    }
}

// Mul returns z*w.
func (z Complex[T]) Mul(w Complex[T]) Complex[T] {
    return Complex[T]{
        Real: z.Real*w.Real - z.Imag*w.Imag,
        Imag: z.Real*w.Imag + z.Imag*w.Real,
    }
}

// Then GaussianInteger is as easy as:
type GaussianInteger = Complex[int]

// I can't believe it's not complex128:
type Complex128 = Complex[float64]

// Just for fun:
type ComplexComplex = Complex[complex128]

I’m not done genericising Complex, however. So far, Add, Neg, and Mul of Complex[T] are implemented using built-in addition, negation, and multiplication operators of whatever T is. But what if we want to make complex numbers out of some other type, like big.Int, big.Float, big.Rat, or some other FunkyNumber I’ve never heard of? Well, as long as it has methods called Add, Neg, Mul, and so on that behave as expected, it could be made to work.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// Ring describes an algebraic structure having addition, 
// negation. and multiplication. Rings also have a zero element
// and an identity element.
type Ring[T any] interface {
    Add(T, T) T
    Neg(T) T
    Mul(T, T) T
    Zero() T
    Identity() T
}

// Complex implements complex numbers with components of any type T,
// using the arithmetic operations of any ring over T.
type Complex[T any, R Ring[T]] struct {
    Real, Imag T
}

// Add returns z+w.
func (Complex[T, R]) Add(z, w Complex[T, R]) Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Add(z.Real, w.Real),
        Imag: r.Add(z.Imag, w.Imag),
    }
}

// Neg returns -z.
func (Complex[T, R]) Neg(z Complex[T, R]) Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Neg(z.Real),
        Imag: r.Neg(z.Imag),
    }
}

// Mul returns z*w.
func (Complex[T, R]) Mul(z, w Complex[T, R]) Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Add(r.Mul(z.Real, w.Real), r.Neg(r.Mul(z.Imag, w.Imag))),
        Imag: r.Add(r.Mul(z.Real, w.Imag), r.Mul(z.Imag, w.Real)),
    }
}

// Zero returns 0 + 0i.
func (Complex[T, R]) Zero() Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Zero(),
        Imag: r.Zero(),
    }
}

// Identity returns 1 + 0i.
func (Complex[T, R]) Identity() Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Identity(),
        Imag: r.Zero(),
    }
}

Note that the math/big types don’t have methods Zero or Identity, so Complex doesn’t work out of the box with those. But it would be reasonably straightforward to implement adapters for them.

The only thing from this that grates against my Go instincts is the need for var r R to access the methods of R, but this is a minor complaint.

Ring is a decent approximation of what we want from an algebraic ring. What is missing from Ring is constraints on the behaviour of the methods: Add should be associative and commutative, Zero should return the additive identity, Mul should be distributive over Add, and so on. For now it is considerably beyond the capability of Go interfaces, so I will leave it for unit tests.

Complex[T, R] is both a struct containing Real, Imag T, and the operations using those values, but in the style of math/big: instead of adding z and w with z.Add(w), it is now z.Add(z, w). Since none of the methods of Complex[T, R] make use of the receiver value, it may make sense to make them all functions instead of methods, but there is no such thing as a “package interface” in Go.

Complex[T, R] is itself a Ring[Complex[T, R]]. So we can make complexes out of complexes out of complexes…

Finally, if we want this new Complex to work with the built-in types, we can use a generic to implement the operations defined by Ring:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// BuiltinRing implements Ring[T] using the built-in operators of T.
type BuiltinRing[T Arithmetic] struct{}

// Add returns x+y.
func (BuiltinRing[T]) Add(x, y T) T { return x + y }

// Neg returns -x.
func (BuiltinRing[T]) Neg(x T) T { return -x }

// Zero returns 0.
func (BuiltinRing[T]) Zero() T { return 0 }

// Mul returns x*y.
func (BuiltinRing[T]) Mul(x, y T) T { return x * y }

// Identity returns 1.
func (BuiltinRing[T]) Identity() T { return 1 }

// Some examples:

// Integer adapts int into a Ring.
type Integer = BuiltinRing[int]

// Real adapts float64 into a Ring.
type Real = BuiltinRing[float64]

// Cmplx adapts complex128 into a Ring.
// This is "Cmplx" and not "Complex" to distinguish it from the
// generic Complex type above.
type Cmplx = BuiltinRing[complex128]

// GaussianInteger implements the integral domain Z[i] as complex
// numbers with int parts, and operations from the ring of integers.
type GaussianInteger = Complex[int, Integer]