P1788: Motion 42 Decoration System PASSES
P1788,
Motion 42 - Decoration System: Yes - 35; No - 6; Needed for quorum - 23 (rules for position papers).
Please note that Motion 42 consists of TWO PARTS, accessible from the link "Decoration System" and the link "Details." We are voting on BOTH.
No votes and comments are appended below. I REALLY value the time and effort invested by many working hard to keep us from mistakes. THANK YOU to all for their efforts.
George Corliss
P1788 Voting Tabulator
Begin forwarded message:
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
> Subject: Correction: RULES FOR POSITION PAPERS ONLY on Motion P1788/M0042: Decoration System -- Voting Period begins
> Date: January 21, 2013 8:20:13 AM CST
> To: <owner-stds-1788@xxxxxxxxxxxxxxxxx>
> Cc: <stds-1788@xxxxxxxxxxxxxxxxx>
> Reply-To: <rbk@xxxxxxxxxxxxx>
>
> P-1788:
>
> I (and the P-1788 web page) misspoke: The
> proposer intended Motion 42 to be a POSITION PAPER.
> That is, you do not need to check the actual wording
> and punctuation. If we agree on the proposed system,
> John will craft the final draft. Only a simple majority
> is required for passage, and don't worry about missing
> commas and awkward wording, as long as you understand
> the intent.
>
> I append the proposer's statement from late November,
> then my original call to vote:
> -------------------------------------------------------------
>
> P1788
>
> Following lively discussions off line, especially with
> Vincent Lefevre and Jürgen Wolff von Gudenberg,
> I submit a revised version of the P1788 decoration system,
> and a motion. I am not submitting that the actual text should
> be accepted, but the motion is
>
> The system here described is accepted as a basis for the P1788 decoration system.
>
> The purpose therefore is promote discussion, and improvements
> and clarifications where needed, and hopefully lead to a consensus.
>
> The present text is based on that of November 2011, but has been much simplified,
> and concentrates on specification rather than on theory. So it is much clearer
> what an implementation shall provide.
>
> The system's "best" decoration, denoted bdc, expresses the fact that a
> function f was found to be "bounded, defined and continuous" on a bounded
> and nonempty input box xx. The original reason for introducing this was
> that, IMO, this is essential for the Motion 36 flavors concept.
> It is equivalent to the idea of a "common evaluation". It is the *only*
> decoration that must exist, and have the same meaning, in all flavors.
>
> However, it also has uses in recognising "harmless" Level 2 overflow:
> perhaps not in all cases where that may be needed, but in many.
>
> Note also that the meaning of "expression" is to be no longer defined
> in the standard. This requires a revision (and simplification) of
> Level 1's §7.5 "Expressions and the functions they define", which I will
> get round to as soon as possible. This is a change to accepted text,
> so AFAIK it will need a separate vote.
>
> -------------------------------------------------------------
> =============================================================
>
> P-1788:
>
> The voting period for this motion herewith begins.
> Voting will continue until after Saturday, February 9, 2013.
> Please give your attention to this important motion.
>
> INCORRECT =========================================
> Voting on this motion will proceed according to the
> RULES FOR STANDARD TEXT. That is,
>
> 1. a 2/3 majority is necessary for the motion to pass, and
>
> 2. any NO votes MUST be accompanied by an explanation of and
> a corresponding commitment to the changes that would cause
> the voter to change the "NO" vote to "YES".
> END INCORRECT =====================================
>
> The motion cannot be changed during voting.
>
> John: Please check the web page to make sure the posted
> motion is current.
>
> Juergen: Please update the web page with this action.
>
> Acting secretary: Please record the transaction in the minutes.
>
> The motion appears in the private area of the IEEE P-1788 site:
>
> http://grouper.ieee.org/groups/1788/private/Motions/AllMotions.html
>
> As usual, please contact me if you need the password to the private
> area.
>
> Best regards,
>
> Baker (acting as chair, P-1788)
> =============================================================
>
> --
>
> ---------------------------------------------------------------
> Ralph Baker Kearfott, rbk@xxxxxxxxxxxxx (337) 482-5346 (fax)
> (337) 482-5270 (work) (337) 993-1827 (home)
> URL: http://interval.louisiana.edu/kearfott.html
> Department of Mathematics, University of Louisiana at Lafayette
> (Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
> Box 4-1010, Lafayette, LA 70504-1010, USA
> ---------------------------------------------------------------
Begin forwarded message:
> From: "Nathan T. Hayes" <nh@xxxxxxxxxxxxxxxxx>
> Subject: Motion 42 question
> Date: January 22, 2013 10:04:03 AM CST
> To: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
> Reply-To: <nh@xxxxxxxxxxxxxxxxx>
>
> Hi George,
>
> I’m looking at the PDF on the P1788 website and it looks to me a significantly reduced version of what was before. Am I really looking at the new motion?
> Also, just to be clear, it is only Clause 6 entitled “Decoration System” in that PDF that we are voting on, as position paper?
>
> Thanks,
>
> Nate
>
Begin forwarded message:
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxxx>
> Subject: Re: Fwd: Motion 42 question
> Date: January 22, 2013 12:42:22 PM CST
> To: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>, Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Reply-To: <rbk@xxxxxxxxxxxxx>
>
> Nate,
>
> The motion consists of TWO PARTS, accessible from the link "Decoration System" and
> the link "Details." We are voting on BOTH.
>
> Note, however, that we have already voted on "flavors."
>
> Baker
>
P-1788:
Please note that Motion 42 consists of TWO PARTS, accessible
from the link "Decoration System" and
the link "Details." We are voting on BOTH.
Note, however, that we have already voted on "flavors," so you
just need to pay attention to Section 6 in the "Decoration System"
part.
Baker
Begin forwarded message:
> From: John Pryce <j.d.pryce@xxxxxxxxxx>
> Subject: Re: [P-1788]: A clarification of Motion 42
> Date: January 23, 2013 2:15:11 AM CST
> To: Ralph Baker Kearfott <rbk@xxxxxxxxxxxxx>, Jürgen Wolff von Gudenberg <wolff@xxxxxxxxxxxxxxxxxxxxxxxxxxx>, George Corliss <george.corliss@xxxxxxxxxxxxx>
>
> On 22 Jan 2013, at 18:45, Ralph Baker Kearfott wrote:
>> Please note that Motion 42 consists of TWO PARTS, accessible
>> from the link "Decoration System" and
>> the link "Details." We are voting on BOTH.
>>
>> Note, however, that we have already voted on "flavors," so you
>> just need to pay attention to Section 6 in the "Decoration System"
>> part.
>
> That should clarify what the motion is about. I hope we don't have another motion supported by more than one file, but if we do, maybe Juergen can find a clearer way for the Motions web page to show this.
>
> John
Begin forwarded message:
> From: Dmitry Nadezhin <dmitry.nadezhin@xxxxxxxxxx>
> Subject: Re: Correction: RULES FOR POSITION PAPERS ONLY on Motion P1788/M0042: Decoration System -- Voting Period begins - NO
> Date: January 26, 2013 8:54:50 PM CST
> To: <stds-1788@xxxxxxxxxxxxxxxxx>
>
> I vote NO for motion 42.
> I would vote YES if section 8.8.7 "Non-arithmetic operations"
> gives special rules for decorated version of operation "case(c,g,h)".
> Below I demonstrate what happens if decorated version of case(c,g,h) is defined by rules of section 8.8.6.
>
> -Dima
>
> ====
>
> Consider a few examples with differnt g but with the same c and h:
> case( [1,2]_com, [3,4]_com, [5,6]_com)
> case( [1,2]_com, [3,4]_emp, [5,6]_com)
> case( [1,2]_com, [3,4]_ill, [5,6]_com)
> case( [1,2]_com, Empty_emp, [5,6]_com)
> case( [1,2]_com, Empty_ill, [5,6]_com)
>
> Natural interval extensios of bare interval version are
> case( [1,2], [3,4], [5,6]) = [5,6]
> case( [1,2], Empty, [5,6]) = Empty
>
> Standard says that implementation shall provide the following interval extension
> case( [1,2], [3,4], [5,6]) = [5,6]
> case( [1.2], Empty, [5,6]) = [5,6]
> So if c > 0, we can avoid computation of subexpression g.
>
> If we apply rules of section 8.8.6 we obtain
> case( [1,2]_com, [3,4]_com, [5,6]_com) = [5,6]_com
> case( [1,2]_com, [3,4]_emp, [5,6]_com) = [5,6]_emp
> case( [1,2]_com, [3,4]_ill, [5,6]_com) = [5,6]_ill
> case( [1,2]_com, Empty_emp, [5,6]_com) = [5,6]_emp
> case( [1,2]_com, Empty_ill, [5,6]_com) = [5,6]_ill
> We can't avoid computation of subexpression g using such rules.
>
> ====
>
> ----- Исходное сообщение -----
> От: rbk@xxxxxxxxxxxx
> Кому: owner-stds-1788@xxxxxxxxxxxxxxxxx
> Копия: stds-1788@xxxxxxxxxxxxxxxxx
> Отправленные: Понедельник, 21 Январь 2013 г 18:23:07 GMT +04:00 Абу-Даби, Маскат
> Тема: Correction: RULES FOR POSITION PAPERS ONLY on Motion P1788/M0042: Decoration System -- Voting Period begins
>
> P-1788:
>
> I (and the P-1788 web page) misspoke: The
> proposer intended Motion 42 to be a POSITION PAPER.
> That is, you do not need to check the actual wording
> and punctuation. If we agree on the proposed system,
> John will craft the final draft. Only a simple majority
> is required for passage, and don't worry about missing
> commas and awkward wording, as long as you understand
> the intent.
>
> I append the proposer's statement from late November,
> then my original call to vote:
> -------------------------------------------------------------
>
> P1788
>
> Following lively discussions off line, especially with
> Vincent Lefevre and Jürgen Wolff von Gudenberg,
> I submit a revised version of the P1788 decoration system,
> and a motion. I am not submitting that the actual text should
> be accepted, but the motion is
>
> The system here described is accepted as a basis for the P1788 decoration system.
>
> The purpose therefore is promote discussion, and improvements
> and clarifications where needed, and hopefully lead to a consensus.
>
> The present text is based on that of November 2011, but has been much simplified,
> and concentrates on specification rather than on theory. So it is much clearer
> what an implementation shall provide.
>
> The system's "best" decoration, denoted bdc, expresses the fact that a
> function f was found to be "bounded, defined and continuous" on a bounded
> and nonempty input box xx. The original reason for introducing this was
> that, IMO, this is essential for the Motion 36 flavors concept.
> It is equivalent to the idea of a "common evaluation". It is the *only*
> decoration that must exist, and have the same meaning, in all flavors.
>
> However, it also has uses in recognising "harmless" Level 2 overflow:
> perhaps not in all cases where that may be needed, but in many.
>
> Note also that the meaning of "expression" is to be no longer defined
> in the standard. This requires a revision (and simplification) of
> Level 1's §7.5 "Expressions and the functions they define", which I will
> get round to as soon as possible. This is a change to accepted text,
> so AFAIK it will need a separate vote.
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"?
§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.
§5.3, first paragraph: 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. As specified, it seems
that any common evaluation is loose. So, concerning the definition
of "tight", "it is not loose" is not possible.
§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.
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.
§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".
§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).
§6.1, last two paragraphs: I would add "IEEE" in front of "754".
§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.
§8.8.1, paragraph 2: §8.8.8 is missing.
§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 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].
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.
§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)?
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.
§8.8.4, paragraph 2: the relation between this paragraph for y_ill
with nonempty y and §8.8.3 is not clear.
§8.8.7: With the rule given on NaI, code ending with something like
(e.g. for piecewise functions):
y = convexHull(u_du,v_dv)
dy = dx
or
y_dy = convexHullDec(u_du,v_dv)
may be wrong if NaI can occur in intermediate results! There should
be a note with some warning. I suspect problems may occur in practice
with parameterized intervals (a function may become nowhere defined
for some values of the parameter). This is a problem with specific
rules for NaI: here a NaI can be produced by evaluating a function
that is never defined, but having such an operation on intervals is
not necessarily a user error.
§8.8.9, Example (i): Replace "2½" by "2+½"? I don't know whether "2½"
is a common notation. However it may be ambiguous.
§8.8.10, definition of "com": about "and the computed interval f(x)
is bounded", I would add (perhaps in the notes, at least more clearly
than in the third note) that this condition is needed only at Level 2
(since all the intervals we consider in the standard are closed), and
an unbounded interval is necessarily a consequence of an overflow.
§8.8.10, "Each arithmetic operation gives com as its local decoration
if the conditions (30) are satisfied.", just after (31): is this a
"shall" or a "should"? And I would add "in" or "of" before "(30)",
since (30) seems to be the whole table rather than the conditions.
§8.8.10, "The propagation rule [...] is" (next line): replace "rule
[...] is" by "rules [...] are" (the plural is used in the notes and
it looks better to me)?
§8.8.11: Since decorations trv, emp, ill and dac are mentioned,
I suppose that compressed arithmetic is specified only for the
set-based flavor (and the common one). This should be said.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxxx>
> Subject: Re: Motion 42: NO
> Date: February 1, 2013 7:22:24 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> Reply-To: <rbk@xxxxxxxxxxxxx>
>
> Vincent,
>
> Although your comments will undoubtedly be useful, there was
> some confusion at the beginning of the vote concerning whether
> the motion represented actual text or just a position. Although
> the motion was presented as actual text, the proposer meant
> for it to be as a position paper. Thus, even though there
> might be awkward wording or incorrect placement of commas, etc.,
> if you understood what it is saying, you should base your "yes" or
> "no" vote on whether or not you agree generally with the ideas in it.
>
> In view of this, you are welcome to change your vote, or keep it as it is.
>
> Best regards,
>
> Baker
>
> On 01/31/2013 11:13 AM, 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"?
>>
>> §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.
>>
>> §5.3, first paragraph: 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. As specified, it seems
>> that any common evaluation is loose. So, concerning the definition
>> of "tight", "it is not loose" is not possible.
>>
>> §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.
>>
>> 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.
>>
>> §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".
>>
>> §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).
>>
>> §6.1, last two paragraphs: I would add "IEEE" in front of "754".
>>
>> §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.
>>
>> §8.8.1, paragraph 2: §8.8.8 is missing.
>>
>> §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 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].
>>
>> 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.
>>
>> §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)?
>> 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.
>>
>> §8.8.4, paragraph 2: the relation between this paragraph for y_ill
>> with nonempty y and §8.8.3 is not clear.
>>
>> §8.8.7: With the rule given on NaI, code ending with something like
>> (e.g. for piecewise functions):
>> y = convexHull(u_du,v_dv)
>> dy = dx
>> or
>> y_dy = convexHullDec(u_du,v_dv)
>> may be wrong if NaI can occur in intermediate results! There should
>> be a note with some warning. I suspect problems may occur in practice
>> with parameterized intervals (a function may become nowhere defined
>> for some values of the parameter). This is a problem with specific
>> rules for NaI: here a NaI can be produced by evaluating a function
>> that is never defined, but having such an operation on intervals is
>> not necessarily a user error.
>>
>> §8.8.9, Example (i): Replace "2½" by "2+½"? I don't know whether "2½"
>> is a common notation. However it may be ambiguous.
>>
>> §8.8.10, definition of "com": about "and the computed interval f(x)
>> is bounded", I would add (perhaps in the notes, at least more clearly
>> than in the third note) that this condition is needed only at Level 2
>> (since all the intervals we consider in the standard are closed), and
>> an unbounded interval is necessarily a consequence of an overflow.
>>
>> §8.8.10, "Each arithmetic operation gives com as its local decoration
>> if the conditions (30) are satisfied.", just after (31): is this a
>> "shall" or a "should"? And I would add "in" or "of" before "(30)",
>> since (30) seems to be the whole table rather than the conditions.
>>
>> §8.8.10, "The propagation rule [...] is" (next line): replace "rule
>> [...] is" by "rules [...] are" (the plural is used in the notes and
>> it looks better to me)?
>>
>> §8.8.11: Since decorations trv, emp, ill and dac are mentioned,
>> I suppose that compressed arithmetic is specified only for the
>> set-based flavor (and the common one). This should be said.
>>
I vote NO on Motion 42.
There are several reasons I vote NO:
-- Against the intent of Motion 8, the Motion 42 doesn't provide
decorated interpretations of Empty such as (Empty,DEF), (Empty,DAC). For
example, section 8.8.7 says decorated intersection operation may provide a
decoration min(dx,dy), where dx and dy are the decorations of the input
operands. So this gives:
([1,2],dac) intersect ([3,4],dac)
= ([1,2] intersect [3,4],min(dac,dac))
= (Empty,dac)
But by section 8.8.4 the empty set is not permitted to be decorated with
decoration dac, so the specification allows implementations that give
contradictory results.
-- I believe everyone agrees Empty is a set. But if Empty is also an
interval, then to call (Empty,ILL) a "decorated interval" on the one hand
and "not an interval" on the other hand doesn't make any sense to me (it is
a contradiction);
-- The ILL decoration may require strong Computer Algebra System
(CAS) to prove; and even if such CAS is available, the ILL decoration may
not always be provable. I think this decoration is unnecessary, too complex
and should be dropped;
-- Since Motion 42 does not allow Empty to be decorated with
decorations such as DEF and DAC, the motion must define these bare
decorations as the compressed decorated intervals (Entire,DEF) and
(Entire,DAC) respectively. This leads to what in my view is a very buggy
compressed interval arithmetic system that may return false positives and
strange, unexpected results. I would warn people not to trust it. For
example, suppose the user specifies the threshold level such that any
operation that is not defined and continuous is considered to be an error:
[1,2] \subseteq floor([0,6])
= [1,2] \subseteq ([0,6],DEF) // Full decorated
result
= [1,2] \subseteq DEF // compress non-DAC result
= [1,2] \subseteq Entire // promote bare decoration
DEF to Entire
= true
This is misleading because [1,2] is not a subset of any defined and
continuous range of floor([0,6]). It would be much better to have bare
decorations promote to Empty instead of Entire:
[1,2] \subseteq floor([0,6])
= [1,2] \subseteq ([0,6],DEF) // Full decorated
result
= [1,2] \subseteq DEF // compress non-DAC result
= [1,2] \subseteq Empty // promote bare decoration
DEF to Empty
= false
But section 8.8.4 does not allow this. More serious containment violations
may also occur with the Motion 42 scheme:
[1,2] \subseteq floor([5,6])
= [1,2] \subseteq ([5,6],DEF) // Full decorated
result
= [1,2] \subseteq DEF // compress non-DAC result
= [1,2] \subseteq Entire // promote bare decoration
DEF to Entire
= true
This is a false positive, since [1,2] is not a subset of [5,6] regardless if
[5,6] is defined and continuous or not.
-- I understand compressed interval arithmetic was removed from
Motion 42, but it appears these problems will remain when we do get to it.
-- Decoration system with EIN that gives containment order
EIN \subseteq DAC \subseteq DEF \subseteq GAP \supseteq NDF
\supseteq EIN
fixes most of the troubles listed above, yet such amendment was not made. I
would likely have voted YES if it had been.
Nate
Begin forwarded message:
> I agree with Nate that this motion appears to have too many serious flaws.
>
> Bill [Walster]
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.
- 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. (And it does not even have to be that arbitrary:
you just need addition, multiplication, floor, conditional, and a
function that is not defined on the whole real line, say square root.)
The note at the end of that section does not say otherwise. Section
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.
- I do not understand why intersectionDec and convexHullDec do not have
symmetric behaviors with respect to propagating decorations. If
convexHullDec returns the tightest decoration containing both input
decorations, then intersectionDec should return the tightest decoration
contained in both input decorations. (I know it does not always exist,
but maybe it is the symptom of a bigger issue.) Or, in the other
direction, if intersectionDec returns the min of the input decorations,
then convexHullDec should return the max. In other words, the lattice
structure is lost once decorations are added to intervals according to
Section 8.8.7, which troubles me.
- Sections 8.8.2 and 8.8.10 define decorations as both a property of the
input intervals and the behavior of the function on these inputs. I am
fine with decorations characterizing the behavior of the function, but
not with taking inputs into account. More precisely, I feel that def,
dac, and com, should not require the inputs to be nonempty, and com
should not require the inputs to be bounded. They should only require
that input intervals are part of the domain. Note that I am fine with
both definitions of newDec and I am also fine with the way decorations
propagate from inputs to outputs.
- I do not agree with com requiring the computed interval to be bounded
at level 2. I feel that the boundedness should only be required at level
1. In particular, I do not see what is gained from stripping com in case
of a harmless overflow. What is the point of com if an unbounded
interval from the point of view of the interval type is necessarily
unbounded from the point of view of the decorations? Any information
about what the mathematical function actually computes is lost.
- Finally, the emp decoration seems superfluous to me. There is no point
in decorating a nonempty interval with an emp decoration (except maybe
for wreaking havoc in an interval library), so the emp decoration could
just as well be removed. An empty interval would then be decorated with
trv when it does not designate a NaI.
Best regards,
Guillaume
On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
> - 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. (And it does not even have to be that arbitrary:
> you just need addition, multiplication, floor, conditional, and a
> function that is not defined on the whole real line, say square root.)
The fact that it is undecidable whether Dom(f) is empty is not a
problem, since an implementation can return emp instead (the best
decoration is not required).
> The note at the end of that section does not say otherwise. Section
> 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.
I agree, there seems to be a problem with the definition.
For instance, take f(x) = x^2 and xx = (Empty,ill). One would
get f(xx) = (Empty,ill), even though Dom(f) is not empty.
I think the definition should be replaced by: Dom(f) is empty and/or
at least one of the inputs has the ill decoration (i.e. is a NaI).
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> Le jeudi 07 février 2013 à 14:07 +0100, Vincent Lefevre a écrit :
>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>>> - 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. (And it does not even have to be that arbitrary:
>>> you just need addition, multiplication, floor, conditional, and a
>>> function that is not defined on the whole real line, say square root.)
>>
>> The fact that it is undecidable whether Dom(f) is empty is not a
>> problem, since an implementation can return emp instead (the best
>> decoration is not required).
>
> That is right: as an implementer, I would always return emp, because I
> would have no way to decide whether the function has an empty domain.
> This defeats the point of such a definition of ill.
>
>>> The note at the end of that section does not say otherwise. Section
>>> 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.
>>
>> I agree, there seems to be a problem with the definition.
>> For instance, take f(x) = x^2 and xx = (Empty,ill). One would
>> get f(xx) = (Empty,ill), even though Dom(f) is not empty.
>>
>> I think the definition should be replaced by: Dom(f) is empty and/or
>> at least one of the inputs has the ill decoration (i.e. is a NaI).
>
> Do people really care about functions that are defined nowhere?
>
> My point was that defining the output decoration as "one of the inputs
> has the ill decoration" seems like the only meaningful definition to me.
> Trying to relate that decoration to functions with empty domains does
> not bring anything, neither to the user nor to the implementer.
>
> Best regards,
>
> Guillaume
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: Re: Meaning of the ill decoration (was: Motion 42: NO)
> Date: February 7, 2013 8:44:39 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-07 14:54:36 +0100, Guillaume Melquiond wrote:
>> Le jeudi 07 février 2013 à 14:07 +0100, Vincent Lefevre a écrit :
>>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>>>> - 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. (And it does not even have to be that arbitrary:
>>>> you just need addition, multiplication, floor, conditional, and a
>>>> function that is not defined on the whole real line, say square root.)
>>>
>>> The fact that it is undecidable whether Dom(f) is empty is not a
>>> problem, since an implementation can return emp instead (the best
>>> decoration is not required).
>>
>> That is right: as an implementer, I would always return emp, because I
>> would have no way to decide whether the function has an empty domain.
>> This defeats the point of such a definition of ill.
>
> The "Dom(f) is empty." was introduced by John on 13 Nov 2012. Now I
> wonder why. I thought it was copied from ndf ("nowhere defined") of
> Motion 27A, but ndf was more like emp.
>
> An implementation that can analyse the expressions (e.g. if P1788
> is implemented by a compiler) could return ill in some cases, such
> as sqrt(-x^2-1). But...
>
>> Do people really care about functions that are defined nowhere?
>
> I don't think so.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Michel Hack <mhack@xxxxxxx>
> Subject: Re: Meaning of the ill decoration (was: Motion 42: NO)
> Date: February 7, 2013 9:03:06 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> The primary purpose of the "ill" decoration is to permit interval
> constructors to report that their (non-interval) arguments were
> invalid, i.e. did not describe ANY interval, not even Empty.
>
> This notion is relevant and should not be discarded.
>
> I never liked the notion that functions should try to report whether
> their domain was empty. It is not even an extrapolation from the
> behaviour of constructors: all arguments of interval functions are
> intervals except for NaI (i.e. Empty_ill), which explicitly denotes
> not being an interval.
>
> Michel.
> ---Sent: 2013-02-07 15:12:52 UTC
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: about com (was: Motion 42: NO)
> Date: February 7, 2013 7:38:51 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>> - 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.
>
> As I understand it, this means that one takes the same definition
> of common at Level 2: instead of considering the Level 1 evaluation,
> one considers the Level 2 evaluation.
>
>> - I do not agree with com requiring the computed interval to be bounded
>> at level 2. I feel that the boundedness should only be required at level
>> 1. In particular, I do not see what is gained from stripping com in case
>> of a harmless overflow. What is the point of com if an unbounded
>> interval from the point of view of the interval type is necessarily
>> unbounded from the point of view of the decorations? Any information
>> about what the mathematical function actually computes is lost.
>
> The primary goal of com is not to give a property of the function
> but to record whether the evaluation does not depend on the flavor
> (assuming identical rounding and some form of reproducibility). As
> some flavors (e.g. Kaucher) do not have unbounded intervals, it was
> necessary to reject overflows.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
> Subject: Re: about com (was: Motion 42: NO)
> Date: February 7, 2013 8:03:56 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Le jeudi 07 février 2013 à 14:38 +0100, Vincent Lefevre a écrit :
>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>>> - I do not agree with com requiring the computed interval to be bounded
>>> at level 2. I feel that the boundedness should only be required at level
>>> 1. In particular, I do not see what is gained from stripping com in case
>>> of a harmless overflow. What is the point of com if an unbounded
>>> interval from the point of view of the interval type is necessarily
>>> unbounded from the point of view of the decorations? Any information
>>> about what the mathematical function actually computes is lost.
>>
>> The primary goal of com is not to give a property of the function
>> but to record whether the evaluation does not depend on the flavor
>> (assuming identical rounding and some form of reproducibility). As
>> some flavors (e.g. Kaucher) do not have unbounded intervals, it was
>> necessary to reject overflows.
>
> It might not have been the primary goal, but the motion explicitly
> defines com as "Definition: x is a bounded, nonempty subset of Dom(f); f
> is continuous at each point of x; and the computed interval f(x) is
> bounded". The fact that it talks about the domain and continuity of the
> mathematical function does not leave much leeway for interpretation.
>
> Now, if the actual goal was that the evaluation does not depend on the
> flavor, it could have been defined just as that: "Definition: the exact
> same interval would have been computed for f(x) with any of the other
> flavors available." At least it would not suffer from the
> reproducibility issue which you point out.
>
> Best regards,
>
> Guillaume
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: Re: about com (was: Motion 42: NO)
> Date: February 7, 2013 8:50:34 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-07 15:03:56 +0100, Guillaume Melquiond wrote:
>> Now, if the actual goal was that the evaluation does not depend on the
>> flavor, it could have been defined just as that: "Definition: the exact
>> same interval would have been computed for f(x) with any of the other
>> flavors available." At least it would not suffer from the
>> reproducibility issue which you point out.
>
> But what if P1788 is implemented by a library, and only the
> compiler controls the reproducibility?
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: "Kreinovich, Vladik" <vladik@xxxxxxxx>
> Subject: RE: about com (was: Motion 42: NO)
> Date: February 7, 2013 9:55:53 AM CST
> To: 'Vincent Lefevre' <vincent@xxxxxxxxxx>, stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> While we have started understanding decorations for the usual flavor intervals, we are far from understanding them for other flavors, so it may be better to explicitly define them for the usual flavor and leave a vague statement about possibility of extending to other flavors?
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: about emp (was: Motion 42: NO)
> Date: February 7, 2013 7:50:19 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>> - Finally, the emp decoration seems superfluous to me. There is no point
>> in decorating a nonempty interval with an emp decoration (except maybe
>> for wreaking havoc in an interval library), so the emp decoration could
>> just as well be removed. An empty interval would then be decorated with
>> trv when it does not designate a NaI.
>
> IIRC, there can be problems with that. For instance, take zz = g(yy)
> where yy is Empty. Since g is defined and continuous on the empty set
> yy, one can return zz = (Empty,dac). But now assume that yy wasn't
> actually an input, but yy = f(xx) for some non-empty xx, e.g.
> sqrt([-2,-1]). So, one would get:
>
> (g o f)(xx) = (Empty,dac)
>
> which is wrong.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 7, 2013 8:07:27 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Le jeudi 07 février 2013 à 14:50 +0100, Vincent Lefevre a écrit :
>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>>> - Finally, the emp decoration seems superfluous to me. There is no point
>>> in decorating a nonempty interval with an emp decoration (except maybe
>>> for wreaking havoc in an interval library), so the emp decoration could
>>> just as well be removed. An empty interval would then be decorated with
>>> trv when it does not designate a NaI.
>>
>> IIRC, there can be problems with that. For instance, take zz = g(yy)
>> where yy is Empty. Since g is defined and continuous on the empty set
>> yy, one can return zz = (Empty,dac). But now assume that yy wasn't
>> actually an input, but yy = f(xx) for some non-empty xx, e.g.
>> sqrt([-2,-1]). So, one would get:
>>
>> (g o f)(xx) = (Empty,dac)
>>
>> which is wrong.
>
> As I understand it, decorations propagate from inputs to output and you
> can never get an output with a stronger decoration than an input. So, on
> your example, you would get:
>
> f(xx) = (Empty,trv)
> g(f(xx)) = (Empty,trv)
>
> which is right.
>
> Best regards,
>
> Guillaume
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 7, 2013 9:11:29 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-07 15:07:27 +0100, Guillaume Melquiond wrote:
>> Le jeudi 07 février 2013 à 14:50 +0100, Vincent Lefevre a écrit :
>>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>
> [Note: this was together with your "I feel that def, dac, and com,
> should not require the inputs to be nonempty".]
>
>>>> - Finally, the emp decoration seems superfluous to me. There is no point
>>>> in decorating a nonempty interval with an emp decoration (except maybe
>>>> for wreaking havoc in an interval library), so the emp decoration could
>>>> just as well be removed. An empty interval would then be decorated with
>>>> trv when it does not designate a NaI.
>>>
>>> IIRC, there can be problems with that. For instance, take zz = g(yy)
>>> where yy is Empty. Since g is defined and continuous on the empty set
>>> yy, one can return zz = (Empty,dac). But now assume that yy wasn't
>>> actually an input, but yy = f(xx) for some non-empty xx, e.g.
>>> sqrt([-2,-1]). So, one would get:
>>>
>>> (g o f)(xx) = (Empty,dac)
>>>
>>> which is wrong.
>>
>> As I understand it, decorations propagate from inputs to output and you
>> can never get an output with a stronger decoration than an input.
>
> IIRC, in our discussions it was allowed to improve a decoration
> if the condition associated with the property was satisfied.
>
> Otherwise...
>
>> So, on your example, you would get:
>>
>> f(xx) = (Empty,trv)
>> g(f(xx)) = (Empty,trv)
>>
>> which is right.
>
> OK. I wonder whether this can be a way to re-introduce the empty
> input under some other form: (Empty,dac). Otherwise, if you decide
> that Empty as an input has the trv decoration, this would mean that
> (Empty,def) and (Empty,dac) would not be possible in practice, which
> can be expressed by the current condition "x nonempty" for def and
> dac.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 7, 2013 12:07:11 PM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Le jeudi 07 février 2013 à 16:11 +0100, Vincent Lefevre a écrit :
>> On 2013-02-07 15:07:27 +0100, Guillaume Melquiond wrote:
>>> Le jeudi 07 février 2013 à 14:50 +0100, Vincent Lefevre a écrit :
>>>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>>
>> [Note: this was together with your "I feel that def, dac, and com,
>> should not require the inputs to be nonempty".]
>
> And I still think so, due to the propagation rule below.
>
>>>>> - Finally, the emp decoration seems superfluous to me. There is no point
>>>>> in decorating a nonempty interval with an emp decoration (except maybe
>>>>> for wreaking havoc in an interval library), so the emp decoration could
>>>>> just as well be removed. An empty interval would then be decorated with
>>>>> trv when it does not designate a NaI.
>>>>
>>>> IIRC, there can be problems with that. For instance, take zz = g(yy)
>>>> where yy is Empty. Since g is defined and continuous on the empty set
>>>> yy, one can return zz = (Empty,dac). But now assume that yy wasn't
>>>> actually an input, but yy = f(xx) for some non-empty xx, e.g.
>>>> sqrt([-2,-1]). So, one would get:
>>>>
>>>> (g o f)(xx) = (Empty,dac)
>>>>
>>>> which is wrong.
>>>
>>> As I understand it, decorations propagate from inputs to output and you
>>> can never get an output with a stronger decoration than an input.
>>
>> IIRC, in our discussions it was allowed to improve a decoration
>> if the condition associated with the property was satisfied.
>
> According to 8.8.6/25, this is not allowed. (And I am perfectly fine
> with it not being allowed. I think it is the only way of defining it
> correctly.)
>
>> Otherwise...
>>
>>> So, on your example, you would get:
>>>
>>> f(xx) = (Empty,trv)
>>> g(f(xx)) = (Empty,trv)
>>>
>>> which is right.
>>
>> OK. I wonder whether this can be a way to re-introduce the empty
>> input under some other form: (Empty,dac). Otherwise, if you decide
>> that Empty as an input has the trv decoration, this would mean that
>> (Empty,def) and (Empty,dac) would not be possible in practice, which
>> can be expressed by the current condition "x nonempty" for def and
>> dac.
>
> Just to clear any potential misunderstanding, I was not saying that
> empty is only allowed to have the trv decoration. What I was saying is
> that the emp decoration is redundant with the trv decoration: there is
> no situation that I can think of where empty_emp could not be encoded by
> empty_trv, and since nonempty_emp does not make sense, that does not
> leave any purposeful meaning for decoration emp.
>
> In other words, I could well live with empty_dac and empty_def for the
> sake of uniformity and mathematical cleanness. To summarize, these are
> all the possible cases:
>
> f(empty_dac) = empty_dac (or empty_def or empty_trv)
> f(empty_def) = empty_def (or empty_trv)
> f(empty_trv) = empty_trv
> f(empty_ill) = empty_ill
>
> newDec(empty) = empty_trv
>
> sqrt([-2,-1]_dac) = empty_trv
> sqrt([-2,-1]_def) = empty_trv
> sqrt([-2,-1]_trv) = empty_trv
>
> Best regards,
>
> Guillaume
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 7, 2013 8:14:52 PM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-07 19:07:11 +0100, Guillaume Melquiond wrote:
>> Le jeudi 07 février 2013 à 16:11 +0100, Vincent Lefevre a écrit :
>>> On 2013-02-07 15:07:27 +0100, Guillaume Melquiond wrote:
>>>> Le jeudi 07 février 2013 à 14:50 +0100, Vincent Lefevre a écrit :
>>>>> On 2013-02-06 22:07:15 +0100, Guillaume Melquiond wrote:
>>>
>>> [Note: this was together with your "I feel that def, dac, and com,
>>> should not require the inputs to be nonempty".]
>>
>> And I still think so, due to the propagation rule below.
>>
>>>>>> - Finally, the emp decoration seems superfluous to me. There
>>>>>> is no point in decorating a nonempty interval with an emp
>>>>>> decoration (except maybe for wreaking havoc in an interval
>>>>>> library), so the emp decoration could just as well be
>>>>>> removed. An empty interval would then be decorated with trv
>>>>>> when it does not designate a NaI.
>>>>>
>>>>> IIRC, there can be problems with that. For instance, take zz = g(yy)
>>>>> where yy is Empty. Since g is defined and continuous on the empty set
>>>>> yy, one can return zz = (Empty,dac). But now assume that yy wasn't
>>>>> actually an input, but yy = f(xx) for some non-empty xx, e.g.
>>>>> sqrt([-2,-1]). So, one would get:
>>>>>
>>>>> (g o f)(xx) = (Empty,dac)
>>>>>
>>>>> which is wrong.
>>>>
>>>> As I understand it, decorations propagate from inputs to output and you
>>>> can never get an output with a stronger decoration than an input.
>>>
>>> IIRC, in our discussions it was allowed to improve a decoration
>>> if the condition associated with the property was satisfied.
>>
>> According to 8.8.6/25, this is not allowed. (And I am perfectly fine
>> with it not being allowed. I think it is the only way of defining it
>> correctly.)
>
> No, the implementation can use additional knowledge to provide a
> different decoration. See the last example of 8.8.3, for instance.
>
>> Just to clear any potential misunderstanding, I was not saying that
>> empty is only allowed to have the trv decoration. What I was saying is
>> that the emp decoration is redundant with the trv decoration: there is
>> no situation that I can think of where empty_emp could not be encoded by
>> empty_trv, and since nonempty_emp does not make sense, that does not
>> leave any purposeful meaning for decoration emp.
>
> nonempty_emp makes sense for sqrt(-x*x-1) with x = [-1,1]. As an
> expression on intervals, sqrt(-x*x-1) = sqrt(-[-1,1]-1) = sqrt([-2,0])
> = [0,0], so that the computed result must contain [0,0]. In general,
> one would get [0,0]_trv. But if the implementation can determine that
> for the point function sqrt(-x*x-1), the result is not defined for any
> input of [-1,1], then it could improve the decoration to emp.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 8, 2013 12:05:57 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Le vendredi 08 février 2013 à 03:14 +0100, Vincent Lefevre a écrit :
>
>>>>> As I understand it, decorations propagate from inputs to output and you
>>>>> can never get an output with a stronger decoration than an input.
>>>>
>>>> IIRC, in our discussions it was allowed to improve a decoration
>>>> if the condition associated with the property was satisfied.
>>>
>>> According to 8.8.6/25, this is not allowed. (And I am perfectly fine
>>> with it not being allowed. I think it is the only way of defining it
>>> correctly.)
>>
>> No, the implementation can use additional knowledge to provide a
>> different decoration. See the last example of 8.8.3, for instance.
>
> I don't see how the last example of 8.8.3 is relevant since it talks
> about ill, which is the lowest decoration on the propagation order scale
> of 8.8.6/26 and thus is not definitely not higher than the decoration of
> the inputs.
>
> Let me quote you the relevant parts of 8.8.6:
>
> "w_dw = phi(v_dv)" where v_dv is a box "v_dv_1, ..., v_dv_k"
> "w \subseteq Rge(phi | v)" (23)
> "p_dv_0(phi,v)" (24)
> "dw = min(dv_0,dv_1,...,dv_k)" (25)
> "where the minimum is taken with respect to the propagation order dac >
> def > trv > emp > ill" (26)
>
> As you can see from (25) above, the decoration dw of the output can
> never be improved so that it becomes higher than the decorations
> dv_0, ..., dv_k of the inputs.
>
>>> Just to clear any potential misunderstanding, I was not saying that
>>> empty is only allowed to have the trv decoration. What I was saying is
>>> that the emp decoration is redundant with the trv decoration: there is
>>> no situation that I can think of where empty_emp could not be encoded by
>>> empty_trv, and since nonempty_emp does not make sense, that does not
>>> leave any purposeful meaning for decoration emp.
>>
>> nonempty_emp makes sense for sqrt(-x*x-1) with x = [-1,1]. As an
>> expression on intervals, sqrt(-x*x-1) = sqrt(-[-1,1]-1) = sqrt([-2,0])
>> = [0,0], so that the computed result must contain [0,0]. In general,
>> one would get [0,0]_trv. But if the implementation can determine that
>> for the point function sqrt(-x*x-1), the result is not defined for any
>> input of [-1,1], then it could improve the decoration to emp.
>
> You are telling me that the implementation knows that the point function
> being computed is not defined, but it still bothers to return a nonempty
> interval for the interval function? That is just crazy.
>
> Either the implementation knows that the point function being computed
> is not defined and it returns empty_emp or empty_ill, or it does not and
> it returns [0,0]_trv or any superset. Any other behavior is meaningless.
>
> Best regards,
>
> Guillaume
Begin forwarded message:
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 8, 2013 3:25:35 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2013-02-08 07:05:57 +0100, Guillaume Melquiond wrote:
>> Le vendredi 08 février 2013 à 03:14 +0100, Vincent Lefevre a écrit :
>>>>>> As I understand it, decorations propagate from inputs to
>>>>>> output and you can never get an output with a stronger
>>>>>> decoration than an input.
>>>>>
>>>>> IIRC, in our discussions it was allowed to improve a decoration
>>>>> if the condition associated with the property was satisfied.
>>>>
>>>> According to 8.8.6/25, this is not allowed. (And I am perfectly fine
>>>> with it not being allowed. I think it is the only way of defining it
>>>> correctly.)
>>>
>>> No, the implementation can use additional knowledge to provide a
>>> different decoration. See the last example of 8.8.3, for instance.
>>
>> I don't see how the last example of 8.8.3 is relevant since it talks
>> about ill, which is the lowest decoration on the propagation order scale
>> of 8.8.6/26 and thus is not definitely not higher than the decoration of
>> the inputs.
>
> It is relevant because as I've already said above, it shows that
> the implementation can use additional knowledge to provide a
> decoration that would be different from the one described by
> 8.8.6.
>
>> Let me quote you the relevant parts of 8.8.6:
>>
>> "w_dw = phi(v_dv)" where v_dv is a box "v_dv_1, ..., v_dv_k"
>> "w \subseteq Rge(phi | v)" (23)
>> "p_dv_0(phi,v)" (24)
>> "dw = min(dv_0,dv_1,...,dv_k)" (25)
>> "where the minimum is taken with respect to the propagation order dac >
>> def > trv > emp > ill" (26)
>>
>> As you can see from (25) above, the decoration dw of the output can
>> never be improved so that it becomes higher than the decorations
>> dv_0, ..., dv_k of the inputs.
>
> And if you do this on the last example from 8.8.3 on an x that is not
> a NaI, you'll get the emp or trv decoration, not ill.
>
>>>> Just to clear any potential misunderstanding, I was not saying that
>>>> empty is only allowed to have the trv decoration. What I was saying is
>>>> that the emp decoration is redundant with the trv decoration: there is
>>>> no situation that I can think of where empty_emp could not be encoded by
>>>> empty_trv, and since nonempty_emp does not make sense, that does not
>>>> leave any purposeful meaning for decoration emp.
>>>
>>> nonempty_emp makes sense for sqrt(-x*x-1) with x = [-1,1]. As an
>>> expression on intervals, sqrt(-x*x-1) = sqrt(-[-1,1]-1) = sqrt([-2,0])
>>> = [0,0], so that the computed result must contain [0,0]. In general,
>>> one would get [0,0]_trv. But if the implementation can determine that
>>> for the point function sqrt(-x*x-1), the result is not defined for any
>>> input of [-1,1], then it could improve the decoration to emp.
>>
>> You are telling me that the implementation knows that the point function
>> being computed is not defined, but it still bothers to return a nonempty
>> interval for the interval function? That is just crazy.
>>
>> Either the implementation knows that the point function being computed
>> is not defined and it returns empty_emp or empty_ill, or it does not and
>> it returns [0,0]_trv or any superset. Any other behavior is meaningless.
>
> No, you didn't understand. The functions are used for different purpose
> by the user: approximation of point functions, range of a point function
> over an interval, range computations, etc. P1788 provides only one kind
> of functions for all these. There are flavors to differentiate some uses
> but even in the set-based flavor, there are different uses. And the
> implementation cannot know what is the intent of the user. For range
> computations (where variables represent no more than intervals), the
> implementation MUST return an interval that contains [0,0], as said
> above. So, returning Empty (with any decoration) would be wrong.
>
> --
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
> 100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
> Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
Begin forwarded message:
> From: Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
> Subject: Re: about emp (was: Motion 42: NO)
> Date: February 8, 2013 10:37:28 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Le vendredi 08 février 2013 à 10:25 +0100, Vincent Lefevre a écrit :
>> On 2013-02-08 07:05:57 +0100, Guillaume Melquiond wrote:
>
>>> As you can see from (25) above, the decoration dw of the output can
>>> never be improved so that it becomes higher than the decorations
>>> dv_0, ..., dv_k of the inputs.
>>
>> And if you do this on the last example from 8.8.3 on an x that is not
>> a NaI, you'll get the emp or trv decoration, not ill.
>
> Now I understand where the disagreement between us lies. You consider
> that ill is an improvement over emp and trv, while I consider it is not
> since it is the smallest element in the propagation scale. So the point
> of the discussion is moot.
>
>>>> nonempty_emp makes sense for sqrt(-x*x-1) with x = [-1,1]. As an
>>>> expression on intervals, sqrt(-x*x-1) = sqrt(-[-1,1]-1) = sqrt([-2,0])
>>>> = [0,0], so that the computed result must contain [0,0]. In general,
>>>> one would get [0,0]_trv. But if the implementation can determine that
>>>> for the point function sqrt(-x*x-1), the result is not defined for any
>>>> input of [-1,1], then it could improve the decoration to emp.
>>>
>>> You are telling me that the implementation knows that the point function
>>> being computed is not defined, but it still bothers to return a nonempty
>>> interval for the interval function? That is just crazy.
>>>
>>> Either the implementation knows that the point function being computed
>>> is not defined and it returns empty_emp or empty_ill, or it does not and
>>> it returns [0,0]_trv or any superset. Any other behavior is meaningless.
>>
>> No, you didn't understand. The functions are used for different purpose
>> by the user: approximation of point functions, range of a point function
>> over an interval, range computations, etc. P1788 provides only one kind
>> of functions for all these. There are flavors to differentiate some uses
>> but even in the set-based flavor, there are different uses. And the
>> implementation cannot know what is the intent of the user. For range
>> computations (where variables represent no more than intervals), the
>> implementation MUST return an interval that contains [0,0], as said
>> above. So, returning Empty (with any decoration) would be wrong.
>
> As you say, the implementation cannot know what is the intent of the
> user. So how does the implementation dare put the emp decoration on the
> result [0,0] after executing the following sequences of operations?
>
> x <- newDec([-1,1])
> a <- x * x
> b <- newDec([1,1])
> c <- - a
> d <- c - b
> e <- sqrt(d)
>
> So I stand by my point. If the implementation knows that the intent of
> the user is to compute the range of the function f(x) = sqrt(-x*x-1) on
> the domain [-1,1], then it might return empty_emp. If the implementation
> does not know what the intent of the user is, then it returns [0,0]_trv.
> But in no cases will it ever return [0,0]_emp. The motion does not allow
> it and it is fortunate.
>
> Best regards,
>
> Guillaume
Begin forwarded message:
> From: "Hanek, Bob" <bob.hanek@xxxxxxxxx>
> Subject: Re:Motion 42: NO
> Date: February 8, 2013 5:47:51 PM CST
> To: "stds-1788@xxxxxxxx" <stds-1788@xxxxxxxx>
>
> I vote NO on motion 42
Begin forwarded message:
> From: Alan Eliasen <eliasen@xxxxxxxxxxxxxx>
> Subject: Motion 42: NO
> Date: February 9, 2013 6:39:15 PM CST
> To: "stds-1788@xxxxxxxx" <stds-1788@xxxxxxxx>
>
> I vote NO on motion 42.
>
> While I believe that decorations denoting continuity are extremely
> important in many common uses of intervals (e.g. graphing equations,)
> and I strongly support their inclusion in the standard, I share the same
> misgivings as Guillaume Melquiond and Nate Hayes that the particular
> definitions of the decorations included in this motion are not quite
> correct and sometimes contradictory, such as the several cases that Nate
> Hayes outlined. The use of ILL, especially decorating the empty
> interval to indicate Not-an-Interval leads to contradictions.
>
> I think this motion is close to being useful, but the problems
> outlined by Hayes and Melquiond should be addressed before it is accepted.
>
> --
> Alan Eliasen
> eliasen@xxxxxxxxxxxxxx
> http://futureboy.us/
Begin forwarded message:
> From: Ulrich Kulisch <ulrich.kulisch@xxxxxxx>
> Subject: Motion 42
> Date: February 9, 2013 10:14:30 AM CST
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> I vote YES on motion 42.
>
> Comment:
> I admire John and all the others who have put together this motion. If it would be a resaerch paper I would be happy supporting it strongly. But there is only little experience available with the use of decorations. Siegfried Rump asked for at least one prototype implmentation and in gerneral I wonder whether we blow up the standard too much with the concepts of flavors and decorations. In the first round the standard should be simple and easily understandable to everybody. A basic goal of P1788 should be getting it accepted by the manufacturers. I agree that supporting the proof of correctness of a verification process would be important. But can't we leave this for a second round or for a part two of the standard..
>
> With best wishes
> Ulrich Kulisch
>
> --
> Karlsruher Institut für Technologie (KIT)
> Institut für Angewandte und Numerische Mathematik
> D-76128 Karlsruhe, Germany
> Prof. Ulrich Kulisch
>
> Telefon: +49 721 608-42680
> Fax: +49 721 608-46679
> E-Mail: ulrich.kulisch@xxxxxxx
> www.kit.edu
> www.math.kit.edu/ianm2/~kulisch/
>
> KIT - Universität des Landes Baden-Württemberg
> und nationales Großforschungszentrum in der
> Helmholtz-Gesellschaft
Begin forwarded message:
> From: Richard Fateman <fateman@xxxxxxxxxxxxxxxxx>
> Subject: Re: Motion 42, reference implementation, manufacturer acceptance, 17th byte
> Date: February 9, 2013 6:49:57 PM CST
> To: Ulrich Kulisch <ulrich.kulisch@xxxxxxx>, 'stds-1788' <stds-1788@xxxxxxxxxxxxxxxxx>
>
> On 2/9/2013 8:14 AM, Ulrich Kulisch wrote:
>> I vote YES on motion 42.
>>
>> Comment:
>> I admire John and all the others who have put together this motion. If it would be a resaerch paper I would be happy supporting it strongly. But there is only little experience available with the use of decorations. Siegfried Rump asked for at least one prototype implmentation and in gerneral I wonder whether we blow up the standard too much with the concepts of flavors and decorations. In the first round the standard should be simple and easily understandable to everybody. A basic goal of P1788 should be getting it accepted by the manufacturers. I agree that supporting the proof of correctness of a verification process would be important. But can't we leave this for a second round or for a part two of the standard..
>>
>> With best wishes
>> Ulrich Kulisch
>>
>
> I find your comment quite interesting.
> I too would like to see at least one implementation, and have
> started working on one.
>
> You refer to the "first round". Are you suggesting there would be
> a second draft of the current document that would add decorations etc?
>
> If you are referring to the next round being another standards
> committee some time in the future, my guess is that this would
> be unlikely to happen for decades if ever, at least under IEEE
> auspices. The revisions of IEEE-754 are separated by 23 years.
>
> Thus if one is uncertain about decorations etc., then this
> standards document should be clear about supporting the tools
> for implementing decorations, not necessarily requiring
> some controversial properties under discussion. If the distinctions
> that are controversial (mathematically) do not affect the
> implementation, it is perhaps unnecessary to agree!
>
> On the matter of having 1788 being accepted by manufacturers,
> I suspect that they just won't take any notice of it, one
> way or the other.
>
> (I don't know if there is a representative of any manufacturer
> on the committee right now, but if so, he or she should speak
> up).
>
> What is the evidence that I speak of? There is substantial
> evidence that the key elements of the IEEE 754 floating-point
> standard (key for a good 754-conforming implementation),
> are generally made inaccessible either by the
> hardware or software manufacturer (or both).
>
> Some manufacturers
> who claim to support the IEEE standard are supportive mainly of
> the FORMATS but not all operations (in particular, directed
> rounding, but also other parts). Just in case the hardware
> provides registers for modes and traps, it is likely that the
> software (operating systems and programming languages) will
> render these hardware features difficult to access or non-portable
> or ineffective. For example, Java specifies round-to-nearest.
> (at least last time I looked). Some operating systems
> supporting multiprocessing may not save and restore
> the bits needed to keep the floating-point
> flags consistent from before and after an interrupt.
>
> Now it is possible to find some implementations on some hardware
> and some software that does just what one wants (754- conforming).
>
> It just may not be the hardware and software that is most widely used.
>
> Or one may implement directed rounding entirely in software,
> assuming the hardware produces some consistent rounding. This may
> or may not be 754-conformant.
>
> Perhaps high speed and getting the tightest possible interval
> are secondary to getting agreement on the mathematics and
> notation. In that case it may not be necessary to
> get manufacturers' or programming language implementers'
> support at all, and an entirely conforming implementation
> of 1788 may depend on nothing of the IEEE 754 standard.
> It seems possible from my (undoubtedly incomplete) understanding
> of the draft standard. If standard language and loose conformance
> is acceptable, that's a lower hurdle for implementers who need
> not worry about intervals widening by a unit in the last place.
>
> .................
>
> At the risk of putting yet too much into one email, I'll mention
> one solution to the 17th byte problem that is widely used in Lisp.
> I do not know if it has been considered for decorated intervals,
> or if it is just silly in the expected context of intervals...
> but if not, here it is.
>
> The notion is of "typed pointers". If
> (and this is certainly not necessarily the case) we assume that
> all references to large objects are done by pointers, we have
> bits at our disposal. To be clear, what this means is that an
> array of intervals will be implemented as an array of pointers.
>
> Each pointer (say 32 bits), has the address of a 16-byte quantity (2 doubles)..
> Assume the 16 byte quantity is on a 16-byte boundary. The
> last 4 bits of the address are necessarily zero. But if you
> know they are supposed to be zero, why not use them to store a
> decoration? When you follow that pointer to an address of an
> interval you mask off those bits. If you want to find the
> decoration you mask off the 28 high-order bits.
>
> (Lisp uses this scheme to distinguish pointers to numbers, to
> lists, etc. This is important because Lisp is not strongly typed.
> It does, however, make it trivial to implement intervals whose
> endpoints are integers, exact rationals, single or double floats,
> "bigfloats", ... and to operate on them with other operands that
> are scalars of any numeric type.)
>
> Richard Fateman