Re: [boost] 3-state boolean type

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-08-02 09:37:16

On Friday 02 August 2002 07:03 am, Richard Peters wrote:
> In the functional language that we studied, a character named "bottom" (
> _|_ ) represents undefinedness. It is often the result of a non-terminating
> function. A tri-state bool as three states: true, false, bottom.
> Defining a function negation is simple:
> not true = false, not false = true, not bottom = bottom.
> Defining a function or is more difficult:
> {true, false} or {true, false} yields the expected values, bottom or bottom
> = bottom but: true or bottom = ?, false or bottom = ?, bottom or true = ?,
> bottom or false = ?

That's the danger with using the term "bottom", because it means different 
things to different people. Andrew Bromage just gave the opposite definition 
of bottom. To paraphrase:

Your definition of "bottom" is that of a nonexistent value, which can also be  
thought of as 'too much (conflicting) information' This is like an undefined 
value in mathematics, or the 'result' you get if you assume that a boolean 
condition p is both true and false at the same time. The return value from a 
nonterminating function also fits this definition, because there is no actual 
value returned from that function.

Andrew's definition of "bottom" is that of an unknown value, which can also be 
thought of as 'too little information'. It means that I know there is a 
value, but I can't say anything about the actual value that's there. 

When dealing with lattices, one of these definitions is chosen for bottom and 
the other becomes top, but I don't think the choice of name is consistent :(. 
I'd be afraid to pick one definition, but would rather use terms like 
'undefined' and 'unknown' that aren't as nebulous.

> There are three possibilities for filling these in:
> The strict interpretation:
>     bottom or {true, false} = bottom, {true, false} or bottom = bottom
>     the strict interpretation means, if one of the parameters is bottom,
> then the result is bottom
> The strongest monotic extension of the two valued operator:
>     bottom or true = true, bottom or false = bottom, true or bottom = true,
> false or bottom = bottom
>     this means something like if you're sure of the answer from examining
> one parameter, you don't need to know the other one.
> The sequential/asymmetric interpretiation:
>     true or y = true, bottom or y = bottom, false or y = y
>     this means that the first parameter is examined. In functional
> languages, when the first parameter doesn't terminate, the operator doesn't
> terminate. When the first parameter terminates, and you don't know the
> answer yet, you examine the second parameter. x or y is different from y or
> x (true or bottom = true, bottom or true = bottom)

Egads :) This is way out of tribool's domain because tribool is based on the 
other definition of "bottom". For the 'too little information' interpretation 
of "bottom", the second interpretation is, I believe, the only one that 
really makes sense (because termination is not an issue)

> Fuzzy logic is something completely than this. Bottom is not something like
> "trueish", "falseish" or "something in between". A fuzzy bool is totally
> different and has totally different purposes than a tri-state bool. If I
> would use a fuzzy bool,  I think I'd rather take a floating type in the
> range [0, 1] with maybe operators that are a bit undeterministic. (Today,
> it says "It's a bit blue", tomorrow, "nah I think it's more greenish")

Lattice theory unifies these, and I suspect that's why Andrew brought it up 
:). The lattice just ends up being infinitely high when we use a real number 
between 0 and 1, but otherwise the ideas are no different.

 > And for the name of the third state, I'm in favor of "bottom", it's a
> well-established name, and short.

I think I'm in favor of "unknown" (and "undefined", when someone needs it). 
They're both reasonably short and I think they can apply without confusion to 
most of the extensions that have been proposed.

> Douglas Gregor wrote:
> > The type, tribool, can be either true, false, or indeterminate. It
> > follows the normal rules for 3-valued logic, and supports all boolean
>
> hmm... the "normal" rules... I'm wondering what rules you used :) Is it
> difficult to add the three interpretations above?

It wouldn't be difficult to create a new type similar to tribool for which the 
states are "true", "false", and "undefined" instead of "true", "false", and 
"unknown". Then it's simple a matter of a policy template parameter to 
determine which of the three indeterpretations to use.

I'll write out the (pseudo?) truth tables for the tribool documentation so 
it's clear which interpretation I've used.

        Doug