From fcd5e5370320d934f371bb96069a4719e94aafcd Mon Sep 17 00:00:00 2001 From: sterni Date: Tue, 11 Oct 2022 14:34:30 +0200 Subject: fix(tvix/eval/builtins): force acc not list element in foldl' When investigating discrepancies between foldl' in tvix and C++ Nix, I discovered that C++ Nix's foldl' doesn't seem to be strict at all. Since this seemed wrong, I looked into Haskell's foldl' implementation which doesn't force the list elements (`val` in our code), but the accumulation value (`res` in our code). You can look at the code here: https://hackage.haskell.org/package/base-4.17.0.0/docs/src/GHC.List.html#foldl%27 This actually makes a lot of sense: If `res` is not forced after each application of `op`, we'll end up thunks nested as deeply as the list is long, potentially taking up a lot of space. This can be limited by forcing the `res` thunk before applying `op` again (and creating a new thunk). I've also PR-ed an equivalent change for C++ Nix at https://github.com/NixOS/nix/pull/7158. Since this is not merged nor backported to our Nix 2.3 fork, I've not copied the eval fail test yet, since it wouldn't when checking our tests against C++ Nix in depot. Change-Id: I34edf6fc3031fc1485c3e714f2280b4fba8f004b Reviewed-on: https://cl.tvl.fyi/c/depot/+/6947 Autosubmit: sterni Reviewed-by: grfn Tested-by: BuildkiteCI --- tvix/eval/docs/language-issues.md | 2 ++ 1 file changed, 2 insertions(+) (limited to 'tvix/eval/docs') diff --git a/tvix/eval/docs/language-issues.md b/tvix/eval/docs/language-issues.md index 20357cba02..fb74b1d3d3 100644 --- a/tvix/eval/docs/language-issues.md +++ b/tvix/eval/docs/language-issues.md @@ -17,6 +17,7 @@ maybe to get rid of the behavior in all implementations for good. Below is an * [Behaviour of nested attribute sets depends on definition order][i7111] * [Partially constructed attribute sets are observable during dynamic attr names construction][i7012] * [Nix parsers merges multiple attribute set literals for the same key incorrectly depending on definition order](i7115) +* [builtins.foldl' doesn't seem to be strict](p7158) On the other hand, there is behavior that seems to violate one's expectation about the language at first, but has good enough reasons from an implementor's @@ -37,3 +38,4 @@ perspective to keep them: [i7111]: https://github.com/NixOS/nix/issues/7111 [i7012]: https://github.com/NixOS/nix/issues/7012 [i7115]: https://github.com/NixOS/nix/issues/7115 +[p7158]: https://github.com/NixOS/nix/pull/7158 -- cgit 1.4.1