[e-lang] Def. consistency vs Strong exception guarantee
daw at cs.berkeley.edu
Wed Oct 31 23:27:40 EDT 2007
Summary of this email: MarkM's thesis suggests that one way to achieve
defensive consistency is for each method to perform full input validation,
checking explicitly that all preconditions are met before doing anything
else. I'm curious to understand in what cases this is or isn't a good
approach, and to work out the details of this approach. Details follow.
Background: Methods have contracts, which specify preconditions
(obligations on the callers) and postconditions (which the object must
establish if the preconditions were met). Objects may also have object
invariants, which define whether the object is in a consistent state;
method calls must always leave the object in a consistent state.
Concept #1: Say that a contract is "fully-checked" if the implementation
of the method uses runtime checks to check all preconditions listed in
the contract. More precisely, it is "fully-checked" if we can rely upon
the following property: if a caller violates any precondition, then it is
guaranteed that the method will throw an exception at some point during
its execution. It follows that, if a call to some fully-checked method
returns without throwing an exception, then the caller has the right to
expect correct service from that method invocation.
Concept #2: The C++ community has introduced the notion of "strong
exception-safety", aka "the strong guarantee". Let me propose "the
stronger guarantee", which requires: (i) if a method call on object O
throws an exception, then no visible changes to the state of O have been
made at any time during that method call; and, (ii) if the method call
returns without throwing an exception, then at any time that the object
O is externally visible (including immediately after the method call
returns), it must be in a consistent state. (O is externally visible
after the method call returns; also, it may become externally visible
if the method invokes a callback or invokes some other object that may
have a reference to O.)
Example coding style: One way to provide "the stronger guarantee"
might be to have a commit point somewhere in the middle of the method.
All operations that might cause the method to propagate an exception
must occur before the commit point is reached. All operations that might
change the state of the object or make the object visible to others must
occur after the commit point.
Question 1: Suppose we design an object so that every method provides the
stronger guarantee and also fully-checks its contract. Does it follow
that this object is necessarily defensively consistent? (Assume we are
in a single-threaded world.)
Motivation: When code needs to be defensively consistent, I can imagine
programming in an style where we fully-check the contracts and provide
the stronger guarantee. It's possible it might be easier to review code
to determine whether they meet these two conditions than to review for
Question 2: Is this a useful programming style? Is it too restrictive?
Are there useful cases where it is more natural or convenient to establish
defensive consistency by some other means (i.e., in a way that requires
violating stronger exception-safety or failing to fully-check a contract)?
Can you give any examples?
Question 3: Can anyone give an example of a contract or service that
is tricky or non-trivial to implement in a defensively consistent way?
For example, binary search is often used as a standard example of an
algorithm that is simple to specify but somewhat tricky to get right; many
beginning programmers, if asked to implement a binary search, will make
any number of common mistakes. Asking someone to write a binary search
algorithm and then revealing the flaws can be educational. As another
example, MarkM suggested the observer pattern as an example of something
that is quite tricky to get right in a shared-state multi-threaded
system; for most folks new to this area, if you ask them to implement a
ValueHolder, they will probably introduce any number of common hazards.
Having these kinds of examples can be helpfully educational. Are there
any nice examples like this for defensive consistency?
Footnote: I should define my terms. For this email, I say that a
method m() throws an exception E if either: (i) the body of m() itself
throws E and E propagates to the caller of m(), or (ii) m() calls some
method that throws E and this exception propagates to the caller of m().
A method returns if it terminates and does not throw an exception.
More information about the e-lang