The Cost Of a Closure in C

36 points by mond

fanf

The “man-or-boy” test is a curious one. It was originally proposed in Algol Bulletin AB17.2.4 and there were some responses in AB19.2.3. (I haven’t chased down any further correspondence from that era.)

The Rosetta Code intro to the man-or-boy test is slightly wrong, in that Algol 60 does not in fact require heap-allocated activation frames. Because procedure invocations and call-by-name thunks are second-class they can’t outlive their creator so a stack is sufficient.

ibookstein

I'm left wondering why GCC Nested Functions would transition to a heap instead of a thread-local bump allocator, as the latter could leverage the intrinsic stack-based nature of function activations and avoid the contention of a shared heap. It could be made lazy-initialized to avoid squandering too much memory.

icefox

Just for funsies I wanted to see what this test would look like in Rust. I translated it from the C++ lambda version and got this: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=7daf9efccb1c88ae9c2a3f5d97d2eab3

However, it fails the test and I'm not familiar enough with either the test or C++ closures to know quite what I did wrong. There's one Funny Hack I have to do as well to deal with Rust closures not being able to refer to themselves. Can I nerd-snipe anyone into helping?

polywolf
Consider me sniped!
```
    // This bit is sticky 'cause Rust closures can't refer to themselves.
    // We gotta make a dummy closure, capture that one, and then copy
    // our real closure into it.  Not even sure it works tbqh.
    let mut dummy_b: &dyn Fn() -> i32 = &|| 0i32;
    let b: &dyn Fn() -> i32 = &|| a(k - 1, dummy_b, x1, x2, x2, x3);
    dummy_b = b;
```
That last line doesn't do what you think it does. By the time b is constructed, it has already gotten the "bad" dummy_b. Reassigning only serves to change what the label dummy_b means going forward. This is somewhat explained in the compiler warning "value assigned to dummy_b is never read".

I think something with RefCell is required (also fixed a typo in ur playground :P):
```
    use std::ops::Deref;
    let dummy_b = std::cell::RefCell::new(
        (&|| -> i32 { panic!("not here") }) as &dyn Fn() -> i32
    );
    let b: &dyn Fn() -> i32 = &|| a(k - 1, dummy_b.borrow().deref(), x1, x2, x3, x4);
    dummy_b.replace(b);
```
https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=7b7f7e8a93f93dfd85ea786aa8ee28b8
- lilyball
  
  You can do it with just Cell, since the contained type is &dyn Fn() -> i32 which is copyable.
- icefox
  
  Yeah I figured that was the source of the problem, but was tired of fighting it and needed to go to work. A little odd, normally Rust does a very good job of pretending that local variables are cells. I kinda expected that if it wasn't then I should have gotten a borrowing error instead.
lilyball

Besides the error you flagged, your implementation is wrong and blows the stack. The k value needs to be shared among multiple call frames but you just have it as a local variable. Notice in the C++ how it's captured by-reference and decremented with --k, such that calling that B mutates the k from the surrounding A.

Here's a fixed version that does this, plus use Cell for the B recursion, plus fixes another typo you had: https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=41593b065b733418908fa497acfddaa2