1. 53
  1.  

  2. 7

    The examples I’d like to see worked out fully, which he mentions in passing, are encapsulation of concurrency patterns (parallelization, work queues, cancelling, etc.). It’s not that big a deal to write Max as a function or even inline, whereas there are serious practical pitfalls and common mistakes when doing real work with channels. It would be a lot more effective to fix these by writing library code rather than writing Gophercon presentations.

    1. 2

      It has nothing to do with generics, but Katherine Cox-Buday’s book “Concurrency in Go” has a lot of great examples of real-world practical concurrency patterns, including everything you mention and more. They’re current and applicable. The book is a little spendy at nearly $40 but I have found it completely worth the cost.

      1. 7

        Oh, I know, but that’s exactly what I’m talking about — if I need a reliable non-leaky cancellable thread-pooled work queue, I should just be able to use the standard (or at least a) library, not have to read a book and copy-paste code.

        type WorkItem struct { ... }
        
        queue := properconcurrency.NewWorkQueue(MyWorkItem)()
        queue.Add(&myWorkItem)
        

        As an example, this blog post should just be part of the standard library, not a blog post: https://blog.golang.org/pipelines

        (Edit) This one too: https://blog.golang.org/advanced-go-concurrency-patterns

    2. 5

      Is the syntax (as seen in the signature of generic functions) unique to Go? I can’t say I’ve seen it anywhere else. As with the method syntax, it seems strange and difficult to read, but maybe that’s just because I haven’t used Go enough. To an experienced Gopher, does this look logical and in keeping with the syntactic design of the rest of the language?

      1. 6

        I think it looks like D templates.

        1. 2

          it seems strange and difficult to read, but maybe that’s just because I haven’t used Go enough

          As someone who has written a bit of Go over the years, I also find it strange and not exactly straightforward to read. It is new though, so maybe I’ll get used to it?
          To me, it seems/feels/looks like some strange form of partial application. Perhaps that is what is happening under the hood with the compiler, and this is just a bit of a leaky abstraction? I’ll probably think of partial application in the back of my head every time I see this anyway, and wish Go had it as a core feature.

          1. 9

            To me, it seems/feels/looks like some strange form of partial application.

            It is! You can think of the Reverse function as desugaring to something like this:

            const Reverse tfunc (Element type) func(s Element[]) = 
                tfunc (Element) {
                    return func(s Element[]) {
                        ...
                    }
                }
            

            Where tfunc is either:

            • a type that is parameterised by another type
            • a term that takes a type as an argument and returns a term specialized to that type argument

            …depending on whether we are in the type syntax or the value syntax.

            You can call Reverse like so:

            elements := {1, 2, 3}
            Reverse(elements)
            

            For sanity’s say, the type checker will infer the type that needs to be supplied to Reverse, but we can invent a syntax for ‘explicit type application’ like so (inspired by D’s template application syntax):

            elements := {1, 2, 3}
            Reverse!(Int)(elements)
            
            // this shows how we might be able to partially apply the
            // type function to get specialised function:
            const IntReverse func(Int[]) = Reverse!(Int)
            

            Perhaps that is what is happening under the hood with the compiler, and this is just a bit of a leaky abstraction?

            I don’t think this is ‘leaky’ - it very clearly maps to something called called System F, with the added semantics that type arguments can be inferred. We can elaborate our invented Go syntax quite straightforwardly into System F:

            • For types:
              tfunc(A type) B   ⟹   ∀ A : Type. B
              func (A) B        ⟹   A → B
              
            • For values:
              tfunc(a A) { b }  ⟹   Λ a : A. b
              func (a A) { b }  ⟹   λ a : A. b
              f!(A)             ⟹   fᴬ
              f(a)              ⟹   f a
              

            Please note that I am not suggesting that Go actually does this, I’m just making it clear that the intuition behind it being partial application is not a bad one!

            1. 1

              Super interesting. Thanks for commenting!

              1. 4

                No worries! There’s lots of really great theory that’s been developed around this stuff, which is why I really encourage language designers to learn it. It can make designing new features like this much easier, especially when it comes to figuring out the semantics that makes sense.

                Sadly it can be a little intimidating to break into - it took me a long time to learn that ‘forall’ was not a type level lambda - it was more akin to a more general function type, where the type of the body depends on the applied argument. I think this was because the only time I’d ever seen things that bound other things was in lambdas. If this stuff interests you, I’d highly recommend finding a copy of Types and Programming Languages by Benjamin Pierce.

          2. 1

            I imagine this will be the first of many attempts at the syntax for generics but it seemed pretty tough to grok by just reading it. I have been writing Go for four years and I couldn’t grasp it at first glance. There isn’t enough logical separation to see a generic type declaration in a complex example like this:

            type Graph (type Node, Edge G) struct { ... }
            

            It took me a while to read that as a new struct definition with two generic types Node and Edge. For all I know, I am still wrong. Why not use <T> or [T] to denote a generic type like many other languages have? The type keyword is overloaded here.

            I also did not care for the contract use case here:

            contract Sequence(T) {
                T string, []byte
            }
            

            This seems like it will be reinvented many times over. I imagine many users will create a contract that defines a type that can be iterated over like this example given in the post. Maybe that’s too judgmental for a first cut though.

            I am confident that things will shape up with time and the Go team will settle on something productive.

            1. 8

              In their Draft Design they mentioned:

              Why not use F<T> like C++ and Java?

              When parsing code within a function, such as v := F<T>, at the point of seeing the < it’s ambiguous whether we are seeing a type instantiation or an expression using the < operator. Resolving that requires effectively unbounded lookahead. In general we strive to keep the Go parser simple.

              This reason personally doesn’t convince me

              1. 7

                It does make sense. This is a serious problem in C++ to the point that you sometimes have to type template X<..> instead of X<...> just to give a hint to the parser.

                1. 4

                  It does indeed get surprisingly problematic, it’s why you have the adorable turbofish syntax in Rust for disambiguating generic types in function calls. Being able to have a function call that goes foo<bar, baz>(bop) is just too ambiguous to live with.

                  Fortunately, nobody seems to have considered solving this by using non-standard symbols for the greater-than and less-than operators.

                  1. 2
                2. 5

                  C# bit that bullet (and it worked rather well), but that language is closer to C++ in complexity than anything else already.

                  Sane languages use [T], but that isn’t an option in Go either, for the same parsing reasons (clashes with arrays).

                  1. 5

                    Or we could just use s-expressions and call it a day.

                    1. 11

                      It seems unlikely go will switch to s expressions for go 2.

                    2. 2

                      D adds an exclamation mark for templates:

                      Foo(bar) // function call
                      Foo!(bar) // template instantiation
                      
                      1. 2

                        Pretty ugly – but I think that’s a property shared by all languages which bolted these things on without wanting to question their existing design.

                        Design by “what-already-used-symbol-can-be-made-to-carry-even-more-syntax”.

              2. 3

                (Apologies if the below isn’t well thought through - I’m at the edge of my understanding here)

                The “contract for multiple types” thing puzzled me, because I didn’t understand the example.

                I thought it would be better to have per-type constraints. But the graph example shows that a contract can express cross-type dependencies. That’s cool.

                The declaration of contracts and interfaces otherwise seem close enough (semantically and conceptually) that I’d really like to understand the semantic differences between the two. I (think I) understand that an interface is implemented as a boxed type and the generics constrained by constract would be implemented as an unboxed type - but to me that should be an implementation detail.

                To me it seems similar to whether a value is allocated on the heap or stack. In go, the heap/stack distinction has a performance difference but not a semantic difference. In C, it also has a semantic difference and that is the source of much pain.

                So I think I’m asking: if we’re happy breaking back-compat, would it be possible to unify the contract+interface concepts and have the compiler choose whether we are boxing or not? (e.g. default to boxing and not-box in the cases where enough information is given to permit the optimisation).

                1. 1

                  if we’re happy breaking back-compat, would it be possible to unify the contract+interface concepts and have the compiler choose whether we are boxing or not?

                  Maybe, in the draft it is clear that Go team wants to have flexibility in how contracts are implemented:

                  We believe that this design permits different implementation choices. Code may be compiled separately for each set of type arguments, or it may be compiled as though each type argument is handled similarly to an interface type with method calls, or there may be some combination of the two.

                  1. 1

                    Thanks, that’s interesting.

                    I think my main interest would be to see if having a single language construct (extended interfaces?) would suffice, rather than adding ‘contract’.

                2. 1

                  The section of the spec on type erasure doesn’t say much, and I’m left wondering how this case would be handled.

                  contract Fruit { HasSeeds() bool }

                  func foo (type Fruit) (a []Fruit) {

                  a[0] = new(Apple)

                  Sometimes a will be array of Apple, but sometimes Banana. Does it compile? Does it run?

                  1. 2

                    Hmm, I think your code is slightly misphrased, which probably makes answering this a bit harder. I think the correct syntax would be:

                    contract Fruit { HasSeeds() bool }
                    func foo(type T Fruit)(a []T) {
                        a[0] = new(Apple)
                    }
                    

                    I’d expect this to not compile, since there’s nothing that proves that T == *Apple.

                    1. 1

                      That’s what I meant (with pointer indirection “equivalency”) and about the answer I’d expect. Kinda surprised they didn’t just mention it though, since I think it’s one of the common questions. Or at least everything I’ve read about genetics in java and c# seems to cover erasure or contravariance, etc. in a bit more detail. It’s always “what if” faq number 1. Saying “contravariance not supported” is kinda vague. At least to me.

                      1. 4

                        I don’t think this is a variance question. Variance should generally only come up when talking about subtyping, and I don’t think subtyping plays a role in the generics proposal. IIRC, the actual design doc does explicitly say that everything is invariant (in keeping with current Go semantics with respect to interfaces).

                        EDIT: More specifically, when one writes (type T Fruit), then the common English translation of that is, “for all types T that satisfy the contract Fruit, do this…” Writing an implementation that is only valid for a particular T would thus be invalid (or in type theory parlance, it would violate parametricity). With that said, IIRC, the generics design specifically permits using type asserts and type switches, so I guess you could use that to violate parametricity and write code that sets the first element to a *Apple, but the compiler would only permit that when T == *Apple (via a type assert/switch).

                        1. 3

                          More specifically, when one writes (type T Fruit), then the common English translation of that is, “for all types T that satisfy the contract Fruit, do this…”

                          I don’t understand how I have read docs on this proposal and only now understand what (type T Fruit) is saying. Thanks!

                        2. 1

                          … are you familiar with Go’s interfaces and how Go, for lack of a more precise phrasing, doesn’t have subtyping in the same way as C++/Java/C#?

                          The function requires that T meet the Fruit contract, so T can be any type that has the appropriate method. That does not mean that you can assign to a T with any type that does have the appropriate method.

                          This sort of thing is what interfaces in Go are for.

                          type Fruit interface { HasSeeds() bool }
                          type Apple struct{}
                          func (a Apple) HasSeeds() bool { return true }
                          func foo(a []Fruit) {
                              a[0] = new(Apple)
                          }
                          

                          If we had the generic function written above:

                          contract Fruity { HasSeeds() bool }
                          func fooy(type T Fruit)(a []T) {
                              //do something valid here
                          }
                          

                          you would be able to give it any type argument that fulfills the Fruit interface or give it the Fruit interface itself– if you give it specific types, you effectively get a monomorphized version of the generic function that runs on just that one type.

                    2. 1

                      [deleted: wrong chan]

                      1. 1

                        I’m not worried about the syntax. I do worry that compile speeds will go up dramatically. If we litter the code with genericized containers and algorithms, won’t it necessitate compiling a new class/function for each type? They could go the C# route, which is to generate one copy for each used primitive type and one catch-all for Objects. (This means calling functions on those objects will have to be virtual.) And with multiple copies of code, the executable also suffers from code bloat.

                        1. 1

                          This means calling functions on those objects will have to be virtual.

                          Not necessarily.

                          1. 1

                            Can you explain why not? I’m genuinely curious!

                            1. 1

                              You can emit “casts” to the specific type after you pull it out of the catch-all-generic code.

                              (Assuming you used the class’ type and not some interface to instantiate the generic piece.)

                              [Or maybe I misunderstood you?]

                              1. 1

                                If you have a catch-all class that is parameterized over all objects, you can only store pointers in the class. Calling the same method on any type via pointer requires virtual calls.

                                If you emit casting code per type, you now have to generate an implementation per type, which defeats the point of having one catch-all class.

                                1. 1

                                  Calling the same method on any type via pointer requires virtual calls.

                                  This has nothing to do with with catch-all vs. specializing code, but is solely a result of passing around pointers.

                                  If you emit casting code per type, you now have to generate an implementation per type

                                  You emit the casting code at the point of usage, not inside the the catch-all code, similar to Java.

                                  1. 1

                                    Oh I think I see what you’re saying. If the object’s exact type is known at compile time, you can just emit casts at use-time. Then, that object’s relevant functions will be used. Those functions know the data layout of the object and can interact with it correctly. You can do this for objects passed by value and by reference/pointer.

                                    The cost is that the generated code for the template class/function can’t know about the parameterized type’s layout or traits. (This is because only one copy of the template is generated; it can’t specialize it’s memory layout or change logic based on type traits. It has to work across all object types, because the casting can later happen anywhere.) This necessitates the objects living on the heap, because the template class’s layout can’t change based on the type. (An object’s layout is a sort of type trait.)

                                    Is my line of reasoning correct? Thank you!!