proposal: spec: generics: make type parameters discoverable from interfaces

[pcostanza]

Author background

• Would you consider yourself a novice, intermediate, or experienced Go programmer?

Experienced.

• What other languages do you have experience with?

C, C++, Common Lisp, Java, Modula-2, Oberon, Pascal, Prolog, Scheme.

Related proposals

This proposal is a feature that adds to the current generics proposal.

Proposal

• What is the proposed change?

The idea of this proposal is to make type parameters discoverable through type switch statements.

• Who does this proposal help, and why?

I am currently implementing a matrix library in Go 1.18 (beta/gotip version). It would be helpful to provide polymorphic function signatures, and for that it would be good to make type parameters discoverable from interface types. Otherwise, users of the library will always have to be explicit which specific function signatures they want.

Example: There is an element-wise multiplication operation both applicable to vectors and matrices:

func ElementWiseMultVector[T Number](v1, v2 Vector[T]) Vector[T] {...}
func ElementWiseMultMatrix[T Number](m1, m2 Matrix[T]) Matrix[T] {...}

(This is a simplified example, the actual library requires more parameters and more type parameters.)

It would be good to be able to provide a more abstract function like this:

func ElementWiseMult(o1, o2 any) any {
     switch c1 := o1.(type) {
     case Vector[T Number]:
          return ElementWiseMultVector(c1, o2.(Vector[T]))
     case Matrix[T Number]:
          return ElementWiseMultMatrix(c1, o2.(Matrix[T]))
     default:
          panic("invalid type")
     }
}

• Please describe as precisely as possible the change to the language.

With "discoverability" I mean that the type switch clauses can introduce new constrained type parameters which then bind to the concrete type of the underlying value.

• Is this change backward compatible?

I believe so.

• Alternatives

With the current specification, it is already possible to "discover" types by requiring the user to explicitly pass them, as follows:

func ElementWiseMult[T Number](o1, o2 any) any {
     switch c1 := o1.(type) {
     case Vector[T]:
          return ElementWiseMultVector(c1, o2.(Vector[T]))
     case Matrix[T]:
          return ElementWiseMultMatrix(c1, o2.(Matrix[T]))
     default:
         panic("invalid type")
     }
}

I believe with the proposal above, the code is easier to use:

ElementWiseMult[float64](m1, m2)    // vs.
ElementWiseMult(m1, m2)

Note that, to the best of my understanding, type inference cannot help with avoiding having to pass the type parameter when the parameters are of type any.

It may also be the case that the Go community prefers the explicit function signatures in general and prefers to discourage polymorphic signatures, for example because they delay checks of type correctness from compile time to runtime.

Costs

I don't understand the current implementation of type parameters, so I don't know what the incurred costs would be.

[thepudds]

Hi @pcostanza, does this overlap with #45380?

[pcostanza]

Hi @thepudds. No, it doesn't. #45380 can already be expressed with:

switch any(v).(type) {
case ...
}

This proposal can't.

[ianlancetaylor]

It's an interesting idea but I don't see how to implement this. It means that we can have arbitrary generic code inside a non-generic function. That can only work if the non-generic function is generic, but it's not.

[pcostanza]

Alternative idea:

func ElementWiseMult[S any](o1, o2 S) any {
     switch c1 := o1.(type) {
     case Vector[T Number]:
          return ElementWiseMultVector(c1, o2.(Vector[T]))
     case Matrix[T Number]:
          return ElementWiseMultMatrix(c1, o2.(Matrix[T]))
     default:
          panic("invalid type")
     }
}

So, given var v1, v2 Vector[float64], S would be bound to Vector[float64]. Therefore, the first case would match, and T would then be bound to float64.

[bcmills]

@pcostanza, for a compiler using a stenciling approach, that would require the compiler to identify the set of all types T that implement Number and may be used to instantiate Vector or Matrix for any variable passed to ElementWiseMulti. The same is true for the “GC shape” implementation approach, if the type-constraint is not as restrictive as something like Number.

Solving those instantiations in general involves either solving a very difficult static-analysis problem, or instantiating things conservatively — and producing massive binary bloat in the process (for hypothetical instantiations that end up not actually being reachable).

As far as I can tell, that all but forces the implementation to use the “dictionary” approach, which seems like a high cost to pay relative to the value of being able to write these kinds of type-switches.

[pcostanza]

@bcmills I realize that I should have described the underlying problem before suggesting a solution (which rather looks like a non-solution based on your explanation). The underlying problem is as follows: Among other things, the library is supposed to be able to load matrices from input files, like the matrix market file format, for example. Unfortunately, the element type for a matrix stored in such an input file is also part of the contents of that file. This means that when opening the file, you cannot statically know in the Go source code what element type to expect. Effectively:

m, err := ReadMatrixFile("foo.txt")

Since the type cannot be known in advance, I am currently returning any from ReadMatrixFile. This in turn means I have to do a manual dispatch afterwards:

	m, err := ReadMatrixFile("foo.txt")
	handle(err)
	switch m := m.(type) {
	case Matrix[uint8]:
		processMatrix[uint8](m)
	case Matrix[int8]:
		processMatrix[int8](m)
	case Matrix[uint16]:
		processMatrix[uint16](m)
	case Matrix[int16]:
		processMatrix[int16](m)
	case Matrix[uint32]:
		processMatrix[uint32](m)
	case Matrix[int32]:
		processMatrix[int32](m)
	case Matrix[uint64]:
		processMatrix[uint64](m)
	case Matrix[int64]:
		processMatrix[int64](m)
	case Matrix[float32]:
		processMatrix[float32](m)
	case Matrix[float64]:
		processMatrix[float64](m)
	default:
		panic("unknown matrix element type")
	}

I'm already seeing this in several places in the code, and processMatrix is always a different function call. Since type parameters are not first-class, I don't see a way how to abstract away from this and make this less cumbersome to write. My "discoverability" idea above was a suggestion how to make this work...

[bcmills]

@pcostanza, certainly there are places where this kind of type-switch would be useful. (In type theory, in is formalized as a “dependent sum type” or “Σ type”. It's useful enough to have been fairly well studied.)

So I agree that it addresses a legitimate underlying problem — I'm just not sure that the increase in utility is worth the additional constraints it would impose on Go implementations.

[ianlancetaylor]

I would put it this way: I don't see any feasible way that this can be implemented. If nobody can describe a way to implement this, then this proposal can't be accepted. Sorry.

[ianlancetaylor]

Closing as infeasible.

[pcostanza]

The code that triggered this proposal is open sourced by now. You can find examples of the issue in the following places:

• https://github.com/intel/forGraphBLASGo/blob/main/api_Vector.go lines 265-295

• https://github.com/intel/forGraphBLASGo/blob/main/api_Matrix.go lines 360-390

• https://github.com/intel/forLAGraphGo/blob/main/api_BreadthFirstSearch_vanilla_test.go lines 242-283

• https://github.com/intel/forLAGraphGo/blob/main/api_TriangleCount_test.go lines 136-177

I'm not advocating for my proposal above anymore, just wanted to ensure that the underlying issue is illustrated by somewhat more realistic examples.