242. Side effects of function objects

Section: 26.7.4 [alg.transform], 29.5 [rand] Status: CD1 Submitter: Angelika Langer Opened: 2000-05-15 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.transform].

View all issues with CD1 status.

Discussion:

The algorithms transform(), accumulate(), inner_product(), partial_sum(), and adjacent_difference() require that the function object supplied to them shall not have any side effects.

The standard defines a side effect in 6.9.1 [intro.execution] as:

-7- Accessing an object designated by a volatile lvalue (basic.lval), modifying an object, calling a library I/O function, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment.

As a consequence, the function call operator of a function object supplied to any of the algorithms listed above cannot modify data members, cannot invoke any function that has a side effect, and cannot even create and modify temporary objects.  It is difficult to imagine a function object that is still useful under these severe limitations. For instance, any non-trivial transformator supplied to transform() might involve creation and modification of temporaries, which is prohibited according to the current wording of the standard.

On the other hand, popular implementations of these algorithms exhibit uniform and predictable behavior when invoked with a side-effect-producing function objects. It looks like the strong requirement is not needed for efficient implementation of these algorithms.

The requirement of  side-effect-free function objects could be replaced by a more relaxed basic requirement (which would hold for all function objects supplied to any algorithm in the standard library):

A function objects supplied to an algorithm shall not invalidate any iterator or sequence that is used by the algorithm. Invalidation of the sequence includes destruction of the sorting order if the algorithm relies on the sorting order (see section 25.3 - Sorting and related operations [lib.alg.sorting]).

I can't judge whether it is intended that the function objects supplied to transform(), accumulate(), inner_product(), partial_sum(), or adjacent_difference() shall not modify sequence elements through dereferenced iterators.

It is debatable whether this issue is a defect or a change request. Since the consequences for user-supplied function objects are drastic and limit the usefulness of the algorithms significantly I would consider it a defect.

Proposed resolution:

Things to notice about these changes:

1. The fully-closed ("[]" as opposed to half-closed "[)" ranges are intentional. we want to prevent side-effects from invalidating the end iterators.
2. That has the unintentional side-effect of prohibiting modification of the end element as a side-effect. This could conceivably be significant in some cases.
3. The wording also prevents side-effects from modifying elements of the output sequence. I can't imagine why anyone would want to do this, but it is arguably a restriction that implementors don't need to place on users.
4. Lifting the restrictions imposed in #2 and #3 above is possible and simple, but would require more verbiage.

Change 25.2.3/2 from:

-2- Requires: op and binary_op shall not have any side effects.

to:

-2- Requires: in the ranges [first1, last1], [first2, first2 + (last1 - first1)] and [result, result + (last1- first1)], op and binary_op shall neither modify elements nor invalidate iterators or subranges. [Footnote: The use of fully closed ranges is intentional --end footnote]

Change 25.2.3/2 from:

-2- Requires: op and binary_op shall not have any side effects.

to:

-2- Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges [first1, last1], [first2, first2 + (last1 - first1)], and [result, result + (last1 - first1)]. [Footnote: The use of fully closed ranges is intentional --end footnote]

Change 26.4.1/2 from:

-2- Requires: T must meet the requirements of CopyConstructible (lib.copyconstructible) and Assignable (lib.container.requirements) types. binary_op shall not cause side effects.

to:

-2- Requires: T must meet the requirements of CopyConstructible (lib.copyconstructible) and Assignable (lib.container.requirements) types. In the range [first, last], binary_op shall neither modify elements nor invalidate iterators or subranges. [Footnote: The use of a fully closed range is intentional --end footnote]

Change 26.4.2/2 from:

-2- Requires: T must meet the requirements of CopyConstructible (lib.copyconstructible) and Assignable (lib.container.requirements) types. binary_op1 and binary_op2 shall not cause side effects.

to:

-2- Requires: T must meet the requirements of CopyConstructible (lib.copyconstructible) and Assignable (lib.container.requirements) types. In the ranges [first, last] and [first2, first2 + (last - first)], binary_op1 and binary_op2 shall neither modify elements nor invalidate iterators or subranges. [Footnote: The use of fully closed ranges is intentional --end footnote]

Change 26.4.3/4 from:

-4- Requires: binary_op is expected not to have any side effects.

to:

-4- Requires: In the ranges [first, last] and [result, result + (last - first)], binary_op shall neither modify elements nor invalidate iterators or subranges. [Footnote: The use of fully closed ranges is intentional --end footnote]

Change 26.4.4/2 from:

-2- Requires: binary_op shall not have any side effects.

to:

-2- Requires: In the ranges [first, last] and [result, result + (last - first)], binary_op shall neither modify elements nor invalidate iterators or subranges. [Footnote: The use of fully closed ranges is intentional --end footnote]

[Toronto: Dave Abrahams supplied wording.]

[Copenhagen: Proposed resolution was modified slightly. Matt added footnotes pointing out that the use of closed ranges was intentional.]