12 ms·

Go generics draft design: building a hashtable

• malcolmgreaves 6y ago
  Since this post is illustrating the use of generics, why not go all the way with the get implementation to return an Option[V] type? It's a natural thing to do here. The return type is already a kind of sum type: it's either the value you want (non-zero value, true) or it's not (zero value, false). If the implementation uses the optional type, it'll become impossible to write code that uses the zeroed-out returned value incorrectly. Calling code must always explicitly check the returned Optional[V] value to access the value of V and continue or to perform some code to handle the not present case. As it stands, it's very possible to ignore the 2nd returned boolean value and write code that'll easily break. Now, I can see why the author would _not_ want to do this, since this "explosion" of sum-typed things is present in all go code (e.g. the err := ...; if err == nil { ... pattern). So, it might be easier for Go programmers to see how they could use generics in their own code by re-using this pattern. However, I think this is a disservice to why generics are an incredibly useful construct in programming languages. They can be used to align code more closely with the semantics that the programmer wants to convey.
  • cy_hauser 6y ago
    I'm not understanding this. Are you saying an Option[V] would reduce the number of lines of code (the explosion) that Go code uses for "err := ...; if err == nil"?
    • jerf 6y ago
      I don't think it would in Go. You'd still end up with result := ThingThatReturnsOption(...) if result.Error() != nil { // ... } happening in general, or some other equivalent construct. The main point of having Option in this case would be to make it so that where Go programmers normally write result, err := ThingThatMayError() you can get precisely one of a result or an error. At the moment with the current calling convention it is possible to both return a result and an error. However, I will say that while in theory this is advantageous (and I mean that seriously), in practice this is nearly a non-issue. I don't think I've ever had a bug because I had both things and misused them. I expect a dozen or more "Option" implementations to pop up nearly overnight once this is released, and for Go programmers to settle pretty quickly on not using it. In non-Go languages, Options can have additional features that make them yet more powerful, such as chaining together optional computations in a way that makes it easy to shortcircuit whole computations, e.g., in Haskell: do x <- optionalFail y <- somethingElseFail x z <- moreMightFail x y return (extractFromZ z) In Haskell, assuming the right definitions of the various functions, while that may look like it's not handling errors, it actually is, because the machinery behind their Option type (called Either in Haskell) is handling all the short circuiting. Go comprehensively lacks the features necessary to make that sufficiently pleasant to use that anyone will, though. It is not unique in lacking those features, most languages are missing at least one thing to make it easy enough to use people will, but it does quite comprehensively lack them. It's not just a matter of adding this one little thing or that other thing, it'd be a whole suite of necessary changes, e.g., you might be able to write an .AndThen(...) function to operate on a Option type, but it's going to be too inconvenient to use, even post-generics, and even if you force it because it's the Right Thing to Do in languages that aren't the one you are currently programming in, it's still going to be a lot of disadvantages for not much advantage. Personally I don't value "Doing the Right Thing in language X while working in language Y" very highly, but some people seem to.
      • deleted 6y ago
        [deleted]
    • Someone 6y ago
      I think they are saying using sum types will remove a source of errors (forgetting to check for error conditions). I also think part of their remark is on ‘either’, not ‘option’, but that’s not important for the point being made.
    • alkonaut 6y ago
      When you chain multiple things that can go wrong with Result[T,E] or Option[V] it should be possible assuming there are methods for chaining/fallback. E.g. opening a file, reading the contents, parsing the contents etc. If all those 3 return Result[T,E] and you want the overall result (parsed) T or the first error to occur, then you should be able to chain that.
  • masklinn 6y ago
    > If the implementation uses the optional type, it'll become impossible to write code that uses the zeroed-out returned value incorrectly. Since Go doesn't have sum types, it would most likely be possible: the option type would just be a reification of the MRV. At best it could panic if you try to get the value of an "empty" optional but now you've got a panic.
    • alkonaut 6y ago
      It’s always possible, even in a Rust Option you’ll panic when you extract the value with unwrap() without knowing that it’s valid. What it does is preventing the accidental use of a missing value. You can’t pass the Option<T> on to a function taking a T without explicitly doing it.
      • weberc2 6y ago
        This doesn't add anything. You get the same protection in Go with pointers. For example, a `*T` can't be passed to a function taking a `T` without explicitly dereferencing it. The problem of course is that the type system doesn't guarantee that the pointer isn't nil when you go to dereference it, similarly your `Option<T>` doesn't guarantee that the option.Value is set correctly. You need sum types to provide this substantial guarantee.
        • alkonaut 6y ago
          It guarantees that the value is set if the flag is saying it is set (that's the invariant of the type). It screams "check flag before accessing the value". To compare with references which are also 0-or-1-thing effectively: A reference where you as a developer know it's never null but always a ref to exactly one thing is denoted "* T" and a reference to "one thing or null" is denoted "* T"! There is no difference in the types! so you can accidentally send one that is "0-or-1-things" to a method accepting a * T that MUST be a thing. Type system didn't help you document which case it was. Options, apart from the annotation benefit it also helps making the syntax nicer in many cases, with e.g. "or()" fallbacks etc. let data = get_cached().or(load_from_disk()).or_panic();
  • simias 6y ago
    I don't use Go myself but knowing its philosophy I wonder if they'll end up replacing the idiomatic "if err == nil" with an generic optional type even if they end up implementing generics in Go. For one thing it would generate a massive amount of churn to upgrade existing code, and if you don't update you'll quickly end up with very ugly mixed error handling patterns. On top of that Go seems to really value compilation speed, so I suspect that they won't want generics "contaminating" interfaces all over the place only to do error handling. I'm really curious to see (from the outside) how all of this is going to coalesce in the end.
    • weberc2 6y ago
      Generics aren't the gap (multiple return values are already generic), but rather sum types. Sum types are what allow you to express that this is either None/Sum(T) (Option) or Ok(T)/Err(E) (Result) or Nil/Cons (List) or etc.
      • Groxx 6y ago
        Sum types are what give you compile-time safety over those options. Run-time safety and developer-intent-signaling is entirely feasible with just generics.
        • weberc2 6y ago
          Right, but as previously mentioned, Go's multiple return values are already "generic" and already signal developer intent. If you have a library method that returns (int, err) every single Go developer will check the err first before using the int. User-defined generics don't improve this use case.
          • Groxx 6y ago
            Result types can, at runtime, by making the err case panic if the value is accessed, instead of just returning a zero value. They let you move past intent and into enforcement. Multiple returns are nothing but intent, and cannot be made stronger. You can do that without generics, of course. But the developer overhead is large enough that it effectively does not happen, as you have to redo that by hand for every type. That's what generics bring - ergonomics good enough to stop using less safe workarounds (e.g. `interface{}`, multiple returns).
  • mdlayher 6y ago
    I like the idea, I just haven't given it a try with the new draft yet. Sounds like it's worth exploring at the very least.
    • malcolmgreaves 6y ago
      Cool! I'm glad you read my comment. I appreciate that you went through the effort to make a blog post (my comment is very low effort in comparison). I hope it came off as constructive.
  • peter_l_downs 6y ago
    Take a look at the comment tree starting here in the Generics announcement thread from the other day for some discussion of Option[V] under the current proposal: https://news.ycombinator.com/item?id=23545361 https://news.ycombinator.com/item?id=23545361 For what it worth, returning `(value, err)` is conceptually the same thing as returning a Result[V]. You can ignore the error case on a result / the None case on an option as easily as you ignore the `err` today.
    • MHordecki 6y ago
      > You can ignore the error case on a result / the None case on an option as easily as you ignore the `err` today. The point of a result type is that you _cannot_ ignore the None case. Any method that would provide you with the value will also check that the error is not present. In comparison, you can happily ignore `err` in Golang and continue with an invalid `value`.
      • weberc2 6y ago
        > In comparison, you can happily ignore `err` in Golang and continue with an invalid `value`. I'm struggling to envision a Result type that requires you to be more explicit than `foo, _ := fallible()`. Seems like `fallible().Ok()` and similar are strictly less explicit.
        • hombre_fatal 6y ago
          To do anything with a Result/Optional, you have to explicitly get the value inside the box at some point. But the container abstraction also gives you a nice composition abstractions instead of the uncomposable top-level `val, err := do()` destructure. Though perhaps not quite as compelling without real sum types. I'd have to play with Go's generic-typing sandbox more to form a stronger opinion.
      • deleted 6y ago
        [deleted]
      • peter_l_downs 6y ago
  • ccktlmazeltov 6y ago
    I really wish Go would pursue sum types instead of generics
    • mrath 6y ago
      Sum types without generics will still be good enough? I think for things like Option/Result we need both sum types and generics.
      • ccktlmazeltov 6y ago
        I don't think you would need user generics for this to work.
        • masklinn 6y ago
          Non-generic sum types are useful but you can’t build an option or result type out of them, so the usefulness is somewhat hampered.
          • ccktlmazeltov 6y ago
            But you don't need to, generic Option and Result types could be built as part of the standard library.
            • masklinn 6y ago
              Yes but then you need neither sum types nor user-defined generics, you can just build-in whatever sugar is useful or necessary (possibly repurposing existing sugar e.g. the `select` statement).
              • ccktlmazeltov 6y ago
                sum types are still super useful imo without generics.
        • 6y ago
• lsllc 6y ago
  Interesting article. I think that using <> for the type specifiers would possibly be better! For example one could quickly end up with something like: func (obj *SomeType(Q, Z)) Foo(type K, V comparable)(key K, val V) (*OtherType(Q, V), error) { ... } ... Lots of Infuriating & Silly Parentheses?
  • monkeyfacebag 6y ago
    On <> syntax, this has been discussed quite a bit. () were chosen to avoid ambiguous parsing. Also note that generic methods are not allowed in the current design, only generic functions. The new draft design ( https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md https://go.googlesource.com/proposal/+/refs/heads/master/des... ) discusses both of these points. I recommend everyone who is interested in this topic read the design spec, ideally before commenting.
    • mdlayher 6y ago
      Exactly. Thanks!
    • twblalock 6y ago
      On the <> syntax, why not improve the parser? Every language that uses <> for generics has a parser that is able to distinguish between generics and the "less than" operator, and it seems odd that Go developers think it can't be done efficiently.
      • 8192kjshad09- 6y ago
        Go developers like to claim that the reason the Go compiler is fast is because it's "simple to parse". Unfortunately this doesn't make a lot of sense as parsing is typically only 1-5% of the total compile time.
        • sacado2 6y ago
          It's not only about the main compiler. Go has tons of third-party tools (linters mainly) that can parse go code, because it's so easy to write one. Most of them wouldn't exist if parsing was a PITA.
• iand 6y ago
  The author asks about using the same hash function as the builtin Go map. This was recently exposed in the standard lib at https://golang.org/pkg/hash/maphash/ https://golang.org/pkg/hash/maphash/ Specifically https://golang.org/src/hash/maphash/maphash.go?s=1316:1346#L203 https://golang.org/src/hash/maphash/maphash.go?s=1316:1346#L... links to the internal hash function.
  • mdlayher 6y ago
    Right, but you can only write strings or bytes to the hash, not integers, booleans, structs, etc. So the problem remains.
• nicoburns 6y ago
  The limitation around implementing methods on built-in types seems unfortunate. If I understand how Go interfaces work correctly, that would mean that you also can't implement your own interfaces on built-in types. Which would seem like quite a severe restriction in being generic over them. Perhaps I'm missing something?
  • lspears 6y ago
    If you assume that the std lib creates a collections package, there could be helper types will for primitives. No Java style auto boxing, but more in the Go style. These could also be used in a refactored math package.
  • deleted 6y ago
    [deleted]
  • mdlayher 6y ago
    The alternative is to do something like: type Int int func (i Int) Hash() uintptr { /* do the hash */ } But I didn't want to deal with it in this code. I agree that it isn't optimal and would be curious to see if the situation can be improved.
  • benhoyt 6y ago
    What would be a real-world example of what you're referring to ("implement your own interfaces on built-in types")?
    • uluyol 6y ago
      Perhaps like overloading in C++? Hash functions are sometimes defined this way (https://abseil.io/docs/cpp/guides/hash#making-hashable-types https://abseil.io/docs/cpp/guides/hash#making-hashable-types)
    • renewiltord 6y ago
      You can do cool things like Ruby's `2.days.ago` in languages that allow you to implement traits on any type.
• _ph_ 6y ago
  Looks pretty nice and readable. Looks to me like a strong indication that the updated generics concept is close to what should go into Go.
• nemetroid 6y ago
  > For my design, I decided to enforce that both key and value types are comparable, so I could build a simple demo using two hashtables as an index and reverse index with flipped key/value types. Surely the demo works equally well without this extra constraint? If the demo had a generic function for creating a reversible mapping it would have been necessary, but as it stands, this extra constraint comes across as avoiding having to write the less aesthetically pleasing type Table(type K comparable, V interface{}) struct { ...
  • mdlayher 6y ago
    Yep that is true. I wanted both values to be comparable for an easy demo but would write it as you've suggested if I intended to make this a general purpose package.
    • deleted 6y ago
      [deleted]
    • nemetroid 6y ago
      What I mean is that as written, the demo doesn't need V to be comparable.
      • mdlayher 6y ago
        Oh wow, for some reason I totally zoned out and finally understand what you mean. Yes, you're right! I should fix that.
• ardit33 6y ago
  I am not a GoLang programmer, but that just didn't look neither pretty or readable... Perhaps, perhaps, hard-core generics are not a great idea after all, and they should only be in the annotation level of the language (especially for container types, which is the only place where generics are truly valuable)...
  • galkk 6y ago
    The problem is that with current proposal Go severely lacks type inference, required for generics to look nice and clean. A lot of the information is already in the definitions, there's no reason to repeat it, but Go chose to do that. // Reduce reduces a []T1 to a single value using a reduction function. func Reduce(type T1, T2)(s []T1, initializer T2, f func(T2, T1) T2) T2 { s := []int{1, 2, 3} sum := slices.Reduce(s, 0, func(i, j int) int { return i + j }) and the example from referenced article is even more outrageous t1 := hashtable.New(string, int)(8, func(key string, m int) int { We have function types literally at the same exression, but Go requires to repeat it.
    • mseepgood 6y ago
      > We have function types literally at the same exression, but Go requires to repeat it. It does not require it, the author chose to do it. t1 := hashtable.New(8, func(key string, m int) int { is perfectly valid. https://go2goplay.golang.org/p/SbEXpyVl-V3 https://go2goplay.golang.org/p/SbEXpyVl-V3
      • mdlayher 6y ago
        In this particular case, the compiler can't infer the type of V if you omit the type parameters at the call sites: type checking failed for main prog.go2:17:3: cannot infer V (prog.go2:46:27) prog.go2:22:3: cannot infer V (prog.go2:46:27) But generally you are right, yes. It is able to infer K at least.
      • galkk 6y ago
        Thanks for noting, but my bigger concern was with different thing, that I’m also quoting from the doc (https://go2goplay.golang.org/p/LFo23rCKHXZ https://go2goplay.golang.org/p/LFo23rCKHXZ): func Filter(type T)(s []T, f func(T) bool) []T { ... } s:= []int{1,2m3} evens := slices.Filter(s, func(i int) bool { return i%2 == 0 }) The type of predicate is already in generic definition, we don’t need this verbosity. Other languages (I’d even say most of languages, used in dev work today) let us write simply something like slices.Filter(s, i->i%2).
• arghblarg 6y ago
  For what it's worth from the Peanut Gallery™, I find the proposed syntax quite readable and am happy there are no angle brackets <> stabbing my eyes. It seems powerful enough to cover most cases of generics. Architecture astronauts will never be happy, but tough.
  • tapirl 6y ago
    Comparing it with the builtin hashtable: * the custom one: hashtable.Table(string, int) * the builtin one: map[string]int The syntax forms are quite different. Wouldn't it be better to make them consistent? Is it so hard to achieve this?
    • jeremyjh 6y ago
      It would not surprise me to learn that the parser has special rules for the token "map".
      • tapirl 6y ago
        Yes, the fact that "map" is a keyword and "Table" is not really makes a trouble for parser. But I think we should think towards the road. There should be always a solution.
        • mpfundstein 6y ago
          lisp
  • IshKebab 6y ago
    I'd definitely prefer angle brackets. With everything being parantheses I just get lost keeping track of what is what - they're now used for type parameters, parameters and return values, one after the other with no separation, and two of them are optional. Quite confusing if you ask me.
    • Cthulhu_ 6y ago
• int_19h 6y ago
  For a long time, Go designers have been saying that it doesn't have generics, because they don't think that the ways they're done in other languages is "good enough". Looking at this, I don't see any fundamental differences from, say, C#. They're even using interfaces for generic constraints. Did they decide that they are "good enough", after all?
  • sudhirj 6y ago
    Don’t think the type systems itself were up for debate - the Go team isn’t necessarily going to invent new types of types or advance research in type theory - That’s already been done enough by Haskell, Scala and others. Whatever system comes into Go will have already been done somewhere. The good enough is more drawing the tradeoff line in a spot that’s useful and clean to maintain, and the place where the core team and the community draws that line is finally converging.
    • int_19h 6y ago
      But that's the thing - they ended up drawing that trade-off line in more or less the same spot as most other mainstream PLs with generics. I don't understand why it took so long to basically acknowledge that prevailing wisdom is correct.
      • sudhirj 6y ago
        A refusal to acknowledge that prevailing wisdom was correct is what got us Go in the first place. I think of the value of the project as being a re examination of every aspect of programming from first principles. Some decisions will change, some will be considered to already be optimal.
• giovannibajo1 6y ago
  Small note: the runtime hash function is available in standard library (hash/maphash) since Go 1.14. You don't need that introspection magic to access it.
• AbuAssar 6y ago
  Offtopic: the blog post title alone is taking up my entire phone screen (iPhone 7)