Featherweight Go
arxiv.org
arxiv.org
YouTube channel where the talk will be streamed live - https://www.youtube.com/channel/UCiGOzKde1rlvzEB7J73gvrQ
Featherweight Go is restricted to a tiny subset of Go. We plan a model
of other important features such as assignments, arrays, slices, and
packages, which we will dub Bantamweight Go; and a model of Go’s
innovative concurrency mechanism based on “goroutines” and message
passing, which we will dub Cruiserweight Go.
Required better for mobile.
This code block is a scrolling nightmare on mobile.
I’m most curious how they perform on compilation speed assuming a big project makes decent use of generics. I doubt golang would merge anything that causes significant slowdown. And I don’t blame them, the only reason I don’t dread TypeScript dev given its slow compile times is you can typecheck async and strip the typing information for the hot reload.
Don't ever try C++. I work on a medium-sized low-level C++ application, and every time we need to compile from scratch it takes over two hours on a single core. Even with distributing the compilation out across over a hundred cores the fastest it can get down to is around 20 minutes.
Pimpl is more for reducing how much you have to change headers forcing a recompile during development. It's also really handy for keeping binary compatibility with published dynamic libraries so that you don't have to recompile dependants.
Perhaps they're changing some fundamentals of the codebase and (unsurprisingly) the compiler seems slower than you might expect.
Formula known for years: keep it simple, minimal template (ab)use and know what you are putting in .h/.cpp files. Cramming everything into headers hoping compiler will inline stuff is a bed time story. Also, your build system will be grateful knowing that every compilation unit is independent as possible; it will take less time to calculate dependencies and will easily distribute compilation across cores, if requested.
- "module" system based around textual inclusion of header file: essentially the compiler duplicates a lot of effort, reading the same files over and over for each translation unit, and you can't avoid the cost because of the interaction with text macros. That said, C++20 offers a solution through its new module system; it will be interesting to see how much of an improvement this will bring.
- complicated parser requiring contextual information (i.e. information from typing and analysis phases) in order to distinguish between, say, a class object instantiation and function forward declaration (the notorious most vexing parse). Most other languages learned from the syntax mistakes of C++, but C++ had a clear mandate to not break existing C code, so it had no choice but to build what existed.
- C++ template system revolves around a kind of syntactic substitution, where you have a template expression with some type variable, and at the template instantiation site (i.e. every call, not at the definition) you you essentially do template argument deduction yielding concrete type bindings for the type variables, and then your next step is the transform the AST with the template expressions into concrete types, functions, etc. This involves a lot of tree transformations which can be expensive. I think with other languages this is less of a problem in part because the type checking is done at the definition site, rather than at call site. Here again C++ concepts were introduced to address this issue, but as always in C++, it's not all milk and honey.
I just compiled around 240k lines of scala split over around 200 gradle subprojects with gradle 6.5rc1 and scalac 2.12.11. Limited to 10 gradle workers. Took 4 minutes without the gradle build cache enabled.
Also gradle 6.5 fixes a scala compilation performance regression that was introduced in gradle 6: https://github.com/gradle/gradle/issues/12591
https://www.lihaoyi.com/post/SowhatswrongwithSBT.html
https://engineering.linkedin.com/blog/2018/07/how-we-improve...
Problem with C++ template generics is that they are reinstantiated per type __per compilation unit__.
I think they can
* Use dynamic dispatch liberally - such that one instantiation per object size in order to avoid boxing. That said, I don't know how the experimental generics work. And this will obviously prevent some optimizations, notably escape analysis.
* defer compilation of generic code to the end i.e "just before linking" phase instead of eliminating duplicates at link time.
* Some kind of caching mechanism for generic code such that you `sed` the machine code / plan9 intermediate to replace it with type specialization wherever required - should work if you are willing to sacrifice some optimizations, As majority of time is spent in code generation. On the flip side, Go team can come up with different optimization strategy for that part of code because Go doesn't do many optimizations in current form.
I am no expert on compilers / optimization. But generics will obviously reduce the total code one needs to compile. And combined with some techniques I guess they can control compile times from regressing.
> Use dynamic dispatch liberally - such that one instantiation per object size in order to avoid boxing. That said, I don't know how the experimental generics work. And this will obviously prevent some optimizations, notably escape analysis.
I think you're right about optimization: dynamic dispatch is what most of the template users want to avoid
> defer compilation of generic code to the end i.e "just before linking" phase instead of eliminating duplicates at link time.
Pretty cool. Never thought about that, though I believe LTO in gcc/clang might cover this part in some near future, or already had some partial supports.
> Some kind of caching mechanism for generic code such that you `sed` the machine code / plan9 intermediate to replace it with type specialization wherever required
Not sure about this though...not sure if the benefit outperforms the overhead cuz it sounds pretty expensive. But as a similar approach, JIT compilation might be a way.
I thought typescript also used structural subtyping? i.e. in typescript I can define:
interface Stringer {
String: () => string
}
function takesStringer(s: Stringer) {}
This seems to match structural subtyping in go.
Am I missing some reason that this isn't structural subtyping as referred to in the paper? Do they mean to say that typescript isn't a "mainstream typed programming language"?
I assume they're not considering it because typescript compiles to javascript, so it doesn't have the problem Go faces of how to generate code for its generics. The wording is definitely weird though.
Up to now it always seems to have been one step forward, two steps back (or rather "wait another few versions")
At least some work is being done, even if "This is the beginning of the story, not the end".
Featherweight Java is an idealized language, small enough for doing experiments. These experiments often involve the necessity of a formal proof. But being a small language, still capturing the crux of the full language, greatly simplifies the problem space.
Featherweight Go serves the same purpose: find the core. Give the core generics. Then you have a good chance at implementing generics for the full language.
Most languages which end up with type parametrization do so when the language is small and somewhat pliable. Neither Java nor Go did, even though both languages had plenty of prior work in the area. Hence, you have to "reconstruct" a world in which there is such a small language such that your experiments run fast.
It was a mistake in Java that they corrected with a lot of pain. It is a mistake in Go they are going to correct and most likely with a lot of pain. If they cannot do it seamlessly it may end up being a Python 2/3 platform split.
Those who fail to learn from history are doomed to repeat it.
It's also not at all clear that Go will have similar problems as Python did, since the Go team considers backward compatibility important and might approach the problem differently, learning from Python what to avoid.
Counterfactual reasoning is difficult. Learning from history isn't as easy as some make it look.
Because there were languages that are much better suited for what Go was designed for. To name a few: Erlang (concurrency that is better than Go's, "channels" and types on par with Go with Dialyzer), Haskell (thread concurrency better than Erlang's, channels, transaction memory, etc and types well beyond Go) and many others.
Go was successful despite mistakes.
Certainly, a lot of people are attracted to Rob Pike's rather idiosyncratic preferences, tastes, and nostalgia for the early days of Unix, which are on display in a lot of Go's design decisions, like the lack of generics. But lots of random people have preferences and nostalgia for all sorts of things; we usually only pay attention to such things when it's a person with a famous pedigree who has them.
Was there something in this paper that you felt unfairly treated Rust, the language you represent on these threads? Because otherwise, I can't see what would motivate you to join this thread to snipe.
I'm with David, for what it's worth. Lack of generics has mostly helped me be productive in Go, and the extreme prevalence of generics in every Rust library I deal with has definitely slowed me down a bit. I'm looking forward to generics support in Go, but mostly for what I hope it does to message board threads.
Let me put it another way: Virtually all languages that have become popular recently have done so because of the backing of some large organization or another. There was a time when languages like Perl, Python, and PHP could arise out of basically nowhere and become popular. That time is gone, and now languages essentially need organizational backing of some kind to succeed. That was true for TypeScript, it was true for Rust, it was true for Swift, it was true for Kotlin, and it was true for Go. They also benefit from some sort of well-known thought leader, a role that Rob Pike plays well. If you think Go would have gotten popular without having a Google and a Rob Pike behind it, then, well, I don't know what to tell you. I don't think Rust would have been popular either without the Mozilla association.
Or, more succinctly: I see no world in which Go having simple ML-style generics, without typeclasses or functors, would have made it any less popular. Other factors dominate when it comes to success of a programming language. TypeScript, in fact, shows that you can have generics that are more complex than those of Rust and still become wildly popular.
But the bigger problem is just that Rust programmers use generics absolutely everywhere (my early impression is you basically can't avoid it, because of lifetimes), and it simply does make everything harder to understand. I know I'm going to be told that if I buckle down all of this stuff will make sense and I'll be fluent with it, and sure, I managed to grok Alexandrescu C++, too. But adding new layers of indirection everywhere just has to impede comprehension; that's always the tradeoff for parameterizing and indirecting!
The flip side of this is, I've built some fairly serious things in Go --- a compiler, a couple emulators, a disassembler, a symbolic evaluator; not just the server stuff Go is supposed to be good at --- and I have complaints about Go, but almost none of them are its lack of generics.
(There are things I like about Rust! But this isn't the thread for it.)
Reading the esbuild discussion at the time, it definitely read to me as "our language is definitely faster and if you're not getting the same performance you're holding it wrong", but looking at it now I can see how it wouldn't be intended that way.
Regardless, sorry; I think I was projecting some frustrations with the wider RESF on to you.
I’ve now resigned myself to wishing it treated its magic generics with proper typing.
You are right, Go got more initial momentum because it came out of google and had Rob and Ken's names attached to it. But the useful part is why people actually use it.
I hear this a lot, but the counterexample is always Dart. Google is behind it, and Lars Bak is definitely not a nobody, yet the language struggled to gain momentum; not until Flutter came on the scene, and it wasn't an official Google project when it started.
for i := len(a)/2 - 1; i >= 0; i-- {
opp := len(a) - 1 - i
a[i], a[opp] = a[opp], a[i]
}
Without generics you have to hope the stdlib gets a blessed generic function like reverse() one day since you can't build one without rolling your own monomorphization code-gen or a goofball interface{}+cast hack.
For people who supposedly prefer the lack of generics (which seems more like cargo culting or Stockholm Syndrome), no problem. We can just add a config option to golint that prohibits you from using generics. That way you don't need to hold up the rest of us. win-win.
That's a recurrent issue with Go: you can either have ergonomic tools (with interface and reflection), or performant code (with no allocation) but you generally can't have both at the same time. Sure it's better than scripting language where you need to use another language when you need performance, but it's still kind of sad.
If writing a function that can take an array or slice of any type of data requires providing a generic argument (I.e. so you can specify that the function returns a slice of the same type of data as it was given), then you can name it "reverse" if it reverses the array, write it only once, and every timr you use it, you read "reverse" and know what it does.
For loops dont have those names, and so have to be rewritten every time you use them. As such, every time you see a for loop, you have to read and parse every statement to see what it is doing, and if it has any unexpected side effects or bugs introduced via copy-paste or what not.
https://github.com/gcanti/io-ts/blob/master/src/Schema.ts#L2...
Granted, genetics don't need to be done that way, but it is among the more common and popular approaches. The type information is tangled up in the implementation, making focusing on either more challenging. Perhaps we need modes for syntax highlighting- one for types, one for implementation?
Which is why Go had already a good example to learn from on how not to do language design.
As much as I like generics, Go's popularity is a success: programmers have spoken, and they value other things more than generics.
Hindsight is 20/20, and even this isn't a commitment to introduce generics in Go.
Both its main influences, Oberon-2 and Limbo had zero traction on the market, and Limbo not only is quite close to Go, it had an whole OS full of the Plan 9 ideas to come along, yet it failed on the market.
Lack of generics has already been publicly acknowldge as problem.
> In three years of Go surveys, lack of generics has always been listed as one of the top three problems to fix in the language.
https://blog.golang.org/why-generics
And yes, there is no place on the 21st century for typed languages without generics, we already have enough of them from the previous century already.
CLU and ML, the first languages to support genericity are from the mid-70's, they are older than C++ and contemporary to C.
It can also feel sometimes like a dynamic language which has attracted people from ruby, python, JS, etc... communities.
You say there's no place for it in the 21st century, yet it already has a place and it doesn't really need generics to continue living.
I agree Go cannot offer similar things due to a weaker type system.
I willingly code Go day-to-day. I miss Java streams, and sometimes the codebase is slightly worse due to the lack of Java streams (or equivalent).
I accept a weaker language because I spend less time debating the Right Way to do things (Go is too inexpressive to support a Right Way), and because I can widen my hiring pool from those that know Java, to those that any language, knowing that they can easily pick up Go.
Why isn't Dart seeing the same type of success?
Original Go team did not suffer from this.
That's from people who complain because they want Golang to be like Java
If I had to write a list of “tools I would have preferred to have”:
1. Perfect serialization libraries - Serde is the gold standard here, and IIRC the macro system from Rust is as important a part of it as the traits part.
2. Mutability of types in shared caches - to build efficient controller patterns you need fast and efficient caches - an immutable type that protects against mutation would have saved a lot of ugly mutation testing code
3. Client library definitions shared across types - we could have reduced a fair amount of boilerplate with generics, although most bugs are in the serialization part these days as types evolve
But most of these are dwarfed by the need to scale reviewer time across hundreds of people submitting PRs that change fundamentals of the code. The simplicity of Go and ability to review stupid, obvious, absolutely critical code is the reason why I love it.
Having a strong way to reduce cleverness has been a godsend. It doesn’t mean cleverness is bad, or I don’t want more tools in Go. But I appreciate that aspect of Go in a way that others may not.
Edit: I have been watching kube-rs mature, but to get the same level of scale and performance we’d have to reproduce the shared index informers and that’s a lot of drudge work to get right. That’s one place where someone motivated could really help Rust become a first place way to extend Kubernetes, which would be exciting.
Don't mind.
It’s just ugly because that’s how it evolved after a community formed and that’s what real evolved software looks like. :)
Not saying it is a bad language, but it really helps that Go had Google's blessing.
Or perhaps Google has many hearts and no one knows exactly how many or where they are at any given point in time :-)
How exactly is Google "shoving it down our throats"?
Second what Sun choose to implement was a smaller subset and not that close to Featherweight Java/pizza compiler. It was only generics, not first class functions at the time, nor algebraic types/pattern matching.
> " We haven't yet found a design that gives value proportionate to the complexity, although we continue to think about it."
I mean if you are going to use 2001 technology, you could have found it long back.
> In three years of Go surveys, lack of generics has always been listed as one of the top three problems to fix in the language.
https://blog.golang.org/why-generics
By the way, they could have gone to 1974 (CLU), 1973 (ML), 1983 (Ada), 1986 (Eiffel), 1988 (Modula-3), 1990 (Sather & BETA), 1998 (C++), 2007 (D), 2009 (Java & Delphi).
These are just the most well known examples, CS literature in SIGPLAN and IEEE has plenty more to choose from. I bet Google employees can afford the respective subscriptions.
When there isn't any political willingness, there isn't anything to be found.
If I understand you right, you are suggesting that instead of doing what they are doing now, they should have just used an existing design from your list, right from the beginning?
Is there any specific design from your list that you think would have been good to use in Go? Or, do you think it would have been better to have a less-capable generics implementation available right away instead of a more-capable one later?
For example the one you mention the most (Java) requires code duplication to work with 32 and 64 bit floats. I think even the previous proposals that have been rejected for Go have at least had that ability.
Not to mention the open invitation for concrete proposals on how to add them Go.
You might find this post by one of the Go team members interesting:
For example, while Valhalla has taken several years so far, OpenJDK team has experimental builds that you can go and play around with value types in Java.
Where are the experimental builds for generics support in Go?
Actually Valhalla is pretty interesting to think about. For what I'm currently working on, the inability to have a list of points without individually heap-allocating each one makes a language much more of a non-starter than the lack of user-defined parameterized types does.
Even back when Java was invented, there was plenty of prior art (going back decades) about efficiently representing a list of points in memory. Probably most of its predecessors could do it. Yet Java has lacked this basic ability for 25 years.
I even expect that when they eventually implement it it will work similarly to other popular languages, compared to Go which seems to be drawing on more recent developments (like concepts etc) for its generics design.
Despite this, I don't accuse the Java team of political machinations every time the topic comes up. Mainly because I don't believe that to be the case. Maybe they've prioritized a critical feature for me lower than I would like, but it seems like a substantial amount of work to implement because (like generics) it interacts with other language features in a complex way and (like generics) once they ship a design they will be stuck keeping backwards compatibility with it basically forever, so they only have one chance to get it right.
Even stuff like error handling improvements and type alias were almost shot down.
Sure, I think it's fair to say they've focused a lot more on implementation and library changes and not language changes up until recently. Things like rewriting the compiler from C, improving code generation / escape analysis / GC, more platform / architecture support, improving the standard library, getting a reasonable package manager, etc.
So it seems a little premature to read some secret anti-generics stance into it (and it not just being a matter of priorities) since there were all these other areas that they were also way behind Java in.
After package management was in generics started showing signs of life again, so it all seems reasonably consistent with the Go team just wanting to clear other stuff off their plate first before tackling it. Hopefully we see it in a similar timeframe to major Java/C++ features now that it's being worked on more.
If there's any silver lining the actual proposals seem pretty ambitious, seems like they want to enable a lot more than just new type safe collections if they add the feature.
https://github.com/ccbrown/wasm-go-playground/tree/master/ex...
So this is the prototype used at the GopherCon talk.
Secondly, I also kind of like Go, just see it as lost opportunity to have been with little more than a C like type system, even C has some genericity support in the meantime.
And whatever gets out of it, will be rather clunky as proven by late adoption in Java.
On another note, every other Go thread has you and @pcwalton bashing Go. Makes me wonder if Go's success causes some sort of discomfort in some people. It's almost religiously guaranteed to have you both regurgitation the same crap over and over.
What about that then?
But I guess you're actually consistent: you often lament about people ignoring or reinventing approaches that proved themselves in older languages. Here are people that actually take clues from one such language, and you lament that they didn't do it earlier. I see now that it's not really ironic. Rather, you're seeing the glass half empty while I was seeing it half full.
While I am sure Java will get value types, it already has had several experimental releases and the features have been incrementally integrated, after the switch to 6 months release cadence, I am not so sure in regards to Go.
All we get is a source code repository full of comments showing how much is left to be done, if ever. Untouched since last August.
https://github.com/wenkokke/featherweight-go-gen
This one seems to be the new FGG one.
In brief, they are following a process of stripping Go to the most basic possible syntax, and then adding generics (Featherweight). Then they will add more features back and build up to the full language, ending with Cruiserweight where channels will be addressed.
The generics proposal builds on interfaces rather than contracts. Wadler sees Go occupying a unique space in terms of supporting "open supertypes" in the sense that in Go we do not have to declare a struct to be of a particular interface type it is automatically derived based on the methods defined on the struct. This allows a proposal which allows Go to be extended tp solve the "expression problem" first defined by Wadler in 98.
I really hope these beautiful ideas turn out to be workable - I am sure Go will gain immensely if they are well thought out.
The example includes a simple generic `Filter` function
https://ccbrown.github.io/wasm-go-playground/experimental/ge...
> Today [Go] sits at position 12 on the Tiobe Programming
> Language Index (Haskell sits at position 41).
But more seriously, it's interesting how this produces publications before actual implementations.
The notation is abused though. Try looking up some of the work by Guy L. Steele in the recent years.
https://labs.oracle.com/pls/apex/f?p=94065:40150:0::::P40150...
Journal papers usually don't get rewritten into Prolog or fed into proof assistants. They're read by human beings. I've long suspected (and colleagues used to "joke" about it) that excessive use of mathematical notation is just employed to impress and/or confuse peer reviewers into just accepting the paper instead of trying to comprehend it first.
The sequent calculus is great—I am far from an expert and for many papers I can skip the text at first, read the sequents, and then just go back to the prose only if I have specific questions. No prolog conversion needed.
As programers, we should be able to read, not just write, formal languages, and appreciate the value of the precision they provide.
I am not ignorant. I tried to rationalize this in the beginning too. It's just hostile towards the reader.
> As programers, we should be able to read, not just write, formal languages, and appreciate the value of the precision they provide.
We should also be able to see where they are appropriate and where not.
The problem is that getting the notation right is actually quite hard. People write, to the best of their effort, to make the description succinct and understandable. But the notation is pliable, in the same way much mathematics is written: it isn't as rigorous as we would like.
Writing the same thing in regular prose is much much harder and there are many more ways things can go wrong.
So the state-of-the-art demands formal proof which can be verified by a machine. And it shows in the precision of the notation, which often leaves little to no room for wrong interpretation.
Sometimes planning before implementing is a good thing, or does even language design need to be agile™?
Not sure what real problem this is solving. In practise you don't just add new cases, you delete some cases, and you re-add different cases later. Two different people might add two different cases in parallel with each other. Oops, now you have to re-compile anyway.
This choice comes with potential business, legal, and other ramifications, for example, should Google get all of the benefit, in terms of fame, goodwill, users and other intrinsic bonuses from the work you've done; or could you profit (if that was your goal) if you were to create your own company around this new language?
You see, that's what I mean by potential business and legal issues.
Oftentimes, people who are employed by other people work extremely hard on academic pursuits, such as academic papers, yet their work is never adequately rewarded, compensated, or even appreciated.
Which is why I suggest you create your own language and possibly your own company around that language. Because otherwise you'll never know nor understand the true economic value of what you've created, and you might spend an eternity trying to convince people who are of lesser intelligence to read your paper, whereas they could be using, downloading, telling their friends about the great new language you created; and maybe even paying you money, if you played your cards right...
Note that I am not suggesting you go this route (it's your decision, maybe you just want to bring better free open source software to the open source community and that's highly laudable), all I'm saying is, you might be on your bed on your 85th birthday, and you might look back at your life, and you might wonder "boy, I wonder what would have happened had I tried to start a company around this set of ideas; I wonder what would have happened if I had taken the road not travelled.."
That's all I'm trying to say...
Nothing more, nothing less.
Your choice.
Make it wisely.
Your paper shows tons of intellect.
The "Featherweight Go" referred to in the paper is simply a tiny subset of the Go language itself that's being used as a framework for formalising the mechanism they're proposing could be used.