Too many type parameters, and complicated signatures

(This isn't a proposal, but a description of a common problem I have and ideas as to how the language can solve it. Maybe other people have this problem, too.)

The Setup

The following is an issue I've been running into a lot, which I wonder if the language could do something about. Let's consider an unhypothetical scenario:

I have a library. It does crypto. It can't pull in something like ring because it's meant to run on SOCs with crypto acceleration in silicon. Thus, I wind up defining dozens of traits with names like Rsa, Sha256, EccBuilder, and so on, which are related by way of associated types. So far, this is a pretty standard Rust abstraction.

The problem is that the entry point for the library now has something like a dozen type parameters that both I, the library author, and my users, need to type out. We can agree that the following is line noise:

impl<Sha256, Rsa, Ed25519, Hmac, Aes, Rng, ...> for ...
  where <lots and lots of bounds> { ... }

The "standard" solution is to write this all down as associated types of a trait:

trait Crypto {
  type Sha256: Sha256;
  type Rsa: Rsa;
  // ...
}

Implementing this trait is a lot of boilerplate and requires creating a single-use ZST, which isn't too terrible, but can be a bit rough to do when you want to capture impl type parameters:

struct MyCrypto<Rsa>(PhantomData(fn() -> Rsa));
impl<Rsa> Crypto For MyCrypto<Rsa> {
    type Sha256 = MySha;
    type Rsa = Rsa;
}

impl<Rsa> ... {
    fn foo() -> MyStruct<MyCrypto<Rsa>>; // Requires T: Crypto.
}

Of course, the real version of this is worse, with many more type parameters.


A Potential Solution

I want to make this kind of API more ergonomic. I run into it a lot in code I need to write, and I can imagine code that has a lot of injection points (something like petgraph comes to mind) also runs into this problem.

This problem reminds me of the problem that Java's anonymous classes solve, so I tried to take that idea, apply it to this problem, and take it to its logical concluison.

What I would like to be able to write would be something like this:

impl<Rsa> ... {
  fn foo() -> MyStruct<impl Crypto { type Rsa = Rsa; type Sha256 = MySha; }>;
}

The production impl $ident { $items } in type position is intended to desugar into:

// In "scratch space", at item scope.
struct $anon;
impl $trait for $anon {
  $items
}
// In type position.
$anon

Of course, if $items or $trait reference any names of types or lifetimes in scope, those should be captured as type parameters on $anon. In the example above, Rsa is captured from impl scope.

One could imagine that impl<'a> Trait<'a> { .. } would result in a type implementing for<'a> Trait<'a>.


As far as I know, this isn't the kind of thing we can really do with macros (locally), because it's not possible to inject a temporary scope in which to define items while in type position.

I also feel like this is a focused solution that only solves one problem. I'm not sure how something like this could be cleanly generalized.

This general problem reminds me of Scala's "type lambdas", though those are more in the space of "I have an HKT parameter, I want to make a type constructor that fits it on the spot". The syntax is as follows:

class Foo[T[_]] { .. } // Foo has kind (type -> type) -> type.
def x: Foo[[V] => Map[String, V]] // Curried application of Map[_, _]

This isn't the same kind of problem (since Rust doesn't, and seems unlikely to ever get, true HKTs), but it does dig into the problem space of "I need to define a fairly simple type on the spot". The solutions all feel like they want to be some kind of "block expressions, but for types". Both my "anonymous impl" and Scala's type lambdas feel like they're getting at this concept.

Thoughts? Maybe there's something useful here for improving the ergonomics of complicated, type-level code.

2 Likes

One woraround you can use for traits that only have associated types is to define a marker type like FooImpl below, and use it everywhere (no need to define a new struct for every function).

To make defining the zero-sized type for a particular trait more ergonomic, one can define a macro_rules! macro, or an attribute macro, and use it once for each trait.

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

use std::fmt::Debug;
use std::marker::PhantomData;

pub fn get_foo() -> impl Foo<'static, u32, Bar = u8, Baz = u16, Qux = String> {
    FooImpl::NEW
}

pub trait Foo<'a, T> {
    type Bar: Debug;
    type Baz: Copy;
    type Qux: Clone;
}

pub struct FooImpl<'a, T, Bar, Baz, Qux>(PhantomData<fn() -> (&'a (), T, Bar, Baz, Qux)>);

impl<'a, T, Bar, Baz, Qux> Foo<'a, T> for FooImpl<'a, T, Bar, Baz, Qux>
where
    Bar: Debug,
    Baz: Copy,
    Qux: Clone,
{
    type Bar = Bar;
    type Baz = Baz;
    type Qux = Qux;
}

impl<'a, T, Bar, Baz, Qux> FooImpl<'a, T, Bar, Baz, Qux> {
    pub const NEW: Self = Self(PhantomData);
}

This should also get better with type alias impl trait, I guess?

And implied bounds, and trait aliases, just off the top of my head.

This is definitely a problem space where we currently need more implementation and stabilization to get done before it makes much sense to design additional changes.

4 Likes

Indeed, that is the state of the art that I've had to use lately. =)

It does seem like there's a few related features pending stabilization that would make this mindly less painful, though I don't think that any of the mentioned features (existential type aliases, implied bounds, and bound/trait aliases) make this particular case of make-me-a-witness-on-demand particularly easier.

I think that what I almost want is some kind of "product kind", analogous to how we can build up product types for passing many values around as a cohesive unit. The mental image I keep coming back to is the desire to write down a struct whose fields are all of "type" type. Ostensibly that's what the tuple type constructors are, but there's no good "struct-like" equivalent, where you can do .-syntax access instead of what is essentially pattern matching in an impl declaration.

If the clarification helps: I do agree with this.

I just think it'll be impractically difficult to design a proper solution to this before any of those other features land, much less convince anyone it's the best solution (and better than doing nothing).

Come to think of it, GATs might be helpful here too.

Oh, I might have misread. Yeah, the type system does have a lot of things in flight, which is why this post is intentionally not a proposal, but more like... aspirational note-taking. I am running on the assumption that all of those features will be stabilized close to the form currently implemented in the nightly compiler, and I don't immediately feel think they're likely to affect the design. But, as you say, it's hard to tell at this stage.

Using GAT, wouldn't this become:

trait Sha256_ { /* ... */ }
trait Rsa_ { /* ... */ }

trait Crypto<Sha256, Rsa, /* ... */ >
where
    Sha256 : Sha256_,
    Rsa: Rsa_,
{
  // ...
}

Which means that you could write

impl<Rsa> ... {
  fn foo() -> MyStruct<impl Crypto<Rsa = Rsa_, Sha256 = MySha>>;
}

Notes:

  • I think the final _ could be removed (I think that the grammar isn't ambiguous if the types parameters and the trait share the same name.
  • I didn't checked the GAT RFC, but I think it should be possible to access to Crypto::Sha256 (and get MySha). If it's not possible directly, it should be easy to add a type Sha256: Sha256_ = Sha256 in the trait Crypto.

Totally unrelated, but what is the antonym of the word "leading"? _foo_ as both a leading and a ??? underscore. Same question for in-the-middle (foo_and_bar has two ??? underscores).

leading/trailing underscores. snake_case I'd probably say as central or internal underscores if I had to, but probably just say snake case.

1 Like

Thanks a lot!