# Conditional construct for a kleenean data type

I was thinking of an hypothetical programming language with a `kleenean` data type which would implement Kleene's three-valued logic. To sum up, it's an extension of the boolean data type with the three constants `true`, `false` and `unknown` where `unknown` means that the value is either `true` or `false`, but we don't know which.

The truth tables for a kleenean type are well-known and the logic is quite easy to understand. However, I was wondering how one would design a conditional construct to take in account this `unknown` value.

A basic `if-then-else` conditional construct is almost always as follows:

``````if (boolean condition) then
condition is true, do something
else
condition is false, do some other thing
end
``````

However, I have troubles seeing what a kleenean `if` construct would look like. How could we interpret the `unknown` constant? Technically speaking, it could satisfy the `true` condition as well as the `false` condition since it is one of these two. However, we can't have it match any of those since it could be the other, it is not really `true` nor `false`.

Is there a well-known way to implement such a construct?

EDIT: To specify a little bit, I would prefere something different than the way `boost::tribool` works, or from a simple `switch` as if was an enum. Answers about quantum superposition and semantics are welcome.

-
Would `if TRUE ... elseif FALSE... else //UNKNOWN ...` work for you? – FrustratedWithFormsDesigner May 22 '13 at 17:54
I'm inclined that the if does not get executed but rather is appended to a chain of things to do when the unknown becomes known, this is basically how IO is done in haskell, you don't act upon the value in the IO context, but you create a chain of things to do and the runtime will eventually execute those things inside of the context when necessary. Your unknown type could just collect all of these things to do together, and then apply them only when they can be applied (when it becomes known, which I presume it will?) – Jimmy Hoffa May 22 '13 at 18:41
@FrustratedWithFormsDesigner Well, that would work, but I still wonder whether there would be something to emphasize more the concept of kleenean. – Morwenn May 22 '13 at 19:13
@Morwenn another thing you should really look at is a common modern paradigm in perl based on quantum superpositions, this also sounds very similar to what you want to do. It basically makes the code flow branch out in all directions across all superpositions and then pares branches to collapse as the code flows forward. Sounds very similar and is really cool: search.cpan.org/~dconway/Quantum-Superpositions-1.03/lib/… – Jimmy Hoffa May 22 '13 at 19:19
@Morwenn With perl 6, this was recognized as a important structure and processing capability and it became part of the core language known as junctions. – user40980 May 23 '13 at 2:15

However, I have troubles seeing what a kleenean `if` construct would look like.

It looks exactly like an ordinary `if`. However, the semantics are slightly different. Instead of saying “if the condition is true, then this otherwise that”, it actually goes something like “if the condition is known to be true, then this otherwise that” (or perhaps “proven” instead of “known”, depending on which modality you prefer to use your kleenean logic to represent). This then means that you may want to have an operator for testing “is unknown/unproven” so that you can check for the third state, though that is not strictly necessary:

``````let boolvar = boolean condition
if (boolvar) then
# The true case...
elseif (not boolvar) then
# The false case...
else
# The unproven case...
fi
``````

(Assuming that `not unknown` is `unknown`, of course.)

-
The halting problem is trivial to solve if you allow this sort of ternary response; you have to work a bit harder to construct a paradoxical program. You still can though. – Donal Fellows May 22 '13 at 22:02
So you are actually proposing the `boost::tribool` approach. Since I am talking about kleenean logic, of course `not unknown = unknown`, so that would work. But in the end, this is only bringing the problem back to a boolean problem. Well, it's easier to think boolean anyway... – Morwenn May 23 '13 at 6:36
The kleenean approach is very similar to what I know as intuitionistic logic. Possibly the same. The effect is that you work with only things you can prove to be true or false, and that greatly improves the practical tractability on arbitrary statements. But for all that, Gödel still says that you can construct paradoxes; if you can't make a paradox, the programming system simply isn't interesting in the first place. – Donal Fellows Jul 23 '13 at 12:25
It has been some time - like quite some time, but I failed to find anything else that seemed both more interesting and reasonable. Well, you have my vote :) – Morwenn Nov 22 '13 at 18:54

From what you said, `unknown` represents represents `true` or `false` "at the same time". You shouldn't take it as another value, but as something special or exceptional.

If `unknown` is passed into `if` it becomes non deterministic which of the two code paths it should take. I think it is best to assume that passing `unknown` into an `if` should result in error.

But you should have way to detect if value is properly defined. Something like

``````if defined (boolean condition) then
condition is defined true or false, do something
else
condition is unknown, do some other thing
end
``````

and there should be negated version of this, because you cannot use normal logic to invert the code paths to remove one of the branches for code clarity.

-
Hum, I don't really like having `unknown` as an error. Sadly, the `if (boolean condition)` only boils down to `if (kleenean condition != unknown)`. I wonder whether there is something a little bit more original :/ – Morwenn May 22 '13 at 21:30
@Morwenn It is unlikely possible to implement something "more original". That's because any program is text. And as such - it is one-dimensional. So, any statement (e.g. `else`) divides the text onto two parts: before and after. There is no way to divide it onto three, like you want. – lorus Jun 11 '13 at 14:10
@lorus Not sure. The comments about quantum superposition expose something quite original :) – Morwenn Jun 11 '13 at 16:41

I've implemented this approach in the language I develop (then I removed this feature and switched to the boolean logic, as considered three-state logic not really useful).

A three-state logical could be converted to boolean transparently with the following rule:

The boolean value of the logical is `true` only when the logical value is `true`.

The `unknown` and `false` logical values correspond to the `false` boolean.

To be able to work with three-state logicals, a set of unary operators could be used:

• `++` (is) - convert a logical operand to boolean value. Just in a more verbose way than implicit conversion.
• `--` (not) - result is `true` only when operand is `false`.
• `+-` (known) - result is `true` only when operand is either `true` or `false`.
• `-+` (unknown) - result is `true` only when operand is `unknown`.

This way conditionals could be implemented to work with boolean conditions, as they use to. A logical could be used as boolean condition either transparently or explicitly. Different combinations of logical operators could be used to achieve the same goal, whatever suits best:

``````if (condition) {
// condition is true
} else if (--condition) {
// condition is false
} else {
// condition is unknown
}

if (-+condition) {
// condition is unknown
} else if (condition) {
// condition is true
} else {
// condition is false
}
``````
-