Complex trait requirements on struct

Question

I have a fairly complex trait set up and I'm having trouble lining the pieces up. Right now it looks roughly like this:

/// Trait for models which can be gradient-optimized.
pub trait Optimizable {
    type Data;
    type Target;

    // The contract //
}

/// Trait for optimization algorithms.
pub trait OptimAlgorithm<M : Optimizable> {

    // The contract //
}

Now I want to be able to allow a struct implementing OptimAlgorithm to be a field in a struct implementing Optimizable. This would look something like this:

/// Model struct
pub struct Model<A: OptimAlgorithm<Self>> {
    alg: A,
}

impl Optimizable for Model<A> {
...
}

This doesn't work as the Self reference on the struct is nonsense. I tried using associated types for OptimAlgorithm but I need the algorithms to be generic over the models so this doesn't work. Is there a magic syntax I'm missing or does this need an overhaul?

Edit --

Here's a minimal example which shows error E0275 as described in Steven's answer. It's a little closer to my source code but less messy.

This looks weird to me. From your definitions, it looks like there's N algorithms for any given model, i.e. the optimizable trait is independent of any algorithms. And yet your model struct tries to link itself to a single algorithm. That feels like a violation of the contract you define in your traits, which may or may not be the reason why you have trouble expressing the requirements in code. — Sebastian Redl, Jan 01 '16 at 01:37
I want my model struct to own an algorithm which can be specified on construction. So that for example a user could make a custom algorithm and plug it into a model. The idea is that there are multiple algorithms which can be used on any algorithm with the Optimizable trait. — user124784, Jan 01 '16 at 01:39

Steven · Answer 1 · 2016-01-01T05:33:11.613

Just use Model<A> instead of Self. Self is only really useful in traits where one needs to be able to refer to the concrete type implementing the trait. Here, the concrete type is always Model<A>.

pub trait Optimizable {
    type Data;
    type Target;

    // The contract //
}

/// Trait for optimization algorithms.
pub trait OptimAlgorithm<M: Optimizable> {

    // The contract //
}
pub struct Model<A> where A: OptimAlgorithm<Model<A>> {
    alg: A,
}

impl<A> Optimizable for Model<A>
    where A: OptimAlgorithm<Model<A>>
{
    type Data = ();
    type Target = ();
}

In response to your updated code, the lifetime appears to be giving rust trouble. It appears you can make this work by using a higher-ranked lifetime but I don't know why.

pub trait Optimizable {
    type Data;
    type Target;

    // The contract //
}

/// Trait for optimization algorithms.
pub trait OptimAlgorithm<M: Optimizable> {

    // The contract //
}

pub struct Algorithm;

impl Default for Algorithm {
    fn default() -> Algorithm { Algorithm }
}

impl<M: Optimizable> OptimAlgorithm<M> for Algorithm {

}


pub struct Model<'a, A> where for<'b> A: OptimAlgorithm<Model<'b, A>> {
    layer_sizes: &'a [usize],
    alg: A,
}

impl<'a, A> Model<'a, A>
    where A: for<'b> OptimAlgorithm<Model<'b, A>>
{
    pub fn new(layers: &'a [usize]) -> Model<Algorithm> {
        Model {
            layer_sizes: layers,
            alg: Algorithm::default(),
        }
    }
}

impl<'a, A> Optimizable for Model<'a, A>
    where A: for<'b> OptimAlgorithm<Model<'b, A>>
{
    type Data = ();
    type Target = ();
}

pub fn main() {
    let layers = &[1usize,2,3];
    let a = Model::<Algorithm>::new(layers as &[usize]);
}

This led me to this error further down the line: E0275 This error occurs when there was a recursive trait requirement that overflowed before it could be evaluated. Often this means that there is unbounded recursion in resolving some type bounds. — user124784, Jan 01 '16 at 03:50
@user124784 D'you have a MCVE for that? [Steven's code works for me.](https://play.rust-lang.org/?gist=45d168596399214e013c&version=stable) — Veedrac, Jan 01 '16 at 03:58
@user124784, please post the rest of your code. The code in the answer above compiles. — Steven, Jan 01 '16 at 03:58
Heres a minimal version I put together on the playground: https://play.rust-lang.org/?gist=93e483be68190063682d&version=stable — user124784, Jan 01 '16 at 04:20
@user124784 Unfortunately, I don't know what's going on. I've been able to "fix" it but I don't really understand the problem. — Steven, Jan 01 '16 at 05:34

score 2 · Answer 2 · edited Apr 05 '16 at 12:12

2

I think it's a bug. Or at least surprising behaviour. If you take off the where bound on the Model struct (and just leave it on the impl), your edited code compiles. I'll try to reduce a bit more and file a bug.

pub trait Optimizable {
    type Data;
    type Target;

    // The contract //
}

/// Trait for optimization algorithms.
pub trait OptimAlgorithm<M: Optimizable> {

    // The contract //
}

pub struct Algorithm;

impl Default for Algorithm {
    fn default() -> Algorithm { Algorithm }
}

impl<M: Optimizable> OptimAlgorithm<M> for Algorithm {

}


pub struct Model<'a, A> { // no bounds here
    layer_sizes: &'a [usize],
    alg: A,
}

impl<'a, A> Model<'a, A>
    where A: OptimAlgorithm<Model<'a, A>>
{
    pub fn new(layers: &[usize]) -> Model<Algorithm> {
        Model {
            layer_sizes: layers,
            alg: Algorithm::default(),
        }
    }
}

impl<'a, A> Optimizable for Model<'a, A>
    where A: OptimAlgorithm<Model<'a, A>>
{
    type Data = ();
    type Target = ();
}

pub fn main() {

}

playground

edited Apr 05 '16 at 12:12

Sevle

3,109
2
19
31

answered Jan 03 '16 at 13:29

Paolo Falabella

24,914
3
72
86

Thanks for taking a look at this. I find it hard to differ between my lack of understanding and bugs. – user124784 Jan 03 '16 at 17:35
@user124784: The generic implementation of `Optimizable` at the bottom is weird. You implement `Optimizable` for an `Model<'a, A>` if `A` implements `OptimAlgorithm>`, however the parameter of `OptimAlgorithm` MUST implement `Optimizable` already... this may well be the heart of the recursion the compiler is complaining about. – Matthieu M. Feb 21 '16 at 16:11
@MatthieuM. Thanks for taking the time to look at this. Maybe it's just that I've spent to long staring at this - do you see any easy ways to get out of this weird loop? I had thought about just removing Optimizable and making OptimAlgorithm take a closure (but this doesn't feel very rusty). – user124784 Feb 22 '16 at 04:09
The reason the implementation is generic is that the model can be `optimized` with any `OptimAlgorithm`. But right now the `OptimAlgorithm` also requires the `Optimizable` model to be specified - so that it can access the optimizing function. – user124784 Feb 22 '16 at 05:18
@user124784: I am afraid I don't see any easy way out of this, and I don't have enough knowledge about your problem domain to be more helpful unfortunately. – Matthieu M. Feb 22 '16 at 07:12
@user124784 well, it looks that types per se are fine (everything compiles without lifetimes). Compiler gets stuck with lifetimes on the bound on the Model struct. On the struct you say you want a `Model` that lives at least `'a` to contain a `OptimAlgorithm` depending on a `Model` that lives at least `'a`, which can't be proven at this time. In the `impl`, I think the same bound works because Rust can see that (at least in this example implementation) `OptimAlgorithm` does not really depend on the lifetime of `Model` and so it can prove that everything lives as long as it should. – Paolo Falabella Feb 22 '16 at 09:05
@PaoloFalabella Thanks! Your comment helped me to figure out why Steven's solution worked (and also highlights how silly my current set up is). I still can't figure out a good way to restructure things though... The only way out I see is removing the Optimizable trait and making the OptimAlgorithm take a closure instead (which would be the equivalent of the function in the Optimizable trait). – user124784 Feb 22 '16 at 17:25
@user124784 I would need to get a sense of what your real code would look like. Based on the example code only, it's hard to give you suggestions – Paolo Falabella Feb 22 '16 at 18:02
@PaoloFalabella I've given a little more information here: https://www.reddit.com/r/rust/comments/46trxu/help_resolving_recursive_trait_dependency/ . In case you haven't seen that. I'm afraid communicating my exact usage won't be easy in SO comments and will also take up a lot of your time! – user124784 Feb 22 '16 at 18:07
That's not to say I'm not happy to do so. I'd love to talk you through it - just don't want to assume that you're willing to. – user124784 Feb 22 '16 at 18:27

Complex trait requirements on struct

2 Answers2

Linked