[HN Gopher] Go generics draft design: building a hashtable
___________________________________________________________________
Go generics draft design: building a hashtable
Author : mdlayher
Score : 100 points
Date : 2020-06-17 18:26 UTC (4 hours ago)
(HTM) web link (mdlayher.com)
(TXT) w3m dump (mdlayher.com)
| lsllc wrote:
| 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?
| sacado2 wrote:
| I'm ready to bet that with <>, you'd introduce ambiguity in the
| grammar, making parsing code (and, as a consequence, writing
| tools for the language) much more complicated.
| monkeyfacebag wrote:
| 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/des...
| ) discusses both of these points. I recommend everyone who is
| interested in this topic read the design spec, ideally before
| commenting.
| twblalock wrote:
| 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- wrote:
| 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 wrote:
| 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.
| monkeyfacebag wrote:
| In my opinion, the new design doc clearly characterizes
| this as a design goal of the parser, rather than a hard
| constraint that cannot be resolved.
|
| "Resolving that requires effectively unbounded lookahead.
| In general we strive to keep the Go parser simple."
|
| It's totally fair to question the tradeoff - should having
| a simple parser outweigh the potential ergonomic benefit of
| <>? I don't know. The forum for this is probably the
| golang-nuts group.
| nemetroid wrote:
| The design doc doesn't say "simple", it says "efficient".
|
| I think "simpler" would have been a stronger argument.
| While using <> would make the parser more complex, I have
| a hard time seeing that making a meaningful performance
| difference in a compilation context. Maybe if you're
| parsing a lot of Go without actually compiling it, but
| that doesn't seem like a use case to optimize for.
| mpoteat wrote:
| It's all a matter of where you accept the complexity - in
| the compiler, in the language, or in the downstream
| applications. In my view it's an obvious choice to choose
| a more complicated compiler on exchange for simpler
| downstream applications...
| Sharlin wrote:
| C++ and Rust require extra disambiguating syntax in some
| contexts (C++ the `foo.template bar<T>()` syntax, Rust the
| "superfish operator" `foo.bar::<T>()`. Java works around
| the problem by awkwardly putting the generic argument list
| in _front_ of the method name (`foo. <T>bar()`). I don't
| know about C#.
| DougBTX wrote:
| C# is `foo.bar<T>()`, I'm not sure what compromises that
| had to make for that to work but from an end-user
| perspective it works well.
| steveklabnik wrote:
| (teeny tiny note: turbofish, not superfish)
| Sharlin wrote:
| Oops :D
| mdlayher wrote:
| Exactly. Thanks!
| _ph_ wrote:
| I never have been able toi read the syntax with < > well, so I
| am soo happy they found some syntax based on parens. It is
| perfectly readable for me.
| nytgop77 wrote:
| After seeing and trying dlang syntax for generics I was
| hugely disappointed that rust chose angle brackets.
| BurningFrog wrote:
| Now that unicode is everywhere I think it's time to use more
| brackets than [], (), {} and <>.
|
| Python is the worst, where dicts and sets both use {} and
| tuples and "grouping" both use (), each causing real problems.
|
| Some of many possibilities:
|
| [?][?]<<>> [[?] <> [?][?] [?][?] [?][?] [?][?] [?][?] ||
|
| Yes, you need a way to type it on non specialized keyboards.
|
| An easy way is is to type it as (( or [[ etc, and let the IDE
| convert it.
| a1369209993 wrote:
| Dicts and sets are _supposed_ to both use {}; {a,b,c} is
| (conceptually) shorthand for {a:dummy,b:dummy,c:dummy}, where
| sets (in some cases, including python, opaquely) are actually
| dicts without the space to store values. (This also shows up
| in set theory and related mathematics, although there it 's
| dicts that are unusual.)
|
| The rest of post is fair point, although I think you
| underestimate the value of plain ASCII that can be typed on a
| unassisted keyboard.
| hombre_fatal wrote:
| To me this is the ultimate "developer chasing shiny" at the
| expense of everything else.
|
| Especially in the context of Go that hasn't even managed to
| use anything other than parentheses in its func definition
| syntax. No language has saturated the bracket options that
| come with the standard US keyboard so much that it's worth
| bringing in characters that you need additional tooling to
| type.
|
| If (), <>, {}, and [] aren't enough for a language, something
| has gone very wrong.
| asjw wrote:
| That's a lot of effort for little benefits
|
| I can already see a lot of edge cases
|
| Most notably font support
|
| I like ligatures and ide/editor support for them, but I'm not
| sure I like this
| BurningFrog wrote:
| The benefit is purely readability.
|
| You read code 1000x more often than you write it, so a
| little extra effort for even a small readability benefit is
| worth it.
|
| Most fonts have quite full Unicode support since many
| years.
|
| I'm often disappointed in how reluctant programmers are to
| use modern technology. The public thinks we're on the
| cutting edge of advanced technology. If they only knew :)
| throw_m239339 wrote:
| There is absolutely no way this gets the vocal "conservative"
| core of the Go community's approval. For better or worse.
| mseepgood wrote:
| The <> people are the conservatives, because they are afraid
| to give new things a try. They want every programming
| language to look the same.
| DaiPlusPlus wrote:
| Consistency is important, though. Using C-family syntax
| makes it easy to get people to dip their toes into
| something within the spending time to learn a new syntax.
| Look at modern languages like Rust, Swift, Dart, and Go:
| they all use C-style syntax.
|
| I'm not accusing you of advocating Go's adopting a
| different syntax for generics solely to be contrarian - but
| using angle-brackets for type-parameters and template-
| parameters is a proven technique with few downsides - and
| certainly not any that downsides that would be fixed by
| using any other syntax I'm aware-of.
| rob74 wrote:
| Well, Go already picks and chooses elements from
| different languages, e.g. Pascal-style declarations ("x
| int" instead of "int x") and C-style blocks ("{...}"
| instead of "begin...end"). So I'm not surprised that when
| deciding on the syntax for generics they look more at
| what fits best for Go than at what other languages are
| doing...
| iand wrote:
| 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/
|
| Specifically
| https://golang.org/src/hash/maphash/maphash.go?s=1316:1346#L...
| links to the internal hash function.
| mdlayher wrote:
| Right, but you can only write strings or bytes to the hash, not
| integers, booleans, structs, etc. So the problem remains.
| ardit33 wrote:
| 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 wrote:
| 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 wrote:
| > 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
| mdlayher wrote:
| 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.
| nicoburns wrote:
| 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?
| mdlayher wrote:
| 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.
| skybrian wrote:
| For example, the caller could cast `int` to `myInt` which
| implements the appropriate interface. This is probably more
| idiomatic than using a bare `int` type anyway.
| sacado2 wrote:
| You can only add methods on types that were defined in the
| current package. As a consequence, you can't add methods to
| built-in types. But that's rarely something you want to do
| anyway (I can't think of a real-world situation where it would
| be useful), what would make sense is creating a new string
| type, and add methods to it: type myInt int
| func (mi myInt) f() myInt { ... }
| [deleted]
| lspears wrote:
| 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.
| benhoyt wrote:
| What would be a real-world example of what you're referring to
| ("implement your own interfaces on built-in types")?
| uluyol wrote:
| Perhaps like overloading in C++? Hash functions are sometimes
| defined this way
| (https://abseil.io/docs/cpp/guides/hash#making-hashable-
| types)
| _ph_ wrote:
| 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.
| malcolmgreaves wrote:
| 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 wrote:
| 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"?
| alkonaut wrote:
| 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.
| jerf wrote:
| 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]
| Someone wrote:
| 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.
| mdlayher wrote:
| 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.
| masklinn wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| 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();
| weberc2 wrote:
| I agree that there are semantic issues with pointers, but
| my point was to illustrate that you need sum types in Go
| to get any real benefit out of an Option type. If you
| need an option type and you aren't content with a
| pointer, you can use `(T, bool)`, but this is still a far
| cry from a real Option type.
| alkonaut wrote:
| I use Option<T> types very happily in C# without sum
| types. Most of what would be pattern matching can be done
| with just methods. Car c =
| maybeCar.GetValueOr(CreateCar()) // inline fallback
| maybeDog.Do(d => b.Bark()) // only performs call if
| present Sailboat s = mybeBoat.As<SailBoat>()
| // none unless of correct subtype
|
| And so on. With nullable reference types C# now has a
| builtin alternative to this, but it has worked we'll for
| many years.
| simias wrote:
| 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 wrote:
| 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.
| peter_l_downs wrote:
| 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
|
| 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.
| [deleted]
| MHordecki wrote:
| > 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`.
| peter_l_downs wrote:
| I see what you're saying, and while I think you're right, I
| think a lot more of the value is in being able to use
| `Map()` /`FlatMap()` to be able to avoid thinking about
| error checking at all, as I laid out in the second part of
| this comment https://news.ycombinator.com/item?id=23549396
| . The convention of returning `(value, err)` goes a long
| way towards enforcing the checking of errors; I have
| golangci-lint's `errcheck` linter enabled and basically
| cannot accidentally ignore the `err` values. In any case,
| Option/Result types are extremely useful and I'm happy that
| with generics the language will be able to include them!
| weberc2 wrote:
| > 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 wrote:
| 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]
| nemetroid wrote:
| > 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 wrote:
| 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]
| nemetroid wrote:
| What I mean is that as written, the demo doesn't need V to be
| comparable.
| mdlayher wrote:
| Oh wow, for some reason I totally zoned out and finally
| understand what you mean. Yes, you're right! I should fix
| that.
___________________________________________________________________
(page generated 2020-06-17 23:00 UTC)