The Y combinator causes stack overflow

[oeb25]

Giving an invocation of a Y combinator to fend_core::evaluate causes fatal runtime error: stack overflow.

The following snippet reproduces the stack overflow:

fend_core::evaluate(
    r"Y = (\f. (\x. f x x)) (\x. f x x); Y(Y)",
    &mut Default::default(),
);

---

A potential user workaround is to use fend_core::evaluate_with_interrupt and limit the number of calculations:

struct Interupter {
    invocations_left: Cell<u32>,
}
impl fend_core::Interrupt for Interupter {
    fn should_interrupt(&self) -> bool {
        match self.invocations_left.get().checked_sub(1) {
            Some(n) => {
                self.invocations_left.set(n);
                false
            }
            None => true,
        }
    }
}
fend_core::evaluate_with_interrupt(
    r"Y = (\f. (\x. f x x)) (\x. f x x); Y(Y)",
    &mut Default::default(),
    &Interupter {
        invocations_left: 100.into(),
    },
);

I don't know if this is the most optimal approach to solve this, but it seems to work for our use case.

---

Perhaps something could be added to make limiting the number of operations more ergonomic. This is of course a bit of a special input, but when exposing fend to user inputs it's good to be a little careful.

Feel free to close this if you feel like it! There exists a workaround, so I completely understand if you would rather not change the API. Either way, thanks for making fend!

[Markos-Th09]

The solution is lazy evaluation, as the Y combinator is designed for a lazily evaluated lambda calculus. As fend uses a strictly evaluated lambda calculus, the Y combinator executes until stack overflow. There is a variant of the Y combinator called the Z combinator designed for strict evaluation.

[printfn]

@oeb25 it‘s pretty cool how you were able to use the interrupt API for your workaround. If you wanted to make a PR to make that more ergonomic I’d happily merge it, but otherwise I think I’m going to close this issue for now.

It’d be nice if fend supported lazy lambda evaluation at some point, or if lambda evaluation were implemented in a better way that doesn’t cause stack overflows like this, but I don’t think that is something I’ll implement myself anytime soon. PRs to improve the situation are more than welcome though!

[oeb25]

Very reasonable! 👍 Also this issue comes up when searching "stack overflow" now, so that at least documents how to possibly handle such cases for future users.