My recursive code of cps style cannot be compiled

help
1

my code:

fn add(n:i32, f: impl Fn(i32)) {
    if n < 1 {
        f(0)
    } else {
        add(n-1, |d:i32| {
            f(n + d);
        });
    }
}

but when i try to build, i got a error:
reached the recursion limit while instantiating

2

The problem is that every closure has its own unique type. Thus when you call add(…, |d| another_closure), you instantiate add() with a new type (not with the type of f), which in turn instantiates it with yet another new type, and so on.

In general, if you need value-level recursion, you can't do that using type-level recursion only. You'll need to introduce a function pointer at some point, e.g.:

fn add(n: i32, f: &mut dyn FnMut(i32)) {
    if n < 1 {
        f(0)
    } else {
        add(n - 1, &mut |d: i32| {
            f(n + d);
        });
    }
}

Playground

3 Likes
3

sorry, i don't understand.
i know the

|d:i32| {
   f(n + d);
}

is a new type fn, but it's also impl Fn(i32). So i don't know why it will be expand forever

4

Generic expansions happen fully at compile time, but your function recursively uses an infinite list of types, which the compiler is unable to handle.

1 Like
5

Here's the type-based recursion spelled out a bit more.

And another sketching how erasing the base type with dyn Fn(i32) avoids the infinite recursion.

2 Likes
6

If every closure is a new type, then every generic instantiation will need to happen with that new type, hence the infinite recursion.

7

I suppose the confusion is because you think that impl Fn(i32) is a single type. It's not. It means any type which implement Fn(i32). For the intents of this question, your signature is

fn add<F>(n:i32, f: F) where F: Fn(i32);

Since all closures (even syntactically identical ones) have different types, it should be clear that your recursively defined closure has a recursive type, which can't terminate based only on compile-time information.

The way to avoid type recursion is to explicitly erase the generic parameter to a single type. This means using dynamic dispatch via trait objects. This means using instead of impl Fn(i32) some sort of pointer: &dyn Fn(i32), Box<dyn Fn(i32)>, Rc<dyn Fn(i32)> etc.

3 Likes
8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.