Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Revised Motion 26 decoration scheme



> Date: Tue, 19 Jul 2011 01:18:42 +0200
> From: Vincent Lefevre <vincent@xxxxxxxxxx>
> To: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Revised Motion 26 decoration scheme
> 
> On 2011-07-18 10:09:42 -0700, Dan Zuras Intervals wrote:
> > 	John,
> > 
> > 	While I don't think we should have bare objects of any kind,
> 
> I haven't looked at the motion yet, but IMHO, while bare intervals are
> mathematically well-defined, bare decorations probably don't make much
> sense without a good idea of applications behind. So, I would agree
> with you at least concerning bare decorations, unless one can show
> that they are really useful in important applications / algorithms
> (Nate's examples are probably useful here...).
> 
> In any case I think that one other principle is that bare decorations
> should never come from true (decorated or not) intervals, except via
> functions that explicitly return bare decorations.
> 
> > 	I agree with Nate on this point.  But for a different reason.
> > 
> > 	If we should promote bare decorations to anything other than
> > 	empty, we risk violating inclusion isotonicity &, therefore,
> > 	violating FTDIA.
> 
> I tend to agree with you. But the choice should also be made according
> to what I've said above.
> 
> -- 
> Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>


	Actually, Vincent, I believe the promotion of bare objects
	to decorated (let's call them true) intervals involves
	risks more serious than that.  I just haven't made my case
	yet.

	Let's see if I can.

	Let me contrive examples starting with the case we are all
	thinking about & then going into increasingly more serious
	cases.

	Let's say I wish to find the global minimum of some function.
	I don't know anything about the internals of that function
	but if I did it would look like this:

		f(x) = 10*(x^2 - x) + floor(x)

	I could create an interval function, ff(xx), from this point
	function, use any of the divide & conquer methods that Nate
	& others know so well & quickly discover that the global
	minimum is the same as the continuous function 10*x*(x-1),
	namely at x = 1/2 & taking on the value -5/2.

	But let's say I know something more about this function.
	Let's say I know that it is discontinuous in places.  Let's
	say that I also know that the global minimum is not at or
	near a discontinuity.

	And not knowing where those discontinuities are nor just
	how many of them there are, I might be tempted to use that
	knowledge to write another search method.  Something like:

		if (isSafe(ff(xx))) {do a continuous search for a
			minimum within xx & compare the results to
			other minima found so far}
		else	/* isDef because of the discontinuity */
			{split xx into xx1 & xx2 & try each in turn}

	(Note that the isSafe() predicate is implicitly extracting
	the bare decoration & using it to control the course of the
	search.  It is not yet being used in any real dangerous
	fashion but even this has its risks.)

	It is a valid program.  It is not something that Nate would
	be tempted to write but it has the flavor of such things.
	And it WILL find the minimum in spite of the fact that my
	additional knowledge has tempted me to use a far more
	inefficient search method.

	Now suppose I use the knowledge of the global minimum being
	isolated from any discontinuity in another way.  Suppose I
	write a helper function thus:

		gg(xx) = (isSafe(ff(xx))) ? ff(xx)
		: makeEmptyIntervalFromBareDecoration(decoration(ff(xx)));

	And search for minima in gg().  The global minimum is still
	in the same place & has the same value but gg() violates
	inclusion isotonicity in that:

		gg([1/3,2/3]) = {[-5/2,-2/9],saf} NOT \subset
		gg([-1/3,4/3]) = {[empty],def}

	My motivation for creating gg() was sound but my reasoning
	about how the search works was not.  And, given that I might
	not KNOW how the search works, it is a mistake that is easy
	to make.

	Note that returning [entire] doesn't help either.  For if I
	write an hh() such that:

		hh(xx) = (isSafe(ff(xx))) ? ff(xx)
		: makeEntireIntervalFromBareDecoration(decoration(ff(xx)));

	I cure the inclusion isotonicity problem but now I have a
	function that can find a minimum for small intervals
	surrounding 1/2 but has global minima of -infinity for any
	interval that includes an integer in its interior.

	I screwed up again.  But in a different way.

	Indeed, both gg() & hh() can be thought of as poor programming
	brought about by a lack of understanding about how intervals
	work.

	And we could adopt the attitude that we, as a standards body,
	need not concern ourselves with stupid or invalid programs.
	That would be a perfectly defensible position to take.

	But by providing the ability to use bare decorations to
	make inferences that get promoted back to true intervals,
	we tempt the user to do things that are risky.

	In tort law this is know as 'an attractive nuisance'.
	And the creators of that nuisance are also held culpable
	in the mischief that results.

	I realize it is a weak argument.  The arguments I have
	against bare intervals finding their way back into the
	world of true intervals are likely even weaker.

	But I believe we should not be handing these loaded weapons
	to our users.

	This is not to say that I believe Nate should be denied his
	use of bare intervals.  Nate is presumed to be an expert.
	And good things can be done in expert hands.  The same
	could be said of optimizing compilers.  They can know
	without a doubt when it is safe to compile to bare
	intervals & when true intervals are needed.

	But if we discuss them in the text of the standard as if
	they were something we encourage the user to use, I think
	we do them a disservice.

	That's it.  I've shot my bolt.  You guys know the dangers
	better than I.

	Remember: You are the marksmen.  Part of the expertise
	of your profession is knowing when to leave the safety on
	& knowing when it is safe to hand a loaded weapon to a
	rookie.

	And, of course, standing behind that weapon at all times.

	Enjoy,

				Dan