[Idea]Levity and Levity polymorphism?

language design
1

Right now rust uses monomorphization to compile polymorphic function and this has several drawbacks:

  1. Bloated binary size
  2. Unable to compile polymorphic recursions
  3. Unable to compile higher-order polymorphic functions
  4. Slows compilation

An alternative would be to erase all type information and box all the polymorphic arguments, but this will impose performance penalties and can slow down tight loops significantly.

Haskell distinguishes boxed (e.g. Int, Bool) and unboxed types (e.g. Int#, Bool#) at the kind level (levity): boxed types (lifted types really, but we ignore the difference here) have the kind # where unboxed types have the kind Type. Distingusing boxed and unboxed types allow us to specialize polymorphic functions when needed, but it also requires us to generate different machine codes because of different calling conventions, write separate functions for boxed and unboxed types and causes other problems in the type system. This motivates us to abstract over levity with so-called levity polymorphism described in this paper.

Compiling polymorphic functions using type erasure has been proposed before, would it be possible to incorprate levity and levity polymorphism into rust? What are your thoughts?

1 Like
2

Am I understanding you correctly that you want functions/types that can accept impl Trait and Box<dyn Trait>?

If I'm not mistaken, since Box<dyn Trait> implements Trait, boxed trait objects can already be passed to polymorphic functions/types.

1 Like
3

Trait object cannot be used for parametrically polymorphic functions, No?

4

Oddly enough, Box<dyn Trait> doesn't automatically implement Trait. You have to explicitly write impl for that.

Then there's the annoying problem of not all traits being Object Safe. Once something is boxed, it's totally type-erased, and Rust will not monomorphize anything for it anymore, so you can't have generic methods.

Boxing also makes type unsized, so it can't use Self by value. That's merely Rust self-imposed limitation. Swift solves that by adding dynamic size and alignment info to the objects (what they call "witness tables").

5

I've bumped into that before. Is there any specific reason for that? It's rather counterintuitive given that Box implements plenty of traits given that T implements that same trait.

6

Because it's impossible to be generic over all traits, so you can write

impl<T: Read> Read for Box<T> {...}

But you can't write

impl<T: Read, TRAIT> TRAIT for Box<T> {...}

The confusing part is that calling trait methods on a Box often just works, because Box<T> implements Deref{Mut}.

1 Like
7

No type automatically implements a trait. You must explicitly write a implementation for each type.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f46e9ca78726f08917668cc9052c2085

(I guess the compiler could automatically generate these impls, but that would be unsound for some traits so it would be a bad ideaTM)

8

I think it would indeed be hard to implement without various type-level features such as Type : Type and kind polymorphism.

9

I think the main issue is object safety. If we could make more traits object safe, that would solve most problems.

The only solution I'm aware of is auto-boxing. This could use the box keyword:

trait Foo {
    box fn display<D: Display>(&self, d: D);
    box fn display_ref<D: Display>(&self, d: &D);
}

impl<T: Foo> Foo for Box<T> { ... }

When the trait is used normally, it uses monomorphization. However, when it's converted to a trait object, it has the following methods:

trait Foo {
    fn display(&self, d: Box<dyn Display>);
    fn display_ref(&self, d: &dyn Display);
}

Note that auto-boxing is not necessary when the generic type is already behind a reference or in a pointer-type such as Box or Rc.

Owned self arguments and Self return types would also need to be boxed. However, AFAIK you can't move ownership out of a Box (it has no into_inner() method), so that doesn't work. As pointed out by @H2CO3, this can work.

I think we could also allow trait objects with functions without a self argument, if we had syntax for calling them.

10

You can, by dereferencing it.

Please let's not pull in more function modifier syntax for that. Functions are already too heavy on modifier keywords (e.g. pub(crate) async extern "C" fn foo() is legal).

Furthermore one might not want Box to be used for Sized-ing the trait object. There are several other alternatives, e.g. &dyn Trait, &mut dyn Trait, Rc<dyn Trait>, etc.

Possible, probably yes. (Although I'm pretty sure there will be several unforeseen caveats which can't be trivially resolved). However, it feels really artificial because the language is so uniform, it can, as a first approximation, do anything with any type.

For example, primitive types can have methods and be extended via user-defined traits, just like complex user-defined types. And then there's the fact that dynamic ("heap") allocation is always explicit in Rust, and heap-allocating types are not considered special, they are only considered "containers". So introducing a whole new dimension to the type system based on whether or not something dynamically allocates would make no more sense to me than introducting a dimension based on whether or not it performs arithmetic, for example.

By the way, making every trait object automatically implement the corresponding trait would help (and make sense in my view), and currently I believe it could work for &T, &mut T and Box<T> without adding much because these types are already special (&T and &mut T are builtin types and Box is a lang item).

However, there are two problems:

  1. wouldn't this be a breaking change?
  2. it wouldn't work for all the other smart pointer and wrapper types, e.g. Rc<T>, without making them into lang items or introducing a whole new can of worms feature for generalizing over all traits (HKT or HKT-ish).
11

I completely forgot that! That means that a function accepting self or returning Self could use auto-boxing as well.

That's why my idea was to only use Box if necessary. See the 2nd trait method from my example:

box fn display_ref<D: Display>(&self, d: &D);
// is converted to
fn display_ref(&self, d: &dyn Display);

However, that means that box might not be the best name for the feature.

FFI functions shouldn't be generic, so combining extern "C" with box will never happen in practice. Besides, modifiers are not a bad thing. It's better to be explicit with things like this.

12

Well, they are not "bad" in isolation, but as I demonstrated it's already possible to pile a lot of modifiers upon each other, which starts to hinder the readability of function signatures.

I didn't imply at all to make boxing implicit, that would be even worse, I agree. To clarify, I don't think we should do this autoboxing.

13

This could be abstracted over with traits:

pub trait Inherit: Deref {}

pub trait InheritMut: Inherit + DerefMut {}

pub trait InheritIntoInner: Inherit {
    fn into_inner(self) -> <Self as Deref>::Target;
}

Then Rust could automatically implement traits for wrapper types, if the traits are implemented for <Self as Deref>::Target.

The problem with types like Rc is that you can't move out of them, so they can inherit PartialCmp, but not Read or IntoIterator.

1 Like
14

This would be unsound for some traits (think unsafe traits that happen to be object safe.) For example, Send. (Or similar unsafe traits). It would be unsound to just mark &T: Send. Now, we could make workaround, for unsafe traits, but this doesn't seem like a good plan. (makes things less orthogonal). It may also be undesirable for some safe traits, so I wouldn't want this.

1 Like
15

Oh, yes, that's right. To be clear, I wouldn't actively want something like this, either, I was just trying to think of less radical alternatives to autoboxing.

1 Like
16

Some interesting discussion about that here: Permit `fn(self)` methods to be invoked on object types · Issue #10672 · rust-lang/rust · GitHub

17

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.