In the company I work for, we receive an electronic invoice for our
mobile phone communications, and we are allowed to claim expenses for business calls.
I wanted to write a program that automates producing the expense claim. In order to do that,
the program needs to be able to decide which call was a business call (as opposed to
a private call). This decision depends on a number of factors, such as:
- Was it a call to a business contact?
- Was it a call I placed while being abroad for work?
- Was it a call I received while being abroad for work?
- Was the call made during normal office hours?
Clearly, the program needs to know the telephone numbers of my business contacts,
or doesn't it?
Sure, the program can maintain a database with known telephone numbers, and store
which of them are business contacts. But inevitably, invoices will contain
telephone numbers that do not appear in the database. So, does it need to ask
the user whether the unknown telephone number is a business contact or not?
Not necessarily. For example, if the call was received while I was abroad for work,
the expenses can be claimed, no matter who called me.
I would like to be able to write a program that has a line such
as the following (somewhat simplified), in which each of the variables are
boolean variables of some sort.
bool canClaim = receivedAbroad |
(calledAbroad | calledDuringOfficeHours) & businessContact;
The type IntentionalBool
presented in this article
allows exactly that, even though some of these variables may have a value "Unknown".
Background
The bool
type has two possible values:
true
and false
. It essentially
implements extensional propositional logic. In this logic, propositions
(statements) are either true or false, irrespective of the observer who
wonders whether they are true or false. In fact, the concept of an observer
doesn't even exist in extensional logic. A telephone number belongs to a
business contact or not.
In intentional logic, the subject plays an important role.
Propositions don’t have an intrinsic value, but rather a value
attributed to them by an observer. Different observers may attribute
different values. Also, it is possible that an observer can’t attribute
any of the traditional values of true or false, since information needed
to make that decision is lacking. In intentional logic, we describe the
belief of an observer or subject. It reasons about statements such as
"I believe this telephone number belongs to a business contact", but also
"I don't know whether this telephone number belongs to a business contact".
Why a three-valued DBBool is no good
Many people have proposed extensions to bool
.
For example, Microsoft describes a
struct called
DBBool in the C# Language Specification. Like most extensions,
this type has three values, True
, False
and Null
. It seems Null
is the value that means "I don't know", right?
In databases, it is common practice to use a special value,
null
, for unknown values. Indeed, say we have
an entity type called Person
, with properties
Name
and IsMale
. If we don’t
know the name of a person, we store the value null
.
This value is distinct from any other value, including from the empty name.
Likewise, if we don’t know a person’s sex, we store the value null
.
This value is distinct from all other values, being true
and
false
. If (and only if) the person is male, we store the value
true
. If (and only if) the person is female, we store the value
false
. If we don’t know, we store the value null
.
The DBBool
type allows for a direct mapping to and from
boolean database columns that are nullable. But there is a problem with this type:
it doesn't behave logically. For example, !p != p
is not always
true, as it would be with traditional logic. Because !Null == Null
,
even p | !p
will not always be true for variables of this type.
I want p | !p
to be true. Any phone number belongs to a
business contact or not. The fact that I don't know this particular phone number
shouldn't change that fact.
IntentionalBool
A type in which !p != p
for any value, all other
properties being equal, needs an even number of values.
True
and False
are clearly needed,
as well as Unknown
. For lack of a better name, the value
of !Unknown
is called NotUnknown
.
The type IntentionalBool
has these four values:
public struct IntentionalBool
{
public static IntentionalBool True
{ get { ... } }
public static IntentionalBool False
{ get { ... } }
public static IntentionalBool Unknown
{ get { ... } }
public static IntentionalBool NotUnknown
{ get { ... } }
...
}
Variable of this type has all the usual characteristics. For example,
the following are always true for all values of IntentionalBool
p
:
p != !p
p == !!p
p | !p
!(p & !p)
IntentionalBool
defines all the usual operators.
The behavior of these operators where only the values True
and False
are concerned, is identical to the behavior of the
operators for type bool
.
Feel free to skip the next section and jump straight to Using the code,
if you're not interested in the details of the operator definitions.
All operators are tested using NUnit 2.1. In fact, these unit tests serve as
formal definitions (test first!) for the operators.
The tests for the !
operator:
Assert.IsTrue(!IntentionalBool.True == IntentionalBool.False);
Assert.IsTrue(!IntentionalBool.Unknown == IntentionalBool.NotUnknown);
Assert.IsTrue(!IntentionalBool.NotUnknown == IntentionalBool.Unknown);
Assert.IsTrue(!IntentionalBool.False == IntentionalBool.True);
The tests for the &
operator:
Assert.IsTrue((IntentionalBool.True & IntentionalBool.True) ==
IntentionalBool.True);
Assert.IsTrue((IntentionalBool.True & IntentionalBool.Unknown) ==
IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.True & IntentionalBool.NotUnknown) ==
IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.True & IntentionalBool.False) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.Unknown & IntentionalBool.True) ==
IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.Unknown & IntentionalBool.Unknown) ==
IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.Unknown & IntentionalBool.NotUnknown) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.Unknown & IntentionalBool.False) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.NotUnknown & IntentionalBool.True) ==
IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.NotUnknown & IntentionalBool.Unknown) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.NotUnknown & IntentionalBool.NotUnknown) ==
IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.NotUnknown & IntentionalBool.False) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.False & IntentionalBool.True) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.False & IntentionalBool.Unknown) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.False & IntentionalBool.NotUnknown) ==
IntentionalBool.False);
Assert.IsTrue((IntentionalBool.False & IntentionalBool.False) ==
IntentionalBool.False);
The tests for the |
operator:
Assert.IsTrue((IntentionalBool.True | IntentionalBool.True)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.True | IntentionalBool.Unknown)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.True | IntentionalBool.NotUnknown)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.True | IntentionalBool.False)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.Unknown | IntentionalBool.True)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.Unknown | IntentionalBool.Unknown)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.Unknown | IntentionalBool.NotUnknown)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.Unknown | IntentionalBool.False)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.NotUnknown | IntentionalBool.True)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.NotUnknown | IntentionalBool.Unknown)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.NotUnknown | IntentionalBool.NotUnknown)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.NotUnknown | IntentionalBool.False)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.False | IntentionalBool.True)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.False | IntentionalBool.Unknown)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.False | IntentionalBool.NotUnknown)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.False | IntentionalBool.False)
== IntentionalBool.False);
The tests for the ^
operator:
Assert.IsTrue((IntentionalBool.True ^ IntentionalBool.True)
== IntentionalBool.False);
Assert.IsTrue((IntentionalBool.True ^ IntentionalBool.Unknown)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.True ^ IntentionalBool.NotUnknown)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.True ^ IntentionalBool.False)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.Unknown ^ IntentionalBool.True)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.Unknown ^ IntentionalBool.Unknown)
== IntentionalBool.False);
Assert.IsTrue((IntentionalBool.Unknown ^ IntentionalBool.NotUnknown)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.Unknown ^ IntentionalBool.False)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.NotUnknown ^ IntentionalBool.True)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.NotUnknown ^ IntentionalBool.Unknown)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.NotUnknown ^ IntentionalBool.NotUnknown)
== IntentionalBool.False);
Assert.IsTrue((IntentionalBool.NotUnknown ^ IntentionalBool.False)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.False ^ IntentionalBool.True)
== IntentionalBool.True);
Assert.IsTrue((IntentionalBool.False ^ IntentionalBool.Unknown)
== IntentionalBool.Unknown);
Assert.IsTrue((IntentionalBool.False ^ IntentionalBool.NotUnknown)
== IntentionalBool.NotUnknown);
Assert.IsTrue((IntentionalBool.False ^ IntentionalBool.False)
== IntentionalBool.False);
IntentionalBool
also defines the "definitely true"
and "definitely false" operators, such that the short circuit
&&
and ||
operators can be used.
We will not list the full tests of their definitions here (they are as good
as equal to the &
and |
tests),
but the following is tested for any combination of
IntentionalBool
p
and q
values as well:
Assert.IsTrue( (p && q) == (p & q) );
Assert.IsTrue( (p || q) == (p | q) );
The &&
and ||
operators
can be used to optimize code, if the right operand of the expression is a complex formula.
You don't need them to protect your code against exceptions, because
IntentionalBool
will never throw exceptions.
Because of the definition of these operators, you can use
IntentionalBool
variables in if
statements as well:
bool success = false;
if (IntentionalBool.True)
{
success = true;
}
Assert.IsTrue(success);
if (IntentionalBool.False)
{
Assert.Fail();
}
if (IntentionalBool.Unknown)
{
Assert.Fail();
}
if (IntentionalBool.NotUnknown)
{
Assert.Fail();
}
In typical formulas, IntentionalBool
operands
will be mixed with traditional bool
operands.
For example, in the statement in the introduction,
receivedAbroad
and calledAbroad
might be simple bool
variables. To make this work,
an implicit conversion from bool
to
IntentionalBool
is defined.
Assert.IsTrue(IntentionalBool.True == true);
Assert.IsTrue(IntentionalBool.False == false);
The reverse conversion is possible as well, using an explicit conversion operator,
but this operator does lose information:
Assert.IsTrue((bool) IntentionalBool.True);
Assert.IsFalse((bool) IntentionalBool.Unknown);
Assert.IsFalse((bool) IntentionalBool.NotUnknown);
Assert.IsFalse((bool) IntentionalBool.False);
To complete the implementation, the ==
and
!=
operators are defined, all object
methods are overridden, and the type is serializable. For additional convenience,
a Parse(string)
method is defined,
and an IsKnown
property, which returns true
if (and only if) the IntentionalBool
is True
or False
.
[Serializable]
public struct IntentionalBool
{
...
public static bool operator == (IntentionalBool p, IntentionalBool q)
{ ... }
public static bool operator != (IntentionalBool p, IntentionalBool q)
{ ... }
public override bool Equals(object obj)
{ ... }
public override int GetHashCode()
{ ... }
public override string ToString()
{ ... }
public static IntentionalBool Parse(string value)
{ ... }
public bool IsKnown
{ ... }
...
}
Implementing IntentionalBool
IntentionalBool
has four possible values,
so all we need is two bits to store it. You could imagine using two
bool
variables to store it, and the first question
that then comes to mind is: what do these booleans mean? I like to think of
these hypothetical booleans as specifying a range, such that a value
p
is known to be between a
and
b
, where p
is an
IntentionalBool
, and a
and
b
are the boolean values:
True
is a value between true
and true
False
is a value between false
and false
Unknown
is a value between false
and true
NotUnknown
is a value between true
and false
Such an implementation would allow us to define all operators in terms of
the same operators on the two booleans.
But in reality, we don't need two bool
variables,
all we need is two bits, stored in a byte. The enum
construct of C# allows us to define symbolic names for the four variables:
[Flags]
private enum State : byte
{ False, Unknown, NotUnknown, True };
Using this definition, all operators can be defined in terms of the
corresponding bitwise operators on type State
.
This leads to a very elegant and efficient implementation. In fact,
all IntentionalBool
methods are implemented as a single statement.
All these methods can be easily inlined by the JIT compiler. As a result,
the performance of IntentionalBool
is very good. In fact,
it is almost as good as the performance of the bool
type.
A few examples:
public struct IntentionalBool
{
[Flags]
private enum State : byte
{ False, Unknown, NotUnknown, True };
private State state;
...
public static bool operator ==
(IntentionalBool p, IntentionalBool q)
{
return p.state == q.state;
}
...
public override bool Equals(object obj)
{
return obj is IntentionalBool &&
((IntentionalBool) obj).state == state;
}
public override string ToString()
{
return state.ToString();
}
...
public static IntentionalBool operator &
(IntentionalBool p, IntentionalBool q)
{
return new IntentionalBool(p.state & q.state);
}
public static IntentionalBool operator |
(IntentionalBool p, IntentionalBool q)
{
return new IntentionalBool(p.state | q.state);
}
public static IntentionalBool operator ^
(IntentionalBool p, IntentionalBool q)
{
return new IntentionalBool(p.state ^ q.state);
}
public static IntentionalBool operator !
(IntentionalBool p)
{
return new IntentionalBool(p.state ^ State.True);
}
...
public static implicit operator IntentionalBool (bool b)
{
return b ? True : False;
}
public static explicit operator bool (IntentionalBool p)
{
return p.state == State.True;
}
}
IntentionalBool
can be used in much the same
way you would normally use bool
.
Let's go back to the example from the introduction:
IntentionalBool businessContact = ...;
IntentionalBool calledDuringOfficeHours = ...;
bool receivedAbroad = ...;
bool calledAbroad = ...;
IntentionalBool canClaim = receivedAbroad |
(calledAbroad | calledDuringOfficeHours) & businessContact;
if (!canClaim.IsKnown)
{
...
}
...
if (canClaim)
{
...
}
Of course, all variables could be functions or properties as well, and the
||
and &&
operators could be
used to avoid evaluating the functions:
Call call = ...;
IntentionalBool canClaim = call.IsReceivedAbroad ||
(call.IsCalledAbroad || OfficeHours.IsDuring(call.Time)) &&
BusinessContacts.IsBusinessContact(call.Number);
if (!canClaim.IsKnown)
{
...
}
...
if (canClaim)
{
...
}
Compare this to the same logic, using only bool
variables.
Try to rewrite the above for yourself. Not only you will find out that you need more
than four variables (or functions), but also that the logic will become much more
complex and far less readable. You might end up nesting if
statements and so on. Also, if your application needs high performance,
bear in mind that IntentionalBool
is quite efficient,
because it essentially performs two boolean operations in a single bitwise
operation on two bits. Also, it effectively stores two booleans in a single byte. The
bool
type cannot do that.
As you can see, you can use IntentionalBool
pretty much
everywhere where you can use a bool
, including in
if
statements and the like. But that in itself won’t
make your programs smarter. Consider using it if you are working on a program
that could benefit from dealing with the unknown. It might be a business application,
or it might be a game of some sort, that needs to keep track of what it knows about
the other player(s). Maybe this can be used for optimization purposes.
Indeed, the value of any boolean expression is basically unknown until it is evaluated.
Programs that do lazy evaluation of complex boolean functions might be easier to
write with this type.
Points of interest
IntentionalBool
is a typical example of a .NET
ValueType
. As per the standard
Design Guidelines, it is immutable. It also follows all other
guidelines, where applicable.
Other extensions to traditional logic have been proposed. Fuzzy logic is a well known one.
In fuzzy logic, statements are not necessarily true of false, they can be "somewhat true"
or "more true than" other statements. For an excellent introduction to the theory of
fuzzy logic, see the
Tutorial On Fuzzy Logic by Jan Jantzen, or have a look at the
articles by pseudonym67 here on CP.
IntentionalBool
is not fuzzy. All propositions still
have an intrinsic value of true or false, it's just that we may not know it.
Not knowing the intrinsic value (the "extensional" value) does not imply that
the value is fuzzy though. Likewise, the assumption that a variable has an intrinsic value,
even though it might be fuzzy, does not imply that it is known. In other words,
typical fuzzy logic is extensional.
It is possible to implement an intentional fuzzy type as well. Even though
calledDuringOfficeHours
might be considered a fuzzy variable,
I didn't need fuzzy logic for my purposes, so I leave the implementation of an
intentional fuzzy type as "an exercise for the reader" ;-).
There is a lot of (mostly philosophical) literature on intentional logic.
I you're interested, do a search on Google or Amazon, and you'll find more than
enough to read. If you do, you'll find out that this implementation only touches
the surface, but that applies to bool
and extensional logic as well.
Neither implements predicate logic or inference engines.
Again, I didn't need these to solve my specific problem.
I hope IntentionalBool
can help you solve yours as well.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.