Trampolining Nix with GenericClosure
a day ago
- #recursion
- #functional-programming
- #Nix
- Nix's evaluator has a call depth limit of 10,000 (configurable via max-call-depth), leading to stack overflow errors for deep recursions.
- builtins.genericClosure can be repurposed to achieve O(1) stack depth by using it as a trampoline for iterative computations.
- The key insight is to use builtins.deepSeq on the state within the key field to prevent thunk chains from forming, ensuring the state is evaluated at each step.
- This approach is slower than builtins.foldl' due to the overhead of genericClosure's key deduplication and deepSeq, but it handles cases where the iteration count is unknown or the state is compound.
- The technique is particularly useful for interpreters, validators, or any computation where the length scales with input size.
- A proposal for builtins.trampoline exists but lacks momentum, making genericClosure the current best option for such use cases.