Boxes with empty components (was Reasons (not) to vote Motion 27: NO)
P1788, and especially Arnold, Nate and Vincent:
The last few days have seen discussion between Arnold, Nate and Vincent. Independently of this, I had come to conclusions similar to Vincent's, from off-list exchanges with Arnold.
Executive summary:
------------------
- 1788 decorations should primarily be about evaluating free expressions,
not bound ones.
- This makes the statement and proof of the FTDIA quite a bit simpler.
- It shouldn't make explaining decorations harder, and probably makes it easier.
- It accords better with the principle Baker Kearfott often reminds us of, that
the semantics of 1788 should as far as possible be specified locally, i.e. at
the level of individual operations.
Details.
--------
The problem is about evaluating arithmetic expressions (not containing intersection or union) over boxes with empty components. Small, niggling, but it must be got right.
Suppose we define f(u,v,w) = u+w. We evaluate over a box xx=(uu,vv,ww). Then according to the set-theory definition,
Range(f | xx) = Empty if any of uu,vv,ww is empty. (1)
In particular this is so if vv is empty even though v does not occur in the expression f. However (straightforward) interval evaluation cannot yield
f(uu,Empty,vv) = Empty, (2)
but instead returns uu+vv.
"That's OK", it is argued, "because uu+vv encloses Empty, so containment is not violated". Well and good, but presumably we think (2) is a Good Thing. Hence Motion 26 invented the domain() function, which is a way to achieve (2).
More precisely, given a bound expression f(x) = f(x_1,...,x_n), Motion 26 basically redefined evaluation f(xx) = f(xx_1,...,xx_n) to mean (straightforward) interval evaluation applied to xx' = domain(xx), where xx' equals (Empty,...,Empty) if any component of xx is Empty.
domain() is somewhat of a "trick". I wouldn't mind that (successful tricks become natural when one is used to them) if it ALWAYS has
(John to Arnold, 25 Aug 11)
> Desirable Property DP:
> The domain() function should be such that straightforward evaluation of an arithmetic expression over xx' = domain(xx) gives an empty result if any component of xx is empty.
DP holds for any bound expression f(x_1,...,x_n) provided
the expression contains at least one of the x_i. (3)
Unfortunately DP FAILS if
the expression contains no variables, i.e. is constant. (4)
E.g., the natural interval extension of f(x)=1 gives f(Empty) = [1,1] according to our rules.
Arnold (26 Aug 2011) argued this is OK:
> On 08/25/2011 03:33 PM, John Pryce wrote:
>> I wrote
>>> This is a basic theoretical problem.
>> Actually not a problem of decorations as such, but of interval arithmetic if one supports Empty. Why has this never been clearly expressed and discussed?
>
> Because there is no problem. It is only less tight than conceivable, like x-x for a thick interval.
I don't agree it is like x-x. That is built into the basic mathematics of intervals, while domain() is a design decision, a *mechanism* proposed for inclusion in 1788.
To my mind (4) demotes domain() from a "trick" to a "kluge". What will 1788 users think in 10 years time, when they see
It makes f(...,Empty,...) come out to the desired Empty
in all cases *except* when f is a constant expression?
Not good for inspiring confidence in 1788's foundations.
Also, implementations may find better ways than this particular mechanism to achieve the Desirable Property above, and do so without exceptional case (4).
Vincent has expressed a view to which I'm sympathetic. In fact my draft decoration scheme of Jan-Feb 2011 (not circulated except to Arnold) essentially did this, but it was very clumsily expressed, so I ditched it.
On 18 Aug 2011, at 23:34, Vincent Lefevre wrote:
> The specification on free expressions can be derived from the
> specification of individual operations...
>
> This is not true for bound expressions, unless the programmer
> does something about the empty intervals...
I propose P1788 does just this:
A. The primary (recursive) definition of evaluating an expression f shall
be in terms of the variables z_i that *actually occur* in f, so that
interval-evaluation returns Empty if & only if the actual argument
xx_i, associated to some z_i occurring in f, is Empty.
B. The definitions of functions, interval extensions, and all the other
stuff based on set theory shall stay the same.
Interval-evaluation of a function defined by a *bound* expression then gives a *different* result from the present definition if & only if
there is a formal argument that (a) doesn't occur in the
expression and (b) has Empty as its actual argument. (5)
The difference is that the result is nonempty but "should" be empty. As Arnold says
> ... there is no problem. It is only less tight than conceivable ...
However I further suggest:
C. P1788 says that implementations either *shall* or *should* (I'm
not sure which) ensure that Empty is returned if (5) holds.
But does not specify any mechanism by which this shall be done.
D. domain() is not abolished, but acts strictly componentwise to give
a suitable initial decoration to bare intervals.
It seems to me the definition of evaluation, and the proof of the FTDIA, are made simpler by this.
But the devil is probably in the details of item C. How to do it seems to be very different depending on whether 1788 is implemented, say,
- by a library in a run-time typed language such as Matlab;
- by a library in a statically typed language such as C++;
- by intervals being a native type in a language.
Vincent and other language experts, I would appreciate your comments on this. I hope we can avoid at least some of the traps Nick Maclaren warns us of.
John Pryce