Simple iterative program support with "trampoline" instead of tail calls

[roberth]

Is your feature request related to a problem? Please describe.

Recursion in Nix leads to recursion on the C++ stack, which leads to crashes. Supporting proper tail recursion in Nix would be possible, but a workaround could be implemented in the form of a fairly simple function.

Describe the solution you'd like

# pseudocode
builtins.trampoline = v:
  while not v?value
    v = v.thunk
  return v.value

Describe alternatives you've considered

Proper tail recursion optimization. This would always apply and shorten many evaluation traces, which may or may not be desirable. If implemented, trampoline would be trivially implementable in the Nix language itself.

"Stackless" evaluation. Evaluate with frames that are on the heap instead of on the stack. In this case the purpose of trampoline becomes the removal of excessive frames. We need better coroutines for this, that are properly collectable. We won't be able to get away with disabling them during basically addToStore anymore. Upstream is working on better coroutine support.

Pure Nix. The trampoline function can perhaps be approximated with an "exponential search"-like algorithm and foldl'. Start with a small number of iterations, needing only a small list, and exponentially increase the size of the abused list so that the stack usage is O(log #iterations). That's basically as good as O(1) stack usage, ignoring its hacky nature and its overhead.

Additional context

• lib.findFirst: Add tests and make lazier nixpkgs#235267 (comment)
• Users who have written parsers and whatnot in Nix have always run into stack overflows and have found workarounds. This is mostly IRL discussion as this is an implementation problem which does not tend to lead to issues being written. Rather you have to talk to Nix language power users, fwiw. This is a fairly generic workaround. Wouldn't call it pretty, but that's ok.

Priorities

Add 👍 to issues you find important.