5 ms·

> In general, for programming languages, there are two ways to translate a generic function: > 1. translate the generic function for each set of instantiated t

by platz 6y ago

> In general, for programming languages, there are two ways to translate a generic function: > 1. translate the generic function for each set of instantiated type parameters > 2. translate the generic function just once, calling each trait method through a function pointer (via a “vtable”). The approach in haskell might be considered a variation of 2, since it involves indirection, but a little different from other languages normally using vtables, since it's not selecting different implementations at run time, but just looking up the pre-determined implementation through a new parameter. In particular, the function is transformed into a higher-order function accepting a new parameter representing the dynamic to_string functinoality, then at the call site, the appropriate concrete implementation to_string parameter is inserted for the new transformed function, and similarly this new higher-order function 'print' only needs to be compiled once.

whateveracct 6y ago
One thing to note is Haskell is exceptionally good at inlining that explicit dictionary away. Haskell isn't 0-cost-abstraction like Rust ofc, but it is definitely a minimize-the-cost-of-abstraction. And the control over said minimization is getting better with each release.
- zenhack 6y ago
  Also worth noting that Haskell's type system is too powerful for monomorphization to work as an implementation strategy for generics in all cases. In particular, polyorphic recursion[1] means that attempting to just monomorphize anything wouldn't necessarily terminate. Higher rank types also break this, as you can define things like: newtype GenericThing = GenericThing (forall a. [a] -> a) doManyGenericThings :: [GenericThing] -> [a] -> [a] doManyGenericThings things list = map (\GenericThing f -> f list) things Here, `doManyGenericThings` takes a list of generic functions, and applies each of them to its argument. You can't just monomorphize it, because you'd have to somehow also monomorphize every argument it is ever passed, which is a dynamic property that you can't know in advance (and again, may not be a finite set). [1]: https://en.wikipedia.org/wiki/Polymorphic_recursion https://en.wikipedia.org/wiki/Polymorphic_recursion
  - heavenlyblue 6y ago
    You should be able to prove that all places that call this function with a fixed list of fixed types are monomorphisable though.
    - zenhack 6y ago
      It is certainly possible to still monorphize some cases, but the point is it can't work as a comprehensive strategy like it does in rust; it's an optimization that applies in some cases.
- platz 6y ago
  It can't inline the dict in general though, and that is more the default situation than the opposite, unless the defn is in the same module
kccqzy 6y ago
How is a Haskell type class dict different from a vtable? It's in fact the same.
- tome 6y ago
  Hmm, not sure what you mean. In the body of a function there is one class dict available. On the other hand there is one vtable per object, typically.
  - richardwhiuk 6y ago
    In C++ and Rust, there's a single vtable per class (trait), not per object. (This is basically why Rust doesn't support multi-trait types (e.g. &dyn Debug + Clone)
    - estebank 6y ago
      You can accomplish the same behavior by having a marker trait: trait Foo: Debug + Clone {} Edit: No you can't, because `Clone` requires `Sized`, which means you can't make a trait object of `Foo`. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=252fbe402fe80be54816667afc5c62f3 https://play.rust-lang.org/?version=stable&mode=debug&editio...
  - ImprobableTruth 6y ago
    I don't know of a single language that has a vtable per object. What would even be the point? Edit: Assuming we're talking about objects that can be grouped into some sort of 'classes'.
    - gpderetta 6y ago
      Isn't python __dict__ pretty much a per-object vtable?
  - tome 6y ago
    I see I wasn't clear enough. With object-style polymorphism, the vtable is looked up on the object, using some means or other. With typeclass-style polymorphism, the "vtable" is (effectively) looked up on the type. Perhaps gpderetta said it better: https://news.ycombinator.com/item?id=23537639 https://news.ycombinator.com/item?id=23537639
cma 6y ago
Sounds like static polymorphism, done in C++ with: https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern https://en.wikipedia.org/wiki/Curiously_recurring_template_p...

by platz 6y ago

whateveracct 6y ago

One thing to note is Haskell is exceptionally good at inlining that explicit dictionary away. Haskell isn't 0-cost-abstraction like Rust ofc, but it is definitely a minimize-the-cost-of-abstraction. And the control over said minimization is getting better with each release.

zenhack 6y ago
Also worth noting that Haskell's type system is too powerful for monomorphization to work as an implementation strategy for generics in all cases. In particular, polyorphic recursion[1] means that attempting to just monomorphize anything wouldn't necessarily terminate. Higher rank types also break this, as you can define things like: newtype GenericThing = GenericThing (forall a. [a] -> a) doManyGenericThings :: [GenericThing] -> [a] -> [a] doManyGenericThings things list = map (\GenericThing f -> f list) things Here, `doManyGenericThings` takes a list of generic functions, and applies each of them to its argument. You can't just monomorphize it, because you'd have to somehow also monomorphize every argument it is ever passed, which is a dynamic property that you can't know in advance (and again, may not be a finite set). [1]: https://en.wikipedia.org/wiki/Polymorphic_recursion https://en.wikipedia.org/wiki/Polymorphic_recursion
- heavenlyblue 6y ago
  You should be able to prove that all places that call this function with a fixed list of fixed types are monomorphisable though.
  - zenhack 6y ago
    It is certainly possible to still monorphize some cases, but the point is it can't work as a comprehensive strategy like it does in rust; it's an optimization that applies in some cases.
platz 6y ago
It can't inline the dict in general though, and that is more the default situation than the opposite, unless the defn is in the same module

kccqzy 6y ago

How is a Haskell type class dict different from a vtable? It's in fact the same.

tome 6y ago
Hmm, not sure what you mean. In the body of a function there is one class dict available. On the other hand there is one vtable per object, typically.
- richardwhiuk 6y ago
  In C++ and Rust, there's a single vtable per class (trait), not per object. (This is basically why Rust doesn't support multi-trait types (e.g. &dyn Debug + Clone)
  - estebank 6y ago
    You can accomplish the same behavior by having a marker trait: trait Foo: Debug + Clone {} Edit: No you can't, because `Clone` requires `Sized`, which means you can't make a trait object of `Foo`. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=252fbe402fe80be54816667afc5c62f3 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- ImprobableTruth 6y ago
  I don't know of a single language that has a vtable per object. What would even be the point? Edit: Assuming we're talking about objects that can be grouped into some sort of 'classes'.
  - gpderetta 6y ago
    Isn't python __dict__ pretty much a per-object vtable?
- tome 6y ago
  I see I wasn't clear enough. With object-style polymorphism, the vtable is looked up on the object, using some means or other. With typeclass-style polymorphism, the "vtable" is (effectively) looked up on the type. Perhaps gpderetta said it better: https://news.ycombinator.com/item?id=23537639 https://news.ycombinator.com/item?id=23537639

cma 6y ago

Sounds like static polymorphism, done in C++ with: https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern https://en.wikipedia.org/wiki/Curiously_recurring_template_p...