Guid guide, part two

So how is it that a GUID can be guaranteed to be unique without some sort of central authority that ensures uniqueness, a la the ISBN system?

Well, first off, notice that the number of possible GUIDs is vastly larger than the number of possible ISBNs. Because the last of the thirteen digits is a checksum, there are only 1012 possible ISBNs. That is about a hundred unique ISBNs for every person on earth. That’s almost exactly 240, so you could represent an ISBN by a 40 bit number (again, ignoring the checksum). There are 2128 possible GUIDs; that’s about 40 billion billion billion unique GUIDs for every person on earth. This alone gives us the intuition that it ought to be pretty easy to ensure that two of them never collide; there are a lot of GUIDs to choose from!

Continue reading

Guid guide, part one

What is a GUID? The acronym stands for “globally unique identifier”; GUIDs are also called UUIDs, which stands for “universally unique identifier”.[1. It is unclear to me why we need two nigh-identical names for the same thing, but there you have it.] A GUID is essentially a 128 bit integer, and when written in its human-readable form, is written in hexadecimal in the pattern {xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx}.

The purpose of a GUID is, as the name implies, to uniquely identify something, so that we can refer to that thing by its identifier and have confidence that everyone can agree upon what thing we are referring to. Think about this problem as it applies to, say, books. It is cumbersome to refer to a book by quoting it in its entirety every time you mention it. Instead, we give every book an identifier in the form of its title. The problem with using a title as an identifier is that there may be many different books with the same title. I have three different books all entitled “The C# Programming Language” on my desk right now; if I want to refer to one of them in particular, I’d typically have to give the edition number. But there is nothing (apart from their good sense) stopping some entirely different publisher from also publishing a book called “The C# Programming Language, fourth edition” that differs from the others.

Continue reading

A brief digression

Before we continue our exploration of truthiness in C#, a brief digression. I mentioned last time the “knights and knaves” puzzles of logician Raymond Smullyan. Though I do enjoy those puzzles, my favourite of his puzzles are his chess puzzles, and my second favourite are his combinatory logic puzzles. Here’s an example of the latter, adapted from the puzzle on page 134 of Satan, Cantor and Infinity.

Continue reading

Null is not false, part two

In Raymond Smullyan‘s delightful books about the Island of Knights and Knaves — where, you’ll recall, knights make only true statements and knaves make only false statements — the knights and knaves are of course clever literary devices to explore problems in deductive logic.

(Aside: Smullyan’s book of combinatory logic puzzles, To Mock a Mockingbird is equally delightful and I recommend it for anyone who wants a playful introduction to the subject.)

Smullyan, to my recollection, never explores what happens when knights and knaves make statements which are disingenuous half-truths, authorial license in pursuit of a larger truth, or other forms of truthiness. A nullable Boolean in C# gives us, if not quite the notion of truthiness, at least the notion that true and false are not the only possible values of a predicate: there is also “null”, whatever that means.

What does that mean? A null Boolean can mean “there is a truth state, but I just don’t know what it is”: for example, if you queried a database on December 1st to ask “were the sales figures for November higher than they were in October?” the answer is either true or false, but the database might not know the answer because not all the figures are in yet. The right answer in that case would be to say “null”, meaning “there is an answer but I do not know what it is.”

Or, a null Boolean can mean “the question has no answer at all, not even true or false”. True or false: the present king of France is bald. The number of currently existing kings of France — zero — is equal to the number of currently existing bald kings of France, but it seems off-putting to say that a statement is “vacuously true” in this manner when we could more sensibly deny the validity of the question. There are certainly analogous situations in computer programming where we want to express the notion that the query is so malformed as to not have a truth value at all, and “null” seems like a sensible value in those cases.

Because null can mean “I don’t know”, almost every “lifted to nullable” operator in C# results in null if any operand is null. The sum of 123 and null is null because of course the answer to the question “what is the sum of 123 and something I don’t know” is “I don’t know!” The notable exceptions to this rule are equality, which says that two null values are equal, and the logical “and” and “or” operators, which have some very interesting behaviour. When you say x & y for nullable Booleans, the rule is not “if either is null then the result is null“. Rather, the rule is “if either is false then the result is false, otherwise, if either is null then the result is null, otherwise, the result is true“.

Similarly for x | y — the rule is “if either is true then the result is true, otherwise if either is null then the result is null, otherwise the result is false“. These rules obey our intuition about what “and” and “or” mean logically provided that “null” means “I don’t know”. That is the truth value of “(something true) or (something I don’t know)” is clearly true regardless of whether the thing you don’t know is true or false. But if “null” means “the question has no answer at all” then the truth value of “(something true) or (something that makes no sense)” probably should be “something that makes no sense”.

Things get weirder though when you start to consider the “short circuiting” operators, && and ||. As you probably know, the && and || operators on Booleans are just like the & and | operators, except that the && operator does not even bother to evaluate the right hand side if the left hand side is false, and the || operator does not evaluate the right hand side if the left hand side is true. After we’ve evaluated the left hand side of either operator, we might have enough information to know the final answer. We can therefore (1) save the expense of computing the other side, and (2) allow the evaluation of the right hand side to depend on a precondition established by the truth or falsity of the left hand side. The most common example of (2) is of course if (s == null || s.Length == 0) because the right hand side would have crashed and burned if evaluated when the left hand side is true.

The && and || operators are not “lifted to nullable” because doing so is problematic. The whole point of the short-circuiting operator is to avoid evaluating the right hand side, but we cannot do so and still match the behaviour of the unlifted version! Suppose we have x && y for two nullable Boolean expressions. Let’s break down all the cases:

  • x is false: We do not evaluate y, and the result is false.
  • x is true: We do evaluate y, and the result is the value of y
  • x is null: Now what do we do? We have two choices:
    • We evaluate y, violating the nice property that y is only evaluated if x is true. The result is false if y is false, null otherwise.
    • We do not evaluate y. The result must be either false or null.
      • If the result is false even though y would have evaluated to null, then we have resulted in false incorrectly.
      • If the result is null even though y would have evaluated to false, then we have resulted in null incorrectly.

In short, either we sometimes evaluate y when we shouldn’t, or we sometimes return a value that does not match the value that x & y would have produced. The way out of this dilemma is to cut the feature entirely.

I said last time that I’d talk about the role of operator true and operator false in C#, but I think I shall leave that to the next episode in this series. Next time on FAIC we’ll digress briefly and then conclude this series after that.