Re: Motion 42: NO
Guillaume
Thanks for your points. I comment on some of them below.
On 6 Feb 2013, at 21:07, Guillaume Melquiond wrote:
> I vote NO on Motion 42 "Decoration system".
>
> Below are the points I cannot make sense of or am in disagreement with.
>
> - The motion states that "the final result is decorated com if and only
> if the evaluation of the whole expression was common as defined in 5.4"
> in Section 6.3. I understand the "only if" direction, but not the "if"
> direction. Indeed, Section 5.4 deals with level 1 while 6.3 deals with
> level 2, where overflow, precision, and so on, matter. I guess that the
> fact the sentence uses "f" instead of "phi" is not unrelated to my
> confusion.
Actually the reference to 5.4 should be to 5.3 (penultimate paragraph) I think.
You query "if (A) the evaluation of the whole expression was common as defined in 5.4, then (B) the final result is decorated com", right? But isn't the proof, both ways round, a purely graph-theory result of the propagation rule for decorations, with no real-analysis content?
If the evaluation of the whole expression (the f) is common, then by the 5.3 definition the evaluation of each individual library operation (the phi's) is a loose -- i.e. allowed to be in finite precision -- common evaluation.
So (inductive hypothesis) its inputs are decorated com, and (hypothesis A) its local decoration is com, so the propagation rule implies (inductive step) its output is decorated com, so (inductive conclusion) the final result is decorated com, which is (B).
Conversely, if the final result of f is decorated com, then, by the propagation rule, for every phi *on a path from inputs to output in the computational graph*, its inputs must be decorated com, and its local decoration must be com.
I notice a problem though ... do we count evaluations with non-common "dead code" as common? Such as
function y = f(x)
dummy = sqrt(x);
y = sin(x);
end
interval-evaluated at x = [-1,1]? I would say Yes, but the current text does not consider this case.
> - I miss the point of the ill decoration as defined in Section 8.8.2,
> since it is undecidable whether Dom(f) is empty for an arbitrary
> real-valued function f ... Section
It's equally undecidable whether *f is everywhere defined* on a given box, but I don't see you complaining about the "def" decoration on that account!
That is, (as you say) there is no single algorithm that given a function f constructed from a few elementary phi's that you list, always answers correctly the question "is Dom(f) empty?".
Equally, I believe, there is no single algorithm that given such a function f, and a box xx, always answers correctly the question "does Dom(f) contain xx?".
The point about a decoration system is that (with the questions phrased as above) it is allowed to give false negatives but must not give false positives. That is,
If it answers Yes to "is Dom(f) empty?" or "does Dom(f) contain xx?",
we know for certain that is correct.
But if it answers No, we have to take that as "Don't know".
And the presented system achieves that AFAIK.
> 8.8.3 later gives a different meaning to ill, which makes much more
> sense to me, but its relation to the definition of 8.8.2 eludes me.
The definition in 8.8.2 *does* match with 8.8.3 (which, I agree, gives a more intuitive meaning) in a respectable way. Despite Vincent (7 Feb 2013, at 14:44) saying
> "Dom(f) is empty" was introduced by John on 13 Nov 2012
this is NOT so. This idea of "ill" is Arnold Neumaier's invention (early 2011?) and has been discussed at various times.
I & Arnold (possibly others) have done a correctness check, which is necessary technical mumbo-jumbo on the border between math and computer science, summarised at the end of this email. Its conclusions:
- Constants are zero-argument functions.
- NaN is the unique zero-argument real function with empty domain.
- NaN's natural (=tightest) bare interval extension is the interval constant (zero-argument interval function) whose value is Empty; the corresponding decorated interval extension is the decorated interval constant whose value is (Empty,ill). (This depends on the decoration scheme of course.) It is reasonable to give this the name NaI.
- A bare or decorated interval constructor constructs a bare or decorated interval constant, i.e. one of these zero-argument functions.
That's the maths. In addition there is a practical design decision:
(*)
At Level 2, an interval constructor always has to return
*something*, i.e. a datum of the relevant interval type.
- Therefore a failed constructor call such as
text2interval("garbage")
(of some decorated interval type DT) must return a DT-datum.
- Which datum? The DT version of NaI seems a natural choice.
This scheme looks pretty coherent to me. IMO, any contradictions that Nate or anyone else sees in it are due to making a mixture of Nate's definitions and assumptions with those of Motion 42. If anyone claims to have a contradiction, let's see the details.
Further, anyone who thinks NaI should not exist: what do you propose to do about (*)?
I will reply separately to Guillaume's other objections, but need to read the many emails in this thread first.
Regards
John
===============================================================
- Notation: R is the reals, IRbar is the 1788 set of intervals.
<mumbo-jumbo>
(1) The standard defines constants (as in the Ada language) to be *zero-argument functions*. This is mainly a device that makes them fit into the semantics of expressions, without need for special treatment. [A library or language is free to make constants look indistinguishable from values, e.g. nums2interval(2,3) returns the interval [2,3] rather than the function whose value is [2,3] .] But the device has some other useful effects as follows.
(2) A k-argument (scalar) real function is a map from the set R^k of real k-tuples (x_1,...,x_k), to R. Thus a real constant is a map from the singleton set R^0 whose only member is the unique real 0-tuple (), to R. [In linear algebra, () is usually called 0, so R^0 is the trivial vector space {0}.]
(3) There is a 1-1 correspondence between *total* functions R^0->R, and real numbers: these are the *real constants*. Strictly, a literal like "3.45" is a denotation of the function that maps ()\in R^0 to 3.45 \in R.
(4) Additionally there is a unique *partial* function R^0->R whose domain is empty: this is a natural candidate to be called NaN at Level 1. It is not a value, but a function.
(5) Similarly a k-argument interval function is a map from IRbar^k to IRbar; an interval constant is a map from the singleton set IRbar^0 to IRbar.
An interval extension of the real constant with value c is any interval constant whose value is an interval cc containing c; the *natural* interval extension has cc = [c,c].
(6) The natural bare interval extension of the function NaN turns out to be the interval constant whose value is Empty. Its output decoration (same as its local decoration since it has no inputs) is clearly "ill", in the proposed decoration scheme.
(7) Hence the natural decorated interval extension of NaN is (Empty,ill).
</mumbo-jumbo>