[rust-dev] Implementation of traits in Rust: could it be dynamic?

Patrick Walton pcwalton at mozilla.com
Fri Jul 25 20:26:24 PDT 2014


On 7/25/14 8:10 PM, Lionel Parreaux wrote:
> Oh I'm sorry I completely missed your message, because I was not
> subscribed to the list.
>
> Thanks for the explanation. I do realize that this is the tough part,
> compared to a system like Haskell where everything is boxed.
>
> It's interesting to hear that this is how it was (meant to be) done in a
> previous version of Rust. Could you expand on the sources of the
> difficulties met trying to implement it? (Or just give me a pointer to
> some material about it.)

Basically it got really complicated when you had things like:

     fn f<T:Copy>(x: T) {
         if ... {
            f((x,x,x));
         }
     }

Not only did we have to have the notion of a "type descriptor" which was 
passed at runtime, because of generics-constructed-out-of-other-generics 
we had to have the notion of a "derived type descriptor" which was a 
type descriptor constructed at runtime on the stack, which formed a 
singly linked list of type descriptors (so that you could find 
destructors for the original types).

Additionally, the requirement that we have to follow C alignment rules 
meant that accessing field N of a struct was actually an O(n) operation, 
since there's no closed-form way to calculate alignment of a struct at 
length N.

These two were the biggest problems.

> I'm interested, because I'm working on a research language without GC
> and without boxed allocation semantics, so this kind of things come up.

Have you seen these notes from Greg Morrisett? 
http://www.eecs.harvard.edu/~greg/cs256sp2005/lec15.txt

They were very helpful for us. I have a few minor quibbles (for example 
I don't think the hazards of infinite template instantiation via 
polymorphic recursion are that big of a deal in practice, whereas those 
notes seem to consider it a deal-breaker). What I do agree with is that 
the best way to do generics if you have non-uniform value 
representations is to JIT each template instantiation as you come to it 
(like .NET does). This is basically the best of all worlds. However, it 
requires a JIT; if you don't have a JIT, I think the best thing is what 
Rust currently does. Uniform value representations work well too (as 
OCaml shows), but of course you'll pay a performance cost for that.

Patrick



More information about the Rust-dev mailing list