No Generics - Type Binding on Imports
Martin Leiser
Hi there
I am aware that the proposal to add generics has been accepted, so the discussion of whether or not Go will get generics is answered. For better or for worse.
I worked on a different approach since a few years, not very intensive, and in spite of this fact, I now want to tell you about:Binding interface types on import
See in: https://github.com/leiser1960/importbinding/blob/master/README.md
I did not speek up yet, because it simply was not ready for
discussion in my eyes.
Why do I think the accepted proposal is not good enough?
Technically it seem sound and consistent to me and has all the
bells and whistles you would expect. And all the Features. And
close enough to the way other languages define generics.
So what do i dislike?
Hmmm... Let me answer another question first:
What do I love about Go?
Its simplicity. And Simplicity is
Complicated
And that is IMHO the problem of the accepted generics proposal,
the lack of simplicity.
To explain this, let me start with a language design question:
What is needed for adding "monomorphic generic types" to Go?
Go already has a polymorphic generic type mechanism: "interface types".
So you have to start from this (as the accepted proposal does) and add to things:
- A way to define type parameters.
- A way to bind the type parameters to concrete types at
compile time
The accepted proposal does so by:
1. Adding positional type parameters to type and function definitions
2. Adding a syntax for binding concrete types to the type parameters on use of the types and functions.
With the proper brackets it is readable. And of course there are more goodies in the propsal such as:
- An extension to the descriptive power of "interface types".
- type inference rules to eliminate the need of the additional type parameters in certain cases.
Both are great for functional libraries such as "sort.go", but
does not help for container types such as "container/list.go".
And the proposal is long because any generic type mechanism is
complicated to implement and tricky to integrate in the language.
This is the obviously complicated part.
But the proposal lacks the simplicity and elegance of for example:
- the way Go integrates inheriting method from a typ by simply omitting the attribute name in a struct definition
- the way Go defines the types of numerical constant expressions for the purpose of type inference
incredibly simple to use and explain. No need for an additional
syntactic element at all.
And completely different from the way other languages treat this.
The accepted proposal more or less follows the syntactic path taken since Ada, over C++ and Java and all the other languages.
It this good enough?
Can we do better?
I think so. But How? Remember we need to do two things:
- A way to define type parameters.
- A way to bind the type parameters to concrete types at
compile time
Is suggest doing this on the package level, not the individual types or functions:
1. Use named interface types as implicit type parameters of a package
2. Bind the named types on import
With the first I simply mean any declaration of the form:
type ElementType interface {}
e.g. The type Locker in
sync.go.
You do not find such a declaration in "containter/list.go"
. But it would be simple task to add such a line and replace all
existing occurences of "interface{}" by "ElementType". Not
changing the behaviour at all.
As a go proverb says: interface
nothing says nothing
But after we named it "ElementType" we can get a hold of it and bind it in the package we intend to use e.G. a "list of strings":
import "container/list" type ElementType string
augmenting the existing "import" clause by this type binding. We say:
We bind (the binding) type "string" to (the bound type) "list.ElementType".
We bind the type string to the type list.ElementType in the
import of package list.
It is as simple as this.
But what does this mean?
It means two things:
1. binding type must implement the bound type.
2. the bound type is treated as if defined by:
type BoundType BindingType
in the imported package.
1. is trivial in our example, because interface{} is implemented by any time.
2. is trivial in our example, because "string" is a standard
type.
The general case is not so trivial, think of the binding type
being defined locally and private to the package.
I tried to give a semantic description in my definition in Binding
interface types on import but it is not as elaborate as the
accepted proposal.
The semantics is defined by a set of program transformations back
to a Go 1 program.
Is this simplicty?
I think so, ok not as simple as inheritance, because I have to
add a syntactic element: The type binding on Import.
But definitely a simpler than the accepted proposal.
Last features. If you need two different bindings in one package, say a list of string and a list of int you may use:
import "container/list" intlist type ElementType = int
import "container/list" stringlist type ElementType = string
And then simply pick either the package name: "intlist" or "stringlist" e.g.
myintlist := intlist.New()
mystringlist := stringlist.New()
This makes myintlist.Value of type int, whereas
mystringlist.Value is of type string.
And if you think of the type "Map" in "sync.go": You need a way to bind more than one type on a single import: sync.Key and sync.Value:
import "sync.go" type Key string; Map mySyncdata
But now we have all of the syntax by example. Simple to use.
You may not bind all "named interface types" on the import, the
above does not bind the Type "Locker", so the "Cond"
type remains polymorphic.
The definition of a generic package is go 1 compatible.
You only have to "name" the parameter types for use by type
binding imports. Which improves the documentation as well.
Not convinced? Lets move from Go 1 polymorphic generics to Go 2
monomorphic use, again using the "container/list.go" example.
It requires two sorts of changes:
1. Add the required type binding to the import clause, see
above
2. delete the type casts needed for accessing the "Value" Attribute of the "Element" struct:
if "" = (string)mystringlist.Value {
has to be changed to:
if "" = mystringlist.Value {
Try the same with the accepted proposal.
But a last word:
So behind the scenes there is more to it:
- there is an additional restriction for "named interface
types" necessary in order to allow them to be used as type
parameters.
- there are new semantic hurdles because of the type parameters being on the package level.
- I did not describe any "type inference rules" yet, but it should be possible to add this for typical functional libraries such as "sort.go".
- type bindings my even be transitive, if the binding type is itself a exported interface type.
So the a full fledged proposal may end up as long as the accepted
proposal. That is the complicated part anyway.
But it is this the kind of simplicity I want to see when
talking about monomorphic generic types. Perhaps someone can do
even better?
Yours Martin Leiser
Ian Lance Taylor
>
> I think so. But How? Remember we need to do two things:
>
> - A way to define type parameters.
>
> - A way to bind the type parameters to concrete types at compile time
I think that a generics proposal needs to do three things. The third
is that it needs to describe which operations are permitted for a type
parameter.
> But after we named it "ElementType" we can get a hold of it and bind it in the package we intend to use e.G. a "list of strings":
>
> import "container/list" type ElementType string
Here are a few examples:
https://gist.github.com/PeterRK/41d4d3f54b8db55cd616403fd5a389f3
https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/blob/master/use-package-as-gen.md
https://groups.google.com/g/golang-nuts/c/xKYXZpsWHus/m/SS4FKMBEAQAJ
There are others.
> Last features. If you need two different bindings in one package, say a list of string and a list of int you may use:
>
> import "container/list" intlist type ElementType = int
>
> import "container/list" stringlist type ElementType = string
What if I want to have a list of some unexported type that I defined
in this package? That seems to require interweaving type definitions
and imports in ways that the language does not currently support.
With this proposal, how can I write a min function that works for any
integer type, including a user-defined integer type? What happens if
I try to import a package that defines that Min function but I set the
argument type to some that does not support the < operator?
Thanks again.
Ian
Martin Leiser
Am 21. März 2021 22:01:38 MEZ schrieb Ian Lance Taylor <ia...@golang.org>:
>On Sun, Mar 21, 2021 at 1:02 PM Martin Leiser <leise...@gmail.com>
>wrote:
>>
>> I think so. But How? Remember we need to do two things:
>>
>> - A way to define type parameters.
>>
>> - A way to bind the type parameters to concrete types at compile
>time
>
>Thanks for the note.
>
>I think that a generics proposal needs to do three things. The third
>is that it needs to describe which operations are permitted for a type
>parameter.
Especially if you think about the kind of things you may do with type parameters and type inference in languages like Haskell or ML.
The only thing you aktually want to do with binding types of type parameters is: use them as parameters of your package.
No difference to the accepted proposal here.
The key difference here is the way to define and bind the parameters.
All else should be as equal as possible, because the accepted proposal is good.
>
>> But after we named it "ElementType" we can get a hold of it and bind
>it in the package we intend to use e.G. a "list of strings":
>>
>> import "container/list" type ElementType string
>
>This general kind of idea has been suggested quite a few times before.
>Here are a few examples:
>
>https://gist.github.com/PeterRK/41d4d3f54b8db55cd616403fd5a389f3
>https://github.com/dotaheor/unify-Go-builtin-and-custom-generics/blob/master/use-package-as-gen.md
>https://groups.google.com/g/golang-nuts/c/xKYXZpsWHus/m/SS4FKMBEAQAJ
>
>There are others.
>
>> Last features. If you need two different bindings in one package, say
>a list of string and a list of int you may use:
>>
>> import "container/list" intlist type ElementType = int
>>
>> import "container/list" stringlist type ElementType = string
>
>What if I want to have a list of lists of strings?
import "container/list" liststringlist type ElementType = stringlist.Element
>What if I want to have a list of some unexported type that I defined
>in this package?
- All the compiler really needs to know about the bound type is specified by the bound interface type, plus the storage size.
- You have to outrule cyclic definitions, but they are impossible, because it is the implementaion which introduces the cycle.
- You may even fall back to the normal implementation of "interface types" behind the scenes when appropriate.
Semantically all is solved by the following three program transformations chained together:
1. Make the private Type exported (does not change behaviour as long as you avoid name clashes by consistent renaming)
2. Add an import to the Package defining the binding type in a renamed copy of the generic package
3. replace the definition of the bind type by a type alias with the binding type in the copy of step 2
In my posting I only named the 3. transformation to keep things simple.
Steps 2 and 3 have to be done at most once for any binding type in the whole program.
All this may be implemented as "source to source" transformations,
as you may know from the compiler construction class talking about generics
(mine was >30 years age full of examples from LIS and Ada, I am a bit rusty here).
And it gets way more complicated when you actually start to do it in reality.
But it is this simple to describe here, because I choose to bind on the package level.
That is part of the trick. The price are global variables.
But can You always apply this transformation? Are there additional limitations required? I do not know yet.
I believe you must outrule a import cycle for the type binding import. Which should be of no practical impact.
> That seems to require interweaving type definitions
>and imports in ways that the language does not currently support.
For every type binding you have to have a way to "instantiate" a copy of the whole package with this binding.
And the "stringlist" must only have one instantiation for all packages using the same type binding imports.
Doing this efficient and effective, that is the complicated part.
Did I mention that there is no big difference in complexity in the implementation of my proposal and the accepted one?
Sorry for ommiting that.
I actually see an additional risk, when talking about global variables involving the parameter types.
(Which makes no sense for practical use, but has to be covered or outruled.)
>
>With this proposal, how can I write a min function that works for any
>integer type, including a user-defined integer type?
this works just fine for my proposal as well. I talked about "named interface types". Whatever is a legal interface type works just fine.
So it this part of the the proposal is added to the language it works just fine for me.
> What happens if
>I try to import a package that defines that Min function but I set the
>argument type to some that does not support the < operator?
and another using the
type Lesser interface {Less(Lesser) Lesser }
The implementation of min with Lesser:
func Min(a, b Lesser) Lesser { if a.Less(b) {return a;} else {return b;}}
The implementation of Min with "ComparableStdType" stolen from the accepted draft:
func Min(a, b ComparableStdType) ComparableStdType {if a < b {return a; } else {return b;}
The idea of the "interface with enumerated standard types" a really good example for simplicity in the accepted draft.
Not adding operator overloading to Go is a good thing.
The builtin stuff is tricky to deal with, but IMHO this could also be solved "the other way around":
Define a set of "Builtin Standard Type Definition Packages" containing all the methods
(it has to be methods, because of interface types which may be used as functions effortlessly):
Plus Minus Multiply Define Less Equal
etc. and define the operators to be more or less a short hands of this Methods.
This would solve the "builtin special case" as well, and eliminates the need to treat the builtin types as special cases, e.g. in the "sort.go" package.
The implementation of this builtin packages should of course still be "well known to the compiler" in oder to spill out efficient code.
But is this really simpler than enumerating the special types? I think so, but no strong arguments here.
Doing it this way eliminates the need for two definitions of the "Min" function for sure, because int simply has a method "Less" now as a synonym for the operator <.
And it would be a perfect starting point for describing the methods I should add to my type,
when trying to implement a "Comparable" type in my own code.
Looking at the Haskell or ML standard libraries is a good starting point for evaluating "generic" additions to the standard library IMHO.
There is e.g. the numerical type class there, I found it helpful for understanding Haskell to treat the Haskell "type class" the same as "interface type" in Go.
Except for the "sort.go" Package there isn't much functional stuff in the Go standard library to choose from when making a proposal.
(And I learned You should use examples from the standard library when making proposals, so I focused on containers.)
Hopefully this will change soon after "generics" are added!
>
>Thanks again.
>
>Ian
Thanks for your quick response.
Martin
Martin Leiser
Am 22.03.2021 um 10:10 schrieb Martin Leiser:
>
> Am 21. März 2021 22:01:38 MEZ schrieb Ian Lance Taylor <ia...@golang.org>:
>> On Sun, Mar 21, 2021 at 1:02 PM Martin Leiser <leise...@gmail.com>
>> wrote:
>>> import "container/list" stringlist type ElementType = string
>> What if I want to have a list of lists of strings?
> That is a no brainer. The type "list of strings" in the example is: "stringlist.Element". So you add the following line:
> import "container/list" liststringlist type ElementType = stringlist.Element
What if the binding type is a parameter type itself?
type MyElement interface{ String() string }
and this is bound to
import "container/list" myelementlist type ElementType = MyElement
I.e my container type build on the list type for its implementation.
This really adds complexity to the implementation, because every import
binding "MyElement" also binds the list package parameter type.
>> What if I want to have a list of some unexported type that I defined
>> in this package?
> That is the "Complicated" part of the proposal. It can be solved and it is not that tricky:
> - All the compiler really needs to know about the bound type is specified by the bound interface type, plus the storage size.
> - You have to outrule cyclic definitions, but they are impossible, because it is the implementaion which introduces the cycle.
> - You may even fall back to the normal implementation of "interface types" behind the scenes when appropriate.
>
> Semantically all is solved by the following three program transformations chained together:
> 1. Make the private Type exported (does not change behaviour as long as you avoid name clashes by consistent renaming)
> 2. Add an import to the Package defining the binding type in a renamed copy of the generic package
> 3. replace the definition of the bind type by a type alias with the binding type in the copy of step 2
across separate packages in case of parameter types used as binding types.
Every binding of "MyElement" type adds another binding to list.ElementType.
Complicated but solvable, but perhaps only if cyclic imports our
outruled for type binding imports in the first place.
>> Thanks again.
>>
>> Ian
>>
>> Thanks for your quick response.
>>
>> Martin
Ian Lance Taylor
>
> > What happens if
> >I try to import a package that defines that Min function but I set the
> >argument type to some that does not support the < operator?
> I would simply write two similar packages: one using the above mentioned enumerated interface of the accepted draft,
> and another using the
> type Lesser interface {Less(Lesser) Lesser }
> The implementation of min with Lesser:
> func Min(a, b Lesser) Lesser { if a.Less(b) {return a;} else {return b;}}
> The implementation of Min with "ComparableStdType" stolen from the accepted draft:
> func Min(a, b ComparableStdType) ComparableStdType {if a < b {return a; } else {return b;}
handle that case. I was asking how the compiler detects an erroneous
use of the Min function with a type that does not support the <
operator.
But I gather that you are suggesting that we use type lists as in the
current generics proposal, so that answers that question.
If we do that, it seems to me that your proposal is no simpler than
the current generics proposal. And I think that in practice it will
be somewhat harder to use, because it ties generic type scope closely
to package scope. I don't think it's the case that all generic types
are logically tied to a package. Forcing them to be associated with
packages will force people to break up their programs in unnatural
ways in order to use generic types.
Ian