Hacker News Reader

Comment by dwohnitmok | Hacker News Reader

In that case maybe generics aren't a compile time killer. (Although I'm quite curious how the OCaml compiler compiles so quickly).

View on HN

Go people have a very weird understanding of generics, and that messes up many discussions.

They typically mix up parametric polymorphism and ad-hoc polymorphism.

I blame C++'s templates for the confusion. (And Go people's common refusal to look much further, and especially not into academia..)

> And Go people's common refusal to look much further, and especially not into academia..

I don't think that's a fair statement, given Phil Wadler's formal work on generics in Go - "Featherweight Go" (https://arxiv.org/abs/2005.11710) - which is acknowledged here: https://blog.golang.org/generics-next-step

Yes, hence my weasel word with 'common' and 'most'.

It's good to see that they are taking the likes of Phil Wadler serious. (Perhaps his beard helps?)

> We’d like to thank Philip Wadler and his collaborators for thinking formally about generics in Go and helping us clarify the theoretical aspects of the design.

In the older post at https://blog.golang.org/why-generics you still see them pretty much mix up parametric polymorphism and ad-hoc polymorphism.

Thanks for the link to the paper!

Technically OCaml typechecking is exponential in the length of your program, but really that's just because it's exponential in the depth of your most deeply nested `let` construct, and most people don't actually write programs that look like

    let a = ...
      in let b = ...
        in let c = ...
          in let d = ...

Wait, that's actually really common in OCaml though. I mean not the indentation of course, but every series of let-bindings is essentially a single nested expression. That's just the way let-bindings work.

Generics in the sense of C++ templates can be a compile time killer. However generics in the sense of HM type systems are basically just asking the compiler to fill in the type for you, which it has already figured out. HM type inference in general is ~O(n) (and exponential in the worst case, but you basically have to try to do that)

Right, so there are two reasons that C++ templates hurt compile times:

1. C++ templates don't require you to treat the type variables as opaque; depending on what the body of a template does with its type parameters it may or may not type check depending on how the variable is instantiated. By contrast, in OCaml (and most languages) generic functions cannot assume anything about their type parameter. This means that the compiler can type check the body of the generic function once and be done, rather than having to essentially check it at every call site.

2. Aside from type checking, C++ templates generate separate code for each instantiation of the type parameters. This (generally) results in faster code as it is specialized to the type in question, but it means more code is generated, which of course takes time (and it can also bloat the executables). This is probably a bigger deal than the type checking part. By contrast, OCaml only generates one copy of the code for a function, which simply doesn't care about the types of its arguments. This is also a common implementation strategy; Java does something similar.

Note that Rust also suffers from (2), but not (1).

You can get OCaml to behave like 2, but you need eg Generalised Algebraic Datatypes or some magic with modules to do so.

See https://blog.janestreet.com/why-gadts-matter-for-performance... and https://blog.janestreet.com/more-expressive-gadt-encodings-v... for why you'd sometimes want the behaviour in 2.

(I do agree, that that behaviour is a bad default.)

Yeah I wonder what the actual cost is of (2). I know the Standard ML compiler MLton takes the monomorphization (2) approach as well, with good success. I'm currently writing a toy SML compiler for fun, and I'm planning on doing the same, since you get better run time performance, assuming you're using that info to do unboxing.

Reply on news.ycombinator.com