5 ms·

Haskell and Rust both require monomorphization, right? That's one thing the JVM doesn't require. You do pay a performance penalty for megamorphic code (http://i

Haskell and Rust both require monomorphization, right? That's one thing the JVM doesn't require. You do pay a performance penalty for megamorphic code (http://insightfullogic.com/2014/May/12/fast-and-megamorphic-what-influences-method-invoca/ http://insightfullogic.com/2014/May/12/fast-and-megamorphic-...) but it's still a difference in what's allowed. I also don't understand what you're saying with regard to V8. Can the optimizing AOT compiler actually do enough optimizations on a language as dynamic as JS?

kibwen 11y ago
I'm not sure what you're getting at regarding monomorphization, can you elaborate? What do Haskell or Rust have to do with this (and I don't think Haskell even does monomorphization)?
bjourne 11y ago
Sure, megamorphic code requires a JIT. But it's a trivial one so I don't count it. :) Essentially, if you have the expression: z = x + y If you statically can't know the types of x and y, you must do an expensive method lookup. You call some variant of the plus function if x and y are floats, another if they are strings or lists and so on. So a good runtime notes the types of x and y the first time the expression is evaluated and recompiles the expensive call to the general_add() function with, say if x and y are 32 bit ints, a quick add_32bit_ints() call. See here for a description of the V8 JIT: http://jayconrod.com/posts/54/a-tour-of-v8-crankshaft-the-optimizing-compiler http://jayconrod.com/posts/54/a-tour-of-v8-crankshaft-the-op... It appears to be just "a plain old compiler" with inlining of method lookups.
steveklabnik 11y ago
Rust lets you choose between monomorphization (trait bounds) and vtables (Trait objects).
- jules 11y ago
  The semantics of those are different. With trait objects the vtable is attached to the value. You could instead imagine a language with two types of trait bounds: one specialized statically (like Rust trait bounds), and the other handled dynamically (like type classes in Haskell). The semantics of these would be identical (vtable travels independently of values), the only difference is performance. I'm not sure if you'd ever want Haskell's implementation strategy in practice though, unless you want to support features that can't be supported by static specialization like polymorphic recursion or higher rank polymorphism (not to be confused with higher kinds). Interestingly C# does support those features and specialization because it specializes at run time. It's a less known very powerful feature, at least in theory :) You can abuse it to make the CLR generate arbitrary code at run-time.
  - Jweb_Guru 11y ago
    In what way does the vtable being attached to the value cause different semantics (what you describe sounds like an implementation detail)? In particular, you can have Box<TraitObject> which has effectively identical semantics to TraitObject; yes, it's a fat pointer, but from the perspective of the trait itself there's no way to tell that this is the case. Anyway, the only ways I can think of to usefully differentiate the fat from a thin pointer in a parametric function are those in which Rust already fails to have proper parametricity for any type (including being able to access its type_id).
    - jules 11y ago
      Steve Klabnik was not talking about Box<TraitObject> vs TraitObject, but about f(x:TraitObject) vs f<T:TraitObject>(x:T). In the former the vtable is attached to the value, in the latter the vtable travels separately. These do have different semantics, compare f<T:TraitObject>(x:Vec<T>) with f(x:Vec<TraitObject>). In the x:Vec<T> case there is a single vtable that gets passed to the function, and all elements of the vector share that same vtable. With x:Vec<TraitObject> each element of the vector has its own vtable. In terms of pseudo Haskell types these two types would be: TraitObject t => List t -> Result List (exists t. TraitObject t) -> Result Rust cleverly sweeps the existential under the rug.
      - Jweb_Guru 11y ago
        Again, in what way is the use of fat pointers a semantic difference, outside of parametricity-breaking functions like size_of_ty and type_id? You are describing an implementation detail. I can think of times that the compiler should be able to desugar the fat trait objects into thin ones in the absence of a Reflect bound.
        jules 11y ago
        As I explained, the difference is that in one case you have one vtable per object in the vector, in the other case you have one vtable for the whole vector. With one vtable per object you can have one vector containing objects of two different types that implement the same trait with a different vtable. With one vtable for the whole vector you cannot. The same difference exists in many languages, e.g. C# List<IFoo> vs List<T> where T:IFoo.

kibwen 11y ago

I'm not sure what you're getting at regarding monomorphization, can you elaborate? What do Haskell or Rust have to do with this (and I don't think Haskell even does monomorphization)?

bjourne 11y ago

Sure, megamorphic code requires a JIT. But it's a trivial one so I don't count it. :) Essentially, if you have the expression: z = x + y If you statically can't know the types of x and y, you must do an expensive method lookup. You call some variant of the plus function if x and y are floats, another if they are strings or lists and so on. So a good runtime notes the types of x and y the first time the expression is evaluated and recompiles the expensive call to the general_add() function with, say if x and y are 32 bit ints, a quick add_32bit_ints() call. See here for a description of the V8 JIT: http://jayconrod.com/posts/54/a-tour-of-v8-crankshaft-the-optimizing-compiler http://jayconrod.com/posts/54/a-tour-of-v8-crankshaft-the-op... It appears to be just "a plain old compiler" with inlining of method lookups.

steveklabnik 11y ago

Rust lets you choose between monomorphization (trait bounds) and vtables (Trait objects).

jules 11y ago
The semantics of those are different. With trait objects the vtable is attached to the value. You could instead imagine a language with two types of trait bounds: one specialized statically (like Rust trait bounds), and the other handled dynamically (like type classes in Haskell). The semantics of these would be identical (vtable travels independently of values), the only difference is performance. I'm not sure if you'd ever want Haskell's implementation strategy in practice though, unless you want to support features that can't be supported by static specialization like polymorphic recursion or higher rank polymorphism (not to be confused with higher kinds). Interestingly C# does support those features and specialization because it specializes at run time. It's a less known very powerful feature, at least in theory :) You can abuse it to make the CLR generate arbitrary code at run-time.
- Jweb_Guru 11y ago
  In what way does the vtable being attached to the value cause different semantics (what you describe sounds like an implementation detail)? In particular, you can have Box<TraitObject> which has effectively identical semantics to TraitObject; yes, it's a fat pointer, but from the perspective of the trait itself there's no way to tell that this is the case. Anyway, the only ways I can think of to usefully differentiate the fat from a thin pointer in a parametric function are those in which Rust already fails to have proper parametricity for any type (including being able to access its type_id).
  - jules 11y ago
    Steve Klabnik was not talking about Box<TraitObject> vs TraitObject, but about f(x:TraitObject) vs f<T:TraitObject>(x:T). In the former the vtable is attached to the value, in the latter the vtable travels separately. These do have different semantics, compare f<T:TraitObject>(x:Vec<T>) with f(x:Vec<TraitObject>). In the x:Vec<T> case there is a single vtable that gets passed to the function, and all elements of the vector share that same vtable. With x:Vec<TraitObject> each element of the vector has its own vtable. In terms of pseudo Haskell types these two types would be: TraitObject t => List t -> Result List (exists t. TraitObject t) -> Result Rust cleverly sweeps the existential under the rug.
    - Jweb_Guru 11y ago
      Again, in what way is the use of fat pointers a semantic difference, outside of parametricity-breaking functions like size_of_ty and type_id? You are describing an implementation detail. I can think of times that the compiler should be able to desugar the fat trait objects into thin ones in the absence of a Reflect bound.
      - jules 11y ago
        As I explained, the difference is that in one case you have one vtable per object in the vector, in the other case you have one vtable for the whole vector. With one vtable per object you can have one vector containing objects of two different types that implement the same trait with a different vtable. With one vtable for the whole vector you cannot. The same difference exists in many languages, e.g. C# List<IFoo> vs List<T> where T:IFoo.