Containment is necessary but not sufficient...
> Date: Thu, 25 Aug 2011 15:56:28 -0500
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
> To: stds-1788 <STDS-1788@xxxxxxxxxxxxxxxxx>
> Subject: Reminder: Discussion period for Motion 28 ends shortly
>
> P-1788 participants,
>
> This is a reminder that the formal discussion period for
> Motion P1788/0028.01:ContainmentOnly ends with the
> world-wide end of August 25, and the formal voting period
> begins.
>
> I note there has not been much recent discussion on this
> motion, although there was some when it was first put forward.
> Discussion on it may continue during the voting period, but
> the motion itself may not change during the voting period.
>
> Baker
Hi Folks,
Baker is right. I seconded this motion so it would get
discussed & I haven't done any of the discussing. Time
flies when you're doing something else... :-)
Well, let me say a few quick words then.
We are writing a standard. It specifies what one has to
do to be considered a conforming instance of that standard.
But equally important to that end is the specification
(implicitly or explicitly) of what does NOT conform to the
standard.
We MUST have a specification (in the form of a statement
of 'shall') that the correct answer is contained in the
returned result. I don't think anybody has a problem with
that.
But if that is our ONLY specification it would admit many
implementations that all of us would agree are neither
useful nor desireable.
As has been pointed out, an extreme example might be an
implementation that returns [-oo,+oo] for all operations
would conform to such a standard. And, while it would have
the property that the 'true' answer is indeed contained in
the result returned, it is of no use to anyone in learning
anything about the nature of that answer.
Less extreme examples might be implementations that return
answers with loose but nevertheless reasonable (say O(ULP))
errors. They might be of some use but if one cannot say
much about the worst cases of such an implementation one
cannot say much about the 'correctness' of the result other
than that it is contained somewhere in that interval which
was returned, however large.
And such errors grow over time becoming quickly unmanagable.
Another property of a standard is that it must be testable.
That is, there must be a computable procedure that is able
to distinguish conforming implementations from non-conforming
implementations. In other words, a verification test suite.
Now, as a practical matter, the best one can do is to write
a test suite that is designed to catch those proposed
implementations that fail in well known or easy to find ways.
The full cross product of operations (x) operands is an
intractably large set. But well written test programs that
look at a vanishingly small subset can be remarkably good
at finding things that fail to conform.
If our only specification is containment, such a test suite
is easy to write as anything conforms to it. But such a
procedure will NEVER find a counter example.
No, we must further constrain our standard to be very specific
about what behaviors are NOT acceptable. And we must specify
those behaviors in a way that is testable.
For if we do not, how will you ever derive proofs that any
of your algorithms work?
It is for these reasons that I believe we must well define
our standard to have very tight & testable constraints on
acceptable behaviors of conforming implementations. We can
argue just how tight at some later date. But consider that,
within the bounds of tractability, the tighter the better.
Answers are narrower. They are easier to verify. And
proofs become easier (even possible) to write.
Containment is necessary but not sufficient.
Not by a long shot.
Dan