Hacker News Reader

Comment by platz | Hacker News Reader

> 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.

View on HN

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.

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

You should be able to prove that all places that call this function with a fixed list of fixed types are monomorphisable though.

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.

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

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

How is a Haskell type class dict different from a vtable?

It's in fact the same.

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.

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)

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&editio...

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'.

Isn't python __dict__ pretty much a per-object vtable?

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

One way is that it can handle functions like return : Monad m => a -> m a where m occurs only in the outputs. There's no input arg you could hang a vtable off of.

In c++ vtables ptrs are attached to object instances (although all instances of the same type vtable), while AFAIK in Haskell "vtables ptrs" (better known as function dictionaries) are attached to object pointers (also known as fat pointers). I believe that rust impl traits behave similarly to Haskell. I think go interfaces also use fat pointers.

The advantage is that "interfaces" can be attached to objects non intrusively (and outside of that object declaration, which is a huge win for interoperability), the disadvantage is that pointers are larger and there is no easy way to cross cast between interfaces.

In c++ "fat pointers" (also sometimes known are virtual concepts) are often implemented manually, the most well known example is std::function. We are all waiting for compile time reflection to be able to implement virtual concepts generically (you can only approximate it up to a point currently).

If you have

    Obj f(Obj a, Obj b);

in C++, you pass in Obj's vtable twice, and the returned value includes a vtable.

If you have

    f :: Obj a => a -> a -> a

in Haskell, you pass in one dictionary. If you have

    f :: (Obj a, Obj b) => a -> b -> a

in Haskell, you pass in two dictionaries. If you have

    f :: (Obj a, Obj b, Obj c) => a -> b -> c

you pass in three dictionaries, and the caller gets to decide what the concrete type of c is, NOT the function implementation.

    data DynObj = forall c. Obj c => DynObj c
    f :: (Obj a, Obj b) => a -> b -> DynObj

In this case, you pass in two dictionaries and the returned value has a vtable. This essentially is what C++ does.

Reply on news.ycombinator.com