On Nov 25, 2011, at 8:06 AM, Marijn Haverbeke wrote:
> Niko proposed categories [1] two weeks ago. I'm happy that we're
> looking in this direction. Niko's proposal makes interfaces
> structural. I'm going to argue that nominal interfaces have advantages
> both in programmer ergonomics and in compilation-model complexity.
The sense I got was that most everyone prefers a move towards almost everything
being nominal. Niko's proposal does not depend on being structural; IIRC he
wrote it that way primarily to stay closer to the current object system.
> I'll be sticking rather closely to Haskell's type class system, which
> has proven itself in practice.
Well, it's not without its issues. Some of the problems relate to inference and
are therefore not an issue for us, but others are more serious. The most
important issue I see is that instance declarations are anti-modular: if
multiple modules have conflicting instance declarations, the program can't be
compiled. Anything we do in this space should address this issue.
> Context: I'd like to implement some minimum viable dynamic dispatch
> system and get rid of our `obj` implementation before the first public
> release. Something that can be extended later with classes and traits,
> but for now just allows us to define vtables that accompany types.
If there's internal work needed for vtables, it makes sense to work on that.
But we don't need to hurry to get new user-facing features in for the first
release.
> Alternatively, my proposal looks like this: interfaces could be fixed
> groups of methods, that are always implemented all at once.
>
> // Define an interface called `seq`
> interface seq<T> {
> fn len() -> uint;
> fn iter(f: block(T));
> }
> // Declare [T] to be an instance of seq
> instance [T] seq<T> {
> fn len() -> uint { vec::len(self) }
> fn iter(f: block(T)) { for elt in self { f(elt); } }
> }
>
> The static way to use this would look the same as above. If you've
> imported `vec::seq` (std::vec's implementation of seq), you can simply
> say [1].len(). If there is any instance in scope that applies to type
> [int] and has a method `len`, that instance's implementation is
> called.
What would you do with multiple instance declarations that differ by
specificity? For example, one declared on [int] and one declared on [T].
> If multiple interfaces are found, the one in the closes scope
> is chosen. If they are in the same scope, or no interface is found,
> you get a compiler error.
Conflict resolution is often the place where the usability bugs show up in
systems with overloading. You want (a) to avoid having automatic resolution
rules that are too strict, but (b) to avoid having automatic resolution rules
that are too subtle, and then (c) to make sure there's some sort of lightweight
syntax for explicitly resolving ambiguous/failed resolutions.
> Dynamic dispatch works differently.
>
> // Declare T to be an instance of the seq interface
> fn total_len<T:seq>(seqs: [T]) -> uint {
> let cnt = 0u;
> for s in seqs { count += s.len(); }
> count
> }
>
> In this proposal, the seq vtable is not something that get attached to
> the value by casting it to an interface, but rather acts as an
> implicit parameter to the function. The cool thing is that we already
> have these implicit parameters -- they map very closely to our type
> descriptors, which we are implicitly passing to generics.
Haven't we been talking about eliminating type descriptors, in particular for
monomorphization? I haven't been close enough to that topic to fully understand
the trade-offs, but I know that Patrick believes we will need to monomorphize.
If we do, I would imagine one approach is simply to hard-wire each specialized
copy of a function to specific vtables. Another is to say that we don't
specialize bounded type parameters, but that's strange and asymmetric.
This comes down to the different implementation approaches polymorphism.
Monomorphizing is rare in the ML/Haskell tradition, so type classes with
dictionary-passing is a nice fit. But it's not as clear what happens to type
classes when you introduce specialization.
> It should be noted that this has both advantages and disadvantages
> compared to the 'wrap by casting to interface approach'. For one
> thing, it doesn't allow this
>
> fn draw_all<T: drawable>(shapes: [T]) { for s in shapes { s.draw(); } }
>
> .. or at least, it doesn't do what you want, because it requires all
> arguments to be of the same type, and only passes a single vtable. An
> extension can be implemented (at a later time), to support this
> instead:
>
> fn draw_all(shapes: [drawable]) { ... }
> draw_all([my_circle as drawable, my_rectangle as drawable]);
This corresponds to where the implicit "forall" occurs in the type:
forall drawable T.([T] -> unit)
[forall drawable T] -> unit
GHC allows both, but the second one requires an explicit forall.
> With a Sufficiently Smart Inliner, we could even do arithmetic with
> methods, and get operator overloading for free (see Haskell's Num type
> class), and allow things like generic implementations of sum, average,
> and similar numeric operations over sequences of `T: num` type.
Overloaded arithmetic is definitely a pleasant aspect of Haskell's type
classes. But they do exploit type inference pretty heavily. For example,
literals have polymorphic types, and expressions can be given different types
based on the expected type of their context. Have you thought about how this
would look in our system, where inference is more limited?
> Our type parameter bounds, `copy` and `send`, could become interfaces,
> with suitable implementations in the standard library. Copying of
> generic types would be forbidden, but `copy` would be a method of the
> `copy` typeclass, so you could say `copy(elt)` if you declared your
> type parameter with a `: copy` bound.
If this worked, it might be the biggest win of type classes. Specifically: if
we can squeeze all notions of type bounds in the entire language to just one
concept (type classes), then that would be a big win for conceptual simplicity.
I'm not sure yet I understand how this works. For example, how do we prevent
programmers from declaring some things to be instances of `send` that aren't
supposed to be?
> Implementing a system like this in its simple form is not terribly
> hard, especially since we already have tydescs implemented. Making it
> as powerful as Haskell's requires some extensions (most importantly:
> default implementations of methods, and interfaces that are
> parameterized with other interfaces), but those can be tackled
> piecemeal. There's even a credible path towards multiple dispatch
> (methods dispatching on the type of more than one argument), though it
> requires a more complicated interface-dispatching mechanism.
It would help if you could flesh this out more in a wiki proposal.
> I'd like to spend next week implementing this.
Is that a good way to proceed? When we have new proposals, we need to get the
group on board before jumping in with both feet. A full proposal needs more
than an overview email, and it needs to be fleshed out, integrated into the
rest of the design, etc. We should discuss how this does or doesn't fit in with
objects, classes and traits, what consequences monomorphization would have on
it or vice versa, etc etc. And IINM, there are still blockers that are
well-established and fundamental, like stack growth and x64, no?
Dave
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
