Generics facilitators in Go

https://rakyll.org/generics-facilititators/

192 129 5 years ago

A nice pattern that will probably become common.

I assume the limitation on generic methods is just an implementation issue, the vtable for an interface has to have a known number of methods, and they can't insert specializations for each type on the fly into the vtable.

jerf6• 5 years ago

There is discussion of this in the proposal: https://go.googlesource.com/proposal/+/refs/heads/master/des...

I'd call it a fundamental semantics issue. That discussion is mostly framed in terms of the compile-time problems that arise, but that brief aside about the reflection package is deceptively short, because it means that the entire compile time set of problems is also lifted into runtime, where the problem is even worse. (To translate for someone who isn't a Go expert, the reflection package has enough power that it can dynamically instantiate new types that the compiler did not and can not even in principle have seen at compile time, which may then require new methods to be created. The current Go runtime has no run-time code creation capabilities. [1]) Without the reflection problem, it's annoying but at least solvable in principle, but I don't see any reasonable design (without a fundamental overhaul to specify a runtime-available compiler in the language spec itself, which is a huge step) that solves the reflection issue.

[1] Which personally I consider almost a feature. YMMV. Runtime compilation is very cool in a lot of ways but is a hell of a subsystem to try to secure, just by its very nature. There's a lot to be said for simply not having that capability unless it is integral to some particular program.

klodolph• 5 years ago

Yes, I agree. I think one of the key problems here is that any solution would create a distinction between polymorphic and monomorphic methods. This is why languages are so much more than a bag of features... every feature interacts with other features, often in subtle ways. For example, take a "simple" feature like operator overloading... if you look at how operator overloading actually works in C++ and C#, it's an incredibly complex feature in both languages, with some surprising behavior. That surprising behavior arises because features interact in weird ways that you wouldn't ordinarily think about.

Saying "no generic methods" is a nice out.

_old_dude_• 5 years ago

it means that the entire compile time set of problems is also lifted into runtime

It's what Swift does if inlining is defeated, the type arguments are passed at runtime as a classical argument on stack.

You don't need full reflection as you suggest, only to be able to materialize the types as structs + an interface at runtime. Yes, it's a little slower but most of the overhead comes from the function not be inlined.

parhamn• 5 years ago

I recently saw a go generic data structures library in the wild: https://github.com/zyedidia/generic.

Anyone have any more? I'm curious what people come up with for goroutines/channels.

nkcmr• 5 years ago

I made this: https://github.com/nkcmr/async so I can experiment with the idea of Promises in Go. Keep in mind it's experimental and I've only lightly played around with the pattern.

Zababa3• 5 years ago

That's interesting, I always found Go's handling of asynchronous stuff way better than other languages, especially the ones that relies on async.

jerf6• 5 years ago

Go doesn't have much use for promises, and generics won't change that, because channel covers the problem space that promises cover.

It is obvious that a channel is not the same thing as a promise. They are quite different in many ways. But the problems that you solve with promises in some languages are solved with channels in Go. There's pros and cons to each, but the cons of channels aren't all that significant in the specific context of Go and there are some compelling pros to the channels in the specific context of Go, so there isn't a very fertile space left over for a promise library. I've already seen half-a-dozen go by (non-generic, but missing generics aren't the problem) and those are just the ones that get posted to reddit.

I advise writing Go in Go, and not Javascript in Go. But it's your codebase.

(Promises are basically an inner platform [1] for functionality not provided by the base language. Go provides the requisite functionality in the base language. I think I'm more hostile to inner platforms every year, but at least when you're adding capabilities to the base language you can't get any other way there's a debate to be had. Adding an inner platform to get functionality that already exists is just a bad plan.)

[1] https://en.wikipedia.org/wiki/Inner-platform_effect

kubb7• 5 years ago

This is actually a pretty neat collection of data structures! Goes to show what people can do given the opportunity.

mappu• 5 years ago

You'll notice the functional iterators under iter/ don't include benchmarks.

Go will not inline a function that exceeds complexity metrics, and one of those metrics is whether the function contains a range statement. You will get a real heap-allocated closure invocation on each loop.

Go's function calls are not that cheap, and these will be measurably slower than the for-loop equivalent. I see functional idioms as being a huge risk factor for Go.

felixge• 5 years ago

Go will not inline a function that exceeds complexity metrics

True, but:

and one of those metrics is whether the function contains a range statement. You will get a real heap-allocated closure invocation on each loop.

I think this is no longer true in Go 1.18, see https://github.com/golang/go/issues/14768#issuecomment-98175... .

zyedidia• 5 years ago

Author here. I think there is definitely room for improvement in the iterator API. I intend to experiment with more implementations in the coming weeks with the goal of settling on something better by the time Go 1.18 is released. The main alternative I have in mind is a cursor-style iterator (for example, with `Next`, `Done`, and `Value` methods). If you have something else in mind too, let me know and I might be able to try it out.

lazyjones• 5 years ago

It should not be hard to automatically convert code using such generics libraries to use specialized type-specific code instead for better performance.

ghughes• 5 years ago

This has been useful: https://github.com/rakeeb-hossain/functools

It contains generic implementations of

    Any
    All
    Count
    Filter
    ForEach
    Map
    Reduce
    ReduceRight
    Sum
    Chunk

kodablah• 5 years ago

Undocumented early impl/design of futures: https://github.com/cretz/fut. Examples: https://github.com/cretz/fut/blob/main/ops_test.go.

feffe• 5 years ago

I've just finished porting my gods module (Go Data Structures) to make use of generics.

https://github.com/johan-bolmsjo/gods/tree/v2

It's not much, only a simple list and an AVL tree that I've carried with me for many years. Binary search trees are useful to solve some problems because they are ordered.

I was impressed with how polished the tools where. The go-lsp plugin just worked with the new generic types. I solved all compiler errors in the editor without actually compiling anything. Did not expect that level of polish. The modules introduction broke the editor integration for many release cycles. This seems much smoother.

arwineap• 5 years ago

Not terribly excited for generics.

sigmonsays• 5 years ago

I have this concern too. I wish to remain optimistic though.

i've enjoyed go for its simplicity. At times it requires more code (or code generation) but that generated code was easier to debug and have tooling operate on.

With generics, Some things will suffer. Complexity of code and tooling increases, tooling is probably going to suffer and become more costly. compile time and performance will probably also be affected.

Generics are likely only great for collections of things, ie []*T, where, you need to do the same thing on many of T.

svnpenn2• 5 years ago

I really dont like this. It just feels like people are trying to ram a square peg into a round hole. Personally I dont get why generics were needed in the first place. Every single example Ive seen so far, could be pretty easily replaced with `interface{}`. And now that we finally have generics, people still arent happy. Now that they have their round peg, they are trying to now ram it into a star shaped hole, as is being done in this post.

I really wish people would just use the language as it is. Yes, it does cause for some repetition, but thats not the worst thing in the world. Compared to some Java codebases I have seen, Go is extremely simple already, in terms of "flatness" in the filesystem, and flatness in the type system. I think people should just know when to leave well enough alone. I dont think the complexity of generics is worth it for 99/100 use cases.

fsdjkflsjfsoij2• 5 years ago

Every single example Ive seen so far, could be pretty easily replaced with `interface{}`

Of course they could just use interface{}... But by doing that they lose both type safety and performance.

svnpenn2• 5 years ago

they lose both type safety and performance

I guess you think generics is a magic pixie dust that has the exact performance envelope as non-generic code?

jjtheblunt2• 5 years ago

Aren't the language builtins (map[X]Y etc) themselves generic ?

Groxx2• 5 years ago

And they're almost universally strongly preferred over custom collections, yeah. I very much doubt that's coincidence.

mattarm• 5 years ago

"All problems in computer science can be solved by another level of indirection" - Butler Lampson

See https://en.wikipedia.org/wiki/Indirection

infogulch• 5 years ago

"Except for the problem of too many levels of indirection" - ?

adgjlsfhk1• 5 years ago

No, you solve that problem by adding another layer of indirection (aka a caching layer)

kubb7• 5 years ago

Go type system is not a traditional type system and it was not possible just to bring an existing generics implementation from other language and be done.

I claim that there are no original ideas in Go's type system and in the way that Go does generics, and the reason it took so long was because it came out of an environment with actors (including a part of the community) pushing against the feature.

You might disagree, I'm curious what original features of Go you will point out to me.

verdverm• 5 years ago

While not necessarily part of the language, but arguably part of Go, something novel is the dep mgmt system. I have not encountered the MVS algorithm in another language. CUE is intending to adopt it.

pxc• 5 years ago

Where can non-Go (for now!) developers read about this to get a sense of what makes it interesting?

randomdata5• 5 years ago

Go's generics have been in development (by the same person) since the pre-1.0 days, with various proposals submitted for their inclusion. Are you suggesting that those earlier proposals failed for frivolous reasons rather than real technical concerns?

It seems to me that that it was less about active pushback and more that people who cared about having generics in Go was limited to an exceedingly small group of people who weren't necessarily experts in the subject matter. In fact, the Go team hired an external expert to lay the groundwork for what became the winning proposal.

anonymoushn7• 5 years ago

A great innovation of Go is that it includes a built-in reference type with both inner nils and outer nils.

Skunkleton2• 5 years ago

As a non-serious user of Go, this was something I found to be a negative. What am I missing?

kubb7• 5 years ago

It is a bit like

  void *outer = 0; // outer can be nil
  int val = 5;
  int *inner = &val; // inner can also be nil
  outer = (void*)(&inner) // can have an inner value, inner nil or outer nil

azth• 5 years ago

A negative innovation, sure :P

throwaway89434517• 5 years ago

Go has no such feature. Go's interfaces are a reference type which point to the runtime implementation. If that implementation is itself a pointer type, then that pointer may also be nil. Any language that has nullable reference types (including languages in which everything is a pointer like Java or Python) will have this problem.

EDIT: would really like to know why I'm being downvoted. If you disagree with my comment, then best of luck to you in rebutting it. :)

Ericson23142• 5 years ago

Well played :)

jerf6• 5 years ago

They are not the same nil: http://www.jerf.org/iri/post/2957

throwaway89434517• 5 years ago

This seems like a straw man. I don't think anyone has claimed Go's type system has novel features.

the reason it took so long was because it came out of an environment with actors (including a part of the community) pushing against the feature.

The reason it took so long is because it simply wasn't the biggest fish to fry. Generics are a massive feature, and there were a lot of other opportunities to deliver more value for considerably less work. Of course, there was a healthy amount of pushback against rushing generics, considering generics must interact with every other feature in the type system even if those features aren't novel.

Frankly, people make too big a deal about generics. It will be a neat quality of life improvement for certain kinds of code, and a lot of additional code will enter the ecosystem which is gratuitously abstract. Builds will probably get a fair bit slower on average while still being fast relative to most other languages. Frankly, no type system feature will ever impact a language as significantly as things like tooling quality, ecosystem, runtime performance, static+native compilation, iteration loop time, learning curve, etc.

masklinn7• 5 years ago

I don't think anyone has claimed Go's type system has novel features.

The third phrase of the linked essay is:

Go type system is not a traditional type system

"non-traditional" is generally read as "novel" in some way.

kubb7• 5 years ago

I'm quoting the author directly. I didn't tamper with the quote.

phillipcarter5• 5 years ago

Frankly, people make too big a deal about generics.

Different strokes for different folks, but I think generics are a huge deal. They make libraries so much more ergonomic and reduce toil generally. It's a case of dealing with many, many small papercuts over a long period of time rather than a big-bang sort of thing.

tooling quality

I'm a huge proponent of tools, so much so that I worked on programming language tools for 5 years. My perspective is that tools are there to optimize an existing experience, but reach a local maxima in the overall experience because they're limited by language semantics. When you improve language semantics, tools get to improve experience again. That's why it's so important to do language design in a way that strongly considers the tooling experience, and a big reason why you see so much love for languages like TypeScript and C#. They work hand in hand. And generics are an example of how semantics can push tools to be better.

jerf6• 5 years ago

"Frankly, people make too big a deal about generics."

I think there's a lot of confusion brought in from languages where generics are a bigger deal than they are in Go, because when generics came in to those languages it was like turning on a light.

However, if you map out the problem space of "what did generics solve in those languages", rather than obsessing about the solution, what you find is that Go's interfaces, combined with the structural typing ("static duck typing" basically, rather than having to explicitly declare conformance at declaration time) covered quite a bit of the problem space. And that's what matters, whether the problem space is covered, not whether the problem space was covered in exactly the same way as some other language.

People who either have never programmed in Go, or only spent long enough with it to try to program "(Not Go) in Go" (e.g., "Javascript in Go"), and didn't learn how to use the tools Go has to cover the problem space, end up vastly overestimating their utility in Go, and vastly overestimating the sort of problems you can't use Go to solve. They're like "How can you program in a language that doesn't cover the 'generics' problem space?", and the answer is, "You're actually right, I couldn't! But I can use Go, because it actually does cover quite a bit of the problem space, just in a different way than what you're demanding." Interfaces DO NOT cover all the space, I would never dream of claiming otherwise, but they cover a lot of the space. There's even some problems where I've found Go simply outright the best solution because of some particular thing I can use interfaces to solve.

I'll actually kind of miss the "How can I do this without generics in Go?" questions on /r/golang. They're fun, and with the exception of "data structures", generally I didn't just come up with "a" solution, but with a good solution.

eweise2• 5 years ago

I'm currently working on a process that has to manipulate collection of data and its really aggravating to invent custom functions to do basic manipulations such as groupby, maps, filter, etc. It basically feels like java back in the early 2000s.

phillipcarter5• 5 years ago

You might disagree, I'm curious what original features of Go you will point out to me.

I think only insiders on the Go team during that time period can really say for sure what the deal is.

But I will say that retrofitting generics onto a language and standard library is a project of enormous scope and incredible difficulty. So I'm pretty sympathetic to the idea that it took them a while.

krzat• 5 years ago

Thoughts and prayers to the Go team. I suspect they got kinda forced into implementing this, otherwise generics would be available from the start.

eweise2• 5 years ago

Guess there's a downside to making a too simple language and then trying to bring it up to modern day standards over time.

jjtheblunt2• 5 years ago

to your point, isn't Go just the Google-funded continuation of Bell Labs' Limbo, with essentially the same people?

If so, it's curious how sparsely mentioned the origin at Bell Labs pre Google is.

https://en.wikipedia.org/wiki/Limbo_(programming_language)

1_player• 5 years ago

What is the point of going into Go generics posts on HN and making a point to mention that core Go developers were against the feature, which is incorrect, but also shows there's some axe to grind against that team. Is that to show they're less smart then they think they are?

I swear there's at least one top-level comment such as yours in every thread, for no reason other than just to discredit people's work. I find it disgraceful.

skybrian• 5 years ago

Unusual doesn't mean unique or better, just different enough to make doing a straight port harder.

For example, Go's interface types and its lack of constructors seem different from most languages you might borrow from.

jayd162• 5 years ago

Reminds me of Java's use of listener objects because it lacked (at the time) lambdas and method references for callbacks.

Hopefully Go generics continue to improve.

kubb7• 5 years ago

I wonder if the limitation of not allowing type parameters for methods came from wanting to prevent people from using it for certain features that would be considered "too complicated for Go", or from it being "too complicated to support" or from "we won't be needing it anyways".

Another option to circumvent this is to use top-level functions, and accept the receiver as the first argument of the function. This is effectively the same thing, the only thing it's missing is the object.method() syntax that's familiar to OO programmers.

randomdata5• 5 years ago

No need to wonder. The proposal goes into lengthy detail as to why they are not included.

There is hope that they will be added in the future, but solutions to the problems will need to be found first.

mcculley• 5 years ago

I don’t think I understand what you mean. What would have been different about listener interfaces if lambdas and method references had been available?

jayd162• 5 years ago

Some examples here show the difference: https://stackoverflow.com/questions/4685563/how-to-pass-a-fu...

    addCallback(new Callable<Integer>() {
        public Integer call() {
            return callback();
        }
    });

    addCallback(this::callback);

At least anonymous types meant you didn't have to manually name all your listener boilerplate.

legulere• 5 years ago

Go type system is not a traditional type system

How so, I don't see anything special about Go's type system in the linked article.

noah_buddy• 5 years ago

I believe they're talking about the semi-duck typing used in go for interfaces but I'm not certain. Interfaces are implicitly implemented with a runtime check determining whether a type x assigned to interface y is valid.This is why you'll often see an empty declaration in packages for structs intended to implement an interface like so:

var _ y = x{} // syntax might be slightly wrong

After writing this, I found the linked article in the OP link to what the author meant.

https://rakyll.org/typesystem/

There's really a bunch of small things that are different about golang that individually you can find elsewhere but are on the whole unique.

politician• 5 years ago

var _ = ThingerInterface(&Struct{})

Creates a compile time error if Struct is not a ThingerInterface.

Groxx2• 5 years ago

You can also cast between these "facilitators", since the unused type doesn't affect memory layout: https://gotipplay.golang.org/p/2w2y1KEjXVE (from https://news.ycombinator.com/item?id=29586456 )

I think they'll be pretty common. It's a simple structure, and simple to manipulate.

kune• 5 years ago

Go 1.18 supports generic functions. Wouldn't a generic function much simpler than an additional type for that use case?

flippinburgers3• 5 years ago

Why not just use an interface for this?

cpuguy832• 5 years ago

Do you have an example of how to make this work with an interface?

flippinburgers3• 5 years ago

The author conveniently leaves out the implementation of the actual method calls themselves, which is frankly the important part.

  interface Query {
     All ...
     Insert ...
     Update ...
     Delete ...
     WhateverElse ...
  }

Now admittedly, the implementation is probably cleaner with "generics", but you can generically approach the problem with interfaces.

asoliveira• 5 years ago

C++ supports generics "template" since 1989. It is a shame for Golang hasn't been designed with this feature since from the beginning.

Generics facilitators in Go

Related Stories