go2draft-contracts-response-auxiliary-types.md

Response to the Go 2 Contracts Draft Design:
Auxiliary Types

Steven Blenkinsop
September 1, 2018

Summary

This response concerns generic types which are found in the signatures of methods on the inputs to a contract which are not themselves inputs to the contract, for example the type of elem in elem := stack.Pop(), where the type of stack is an input to the contract. It suggests formalizing these types as part of the signature of a contract, like

contract stacker(stack Stack) (elem Elem) { ... }

so that they can be used in the signatures of generic functions:

func Peek(type Stack stacker)(stack Stack) (elem stacker.Elem) { ... }

/*** OR ***/

func Peek(type Stack, Elem stacker)(stack Stack) (elem Elem) { ... }

Introduction

The Go 2 contracts draft design sets out a proposal for how to extend the Go programming language with a generics capability. I originally intended to write a general response to the draft design, but found there was a particular aspect of the design which I felt was underdeveloped, that being the handling of auxiliary types in contracts. I've decided to focus on that aspect in this response.

To illustrate what I mean by "auxiliary types in contracts", I'm going to start with an excerpt from the draft design:

What does := mean in a contract body?

If a contract body uses a short declaration, such as

s := x.String() 

this does not provide any information about the result parameter of the String method. This contract body would match any type with a String method that returns a single result of any type. It's less clear what it permits in the function using this contract. For example, does it permit the function to call the String method and assign the result to a variable of empty interface type?

In this case, we could step around the question by just changing the declaration to var s string = x.String(). This isn't particularly illuminating, so let's change the example somewhat:

contract stacker(stack Stack) {
	var ok bool
	elem, ok := stack.Pop()
	stack.Push(elem)
}

We can take two things away from this example. The first is that this contract does tell us something about the result parameter of the Pop method: it can be used as an argument to the Push method. The second is that code taking advantage of this property can work irrespective of the actual type of the result parameter of Pop (the element type of the stack). Generic code using this contract can accept stacker types with different element types and work just fine:

func DupTop(type Stack stacker)(stack Stack) (Stack, bool) {
	elem, ok := stack.Pop()
	if ok {
		stack.Push(elem)
		stack.Push(elem)
	}
	return stack, ok
}

There is a third observation we can make. As is, there's no way to talk directly about the element type of Stack. For any type Stack, there is a unique element type, the existence of which is implied by the body of the stacker contract, but which is not an input type to the contract. Types like this are what I'm referring to when I say "auxiliary types in contracts".

Of course, it could be argued that auxiliary types are not part of the design presented in the contracts draft proposal and that I'm just inventing them. The response to my saying they are underdeveloped might very well be to say "we don't want those anyway". However, as I feel I've demonstrated above, encountering unknown types whose identities depend on the inputs to a contract while not being inputs themselves is an unavoidable consequence of the contracts design, and so I feel that a complete contracts proposal needs to address these auxiliary types.

Auxiliary types as inputs to a contract

Contracts as presented in the draft proposal have exactly one way to talk about a generic type: as an input parameter. One question to explore in relation to auxiliary types under the contract proposal is whether they can be lifted to input types, allowing us to talk about them in the same way as other generic types. Naively, we could try to do this as follows:

contract stacker_v2a(stack Stack, elem Elem) {
	var ok bool
	elem, ok = stack.Pop()
	stack.Push(elem)
}

One problem that immediately arises is that this doesn't say quite the same thing as before. In the introductory example, we could say that the return type of the Pop method was assignable to the input type of the Push method because the type of elem was inferred to be identical to the return type of Pop. Now, we can only say that the return type of Pop is assignable to an arbitrary type Elem, which is in turn assignable to the input type of Push. This is problematic, in particular because assignability is not transitive(!). This also means that Elem no longer has a unique identity given an instantiation of Stack, which is the property I intended to discuss.

We can adjust the contract to retain this property in multiple ways. The most obvious is to use an interface conversion to specify the precise signature of Pop. Or we could get creative:

contract stacker_v2b(stack Stack, elem Elem) {
	var ok bool
	elem2, ok := stack.Pop()
	
	// Pointer types are only assignable if their element types are identical. Thus,
	// `Elem` can be determined to be identical to the inferred type of `elem2`, which
	// is identical to the return type of `Pop`.
	var _ *Elem = &elem2
	
	stack.Push(elem)
}

(Aside: A potential hazard with the contracts design is that it encourages people to design interfaces based on current properties of the language. If, say, the assignability rules were to change, then the meaning of this contract would change subtly as well. Normally, changing a language to accept more code as valid would be backward compatible, but with contracts, we're relying on the restrictiveness of the existing language to determine what we're allowed to do with generic types. Multiply this over every aspect of contracts where we're saying "being able to write this code means that property holds" and we have a fairly substantial hinderance to future language evolution.)

We would then rewrite our DupTop function:

func DupTop_v2(type Stack, Elem stacker)(stack Stack) (Stack, bool) { ... }

Right here, you might spot a problem with using an input type to represent an auxiliary type: anyone who wants to call DupTop_v2 will have to explicitly supply type arguments because Elem does not appear in the input parameter list and thus cannot be inferred. Using input types to model auxiliary types is thus inadequate.

Auxiliary types as output types

If auxiliary types don't work as an input, then maybe they work as an output. We can add output type parameters to contracts, and use these to represent auxiliary types:

contract stacker_v3(stack Stack) (elem Elem) {
	var ok bool
	elem2, ok := stack.Pop()
	
	// Pointer types are only assignable if their element types are identical. Thus,
	// `Elem` can be determined to be identical to the inferred type of `elem2`, which
	// is identical to the return type of `Pop`.
	var _ *Elem = &elem2
	
	stack.Push(elem)
}

This looks very similar to the previous design, except that the element type appears in a second set of parentheses represent outputs from the contract. Code using this contract could look identical to the previous design:

func DupTop_v3(type Stack, Elem stacker_v3)(stack Stack) (Stack, bool) { ... }

The difference is that the compiler knows that the Elem type does not need to be supplied by the caller. The compiler would instead determine the type of Stack, and then unify Elem with the return type of the Pop method. It's somewhat unfortunate to have to list Elem this way when DupTop_v3 doesn't actually use it in it's signature, though. The actual name given to the type is only really for potential use within DupTop_v3, which seems somewhat like exposing an implementation detail. However, doing it this way does allow us to return the Elem type if we wanted to:

func Peek(type Stack, Elem stacker_v3)(stack Stack) (Elem, bool) {
	elem, ok := stack.Pop()
	if ok {
		stack.Push(elem)
	}
	
	return elem, ok
}

While I've syntactically distinguished input types and output types in the contract definition, it's also possible for the compiler to just figure out that it can infer the output types based on the input types on its own, and just have a single parameter list. I think being explicit here seems more straightforward in terms of defining your interface and for describing how the implementation should work.

Auxiliary types as associated type aliases

The concepts draft proposal for Go 2 isn't the first time this has come up. A solution common in other languages is to use associated type aliases. The basic idea behind an associated type alias is to be able to write:

type IntStack struct { ... }
type IntStack.Elem = int

This is how we would define the stacker contract using associated type aliases:

contract stacker_v4(stack Stack) {
	var ok bool
	
	elem, ok := stack.Pop()
	var _ *Stack.Elem = &elem
	
	stack.Push(elem)
}

This contract requires Stack to have an associated type alias Stack.Elem which is identical to the return type of Pop. By using an associated type alias, we can refer to the element type of any type parameter bound by the stacker_v4 contract without the element type needing to appear as a distinct type parameter. This changes how we define the function Peek:

func Peek(type Stack stacker_v4)(stack Stack) (Stack.Elem, bool) {
	elem, ok := stack.Pop()
	if ok {
		stack.Push(elem)
	}
	
	return elem, ok
}

If we weren't returning an element, we wouldn't mention Elem in the signature at all. Stack would still be required by the contract to have the Stack.Elem associated type alias, however.

Other languages might include associated types in their interface equivalent. However, an associated type wouldn't be very useful in a Go interface, since having the input/output types of an interface method depend on the dynamic type of the interface value wouldn't work under Go's current runtime model. Making this work would require the associated type alias to be treated as generic at runtime, which goes against the implementation-agnosticism present in the existing contracts draft proposal. Contracts therefore seem like the more appropriate place to leverage associated type aliases in the draft design.

A disadvantage of associated type aliases is that they might fall on the wrong side of the line as far as "interfaces" (contracts in this case) being implicitly satisfied. This is going to be fairly subjective, but having to add a declaration to the definition of a type just so that the compiler can recognize that an existing method satisfies a contract is getting fairly close to a conformance declaration, and so associated type aliases might not be the right fit for Go's more ad hoc approach to polymorphism.

Hybrid approach – associated output types

The challenge with output types is that they always need to be declared in the signature of a function employing the contract they come from, even if they don't otherwise form part of the interface of the function. The challenge with associated type aliases is that they need to be declared by the types conforming to a contract just for the sake of conformance, which might fall on the wrong side of the line between implicit and explicit conformance. One way to combine the advantages of both approaches while mitigating the disadvantages is to use associated type-style syntax to access the output types of a contract.

contract stacker_v5a(stack Stack) {
	type Elem

	var ok bool
	
	elem, ok := stack.Pop()
	var _ *Stack.Elem = &elem
	
	stack.Push(elem)
}

func Peek(type Stack stacker_v5a)(stack Stack) (stacker_v5.Elem, bool) {
	elem, ok := stack.Pop()
	if ok {
		stack.Push(elem)
	}
	
	return elem, ok
}

I'm not entirely convinced the syntax for declaring the type in the contract is right. It might still be appropriate to use the output type-style syntax on the contract side instead, while still using the associated type-style syntax where the contract is used:

contract stacker_v5b(stack Stack) (elem Elem) { ... }

func Peek(type Stack stacker_v5b)(stack Stack) (stacker_v5b.Elem, bool) { ... }

Having the auxiliary type be associated with the contract rather than with a conforming type avoids requiring more explicit conformance on the part of types than is strictly necessary, and using associated type syntax prevents us from having to declare the type name in the type argument list where it doesn't really belong. This feels like a decent balance to me. Using a local type declaration like in stacker_v5a might still be useful when the type is only to be used internally to the contract to constrain the input types without exporting the type name to users of the contract.

Conclusion

There are several possible approaches for addressing the presence of auxiliary types in contract definitions. Having them as outputs of a contract would work, as would importing the idea of associated type aliases from other languages, though the latter might not be the best fit for Go's more ad hoc polymorphism. What I'm convinced doesn't work is ignoring the existence of auxiliary types, since they arise so naturally from the proposed design of contracts, and neither does attempting to treat them as input types, since this severely undermines the type argument inference needed to make generics useable.

Nice post!
FWIW I believe my suggestions here would remove auxilliary types from contracts without requiring any new syntax, albeit at some expressivity cost.