The basic idea is traits/type classes and modules a la ML both have their advantages, and it is possible to have the best of both worlds. I choose to put this here rather than RFC as it is not concrete enough, and I’d like some feedback before I make my first RFC. If this is “cheating” or otherwise frowned upon, my apologies.
First, let me link www.mpi-sws.org/~dreyer/papers/mtc/main-long.pdf where this idea basically comes from. It seems like Ocaml Labs is currently working on adding this to OCaml under the name “Modular Implicits”
Second, I believe the changes proposed by @glaebhoerl in https://github.com/rust-lang/rfcs/pull/135#issuecomment-47713550 are a prerequisite to any progress in this arena.
To summarize the paper: Traits are modular signatures, and trait implementations are modules. The key to type classes is the coherence rules mean that there is exactly one implementation per Sig, so that the compiler can route the required instances to functions that need them (and in Rust’s cases inline/monomorphize everything). ML modules and traits are are combined by “separat[ing] the definition of an instance from its adoption as a canonical instance”. Programmers can create as many impls as they want, but they only offer one per scope to the compiler for propagation.
My only interesting change to what they propose in the paper is to represent traits today as
Type -> Sig, rather than
Sig. This better distinguishes between “input” and “output” types, which are / should be a keep part of the coherence definition and instance resolution algorithm.
Why add to Rust?
I can think of two reasons:
The first is with things like libstd facade, and https://github.com/rust-lang/rfcs/pull/185. The current system of putting undefined declarations in crates IMO makes for somewhat subtle-looking code in comparison to ML functors. The way errors aren’t caught until some sort of rlib link time also reminds me of one of the most obvious disadvantages of templates vs traits, in that one isn’t aware of any problems until “downstream” in build process.
The second is for allocators. As far as I can tell from trying to find previous discussion of the topic is basically sometimes one wants to statically define what allocator is used, e.g.
Box<T, LibcMalloc>, and sometimes one wants it to be determined dynamically, with the allocator vtable, and perhaps some extra allocation metadata, as extra fields. Of course nobody wants to have to duplicate their allocator code to support both use-cases.
This sounds a lot like the problem trait objects solve, and I thought a while about how trait objects could be used to hack this together with things like https://github.com/rust-lang/rfcs/pull/9, and defining a bunch of unit types for each allocate instance. But everything I could think of seemed like hacks, and hacks that raise the bar for the implementation of allocators and result in lousy errors.
A better solution in my mind would be to define allocators as a parameter-less trait (Sig, not Type -> Sig like single - parameter traits). Then, give rust a better notion of existential types:
exists (<ID : SIG> | <ID>) TYPE. Normal “object types” desugar / are rewritten as
exists <T> (some-trait<T>, T). Boxes with dynamic allocators are defined something like
type DynAllocBox<T> = exists<A : Alloc>Box<T, A>.
Applying trait impls with
<IMPL> makes sense to me as a), trait implementations like types are “applied statically” in that all functions are monomorphized over trait and type arguments already, and b) in the conventional dependent type modelling of ML sigs as types in a higher universe, both sigs and and trait implementations are technically types. In a language like Rust, TYPE, each trait, (and arguably LIFETIME) are kinds. SIG itself would be a “super-kind”.
Lastly, let me add that I have much more Haskell than ML experience. I am sure somebody who has used ML modules systems more than I could enumerate many more advantages they would bring to Rust.
As far as I can tell the trait coherence rules only depend on the adaption of implementations as canonical implementations, so this could be done after 1.0 in a backwards-compatible way by adding a new syntax both for canonicalization, and definition without canonicalization. However I think this change would have far reaching implications in the way the libraries and interfaces are designed, so would be best do do this before 1.0.
Some other system could be devised where functors were
crate -> crate or
rust module -> rust module instead of
trait -> trait. Or do nothing of course.