Re: Motion 42: NO

[John Pryce <j.d.pryce@xxxxxxxxxx>]

Vincent
<I'm including snippets as both source text & PDF since Michel had trouble with the PDF.>

I'm responding to your comments on the text. They are very useful, though (as you discussed with Baker) many of them are more of wording than content.

On 31 Jan 2013, at 17:13, Vincent Lefevre wrote:
> I vote NO on Motion 42. Here are my comments. My vote would be changed
> to YES if my comments (at least the most important ones) are taken into
> account.
> 
> §5.2, paragraph 2: "no other intervals belong to all of them" to be
> changed to "no other intervals belong to the set of all of them"?
How about "..., and there is no interval outside IR that is supported in all these flavors"?

> §5.2, "Arithmetic operation": "an interval extension of the
> corresponding point function phi". It doesn't seem to be any
> interval extension, but the *natural* interval extension.
True. Changed to "Arithmetic operation: Such an operation is an interval extension, in fact the natural interval extension (Defn 4.2.11), of the corresponding point function phi..."

BUT! This brings up the issue I've written about separately.

> §5.3, first paragraph:
Last para of 5.2 I think.
> If I understand correctly, the notion of
> "loose" / "tight" is mainly for Level 1 and is aimed to be similar
> to the notion of accuracy modes at Level 2.
No, it is intended to apply to both Levels, in fact mainly to Level 2 in practice.
> As specified, it seems
> that any common evaluation is loose. So, concerning the definition
> of "tight", "it is not loose" is not possible.

You are right: indeed, any common evaluation is loose. Bad use of language. In the current version loose common evaluations have their own subclause, which now reads
> At Level 2, common evaluations are usually not computable because of roundoff; instead, an enclosing interval of some finite precision interval type is computed. 
> The notion of a {\bf loose common evaluation} takes account of this. A loose common evaluation derived from a common evaluation $\phi(\~x_1,\~x_2,\ldots,\~x_k) = \~y$ in $\flavCO(\phi)$ is defined to be any
> \begin{align}\label{eq:flavCOloose}
>   \phi(\~x_1,\~x_2,\ldots,\~x_k) = \~y'
> \end{align}
> where $\~y'$ is a member of $\IRb$ containing $\~y$. 
> An element of $\flavCO(\phi)$ is itself loose by this definition, but may be called a {\bf tight} common evaluation to emphasize that its $\~y$ is contained in each derived $\~y'$, above.

Attachment: texshop_image.pdf
Description: Adobe PDF document

> §5.5, about "sharing" for a common evaluation at Level 2: For
> operations with numbers in input and/or output, the number formats
> should be the same (or at least have some language-defined form of
> compatibility). Now, I wonder whether this is worth mentioning.
> 
> I think that "sharing" makes sense only if one has "reproducible
> interval arithmetic" (see §1.8 in Draft 6.3). Something should be
> said about that. In particular, the same evaluation scheme (e.g.
> ordering, contractions...) shall be used.

Good points. I want to keep this fairly short so it now reads as follows referring to an Annex C "Reproducibility".
"It is useful to consider when a flavor-independent result of common evaluation occurs. That is, when does evaluating a given expression, over the same bounded nonempty box in two or more different flavors, give identical results modulo the embedding map? At Level 1, this is always true if the individual operation evaluations are tight.
An implementation may create conditions under which this holds in actual program execution. A prerequisite for this is support of a reproducible mode, see Annex C. In addition it must let flavors “share” at Level 2 by providing: shared interval types, which represent the same finite set of common intervals in each flavor; shared number formats that represent the same set of reals in each flavor; and shared library operations (on the shared types and formats), which when acting on common intervals have identical behavior in each flavor, modulo the embedding map.
Then a common evaluation in reproducible mode that only uses shared types and operations gives identical results in both flavors, modulo the embedding map. More details are in Annex C."
Is that OK?

> BTW, "rounding" (for an interval) should be defined in §3.2. I suppose
> that it is regarded as a mapping of a Level 1 interval x to a Level 2
> interval y containing x.
It's the same as T-interval hull in Table 1 in Levels clause (was §4, currently §5). But I just changed "identical rounding behavior" to "identical behavior" and think it reads OK.

> §6.1, first paragraph: I would replace "for a real-valued function" by
> "for real-valued functions", and "decorated intervals [...] target the
> second" by "the decoration system [...] targets the second".
Yes.

> §6.1, paragraph 5 ("Especially..."): it is said "f restricted to x
> being continuous", but this is not the same as f being continuous
> at each point of x (used for common intervals). In §8.8.2, dac uses
> the latter property, contrary to com (§5.2 and §8.8.10). Is this
> difference intentional? If yes, I think this should be emphasized
> (here and/or later). IIRC, this point was unclear in our private
> discussions (in particular when "bdc" was introduced).

Intentional. I added an explanation in the examples at the end of draft 6.2 §5.2 (now draft 7.0 §6.2). I would be glad if you can check the draft 7.0 text & say what other places should cross-reference this.

> §6.1, last two paragraphs: I would add "IEEE" in front of "754".
I aim to leave such things to our IEEE Style Editor, hopefully just appointed.

> §6.2, paragraph 3: "For diagnostic use it may convey Level 3 or 4
> information, e.g., how an interval is represented, or how memory is
> used." would be possible only for specific intervals, in particular
> not in a common evaluation (unless only one flavor is provided), as
> the "com" decoration shall be used. This is a bit misleading.

I don't follow. Common-ness is only about numerical behaviour. A program running in some debugging mode, say, can store whatever it likes in a tag to an interval (machine addresses, time of day, links to the latest BBC news, ...) without changing the numerics.

> §8.8.1, paragraph 2: §8.8.8 is missing.
Strange. In my copy of what was circulated it's there, "User-supplied functions".

> §8.8.3: It should be made clear that NaI must not be returned if
> the interval interpretation would not return an empty interval,
> even in the case where the true decoration is ill (this was from
> my remarks in our private discussion). For instance, even though
> the implementation may return NaI
NaN, perhaps?
> for sqrt(-1-x^2) for any x, it
> must not return NaI for sqrt(-1-x*x) where x = [-1,1], because
> at Level 1: x*x = [-1,1], -1-x*x = [-2,0], sqrt(-1-x*x) = [0,0].

This is an important technical issue, related to Guillaume's recent ideas.
If one takes the view that "ill" should be used whenever one finds the domain of a function is empty, then IMO your stance is quite illogical. Namely if clever analysis determines that point-function sqrt(-1-x*x) is nowhere defined, then at Level 1, or 2, Empty_ill is exactly what should be returned for sqrt(-1-x*x) where x = [-1,1] or anything else. Why use the clever analysis for half the job (ill) and not the other half (Empty)? But we have discussed this already.

But if one takes the view that NaI is a pragmatic object, that only occurs as a result of bad constructions, is your view logical? I still don't find it so, for the "half the job" reason.

If we had a pragmatic NaI, and also an "ill" that was unconnected to NaI, would that be useful? It's possible but seems OTT to me.

I feel that the whole "Dom(f) is empty" thing is putting people off, and a pragmatic NaI is required, so we should redefine "ill" to be just "the decoration that is applied to NaI and to nothing else". Then Guillaume will have simplified the system by abolishing both "emp" and "ill", in effect.

> The reason to decorrelate the variables is that the implementation
> doesn't know what a variable means exactly (this may be specified
> by the language, but the exact meaning may also be left to the end
> user). By default, the implementation should behave in a safe way.
> Indeed, a variable may represent several mathematical values. For
> instance, a math problem may have its own x_i's, where the index i
> can take a huge number of values, and it would be inefficient (or
> even impossible) to take care of all these different x_i's in a
> program. So, the user may choose to represent each x_i by a single
> interval variable x such that x_i is in x for all i.

One can argue such things but math says what math says, and I'm unconvinced.

> §8.8.4, paragraph 1: is "implementations shall not produce them."
> for arithmetic operations (implied by the beginning of the paragraph)
> only or more generally for all operations (including constructors)?
Unconditionally shall not, if one accepts the reasoning of that paragraph, IMO.

> This is ambiguous. There's also the question of what is specified if
> the user produces a forbidden combination via Level 3 or 4 (e.g. via
> a union in C). I don't think that implementations shall support such
> combinations in input.

This Level 3/4 question is related to Richard Fateman's recent email about "what if [NaN,NaN] is produced?". In any Level 3 representation-scheme of any interval type, bare or decorated, there are almost certainly objects (representation instances) that have no Level 2 meaning. Here, I think [NaN,NaN] represents Empty in Ulrich Kulisch's Level 3 scheme, but might have no meaning in other schemes.

I think from earlier discussions
- A software implementation's debugging mode should check for these at each operation and signal an exception when one is found.
- A hardware implementation can presumably do such a check at zero cost, so it should do so.
- But for a software implementation's production mode to check in this way is probably too costly so one can't expect it.

What should 1788 say about this issue, and where? 
I suggest: a slight expansion of the previous paragraph, put in the Level 3 clause.

More to follow.

John Pryce