[Solved] Simulate recursion with stack and closures

help
1

Hello,
I'm new to Rust and I'd like to implement recursion with stack on the heap, but I cannot get it compiled. The following code is the last of my many attempts, still failing to compile. I think I can roughly imagine where is the problem (that the lifetime 'a of all the boxes is the same as the lifetime of the stack?), but as I am a newbie, I am still a little bit lost in the world of lifetimes and cannot figure out how to make it right. Could you please help me? This is the code:

extern crate boxfnonce;

use boxfnonce::BoxFnOnce;

struct StackFn<'a>(BoxFnOnce<'a, (&'a mut Stack<'a>,)>);
type Stack<'a> = Vec<StackFn<'a>>;

fn salute<'a>(
    message: String,
) -> StackFn<'a> {
    let msg = message.to_string();

    StackFn(BoxFnOnce::from(move |stack: &mut Stack| {
        println!("hello {}", msg);

        stack.push(StackFn(BoxFnOnce::from(move |_stack: &mut Stack| {
            println!("bye {}", msg);
        })));
    }))
}

pub fn simulate_recursion() {
    let mut stack: Stack = Vec::new();

    stack.push(salute("you".to_string()));

    while let Some(StackFn(f)) = stack.pop() {
        f.call(&mut stack);
    }
}

fn main() {
    simulate_recursion();
}

A simple solution comes to my mind: not to use closures, instead, I could make an enum of structures that represent all functions which can be added to stack and their arguments - i.e. handle the closures manually. However, since Rust supports closures, I would like to benefit from the feature.

2

I'm not sure about that but the issue may be caused by BoxFnOnce. Its type parameters and the signature of its call() method imply that all your stack: &mut Stack parameters passed to each Stack element should have the same lifetime. However, it's not possible to actually pass a &'a mut Stack with the same 'a to each element. For example, you have to re-borrow the stack in each iteration of the while let loop, so all your &mut Stack arguments will have distinct, non-overlapping lifetimes. This is not a problem with normal functions because they have an implicit lifetime parameter corresponding to each input reference type, so the compiler will just use the lifetime of the argument to infer it. Since in this case the lifetime is locked in the struct type declaration, the compiler can't do that.

1 Like
3

If I understood your intent correctly, you don’t need the lifetimes there. Here is a way to do it. I’m using a normal Box<Fn> instead of the fnonce box, but that shouldn’t matter.

4

Thank you both, I have decided to get rid of BoxFnOnce because it requires to specify the lifetimes. I have realized that my project does not require much stability, so I have finally used the unstable FnBox instead, with no problem. My final solution is very similar to the one proposed by @vitalyd, only the message is not being cloned (because it is inacceptable for me for efficiency reasons), but instead it is moved (it is possible, as I'm using the FnBox instead of Fn).

5

Yeah, the clone was there because I was using Fn.

If a lifetime was required in BoxFnOnce, then a 'static one would probably work (I’m not familiar with that crate) since your closures didn’t actually hold references to anything from their environment.

6

I've just tried to replace both the 'a lifetimes from the StackFn definition with the 'static ones but the error remains. Maybe because the vector is not static, but only local in the simulate_recursion function? Now I'm a bit confused, how the references you're talking about relate to the 'static lifetime. I thought that 'static means that it lives during whole program execution. I try to avoid it wherever possible, because I want the memory to be freed after it is not required anymore.

7

I looked at BoxFnOnce just now and see that it doesn’t work well here. My initial thinking was you’d use 'static to indicate that the closure doesn’t borrow anything from the environment and therefore can live forever. But, I overlooked the need for a lifetime parameter for the &mut Stack argument.

I see you went on to use std’s FnBox but you can replicate its functionality (modulo the call sugar) yourself: example

8

cool - it looks simple and interesting. thank you for a piece of code to learn from.