Empty interval representations & Motion 13...

[Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>]

	Folks,

	I have been thinking about something for some time now
	& Ulrich's recent revision of Motion 13 has brought it
	up again.

	It is the issue of the representation of the empty
	interval.

	Many of you out there seem to presume that the proper
	representation for the empty interval is [NaN,NaN].
	And this may turn out to be the best thing for us.

	But let me point out that we have scrupulously avoided
	NaNs in any form at all so far.

	And I believe this is a good thing.

	NaNs cause trouble where ever they appear.  They even
	cause trouble when they MIGHT appear.  At the very least,
	the diligent function writer must take into account the
	possibility that it might happen somewhere in his code.

	One simple example from floating-point:  Take the code
	fragment that says

		if a < b then r = sqrt(b^2 - a^2)
		else r = sqrt(a^2 = b^2)

	But if a NaN is possible then one must do something like

		if a < b then r = sqrt(b^2 - a^2)
		else if a >= b then r = sqrt(a^2 = b^2)
		else <do something NOW before the rocket fails>

	There are many examples & they are all as non-intuitive
	as this one.

	So, if we can avoid the use of NaNs in intervals I think
	it would simplify our lives considerably.  I can tell
	you from personal experience that they have complicated
	MY life for the past 30 years.  And intervals, both
	standard & non-standard would remain ordered as we believe
	they should be.

	At the very least, if we permit no NaNs in the
	representation of any valid interval we will know that
	the appearance of a NaN is somebody else's fault not our's.
	(And we can go to some pains to eliminate them by importing
	only numeric values to valid intervals.)

	But if we do not use NaNs to represent the empty interval,
	how DO we represent it?

	Well, I can think of two general approaches.

	(1) We can decorate an interval with a decoration that
	means (or implies) 'this is an empty interval'.  I have
	already gone into that in some detail as a side effect
	of the 'domain' decoration so I'll not belabor that
	approach now.

	(2) We can pick a numeric value that would otherwise
	never appear in a valid interval (either standard or
	non-standard).

	I believe the representation [+oo,-oo] fits that
	description.  It is unique & pretty easy to test for in
	any of a number of ways.  (Nate, check me on this.  This
	is not used in non-standard intervals, correct?)

	But if we use empty = [+oo,-oo], how does that come out
	for Ulrich's comparisons?

		a    equals    b <==> a1  = b1 && a2  = b2
		a    subset    b <==> b1 <= a1 && a2 <= b2
		a  lessEqual   b <==> a1 <= b1 && a2 <= b2
		a precedeTouch b <==> a2 <= b1
		a   interior   b <==> b1 <  a1 && a2 <  b2
		a  strictLess  b <==> a1 <  b1 && a2 <  b2
		a   preceed    b <==> a2 <  b1

	Let's let any = [b1,b2] be some otherwise non-empty
	interval.  I believe we have that

		empty    equals    any = False
		empty    subset    any = True
		empty  lessEqual   any = False (1)
		empty precedeTouch any = True (2)
		empty   interior   any = True
		empty  strictLess  any = False
		empty   preceed    any = True (3)

	as well as

		any    equals    empty = False
		any    subset    empty = False
		any  lessEqual   empty = False (1)
		any precedeTouch empty = True (2)
		any   interior   empty = False
		any  strictLess  empty = False
		any   preceed    empty = True (3)

	and, for completeness sake

		empty    equals    empty = True
		empty    subset    empty = True
		empty  lessEqual   empty = True (4)
		empty precedeTouch empty = True (2)
		empty   interior   empty = False
		empty  strictLess  empty = False
		empty   preceed    empty = True (4)


	Which are all correct with the following qualifications

	(1) (a lessEqual b) tests for mere overlap in one direction
	or the other.  Therefore, it is acceptable to the programmer
	that this be true if SOME a is less than or equal to SOME b.
	This has the flavor of an existential quantification & if
	this test is written in this way, empty tests correct.

	(2) Similarly, (a precedeTouch b) test to make sure that NO
	element of a exceeds ANY element of b.  If it is written
	with universal quantification (essentially not (any a >
	any b)) then empty tests correct.

	(3) This one is True except for (empty preceed [-oo,x]) or
	([x,+oo] preceed empty) in which case it tests False.  This
	may have to be special cased.

	(4) My interpretation is that these two are False with the
	quantification I suggest.  So they may have to be special
	cased as well.


	So, all in all, that's not too bad.

	What do you think?


				   Dan