Calculating Go type sets is harder than you think(blog.merovius.de)
blog.merovius.de
Calculating Go type sets is harder than you think
https://blog.merovius.de/posts/2022-05-16-calculating-type-sets/
4 comments
> In go, if you want a macro, you write a separate go program that generates code, write a "//go:generate" comment, and then have no way of knowing when to run it
You run it every time you do a commit (at least), and then you check in the changes.
Also, you probably run it during development by using a Makefile that will automatically run it whenever the input changes.
This means that downstream packages never have to run it. They don't even have to have the code generation tool installed. This means a package maintainer can use any code generation tool they like.
It was probably done that way due to experience with Bazel, where doing a build means you need to build and run code generators written in multiple programming languages. It does indeed slow things down.
You run it every time you do a commit (at least), and then you check in the changes.
Also, you probably run it during development by using a Makefile that will automatically run it whenever the input changes.
This means that downstream packages never have to run it. They don't even have to have the code generation tool installed. This means a package maintainer can use any code generation tool they like.
It was probably done that way due to experience with Bazel, where doing a build means you need to build and run code generators written in multiple programming languages. It does indeed slow things down.
I think the Bazel style is to never check in the generated code, and to generate it at build time (potentially hitting a cache based on the declared inputs, of course). For cases where I use "go generate", I tend to check in the generated file so that you can install the resulting package with "go install". (It's also nice when someone who just wants to work on another part of the code doesn't have to install the generation tool just to run the application/module.)
In this case, you know to run "go generate" because the feature you just added doesn't work. (Though I tend to add a CI rule to make sure that the generator in CI produces the file that is checked into the repo. Because, yeah, you can forget, and it's nice for the computer to double check that.)
In this case, you know to run "go generate" because the feature you just added doesn't work. (Though I tend to add a CI rule to make sure that the generator in CI produces the file that is checked into the repo. Because, yeah, you can forget, and it's nice for the computer to double check that.)
> I think the Bazel style is to never check in the generated code
Not necessarily; there is plenty of checked in generated Go code at Google (as well as other PLs, but probably not as much), and other projects (e.g. Entgo) seem to encourage checking in generated Go code as well.
Not necessarily; there is plenty of checked in generated Go code at Google (as well as other PLs, but probably not as much), and other projects (e.g. Entgo) seem to encourage checking in generated Go code as well.
I don't really understand how this approach would work well with IDEs/autocompletion though.
For example, suppose I'm writing some mocked unit tests in Go and want to use mockgen to generate some mocks on an interface...
The code will compile and run successfully, but the developer experience is terrible because you lose the ability to use your IDE's code lens, syntax checks, autocompletion. Everything that's generated shows a red squiggly this-doesnt-exist line.
Maybe I'm just fundamentally misunderstanding how Bazel is supposed to be used. My setup is pretty typical. I develop in VS Code, and build using Bazel, but I do not allow Bazel to automate code generation because the generated sources do not appear in my local environment - just in the bazel sandbox.
Maybe someone can suggest a better approach?
For example, suppose I'm writing some mocked unit tests in Go and want to use mockgen to generate some mocks on an interface...
//go:generate mockgen (N.B. This generation is done by Bazel)
type Object interface {
Thing() string
}
mockThing := NewMockObject(ctrl)
mockThing.EXPECT().Thing().Return("Foo")
The code will compile and run successfully, but the developer experience is terrible because you lose the ability to use your IDE's code lens, syntax checks, autocompletion. Everything that's generated shows a red squiggly this-doesnt-exist line.
Maybe I'm just fundamentally misunderstanding how Bazel is supposed to be used. My setup is pretty typical. I develop in VS Code, and build using Bazel, but I do not allow Bazel to automate code generation because the generated sources do not appear in my local environment - just in the bazel sandbox.
Maybe someone can suggest a better approach?
Bazel in theory maintains its own directory of generated code that your IDE should refer to. Back when I last used Bazel, there was a bug open to make gopls properly understand this ("go packages driver" is the search term). Nobody touched this bug for a couple years, so I gave up.
Here's the bug: https://github.com/bazelbuild/rules_go/issues/512
I basically wouldn't use Bazel with Go. Go already has a build system, Bazel is best for languages that don't ship a build system, like C++.
Here's the bug: https://github.com/bazelbuild/rules_go/issues/512
I basically wouldn't use Bazel with Go. Go already has a build system, Bazel is best for languages that don't ship a build system, like C++.
This is exactly what I needed. However, the tooling around IDEs and the go packages driver still isn't up to scratch. For example, I can't get code lens to use Bazel for testing individual functions.
I think I agree that Bazel is poor for Go code, sadly it's what our SREs decided to use for our monorepo.
I think I agree that Bazel is poor for Go code, sadly it's what our SREs decided to use for our monorepo.
Good IDEs for Java, C# and Rust will handle generated code no problem. I have no idea how VS Code handles this but I’d image it’s a job for the language server. Whether or not Go’s server does it is a different matter - most Go I edit these days is in IntelliJ and built with Bazel, and everything works ok.
Frankly, I think that Go compiler speed is a huge feature, and this trade-off seems quite reasonable to me. It’s not that the bug will be undetected, it’s that it will be detected at the point of use rather than the declaration. But still at compile time. So what? It’s going to be pretty obvious what’s wrong.
Additionally, they do in fact have a timeout for build process in the Go playground. I tried running https://go.dev/play/p/mwyBUjcKvAo, and it says "timeout running go build".
> more important that the compiler is fast than that it is able to tell programmers about clear bugs in their code.
The actual tradeoff being made here is more like "it's better to give a good error message in 1s than a great error message in 10s." That doesn't seem obviously wrong to me.
The actual tradeoff being made here is more like "it's better to give a good error message in 1s than a great error message in 10s." That doesn't seem obviously wrong to me.
> In go, if you want a macro, you write a separate go program that generates code, write a "//go:generate" comment, and then have no way of knowing when to run it, no way of having incremental compilation with it, and it invariably ends up being slower than the compiler expanding it itself would have been.
1. Macros are just one use case replaced by go:generate step.
2. go:generated files are usually not the most moving parts while developing (except of course while you write the generator or its input. In fact go:embed has allowed to move some generated files to compile time and have not seen the need to replace go:generate with go:embed for those. (Does anyone has a compile benchmark?)
2. The Go compiler already uses caches and we can expect more and more caching will happen in future releases.
So I'm really not concerned by the compile time of files produced by go:generate instead of macros.
1. Macros are just one use case replaced by go:generate step.
2. go:generated files are usually not the most moving parts while developing (except of course while you write the generator or its input. In fact go:embed has allowed to move some generated files to compile time and have not seen the need to replace go:generate with go:embed for those. (Does anyone has a compile benchmark?)
2. The Go compiler already uses caches and we can expect more and more caching will happen in future releases.
So I'm really not concerned by the compile time of files produced by go:generate instead of macros.
> To be clear here, the tradeoff being made is that it is more important that the compiler is fast than that it is able to tell programmers about clear bugs in their code.
I'm not sure that's entirely true. Or it seems at least misleading.
"Fast" here means "guaranteed to finish before the heat death of the universe", in the worst case.
And as I'm trying to explain in the post, it is easier to explain clear bugs to the programmer, if you don't have to rely on solving NP-complete problems. NP-complete problems are notoriously hard to report errors for, which the user understands.
I'm not sure that's entirely true. Or it seems at least misleading.
"Fast" here means "guaranteed to finish before the heat death of the universe", in the worst case.
And as I'm trying to explain in the post, it is easier to explain clear bugs to the programmer, if you don't have to rely on solving NP-complete problems. NP-complete problems are notoriously hard to report errors for, which the user understands.
> ... but also in other languages where it could happen, but you know, doesn't.
My rust experience denies this.
My rust experience denies this.
> The compiler accepts it just fine, though.
I've never seen a concrete type in an interface before, so I decided to try it:
Since this is in the context of generics, I think the author might have been thinking about embedding types like comparable, which are interfaces (comparable is interestingly defined as `type comparable interface { comparable }`). You can, of course, put interfaces in interfaces in general (see io.ReadCloser and friends).
For the comparable case:
I don't know what the point of this comment is, since 99% of the article is not about this code block, but I guess I found it interesting.
I've never seen a concrete type in an interface before, so I decided to try it:
package main
type A interface {
int
M()
}
func f(x A) { // line 8
x.M()
}
./main.go:8:10: interface contains type constraints
Since this is in the context of generics, I think the author might have been thinking about embedding types like comparable, which are interfaces (comparable is interestingly defined as `type comparable interface { comparable }`). You can, of course, put interfaces in interfaces in general (see io.ReadCloser and friends).
For the comparable case:
type A interface {
comparable
M()
}
func p(x A) {
x.M()
}
./main.go:8:10: interface is (or embeds) comparable
I don't know what the point of this comment is, since 99% of the article is not about this code block, but I guess I found it interesting.
> interface contains type constraints
> interface is (or embeds) comparable
Currently, not all interface types may be used as value types. Such types include comparable.
It is very possible that all interface types could be used as value types in future Go versions, and comparable might be able to be used as value types as early as Go 1.20.
> interface is (or embeds) comparable
Currently, not all interface types may be used as value types. Such types include comparable.
It is very possible that all interface types could be used as value types in future Go versions, and comparable might be able to be used as value types as early as Go 1.20.
> It is indeed accepted if it's there by itself, but it is rejected if you try to use the interface, which is what function f does:
You can't use it as a type, but you can use it as a constraint: https://go.dev/play/p/LnmudHIjAoQ
Of course, you can then not actually instantiate that function (as the type set is empty). But using concrete types in interfaces is very possible. And it's indeed why the |-operator was introduced. It allows you to use operators: https://go.dev/play/p/I3eMDBwIcHA
You can't use it as a type, but you can use it as a constraint: https://go.dev/play/p/LnmudHIjAoQ
Of course, you can then not actually instantiate that function (as the type set is empty). But using concrete types in interfaces is very possible. And it's indeed why the |-operator was introduced. It allows you to use operators: https://go.dev/play/p/I3eMDBwIcHA
Huh?
You can put concrete types in interface definitions as of 1.18. See the spec: https://go.dev/ref/spec#Interface_types
You can put concrete types in interface definitions as of 1.18. See the spec: https://go.dev/ref/spec#Interface_types
The spec does say that. You can put them in the interface, but you can't use the interface. Try it:
https://go.dev/play/p/9ptEd8zasML
https://go.dev/play/p/9ptEd8zasML
You can put them in the interface, and then you can use the interface as a type constraint for generics:
https://go.dev/play/p/U25AzZndz-7
If you wanted to argue that you can't use it everywhere you could use an interface before, that'd be all well and good—but your assertion
> you can't actually put concrete types in interface{} definitions
is just incorrect, in a way that lead you to misunderstand the article.
https://go.dev/play/p/U25AzZndz-7
If you wanted to argue that you can't use it everywhere you could use an interface before, that'd be all well and good—but your assertion
> you can't actually put concrete types in interface{} definitions
is just incorrect, in a way that lead you to misunderstand the article.
It's astonishing how hard "modern" PL find it to implement parametric polymorphism. Java got it wrong and C# did at least have a hard time. I don't want to talk about what C++ did. Go needed years for that feature and now has problems with type constraints (I am not a go expert, though. Maybe these constraints aren't related to their generics?). So far, Rust seems to have gotten it right by essentially copying Haskell.
Is it pride that let's "industry" languages ignore decades of PL theory and research? The "design by committee" problem? Or something else entirely?
Is it pride that let's "industry" languages ignore decades of PL theory and research? The "design by committee" problem? Or something else entirely?
Philip Walder, who contributed to the design of Haskell (according to wikipedia, haven't dug deep here) worked with the Go developers on a PL theory underpinning for Go's generics: https://arxiv.org/abs/2005.11710
So, in fact, industry didn't ignore PL theory and research at all.
So, in fact, industry didn't ignore PL theory and research at all.
To go with sibling's comment, Wadler also had a hand in designing Java's generics while Guy Steele was a co-author of the Java Language Specification. And the idea that Eric Meijer ignored PL research is just mistaken.
Instead of belly aching about everyone who did it wrong, why not explain what is wrong and why you think so.
I mean, I think think Rust didn't do it perfect because I often want to use Box<dyn MyTrait> which is a hassle because I need to mark every function ?Sized if I want to pass a reference to my `x: &T...where T: MyTrait + ?Sized` and I don't enjoy that.
Instead of belly aching about everyone who did it wrong, why not explain what is wrong and why you think so.
I mean, I think think Rust didn't do it perfect because I often want to use Box<dyn MyTrait> which is a hassle because I need to mark every function ?Sized if I want to pass a reference to my `x: &T...where T: MyTrait + ?Sized` and I don't enjoy that.
Additionally, Josh's first generics implementation in Java was reified (like C#), but the necessary JVM changes were delayed, so he had to quickly do a second implementation using erasure.
Sometimes, reality bites.
Sometimes, reality bites.
One of Java's original goals was to work in embedded systems. As such, I think type erasure actually is helpful to reduce the size of compiled artefacts because you haven't monomorphised functions - hence avoiding potential bloat.
As in all of engineering, most things are a tradeoff.
As in all of engineering, most things are a tradeoff.
The other proposals I've heard for Java generics didn't monomorphize at compile time but instead modified the .class format to represent generic classes/methods closer to their source representation. Because the embedded systems at the time that cared about code size in Java would have been structured as bytecode interpreters, they arguably would have had smaller binaries without type erasure. The casts the erasure does under the hood are represented as additional bytecode at most call sites, but would have been implicit if generic functions had first class JVM support.
Every language has its own design features that end up influencing its generics system. Java has subtyping (in the form of class inheritance). Rust has lifetimes and linear types. Go has its ‘structurally typed’ interfaces (which are the reason impossible combinations of constraints exist in the first place).
Haskell has none of those, but it has plenty of other features that at least historically caused exponential compilation time [1] and unsoundness [2].
Even C++ arguably falls into that category to an extent. Its template system definitely could have been designed better, and using Haskell-like type signatures like Rust does is arguably a better approach… but Rust trait signatures tend to be more complex and less elegant than Haskell ones, because the simple and elegant ones have runtime overhead that Rust, like C++, isn’t willing to accept. (For example, see functions being a trait as opposed to a type.) And even Rust struggles to match C++ in metaprogramming expressivity, which also helps C++ reduce runtime overhead. Upcoming Rust features like `const fn` and specialization will help with that, but both have been ‘upcoming’ for many years…
[1] https://news.ycombinator.com/item?id=8130487
[2] https://gitlab.haskell.org/ghc/ghc/-/issues/7148
Even C++ arguably falls into that category to an extent. Its template system definitely could have been designed better, and using Haskell-like type signatures like Rust does is arguably a better approach… but Rust trait signatures tend to be more complex and less elegant than Haskell ones, because the simple and elegant ones have runtime overhead that Rust, like C++, isn’t willing to accept. (For example, see functions being a trait as opposed to a type.) And even Rust struggles to match C++ in metaprogramming expressivity, which also helps C++ reduce runtime overhead. Upcoming Rust features like `const fn` and specialization will help with that, but both have been ‘upcoming’ for many years…
[1] https://news.ycombinator.com/item?id=8130487
[2] https://gitlab.haskell.org/ghc/ghc/-/issues/7148
No, Rust and Haskell didn't solve the NP-completeness problem, which to avoid this is all about.
Don't Rust and Haskell "solve" this by just copping to an NP-hard compilation task and trying to do it anyway?
The usual way is to add a lot of special case heuristic for it, hope those work, and if they don't then bail out. (Report an error to the developer, so then they can nudge the types a bit an hope to find a setup where one of the heuristics work.)
And it's fine if the error messages are helpful, but this added implicit complexity to the language rightly gives folks the heebie-jeebies (se the recent comments for Rust's GAT patches)
And it's fine if the error messages are helpful, but this added implicit complexity to the language rightly gives folks the heebie-jeebies (se the recent comments for Rust's GAT patches)
As an N=1 sample point, I've programmed in Rust for years now, extensively using generics, and have not once ran into this issue.
NP-hardness only shows the worst case is really difficult. It does not mean that an approach is not useful. For example, Rust's exhaustive pattern matching is also technically NP-hard: https://niedzejkob.p4.team/rust-np/
NP-hardness only shows the worst case is really difficult. It does not mean that an approach is not useful. For example, Rust's exhaustive pattern matching is also technically NP-hard: https://niedzejkob.p4.team/rust-np/
Yeah, I don't mean to criticize the approach taken by other languages at all. Programmers want powerful type systems and fast compilation times and good error messages, and unfortunately this is one of the cases where things are really fundamentally, mathematically provably, at odds with each other in PL ergonomics. It's a wicked problem, not one you can "get it right".
But these "Go's ignoring decades of PL research!" comments are, at best, tiresome even when somewhat true. In this case it's the outright opposite.
But these "Go's ignoring decades of PL research!" comments are, at best, tiresome even when somewhat true. In this case it's the outright opposite.
No it's just ignorance. PL design is just one of the few areas where academia leads industry by a wide margin in understanding how to design compilers and type systems. Where academia lags and why these features fail to make it into production languages is that industry needs working compilers, build systems, debuggers, package managers, and linters more than it needs any kind of static typing.
The other problem is incentive and design approach. The academic approach to PL design is to carefully develop the type system and understand the way the rules interact, proving things like soundness, decidability, etc. the industry approach to software development is MVP. These two approaches are incompatible and lead to different language designs, because you can't slap a carefully designed system on top of a recklessly developed MVP that has been bumped incrementally over a long time. At least not without major time consuming rewrites.
The other problem is incentive and design approach. The academic approach to PL design is to carefully develop the type system and understand the way the rules interact, proving things like soundness, decidability, etc. the industry approach to software development is MVP. These two approaches are incompatible and lead to different language designs, because you can't slap a carefully designed system on top of a recklessly developed MVP that has been bumped incrementally over a long time. At least not without major time consuming rewrites.
> So far, Rust seems to have gotten it right by essentially copying Haskell.
FWIW I've used Rust for a bit and I disagree that they "got it right". I'm not saying Rust is bad, I like the language. But it's not as if their generics implementation does not have issues. It's just that they are different issues.
FWIW I've used Rust for a bit and I disagree that they "got it right". I'm not saying Rust is bad, I like the language. But it's not as if their generics implementation does not have issues. It's just that they are different issues.
[deleted]
[deleted]
Not pride, just little consequence.
Its not academia, the grade is getting fast funding or revenue because any language is fine and any performance is good enough because the bottlenecks are somewhere else or irrelevant
Its not academia, the grade is getting fast funding or revenue because any language is fine and any performance is good enough because the bottlenecks are somewhere else or irrelevant
I don't get why the compiler should have to check if the type set is non-empty.
The compiler only has to check when the generic type/func is used if the concrete type matches the type set. At worse the developer has written generic code that nobody can use.
Checking type sets is a work for a linter. But the developer should have caught the problem with a simple unit test.
I'm glad that the specification relieves the compiler writers from that the non-empty check task.
Checking type sets is a work for a linter. But the developer should have caught the problem with a simple unit test.
I'm glad that the specification relieves the compiler writers from that the non-empty check task.
There are two reason why the compiler would need to check: 1. Because it makes for a better developer experience, if you get early feedback about your code being wrong. And 2. because type-checking a generic function requires you to check that an operation is allowed for all types in a type set. If you write func F[T C](a, b T) T { return a + b }, the compiler needs to check that all types in C have a + operator. If the type set of C is empty, then that's true - all types in the empty set have the + operator.
I want type check to be fast, directly in my editor.
Linting can happen asynchronously in CI.
Linting can happen asynchronously in CI.
> ...
> This is especially important for environments like the Go playground, which regularly compiles untrusted code.
To be clear here, the tradeoff being made is that it is more important that the compiler is fast than that it is able to tell programmers about clear bugs in their code.
I see the justification of the playground as unconvincing too. You can run 'for {}' in the playground, and you'll get "timeout running program". They already have solved the problem for the playground because obviously at runtime a go program can take infinite time, and it doesn't seem like it's any harder to also constrain compilation in the same way.
The actual cost that the go compiler being fast has is that other parts of go are slow. In other languages, a macro will execute as part of compilation, and incremental compilation will work with it. In go, if you want a macro, you write a separate go program that generates code, write a "//go:generate" comment, and then have no way of knowing when to run it, no way of having incremental compilation with it, and it invariably ends up being slower than the compiler expanding it itself would have been.
Now, if you want to know if you have an impossible type set, you'll run "go vet" (which likely doesn't do this validation, I haven't checked) or one of the various linting tools, it'll have to re-parse and re-compile all the code, it won't cache, and it'll ultimately give you the same answer the compiler could have given you.
I suppose this is superior in one way: when performing such generation and validation, you can do it against only your own code, rather than against third party code you import, while if it were part of the compiler directly it would typically end up running against all compilation units, even third party ones....
In practice though, even for "slow to compile" languages, I find that I spend more time finding and fixing bugs than I do waiting for compilation, especially with incremental compilation. On the other hand, with go, I spend less time total compiling code, more time total fixing bugs, and more time total running golangci-lint and various other bits of code-generation.
I spend exactly 0 time worrying that some adversarial third-party dependency I import will make my compile-times exponential, both in go where it can't happen by design, but also in other languages where it could happen, but you know, doesn't.