collective
Browse / github.com/storytold/gridcraft / patch
LAMBDA tail recursion reaches Excel's depth (5,459)
LAMBDA tail recursion reaches Excel's depth (5,459) ## What was wrong A recursive LAMBDA that calls itself in tail position (`IF(n=0,0,me(me,n-1))`) stopped at about 139 calls and answered `#NUM!`. Excel computes the same formula up to n=5,459 and answers `#NUM!` from 5,460. ## Cause Every LAMBDA call nested under the previous one on the native stack, so the call count had to stay low (`MAX_LAMBDA_CALLS` = 140) to keep a 1 MiB thread and wasm from overflowing. ## Fix `call_lambda_values` now follows the body through the tail positions (`IF` branches, parentheses, applied lambdas) and, when the value is another LAMBDA call, evaluates its argum
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- Harrison-Booth (imported from pull request #2660, open)
- Base
11bb67386c9bb19b0717e21e98adc608162ae2e5- Size
- +176 −15 in 5 files
- Review
- pending
- Shared
- 2026-10-28
- Id
f9e34fc3855add5c6375704b
How it went
No other operator has reported using it yet.
Diff
raw · crates/calc/src/eval.rs crates/calc/src/eval/call.rs crates/calc/src/eval/lambda.rs crates/calc/src/eval/special.rs crates/calc/src/tests.rs
@@ -53,6 +53,28 @@ pub struct Lambda { pub env: Vec<(String, Ev)>, } +/// What the tail of a LAMBDA body came to.+enum Tail {+ Done(Ev),+ /// A call to make in place of the current one, its arguments evaluated.+ Call(Arc<Lambda>, Vec<(String, Ev)>),+}++/// A tail call can pass a closure that captures the previous one, thousands deep. Releasing the+/// chain is a loop, not a recursion, so it cannot overflow the native stack.+impl Drop for Lambda {+ fn drop(&mut self) {+ let mut pending = std::mem::take(&mut self.env);+ while let Some((_, ev)) = pending.pop() {+ if let Ev::L(l) = ev+ && let Ok(mut inner) = Arc::try_unwrap(l)+ {+ pending.append(&mut inner.env);+ }+ }+ }+}+ #[derive(Clone, Debug)] pub enum Ev { V(Value),@@ -75,6 +97,11 @@ fn err(e: CellError) -> Ev { /// calls in progress, so it still runs. const MAX_LAMBDA_CALLS: usize = 140; +/// Tail calls one LAMBDA call may chain. They run in a loop on one native frame, so this only keeps+/// an endless tail recursion finite. Excel computes a tail countdown to 5,459 and answers `#NUM!`+/// for 5,460, which is 5,460 invocations in the chain.+const MAX_TAIL_CALLS: usize = 5460;+ /// Native stack, in bytes, that one formula's evaluation may use below its first `eval`. Past it, /// `eval` answers `#NUM!`. It guards the stack and leaves 128 KiB of a 1 MiB thread for the frames /// above the formula. A cell that another cell's formula computes on demand shares the budget of the@@ -4,6 +4,17 @@ use super::special::{ev_shape, resized_sum_range, resizes_sum_range}; use super::*; impl<'h> Evaluator<'h> {+ /// `IF` with an array condition: element-wise.+ pub(super) fn if_elementwise(&mut self, arr: &Array, args: &[Expr]) -> Ev {+ let t = self.arg_val(args, 1).unwrap_or(Value::Bool(true));+ let f = if args.len() > 2 { self.arg_val(args, 2).unwrap_or(Value::Bool(false)) } else { Value::Bool(false) };+ Ev::V(zip3(arr, &t, &f, |c, t, f| match c.to_bool() {+ Ok(true) => t.clone(),+ Ok(false) => f.clone(),+ Err(e) => Value::Error(e),+ }))+ }+ pub(super) fn call(&mut self, name: &str, args: &[Expr]) -> Ev { match name { "IF" => {@@ -12,14 +23,7 @@ impl<'h> Evaluator<'h> { } let c = self.arg_val(args, 0).unwrap_or_default(); if let Value::Array(arr) = &c {- // Array condition: element-wise.- let t = self.arg_val(args, 1).unwrap_or(Value::Bool(true));- let f = if args.len() > 2 { self.arg_val(args, 2).unwrap_or(Value::Bool(false)) } else { Value::Bool(false) };- return Ev::V(zip3(arr, &t, &f, |c, t, f| match c.to_bool() {- Ok(true) => t.clone(),- Ok(false) => f.clone(),- Err(e) => Value::Error(e),- }));+ return self.if_elementwise(arr, args); } match c.to_bool() { Ok(true) => match args.get(1) {@@ -1,15 +1,24 @@ use super::array::{broadcast_len, single};+use super::special::is_special; use super::*; impl<'h> Evaluator<'h> { pub fn apply_lambda(&mut self, l: &Lambda, args: &[Expr]) -> Ev {+ match self.bind_args(l, args) {+ Ok(bound) => self.call_lambda_values(l, bound),+ Err(e) => e,+ }+ }++ /// The arguments of a call to `l`, evaluated in the current scope.+ fn bind_args(&mut self, l: &Lambda, args: &[Expr]) -> Result<Vec<(String, Ev)>, Ev> { // Too many or too few argument positions is #VALUE!. An explicitly empty position, as in // `(1,)`, is `Expr::Missing` and still counts as a position (it binds as omitted). `f()` // parses to no arguments, which for a one-parameter lambda can also be read as one empty // position, so that call still binds the parameter as omitted. let positions_ok = args.len() == l.params.len() || (args.is_empty() && l.params.len() == 1); if !positions_ok {- return err(CellError::Value);+ return Err(err(CellError::Value)); } let mut bound = Vec::with_capacity(l.params.len()); for (i, p) in l.params.iter().enumerate() {@@ -19,7 +28,56 @@ impl<'h> Evaluator<'h> { }; bound.push((p.clone(), v)); }- self.call_lambda_values(l, bound)+ Ok(bound)+ }++ /// Follows `e` through the positions whose value is the value of a LAMBDA call (`IF` branches,+ /// parentheses), and returns the call with its arguments evaluated instead of making it, so+ /// that `call_lambda_values` can loop. Anything else is evaluated here.+ fn tail_step(&mut self, e: &Expr) -> Tail {+ match e {+ Expr::Paren(x) => self.tail_step(x),+ Expr::Call(name, args) if name == "IF" && (2..=3).contains(&args.len()) => {+ let c = self.arg_val(args, 0).unwrap_or_default();+ if let Value::Array(arr) = &c {+ return Tail::Done(self.if_elementwise(arr, args));+ }+ match c.to_bool() {+ Ok(true) => self.tail_step_branch(args.get(1)),+ Ok(false) => match args.get(2) {+ Some(_) => self.tail_step_branch(args.get(2)),+ None => Tail::Done(Ev::V(Value::Bool(false))),+ },+ Err(x) => Tail::Done(err(x)),+ }+ }+ Expr::Call(name, args) if gridcraft_functions::lookup(name).is_none() && !is_special(name) => match self.name(name) {+ Ev::L(l) => self.tail_call(l, args),+ Ev::V(Value::Error(x)) => Tail::Done(err(x)),+ _ => Tail::Done(err(CellError::Name)),+ },+ Expr::Invoke(callee, args) => match self.eval(callee) {+ Ev::L(l) => self.tail_call(l, args),+ Ev::V(Value::Error(x)) => Tail::Done(err(x)),+ _ => Tail::Done(err(CellError::Value)),+ },+ _ => Tail::Done(self.eval(e)),+ }+ }++ /// An `IF` branch; an omitted one (`IF(c,,1)`) is 0.+ fn tail_step_branch(&mut self, branch: Option<&Expr>) -> Tail {+ match branch {+ Some(Expr::Missing) | None => Tail::Done(Ev::V(Value::Number(0.0))),+ Some(b) => self.tail_step(b),+ }+ }++ fn tail_call(&mut self, l: Arc<Lambda>, args: &[Expr]) -> Tail {+ match self.bind_args(&l, args) {+ Ok(bound) => Tail::Call(l, bound),+ Err(e) => Tail::Done(e),+ } } pub(super) fn call_lambda_values(&mut self, l: &Lambda, bound: Vec<(String, Ev)>) -> Ev {@@ -36,7 +94,29 @@ impl<'h> Evaluator<'h> { self.calls += 1; let saved = std::mem::replace(&mut self.env, l.env.clone()); self.env.extend(bound);- let r = self.eval(&l.body);+ // A call in tail position replaces this one instead of nesting under it, so a tail recursion+ // uses no more native stack at 5,000 deep than at 5. Each link still spends fuel.+ let mut tails = 0;+ let mut step = self.tail_step(&l.body);+ let r = loop {+ match step {+ Tail::Done(v) => break v,+ Tail::Call(next, bound) => {+ tails += 1;+ if tails >= MAX_TAIL_CALLS {+ break err(CellError::Num);+ }+ self.fuel = match self.fuel.checked_sub(1) {+ Some(f) => f,+ None => break err(CellError::Calc),+ };+ self.env.clear();+ self.env.extend(next.env.iter().cloned());+ self.env.extend(bound);+ step = self.tail_step(&next.body);+ }+ }+ }; self.env = saved; self.calls -= 1; r@@ -84,7 +84,7 @@ pub fn precedents(wb: &Workbook, sheet: usize, e: &Expr) -> (Vec<Area>, bool) { (out, dynamic) } -fn is_special(n: &str) -> bool {+pub(super) fn is_special(n: &str) -> bool { matches!( n, "IF" | "IFS"@@ -1097,17 +1097,67 @@ fn a_recursive_lambda_stops_at_the_same_call_on_any_stack_size() { comment: String::new(), hidden: false, });- // F(F,n) has n + 1 calls in progress at its deepest; W adds one more call per step.+ // W's call to `f` is a tail call, so a wrapped call level costs one call in progress, not two. A tail call reuses its frame, so the tail chain is bounded by `MAX_TAIL_CALLS`, as in Excel+ // (5,459 ok, 5,460 #NUM!). F(F,n) otherwise has n + 1 calls in progress at its deepest; W adds+ // one more call per step. let tail = |n: u32| format!("=LET(F,LAMBDA(me,n,IF(n=0,0,me(me,n-1))),F(F,{n}))"); let wrapped = |n: u32| format!("=LET(W,LAMBDA(f,k,f(f,k)),F,LAMBDA(me,n,IF(n<=0,0,1+W(me,n-1))),F(F,{n}))");- [tail(139), tail(140), wrapped(69), wrapped(70), "=CNT(131)".to_string()].map(|f| crate::evaluate(&wb, 0, c("B1"), &f))+ [tail(5459), tail(5460), wrapped(69), wrapped(70), "=CNT(131)".to_string()].map(|f| crate::evaluate(&wb, 0, c("B1"), &f)) }) .expect("spawn") .join() .expect("recursion must not overflow the stack") }; let small = run(1 << 20);- assert_eq!(small, [Value::Number(0.0), Value::Error(CellError::Num), Value::Number(69.0), Value::Error(CellError::Num), Value::Number(131.0)]);+ assert_eq!(small, [Value::Number(0.0), Value::Error(CellError::Num), Value::Number(69.0), Value::Number(70.0), Value::Number(131.0)]);+ assert_eq!(run(64 << 20), small);+}++#[test]+fn a_tail_recursive_lambda_reaches_excels_depth_on_a_small_stack() {+ // Excel (measured): a tail countdown is 0 at 5,000 and 5,459 and #NUM! at 5,460 and 10,000.+ let run = |stack: usize| {+ std::thread::Builder::new()+ .stack_size(stack)+ .spawn(|| {+ let mut wb = Workbook::new();+ wb.names.push(gridcraft_model::DefinedName {+ name: "TAILN".into(),+ scope: None,+ formula: "LAMBDA(n,IF(n=0,0,TAILN(n-1)))".into(),+ comment: String::new(),+ hidden: false,+ });+ let tail = |n: u32| format!("=LET(F,LAMBDA(me,n,IF(n=0,0,me(me,n-1))),F(F,{n}))");+ // The same chain through parentheses and an applied lambda, and one that returns the base case's value.+ let paren = "=LET(F,LAMBDA(me,n,IF(n=0,7,(me(me,n-1)))),F(F,5000))".to_string();+ let invoke = "=LET(F,LAMBDA(me,n,IF(n=0,7,LAMBDA(a,b,me(me,a))(n-1,0))),F(F,2000))".to_string();+ let endless = "=LET(f,LAMBDA(g,x,g(g,x)),f(f,1))".to_string();+ // Each call passes a closure that captures the last, 5,000 deep: releasing them must not recurse.+ let closures = "=LET(F,LAMBDA(me,n,acc,IF(n=0,0,me(me,n-1,LAMBDA(x,acc)))),F(F,5000,0))".to_string();+ [tail(5000), tail(5459), tail(5460), tail(10000), paren, invoke, endless, "=TAILN(5000)".to_string(), closures]+ .map(|f| crate::evaluate(&wb, 0, c("B1"), &f))+ })+ .expect("spawn")+ .join()+ .expect("tail recursion must not overflow the stack")+ };+ let num = Value::Error(CellError::Num);+ let small = run(1 << 20);+ assert_eq!(+ small,+ [+ Value::Number(0.0),+ Value::Number(0.0),+ num.clone(),+ num.clone(),+ Value::Number(7.0),+ Value::Number(7.0),+ num,+ Value::Number(0.0),+ Value::Number(0.0)+ ]+ ); assert_eq!(run(64 << 20), small); }