[generics] Was "no type contracts" considered?

[Markus Heukelom]

Concerning the current generics proposal, was it every considered to not allow type contracts at all?

No type contracts would mean that generic functions can only use =, & on variables of parametric types, as these are always available for all types. Nothings else is allowed.  

This would remove the possibility to write generic mathematical functions, for example. But it is simple and it already enables a lot of usefulness. Was this considered too restrictive?

Type contracts could optionally be added in a later stage, but at least at that point we will have a larger body of generic code to work and test with. 

A bonus, disallowing all operations except assignment and address-taking would maybe also stop abuse of templates in the name of "but it is more efficient than interfaces" and "fancy coding syndromes".

-Markus

[Jesper Louis Andersen]

On Sat, Jul 18, 2020 at 1:55 PM Markus Heukelom <markus....@gain.pro> wrote:

Concerning the current generics proposal, was it every considered to not allow type contracts at all?

No type contracts would mean that generic functions can only use =, & on variables of parametric types, as these are always available for all types. Nothings else is allowed.  

I've written a lot of code in this style in Standard ML. In fact, SML distinguishes between types and eqtypes, where the latter allows for equality comparisons. Many types do not have an equality check defined on them, most notably floating point values and functions among the ground types.

The place where you hit the limitation is usually when you have an ordered tree and you need a function `cmp` of type `'k -> 'k -> order` which can order the keys in the tree. When you construct the tree, you have to provide such an ordering function and embed the order in the data structure of the tree. It is usually nicer to have that order implicitly bound to the type, especially for trees where you don't require a specific order, only some order that is total (or perhaps well-ordered).

Standard ML gets around this limitation by the means of "Functors" which are functions from modules to modules. In Go-parlance that would be generics on the package level, which I believe has been explored. My guess is that to make this efficient in writing, you also need to have nested packages, something which Standard ML has, but Go doesn't. Functors are also a nominal construction, whereas Go tends to use structural constructions where possible.

The current Go solution is closer to Haskell, where you can write the signature for the insertion into a tree as

insert :: Ord k => k -> a -> Map k a -> Map k a

that is, given a key, k, a value of type a, and a map for those types, produce a map where the K/V pair has been inserted. The `Ord k => ...` part constrain the type `k` to be ordered.

[Ian Lance Taylor]

I think that for a language like Go any generics implementation must
permit people to write the functions Min and Max. The functions are
trivial, but they are among the first that programmers accustomed to
generics complain about in Go.

Ian

[Markus Heukelom]

I complained myself too about not being able to write a generic Min, Max, but  I am not so sure anymore myself of the strength of this argument.

The point is: besides Min and Max, what other really good, general, examples are there of really missing?

To give an example myself,  I'd love to write

func (type T) SliceContains(list []T) bool 

Turns out, it was 99% always strings in my case! Maybe 100%. So I really didn't need it. I *thought* I needed it, but I just wanted to be fancy and write it for all types. Besides like you also said most of these functions are really really trivial to write quickly. I have MaxInt in several packages.

What we do undoubtedly need generics for is better type safety in generic data structures and (channel algorithms maybe). Generic (math) algorithms are very powerful too, I personally would love to have them, but could "delayed" or even decided to be never allowed to protect from "fancy template coding". It would certainly protect me from the latter.

So I am not saying Max(T) should be never supported, but generics would already be very useful without and it simplifies the design process a lot (if care is taken that it could reasonably added later).

It's just something that could be considered. 

-Markus

[Markus Heukelom]

For what it is worth: for non-exported functions/types all operations could be allowed, possibly leading to infamous C++-level error messages but as you are the author of the package, those error messages would make sense to you anyway.

For example, I could really use to be able to write things like this:

func sibling[type t](node *t) *t {

    if node.parent == nil {

        return nil

}

    if node.parent.left == node {

        return node.parent.right

  }

  return node.parent.left

}

This is not really possible with the current design. Of course I could specify an interface with getters/setters, but that feels a bit silly and cumbersome as everything is local to the package anyway. 

I don't have better a solution, but all contracts/constraints do is prevent long, unreadable error messages while inside a package there's no real problem with those error messages to begin with.  

 

Ian

[Ian Lance Taylor]

Go is a strictly typed languages, and constraints are the meta-types
of type parameters. You are suggesting that we should have an escape
hatch for that meta-type system when using unexported types. I
suppose that is possible. It seems like something we could add later
if it brings a big benefit.

I'm not sure when your example would really arise. It looks like you
have a tree type; why not make that a parameterized type and make
sibling a method on the type?

Ian

[Markus Heukelom]

On Mon, Aug 10, 2020 at 8:30 PM Ian Lance Taylor <ia...@golang.org> wrote:

On Mon, Aug 10, 2020 at 6:07 AM Markus Heukelom
<markus....@gain.pro> wrote:
>
> For what it is worth: for non-exported functions/types all operations could be allowed, possibly leading to infamous C++-level error messages but as you are the author of the package, those error messages would make sense to you anyway.
>
> For example, I could really use to be able to write things like this:
>
> func sibling[type t](node *t) *t {
>     if node.parent == nil {
>         return nil
> }
>     if node.parent.left == node {
>         return node.parent.right
>   }
>   return node.parent.left
> }
>
> This is not really possible with the current design. Of course I could specify an interface with getters/setters, but that feels a bit silly and cumbersome as everything is local to the package anyway.
>
> I don't have better a solution, but all contracts/constraints do is prevent long, unreadable error messages while inside a package there's no real problem with those error messages to begin with.

Go is a strictly typed languages, and constraints are the meta-types
of type parameters.  

I just realised there might be a distinction between strictly typed and strongly typed languages. Would it be correct to say C++ is strongly typed, but not strictly typed wrt templates (up C++20 at least)? Did you mean it in that sense?

You are suggesting that we should have an escape
hatch for that meta-type system when using unexported types.  I
suppose that is possible.  It seems like something we could add later
if it brings a big benefit.

I'm not sure when your example would really arise.  It looks like you
have a tree type; why not make that a parameterized type and make
sibling a method on the type?

Mainly for intrusive containers, see for example https://www.boost.org/doc/libs/1_73_0/doc/html/intrusive.html 

In my case I have two multi-index containers that are only used internally. They use the same rebalancing algorithm and some other stuff for adding/removing nodes, but I couldn't factor that out with the current generics design. Well tbh I could define an interface maybe with getters /setters for the fields but it feels a bit silly for internally used only stuff. I do agree that it's very niche probably and it does not warrant the addition of fields to interface constraints.

 

Ian

[Ian Lance Taylor]

On Wed, Aug 12, 2020 at 9:58 AM Markus Heukelom
<markus....@gain.pro> wrote:
>
>
>
> On Mon, Aug 10, 2020 at 8:30 PM Ian Lance Taylor <ia...@golang.org> wrote:
>>
>> Go is a strictly typed languages, and constraints are the meta-types
>> of type parameters.
>
>
> I just realised there might be a distinction between strictly typed and strongly typed languages. Would it be correct to say C++ is strongly typed, but not strictly typed wrt templates (up C++20 at least)? Did you mean it in that sense?

I'm not sure about the exact terminology here. I would agree that C++
is only weakly typed at the template meta level. As I understand it
(and I may not), C++20 introduces optional strict typing at the
template meta level.

In the current generics design draft we are requiring strict
meta-types at the generic level.

Ian