Skip to content

Instantly share code, notes, and snippets.

@rogpeppe
Last active September 26, 2018 14:17
Show Gist options
  • Save rogpeppe/0a87ef702189689201ef1d4a170939ac to your computer and use it in GitHub Desktop.
Save rogpeppe/0a87ef702189689201ef1d4a170939ac to your computer and use it in GitHub Desktop.

Operator overloading in Go with contracts

Roger Peppe 2018-09-03

[Edit 2018-09-11 Reworked following feedback from @jba]

In his Go generics feedback document, Dominic Honnef writes "Contracts are nice, but where is the operator overloading?". In this document, I set down some thoughts about how operator overloading might be added to Go within the context of the new generics design, layered on top of the current design.

The central part would be a new package in the standard library. This package would hook a type-parameterized type up to chosen Go operators. The Go compiler would know how to rewrite operator syntax into method call syntax on associated interface methods. How that's done is implementation-defined, and the API itself is defined by a package, but contracts supply a way of reasoning about available operators without defining the mapping between operators and method names.

The compiler would be responsible for making sure existing values are reused when possible (hence the reason for the mutation semantics of method calls, akin to those in the math/big package).

// Package op defines a set of types that allow
// user-defined values to be operated on with Go
// operators.
package op

// NumericInterface defines a set of methods that a type
// may implement to provide operator overloading
// functionality.
//
// Most operations mutate the receiver. The zero value
// of T must be OK to use as a receiver.
type NumericInterface(type T) interface{
	// Set sets the receiver to the value of a. If the receiver
	// is changed later, a should not be changed as a result.
	Set(a T)
	// Add corresponds to the + operator. It
	// adds the two values a and b and stores the result
	// in the receiver.
	Add(a, b T)
	// Neg corresponds to the unary - operator. It sets
	// the reveiver to the negation of a.
	Neg(a T)
	Mul(a, b T)
	Div(a, b T)
	// EqZero reports whether the receiver is zero.
	EqZero() bool
	SetZero()
	// etc
}

contract NumericContract(t T) {
	NumericValue(T)(&t)
}

// Numeric defines the contract that's fulfilled by the Num
// type. It's also fulfilled by all the built in Go numeric
// types.
type Numeric contract(t T) {
	t + t
	t * t
	t / t
	t == t
	t > t
	t != t
	-t
	t = 0
	// etc
}

// Num provides values that can be operated with
// all the usual Go arithmetic operations.
type Num(type T NumericValueContract) struct {
	T
}

An example package that implements operator overloading for a given type. It's layered on top of the existing math/big package (hence the need for the double pointer indirection, as that package uses pointers already).

package bigop
import (
	"math/big"
	"op"
)

type Int = op.Num(bigInt)

type BigInt struct {
	*big.Int
}

func (z *BigInt) ensure() *big.Int {
	if z.Int == nil {
		z.Int = new(big.Int)
	}
	return z
}

func (z *BigInt) Set(a BigInt) {
	z.ensure().Set(a.Int)
}

func (z *BigInt) Add(a, b BigInt) {
	z.ensure().Add(a.Int, b.Int)
}

func (z *BigInt) Neg(a BigInt)
	z.ensure().Neg(a.Int)
}

func NewInt(x int64) Int {
	return op.Num(BigInt){big.NewInt(z)}
}

In order to make it clear in code that arithmetic operations might mean something unusual, we define a new keyword, operators, that allows a type that satisfies a contract with operators to use those operators in Go code. The syntax is:

operators Type Contract

where Type is a Go type and Contract is the name of a contract with one type argument. The operator overloading applies only to the file that the keyword appears in (similar to module identifier scope). Operators on the type mentioned in the contract are allowed in the code.

This is how one might use it:

package main
import (
	"math/bigop"
	"op"
)

operators bigop.BigInt op.Numeric

func main() {
	x := bigop.NewInt(5)
	y := bigop.NewInt(7)
	z := x + y * bigop.NewInt(2)
}

This would de-sugar into something like the following code:

package main
import "math/bigop"

func main() {
	x := bigop.NewInt(5)
	y := bigop.NewInt(7)
	z := new(bigop.BigInt)
	z.Set(y)
	z.Mul(y, bigop.NewInt(2))
	z.Add(x, z)
}

We could consider all the standard Go operators to be implicitly defined in each file:

operators int, float, int64, int32, int16, int8, uint64, etc op.Numeric

but maybe that's going a bit far. :-)

A more convenient interface

The above pointer-based interface might be considered inconvenient. Why can't we just return values instead of setting a value inside a pointer? The reason for having it this way is that it allows the compiler to be clever about allocating temporaries. Just as the big.Int type is designed that way - we can reuse existing values to avoid memory allocation overhead.

However, if we want a more convenient interface, it's not too hard to provide one:

// ByValue is the type of value expected by the ByValueNum adaptor.
type ByValue(type T) interface {
	Copy(a T) T
	Add(a T) T
	Neg() T
	Mul(a T) T
	Div(a T) T
	EqZero() bool
	Zero() T
	// etc
}

// ByValueNum adapts a value that implenents the ByValue interface
// into a value that implements NumericInterface.
type ByValueNum(type T ByValue) struct {
	T
}

func (z *ByValueNum(T)) Set(a ByValueNum(T)) {
	*z = z.new(a.Copy())
}

func (z *ByValueNum(T)) Add(a, b ByValueNum(T)) {
	*z = z.new(a.Add(b))
}

func (z *ByValueNum(T)) Neg(a ByValueNum(T)) {
	*z = z.new(a)
}

func (z *ByValueNum(T)) new(a T) ByValueNum(T) {
	return ByValueNum(T){a}
}

// etc
@jba
Copy link

jba commented Sep 10, 2018

NumericValue(T) is more general than it should be. A Go operator must have operands and a result of the same type. NumericValue(T) is satisfied by any typeU that implements it, even if U is different than T.

That interface and its BigInt implementation don't match the de-sugared code you write later. For instance, Add takes two arguments in the first two but only one in the last.

@deanveloper
Copy link

Something fun - many unary operators aren't needed to have functions. The go spec defines the following unary operators:

+x                          is 0 + x
-x    negation              is 0 - x
^x    bitwise complement    is m ^ x  with m = "all bits set to 1" for unsigned x
                                      and  m = -1 for signed x

I'd rather keep these the same if possible

@rogpeppe
Copy link
Author

@jba Very nice feedback, thank you!

NumericValue(T) is more general than it should be. A Go operator must have operands and a result of the same type. NumericValue(T) is satisfied by any typeU that implements it, even if U is different than T.

Yes, that's true, but the Num type ties together the receiver with the arguments:

type Num(type T NumericValue(*T)) struct {
	T
}

I may be wrong, but I think this specifies that the T held in the struct must be a value such that the interface NumericValue(*T) is satisfied; that is, for all types T the interface is satisfied if it has all the NumericValue defined on *T. That is if you try to use a different receiver type, say S, values of type S may well satisfy NumericValue(T), but when *S is not the same as T, you'll get a type error.

In fact, I am wrong. This works precisely the opposite of the way I intended. It does tie the receiver and argument together, but expects pointer values as the arguments, and a value receiver. Unfortunately in Go there is no way to specify "the type pointed to by this". And there probably shouldn't be. :)

We can do better with a contract, however:

contract NumericValueContract(t T) {
	NumericValue(T)(&t)
}

(Aside: This is a counter-example to my previously suggested contract simplification rules that only allow one operator per line; I can't currently think how to express this with those restrictions).

I've updated the gist to do this. I've also added an explicit operators keyword suggestion because it might actually make it palatable to me for real :)

That interface and its BigInt implementation don't match the de-sugared code you write later. For instance, Add takes two arguments in the first two but only one in the last.

Yup. Fixed now.

@wsc1
Copy link

wsc1 commented Sep 26, 2018

Interesting ideas!

For reference, when you wrote

// ByValue is the type of value expected by the ByValueNum adaptor.
type ByValue(type T) interface {
	Copy(a T) T
	Add(a T) T
	Neg() T
	Mul(a T) T
	Div(a T) T
	EqZero() bool
	Zero() T
	// etc
}

you have proposed something similar to my modification of the draft proposal

There is an issue in the above related to your gist, entitled "Unary contracts as types applied with example code" near the bottom. It would be interesting to see how your ideas relate and if or to what extent they can be made compatible.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment