dependent and independent intervals, proposal to toss out text2interval. Was re: about emp (was: Motion 42:no)

[Richard Fateman <fateman@xxxxxxxxxxxxxxxxx>]

On 2/19/2013 2:00 AM, Guillaume Melquiond wrote:

.... snip,   , expressions meaning what they say...

I think that whatever advantage can be gained by  allowing an implementation
to process string expressions like "0.1 + pi" is more than overcome by requiring
the library of programs double_float_text2interval etc. to include a parser,
evaluator of arbitrary-precision (or perhaps exact rational) arithmetic, an
algebraic simplifier, and perhaps more.  While some users might be happy
with an interval standard that required Mathematica or Maple or similar programs
to be available to the compiler, or perhaps even run-time system, it seems to me
that this is not appropriate.  Thus I suggest that this text conversion be dropped
and that the only "input of interval constants" required by the standard be
the inf-sup form of two values taken from the host language, that is, read in
by its decimal-to-binary conversion or somehow computed as scalar
values (etc).  A midpoint-radius form could also be standardized.

... <snip>...

Now let us move to more practical considerations. Let us assume that the
text of the standard ends up giving a clear way to infer an _expression_
from the user program. How, as a library implementer, should I implement
it in practice? For instance, in C++, I could go the following way for
multiplication:

        interval operator*(interval const &x, interval const &y) {
          if (&x == &y) return square_of(x);
          else return product_of(x, y);
        }

I test whether the two arguments point to the same memory location, and
if they do, I compute the square instead of the product. Seems clever
and foolproof, right? Wrong. If any of the following happens, the answer
will be incorrect:

1. the user performs memoization (some systems also do it, e.g. Maple);
2. the user performs hash-consing;
3. the environment performs maximal sharing (e.g. garbage collection or
serialization);
4. the compiler performs optimization (e.g. common subexpression
eliminations).

This is all entirely correct. There is a way around problems(1-4) which is to add a sequential
marker to each newly-generated-interval-datum.

thus A :=make_interval(-2,2)   produces  {inf=-2, sup=2, index=1}
         B :=make_interval(-2,2)   produces  {inf=-2, sup=2, index=2}
  ... etc.  so each created interval has a new index tag initially.
  
 then   x:= A*B  is the multiplication of two distinct intervals whose endpoints are equal point-wise.
 but     x:= A*A  is the squaring of a particular interval.  We know it is squaring because of the index.

The index tag may in fact be more elaborate, especially if you have a computer algebra system handy.  e.g the tag
for A^2  could explicitly encode the fact that it is   (index=1)^2.  This is not a new idea in the reliable
computing literature.

So, let me state it clearly: I am convinced it is impossible to write a
library that follows your meaning of expressions, whatever the
programming language. Now, it would be possible to achieve it by
modifying compilers, but you have to wonder whether a feature (from a
non-language standard) that requires modifying compilers is actually
useful.

Just to be complete, I want to point out that it is impossible to write
a library, but only if you expect expressions to be inferred implicitly
from the user code. Now, if you relax your expectations and depend on
the user to explicitly provide expressions, this becomes a whole
different matter. 

yes, I agree;  this can be helped with tags, or in the particular example of x^2, making
sure that power(x,2)  and multiply(x,x) are different operations.

You can then rely on quotation, reflection,
reification, or whatever related technique your programming language
support (all of them do, with more or less syntactic sugar). For
instance, I can write a C++ library that supports the following syntax:

        evaluate(sqrt(- _1 * _1 - 1), interval(-1, 1))

But notice how different it is from what you suggest. In particular, the
user explicitly wrote the syntax tree of the _expression_; it was not
inferred from the program.

It is not necessary to parse a tree at runtime, if the calls etc are stated explicitly
as ...
  define (f(x),  sqrt(difference(-1 , power(x, 2))))
then  f(interval(-1,1))

or some such _expression_.

Note that this issue also occurs with constant constructors. For
instance, nobody on this mailing-list expects interval(0.1) to return an
enclosure of one tenth for languages that do not support decimal
arithmetic. We all know that the compiler will have replaced it by the
binary floating-point number the closest to one tenth beforehand. As a
consequence, we would all suggest to write it interval("0.1") instead.
That process perfectly matches what a quotation is.

I think that this is unnecessary.

If we are allowed to be slightly sloppy, by about half a unit in the last place, we can take
the closest binary approximation for 0.1d0 and widen it by one ulp up and down, and enclose
it.  It turns out that for careful decimal-to-binary conversion, this interval will
also enclose the mathematical  value of 1/10 as well.

If we want to get the tightest interval some work is required but I'm not sure which of several
approaches is simplest.

One way is to form an interval  [1.0d0,1.0d0]  and divide by the scalar 10.0d0. If proper IEEE-754
directed rounding is available, we are done.

Any decimal constant, say 3.141, could be done by scalar_to_interval(3141d0)/10^3.

(I believe that directed rounding here can  be cheaply simulated by default rounding-to-nearest
by bumping 3141  up and down before division.  for example, to get the tightest enclosure
around 1/3, in double-float binary, let eps =  double-float-epsilon = 2.0d0^-53= 1.11022...d-16;
 then create an interval   [ 3141*(1-eps), 3141*(1+eps)]  and then divide, default rounding,
by 10.
)

Another more elaborate way is to make available tight intervals around 1/10, 1/100, etc.


e.g. let n be the result of round(2^55/10) .

 double_interval_tenth  :=  double_make_interval_from_inf_sup(n,n+1)  /2^55


I think there is excessive concern for the exact or closest representation of 0.1.
This is mostly caused by naive users wondering about outputs that have
 strings of ...99999  or  ..000001 in them and not serious scientific computations.

I am unfamiliar with any scientific computation that is impacted by considerations
of radix representation and closeness of approximation to constants that are
exact in decimal but not in binary. Can anyone cite a related paper?

Anyway, this has rambled some, but my suggestion is to eliminate text2interval entirely,
and thereby shorten the standard by several pages.
It also means that creating intervals is no longer potentially undecidable, since
the decision as to whether the interval is proper, i.e. has  inf<=sup is trivial.

 Instead add some constructor functions, if they are not already in the
standard , for example  double_float_inf_sup_2interval, and
other type variants which are functions of the already-existing numeric types in the
host programming language.  These could be single, double, extended floats, or
integers 16, 32, 64, arbitrary length, or exact rationals.  The returned types could
be similarly variable.  Each of these constructors could have a 3rd argument which
would be the decoration,  or another function could be called to put in a decoration
on a bare interval created from two constant scalars.


Richard Fateman