Hello list,
I have some ideas about typey things and I'm going to write them down. It
will be long.
It would be nice if `Trait1 + Trait2` were itself a trait, legal in the
same positions as any trait. This is already partly true: in trait bounds
on type parameters and super-traits of traits. Where it's not true is trait
objects, e.g. `~(ToStr + Send)`. Having this could remove the need for the
current `~Trait:OtherTraits` special syntax.
I wonder whether lifetimes could also be interpreted as traits, with the
meaning: "[object of type implementing lifetime-trait] does not outlive
[the given lifetime]". This is an honest wondering: I'm not sure if it
makes sense. If it does make sense, it would fit in perfectly with the fact
that 'static is already a trait. Together with the above, it might also
allow a solution for capturing borrowed data in a trait object: you could
write `~(Trait + 'a)`.
The next few are going to be about higher- (or just different-) kinded
generics. To avoid confusion, I'm going to use "built-in trait" to mean
things like `Freeze` and `Send`, and "kind" to mean what it does everywhere
else in the non-Rustic world.
I think the best available syntax for annotating the kinds of types would
be to borrow the same or similar syntax as used to declare them, with
either `type` or `struct` being the kind of "normal" non-generic types (the
only kind of type that current Rust lets you abstract over). [I prefer
`type`, because both structs and enums inhabit the same kind.] This is kind
of like how C++ does it. For example, the kind of `Result` would be
`type<type, type>`. Our `type` corresponds to C++'s `typename` and
Haskell's `*`, and `type<type, type>` to C++'s `template<typename,
typename> class` and Haskell's `* -> * -> *`. So, for example, you could
write the fully kind-annotated signature of an identity function restricted
to Result-shaped types (yeah, actually doing this would be pointless!) as:
fn dumb_id<type<type, type> R, type A, type B>(x: R<A, B>) -> R<A, B>;
To explicitly annotate the kind of the Self-type of a trait, we could
borrow the `for` syntax used in `impl`s. Here's the fully kind-annotated
version of the `Functor` trait familiar from Haskell:
trait Functor for type<type> Self {
fn fmap<type A, type B>(a: &Self<A>, f: |&A| -> B) -> Self<B>;
}
(Obviously, explicitly annotating every kind would be tiresome, and `Self`
is a little redundant when nothing else could go there. I could imagine
`trait Functor for type<type>`, `trait Functor for Self`, and/or `trait
Functor` all being legal formulations of the above. I'll get back to this
later.)
One question with regards to higher-kinded traits is what to do about
methods and `self`. What syntax to use? Does it even make sense? For
syntax, I see two possibilities (snipping from the `fmap` signature):
- `self: &Self<A>`
- `&self<A>`
I don't have a preference, but I'll be using the latter for now. And it
*does* make sense. Every trait over a `Self` with parameters of given kinds
gives rise to trait objects with parameters of the same kinds. Basically,
it's always the outermost type constructor that gets erased. In the trivial
case, the `Self` of `ToStr` does not have any parameters, and neither does
`~ToStr`. To see a less trivial case, let's write a variant of Haskell's
`Foldable`:
trait Foldable for type<type> Self {
fn fold<T>(&self<T>, init: &T, folder: |&T, &T| -> T) -> T;
}
Then `&Foldable<int>` is a trait object hiding any foldable container of
ints (for example `~[int]`). There should probably be a way to distinguish
the arguments of the trait from the arguments of Self: so perhaps that
should be something like `&Foldable<for int>` instead (but that doesn't
cleanly extend to more than one argument). An example of its use:
fn sum(vals: &Foldable<for int>) -> int {
vals.fold(&0, |a, b| a + b)
}
let n = sum(&[1, 2, 3] as &Foldable<for int>);
So far we've seen two sorts of kinds: the base kind `type`, and generic
kinds `type<...>`. Another very important one is lifetimes. And I can
imagine two more beyond these:
Like C++, types could be parameterized over constants. Again, the syntax
could mirror their declarations. For example, a function to construct a
fixed-length array:
fn make_n<static N: int>(n: int) -> ~[int, ..N] { [n, ..N] }
Interesting questions here include what types to allow, how or whether to
handle literals of various types as type arguments, and the constant
expression sublanguage.
The other is the potential to abstract over traits. GHC does this with the
`ConstraintKinds` extension. (According to people who have implemented
Haskell compilers, it's actually easier to implement it than not to![1]
Which is pretty crazy.) In that case, just to stick to trivial, useless
examples, and continue with parameter-syntax-follows-declaration, you could
write a generic alias for `Trait1 + Trait2` as:
trait And<trait A, trait B>: A + B { }
impl<trait A, trait B, type T: A + B> And<A, B> for T { }
[1]:
http://www.reddit.com/r/haskell/comments/10w3cx/ideas_for_a_library_that_uses_constraintkinds_to/c6h6di4
(I don't want to dive any more deeply into the motivations for and
complications of this feature here; I only wanted to mention the
possibility and demo the syntax.)
There's two further issues that higher-kinded generics raise. The first is
that in order for traits like `Functor` to be truly useful, you really want
currying and partial application at the type level. Otherwise, while you
can `impl Functor for` arrays and `Option`, you can't impl it for `Result`
and `HashMap`, which is a significant loss. Thankfully, there are no
difficulties regarding evaluation order at the type level, which is one of
the reasons that partial application syntax was removed at the value level.
I could imagine the syntax being something like this:
impl<K> Functor for HashMap<K, ..> { fn fmap etc. }
in which case `HashMap` is partially applied to `K`, and the remaining
parameters (only one in this case) are left hanging - and so the result is
of the `type<type>` kind that `Functor` expects (rather than the
`type<type, type>` kind of plain `HashMap`). What the above means is that
if you have a `HashMap`, you can make a new `HashMap` with the same keys
but different values of a potentially different type.
I expect that kind annotations would be legal anywhere a type parameter is
declared. The second issue is: in which cases would they be optional, in
which cases required, and what happens if you omit one? I see several
possibilities:
- If you omit a kind, it defaults to `type`. Any other kind must be
explicitly annotated. This is the simplest and dumbest option, and is
completely backwards compatible.
- If you omit a kind, it is inferred. If it can't be inferred, an error
is raised. This is not quite backwards compatible.
- If you omit a kind, it is inferred. If it can't be inferred, it
defaults to `type`. This is again backwards compatible with current Rust.
- If you omit a kind, it is inferred. If it is unconstrained, the
declaration is kind-polymorphic, meaning it works with any kind. I think
this is backwards compatible, but I'm not 100% sure. GHC has this with
`PolyKinds`. The absence of it is frequently annoying in C++ when writing
template-heavy code: you have to manually duplicate things for `typename`,
`template<...> class`, various non-type template parameters, and all the
combinations of these that you want, and it's impossible to get full
coverage with a finite number of declarations: you have to choose the ones
you want to support. Proposals to address this issue have been submitted to
the C++ standards committee. Similarly, in Haskell's case, they were forced
to have `Typeable1` ... `Typeable7` classes (the equivalent of our `Any`
trait) for kinds of a few selected arities, which will be collapsed into a
single `Typeable` in the next GHC, both reducing duplication and attaining
full coverage of every type of every kind.
Higher-kinded types are connected to dynamically sized types. In
particular, I think sized and unsized types should be *separate kinds*,
instead of using a built-in trait to distinguish them. Multiple
considerations support this:
- They are qualitatively different. Built-in traits are required only for
safety. You could imagine leaving one off, and it would still make sense,
it just wouldn't be safe. On the other hand, an unsized type in the wrong
place is close to nonsensical. Defining what kinds of types make sense in
what places is exactly what kinds are for. `[[int]]` doesn't make sense in
a similar way to how `let foo: HashMap`, `[Option]`, and `fn foo<T: int>`
don't make sense. In fact, this is precisely what GHC does: it has separate
kinds for boxed types (`*`), unboxed types (`#`), and trait bounds which in
Haskell are called constraints (`Constraint`).
- If `Sized` is a built-in trait, it re-raises questions about whether
trait bounds should be allowed on struct type parameters. If the
distinction is made at the kind level, this kind of problem goes away: type
parameters already have kinds.
- A `Sized` trait significantly increases the annotation burden. If the
distinction is made with kinds, on the other hand, they could be inferred
with the same kind inference algorithm used for all other kinds (supposing
support for different kinds and kind inference exists).
That still leaves the question of what the kind hierarchy should
specifically be. A first attempt might look something like this:
type { sized, unsized { array, trait } }
where kinds inside braces are subkinds of those outside. (Even GHC has
subkinds, so I hope subkinding is not a big problem.) I *think* that mostly
makes sense: the type parameter of an array would have `sized` kind; the
type parameter of a pointer type would have the most general `type` kind,
but its representation would be different for `sized` and `unsized`; and in
trait-bound positions things of `trait` kind would be accepted, but not
arrays. I haven't put much thought into the actual names and syntax for all
of these. (In particular, I don't think there's an actual use case for
specifying `unsized` or `array` kinds: they're just what you get if you
take the complement of `sized` and `trait`, respectively, relative to their
superkind.)
This gets more interesting if we also have struct inheritance, and structs
can be used as traits (with the meaning is-a-substruct-of). I haven't
thought about that possibility very much yet.
The next few are about generics and dictionaries (vtables). I'm at a
somewhat earlier stage in my thinking about this than about the other
things.
Current Rust has two things it can do with generics, traits and their
dictionaries:
- In the case of generic functions, traits are completely monomorphized
away: the implementations to call are all selected at compile time;
- Rust also has syntactic sugar for a form of existential types in the
form of trait objects, in which case a pointer to the trait's dictionary is
packaged along with a pointer to the object, and the implementation to call
is determined at runtime.
I think there are a few other directions that could be explored. In recent
blog posts[2][3] Niko Matsakis mentioned the possibility for closures which
are generic over a lifetime (not top-level functions, but closures!) --
meaning that the lifetime(s) the closure will be invoked with are not known
until runtime. This works because the representation of the closure does
not depend on the lifetime: that information is completely erased during
compilation. The basic idea in all of the following is that lifetimes
aren't the only thing which don't affect representation: neither do the
type arguments to pointer-like types! [Let's pretend for now that only
sized types exist.] This opens the possibility of generic closures
parameterized over *types*, provided those types are only used as arguments
to pointer-like types. This corresponds to pointers to function templates
in C++ (which are notable for being occasionally desired but impossible),
and to higher-rank types in Haskell. For example, a generic closure
representing the identity function restricted to owned pointers would have
the type:
for<T> |x: ~T| -> ~T
Here I'm using our ever-versatile `for` keyword to introduce the type
parameter list, which I think reads better than the plain `<T> |x: ~T|`
style from Niko's blog posts (and tracks Haskell's use of `forall` for the
same purpose). So far so good: a closure of the above type will indeed have
the same representation no matter what type it's used with. But there's a
wrinkle: what if there are trait bounds on the type parameter? Then the
closure will have to call different trait methods depending on which type
is used, seeming to require different representations for each. There's a
way out: pass a pointer to the trait dictionary (vtable) as a hidden
argument to the closure, and make calls to trait methods (and associated
functions) through that pointer. This is analogous to how pointers have a
hidden pointer-to-vtable field when they are pointing to trait objects.
(Incidentally, the fact that pointers have the same representation
regardless of the type they are pointing to is also what allows
pointers-to-trait-objects to work at all.) In both cases, this happens to
be the same thing that GHC does. There are few more interesting questions
and wrinkles this raises:
- Looking at the above generic closure, what if it did not return its
argument, but let it go out of scope? Then it would have to invoke the
destructor for the given type - which again varies depending on which type
it is! This points back to the fact `Drop` really is an honest-to-god
trait, and it's not just a superficial syntactic resemblence. The reason
`Drop` is so weird is that, in effect, there's an implicit `impl` of it for
every type (when there isn't an explicit one), which does nothing, and it's
present as an implicit trait bound on every type argument. (You could
imagine it working like any other trait, and requiring an explicit `Drop`
bound in any generic function where an object of that type is destroyed
(transitively), but that would be super-annoying which is presumably why we
don't do it.) In any case, to make this example work, we would have to pass
a pointer to the `Drop` dictionary for the type as a hidden argument to the
closure, the same as with other traits. (This is similar to the issues with
owned pointers and struct inheritance from another of Niko's blog posts[4],
though I'm not sure what it teaches us.)
[2]:
http://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
[3]:
http://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
[4]:
http://smallcultfollowing.com/babysteps/blog/2013/10/24/single-inheritance/
- There's the question of how to actually codify which generic function
types are legal and which ones aren't. For example, `for<T> |x: T| -> T`
and anything else which uses a generic argument unboxed should not be
legal. This feels like another thing that the kind system should handle,
but I'm less sure about exactly how. At first, there's a seductive
possibility: what if all types introduced in a `for<>` were considered
unsized? In a sense this is literally true: because the type is not known
until runtime, neither is its size, and unsized types can only be
manipulated through pointers, which is what we want. I'm not sure if it
completely works out, though. For one thing, unlike "normal"
pointers-to-unsized types, here pointers to these "pseudo-unsized" types
are still only a single word, they don't have hidden pointer-to-dictionary
fields (which are passed as hidden arguments to the closure, instead).
Perhaps if the sizedness of a type were treated separately from whether it
carries a dictionary, this could be made to work out (for example, `Send`
and `Freeze` don't have dictionaries either), but it's not clear how that
might be done. The other issue is that this seems too restrictive for the
return types of functions. Rust writes out the return value of a function
through a hidden pointer that is passed in to the function, so it seems
like it should be possible to have closures which return a generic value
"unboxed": while the closure does not know what type it is, the caller
does, so the caller can pass in a pointer to an appropriately-sized piece
of memory, and it would seem to all work out. For example, a type like
`for<T: Clone> |x: &T| -> T` would then be legal. And because values are
implicitly returned through pointers, there's no penalty to returning
values "unboxed", and so most Rust function do that, even if they take
their arguments by pointer: it would be a shame to exclude them all.
- Earlier I said "let's pretend for now that only sized types exist". It's
obvious why: the size of pointers can change depending on the *kind* of the
type they point to, which would invalidate the property we've been relying
on. In can imagine two remedies. One is in fact to simply restrict the type
parameters of generic closures to sized kinds. The other is to permit
different kinds of the programmer's choice, as long as they are used
consistently and not mixed. For example, `for<sized T> |x: ~T| -> ~T` and
`for<trait T> |x: ~T| -> ~T` would both be legal under this scheme, and
incompatible.
Let's look at a few more fun things you could do using similar tricks as we
used for generic closures. One is another classic example of something you
can't do in C++: virtual function templates. In Rust terms, this
corresponds to calling a generic method through a trait object pointer.
It's clear why C++ disallows this: function templates work by generating a
separate actual function for each instantiation of the template
(monomorphization), and virtual functions work by calling the function
through a pointer, and you definitely can't have a single pointer to an
arbitrary number of different functions template instantiations. Rust could
do mostly the same thing here as with generic closures: if the generic
arguments of the method are only manipulated through pointers, then
generate an additional "generic" instantion of the method where trait
dictionaries are passed as hidden arguments, and when calling the method
through a trait object, use this instantiation of it and pass in the
dictionaries. After that, the same considerations apply as for generic
closures, from above.
Another possibility is explicit existential types inside of structs. That
might look like this:
struct LeftFold<In, Out, 'a> {
type Seed,
initial: &'a Seed,
folder: |&Seed, &In|:'a -> Seed,
result: |&Seed|:'a -> Out
}
(This is borrowed from the blog post "Beautiful Folding" by "Quiz"[5].)
This represents a type which encapsulates and hides both the folding
function and accumulator of a left fold. You pass in values of type `In`,
it does the folding work behind the scenes, and you get out a value of type
`Out`. (See the blog post for more details). Again, the same restrictions
apply here to the use of the `Seed` type as to generic arguments of generic
closures and methods. (If you were to use it unboxed, the struct could not
be represented.) Another thing we could do with this, along with the
`trait` kind from earlier, is write out the representation of a trait
object pointer explicitly:
trait BorrowedObject<'a, trait Trait> {
type T: Trait,
object: &'a T
}
Here, the pointer-to-Trait-dictionary will be stored as a hidden field at
the end of the struct. This results in the same representation as for the
trait object pointers that are built-in to the language. (The `object`
field itself is only one word wide, the same as pointers to generic
arguments of generic closures.)
[5]: http://squing.blogspot.hu/2008/11/beautiful-folding.html
Finally, one more thing that could be supported in this way is polymorphic
recursion. The problem with polymorphic recursion in monomorphizing
languages is that it requires an infinite number of "template
instantiations" as the recursion descends, but if the representation of the
functions is the same no matter what type arguments they are used with,
then the problem goes away. Again, the same restrictions would apply as for
all of the previous examples.
The last few are about closures. I really like the observation originally
made by strcat (Daniel Micay) that closures are basically just trait
objects[6]. In effect, our current (recently introduced) closure type
corresponds to this (using much imaginary syntax):
trait FnMut<Args..., Ret> {
fn call(&mut self, Args...) -> Ret;
}
type |Args...|:'a -> Ret = &'a mut FnMut<Args..., Ret>;
Looking at it this way, it makes sense why these closures are move-only:
they mutate their environment, hence `&mut self`, which requires the
pointer to the trait object to also be `&mut`, which is move-only. (An
aside: wouldn't `&mut 'a T` perhaps be nicer than `&'a mut T`?) Our
recently introduced `proc` type corresponds to this:
trait FnOnce<Args..., Ret> {
fn call(self, Args...) -> Ret;
}
type proc(Args...) -> Ret = ~FnOnce<Args..., Ret>;
Finally, there's a third important possibility (the old `&fn`) which
neither of the above capture:
trait Fn<Args..., Ret> {
fn call(&self, Args...) -> Ret;
}
type &'a fn(Args...) -> Ret = &'a Fn<Args..., Ret>;
This corresponds to closures with an immutable environment, which can
therefore be freely copied. In addition, if you mix and match the traits
and pointer types, `~FnMut<Args..., Ret>` is also a useful point in the
space, allowing mutation of the owned environment; and so is `@Fn<Args...,
Ret>`, which is basically the type of closures in Haskell (if you don't
consider laziness), allowing arbitrary sharing of immutable environments
between closures.
[6]: https://github.com/mozilla/rust/issues/8622
The reason all of this is so cool is that it unifies the C++ practice of
using unboxed closures via an overloaded `operator ()` with the standard in
functional languages of having a single first-class function (boxed
closure) type. Like all other templates-plus-overloading in C++,
overloading the function call operator corresponds in Rust to using a
trait. Then if you add trait objects, boxed closures - the equivalent of
C++'s `std::function` - fall out for free! (With memory management of the
closure chosen by the client, unlike `std::function`.) Like C++, you could
`impl` these Fn traits for your own types, and like functional languages,
you have the liberty of using a single unified function type (boxed
closures). (Or, well, three, thanks to Rust's distinction between by-ref,
by-mut-ref, and by-val: but they're effectively subtypes of each other, in
the reverse order.)
The problem is that doing all of this by hand in Rust with user-defined
traits is super-awkward. There's no built-in support for variadic
arguments, so you have to simulate it with tuples, or define separate
`Fn0`, `Fn1`, .. `FnN` traits; you don't have literals, so you have to
write the closure `struct` by hand and `impl` the trait for it (just like
C++ before lambdas); you can't make stack closures with the stack frame
itself as the environment; and you don't get to use the function call
operator, but have to call the `call()` method. It would be nice if Rust
solved these by in fact overloading the function call operator on traits
such as these; had some kind of built-in syntax for the traits, to solve
the variadic and plain ugliness problems (my old idea was built-in
special-syntax `trait fn(T...) -> U`, `trait fn mut(T...) -> U`, and `trait
fn once(T...) -> U` at each arity, like tuples); and had closure literals
desugar to anonymous structs `impl`ing the appropriate trait (similarly to
C++ lambdas). Perhaps the current closure types could then also desugar to
the afore-mentioned things.
If you got this far: thanks for reading! (My condolences.) I hope any of
this proves to be useful in any way. I'd be happy to elaborate on anything
if anyone wants me to elaborate on it.
-Gábor
--
Your ship was destroyed in a monadic eruption.
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
