GotW #98: Assertion levels (Difficulty: 5/10)

This special Guru of the Week series focuses on contracts. We covered basic assertions in GotW #97… but not all asserted conditions are created equal.

JG Questions

Given some assertion syntax:

SomeAssert( condition );  // expresses that ‘condition’ must be true

1. Give one example each of an asserted condition whose run-time evaluation is:

a) super cheap

b) arbitrarily expensive

Guru Questions

2. What does the answer to Question 1 imply for assertion checking? Explain.

3. Give an example of an asserted condition that is in general impossible to evaluate, and so cannot be checked. Can these kinds of conditions still be useful?

4. How do these questions help answer:

a) what “levels” of asserted conditions we should be able to express?

b) why the assertions we can “practically” write are a subset of all the ones we might “ideally” like to write?

11 thoughts on “GotW #98: Assertion levels (Difficulty: 5/10)

  1. 1) a) SomeAssert(ptr != nullptr);
    1) b) SomeAssert(std::all_of(std::begin(someVec), std::end(someVec), SomePredicate));

    2) All assertions cannot be done ; their use depends on their cost

    3) Invariants for classes with many members are genrally too expensive to be checked for each member function

    4) a) Always, Debug, Never (assertions are put only for documentation pusposes)
    4) b) It is good that assertions are only one line long, and short

  2. Should there be a syntax in C++ which captures invariants of classes so that some stand-alone program (or theorem proving software) can capture it?

  3. 3. Give an example of an asserted condition that is in general impossible to evaluate:

    const char* some_program_code = …
    assert(program_will_halt(some_program_code))
    auto result = program_result( some_program_code)

  4. 1.a.)
    `assert(abs(sin(x)) <= 1);`
    `assert(size(span1) == size(span2));`

    1.b.)
    `assert(abs(pow(sin(x),2)+pow(cos(x,2)) – 1) 4.a) Usually, given a set of assertions, we are interested in 3 levels: never checked, always checked, check only the cheap ones. But we may also imagine scenarios where we really want to check the expensive assertions from a set of translation units or modules only, and not the other ones.

    And it could turn even into something even more complex. For instance: we may use 2 libraries: A and B, and A is also using B. We want to be sure we are correctly respecting B contracts — not whether A is correctly using B. It would be nice to only turn on the preconditions checks from our calls to B, and not on the calls from A to B.
    (And no, a library does not need to have an API that only exposes wide contracts. See std::stack::pop(), it has a narrow contract.)

    3.)
    It’s impossible to check whether a pointer points to a buffer that guarantees 42 accessible elements. At least, there is no way to express that (yet? We can dream, can’t we?).

    I also often state in some RAII classes where I manually hold memory: “///@invariant single responsible for the memory referenced”. Thankfully, since C++11, unique pointers let’s us express this with strong typing. Yet, it’s now the unique pointers that have this quite impossible to check invariant: “nobody else is responsible for (/of?) this resource”

    Some of there hard/impossible to check assertions could still be checked with a static analysys. For instance, a tool may model this `n_elements_can_be_accessed_in(42, address)`. This means we have somehow another level: “absolutely never check at runtime, but try to exploit it with tools”. (4.a. as well)

    3) & 4.b)
    While simplified assertions may not cover everything we could expect, they can be useful as some kind of milestones. If we imagine something simple like `sqrt(1- cos(x))`, we don’t necessarily have to assert that cos(x) models the abscissa of the point on the unitary(?) circle for the angle x. We can, and should, leave it to unit tests.
    Yet, it’s interesting to be sure that 1-cos(x) is positive as this is the precondition for sqrt().

    There are also other issues with moved-from objects. Non-copyable objects. If we take `sort()` for instance. We may sort a vector of unique pointers. We can checked it’s sorted. But we cannot take a snapshot of the unique pointers, as they are not copyable, to check we have exactly the same element before and after the sort.

  5. Sorry. Something went wrong with wordpress :/
    I’ll try to fix my answers 1.b and 2 without newlines nor ampersands

    1.b.)
    `assert(abs(pow(sin(x),2)+pow(cos(x,2)) – 1) <epsilon);`
    `assert(size(spain1) == size(span2) and sorted(span2) and have_the_same_elements(span1, span2));`

    2.)
    We may not want to pay the execution price for checking all assertions.
    4.a) Usually, given a set of assertions, we are interested in 3 levels: never checked, always checked, check only the cheap ones. But we may also imagine scenarios where we really want to check the expensive assertions from a set of translation units or modules only, and not the other ones.

    And it could turn even into something even more complex. For instance: we may use 2 libraries: A and B, and A is also using B. We want to be sure we are correctly respecting B contracts — not whether A is correctly using B. It would be nice to only turn on the preconditions checks from our calls to B, and not on the calls from A to B.
    (And no, a library does not need to have an API that only exposes wide contracts. See std::stack::pop(), it has a narrow contract.)

  6. 1a) super cheap:

    Example 1:

    template void f(T n)
    {
    assert (n>=0) // Zero cost for T unsigned
    }

    Example 2:

    if(…) // case 1
    { …}
    else if(…) // case 2
    { …}

    else if(…) // case n
    { …}
    else // This must never happen
    { assert (false); }

  7. @Mark:
    > Should there be a syntax in C++ which captures invariants of classes

    Yes, I think there should. Note though that it has not yet been proposed for C++, even in the draft-C++20 contracts design that was removed for further work.

    An upcoming GotW will focus on class invariants. I’m currently planning to write that GotW sandwiched in between one about “general invariant theory” and “non-class invariants.”

    > so that some stand-alone program (or theorem proving software) can capture it?

    Or actually check them at testing time!

    But most people who’ve ever taken a run at checking class invariants, in many languages, have hit a major practicality problem. I’ll cover that problem in that GotW, and why I think it has an elegant solution.

    @Helmut: I was wondering if someone was going to give “program will halt” as an example. :) How about another example that’s actually a compilable expression that would come up in normal C++ code?

    Also, assert(false) is a good cheap example, but I’m going to avoid one that’s quite that simple because assert(false) actually isn’t so much an assertion as it’s a way to say “this is not reachable” to the compiler which isn’t quite the same thing… it’s more about what I cover in paper P2064, “Assumptions”: http://wg21.link/p2064

    @Luc:
    > It would be nice to only turn on the preconditions checks from our calls to B, and not on the calls from A to B.

    Yes, that’s a key observation, thanks for mentioning it! It’s part of the more general fundamental question “what contracts should be checked when testing ,” a key question I’ll cover when we talk about checking assertions later in this series. I won’t cover it in this solution because that issue deserves its own article, but it’s coming up in the next few months.

  8. assert(false) ist not necessarily a hint to the compiler. Consider the following example:

    template
    const T& helmut_max(const T& x, const T&y)
    {
    if(x>=y)
    {
    return x;
    }
    else if(x<y)
    {
    return y;
    }
    assert(false);
    }

    assert(false) could be reached if T were not totally ordered, e.g. try

    helmut_max(4.,nan(0))

  9. It seems that the template arguments are “stolen”. It should be
    template std::totally_ordered T

  10. How about another example that’s actually a compilable expression (that is in general impossible to evaluate, and so cannot be checked) that would come up in normal C++ code?

    1) helmut_max can be changed to such an example:

    template < typename T >
    const T& helmut_max(const T& x, const T&y)
    {
    assert(std::totally_ordered < T >);
    if(x>=y)
    {
    return x;
    }
    return y;
    }

    This version will actually fail to detect the NAN problem.

    2)

    template < class ForwardIt, class T >
    bool checked_binary_search( ForwardIt first, ForwardIt last, const T& value )
    {
    assert(std::is_sorted(first,last));
    return std::binary_search(first, last, value);
    }

    Here it is impossible to check the precondition without violating the complexity guarantee.

  11. @Helmut: Nice! In fact binary_search with is_sorted is exactly the example I wrote up for the solution… which I need to go post now, hold a sec…

Comments are closed.