Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
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
3  
@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
2  
@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. –  MichaelT May 23 '13 at 2:15
show 3 more comments

3 Answers

up vote 2 down vote accepted

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.)

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.