On trits & tetrits...

[Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>]

	Folks,

	The other day John mentioned thinking about an interval
	relation as a mapping of xx R yy onto a subset of the set
	{true, false}.

	Then today, he gave us version 2.2 of the draft & I paused to
	look at the definition of trits in the section on decorations.

	And I had an idea.

	I have to tell you that I have always been bothered by the
	value 'possibly true'.  It is not so much that I can't handle
	a 3-valued logic.  It is that everyone speaks differently
	when they talk about things that return that value.  What
	bothers me is that I think we are all using our own definition
	of 'possibly' & thinking different things when we discuss it.

	The idea that struck me is that we might be able to make that
	notion concrete by considering trits as subsets of {true, false}.
	(This may mean that they will actually be tetrits but let's pass
	on that until later.)

	First, consider that a decoration is some property P of some
	function f such that P is either true or false when evaluated
	at some point x.  So, for example, if P = inDomain, f = sqrt,
	we have that inDomain(sqrt,-1) = false & inDomain(sqrt,1) =
	true.

	Now, to make it concrete for intervals, let us define the
	evaluation of P on an interval xx as that subset of {true,
	false} we get when we evaluate P(f,x) for all x in xx.  That
	is:

		decorationP(f,xx) = {P(f,x) for all x in xx}.

	So, for example, we have:

		inDomain(sqrt,[0,1]) = {true}
		inDomain(sqrt,[-1,1]) = {true, false}
		inDomain(sqrt,[-2,-1]) = {false}.

	That is, the interval [0,1] is entirely contained within the
	domain of sqrt, [-1,1] has points both in & out of the domain,
	& [-2,-1] is entirely outside the domain.

	(Looks useful for divide & conquer, does it not? :-)

	Under this interpretation, a decoration may be considered true
	if the evaluation of that property on that function is always
	true for that interval (i.e. evaluates to {true}).  It is false
	if it is always false (evaluates to {false}).  And it is the
	third value (possibly true, trueFalse, whatever) if it is
	sometimes true & sometimes false (evaluates to {true, false}).

	This would be easy to implement.  We could store the value of
	a decoration as two bits, one for the false value & the other
	for the true value.  Say, for inDomain, we might have:

		inDomainFalse = There exists x in xx such that
			inDomain(f,x) is false &
		inDomainTrue = There exists x in xx such that
			inDomain(f,x) is true.

	The careful reader will notice that there is a 4th possibility.
	We might have inDomain(sqrt,[empty]) = {} (the empty set).  This
	could happen during the evaluation of the empty set for just
	about any property for just about any function.  It could also
	serve as the default (or initial) value for constructors,
	depending on the property.

	Does this sound good to anyone?

	While it simplifies the thinking about decorations for me, I
	must confess that it loses the 'stickyness' property that some
	people may be counting on for tracking decorations as if they
	were exceptions.  This may be important.  If it is we may need
	another bit to track it for each property.

	Anyway, I just thought I'd try to start a discussion on the
	subject.  I have no specific motion at the moment.  Perhaps
	one will come out of the discussion.

	There you go folks, enjoy...


				   Dan