22

I've read that Hindley-Milner does not work with type systems that have subclasses, and there are other type system features that also do not work well with it. Go currently has only very limited type inference in the := operator. But Go does not have subclasses in the traditional sense, only interfaces which look very much like Haskell's type classes which work fine with Hindley-Milner inference.

So, could Hindley-Milner inference work in principle for Go the same way as it does for Haskell? Or does Go have other features that break it? (On the other hand, Haskell also has some features that don't work with Hindly-Milner, if you use those you have to manually type those parts of your program.)

35

The Hindley-Milner type inference is used for Hindley-Milner type systems, a restriction of System-F type systems. The interesting feature of HM type systems is that they have parametric polymorphism (aka. generics). That is the single biggest type system feature that Golang refuses to have.

With that frustrating restriction, HM-style type inference is impossible. Let's look at the untyped code:

func f(a) {
  return a.method()
}

What is the type of f? We might notice that a must have a method, so we could use an anonymous interface: func f(a interface { method() ??? }) ???. However, we have no idea what the return type is. With type variables, we could declare the type as

func f[T](a interface{ method() T }) T

However, Go does not have type variables so this won't work. While implicit interfaces make some aspects of type inference easier, we now have no way to find out the return type of a function call. The HM-system requires all functions to be declared rather than be implied, and each name can only have a single type (whereas Go's methods can have different types in different interfaces).

Instead, Go requires that functions are always fully declared, but allows variables to use type inference. This is possible because the right hand side of an assignment variable := expression already has a known type at that point of the program. This kind of type inference is simple, correct, and linear.

  • The type of a variable is immediately known at the point of the declaration, whereas HM inference has to potentially type-check the whole program first. This has a noticeable impact on the quality of error messages, too.
  • Go's type inference approach will always select the most specific type for a variable, in contrast to HM which picks the most general type. This cleanly works with subtyping, even with Go's implicit interfaces.
  • 22
    @bishop It's "reasoned" for infinitesimally small values of "reason". – hobbs Apr 18 '16 at 17:44
  • 17
    @bishop Having done compiler work in languages with generics, I can certainly agree: it's difficult to implement without significantly complicating the implementation. I'd go so far as to even replace "difficult" with "impossible." However, that's not the point; the point is, is it worth the extra complication? And the answer, to anyone who's worked with and without generics, is obviously "yes, definitely!" I'd have to agree wholeheartedly with the claim that refusing to implement generics because "oh no, complexity" is idiotic. – Mason Wheeler Apr 18 '16 at 17:48
  • 17
    This is also why Go devs pretend that FP of all sorts is bad; Go has first-class functions with lexical closure, and with that the ability to create higher-order functions, but it's impossible to put them to any good use because the types of such basic functions as map, filter, and reduce are all inexpressible within Go's very limited type system. – hobbs Apr 18 '16 at 17:48
  • 9
    @hobbs And Go could be a really nice language if that were fixed, but instead people have to write generic-generation libraries like gengen and gonerics – cat Apr 18 '16 at 18:39
  • 13
    @cat It's a shame. At first Go seems like a great language full of great ideas, but then you realize it has no inheritance and polymorphism, so you can't do OOP well, and it has no generics, so you can't do FP well, and you're left staring blankly at the screen asking "then how exactly are you supposed to use this language?!?" – Mason Wheeler Apr 18 '16 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.