`lib.lists.foldl'`: Make stricter, tests and docs by infinisil · Pull Request #256544 · NixOS/nixpkgs

infinisil · 2023-09-21T17:38:28Z

Description of changes

Makes lib.lists.foldl' always evaluate its accumulator argument before starting the iteration.

Before:

nix-repl> builtins.foldl' (acc: el: el) (throw "evaluated") [ 1 ]         
1

After:

nix-repl> foldl' (acc: el: el) (throw "evaluated") [ 1 ]          
error: evaluated

This is technically a backwards-incompatible change, which is why it needs to be done in Nixpkgs and not Nix itself, see NixOS/nix#7158.

In practice, the chance of this actually causing issues for anybody are slim. In fact, Haskell accidentally did the same in 2015, and nobody seems to have a problem with it, despite there being many more users.

This work is sponsored by Antithesis ✨

Things done

Wrote an entry in the backwards-incompatible changes section in the release notes

roberth

Docs suggestions

nixos/doc/manual/release-notes/rl-2311.section.md

lib/lists.nix

infinisil · 2023-09-22T00:46:04Z

I now also added lib.foldl' tests, including ones for the strictness of it.

lib/tests/misc.nix

roberth

In my suggestions I'm using two academic terms (denotational vs operational semantics) that could be considered to make the text slightly less accessible to newcomers. However, I believe they can still infer the meaning from context, and having the terms, we give them an opportunity to better understand the functional programming context. foldl' exists precisely for "advanced" reasons, which aligns with these two terms.
(Not sure that I should be explaining myself in this regard, as I feel this should be normal, but now I already wrote it so here ya go)

roberth · 2023-09-22T10:30:59Z

lib/lists.nix

Suggested change

is semantically the same as

is denotationally equivalent to

If we're going to talk about the semantics, we have to pick the right semantics.

We should then also (later) discuss the other semantics, the operational semantics:

+However, operationally, the accₙ bindings are optimized away using a single memory location instead.

I actually don't think we need to mention the operational semantics. It's not very useful information and pretty much an implementation detail.

I am now using "is (denotationally) equivalent to" though.

roberth · 2023-09-22T10:42:43Z

lib/lists.nix

Stack overflows aren't part of the Nix language semantics, so I'd phrase this a bit differently.
Also I would refrain from comparing these two models, precisely because they're different kinds of models. They are not to be treated as example code.
Furthermore, even if you did, the example with the lets and seqs will still overflow the stack.

Suggested change

The only difference is that the second version would always cause a stack overflow for large enough lists,

which isn't a problem with this function.

The most significant benefit of `foldl'` over any hand-written recursion is that it gives the Nix evaluator the opportunity to avoid a stack overflow, even if regular calls are susceptible to this error condition.

I now removed any text after the code. It's really not that important to point out the difference, nobody would ever write that code anyways.

And the think about stack overflows is already mentioned in an earlier paragraph, so I don't think it needs to be repeated. I did reword that slightly though. (diff)

lib/lists.nix

infinisil · 2023-09-25T20:52:28Z

In my suggestions I'm using two academic terms (denotational vs operational semantics) that could be considered to make the text slightly less accessible to newcomers. However, I believe they can still infer the meaning from context, and having the terms, we give them an opportunity to better understand the functional programming context. foldl' exists precisely for "advanced" reasons, which aligns with these two terms.
(Not sure that I should be explaining myself in this regard, as I feel this should be normal, but now I already wrote it so here ya go)

While I did learn about denotational vs operational semantics in university, I had to refresh my memory of it. I really don't think this is necessary in any way, even for advanced users. However, I now added (denotational) in parenthesis.

Nix 2.3, the minimum Nix version supported by Nixpkgs, has `builtins.foldl'` already.

roberth · 2023-09-26T18:26:07Z

lib/lists.nix

Suggested change

Compared to regular recursive functions, this allows avoiding stack overflows on large lists.

This sentence doesn't belong in this paragraph, because the paragraph is about strictness, not the stack behavior. Specifically this seemed to refer to the preceding sentence, which would be an incorrect relation.

Alternatively, you could move this sentence after "Before each application of the operator, the accumulator value is evaluated.", in which case it does hold up.

However, the relation between strictness and stack overflows is mostly an implementation detail, so I'd be happy to present these aspects in separate paragraphs.

roberth · 2023-09-26T18:28:12Z

lib/lists.nix

Suggested change

is (denotationally) equivalent to

is (denotationally) equivalent to the following, but with the added benefit that `foldl'` itself will never overflow the stack.

Co-Authored-By: Robert Hensing <[email protected]>

To maintain backwards compatibility, this can't be changed in the Nix language. We can however ensure that the version Nixpkgs has the more intuitive behavior.

See the parent commit for the same change to lib.lists.foldl'

infinisil · 2023-09-27T00:44:21Z

@roberth Your suggestions sound good to me, applied!

nixos-discourse · 2023-10-11T11:43:54Z

This pull request has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/new-nix-builtins-search/34059/3

infinisil requested a review from edolstra as a code owner September 21, 2023 17:38

github-actions bot added 6.topic: nixos Issues or PRs affecting NixOS modules, or package usability issues specific to NixOS 8.has: documentation This PR adds or changes documentation 8.has: changelog This PR adds or changes release notes 6.topic: lib The Nixpkgs function library labels Sep 21, 2023

infinisil force-pushed the strict-foldl branch from 0f181d9 to 7ccf457 Compare September 21, 2023 17:39

infinisil requested a review from roberth September 21, 2023 17:39

infinisil mentioned this pull request Sep 21, 2023

lib.fileset.trace, lib.fileset.traceVal: init #256417

Merged

4 tasks

infinisil force-pushed the strict-foldl branch from 7ccf457 to c7270e0 Compare September 21, 2023 17:49

roberth reviewed Sep 21, 2023

View reviewed changes

nixos/doc/manual/release-notes/rl-2311.section.md Outdated Show resolved Hide resolved

lib/lists.nix Outdated Show resolved Hide resolved

lib/lists.nix Outdated Show resolved Hide resolved

lib/lists.nix Outdated Show resolved Hide resolved

infinisil force-pushed the strict-foldl branch from c7270e0 to 4edb148 Compare September 22, 2023 00:44

infinisil force-pushed the strict-foldl branch 2 times, most recently from 940da1d to c529951 Compare September 22, 2023 00:53

ofborg bot added 10.rebuild-darwin: 0 This PR does not cause any packages to rebuild on Darwin. 10.rebuild-linux: 1-10 This PR causes between 1 and 10 packages to rebuild on Linux. labels Sep 22, 2023

roberth reviewed Sep 22, 2023

View reviewed changes

lib/tests/misc.nix Outdated Show resolved Hide resolved

lib/tests/misc.nix Outdated Show resolved Hide resolved

lib/tests/misc.nix Outdated Show resolved Hide resolved

infinisil force-pushed the strict-foldl branch from c529951 to aef4719 Compare September 22, 2023 10:25

roberth reviewed Sep 22, 2023

View reviewed changes

infinisil force-pushed the strict-foldl branch from aef4719 to a9c39cd Compare September 25, 2023 20:50

ofborg bot added the 2.status: merge conflict This PR has merge conflicts with the target branch label Sep 25, 2023

infinisil added 2 commits September 26, 2023 18:55

lib.lists.foldl': Remove fallback

7a0b5c3

Nix 2.3, the minimum Nix version supported by Nixpkgs, has `builtins.foldl'` already.

lib.lists.foldl': Add tests

9893fee

infinisil force-pushed the strict-foldl branch from a9c39cd to b4aba29 Compare September 26, 2023 16:57

ofborg bot removed the 2.status: merge conflict This PR has merge conflicts with the target branch label Sep 26, 2023

roberth reviewed Sep 26, 2023

View reviewed changes

infinisil and others added 3 commits September 27, 2023 02:43

lib.lists.foldl': Redo documentation

857a844

Co-Authored-By: Robert Hensing <[email protected]>

lib.lists.foldl': Make strict in the initial accumulator

3b6169f

To maintain backwards compatibility, this can't be changed in the Nix language. We can however ensure that the version Nixpkgs has the more intuitive behavior.

lib.attrsets.foldlAttrs: Make stricter

dd72ff2

See the parent commit for the same change to lib.lists.foldl'

infinisil force-pushed the strict-foldl branch from b4aba29 to dd72ff2 Compare September 27, 2023 00:44

roberth approved these changes Sep 27, 2023

View reviewed changes

roberth merged commit bdce311 into NixOS:master Sep 27, 2023

infinisil deleted the strict-foldl branch September 27, 2023 19:01

infinisil changed the title ~~lib.lists.foldl': Make stricter~~ lib.lists.foldl': Make stricter, tests and docs Sep 28, 2023

	The only difference is that the second version would always cause a stack overflow for large enough lists,
	which isn't a problem with this function.
	The most significant benefit of `foldl'` over any hand-written recursion is that it gives the Nix evaluator the opportunity to avoid a stack overflow, even if regular calls are susceptible to this error condition.

	is (denotationally) equivalent to
	is (denotationally) equivalent to the following, but with the added benefit that `foldl'` itself will never overflow the stack.

Uh oh!

Comments

Conversation

infinisil commented Sep 21, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description of changes

Things done

Uh oh!

roberth left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

infinisil commented Sep 22, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

roberth left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

roberth Sep 22, 2023

Choose a reason for hiding this comment

Uh oh!

infinisil Sep 25, 2023

Choose a reason for hiding this comment

Uh oh!

roberth Sep 22, 2023

Choose a reason for hiding this comment

Uh oh!

infinisil Sep 25, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

infinisil commented Sep 25, 2023

Uh oh!

roberth Sep 26, 2023

Choose a reason for hiding this comment

Uh oh!

roberth Sep 26, 2023

Choose a reason for hiding this comment

Uh oh!

infinisil commented Sep 27, 2023

Uh oh!

nixos-discourse commented Oct 11, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

infinisil commented Sep 21, 2023 •

edited

Loading

roberth left a comment •

edited

Loading

infinisil Sep 25, 2023 •

edited

Loading