[Review:Algorithms] - Review by Neil Groves
*Evaluation of the design.* The design is pleasingly consistent with other algorithms with the exception of clamp_range. The clamp_range function copies, which is inconsitent with the other Boost string algorithms that have the _copy suffix. The clamp_range feature would be better designed as a clamped range adaptor. *Evaluation of the implementation* Generally, the algorithms would benefit from concept checking. In particular the iterator traversals, and range concept requirements should be checked. The implementation of the functions in all.hpp and clamp.hpp are correctly implemented. The clamp function does not provide the usual guarantees about NaN values that most of the floating-point operations do. That is any one argument being NaN does not guarantee a NaN result. This is probably intended, if so a note should be made in the documentation.The argument types may benefit from using call_traits to optimally chose between constant reference and value types. It might be worth considering an assertion that p(lo,hi) is true in the clamp function. The mixing of differing integer types makes the search algorithms defective. The int type is signed, and typically <= the size of std::size_t yet these are mixed. The skip table uses ints, but std::size_t values are inserted. Certainly there should not be any c style casts. It would seem logical to use the boost::iterator_difference<Iterator>::type instead. Currently these algorithms are defective albeit under unusual conditions. There are numerous invocations of non-member functions that should use qualified calls to avoid accidental argument-dependent lookup. range_const_iterator<Rng> has been deprecated in favour of range_iterator<const Rng> The Range versions of the functions should provide a non-const reference version since there are no requirements for the interoperability of range_iterator<const Range> and range_iterator<Range> although they normally exist.. The tests have some defects with respect to dereferencing end iterators. As others have mentioned there should be range versions of all of the functions. *Evaluation of the documentation* The documentation should make very clear that the result for empty ranges into all_of, any_of, none_of as this is currently ambiguous. The documentation should provide more clear performance guarantees about the number of predicate evaluations where this is possible eg. any_of can and does early exit. The documentation should also provide the exception guarantees. *Evaluation of usefulness* If corrected and properly documented these functions will be very useful. The functions any_of etc. are extremely useful for runtime assertions of pre- and post-conditions. *Did I try to use the library?* I used the library with GCC 4.6.1. I had no problems, although I did defect the defects noted above. *How much effort did I put into my evaluation?* I reviewed the code for a couple of hours which was sufficient for the small amount of code under review. *Am I knowledgeable about the problem domain?* Yes, I maintain Boost.Range hence my comments with respect to ranges are reasonably well informed. I have long been a fan of Design by Contract and hence I have experience using my own versions of the functions all_of etc. I vote for inclusion into Boost if and only if: 1. the defects in the search functions and test are resolved 2. clamp_range is removed or replaced. Regards, Neil Groves
On Oct 1, 2011, at 8:20 AM, Neil Groves wrote:
*Evaluation of the design.*
The design is pleasingly consistent with other algorithms with the exception of clamp_range. The clamp_range function copies, which is inconsitent with the other Boost string algorithms that have the _copy suffix. The clamp_range feature would be better designed as a clamped range adaptor.
The clamp_range functions were added, as a trial balloon, after the review started. They're (technically) not part of the review. That being said - thanks for the notes.
*Evaluation of the implementation*
Generally, the algorithms would benefit from concept checking. In particular the iterator traversals, and range concept requirements should be checked.
The implementation of the functions in all.hpp and clamp.hpp are correctly implemented. The clamp function does not provide the usual guarantees about NaN values that most of the floating-point operations do. That is any one argument being NaN does not guarantee a NaN result. This is probably intended, if so a note should be made in the documentation.
I'll add notes to the documentation.
The argument types may benefit from using call_traits to optimally chose between constant reference and value types.
It might be worth considering an assertion that p(lo,hi) is true in the clamp function.
Good idea - added.
The mixing of differing integer types makes the search algorithms defective. The int type is signed, and typically <= the size of std::size_t yet these are mixed. The skip table uses ints, but std::size_t values are inserted. Certainly there should not be any c style casts. It would seem logical to use the boost::iterator_difference<Iterator>::type instead. Currently these algorithms are defective albeit under unusual conditions.
There are numerous invocations of non-member functions that should use qualified calls to avoid accidental argument-dependent lookup.
range_const_iterator<Rng> has been deprecated in favour of range_iterator<const Rng>
The Range versions of the functions should provide a non-const reference version since there are no requirements for the interoperability of range_iterator<const Range> and range_iterator<Range> although they normally exist..
Captured as: https://github.com/mclow/Boost.Algorithm/issues/15
The tests have some defects with respect to dereferencing end iterators.
I believe that I have fixed all of these since the review started - but if you disagree, I'ld love to hear about it.
As others have mentioned there should be range versions of all of the functions.
https://github.com/mclow/Boost.Algorithm/issues/11
*Evaluation of the documentation*
The documentation should make very clear that the result for empty ranges into all_of, any_of, none_of as this is currently ambiguous. The documentation should provide more clear performance guarantees about the number of predicate evaluations where this is possible eg. any_of can and does early exit. The documentation should also provide the exception guarantees.
New issue: https://github.com/mclow/Boost.Algorithm/issues/16
*Evaluation of usefulness*
If corrected and properly documented these functions will be very useful. The functions any_of etc. are extremely useful for runtime assertions of pre- and post-conditions.
*Did I try to use the library?*
I used the library with GCC 4.6.1. I had no problems, although I did defect the defects noted above.
*How much effort did I put into my evaluation?*
I reviewed the code for a couple of hours which was sufficient for the small amount of code under review.
*Am I knowledgeable about the problem domain?*
Yes, I maintain Boost.Range hence my comments with respect to ranges are reasonably well informed. I have long been a fan of Design by Contract and hence I have experience using my own versions of the functions all_of etc.
I vote for inclusion into Boost if and only if:
1. the defects in the search functions and test are resolved
2. clamp_range is removed or replaced.
Thanks for the review! -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
On Sat, Oct 1, 2011 at 11:20 AM, Neil Groves <neil@grovescomputing.com> wrote:
Yes, I maintain Boost.Range hence my comments with respect to ranges are reasonably well informed. I have long been a fan of Design by Contract and hence I have experience using my own versions of the functions all_of etc.
Indeed N1962 uses a "contract helper" function all_equals (which should ideally be accompanied by the assertion requirement has_equal_to<T>::value so to not always require the vector's type T to be EqualityComparable): http://svn.boost.org/svn/boost/sandbox/contract/libs/contract/doc/html2/cont... boost::algorithm::all_of_equal (or all_equal_to, or whatever the final named ends being) could be conveniently used here instead of all_equals. The same applies to the contract of most (all?) other STL containers. --Lorenzo
On Oct 1, 2011, at 8:20 AM, Neil Groves wrote:
It might be worth considering an assertion that p(lo,hi) is true in the clamp function.
i dont; think that this is correct; consider the (limiting) case of clamp ( x, 3, 3 ). Probably not what the developer intended, but not incorrect.
The documentation should make very clear that the result for empty ranges into all_of, any_of, none_of as this is currently ambiguous. The documentation should provide more clear performance guarantees about the number of predicate evaluations where this is possible eg. any_of can and does early exit. The documentation should also provide the exception guarantees.
How about this: [heading Complexity] All of the variants of `all_of` and `all_of_equal` run in ['O(N)] (linear) time; that is, they compare against each element in the list once. If any of the comparisons fail, the algorithm will terminate immediately, without examining the remaining members of the sequence. [heading Exception Safety] All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee. [heading Notes] * `all_of` and `all_of_equal` both return true for empty ranges, no matter what is passed to test against. When there are no items in the sequence to test, they all satisfy the condition to be tested against. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
Marshall Clow wrote:
How about this:
You can be more succinct:
[heading Complexity]
All of the variants of `all_of` and `all_of_equal` run in ['O(N)] (linear) time; that is, they compare against each element in the list once. If any of the comparisons fail, the algorithm will terminate immediately, without examining the remaining members of the sequence.
All variants of `all_of` and `all_of_equal` have ['O(N)] (linear) complexity. If an element fails the comparison, the algorithms return immediately. Otherwise, all elements in the input sequence are compared exactly once.
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
All variants of `all_of` and `all_of_equal` provide the strong exception guarantee.
[heading Notes]
* `all_of` and `all_of_equal` both return true for empty ranges, no matter what is passed to test against. When there are no items in the sequence to test, they all satisfy the condition to be tested against.
[heading Empty Ranges] All variants of `all_of` and `all_of_equal` always return true for empty ranges. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On Oct 18, 2011, at 5:30 AM, Stewart, Robert wrote:
Marshall Clow wrote:
How about this:
You can be more succinct:
I'm not really sure that being succinct is a goal.
[heading Complexity]
All of the variants of `all_of` and `all_of_equal` run in ['O(N)] (linear) time; that is, they compare against each element in the list once. If any of the comparisons fail, the algorithm will terminate immediately, without examining the remaining members of the sequence.
All variants of `all_of` and `all_of_equal` have ['O(N)] (linear) complexity. If an element fails the comparison, the algorithms return immediately. Otherwise, all elements in the input sequence are compared exactly once.
I like it!
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
All variants of `all_of` and `all_of_equal` provide the strong exception guarantee.
If I could explain why - instead of just asserting it - I think it would be better. Dave has pointed out that my explanation here is incorrect.
[heading Notes]
* `all_of` and `all_of_equal` both return true for empty ranges, no matter what is passed to test against. When there are no items in the sequence to test, they all satisfy the condition to be tested against.
[heading Empty Ranges]
All variants of `all_of` and `all_of_equal` always return true for empty ranges.
This is a case where a bit of rationale adds to the explanation, I think. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
Marshall Clow wrote:
On Oct 18, 2011, at 5:30 AM, Stewart, Robert wrote:
Marshall Clow wrote:
How about this:
You can be more succinct:
I'm not really sure that being succinct is a goal.
In and of itself, it isn't, but when clarity is retained, succinctness is better. There might be the rub, however.
[heading Notes]
* `all_of` and `all_of_equal` both return true for empty ranges, no matter what is passed to test against. When there are no items in the sequence to test, they all satisfy the condition to be tested against.
[heading Empty Ranges]
All variants of `all_of` and `all_of_equal` always return true for empty ranges.
This is a case where a bit of rationale adds to the explanation, I think.
Your rationale added nothing, as far as I'm concerned. Besides, a statement like, "when there are no items...they all satisfy", is nonsensical. No matter how you try to rationalize the result, the other could be justified equally. That is, since there are no elements, none satisfied the criteria, so return false. Returning true or false for empty ranges is determined by fiat. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Your rationale added nothing, as far as I'm concerned. Besides, a statement like, "when there are no items...they all satisfy", is nonsensical. No matter how you try to rationalize the result, the other could be justified equally. That is, since there are no elements, none satisfied the criteria, so return false. Returning true or false for empty ranges is determined by fiat.
I like to think returning true demonstrates the positive, can-do, glass half-full, outlook of us software developers. :-) Gareth ************************************************************************ The information contained in this message or any of its attachments may be confidential and is intended for the exclusive use of the addressee(s). Any disclosure, reproduction, distribution or other dissemination or use of this communication is strictly prohibited without the express permission of the sender. The views expressed in this email are those of the individual and not necessarily those of Sony or Sony affiliated companies. Sony email is for business use only. This email and any response may be monitored by Sony to be in compliance with Sony's global policies and standards
On 18 Oct 2011, at 18:02, Stewart, Robert wrote:
Marshall Clow wrote:
On Oct 18, 2011, at 5:30 AM, Stewart, Robert wrote:
Marshall Clow wrote:
How about this:
You can be more succinct:
I'm not really sure that being succinct is a goal.
In and of itself, it isn't, but when clarity is retained, succinctness is better. There might be the rub, however.
[heading Notes]
* `all_of` and `all_of_equal` both return true for empty ranges, no matter what is passed to test against. When there are no items in the sequence to test, they all satisfy the condition to be tested against.
[heading Empty Ranges]
All variants of `all_of` and `all_of_equal` always return true for empty ranges.
This is a case where a bit of rationale adds to the explanation, I think.
Your rationale added nothing, as far as I'm concerned. Besides, a statement like, "when there are no items...they all satisfy", is nonsensical. No matter how you try to rationalize the result, the other could be justified equally. That is, since there are no elements, none satisfied the criteria, so return false. Returning true or false for empty ranges is determined by fiat.
No, I agree with the justification. Almost all of mathematics relies on a basis which requires "forall i in S. p(i)" is true when S is empty, and "exists i in S. p(i)" is false when S is empty. There are lots of conditions people expect to hold like: If T is a subset of S, then "forall i in S.p(i)" implies "forall i in T.p(i)". Which would be violated with forall wasn't always true for an empty set (or in our case, empty range). Chris
Christopher Jefferson wrote:
On 18 Oct 2011, at 18:02, Stewart, Robert wrote:
Marshall Clow wrote:
On Oct 18, 2011, at 5:30 AM, Stewart, Robert wrote:
Marshall Clow wrote:
* `all_of` and `all_of_equal` both return true for empty ranges, no matter what is passed to test against. When there are no items in the sequence to test, they all satisfy the condition to be tested against.
[heading Empty Ranges]
All variants of `all_of` and `all_of_equal` always return true for empty ranges.
This is a case where a bit of rationale adds to the explanation, I think.
No matter how you try to rationalize the result, the other could be justified equally. That is, since there are no elements, none satisfied the criteria, so return false. Returning true or false for empty ranges is determined by fiat.
No, I agree with the justification. Almost all of mathematics relies on a basis which requires "forall i in S. p(i)" is true when S is empty, and "exists i in S. p(i)" is false when S is empty.
There are lots of conditions people expect to hold like:
If T is a subset of S, then "forall i in S.p(i)" implies "forall i in T.p(i)".
Which would be violated with forall wasn't always true for an empty set (or in our case, empty range).
Marshall's rationale wasn't based upon mathematics. Your statements may well be sufficient to justify the choice, which removes it from the realm of fiat, but what Marshall wrote added no clarity. I didn't argue for returning false; I just noted that the rationale didn't justify the choice. I'm not convinced that any rationale is needed. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
on Mon Oct 17 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
It may be true, but it's not an appropriate conclusion from the premises. std::copy also takes all its parameters by value. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Oct 18, 2011, at 6:42 AM, Dave Abrahams wrote:
on Mon Oct 17 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
It may be true, but it's not an appropriate conclusion from the premises. std::copy also takes all its parameters by value.
Good point - how would you state it, then? "Only reads from the iterators" is the key point (unlike std::copy) -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
Marshall Clow wrote:
On Oct 18, 2011, at 6:42 AM, Dave Abrahams wrote:
on Mon Oct 17 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
It may be true, but it's not an appropriate conclusion from the premises. std::copy also takes all its parameters by value.
Good point - how would you state it, then? "Only reads from the iterators" is the key point (unlike std::copy)
Perhaps this will work: All variants of `all_of` and `all_of_equal` emit only exceptions resulting from comparisons, if any. The input range is not modified, so they also provide the strong exception guarantee. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Le 18/10/11 17:07, Marshall Clow a écrit :
On Oct 18, 2011, at 6:42 AM, Dave Abrahams wrote:
on Mon Oct 17 2011, Marshall Clow<mclow.lists-AT-gmail.com> wrote:
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee. It may be true, but it's not an appropriate conclusion from the premises. std::copy also takes all its parameters by value.
Good point - how would you state it, then? "Only reads from the iterators" is the key point (unlike std::copy)
Maybe because these functions don't modify anything? Vicente
On Tue, Oct 18, 2011 at 12:21, Vicente J. Botet Escriba < vicente.botet@wanadoo.fr> wrote:
Le 18/10/11 17:07, Marshall Clow a écrit :
On Oct 18, 2011, at 6:42 AM, Dave Abrahams wrote:
on Mon Oct 17 2011, Marshall Clow<mclow.lists-AT-gmail.com> wrote:
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
It may be true, but it's not an appropriate conclusion from the premises. std::copy also takes all its parameters by value.
Good point - how would you state it, then? "Only reads from the iterators" is the key point (unlike std::copy)
Maybe because these functions don't modify anything?
Vicente
I think the appropriate wording is "All variants of 'all_of' and 'all_of_equal' have no side effects, and therefore provide the strong exception guarantee." The first-order predicate logic equivalence "( for_all_x p(x) ) == not ( for_some_x not p( x ) )" is a very good reason for 'all_of' and 'all_of_equal' to return true when given the empty set as input. -- Casey Carter
on Tue Oct 18 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
On Oct 18, 2011, at 6:42 AM, Dave Abrahams wrote:
on Mon Oct 17 2011, Marshall Clow <mclow.lists-AT-gmail.com> wrote:
[heading Exception Safety]
All of the variants of `all_of` and `all_of_equal` take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
It may be true, but it's not an appropriate conclusion from the premises. std::copy also takes all its parameters by value.
Good point - how would you state it, then? "Only reads from the iterators" is the key point (unlike std::copy)
You state it by saying it's a pure function. However, I agree with Robert that it doesn't help. In fact, I think it hurts. This makes it sound almost like something that might change in the future, rather than like a guarantee clients can rely on. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (9)
-
Casey Carter -
Christopher Jefferson -
Dave Abrahams -
Lorenzo Caminiti -
Marshall Clow -
Neil Groves -
Stewart, Robert -
Sylvester-Bradley, Gareth -
Vicente J. Botet Escriba