Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!tut.cis.ohio-state.edu!seal.cis.ohio-state.edu!ogden
From: ogden@seal.cis.ohio-state.edu (William F Ogden)
Newsgroups: comp.software-eng
Subject: Re: Tolerance
Message-ID: <87999@tut.cis.ohio-state.edu>
Date: 5 Feb 91 00:03:06 GMT
References: <1401@ucl-cs.uucp> <27A9B451.48BF@tct.uucp> <15863.27ad36b6@levels.sait.edu.au> <777@caslon.cs.arizona.edu>
Sender: news@tut.cis.ohio-state.edu
Reply-To: William F Ogden <ogden@cis.ohio-state.edu>
Organization: Ohio State University Computer and Information Science
Lines: 45

In article <777@caslon.cs.arizona.edu> dave@cs.arizona.edu (Dave P. Schaumann) writes:
   ...
>GJ: Can the tolerance idea get off the starting blocks?
   ...
>BH: For me, I think the notion of tolerance is a good one, and is already 
>BH: implicit in many areas of software.

>I'd certainly be interested in hearing a discussion on this topic (tolerance
>implicit in software).
>Numerical analysis aside, I can't imagine a single instance of "close is good
>enough".

One difficulty in recognizing instances of tolerances in software is that
we tend to have a fixation on the first setting where we were exposed to
the notion of tolerance -- namely in the domain of real numbers. There
it got tangled up with the metric notion of the distance between an
ideal desired answer and an actual answer.
So one problem is that we tend to look for the distance metric in our
problem domains. However, there is a more subtle perception bias;
we expect that for a given input, a computation should produce a single
right answer. In other words, we expect that the specifications for
our programs should take the form of functions (which after all is
the familiar object in real analysis).
The better perspective on the problem is that program specifications
generally take the form of a relation between input values and output
values rather than always being a function. This works for the familiar
analysis examples. For say a Cos(x) calculation, the input/output relation
might be R(x,y) = `|y - Cos(x)| < 10^-6', which says that for a given input
x, we're willing to accept a whole host of outputs y. This spec involves
a math function (Cos) and a distance metric, to be sure, but in the end,
they are just incidental concomitants of describing a relation.
A relation then can prescribe the precise range of answers that we are
willing to accept (tolerate) for any given input. Moreover, this perspective
on tolerances is applicable to any programming domain whatsoever. Familiar
examples in everyday computing arise in say (unstable) sorting where our
specifications might insist that records be put in order on a certain
field, but that the output order of records with identical values in
that field are of no moment to us. In fact, certain efficient algorithms
take advantage of this particular tolerance.
Most optimization problems admit to multiple solutions (before we even
begin to consider approximate solutions). Etc.
So I suggest that if we bothered to specify our current software (provided
of course we didn't over specify it), we would find tolerances to be
quite common -- even leaving numerical analysis aside.
/Bill