This has shown up on the orange site as well and I’m… a little baffled by the discussions there, and by the article itself, too. I’m kind of going through a bit of an “am I getting grumpy and obsolete and not getting how programming is done anymore?” phase so this hits a little close to home…
I mean, this whole criticism is centered around one buggy implementation of a hash table, mostly related to a poor choice of algorithm and a few oversights, such as key collisions. Any approach to generics can run into these problems. I can write exactly the same code in Rust using generics and it will have exactly the same problems – except, I guess, since my BuggyHashMap is now a BuggyHashMap<K: Eq + HashFNV32, V> or whatever, I will be able shoot myself in the foot in several places, using a wide variety of bullets.
Providing a particular abstraction (or not!) is a trade-off like all others. It’s not like C++ or Rust’s approach to generics and their use in the standard library are “free”. You pay for them with compiler complexity, tortuous long-term evolution due to standard library size (also development effort – remember the get_temporary_buffer fiasco?), and extra difficulties in reasoning about performance in more complex cases.
In fact, as the author otherwise points out, “there isn’t just a hash table algorithm, the details matter. A lot. “ Maybe the folks behind Hare figured that, for the applications they’re targeting, you either have modest performance requirements, in which case any naive (but bug-free) implementation you copy-paste off StackOverflow is fine, or you have high performance requirements, in which you’re likely going to end up employing black hashing magic anyway so you might as well write the rest of the boilerplate, too.
I’m not saying I agree with them – I don’t know what they intend to do with Hare and what kind of programming it’s meant to facilitate, so I really wouldn’t know where to begin agreeing or disagreeing (edit, FWIW I’m sort of suspect @Corbin is right here but let’s give Hare the benefit of the doubt, eh?). But I have a feeling they may have a better grasp of what’s relevant for their project than some random Internet person. Either way, while it may be the wrong trade-off to make (and, okay, I have so many void *-induced nightmares that I don’t really want to put up with a language that doesn’t have generics, so I’m more than willing to entertain the idea that it is the wrong trade-off to make in 2022), it may be worth at least acknowledging that it is a trade-off.
The author is also making some… overly-general, I guess (I was gonna say weird) claims about C, like:
In C, you don’t have a hash table, and the most natural data structure is some form of a linked list. So that gets used a lot. You can bring in a hash table, of course, but adapting it for use is non trivial, so they are used a lot less often.
The most natural data structure for what? I’ve written a lot of C over the years (embedded development is like that, sadly…) and while I’m anything but enthusiastic about C (or anything that isn’t Ada for that matter, shh!) I can’t think of a single case where I ended up using a linked list even though a hash table would’ve been better. When you need a hash table, you bring in a hash table – sure, it’s not trivial, but there are plenty of non trivial things in other languages as well. It’s not very productive to dwell on this one particular case.
Right, if that’s the case, it is very likely that I have misunderstood it, my memories about my behaviour around the ripe age of nine are thankfully somewhat dim.
I think one of the things that Go got right is figuring out what the core data types needed for a modern language are. I wrote this in 2013, and I think it holds up:
The designers of Go agree with the collective experience of the last twenty years of programming that there are three basic data types a modern language needs to provide as built-ins: Unicode strings, variable length arrays (called “slices” in Go), and hash tables (called “maps”). Languages that don’t provide those types at a syntax level cannot be called modern anymore.
I think a lot of people would like to add Optional/Maybe and sum types to that list of core data types. In any event, you’re going to get pushback if you try to release a new language without an easy way to create those types.
Even C has special syntax for strings and arrays (considering that strings in C are just 0-terminated character arrays, it could have done without string literals). I think Kotlin has it only for strings, but it makes the code more verbose.
You could provide hash tables via the standard library, I guess, but I don’t see how you could possible do strings or arrays without some special syntax.
A couple of minor nits, given because the author kinda asks for them…
I mean, I guess it would be nice to have a way to do streaming on query strings? But the most natural way to do that is to use a hash table directly.
URL query strings are not guaranteed to have a 1-1 mapping between keys and values, as [there is nothing in the RFC suggesting that there should be(https://www.rfc-editor.org/rfc/rfc3986#section-3.4). In the wild, especially with forms and things (IIRC) you’ll run into duplicate keys, the interpretation of which is up to the stack. Saying “just shove it all into a hashmap” is ignorant of the problem domain, unless you specify how you mean to use that map.
In C, you don’t have a hash table, and the most natural data structure is some form of a linked list. So that gets used a lot.
There isn’t a standard library in C for linked-lists, as far as I remember, and the number of bugs due to incorrect hand-rolled implementations of linked-lists I think probably far outstrip the number of bugs due to bad hahtable implementations.
A hash table is not a simple data structure, let’s start with that. It is the subject of much research and a ton of effort was spent on optimizing them. They are not the sort of things that you roll out yourself.
It’s not easy to get them perfect, and quite tricky to get them really performant in the general case, but in my experience implementing a basic hashmap isn’t something you need a PhD and FANG money to do. The author then immediately appeals to authority by linking a bunch of CppCON talks, and given my experience with hashmaps comes directly from reimplementing them due to the super neat EASTL whitepaper and the lack of a good cross-platform unordered_map in the standard library between the GCC and MSVC ecosystems at the time…yeah, I call bullshit.
Plainly: Stop gatekeeping datastructures bro.
Let’s see how many things just pop to mind immediately in here as issues.
The context the author cheerfully leaves out, from the article he’s attempting to lambast, is that they needed a one-off special-case hashmap for some little fiddly bit of code and they built a really barebones one that exactly fit their usecase. In the original article, DDV explicitly says “Yeah, we picked 64 buckets because it was enough, yeah we could’ve done dynamic rehashing if we needed to, meh this is Good Enough”.
The author is complaining about a one-off implementation because it isn’t a high-performance generalized standard library package developed over decades (as it is in other languages), and I guess I’d say…that isn’t the point. If profiling reveals that routine to be a true bottleneck in their code, they’ll probably update the hashmap or hash function when that day comes, but they’ve got a lot of ground to cover in developing the foundations of Hare without spending time polishing a data structure.
I think there are valid criticisms of the language and process, but this whole article didn’t strike me as having pretty much any of them.
The author is complaining about a one-off implementation because it isn’t a high-performance generalized standard library package developed over decades[…]
The author is complaining because this basic hashmap is not even correct as it doesn’t handle collisions. It also doesn’t implement deletion.
Also, if performance isn’t that important and you can do with crappy hashmaps and the likes… Why write in a C-like language? Why do manual allocations? Why not use a GC and better building blocks? That’s what gets me, personally.
For deletion, probably not. For collisions, my understanding is that the collision would be handled silently (on lookup), so it’s hard to argue that this is correct behavior. Unless you like playing russian roulette with your module names.
I have mercilessly flagged rants and sourcehut spam, as well as gotten into slapfights with Drew here. Believe me when I say, without any love or affection for the fellow, that I’m pretty sure your take here is wrong.
Haskell doesn’t have hashmaps in base, but the tools that haskell gives you to implement maps are so powerful that it makes them easy. With hare you have to draw the rest of the owl. Some people do like drawing the rest of the owl though.
:shrugs: I cannot imagine using a language without generics. Even in C one frequently ends up emulating vtables or passing comparators manually and so on. But the arguments in the article were lacking.
Is in the Prelude I think, and works well until you need performance. I mostly use Haskell for research code (read: not performance intensive) and you’d be surprised how far list-based maps take you.
Yes, the tuple (a, b) represents a key paired with a value (equal to Lisp’s '(a . b)), and the [ ] brackets imply a Cons list. The alist is linear and insert/append/removes are still very much O(n).
Data.Map implements a hash-map-like balanced tree, and is simple to implement on your own (if you like writing trees in Haskell, that is).
Language with first public release does not have put as much thought and research into a data structure as the language ecosystem that often claims to be the #1. News at 11.
That is not me defending Hare but I didn’t like the tone of this post either.
Perhaps I’m wrong but it seems that the arguments made in this article contradict themselves. The Hare blog post is quoted as saying:
…it’s likely that the application of a higher-level data structure will provide a meaningful impact to your program. Instead of providing such data structures in the standard library (or even, through generics, in third-party libraries), Hare leaves this work to you.
The author seems to take issue with this statement but then to disprove the claim that hash maps are simple to implement he states this:
tsl::hopscotch_map
tsl::robin_map
tsl::sparse_map
std::unordered_map
google::dense_hash_map
QHash
Why are there so many of those?
Well, because that matters. Each of those implementations are optimizing for something specific in different ways. There isn’t just a hash table algorithm, the details matter. A lot.
That statement seems perfectly consistent with the statement made by the Hare blog post, in other words, the specific implementation of hash map matters a lot for your particular application.
In the C tradition, I agree with Hare’s claim that a robust standard open addressing hash table (as a specific implementation of a hash map) is relatively straightforward to build. The complexity tends to be in the design of the hash function, which would be the case even if Hare provided a standard library hash table.
I don’t really agree that maps are a basic data structure, and I think the amount of C++ implementations and comparisons linked in the author’s post proves that. They are widely used and providing a “good enough in most cases” implementation like Go does would probably be useful, but I wouldn’t say it’s necessary in a language as barebones as Hare. And it would require the language to have some form of generics (which should’ve been in from the start, imo) or some compiler magic like Go did with map[].
Many C programs often use a singly linked list for n < ~10 - that usually performs very well, a lookup is often only 10 comparisons which is probably pretty close to the cost of running a hash function anyway… I need to run a benchmark.
I have seen compilers do this - its quite common to have fewer than 10 variables in a scope. It’s still a map, but for many human scale problems a hash map doesn’t matter.
C does not provide maps, and when I really need one I can implement it in less than 200 lines (won’t be generic, though). Were I to design a language like Hare or Zig, providing an actual (hash) map implementation would be way down my list of priorities. Even if it belongs in the standard library, my first order of business would be to make sure we can implement that kind of things.
In fact, Go made a mistake when it provided maps directly without providing general purpose generics. That alone hinted at a severe lack of orthogonality. If maps have to be part of the core language, that means users can’t write one themselves. Which means they probably can’t write many other useful data structures. As Go authors originally did, you could fail to see that if the most common ones (arrays, hash tables…) are already part of the core language.
The most important question is not whether your language has maps. It’s whether we can add maps that really matters. Because if we can’t, there’s almost certainly a much more serious root cause, such as the lack of generics.
Go’s original approach of providing just three fundamental generic data structures (vec, map, and chan) definitely was a worthwhile experiment in language design, and I have the feeling that it almost worked.
At this point I’d argue that the benefits of even the simplest version of generics (not bounded, template-style or ML-functor-style, whatever) are so huge compared to the downsides, that it’s just poor design to create a new statically typed language without them. It’s almost like creating a language without function calls.
Go finally fixed that — which doesn’t fix all the other design issues like zero values or lack of sum types — but their initial set of baked-in generic structures was necessary to make the language not unbearable to use. If they hadn’t baked these in, who would use Go at all?
Could you share more here? I agree about Go generics, but its zero values are one thing I miss when using other imperative languages. They’re less helpful in functional languages, but I even miss zero values when using OCaml in an imperative style.
not always something that makes sense (what’s the 0 value for a file descriptor? an invalid file descriptor, is what. For a mutex? same thing.) The criticism in a recent fasterthanlime article points this out well: Go makes up some weird rules about nil channels because it has to, instead of just… preventing channels from being nil ever.
error prone: you add a field to a struct type, and suddenly you need to remember to update all the places you create this struct
encouraging bad programming by not forcing definition to go with declaration. This is particularly true in OCaml, say: there are no 0 values, so you always have to initialize your variables. Good imperative languages might allow var x = undefined; (or something like that) but should still warn you if a path tries to read before writing to the field.
nitpick: Go’s sync.Mutex has a perfectly valid and actually useful zero value: an unlocked mutex.
That said, I broadly agree with you; some types simply do not have a good default, and the best solution is not to fudge it and require explicit initialization.
@mndrix, note that there is a middle ground that gives you the best of both worlds: Haskell and Rust both have a Default type class/trait, that can be defined for types for which it does makes sense. Then you can just write
(in haskell):
let foo = def
in ...
(or rust):
let foo = Default::default();
Note you can even write this in Go, it just applies to more types than it should:
func Zero[T any]() T {
var ret T
return ret
}
// Use:
foo := Zero[T]()
You could well define some mechanism for restricting this to certain types, rather than just any. Unfortunately, it’s hard for me to see how you could retrofit this.
not always something that makes sense (what’s the 0 value for a file descriptor? an invalid file descriptor, is what. For a mutex? same thing.)
Partially agreed on a mutex (though on at least some platforms, a 0 value for a pthread mutex is an uninitialised, unlocked, mutex and will be lazily initialised on the first lock operation). If you bias your fd numbers by one then a 0 value corresponds to -1, which is always invalid and is a useful placeholder, but your example highlights something very important: the not-present value may be defined externally.
I saw a vulnerability last year that was a direct result of zero initialisation, of a UID field. A zero value on *NIX means root. If you hit the code path that accidentally skipped initialising the field properly, then the untrusted thing would run as root. Similarly, on most *NIX systems (all that I know of, though POSIX doesn’t actually mandate this), fd 0 is stdin, which is (as you point out) a terrible default.
Any time you’re dealing with an externally defined interface, there’s a chance that either there is no placeholder value or there is a placeholder value and it isn’t 0.
Agreed. However, my experience is that zero values are sensible for roughly 90% of types, and Go’s designers made the right Huffman coding decision here.
The criticism in a recent fasterthanlime article points this out well: Go makes up some weird rules about nil channels because it has to, instead of just… preventing channels from being nil ever.
For anyone who comes along later, I think this is the relevant fasterthanlime article. Anyway, the behavior of nil and closed channels is well-grounded in the semantics of select with message passing, and quite powerful in practice. For me, this argument ends up favoring zero values, for channels at least.
you add a field to a struct type, and suddenly you need to remember to update all the places you create this struct
My experience has been that they’d all be foo: 0 anyway. Although in practice I rarely use struct literals outside of a constructor function in Go (same with records in OCaml) because I inevitably want to enforce invariants and centralize how my values are created. In both languages, I only have to change one place after adding a field.
by not forcing definition to go with declaration
The definition there but it’s implicit. I guess I don’t see much gained by having repetitive = 0 on each declaration, like I often encounter in C.
I hope you’re not serious. I mean, sure, but it makes absolutely no sense whatsoever that leaving a variable uninitialized just means “use stdin” (if it’s still open).
File descriptor 0 is standard input on unix systems. (Unless you close it and it gets reused, of course, leading to fun bugs when code expects it to be standard input.)
As ludicrous as it would be, it would be a natural default value to have for careless language implementers, and before you know it users come to expect it. Even in C, static variables are all zero initialised and using one on read(2) would indeed read from standard input.
I’m sure we can point out various language quirks or weird idioms that started out that way.
Thing is, Go not only is statically typed, it is garbage collected.
As such, it is quite natural for it to use heap allocation for (almost) everything, and compensate for this with a generational GC. Now things get a little more complicated if they want to support natively sized integers (OCaml uses 31/62-bit integers to have one bit to distinguish them from pointers, so the GC isn’t confused), but the crux of the issue is that when you do it this way, generics become dead simple: everything is a pointer, and that’s it. The size of objects is often just irrelevant. It may sometime be a problem when you want to copy mutable values (so one might want to have an implicit size field), but for mere access, since everything are pointers size does not affect the layout of your containing objects.
This is quite different from C++ and Rust, whose manual memory management and performance goals kinda force them to favour the stack and avoid pointers. So any kind of generic mechanism there will have to take into account the fact that every type might have a different size, forcing them to go to a specialization based template, which may be more complex to implement (especially if they want to be clever and specialise by size instead of by type).
What’s clear to me is that Go’s designers didn’t read Pierce’s Type and Programming Languages, and the resulting ignorance caused them to fool themselves into thinking generics were complicated. No they aren’t. It would have taken a couple additional weeks to implement them at most, and that would have saved time elsewhere (for instance they wouldn’t have needed to make maps a built in type, and pushed that out to the standard library).
I have personally implemented a small scripting language to pilot a test environment. Plus it had to handle all C numeric types, because the things it tests were low level. I went for static typing for better error reporting, local type inference to make things easier on the user, and added an x.f() syntax and a simple type based static dispatch over the first argument to get an OO feel. I quickly realised that some of the functions I needed required generics, so I added generics. It wasn’t perfect, but it took me like 1 week. I know that generics are simple.
The reason the debate there is so one sided is because Go should have had generics for the start. The benefits are enormous, the drawbacks very few. It’s not more complex for users who don’t use generics, generic data structures can still be used as if they were built in, it hardly complicates the implementation, and it improves orthogonality across the board.
“LoL no generics” was the correct way to react, really.
It still seems to me that you are overconfident in this position. That’s fanboyism from my side, but Graydon certainly read TAPL, and if Graydon says “there’s a tradeoff between expressiveness and cognitive load” in the context of Go’s generics, it does seem likely that there’s some kind of tradeoff there. Which still might mean “LoL no generics” is the truth, but not via a one-sided debate.
Having covered meta issues, let me respond to specific points, which are all reasonable, but also are debatable :)
First, I don’t think the GC/no-GC line of argument holds for Go, at least in a simple form. Go deliberately distinguishes value types and pointer types (up to having a dedicated syntax for pointers), so “generics are easy ‘cause everything is a pointer” argument doesn’t work. You might have said that in Go everything should have been a pointer, but that’s a more complex argument (especially in the light of Java trying to move away from that).
Second, “It’s not more complex for users who don’t use generics,” – this I think is just in general an invalid line of argumentation. It holds in specific context: when you own the transitive closure of the code you are working with (handmade-style projects, or working on specific things at the base of the stack, like crypto libraries, alone or in a very small and tightly-knit teams). For “industrial” projects (and that’s the niche for Go) user’s simply don’t have the luxury of ignoring parts of the language. If you work on an average codebase with >10 programmers and >100k lines of code, the codebase will use everything which is accepted by the compiler without warnings.
Third, I personally am not aware of languages which solve generics problem in a low cognitive-load way. Survey:
C++ is obviously pretty bad in terms of complexity – instantiation-time errors, up-until-recently a separate “weird machine” for compile-time computations, etc.
Rust – it does solve inscrutable instantiation-time errors, but at the cost of far-more complex system, which is incomplete (waiting for GATod), doesn’t compose with other language features (async traits, const traits), and still includes “weird machine” for compile-time evaluation.
Zig. Zig is exciting – it fully and satisfactory solves the “weird machine” problem by using the same language for compile-time (including parametric polymorphism) and run-time computation. It’s also curious in that, as far as I understand, it also essentially “ignores TAPL” – there are no generics in the type system. It, however, hits “instantiation time errors” on the full speed. It seems to be that building tooling for such a language would be pretty hard (it would be anti-go in this sense). But yeah, Zig so far for me is one of the languages which might have solved generics.
Haskell – it’s a bit hard to discuss what even is the generics impl in Haskell, as it’s unclear which subset of pragmas are we talking about, but I think any subset generally leads to galactic-brain types.
OCaml – with questionable equality semantics, and modular implicit which are coming soon, I think it’s clear that generics are not solved yet. It also has a separate language for functors, which seems pretty cognitively complex.
Scala – complexity-wise, I think it’s a super-set of both Haskell and Java? I don’t have a working memory of Scala to suggest specific criticisms, but I tend to believe “Scala is complex” meme. Although maybe it’s much better in Scala 3?
Java – Java’s type system is broken in a trivial way (covariant arrays) and a (couple of?) interesting way (they extended type-inference when they added lambdas, and that inference allowed materialization of some un-denotable types which break the type system). I am also not sure that its “LoL covariant arrays”, as some more modern typed languages also make this decision, citing reduction of cognitive load. And variance indeed seems to be quite complex topic – Effective Java (I think?) spends quite some pages explaining “producer extends, consumer super”.
C# – I know very little about C#, but it probably can serve as a counter example for “generics in GC languages are simple”. Like Go, C# has value types, and, IIRC, it implements generics by just-in-time monomorphisation, which seems to be quite a machinery.
Now, what I think makes these systems complicated is not just parametric polymorphism, but bounded quantitication. The desire to express not only <T>, but <T: Ord>. Indeed, to quote TAPL,
This chapter introduces bounded quantification, which arises when polymorphism and subtyping are combined, substantially increasing both the expressive power of the system and its metatheoretic complexity.
I do think that there’s an under-explored design space of non-bounded generics, and very much agree with @c-cube . I am not quite convince that it would work and that Go should have been SML without functors and with channels, but that also doesn’t seem obviously worse than just three generic types! The main doubt for me is that having both interfaces and unbounded generics feels weird. But yeah, once I have spare time for implementing a reasonable complete language, unbounded generics is what I’d go for!
Ah. that’s one hypothesis down then. Thanks for the correction.
It holds in specific context: when you own the transitive closure of the code you are working with (handmade-style projects, or working on specific things at the base of the stack, like crypto libraries, alone or in a very small and tightly-knit teams). For “industrial” projects (and that’s the niche for Go) user’s simply don’t have the luxury of ignoring parts of the language. If you work on an average codebase with >10 programmers and >100k lines of code, the codebase will use everything which is accepted by the compiler without warnings.
OK, while I do have some experience with big projects, my best work by far was in smaller ones (including my crypto library, which by the way did not even need any generics to implement). What experience I do have with bigger projects however have shown me that most of the time (that is, as long as I don’t have to debug something), the only pieces of language I have to care about are those used for the API of whatever I’m using. And those tend to be much more reasonable than whatever was needed to implement them. Take the C++ STL for an extreme example: when was the last time you actually specified the allocator of a container? Personally I’ve never done it in over 10 years being paid to work with C++.
I personally am not aware of languages which solve generics problem in a low cognitive-load way
I have written one. Not public, but that language I’ve written for test environments? It had generics (unbounded, no subtyping), and I didn’t even tell my users. I personally needed them to write some of the functions of the standard library, but once that was done, I thought users would not really need them. (Yeah, it was easier to add full blown generics than having a couple ad-hoc generic primitives.)
Now, what I think makes these systems complicated is not just parametric polymorphism, but bounded quantitication. The desire to express not only <T>, but <T: Ord>.
Yeah, about subtyping…
In the code I write, which I reckon has been heavily influenced by an early exposure to OCaml (without the object part), I almost never use subtyping. Like, maybe 3 or 4 times in my entire career, two of which in a language that didn’t have closures (C++98 and C). If I design a language for myself, subtyping will be way down my list of priorities. Generics and closures will come first, and with closures I’ll have my poor man’s classes in the rare cases I actually need them. Even in C I was able to add virtual tables by hand that one time I had to have subtype polymorphism (It’s in my crypto library, it’s the only way I found to support several EdDSA hashes without resorting to a compilation flag).
I’ve heard of subtyping being successfully used elsewhere. Niklaus Witrth took tremendous advantage of it with its Oberon programming language and operating system. But I believe he didn’t have parametric polymorphism or closures either, and in this case I reckon subtyping & class based polymorphism are an adequate substitute.
Type classes (or traits) however are really enticing. I need more practice to have a definite opinion on them, though.
Ah. that’s one hypothesis down then. Thanks for the correction.
To clarify, graydon, as far as I know, didn’t participate in Go’s design at all (he designed Rust), so this has no bearing on your assumption about designers of Go.
Generics are simple under a critical condition: Design them from the ground up
Done after the fact in a system not designed for them, of course they’re going to be difficult. Then again, why waste a couple weeks of up front design when you can afford years of waiting and months of pain?
I don’t agree that generics are simple, but I agree that designing them in from the start is vastly easier than trying to retrofit them to an existing language. There are a lot of choices in how generics interact with your type system (especially in the case of a structural type system, which Go has, and even more so in an algebraic type system). If you build generics in as part of your type system from the start then you can explore the space of things allowed by generics and the other features that you want. If you don’t, then you may find that the point that you picked in the space of other things that you want is not in the intersection of that and generics.
I kinda had to change my mind on that one. Generics can be very simple in some contexts (like my own little language), but I see now that Go wasn’t one of them.
If you build generics in as part of your type system from the start then you can explore the space of things allowed by generics and the other features that you want. If you don’t, then you may find that the point that you picked in the space of other things that you want is not in the intersection of that and generics.
One thing I take for granted since I went out of college in 2007, is that we want generics. If your language is even slightly general purpose, it will need generics. Even my little specialised language, I didn’t plan to add generics, but some functions in my standard library required it. So this idea of even attempting to design a language without generics feels like an obvious waste of time to me. Likewise for closures and sum types by the way.
There is one thing that can make me change my mind: systematic experimentation for my niche of choice. I design my language, and I write a real program with it, trying to use as few features as possible. For instance, my experience in writing a cryptographic library in C convinced me they don’t need generics at all. Surprisingly though, I did see a case for subtype polymorphism, in some occasions, but that happens rarely enough that an escape hatch like writing your vtable by hand is good enough. I believe Jonathan Blow is doing something similar for his gaming language, and Niklaus Wirth definitely did the same for Pascal (when he devised Modula and Oberon).
One thing I take for granted since I went out of college in 2007, is that we want generics. If your language is even slightly general purpose, it will need generics
I completely agree here. I wrote a book about Go that was finished just after Go reached 1.0 and, even then, I thought it was completely obvious that once you’ve realised that you need generic maps you should realise that you will need other generic types. Having maps (and arrays and slices) as special-case generics felt like a very bad decision.
Mind you, I also thought that having a language that encouraged concurrency and made data races undefined behaviour, but didn’t provide anything in the type system to allow you to define immutable types or to limit aliasing was also a terrible idea. It turns out that most of the folks I’ve spoken to who use Go use it as a statically compiled Python replacement and don’t use the concurrency at all. There was a fantastic paper at ASPLOS a couple of years back that looked at concurrency bugs in Go and found that they are very common.
I think Oberon and Go have a lot in common. Both were designed by an experienced language constructor late in his career, emphasising “simplicity” over everything else, leaving out even basic things such as enums, even though he had created more expressive languages earlier on.
I tend to be more sympathetic to Wirth’s decisions, because he was working in a closed ecosystem he completely controlled and understood. I mean, they were like less than 5 people working on the entire OS + compiler + main applications, and in the case of the Lilith computer, and FPGA Oberon, even the hardware!
He could have criteria such as “does this optimisation makes the entire compiler bootstrap faster? Here it’s for speed, but I can see the idea that every single piece of complexity has to pay for itself. It was not enough for a feature to be beneficial, the benefits had to outweigh the costs. And he could readily see when they did, because he could fit the entire system in his head.
Go is in a different situation, where from the start it was intended for a rather large audience. Thus, the slightest benefit to the language, even if it comes at a significant up-front cost, is liable to pay huge dividends as it becomes popular. So while I can believe even generics may not be worth the trouble for a 10K LOC system (the size of the Oberon system), that’s a different story entirely when people collectively write hundreds of millions of lines of code.
While Go is garbage collected, it is still very much “value oriented” in that it gives control to the programmer for the layout of your memory, much like C++ and Rust. Just making everything a pointer and plugging your ears to the issues that brings isn’t solving the problem.
I’m glad that you added generics to your small scripting language for a test environment in 1 week. I don’t think that speaks much to the difficulty in adding it to a different language with a different type system and different goals. When they started the language, things like “very fast compile times” where very high priority, with the template system of C++ generics heavily inspiring that goal. It would be inane to start a project to avoid a problem in a language and then cause the exact same problem in it.
So, they didn’t want to implicitly box everything based on their experience with Java, and they didn’t want to template everything based on their experience with C++. Finding and implementing a middle ground is, in fact, difficult. Can you name any languages that avoid the problems described in https://research.swtch.com/generic?
The problem with “lol no generics” is that the word “generics” sweeps the whole elephant under the rug. There are a fractal of decisions to make when designing them with consequences in the type system, runtime, compiler implementation, programmer usability, and more. I can’t think of any languages that have the exact same generics system. Someone who prefers Rust generics can look at any other language and say “lol no traits”, and someone who prefers avoiding generics entirely (which, I promise, is a reasonable position to hold) may look around and say “lol 2 hour compile times”. None of those statements advance any conversation or are a useful way to react.
I can’t think of any languages that have the exact same generics system. Someone who prefers Rust generics can look at any other language and say “lol no traits”,
While Go is garbage collected, it is still very much “value oriented” in that it gives control to the programmer for the layout of your memory, much like C++ and Rust.
That kind of changes everything… Oops. (Really, I mean it.)
When they started the language, things like “very fast compile times” where very high priority, with the template system of C++ generics heavily inspiring that goal.
Several things conspire to make C++ compile times slow. The undecidable grammar, the complex templates, and the header files. Sure we have pre-compiled headers, but in general, those are just copy pasta that are being parsed and analysed over and over and over again. I’ve seen bloated header-only libraries add a full second of compilation time per .cpp file. And it was a logging library, so it was included everywhere. Properly isolating it solved the problem, and the overhead was reduce to one second for the whole project.
A simpler grammar is parsed basically instantly. Analysis may be slower depending on how advanced static checks are, but at least in a reasonable language it only has to happen once. Finally there’s code generation for the various instantiations, and that may take some time if you have many types to instantiate. But at least you don’t have to repeat the analysis, and the most efficient optimisations don’t take that much compilation time anyway.
The undecidable grammar, the complex templates, and the header files. Sure we have pre-compiled headers, but in general, those are just copy pasta that are being parsed and analysed over and over and over again.
The parsing and analysis isn’t the whole problem. The C++ compilation model is an incremental evolution of Mary Allen Wilkes’ design from the ’70s, which was specifically designed to allow compiling complex problems on machines with around 2 KiB of memory. Each file is compiled separately and then pasted together in a completely separate link phase. In C++, inline and templated functions (including methods on templated classes) are emitted in every compilation unit that uses them. If 100 files use std::vector<int>::push_back then 100 instances of the compiler will create that template instantiation (including semantic analysis), generate IR for it, optimise it, and (if they still have calls to it left after inlining) spit out a copy of it in a COMDAT in the final binary. It will then be discarded at the end.
Sony has done some great work on a thing that they call a ‘compilation database’ to address this. In their model, when clang sees a request for std::vector<int>::push_back, it queries a central service to see if it’s already been generated. It can skip the AST generation and pull the IR straight from the service. Optimisers can then ignore this function except for inlining (and can provide partially optimised versions to the database). A single instance is emitted in the back end. This gives big compile time speedups, without redesigning the language.
It’s a shame that the Rust developers didn’t build on this model. Rust has a compilation model that’s more amenable to this kind of (potentially distributed) caching than C++.
I meant back when Go first came out. That was over 12 years ago, in 2009. This paper is from 2020.
Nevertheless, the present thread significantly lowered my confidence in that claim. I am no longer certain Go designers failed to read Pierce’s work or equivalent, I now merely find it quite plausible.
What’s clear to me is that Go’s designers didn’t read Pierce’s Type and Programming Languages . . .
Do you really think that Ken Thompson, Rob Pike, and Robert Greisemer were ignorant to this degree? That they made the design decisions they did based on a lack of theoretical knowledge?
None of them is known for statically typed functional languages, and I know for a fact there is little cross talk between that community and the rest of the world. See Java, designed in 1995, twenty years after ML showed the world not only how to do generics, but how neat sum types are. Yet Java’s designers chose to have null instead, and generics came only years later. Now I kinda forgive them for not including generics at a time they likely believed class based polymorphism would replace parametric polymorphism (a.k.a. generics), but come on, adding null when we have a 20 year old better alternative out there?
So yeah, ignorance is not such an outlandish hypotheses, even with such people.(Edit: apparently one of them did read TAPL, so that should falsify the ignorance hypothesis after all.)
But that’s not my only hypothesis. Another possibility is contempt for their users. In their quest for simplicity, they may have thought the brains of Go programmers would be too weak to behold the frightening glory of generics. That instead they’d stay in the shelter of more familiar languages like Python or C. I’m not sure how right they may have been on that one to be honest. There are so many people that don’t see the obvious truth that programming is a form of applied maths (some of them explicitly fled maths), that I can understand they may panic at the first sight of an unspecified type. But come on, we don’t have to use generics just because they’re there. There’s no observable difference between a built in map and one that uses generics. Users can use the language now, and learn generics later. See how many people use C++’s STL without knowing the first thing about templates.
Yet another hypothesis is that they were in a real hurry, JavaScript style, and instead of admitting they were rushed, they rationalised the lack of generics like it was a conscious decision. Perhaps they were even told by management to not admit to any mistake or unfinished job.
But that’s not my only hypothesis. Another possibility is contempt for their users.
…
Yet another hypothesis is that they were in a real hurry, JavaScript style, and instead of admitting they were rushed, they rationalised the lack of generics like it was a conscious decision. Perhaps they were even told by management to not admit to any mistake or unfinished job.
This is exhausting and frustrating. It’s my own fault for reading this far, but you should really aim for more charity when you interpret others.
The key point here is our programmers are Googlers, they’re not researchers. They’re typically, fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt.
Ah, I didn’t remember that quote, thank you. That makes the contempt hypothesis much more plausible.
That being said, there’s a simple question of fact that is very difficult to ascertain: what the “average programmer” is capable of understanding and using, and at what cost? I personally have a strong intuition that generics don’t introduce unavoidable complexity significant enough to make people lives harder, but I’m hardly aware of any scientific evidence to that effect.
We need psychologists and sociologists to study is.
I’ve ran out of charitable interpretations to be honest. Go designers made a mistake, plain and simple. And now that generics have been added, that mistake has mostly been fixed.
I’m surprised you’re saying this after noticing that you didn’t know basic things about Go’s type system and implementation and learning those details “changes everything” (which, in my opinion, is commendable). Indeed, you’ve also apparently learned many facts about the authors and their history in this thread. Perhaps this is a good moment to be reflective about the arguments you’re presenting, with how much certainty you’re presenting them, and why.
I still think that omitting generics from a somewhat general purpose language past 2005 or so is a mistake. The benefits are just too large.
I’ve seen comments about how the standard library itself had to jump through some hoops that wouldn’t be there if Go had generics from the start. So Go authors did have some warning.
Go now has generics, even though adding them after the fact is much harder. There can be lots of reasons for this change, but one of them remains an admission of guilt: “oops we should have added generics, here you are now”.
So yeah, I still believe beyond reasonable doubt that omitting generics back then was a mistake.
All of your “analyses” are rooted in a presumption of ignorance, or malice, or haughty superiority, or some other bad-faith foundation. Do you really thing that’s the truth of the matter?
There are so many people that don’t see the obvious truth that programming is a form of applied maths
Some programming is a form of applied math. Most programming, as measured by the quantity of code which exists and is maintained by human beings, is not. Most programming is the application of computational resources to business problems. It’s imperative, it’s least-common-denominator, and it’s boring.
All of your “analyses” are rooted in a presumption of ignorance, or malice, or haughty superiority, or some other bad-faith foundation. Do you really thing that’s the truth of the matter?
The only way it’s false is if omitting generics was the right thing to do. I don’t believe that for a second. It was a mistake, plain and simple. And what could possibly cause mistakes, if not some form of incompetence or malice?
Most programming is the application of computational resources to business problems. It’s imperative, it’s least-common-denominator, and it’s boring.
It’s also maths. It’s also the absolutely precise usage of a formal notation that ends up being transformed into precise instructions for an (admittedly huge) finite state machine. Programs are still dependency graphs, whose density is very important for maintainability — even the boring ones.
It’s not the specific kind of maths you’ve learned in high school, but it remains just as precise. More precise in fact, given how unforgiving computers are.
The only way it’s false is if omitting generics was the right thing to do. I don’t believe that for a second.
“The right thing to do” is a boolean outcome of some function. That function doesn’t have a a single objective definition, it’s variadic over context. Can you not conceive of a context in which omitting generics was the right thing to do?
Designing a language before Y2K. Past 2005, it is too easy to know about them to ignore them.
Addressing a specific niche for which generics don’t buy us much.
Generics are too difficult to implement.
Users would be too confused by generics.
Other features incompatible with generics are more important.
Go was designed too late for (1) to fly with me, and it is too general purpose for (2). I even recall seeing evidence that its standard library would have significantly benefited from generics. I believe Rust and C++ have disproved (3) despite Go using value types extensively. And there’s no way I believe (4), given my experience in OCaml and C++. And dammit, Go did add generics after the fact, which disavows (4), mostly disproves (3), and utterly destroys (5). (And even back then I would have a hard time believing (5), generics are too important in my opinion.)
So yeah, I can come up with various contexts where omitting generics is the right think to do. What I cannot do is find one that is plausible. If you can, I’m interested.
[Go] is too general purpose for (2). I even recall seeing evidence that its standard library would have significantly benefited from generics.
You don’t need to speculate about this stuff, the rationale is well-defined and recorded in the historical record. Generics were omitted from the initial release because they didn’t provide value which outweighed the cost of implementation, factoring in overall language design goals, availability of implementors, etc. You can weight those inputs differently than the authors did, and that’s fine. But what you can’t do is claim they were ignorant of the relevant facts.
I believe Rust and C++ have disproved (3)
A language is designed as a whole system, and its features define a vector-space that’s unique to those features. Details about language L1 don’t prove or disprove anything about language L1. The complexity of a given feature F1 in language L1 is completely unrelated to any property of that feature in L2. So any subjective judgment of Rust has no impact on Go.
Go did add generics after the fact, which disavows (4), mostly disproves (3), and utterly destroys (5).
Do you just not consider the cost of implementation and impact on the unit whole as part of your analysis? Or do you weight these things so minimally as to render them practically irrelevant?
Generics did not materially impact the success of the goals which Go set out to solve initially. Those goals did not include any element of programming language theory, language features, etc., they were explicitly expressed at the level of business objectives.
You don’t need to speculate about this stuff, the rationale is well-defined and recorded in the historical record.
What record I have read did not convince me. If you know of a convincing article or discussion thread, I’d like to read it. A video would work too.
I believe Rust and C++ have disproved (3)
A language is designed as a whole system […]
I picked Rust for a specific reason: manual memory management, which means value types everywhere, and the difficulties they imply for generics. That said, I reckon that Go had the additional difficulty of having suptyping. But here’s the thing: in a battle between generics and subtyping, if implementing both is too costly, I personally tend to sacrifice subtyping. In a world of closures, subtyping and suptype polymorphism simply are not needed.
Do you just not consider the cost of implementation and impact on the unit whole as part of your analysis?
I’m not sure what you mean there… I think pretty much everyone agrees that designing and implementing generics up front is much easier than doing so after the fact, in a system not designed for them. If the Go team/community were able to shoulder the much higher cost of after-the-fact generics, then they almost certainly could have shouldered the cost of up-front generics back then —even though the team was much smaller.
Generics did not materially impact the success of the goals which Go set out to solve initially.
Well if they just wanted to have a big user base, I agree. The Google brand and the reputation of its designers did most of that work. As for real goals, they’re the same as any language: help the target audience write better programs for cheaper in the target niche. And for this, I have serious doubts about the design of Go.
Now as @xigoi pointed out, Go authors targetted noobs. That meant making the language approachable by people who don’t know the relevant theory. That didn’t mean making the language itself dumb. Because users can’t understand your brilliant language doesn’t mean they won’t be able to use it. See every C++ tutorial ever, where you’re introduced to its features bit by bit. For instance when we learn I/O in C++ we don’t get taught about operator overloading (<< and >> magically work on streams, and we don’t need to know why just yet). Likewise we don’t learn template meta programming when we first encounter std::vector.
People can work with generics before understanding them. They won’t write generic code just yet, but they absolutely can take advantage of already written code. People can work with algebraic data types. They won’t write those types right away, but they can absolutely take advantage of the option type for the return value of functions that may fail.
A language can be brilliant and approachable. Yet Go explicitly chose to be dumb, as if it was the only way to be easy to work with. Here’s the thing though: stuff like the lack of generics and sum types tends to make Go harder to work with. Every time someone needed a generic data structure, they had to sacrifice type safety and resort to various conversion to and from the empty interface. Every time someone needs to report failures to the caller, they ended up returning multiple values, making things not only cumbersome, but also fairly easy to miss —with sum types at least the compiler warns you when you forget a case.
It’s all well and good to design a language for other people to use, but did they study the impact of their various decision on their target audience? If I’m writing a language for myself I can at least test it on myself, see what feels good, what errors I make, how fast I program… and most of my arguments will be qualitative. But if I’m writing for someone else, I can’t help but start out with preconceived notions about my users. Maybe even a caricature. At some point we need to test our assumptions.
Now I say that, such studies are bloody expensive, so I’m not sure what’s the solution there. When I made my little language, I relied on preconceived notions too. We had the requirements of course, but all I knew wast that my users weren’t programmers by trade. So I made something that tries its best to get out of their way (almost no explicit typing by default), and reports errors early (static typing rules). I guess I got lucky, because I was told later that they were happy with my language (and home grown languages have this reputation for being epically unusable).
But here’s the thing: in a battle between generics and subtyping, if implementing both is too costly, I personally tend to sacrifice subtyping. In a world of closures, subtyping and suptype polymorphism simply are not needed.
Do you consider generics and subtyping and polymorphism and other programming language properties means to an end, or ends in themselves?
In the programs I write, I need inheritance or subtyping maybe once a year. Rarely enough that using closures as a poor’s man classes is adequate. Heck, even writing the odd virtual table in C is enough in practice.
Generics however were much more useful to me, for two purposes: first, whenever I write a new data structure or container, it’s nice to have it work on arbitrary data types. For standard libraries it is critical: you’ll need what, arrays & slices, hash tables, maybe a few kind of trees (red/black, AVL…).
I don’t write those on a day to day basis, though. I’ve also grown susceptible to Mike Acton’s arguments that being generic often causes more problems than it solves, at least when speed matters. One gotta shape one’s program to one’s data, and that makes generic data structures much less useful.
My second purpose is less visible, but even more useful: the right kind of generics help me enforce separation of concerns to prevent bugs. That significantly speeds up my development. See, when a type is generic you can’t assume anything about values of that type. At best you can copy values around. Which is exactly what I’m looking for when I want to isolate myself from that type. That new data structure I’m devising just for a particular type? I’m still going to use generics if I can, because they make sure my data structure code cannot mess with the objects it contains. This drastically reduces the space of possible programs, which is nice when the correct programs are precisely in that space. You can think of it as defining bugs out of existence, like Ousterhout recommends in A Philosophy of Software Design.
Languages like C# or Java took this further and make sure that all objects have GetHashCode() and Equals() methods, specifically to support the hash table scenario. It is that important.
That is not exactly why these languages have these features. They have these features because they do not expose a mechanism for capturing object identity. In C, you can cast a pointer to an address-sized integer and have a unique identifier that corresponds to the object. You can then do any integer operations on this value, whether it’s hashing, ordered comparison, or whatever. In a language that permits moving garbage collectors, you cannot use the memory location of the objects as identity and so you need something else. The default implementation of hashCode typically returns the address of the object the first time it’s called and sets a flag in the header so that it can be cached in a larger header if the object is moved.
Capturing of object identity is done using == and System.identityHashCode (in java). equals and hashcode are there specifically so that they can be overridden; if that were not the case, there would be no need to make them user-overrideable methods. The operations which are exposed which are dedicated to identity are not user-overrideable, with good reason.
I think one of the interesting properties of Hare s that it’s C semantics/programming model with some minimal additions that make it nicer to use than C. I don’t think I’m sold (I’m happy with Rust, which I think makes me not the target for something like Hare) but it’s certainly an interesting take.
This post and some of the HN discussion just felt like flame bait, a kind of disingenuous look at the project. It’s like trying to write a circularly linked list in Rust and deciding “Rust sucks, it will never catch on without cyclic data structures!” Sure that feature has value, but making it easy to use doesn’t align with the rest of the project.
A: “You can’t even get this data structure right in a 600-word blog post! FAIL.”
B: “Hash tables are easy! Just roll your own if you can’t figure out how to do everything with slices and structs like Kernighan intended.”
Me: “Um, programming is hard and I don’t like being told that liking a robust stdlib is wrong any more than I like seeing people dunk on someone else instead of trying to glean the intent and ideas behind a new tool.”
That’s just an artifact of a couple of days of posting–give it a month or two and see if a whole bunch more articles are posted. At that point, use a meta thread to ask for the tag.
This has shown up on the orange site as well and I’m… a little baffled by the discussions there, and by the article itself, too. I’m kind of going through a bit of an “am I getting grumpy and obsolete and not getting how programming is done anymore?” phase so this hits a little close to home…
I mean, this whole criticism is centered around one buggy implementation of a hash table, mostly related to a poor choice of algorithm and a few oversights, such as key collisions. Any approach to generics can run into these problems. I can write exactly the same code in Rust using generics and it will have exactly the same problems – except, I guess, since my
BuggyHashMapis now aBuggyHashMap<K: Eq + HashFNV32, V>or whatever, I will be able shoot myself in the foot in several places, using a wide variety of bullets.Providing a particular abstraction (or not!) is a trade-off like all others. It’s not like C++ or Rust’s approach to generics and their use in the standard library are “free”. You pay for them with compiler complexity, tortuous long-term evolution due to standard library size (also development effort – remember the
get_temporary_bufferfiasco?), and extra difficulties in reasoning about performance in more complex cases.In fact, as the author otherwise points out, “there isn’t just a hash table algorithm, the details matter. A lot. “ Maybe the folks behind Hare figured that, for the applications they’re targeting, you either have modest performance requirements, in which case any naive (but bug-free) implementation you copy-paste off StackOverflow is fine, or you have high performance requirements, in which you’re likely going to end up employing black hashing magic anyway so you might as well write the rest of the boilerplate, too.
I’m not saying I agree with them – I don’t know what they intend to do with Hare and what kind of programming it’s meant to facilitate, so I really wouldn’t know where to begin agreeing or disagreeing (edit, FWIW I’m sort of suspect @Corbin is right here but let’s give Hare the benefit of the doubt, eh?). But I have a feeling they may have a better grasp of what’s relevant for their project than some random Internet person. Either way, while it may be the wrong trade-off to make (and, okay, I have so many
void *-induced nightmares that I don’t really want to put up with a language that doesn’t have generics, so I’m more than willing to entertain the idea that it is the wrong trade-off to make in 2022), it may be worth at least acknowledging that it is a trade-off.The author is also making some… overly-general, I guess (I was gonna say weird) claims about C, like:
The most natural data structure for what? I’ve written a lot of C over the years (embedded development is like that, sadly…) and while I’m anything but enthusiastic about C (or anything that isn’t Ada for that matter, shh!) I can’t think of a single case where I ended up using a linked list even though a hash table would’ve been better. When you need a hash table, you bring in a hash table – sure, it’s not trivial, but there are plenty of non trivial things in other languages as well. It’s not very productive to dwell on this one particular case.
Pretty sure this entire post was meant to rag on Drew a bit, as he is known for ragging on others.
In my experience hes a nice guy but also quite focused and direct. I think its a bit unfair to perpetuate third party criticisms past their use by.
Right, if that’s the case, it is very likely that I have misunderstood it, my memories about my behaviour around the ripe age of nine are thankfully somewhat dim.
I think one of the things that Go got right is figuring out what the core data types needed for a modern language are. I wrote this in 2013, and I think it holds up:
I think a lot of people would like to add Optional/Maybe and sum types to that list of core data types. In any event, you’re going to get pushback if you try to release a new language without an easy way to create those types.
What’s wrong with providing them in the standard library, without special syntax?
Even C has special syntax for strings and arrays (considering that strings in C are just 0-terminated character arrays, it could have done without string literals). I think Kotlin has it only for strings, but it makes the code more verbose.
You could provide hash tables via the standard library, I guess, but I don’t see how you could possible do strings or arrays without some special syntax.
A couple of minor nits, given because the author kinda asks for them…
URL query strings are not guaranteed to have a 1-1 mapping between keys and values, as [there is nothing in the RFC suggesting that there should be(https://www.rfc-editor.org/rfc/rfc3986#section-3.4). In the wild, especially with forms and things (IIRC) you’ll run into duplicate keys, the interpretation of which is up to the stack. Saying “just shove it all into a hashmap” is ignorant of the problem domain, unless you specify how you mean to use that map.
There isn’t a standard library in C for linked-lists, as far as I remember, and the number of bugs due to incorrect hand-rolled implementations of linked-lists I think probably far outstrip the number of bugs due to bad hahtable implementations.
It’s not easy to get them perfect, and quite tricky to get them really performant in the general case, but in my experience implementing a basic hashmap isn’t something you need a PhD and FANG money to do. The author then immediately appeals to authority by linking a bunch of CppCON talks, and given my experience with hashmaps comes directly from reimplementing them due to the super neat EASTL whitepaper and the lack of a good cross-platform
unordered_mapin the standard library between the GCC and MSVC ecosystems at the time…yeah, I call bullshit.Plainly: Stop gatekeeping datastructures bro.
The context the author cheerfully leaves out, from the article he’s attempting to lambast, is that they needed a one-off special-case hashmap for some little fiddly bit of code and they built a really barebones one that exactly fit their usecase. In the original article, DDV explicitly says “Yeah, we picked 64 buckets because it was enough, yeah we could’ve done dynamic rehashing if we needed to, meh this is Good Enough”.
The author is complaining about a one-off implementation because it isn’t a high-performance generalized standard library package developed over decades (as it is in other languages), and I guess I’d say…that isn’t the point. If profiling reveals that routine to be a true bottleneck in their code, they’ll probably update the hashmap or hash function when that day comes, but they’ve got a lot of ground to cover in developing the foundations of Hare without spending time polishing a data structure.
I think there are valid criticisms of the language and process, but this whole article didn’t strike me as having pretty much any of them.
The author is complaining because this basic hashmap is not even correct as it doesn’t handle collisions. It also doesn’t implement deletion.
Also, if performance isn’t that important and you can do with crappy hashmaps and the likes… Why write in a C-like language? Why do manual allocations? Why not use a GC and better building blocks? That’s what gets me, personally.
Does it need to handle collisions or deletions in its current usage? Is that a requirement of how it is being used?
For deletion, probably not. For collisions, my understanding is that the collision would be handled silently (on lookup), so it’s hard to argue that this is correct behavior. Unless you like playing russian roulette with your module names.
I kind of feel that the author, intent on proving a point, himself misses the entire point of Hare as a language
Well, the author is being polite. The point of Hare is to aggrandize its inventor.
I have mercilessly flagged rants and sourcehut spam, as well as gotten into slapfights with Drew here. Believe me when I say, without any love or affection for the fellow, that I’m pretty sure your take here is wrong.
Oof. You’ve now convinced bunch of onlookers never to share their projects here. Aren’t we all here to learn new things via sharing?
I’m genuinely curious how you arrived that conclusion.
Corbin doesn’t like Drew
I hope ad hominem attacks don’t become the norm here.
Working hard on something for years is the best way to aggrandize yourself. Shit posting on the other hand…
baseeither.Haskell doesn’t have hashmaps in base, but the tools that haskell gives you to implement maps are so powerful that it makes them easy. With hare you have to draw the rest of the owl. Some people do like drawing the rest of the owl though.
:shrugs: I cannot imagine using a language without generics. Even in C one frequently ends up emulating vtables or passing comparators manually and so on. But the arguments in the article were lacking.
Is in the Prelude I think, and works well until you need performance. I mostly use Haskell for research code (read: not performance intensive) and you’d be surprised how far list-based maps take you.
Is that like an alist (association list) in Lisp?
Yes, it looks like it.
Yes, the tuple
(a, b)represents a key paired with a value (equal to Lisp’s'(a . b)), and the[ ]brackets imply a Cons list. The alist is linear and insert/append/removes are still very much O(n).Data.Map implements a hash-map-like balanced tree, and is simple to implement on your own (if you like writing trees in Haskell, that is).
Language with first public release does not have put as much thought and research into a data structure as the language ecosystem that often claims to be the #1. News at 11.
That is not me defending Hare but I didn’t like the tone of this post either.
Perhaps I’m wrong but it seems that the arguments made in this article contradict themselves. The Hare blog post is quoted as saying:
The author seems to take issue with this statement but then to disprove the claim that hash maps are simple to implement he states this:
That statement seems perfectly consistent with the statement made by the Hare blog post, in other words, the specific implementation of hash map matters a lot for your particular application.
In the C tradition, I agree with Hare’s claim that a robust standard open addressing hash table (as a specific implementation of a hash map) is relatively straightforward to build. The complexity tends to be in the design of the hash function, which would be the case even if Hare provided a standard library hash table.
I don’t really agree that maps are a basic data structure, and I think the amount of C++ implementations and comparisons linked in the author’s post proves that. They are widely used and providing a “good enough in most cases” implementation like Go does would probably be useful, but I wouldn’t say it’s necessary in a language as barebones as Hare. And it would require the language to have some form of generics (which should’ve been in from the start, imo) or some compiler magic like Go did with map[].
I’ve personally never written a nontrivial program which didn’t make use of a map-like data structure.
Many C programs often use a singly linked list for n < ~10 - that usually performs very well, a lookup is often only 10 comparisons which is probably pretty close to the cost of running a hash function anyway… I need to run a benchmark.
I have seen compilers do this - its quite common to have fewer than 10 variables in a scope. It’s still a map, but for many human scale problems a hash map doesn’t matter.
C does not provide maps, and when I really need one I can implement it in less than 200 lines (won’t be generic, though). Were I to design a language like Hare or Zig, providing an actual (hash) map implementation would be way down my list of priorities. Even if it belongs in the standard library, my first order of business would be to make sure we can implement that kind of things.
In fact, Go made a mistake when it provided maps directly without providing general purpose generics. That alone hinted at a severe lack of orthogonality. If maps have to be part of the core language, that means users can’t write one themselves. Which means they probably can’t write many other useful data structures. As Go authors originally did, you could fail to see that if the most common ones (arrays, hash tables…) are already part of the core language.
The most important question is not whether your language has maps. It’s whether we can add maps that really matters. Because if we can’t, there’s almost certainly a much more serious root cause, such as the lack of generics.
I think this is too a one-sided debate. Generics have benefits and drawbacks (to argument from authority, see https://nitter.net/graydon_pub/status/1036279571341967360).
Go’s original approach of providing just three fundamental generic data structures (vec, map, and chan) definitely was a worthwhile experiment in language design, and I have the feeling that it almost worked.
At this point I’d argue that the benefits of even the simplest version of generics (not bounded, template-style or ML-functor-style, whatever) are so huge compared to the downsides, that it’s just poor design to create a new statically typed language without them. It’s almost like creating a language without function calls.
Go finally fixed that — which doesn’t fix all the other design issues like zero values or lack of sum types — but their initial set of baked-in generic structures was necessary to make the language not unbearable to use. If they hadn’t baked these in, who would use Go at all?
Could you share more here? I agree about Go generics, but its zero values are one thing I miss when using other imperative languages. They’re less helpful in functional languages, but I even miss zero values when using OCaml in an imperative style.
Zero values are:
var x = undefined;(or something like that) but should still warn you if a path tries to read before writing to the field.nitpick: Go’s sync.Mutex has a perfectly valid and actually useful zero value: an unlocked mutex.
That said, I broadly agree with you; some types simply do not have a good default, and the best solution is not to fudge it and require explicit initialization.
@mndrix, note that there is a middle ground that gives you the best of both worlds: Haskell and Rust both have a
Defaulttype class/trait, that can be defined for types for which it does makes sense. Then you can just write(in haskell):
(or rust):
Note you can even write this in Go, it just applies to more types than it should:
You could well define some mechanism for restricting this to certain types, rather than just
any. Unfortunately, it’s hard for me to see how you could retrofit this.Thank you for the correction!
Partially agreed on a mutex (though on at least some platforms, a 0 value for a pthread mutex is an uninitialised, unlocked, mutex and will be lazily initialised on the first lock operation). If you bias your fd numbers by one then a 0 value corresponds to -1, which is always invalid and is a useful placeholder, but your example highlights something very important: the not-present value may be defined externally.
I saw a vulnerability last year that was a direct result of zero initialisation, of a UID field. A zero value on *NIX means root. If you hit the code path that accidentally skipped initialising the field properly, then the untrusted thing would run as root. Similarly, on most *NIX systems (all that I know of, though POSIX doesn’t actually mandate this), fd 0 is stdin, which is (as you point out) a terrible default.
Any time you’re dealing with an externally defined interface, there’s a chance that either there is no placeholder value or there is a placeholder value and it isn’t 0.
Agreed. However, my experience is that zero values are sensible for roughly 90% of types, and Go’s designers made the right Huffman coding decision here.
For anyone who comes along later, I think this is the relevant fasterthanlime article. Anyway, the behavior of nil and closed channels is well-grounded in the semantics of
selectwith message passing, and quite powerful in practice. For me, this argument ends up favoring zero values, for channels at least.My experience has been that they’d all be
foo: 0anyway. Although in practice I rarely use struct literals outside of a constructor function in Go (same with records in OCaml) because I inevitably want to enforce invariants and centralize how my values are created. In both languages, I only have to change one place after adding a field.The definition there but it’s implicit. I guess I don’t see much gained by having repetitive
= 0on each declaration, like I often encounter in C.standard input
I hope you’re not serious. I mean, sure, but it makes absolutely no sense whatsoever that leaving a variable uninitialized just means “use stdin” (if it’s still open).
File descriptor 0 is standard input on unix systems. (Unless you close it and it gets reused, of course, leading to fun bugs when code expects it to be standard input.)
As ludicrous as it would be, it would be a natural default value to have for careless language implementers, and before you know it users come to expect it. Even in C,
staticvariables are all zero initialised and using one onread(2)would indeed read from standard input.I’m sure we can point out various language quirks or weird idioms that started out that way.
A zero-value file descriptor is invalid, sure, but a zero-value mutex is just an unlocked mutex. Why would that be invalid?
There is no “zero” postal code, telephone number or user input.
Thing is, Go not only is statically typed, it is garbage collected.
As such, it is quite natural for it to use heap allocation for (almost) everything, and compensate for this with a generational GC. Now things get a little more complicated if they want to support natively sized integers (OCaml uses 31/62-bit integers to have one bit to distinguish them from pointers, so the GC isn’t confused), but the crux of the issue is that when you do it this way, generics become dead simple: everything is a pointer, and that’s it. The size of objects is often just irrelevant. It may sometime be a problem when you want to copy mutable values (so one might want to have an implicit size field), but for mere access, since everything are pointers size does not affect the layout of your containing objects.
This is quite different from C++ and Rust, whose manual memory management and performance goals kinda force them to favour the stack and avoid pointers. So any kind of generic mechanism there will have to take into account the fact that every type might have a different size, forcing them to go to a specialization based template, which may be more complex to implement (especially if they want to be clever and specialise by size instead of by type).
What’s clear to me is that Go’s designers didn’t read Pierce’s Type and Programming Languages, and the resulting ignorance caused them to fool themselves into thinking generics were complicated. No they aren’t. It would have taken a couple additional weeks to implement them at most, and that would have saved time elsewhere (for instance they wouldn’t have needed to make maps a built in type, and pushed that out to the standard library).
I have personally implemented a small scripting language to pilot a test environment. Plus it had to handle all C numeric types, because the things it tests were low level. I went for static typing for better error reporting, local type inference to make things easier on the user, and added an
x.f()syntax and a simple type based static dispatch over the first argument to get an OO feel. I quickly realised that some of the functions I needed required generics, so I added generics. It wasn’t perfect, but it took me like 1 week. I know that generics are simple.The reason the debate there is so one sided is because Go should have had generics for the start. The benefits are enormous, the drawbacks very few. It’s not more complex for users who don’t use generics, generic data structures can still be used as if they were built in, it hardly complicates the implementation, and it improves orthogonality across the board.
“LoL no generics” was the correct way to react, really.
It still seems to me that you are overconfident in this position. That’s fanboyism from my side, but Graydon certainly read TAPL, and if Graydon says “there’s a tradeoff between expressiveness and cognitive load” in the context of Go’s generics, it does seem likely that there’s some kind of tradeoff there. Which still might mean “LoL no generics” is the truth, but not via a one-sided debate.
Having covered meta issues, let me respond to specific points, which are all reasonable, but also are debatable :)
First, I don’t think the GC/no-GC line of argument holds for Go, at least in a simple form. Go deliberately distinguishes value types and pointer types (up to having a dedicated syntax for pointers), so “generics are easy ‘cause everything is a pointer” argument doesn’t work. You might have said that in Go everything should have been a pointer, but that’s a more complex argument (especially in the light of Java trying to move away from that).
Second, “It’s not more complex for users who don’t use generics,” – this I think is just in general an invalid line of argumentation. It holds in specific context: when you own the transitive closure of the code you are working with (handmade-style projects, or working on specific things at the base of the stack, like crypto libraries, alone or in a very small and tightly-knit teams). For “industrial” projects (and that’s the niche for Go) user’s simply don’t have the luxury of ignoring parts of the language. If you work on an average codebase with >10 programmers and >100k lines of code, the codebase will use everything which is accepted by the compiler without warnings.
Third, I personally am not aware of languages which solve generics problem in a low cognitive-load way. Survey:
C++ is obviously pretty bad in terms of complexity – instantiation-time errors, up-until-recently a separate “weird machine” for compile-time computations, etc.
Rust – it does solve inscrutable instantiation-time errors, but at the cost of far-more complex system, which is incomplete (waiting for GATod), doesn’t compose with other language features (async traits, const traits), and still includes “weird machine” for compile-time evaluation.
Zig. Zig is exciting – it fully and satisfactory solves the “weird machine” problem by using the same language for compile-time (including parametric polymorphism) and run-time computation. It’s also curious in that, as far as I understand, it also essentially “ignores TAPL” – there are no generics in the type system. It, however, hits “instantiation time errors” on the full speed. It seems to be that building tooling for such a language would be pretty hard (it would be anti-go in this sense). But yeah, Zig so far for me is one of the languages which might have solved generics.
Haskell – it’s a bit hard to discuss what even is the generics impl in Haskell, as it’s unclear which subset of pragmas are we talking about, but I think any subset generally leads to galactic-brain types.
OCaml – with questionable equality semantics, and modular implicit which are coming soon, I think it’s clear that generics are not solved yet. It also has a separate language for functors, which seems pretty cognitively complex.
Scala – complexity-wise, I think it’s a super-set of both Haskell and Java? I don’t have a working memory of Scala to suggest specific criticisms, but I tend to believe “Scala is complex” meme. Although maybe it’s much better in Scala 3?
Java – Java’s type system is broken in a trivial way (covariant arrays) and a (couple of?) interesting way (they extended type-inference when they added lambdas, and that inference allowed materialization of some un-denotable types which break the type system). I am also not sure that its “LoL covariant arrays”, as some more modern typed languages also make this decision, citing reduction of cognitive load. And variance indeed seems to be quite complex topic – Effective Java (I think?) spends quite some pages explaining “producer extends, consumer super”.
C# – I know very little about C#, but it probably can serve as a counter example for “generics in GC languages are simple”. Like Go, C# has value types, and, IIRC, it implements generics by just-in-time monomorphisation, which seems to be quite a machinery.
Now, what I think makes these systems complicated is not just parametric polymorphism, but bounded quantitication. The desire to express not only
<T>, but<T: Ord>. Indeed, to quote TAPL,I do think that there’s an under-explored design space of non-bounded generics, and very much agree with @c-cube . I am not quite convince that it would work and that Go should have been SML without functors and with channels, but that also doesn’t seem obviously worse than just three generic types! The main doubt for me is that having both interfaces and unbounded generics feels weird. But yeah, once I have spare time for implementing a reasonable complete language, unbounded generics is what I’d go for!
EDIT: forgot Swift, which absolutely tops my personal chart of reasons why adding generics to a language is not a simple matter: https://forums.swift.org/t/swift-type-checking-is-undecidable/39024.
Ah. that’s one hypothesis down then. Thanks for the correction.
OK, while I do have some experience with big projects, my best work by far was in smaller ones (including my crypto library, which by the way did not even need any generics to implement). What experience I do have with bigger projects however have shown me that most of the time (that is, as long as I don’t have to debug something), the only pieces of language I have to care about are those used for the API of whatever I’m using. And those tend to be much more reasonable than whatever was needed to implement them. Take the C++ STL for an extreme example: when was the last time you actually specified the allocator of a container? Personally I’ve never done it in over 10 years being paid to work with C++.
I have written one. Not public, but that language I’ve written for test environments? It had generics (unbounded, no subtyping), and I didn’t even tell my users. I personally needed them to write some of the functions of the standard library, but once that was done, I thought users would not really need them. (Yeah, it was easier to add full blown generics than having a couple ad-hoc generic primitives.)
Yeah, about subtyping…
In the code I write, which I reckon has been heavily influenced by an early exposure to OCaml (without the object part), I almost never use subtyping. Like, maybe 3 or 4 times in my entire career, two of which in a language that didn’t have closures (C++98 and C). If I design a language for myself, subtyping will be way down my list of priorities. Generics and closures will come first, and with closures I’ll have my poor man’s classes in the rare cases I actually need them. Even in C I was able to add virtual tables by hand that one time I had to have subtype polymorphism (It’s in my crypto library, it’s the only way I found to support several EdDSA hashes without resorting to a compilation flag).
I’ve heard of subtyping being successfully used elsewhere. Niklaus Witrth took tremendous advantage of it with its Oberon programming language and operating system. But I believe he didn’t have parametric polymorphism or closures either, and in this case I reckon subtyping & class based polymorphism are an adequate substitute.
Type classes (or traits) however are really enticing. I need more practice to have a definite opinion on them, though.
To clarify, graydon, as far as I know, didn’t participate in Go’s design at all (he designed Rust), so this has no bearing on your assumption about designers of Go.
Crap! Well, at least his argument has value.
If generics are simple, can you read this issue thread and tell everyone else how to fix
comparableto be consistent? TIA.Generics are simple under a critical condition: Design them from the ground up
Done after the fact in a system not designed for them, of course they’re going to be difficult. Then again, why waste a couple weeks of up front design when you can afford years of waiting and months of pain?
I don’t agree that generics are simple, but I agree that designing them in from the start is vastly easier than trying to retrofit them to an existing language. There are a lot of choices in how generics interact with your type system (especially in the case of a structural type system, which Go has, and even more so in an algebraic type system). If you build generics in as part of your type system from the start then you can explore the space of things allowed by generics and the other features that you want. If you don’t, then you may find that the point that you picked in the space of other things that you want is not in the intersection of that and generics.
I kinda had to change my mind on that one. Generics can be very simple in some contexts (like my own little language), but I see now that Go wasn’t one of them.
One thing I take for granted since I went out of college in 2007, is that we want generics. If your language is even slightly general purpose, it will need generics. Even my little specialised language, I didn’t plan to add generics, but some functions in my standard library required it. So this idea of even attempting to design a language without generics feels like an obvious waste of time to me. Likewise for closures and sum types by the way.
There is one thing that can make me change my mind: systematic experimentation for my niche of choice. I design my language, and I write a real program with it, trying to use as few features as possible. For instance, my experience in writing a cryptographic library in C convinced me they don’t need generics at all. Surprisingly though, I did see a case for subtype polymorphism, in some occasions, but that happens rarely enough that an escape hatch like writing your vtable by hand is good enough. I believe Jonathan Blow is doing something similar for his gaming language, and Niklaus Wirth definitely did the same for Pascal (when he devised Modula and Oberon).
I completely agree here. I wrote a book about Go that was finished just after Go reached 1.0 and, even then, I thought it was completely obvious that once you’ve realised that you need generic maps you should realise that you will need other generic types. Having maps (and arrays and slices) as special-case generics felt like a very bad decision.
Mind you, I also thought that having a language that encouraged concurrency and made data races undefined behaviour, but didn’t provide anything in the type system to allow you to define immutable types or to limit aliasing was also a terrible idea. It turns out that most of the folks I’ve spoken to who use Go use it as a statically compiled Python replacement and don’t use the concurrency at all. There was a fantastic paper at ASPLOS a couple of years back that looked at concurrency bugs in Go and found that they are very common.
I think Oberon and Go have a lot in common. Both were designed by an experienced language constructor late in his career, emphasising “simplicity” over everything else, leaving out even basic things such as enums, even though he had created more expressive languages earlier on.
I tend to be more sympathetic to Wirth’s decisions, because he was working in a closed ecosystem he completely controlled and understood. I mean, they were like less than 5 people working on the entire OS + compiler + main applications, and in the case of the Lilith computer, and FPGA Oberon, even the hardware!
He could have criteria such as “does this optimisation makes the entire compiler bootstrap faster? Here it’s for speed, but I can see the idea that every single piece of complexity has to pay for itself. It was not enough for a feature to be beneficial, the benefits had to outweigh the costs. And he could readily see when they did, because he could fit the entire system in his head.
Go is in a different situation, where from the start it was intended for a rather large audience. Thus, the slightest benefit to the language, even if it comes at a significant up-front cost, is liable to pay huge dividends as it becomes popular. So while I can believe even generics may not be worth the trouble for a 10K LOC system (the size of the Oberon system), that’s a different story entirely when people collectively write hundreds of millions of lines of code.
The best characterisation of Go and Oberon I can come up with is »stubborn«.
While Go is garbage collected, it is still very much “value oriented” in that it gives control to the programmer for the layout of your memory, much like C++ and Rust. Just making everything a pointer and plugging your ears to the issues that brings isn’t solving the problem.
I’m glad that you added generics to your small scripting language for a test environment in 1 week. I don’t think that speaks much to the difficulty in adding it to a different language with a different type system and different goals. When they started the language, things like “very fast compile times” where very high priority, with the template system of C++ generics heavily inspiring that goal. It would be inane to start a project to avoid a problem in a language and then cause the exact same problem in it.
So, they didn’t want to implicitly box everything based on their experience with Java, and they didn’t want to template everything based on their experience with C++. Finding and implementing a middle ground is, in fact, difficult. Can you name any languages that avoid the problems described in https://research.swtch.com/generic?
The problem with “lol no generics” is that the word “generics” sweeps the whole elephant under the rug. There are a fractal of decisions to make when designing them with consequences in the type system, runtime, compiler implementation, programmer usability, and more. I can’t think of any languages that have the exact same generics system. Someone who prefers Rust generics can look at any other language and say “lol no traits”, and someone who prefers avoiding generics entirely (which, I promise, is a reasonable position to hold) may look around and say “lol 2 hour compile times”. None of those statements advance any conversation or are a useful way to react.
Aren’t Rust traits analogous to Swift protocols?
That kind of changes everything… Oops. (Really, I mean it.)
Several things conspire to make C++ compile times slow. The undecidable grammar, the complex templates, and the header files. Sure we have pre-compiled headers, but in general, those are just copy pasta that are being parsed and analysed over and over and over again. I’ve seen bloated header-only libraries add a full second of compilation time per .cpp file. And it was a logging library, so it was included everywhere. Properly isolating it solved the problem, and the overhead was reduce to one second for the whole project.
A simpler grammar is parsed basically instantly. Analysis may be slower depending on how advanced static checks are, but at least in a reasonable language it only has to happen once. Finally there’s code generation for the various instantiations, and that may take some time if you have many types to instantiate. But at least you don’t have to repeat the analysis, and the most efficient optimisations don’t take that much compilation time anyway.
The parsing and analysis isn’t the whole problem. The C++ compilation model is an incremental evolution of Mary Allen Wilkes’ design from the ’70s, which was specifically designed to allow compiling complex problems on machines with around 2 KiB of memory. Each file is compiled separately and then pasted together in a completely separate link phase. In C++,
inlineand templated functions (including methods on templated classes) are emitted in every compilation unit that uses them. If 100 files usestd::vector<int>::push_backthen 100 instances of the compiler will create that template instantiation (including semantic analysis), generate IR for it, optimise it, and (if they still have calls to it left after inlining) spit out a copy of it in a COMDAT in the final binary. It will then be discarded at the end.Sony has done some great work on a thing that they call a ‘compilation database’ to address this. In their model, when clang sees a request for
std::vector<int>::push_back, it queries a central service to see if it’s already been generated. It can skip the AST generation and pull the IR straight from the service. Optimisers can then ignore this function except for inlining (and can provide partially optimised versions to the database). A single instance is emitted in the back end. This gives big compile time speedups, without redesigning the language.It’s a shame that the Rust developers didn’t build on this model. Rust has a compilation model that’s more amenable to this kind of (potentially distributed) caching than C++.
I’ll just leave this here https://www.research.ed.ac.uk/en/publications/featherweight-go
I meant back when Go first came out. That was over 12 years ago, in 2009. This paper is from 2020.
Nevertheless, the present thread significantly lowered my confidence in that claim. I am no longer certain Go designers failed to read Pierce’s work or equivalent, I now merely find it quite plausible.
Do you really think that Ken Thompson, Rob Pike, and Robert Greisemer were ignorant to this degree? That they made the design decisions they did based on a lack of theoretical knowledge?
None of them is known for statically typed functional languages, and I know for a fact there is little cross talk between that community and the rest of the world. See Java, designed in 1995, twenty years after ML showed the world not only how to do generics, but how neat sum types are. Yet Java’s designers chose to have
nullinstead, and generics came only years later. Now I kinda forgive them for not including generics at a time they likely believed class based polymorphism would replace parametric polymorphism (a.k.a. generics), but come on, addingnullwhen we have a 20 year old better alternative out there?So yeah, ignorance is not such an outlandish hypotheses, even with such people.(Edit: apparently one of them did read TAPL, so that should falsify the ignorance hypothesis after all.)But that’s not my only hypothesis. Another possibility is contempt for their users. In their quest for simplicity, they may have thought the brains of Go programmers would be too weak to behold the frightening glory of generics. That instead they’d stay in the shelter of more familiar languages like Python or C. I’m not sure how right they may have been on that one to be honest. There are so many people that don’t see the obvious truth that programming is a form of applied maths (some of them explicitly fled maths), that I can understand they may panic at the first sight of an unspecified type. But come on, we don’t have to use generics just because they’re there. There’s no observable difference between a built in
mapand one that uses generics. Users can use the language now, and learn generics later. See how many people use C++’s STL without knowing the first thing about templates.Yet another hypothesis is that they were in a real hurry, JavaScript style, and instead of admitting they were rushed, they rationalised the lack of generics like it was a conscious decision. Perhaps they were even told by management to not admit to any mistake or unfinished job.
This is exhausting and frustrating. It’s my own fault for reading this far, but you should really aim for more charity when you interpret others.
In the words of Rob Pike himself:
I’d say that makes it quite clear.
Ah, I didn’t remember that quote, thank you. That makes the contempt hypothesis much more plausible.
That being said, there’s a simple question of fact that is very difficult to ascertain: what the “average programmer” is capable of understanding and using, and at what cost? I personally have a strong intuition that generics don’t introduce unavoidable complexity significant enough to make people lives harder, but I’m hardly aware of any scientific evidence to that effect.
We need psychologists and sociologists to study is.
I’ve ran out of charitable interpretations to be honest. Go designers made a mistake, plain and simple. And now that generics have been added, that mistake has mostly been fixed.
I’m surprised you’re saying this after noticing that you didn’t know basic things about Go’s type system and implementation and learning those details “changes everything” (which, in my opinion, is commendable). Indeed, you’ve also apparently learned many facts about the authors and their history in this thread. Perhaps this is a good moment to be reflective about the arguments you’re presenting, with how much certainty you’re presenting them, and why.
A couple things:
So yeah, I still believe beyond reasonable doubt that omitting generics back then was a mistake.
All of your “analyses” are rooted in a presumption of ignorance, or malice, or haughty superiority, or some other bad-faith foundation. Do you really thing that’s the truth of the matter?
Some programming is a form of applied math. Most programming, as measured by the quantity of code which exists and is maintained by human beings, is not. Most programming is the application of computational resources to business problems. It’s imperative, it’s least-common-denominator, and it’s boring.
The only way it’s false is if omitting generics was the right thing to do. I don’t believe that for a second. It was a mistake, plain and simple. And what could possibly cause mistakes, if not some form of incompetence or malice?
It’s also maths. It’s also the absolutely precise usage of a formal notation that ends up being transformed into precise instructions for an (admittedly huge) finite state machine. Programs are still dependency graphs, whose density is very important for maintainability — even the boring ones.
It’s not the specific kind of maths you’ve learned in high school, but it remains just as precise. More precise in fact, given how unforgiving computers are.
“The right thing to do” is a boolean outcome of some function. That function doesn’t have a a single objective definition, it’s variadic over context. Can you not conceive of a context in which omitting generics was the right thing to do?
I see some:
Go was designed too late for (1) to fly with me, and it is too general purpose for (2). I even recall seeing evidence that its standard library would have significantly benefited from generics. I believe Rust and C++ have disproved (3) despite Go using value types extensively. And there’s no way I believe (4), given my experience in OCaml and C++. And dammit, Go did add generics after the fact, which disavows (4), mostly disproves (3), and utterly destroys (5). (And even back then I would have a hard time believing (5), generics are too important in my opinion.)
So yeah, I can come up with various contexts where omitting generics is the right think to do. What I cannot do is find one that is plausible. If you can, I’m interested.
You don’t need to speculate about this stuff, the rationale is well-defined and recorded in the historical record. Generics were omitted from the initial release because they didn’t provide value which outweighed the cost of implementation, factoring in overall language design goals, availability of implementors, etc. You can weight those inputs differently than the authors did, and that’s fine. But what you can’t do is claim they were ignorant of the relevant facts.
A language is designed as a whole system, and its features define a vector-space that’s unique to those features. Details about language L1 don’t prove or disprove anything about language L1. The complexity of a given feature F1 in language L1 is completely unrelated to any property of that feature in L2. So any subjective judgment of Rust has no impact on Go.
Do you just not consider the cost of implementation and impact on the unit whole as part of your analysis? Or do you weight these things so minimally as to render them practically irrelevant?
Generics did not materially impact the success of the goals which Go set out to solve initially. Those goals did not include any element of programming language theory, language features, etc., they were explicitly expressed at the level of business objectives.
What record I have read did not convince me. If you know of a convincing article or discussion thread, I’d like to read it. A video would work too.
I picked Rust for a specific reason: manual memory management, which means value types everywhere, and the difficulties they imply for generics. That said, I reckon that Go had the additional difficulty of having suptyping. But here’s the thing: in a battle between generics and subtyping, if implementing both is too costly, I personally tend to sacrifice subtyping. In a world of closures, subtyping and suptype polymorphism simply are not needed.
I’m not sure what you mean there… I think pretty much everyone agrees that designing and implementing generics up front is much easier than doing so after the fact, in a system not designed for them. If the Go team/community were able to shoulder the much higher cost of after-the-fact generics, then they almost certainly could have shouldered the cost of up-front generics back then —even though the team was much smaller.
Well if they just wanted to have a big user base, I agree. The Google brand and the reputation of its designers did most of that work. As for real goals, they’re the same as any language: help the target audience write better programs for cheaper in the target niche. And for this, I have serious doubts about the design of Go.
Now as @xigoi pointed out, Go authors targetted noobs. That meant making the language approachable by people who don’t know the relevant theory. That didn’t mean making the language itself dumb. Because users can’t understand your brilliant language doesn’t mean they won’t be able to use it. See every C++ tutorial ever, where you’re introduced to its features bit by bit. For instance when we learn I/O in C++ we don’t get taught about operator overloading (
<<and>>magically work on streams, and we don’t need to know why just yet). Likewise we don’t learn template meta programming when we first encounterstd::vector.People can work with generics before understanding them. They won’t write generic code just yet, but they absolutely can take advantage of already written code. People can work with algebraic data types. They won’t write those types right away, but they can absolutely take advantage of the option type for the return value of functions that may fail.
A language can be brilliant and approachable. Yet Go explicitly chose to be dumb, as if it was the only way to be easy to work with. Here’s the thing though: stuff like the lack of generics and sum types tends to make Go harder to work with. Every time someone needed a generic data structure, they had to sacrifice type safety and resort to various conversion to and from the empty interface. Every time someone needs to report failures to the caller, they ended up returning multiple values, making things not only cumbersome, but also fairly easy to miss —with sum types at least the compiler warns you when you forget a case.
It’s all well and good to design a language for other people to use, but did they study the impact of their various decision on their target audience? If I’m writing a language for myself I can at least test it on myself, see what feels good, what errors I make, how fast I program… and most of my arguments will be qualitative. But if I’m writing for someone else, I can’t help but start out with preconceived notions about my users. Maybe even a caricature. At some point we need to test our assumptions.
Now I say that, such studies are bloody expensive, so I’m not sure what’s the solution there. When I made my little language, I relied on preconceived notions too. We had the requirements of course, but all I knew wast that my users weren’t programmers by trade. So I made something that tries its best to get out of their way (almost no explicit typing by default), and reports errors early (static typing rules). I guess I got lucky, because I was told later that they were happy with my language (and home grown languages have this reputation for being epically unusable).
Do you consider generics and subtyping and polymorphism and other programming language properties means to an end, or ends in themselves?
Of course they’re a means to an end, why do you even ask?
In the programs I write, I need inheritance or subtyping maybe once a year. Rarely enough that using closures as a poor’s man classes is adequate. Heck, even writing the odd virtual table in C is enough in practice.
Generics however were much more useful to me, for two purposes: first, whenever I write a new data structure or container, it’s nice to have it work on arbitrary data types. For standard libraries it is critical: you’ll need what, arrays & slices, hash tables, maybe a few kind of trees (red/black, AVL…).
I don’t write those on a day to day basis, though. I’ve also grown susceptible to Mike Acton’s arguments that being generic often causes more problems than it solves, at least when speed matters. One gotta shape one’s program to one’s data, and that makes generic data structures much less useful.
My second purpose is less visible, but even more useful: the right kind of generics help me enforce separation of concerns to prevent bugs. That significantly speeds up my development. See, when a type is generic you can’t assume anything about values of that type. At best you can copy values around. Which is exactly what I’m looking for when I want to isolate myself from that type. That new data structure I’m devising just for a particular type? I’m still going to use generics if I can, because they make sure my data structure code cannot mess with the objects it contains. This drastically reduces the space of possible programs, which is nice when the correct programs are precisely in that space. You can think of it as defining bugs out of existence, like Ousterhout recommends in A Philosophy of Software Design.
How do you add two languages, or multiply a language by an element of a field?
That is not exactly why these languages have these features. They have these features because they do not expose a mechanism for capturing object identity. In C, you can cast a pointer to an address-sized integer and have a unique identifier that corresponds to the object. You can then do any integer operations on this value, whether it’s hashing, ordered comparison, or whatever. In a language that permits moving garbage collectors, you cannot use the memory location of the objects as identity and so you need something else. The default implementation of
hashCodetypically returns the address of the object the first time it’s called and sets a flag in the header so that it can be cached in a larger header if the object is moved.Capturing of object identity is done using == and System.identityHashCode (in java). equals and hashcode are there specifically so that they can be overridden; if that were not the case, there would be no need to make them user-overrideable methods. The operations which are exposed which are dedicated to identity are not user-overrideable, with good reason.
I think one of the interesting properties of Hare s that it’s C semantics/programming model with some minimal additions that make it nicer to use than C. I don’t think I’m sold (I’m happy with Rust, which I think makes me not the target for something like Hare) but it’s certainly an interesting take.
This post and some of the HN discussion just felt like flame bait, a kind of disingenuous look at the project. It’s like trying to write a circularly linked list in Rust and deciding “Rust sucks, it will never catch on without cyclic data structures!” Sure that feature has value, but making it easy to use doesn’t align with the rest of the project.
A: “You can’t even get this data structure right in a 600-word blog post! FAIL.”
B: “Hash tables are easy! Just roll your own if you can’t figure out how to do everything with slices and structs like Kernighan intended.”
Me: “Um, programming is hard and I don’t like being told that liking a robust stdlib is wrong any more than I like seeing people dunk on someone else instead of trying to glean the intent and ideas behind a new tool.”
uhm this is not reddit..
TL;DR, but won’t comment on it either, rather just tangentially: maybe we need a Hare tag? It’s coming up a lot
That’s just an artifact of a couple of days of posting–give it a month or two and see if a whole bunch more articles are posted. At that point, use a
metathread to ask for the tag.