Fabulous Adventures In Coding

GUID guide, part three

Eric Lippert — Mon, 07 May 2012 15:18:00 GMT

Let's recap: a GUID is a 128 bit integer that is used as a globally unique identifier. GUIDs are not a security system; they do not guarantee uniqueness in a world where hostile parties are deliberately attempting to cause collisions; rather, they provide a cheap and easy way for mutually benign parties to generate identifiers without collisions. One mechanism for ensuring global uniqueness is to generate the GUID so that its bits describe a unique position in spacetime: a machine with a specific network card at a specific time. The downside of this mechanism is that code artifacts with GUIDs embedded in them contain easily-decoded information about the machine used to generate the GUID. This naturally raises a privacy concern.

To address this concern, there is a second common method for generating GUIDs, and that is to choose the bits at random. Such GUIDs have a 4 as the first hex digit of the third section.

First off, what bits are we talking about when we say "the bits"? We already know that in a "random" GUID the first hex digit of the third section is always 4. Something I did not mention in the last episode was that there is additional version information stored in the GUID in the bits in the fourth section as well; you'll note that a GUID almost always has 8, 9, a or b as the first hex digit of the fourth section. So in total we have six bits reserved for version information, leaving 122 bits that can be chosen at random.

Second, why should we suppose that choosing a number at random produces uniqueness? Flipping a coin is random, but it certain does not produce a unique result! What we rely on here is probabilistic uniqueness. Flipping a single coin does not produce a unique result, but flipping the same coin 122 times in a row almost certainly produces a sequence of heads and tails that has never been seen before and will never be seen again.

Let's talk a bit about those probabilities. Suppose you have a particular randomly-generated GUID in hand. What is the probability that a specific time that you randomly generate another GUID will produce a collision with your particular GUID? If the bits are chosen randomly and uniformly, clearly the probability of collision is one in 2¹²². Now, what is the probability that over n generations of GUIDs, you produce a collision with your particular GUID? Those are independent rare events, so the probabilities add (*); the probability of a collision is n in 2¹²². This 2¹²²is an astonishingly large number.

There are on the order 2³⁰ personal computers in the world (and of course lots of hand-held devices or non-PC computing devices that have more or less the same levels of computing power, but lets ignore those). Let's assume that we put all those PCs in the world to the task of generating GUIDs; if each one can generate, say, 2²⁰ GUIDs per second then after only about 2⁷² seconds -- one hundred and fifty trillion years -- you'll have a very high chance of generating a collision with your specific GUID. And the odds of collision get pretty good after only thirty trillion years.

But that's looking for a collision with a specific GUID. Clearly the chances are a lot better of generating a collision somewhere else along the way. Recall that a couple of years ago I analyzed how often you get any collision when generating random 32 bit numbers; it turns out that the probability of getting any collision gets extremely high when you get to around 2¹⁶ numbers generated. This generalizes; as a rule of thumb, the probability of getting a collision when generating a random n bit number gets large when you've generated around 2^n/2 numbers. So if we put those billion PCs to work generating 122-bits-of-randomness GUIDs, the probability that two of them somewhere in there would collide gets really high after about 2⁶¹ GUIDs are generated. Since we're assuming that about 2³⁰ machines are doing 2²⁰ GUIDs per second, we'd expect a collision after about 2¹¹ seconds, which is about an hour.

So clearly this system is not utterly foolproof; if we really, really wanted to, we could with high probability generate a GUID collision in only an hour, provided that we got every PC on the planet to dedicate an hour of time to doing so.

But of course we are not going to do that. The number of GUIDs generated per second worldwide is not anywhere even close to 2⁵⁰! I would be surprised if it were more than 2²⁰GUIDs generated per second, worldwide, and therefore we could expect to wait about 2⁴¹ seconds, for there to be a reasonable chance of collision, which is about seventy thousand years. And if we are looking for a collision with a specific GUID, then again, it will take about a billion times longer than our initial estimate if we assume that a relatively small number of GUIDs are being generated worldwide per second.

So, in short: you should expect that any particular random GUID will have a collision some time in the next thirty billion trillion years, and that there should be a collision between any two GUIDs some time in the next seventy thousand years.

Those are pretty good odds.

Now, this is assuming that the GUIDs are chosen by a perfectly uniform random process. They are not. GUIDs are in practice generated by a high-quality pseudo-random number generator, not by a crypto-strength random number generator. Here are some questions that I do not know the answers to:

What source of entropy is used to seed that pseudo-random number generator?
How many bits of entropy are used in the seed?
If you have two virtual machines running on the same physical machine, do they share any of their entropy?
Are any of those entropy bits from sources that would identify the machine (such as the MAC address) or the person who created the GUID?
Given perfect knowledge of the GUID generation algorithm and a specific GUID, would it be possible to deduce facts about the entropy bits that were used as the seed?
Given two GUIDs, is it possible to deduce the probability that they were both generated from a pseudo-random number generator seeded with the same entropy? (And therefore highly likely to be from the same machine.)

I do not know the answers to any of these questions, and therefore it is wise for me to assume that the answers to the bottom four questions is "yes". Clearly it is far, far more difficult for someone to work out where and when a version-four GUID was create than a version-one GUID, which has that information directly in the GUID itself. But I do not know that it is impossible.

There are yet other techniques for generating GUIDs. If there is a 2 in the first hex digit of the third section then it is a version 1 GUID with some of the timestamp bits have slightly different meanings. If there is a 3 or 5 then the bits are created by running a cryptographic hash function over a unique string; the uniqueness of the string is then derived from the fact that it is typically a URL. But rather than go into the details of those more exotic GUIDs, I think I will leave off here.

Summing up:

GUIDs are guaranteed to be unique but not guaranteed to be random. Do not use them as random numbers.
GUIDs that are random numbers are not cryptographic strength random numbers.
GUIDs are only unique when everyone cooperates; if someone wants to re-use a previously-generated GUID and thereby artificially create a collision, you cannot stop them. GUIDs are not a security mechanism.
GUIDs have an internal structure; at least six of the bits are reserved and have special meanings.
GUIDs are allowed to be generated sequentially, and in practice often are.
GUIDs are only unique when taken as a whole.
GUIDs can be generated using a variety of algorithms.
GUIDs that are generated randomly are statistically highly unlikely to collide in the foreseeable future.
GUIDs could reveal information about the time and place they were created, either directly in the case of version one GUIDs, or via cryptanalysis in the case of version four GUIDs.
GUIDs might be generated by some entirely different algorithm in the future.

(*) As the comments point out, this is an approximation that only holds if the probability is small and n is relatively small compared to the total number of possible outcomes.

GUID guide, part two

Eric Lippert — Mon, 30 Apr 2012 14:11:00 GMT

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 10¹² possible ISBNs. That is about a hundred unique ISBNs for every person on earth. That's almost exactly 2⁴⁰, so you could represent an ISBN by a 40 bit number (again, ignoring the checksum). There are 2¹²⁸ 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!

There are a number of possible strategies for making a unique GUID, and in fact information about the strategy used is encoded in the first four bits of the third "group"; almost every GUID you see will be of the form {xxxxxxxx-xxxx-1xxx-xxxx-xxxxxxxxxxxx} or {xxxxxxxx-xxxx-4xxx-xxxx-xxxxxxxxxxxx}.

If there is a one in that place then the algorithm used to guarantee uniqueness is essentially a variation on the ISBN strategy. The GUID is guaranteed to be unique "in space" by choosing some of the bits as the MAC address of the network card in the machine. (The tricky problem of ensuring that no two network cards in the world have the same MAC address is solved somehow by someone else; how that problem is solved, we don't particularly care. The cost of solving that problem is passed on to you, the consumer, in the purchase cost of the network card.)

(UPDATE: Larry Osterman pointed out to me that of course, this MAC address solution is not foolproof. First, you could deliberately or accidentally set your MAC address to an already-used value. Second, a hardware manufacturer might forget to set the address at all and have it be all zeros. Third, two virtual machines might be using the same physical network card and those virtual machines could be generating GUIDs at exactly the same time fast enough to cause collisions.)

We know that we can rely on this as a source of uniqueness in space. Most of the remaining bits are a high-resolution timestamp. Therefore every generated GUID is unique in both space and time, and is therefore globally unique.

This system does in practice have a few weak spots. The most obvious one is that it does not work well if the machine does not have a network card! Version-one GUIDs generated on machines without network cards are not guaranteed to be unique. The less obvious one is that there is a slim chance that two GUIDs could be generated "at the same time". Perhaps two GUID generators were running on two different processors in the same machine at the same time. Or perhaps a GUID was generated, the clock in the machine was deliberately "turned back", and the same GUID was then generated again, just by bad luck. There are a few "extra" bits in a GUID that are used to mitigate these timing problems, so in practice they don't arise.

There are a number of interesting consequences of this algorithm. The first is that such GUIDs are almost completely non-random. Many people seem to be of the mistaken belief that GUIDs are a source of randomness, when in fact they are only guaranteed to be a source of uniqueness.

The second is that it is possible for GUIDs generated on a particular machine with this algorithm to be monotone increasing. This is actually a very nice property for GUIDs to have; GUIDs are often used as primary keys in databases, and it can be much cheaper to insert a large number of rows into an indexed-by-primary-key database table if the rows are already sorted and you're always inserting after every previous entry. This again demonstrates that using a sequence of GUIDs as a sequence of random 128 bit numbers is a terrible idea; random numbers are typically not monotone increasing!

The third interesting consequence is that code or documents that contains a GUID generated with this first algorithm contain information that uniquely identifies the machine that was used to create the GUID. Just as a skilled reader can determine interesting facts about a book from its ISBN, so too can a skilled reader determine when and where a GUID was generated if it has a one as its thirteenth hex digit. This fact was used when tracking down and prosecuting the author of the famous Melissa virus. (We'll discuss the implications of this in more detail in an upcoming episode.)

The fourth interesting consequence is that no proper subsequence of the bits of a GUID have the global uniqueness property, as Raymond pointed out back in 2008. And indeed, we have no reason to expect that a smaller set of bits would have the same properties as a larger set of bits! You don't expect to be able to saw one aircraft in half and end up with two things that both fly.

Next time we'll talk about GUIDs that have a four in their thirteenth hex digit; they use a completely different technique for ensuring uniqueness.

GUID Guide, part one

Eric Lippert — Tue, 24 Apr 2012 13:32:00 GMT

What is a GUID? The acronym stands for "globally unique identifier"; GUIDs are also called UUIDs, which stands for "universally unique identifier". (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.

Publishers have solved this problem by creating a globally unique identifier for each book called the International Standard Book Number, or ISBN. This is the 13-decimal-digit bar coded number you see on pretty much every book(*). How do publishers manage to get a unique number for each of the millions of books published? They divide and conquer; the digits of an ISBN each have a different meaning. Each country has been assigned a certain range of ISBN numbers that they can allocate; governments then further allocate subsets of their numbers to publishers. Publishers then decide for themselves how to assign the remaining digits to each book. The ISBNs for my three editions of the C# spec are 978-0-321-15491-6, 978-0-321-56299-9 and 978-0-321-74176-9. You'll notice that the first seven digits are exactly the same for each; they identify that this is a publishing industry code (978), that the book was published in a primarily English-speaking region (0), by Addison-Wesley (321). The next five digits are Addison-Wesley's choice, and the final digit is a checksum. If I wish to uniquely identify the fourth edition of the C# specification I need not state the ambiguous title at all; I can simply refer you to book number 978-0-321-74176-9, and everyone in the world can determine precisely which book I'm talking about.

An important and easily overlooked characteristic of the ISBN uniqueness system is that it only works if everyone who uses it is non-hostile. If a rogue publisher decides to deliberately publish books with the ISBN numbers of existing books so as to create confusion then the usefulness of the identifier is compromised because it no longer uniquely identifies a book. ISBN numbers are not a security system, and neither are GUIDs; ISBN numbers and GUIDs prevent accidental collisions. Similarly, traffic lights only prevent accidental collisions if everyone agrees to follow the rules of traffic lights; if anyone decides to go when the light is red then collisions might no longer be avoided, and if someone is attempting to deliberately cause a collision then traffic lights cannot stop them.

The ISBN system has the nice property that you can "decode" an ISBN and learn something about the book just from its number. But it has the enormous down side that it is extraordinarily expensive to administer. There has to be international agreement on the general form of the identifier and on what the industry and language codes mean. In any given country there must be some organization (either a government body or private companies contracted by the government) to assign numbers to publishers. It can cost hundreds of dollars to obtain a unique ISBN.

GUIDs do not have this cost problem; GUIDs are free and there is no requirement that any governing body get involved to ensure their uniqueness. A GUID is a number that you can generate yourself and be guaranteed that no one else in the world will generate that same number. That seems a bit magical. How does that work? Over the next couple of episodes we'll take a look at how that magical property is achieved.

(*) The attentive reader will note that there are usually two bar codes on a book in the United States. The first one is the ISBN; the second bar code is the number 5 followed by a four digit number that is the publisher's suggested price of the book in American pennies.

null is not false, part three

Eric Lippert — Thu, 19 Apr 2012 14:03:00 GMT

Returning now to the subject at hand: we would like to allow user-defined "overloads" of the & and | operators in C#, and if we are going to have & and | be overloadable, it seems desirable to have && and || be overloadable too.

But now we have a big design problem. We typically overload operators by making a method:

class C
{
string s;
public C(string s) { this.s = s; }
public override string ToString() { return s; }
public static C operator +(C x, C y) { return new C(x.s + "+" + y.s); }
}
...
Console.WriteLine(new C("123") + new C("456")); // "123+456"

But method arguments are eagerly evaluated in C#. We can't very well say:

public static C operator &&(C x, C y) { ... whatever ... }

because when you cay

C c = GetFirstC() && GetSecondC();

that is going to be rewritten as something like:

C c = C.op_ShortCircuitAnd(GetFirstC(), GetSecondC());

which obviously evaluates both operands regardless of whether the left hand is "true" or "false".

Of course in modern-day C# we have a type which represents "perform this calculation that produces a result in the future, on demand"; that type is Func<T>. We could implement this as:

public static C operator &&(C x, Func<C> fy) { ... whatever ... }

and now the rewrite becomes

C c = C.op_ShortCircuitAnd(GetFirstC(), ()=>GetSecondC());

The method can then invoke the delegate only if it decides that it needs to evaluate the right hand side.

That would totally work, though it has a couple of problems. First, it is potentially expensive; even if we never use it, we go to all the trouble of allocating a delegate. Second, C# 1.0 did not have either lambdas or generic delegate types, so the whole thing would have been a non-starter back then.

What we settled on instead was to say that really there are two things going on here. First we must decide whether to evaluate the right hand side or not. If we do not evaluate the right hand side then the result can be the left hand side. If we do evaluate the right hand side then we combine the two evaluated sides using the non-short-circuiting operator.

It is that first operation -- decide whether or not to evaluate the right hand side -- that requires operator true and operator false. These are the "is this operand one that requires the right hand side to be implemented or not?" operators.

But now we face another problem. I said last time that we have a problem with the short-circuiting && and || operators when considering values other than true or false: namely, does x && y mean "evaluate y if and only if x is true", or "evaluate y if and only if x is not false"? Obviously for straight-up Boolean x and y, those are the same, but for nullable Booleans they are not. And for our user-defined operator they are not the same either. After all, if you already had an unambiguous way to convert your type to true or false, you would simply implement an implicit conversion to bool and use the built-in && and || operators.

The C# 1.0 design team decided that the rule is "evaluate y if and only if x is not false". We implement that rule by having an "operator false" that returns true if x is to be treated as false, and false if it is not to be treated as false. That's a bit confusing, I know. Maybe an example will help:

class C
{
string s;
public C(string s) { this.s = s; }
public override string ToString() { return s; }
public static C operator &(C x, C y) { return new C(x.s + "&" + y.s); }
public static C operator |(C x, C y) { return new C(x.s + "|" + y.s); }
public static bool operator true(C x) { return x.s == "true"; }
public static bool operator false(C x) { return x.s == "false"; }
}
...
C ctrue = new C("true");
C cfalse = new C("false");
C cfrob = new C("frob");

Console.WriteLine(ctrue && cfrob); // true&frob
Console.WriteLine(cfalse && cfrob); // false
Console.WriteLine(cfrob && cfrob); // frob&frob

That is to say, x && y here is implemented as:

C temp = x;
C result = C.op_false(temp) ? temp : temp & y;

And similarly, x || y uses the "operator true" in the analogous manner.

A little known fact is that if you can use && and || with a user-defined type, then you can also use them in control flows that take a bool, like if and while. This means that you can in fact say:

if (ctrue && cfrob) ...

because that becomes the moral equivalent of:

C temp = ctrue;
C result = C.op_false(temp) ? temp : temp & cfrb;
bool b = C.op_true(result);
if (b) ...

Pretty neat, eh?

A brief digression

Eric Lippert — Tue, 17 Apr 2012 14:04:00 GMT

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.

We have an alphabet consisting of the letters S, E, R, M, K and V. You can make strings out of these letters; a "string" is defined as a ordered sequence of letters drawn from the given alphabet; the sequence can be of any finite length. Some strings are said to "name" other strings.

I'll use "x" and "y" as variables that stand in for strings, and furthermore we can assume that x and y never stand for empty strings. (And that moreover, in the fourth rule, y is a string with at least two characters.) The rules of naming are:

SxE names x
if x names y then Rx names yy
if x names y then Mx names SyE
if x names y then Kx names the string formed by removing the leftmost character from y
if x names y then Vx names the string formed by reversing the letters of y

So, for example, SRME names RM, by the first rule. Because SRME names RM, we know that RSRME names RMRM by the second rule. And thus KRSRME names MRM.

There has been a small amount of confusion in the comments; note that I am not saying that some strings are "legal" and some are "illegal" in any way; rather, I am saying that some strings just happen to "name" other strings. A string that does not name any other string is still a perfectly "good" string; no string is more or less valid than any other. "RM" for example does not name any string.

The challenge -- which probably will not be too hard for computer programmers, but will be a bit tricky for non-programmers who haven't read the fifteen pages of easier puzzles leading up to this one -- is to find a string that names itself. Smullyan's solution is 18 letters long and he challenges the reader to find a shorter one. I have found a 12 letter solution. I conjecture that 12 letters is the smallest such string, but I have not proven it. I'll put both Smullyan's solution and my solution in the comments. Good luck!

UPDATE: There is a nine-letter solution, and it is minimal. Nice work!

null is not false, part two

Eric Lippert — Thu, 12 Apr 2012 16:29:11 GMT

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. 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". And 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.

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

null is not false

Eric Lippert — Mon, 26 Mar 2012 16:24:00 GMT

The way you typically represent a "missing" or "invalid" value in C# is to use the "null" value of the type. Every reference type has a "null" value; that is, the reference that does not actually refer to anything. And every "normal" value type has a corresponding "nullable" value type which has a null value.

The way these concepts are implemented is completely different. A reference is typically implemented behind the scenes as a 32 or 64 bit number. As we've discussed previously in this space, that number should logically be treated as an "opaque" handle that only the garbage collector knows about, but in practice that number is the offset into the virtual memory space of the process that the referred-to object lives at, inside the managed heap. The number zero is reserved as the representation of null because the operating system reserves the first few pages of virtual memory as invalid, always. There is no chance that by some accident, the zero address is going to be a valid address in the heap.

By contrast, a nullable value type is simply an instance of the value type plus a Boolean that indicates whether the value is to be treated as a value, or as null. It's just a syntactic sugar for passing around a flag. This is because value types need not have any "special" value that has no other meaning; a byte has 256 possible values and every one of them is valid, so a nullable byte has to have some additional storage.

Some languages allow null values of value types or reference types, or both, to be implicitly treated as Booleans. In C, you can say:

int* x = whatever();
if (x) ...

and that is treated as if you'd said "if (x != null)". And similarly for nullable value types; in some languages a null value type is implicitly treated as "false".

The designers of C# considered those features and rejected them. First, because treating references or nullable value types as Booleans is a confusing idiom and a potential rich source of bugs. And second, because semantically it seems presumptuous to automatically translate null -- which should mean "this value is missing" or "this value is unknown" -- to "this value is logically false".

In particular, we want to treat nullable bools as having three states: true, false and null, and not as having three states: true, false and different-kind-of-false. Treating null nullable Booleans as false leads to a number of oddities. Suppose we did, and suppose x is a nullable bool that is equal to null:

if (x)
Foo();
if (!x)
Bar();

Neither Foo nor Bar is executed because "not null" is of course also null. (The answer to "what is the opposite of this unknown value?" is "an unknown value".) Does it not seem strange that x and !x are both treated as false? Similarly, if (x | !x) would also be treated as false, which also seems bizarre.

The solution to the problem of these oddities is to avoid the problem in the first place, and not make nulls behave as though they were false.

Next time we'll look at a different aspect of truth-determining: just what is up with those "true" and "false" user-defined operators?

Why not automatically infer constraints?

Eric Lippert — Fri, 09 Mar 2012 19:09:00 GMT

UPDATE: Whoops! I accidentally set a draft of this article to automatically publish on a day that I was away on vacation. The fact that it was (1) not purple and (2) introduced the topic and then stopped in mid-sentence were both clues that this was an unfinished edit. Sorry about that; I thought I had set it to *not* publish on Monday. I am not so good with these computer thingies apparently.

I spent the weekend not thinking about computers by lying beside a pool in Palm Springs, which I can definitively report is an awesome way to spend a rainy weekend in Seattle. I can also definitely report that Peter Frampton has lost almost all his hair and absolutely none of his talent; the man is amazing. If you like 1970's hard rock guitar solos, you've got just a couple more weeks to hear him perform all of Frampton Comes Alive.

Right, let's actually finish off that article then:

--------------

Suppose you have a generic base type with a constraint:

class Bravo<T> where T : IComparable<T> { ... }

If you make a generic derived class in the obvious way:

class Delta : Bravo { ... }

then the C# compiler gives you an error:

error CS0314: The type 'U' cannot be used as type parameter 'T' in the generic type or method 'Bravo<T>'. There is no boxing conversion or type parameter conversion from 'U' to 'System.IComparable'.

Which seems reasonable; every construction of Bravo<T> is required to meet the constraints on T and we have no evidence whatsoever that the type supplied for U will meet those constraints.

But that's only one way of looking at the problem; another way of looking at it is that we do have evidence that the person who declared U expected that U meets the constraints of T, since they used it as T. Given that evidence one might reasonably then expect the compiler to simply silently place the same constraint upon U. U would then meet the constraint on T; any error then would not be on the declaration of Delta's base class, but rather, upon any code which constructs Delta such that Bravo<T>'s constraints are violated.

I'm often asked why the compiler does not implement this feature or that feature, and of course the answer is always the same: because no one implemented it. Features start off as unimplemented and only become implemented when people spend effort implementing them: no effort, no feature. This is an unsatisfying answer of course, because usually the person asking the question has made the assumption that the feature is so obviously good that we need to have had a reason to not implement it. I assure you that no, we actually don't need a reason to not implement any feature no matter how obviously good. But that said, it might be interesting to consider what sort of pros and cons we'd consider if asked to implement the "silently put inferred constraints on class type parameters" feature.

As C# has evolved, clearly more and more features involve the compiler silently making inferences on your behalf: method group conversions, method type inference, implicitly typed locals, implicitly typed arrays, implicitly typed lambdas, and so on, all involve a great deal of inference work by the compiler. You would think we could do the same thing for generic type constraints. However, the problem is not as easy as it looks. The easy case mentioned above is, well, easy. Things quickly get complicated:

class Echo<W, X> where W : IComparable<W> where X : IComparable<X> { }
class Foxtrot<Y> : Echo<Y, Y> { }

The supposition here is now that Y must be implicitly constrained to be both IComparable<Y> and... IComparable<Y>. OK, that seems reasonable. But what if we then change that to:

class Echo<W, X> where W : Foo where X : Bar { }
class Foxtrot<Y> : Echo<Y, Y> { }

Suppose Foo and Bar are class types with no relationship between them. Now there is no possible type argument for Y that meets the inferred constraint. Is the compiler now required to tell you that fact? How smart does it have to be about that?

Let's make this a bit more complicated. I'll just make something up off the top of my head:

class Golf<T> where T : Hotel<T> {}
class Hotel : Golf<Indigo> where U : IJuliet<Hotel> {}
class Indigo<V> : Hotel<Golf<V>> where V : IKilo<V> {}
interface IJuliet<W> {}
interface IKilo<X>

What are the constraints that we have to infer? Well for T to be a Hotel<T>, T has got to be an IJuliet<Hotel<T>>, so we should add that constraint. But in order to be an IJuliet<Hotel<T>>, T has got to meet the constraints on Hotel<T>... oh, wait, we already added that constraint. Looks like our constraint adder is going to have to be resistant to cycles. But wait, do we have *all* the constraints on Hotel<T>? So far we have only evaluated the *stated* constraints. U in Hotel not only has to be an IJuliet<Hotel>, it also has to be a legal Indigo, which means it needs to be an IKilo, which means we should add a constraint to T that T be IKilo<T>.

And so on. I'm not going to go through a full analysis of this thing. The point is, the analysis is complicated, the analysis may go into infinite loops very easily, and it is not at all clear when you know that you've worked out the full set of type constraints when types refer to each other in arbitrary ways. (And we haven't even considered what happens if the interfaces are covariant or contravariant!) I don't like adding inference algorithms to the compiler that require cycle detection and do potentially unbounded amounts of work. The possibility of getting the algorithm wrong is very real. Even if we get the algorithm right, the odds that the implementation will be buggy is very high. If we add this feature then the compiler needs to be able to get the right answer all the time, and to give a sensible error message that helps the user if there is no right answer. Both problems seem very difficult.

Moreover, why are we stopping with base types? It seems like if we're going to do the feature of inferring constraints, then we ought to consume information about the entire class, not just the base types:

class Mike<T> where T : November {}
class Oscar<V> { Mike<V> bv; }

Should we deduce that V must be November because Oscar<V> has a field of type Mike<V>? I don't see why the base types are any more special than the field types.

What if Oscar<V> had used Mike<V> as a return type of a method? Or a parameter type? Or as the type of a local variable? Where does it stop?

Basically, the feature is too much pain for too little gain. When you construct a generic, you are the one required to supply a proof to the compiler that you have satisfied the constraints. C# is not a "figure out what the developer meant to say and say it for them" language; it's a "tell the developer when they have supplied too little information" language.

Why are local variables definitely assigned in unreachable statements?

Eric Lippert — Mon, 05 Mar 2012 22:05:18 GMT

You're probably all familiar with the feature of C# which disallows reading from a local variable before it has been "definitely assigned":

void M()
{
int x;
if (Q())
x = 123;
if (R())
Console.WriteLine(x); // illegal!
}

This is illegal because there is a path through the code which, if taken, results in the local variable being read from before it has been assigned; in this case, if Q() returns false and R() returns true.

The reason why we want to make this illegal is not, as many people believe, because the local variable is going to be initialized to garbage and we want to protect you from garbage. We do in fact automatically initialize locals to their default values. (Though the C and C++ programming languages do not, and will cheerfully allow you to read garbage from an uninitialized local.) Rather, it is because the existence of such a code path is probably a bug, and we want to throw you in the pit of quality; you should have to work hard to write that bug.

The way in which the compiler determines if there is any path through the code which causes x to be read before it is written is quite interesting, but that's a subject for another day. The question I want to consider today is: why are local variables considered to be definitely assigned inside unreachable statements?

void M()
{
int x;
if (Q())
x = 123;
if (false)
Console.WriteLine(x); // legal!
}

First off, obviously the way I've described the feature immediately gives the intuition that this ought to be legal. Clearly there is no path through the code which results in the local variable being read before it is assigned. In fact, there is no path through the code that results in the local variable being read, period!

On the other hand: that code looks wrong. We do not allow syntax errors, or overload resolution errors, or convertibility errors, or any other kind of error, in an unreachable statement, so why should we allow definite assignment errors?

It's a subtle point, I admit. Here's the thing. You have to ask yourself "why is there unreachable code in the method in the first place?" Either that unreachable code is deliberate, or it is an error.

If it is an error, then something is deeply messed up here. The programmer did not intend the written control flow in the first place. It seems premature to guess at what the definite assignment errors are in the unreachable code, since the control flow that would be used to determine definite assignment state is wrong. We are going to give a warning about the unreachable code; the user can then notice the warning and fix the control flow. Once it is fixed, then we can consider whether there are definite assignment problems with the fixed control flow.

Now, why on earth would someone deliberately make unreachable code? It does in fact happen; actually it happens quite frequently when dealing with libraries made by another team that are not quite done yet:

// If we can resrov the frob into a glob, do that and then blorg the result.
// Even if the frob is not a glob, we know it is definitely a resrovable blob,
// so resrov it as a blob and then blorg the result. Finally, fribble
// the blorgable result, regardless of whether it was a glob or a blob.
void BlorgFrob(Frob frob)
{
IBlorgable blorgable;
// TODO: Glob.TryResrov has not been ported to C# yet.
if (false /* Glob.TryResrov(out blorgable, frob) */)
{
    BlorgGlob(blorgable);
}
else
{
    blorgable = Blob.Resrov(frob)
    BlorgBlob(blorgable);
}
blorgable.Fribble(frob);
}

Should BlorgGlob(blorgable) be an error? It seems plausible that it should not be an error; after all, it's never going to read the local. But it is still nice that we get overload resolution errors reported inside the unreachable code, just in case there is something wrong there.

The C# 5.0 beta release is now available

Eric Lippert — Wed, 29 Feb 2012 16:07:08 GMT

I am super excited to announce that the beta release of Visual Studio version 11 (which includes the .NET CLR version 4.5, Visual Basic version 11 and C# version 5) is available for download right now. As you know if you've been following our CTP releases, in C# and VB we've greatly improved the ease of programming in an asynchronous "continuation-passing" style such that the compilers do the hard work of rearranging the code into a form amenable to asynchrony, so that you don't have to. VB also now has iterator blocks, and has surpassed C# in that VB iterator blocks can even be inside lambdas. Pretty neat.

And that's just the big stuff for C# and VB; there is an enormous amount of new stuff here in the languages, the tools and the runtime. I can't wait to see what developers do with all of these amazing features. Please, download the beta and give us feedback on what you like and what you don't like.

See the following blog posts for more details:

* Jason Zander
* C# Team
* VB Team

The Solution To The Simple Puzzle

Eric Lippert — Mon, 27 Feb 2012 14:04:00 GMT

The first time I ran my histogram visualizer I asked for a Cauchy distribution with a minimum of -10 and a maximum of 10, and of course I got a graph that looks much like the one from my article of last week:

Looks perfectly reasonable; I guess my program is correct right out of the gate, because I am that awesome!

Then I went to make a graph of a uniform distribution with a minimum of zero and a maximum of one, but I forgot to update the actual query; it still gave me a Cauchy distribution. Here's that same Cauchy distribution this time graphed only from 0 to 1. Oh, the pain:

Which is obviously neither uniform nor Cauchy. Equally obvious: I am not sufficiently awesome to write a twenty-line program without a trivial floating point bug the first time.

The bug, which is very subtle in the first graph, was now obvious: the calculation to determine what the count is for the leftmost bucket is wrong. Why? Because converting a double to an integer simply discards the fractional part, effectively truncating towards zero, and "towards zero" is not downwards if any datum is negative. That means that the leftmost bucket got everything that was supposed to be in it, and everything that was supposed to be in the bucket to its left as well! The solution is either to take the floor of the number before turning it into an int, or to check to see if the double is in the right range before truncating it, not after.

A Simple Puzzle

Eric Lippert — Fri, 24 Feb 2012 14:45:00 GMT

My original version of the histogram-generating code that I whipped up for the previous episode of FAIC contained a subtle bug. Can you spot it without going back and reading the corrected code?

private static int[] CreateHistogram(IEnumerable<double> data, int buckets, double min, double max)
{
int[] results = new int[buckets];
double multiplier = buckets / (max - min);
foreach (double datum in data)
{
 int index = (int) ((datum - min) * multiplier);
 if (0 <= index && index < buckets)
 results[index] += 1;
}
return results;
}

Note that of course if this were production code, instead of demo code I whipped up in five minutes, it would be a lot more robust in its error detection; the bug that I am looking for is a bona fide error in the logic of the method, rather than things like "the method does not verify that min is smaller than max", and so on.

A hint: the first time I ran this code and displayed the results, the generated histogram looked fine. Then I made a small change to the arguments and the resulting histogram image was obviously wrong. Can you spot the defect?

Generating Random Non-Uniform Data In C#

Eric Lippert — Tue, 21 Feb 2012 14:20:00 GMT

When building simulations of real-world phenomena, or when generating test data for algorithms that will be consuming information from the real world, it is often highly desirable to produce pseudo-random data that conform to some nonuniform probability distribution.

But perhaps I have already lost some readers who do not remember STATS 101 all those years ago. I sure don't. Let's take a step back.

The .NET Framework conveniently provides you with a pseudo-random number generator that produces an approximately uniform distribution (*) of doubles between zero and one. By a "uniform distribution" we mean that if you took a whole lot of those random numbers and put them in two buckets, based on whether they were greater than one half or smaller than one half, then you would expect to see roughly half the numbers in each bucket; there is no bias towards either side. But moreover: if you took those same numbers and put them in ten buckets, based on whether they were in the range 0.0-0.1, 0.1-0.2, 0.2-0.3, and so on, you would also expect to see no particular bias towards any of those buckets either. In fact, no matter how many buckets of uniform size you make, if you have a large enough sample of random numbers then each bucket will end up with approximately the same number of items in it.

That's what we mean by a "uniform probability distribution": the number of items you find in the bucket is proportional to the size of the bucket, and has nothing to do with the position of the bucket. Here I've generated one hundred thousand pseudo-random numbers between zero and one, put them into fifty buckets, and graphed the number of items found in each bucket: (**)

Such a graph is called a histogram. As you can see, each of the 50 buckets contains approximately 2% of the total, and there seems to be no particular pattern to which buckets were lucky enough to get a few more than average. This histogram is entirely characteristic of a uniform distribution.

Now let's consider for a moment the relationship between the geometry and probability. Suppose we chose one of those data at random, from the hundred thousand points. What is the probability that it was in bucket 25? Obviously, the "height" of that bucket on the graph divided by the total number of items. But geometrically, we could think of this probability as the area under the curve limited to the region of bucket 25 divided by the total blue area.

Do you notice something vexing about this graph though? The axes are completely determined by the arbitrary factors that I chose in running my simulation. Let's normalize this. We'll re-label the horizontal axis so that it represents the highest value that would have been put in that bucket. How shall we re-label the vertical axis? Well, we said that the probability of a particular datum being found in a particular bucket was proportional to the area of that bucket. Therefore, let's recalibrate the axis such that the total area of the graph is 100%. That way, the answer to "what is the probability of a given item being found in such and such a region?" is precisely the area of that region:

This normalization has the beautiful property that no matter how many random numbers we generate, and no matter how many buckets we put them in, every histogram will look more or less the same, and will have the same labels on the axes; the distribution will go from zero to one on both axes and the total area will always be 100%.

Now imagine what would happen in the limiting case. Suppose we kept generating more and more numbers; trillions of them. And we made the buckets smaller and smaller. If you squint a bit, you might as well just say that you're going to do a graph as though the whole thing were continuous, and just draw the extraordinarily simple line graph:

And there you have it; the continuous uniform distribution. But that is certainly not the only distribution! There is the famous "bell curve" or "normal" distribution. The range of the normal distribution is infinite on both ends; a normally-distributed random value can have any magnitude positive or negative. Here's Wikipedia's image of four different bell curves:

Remember, these are just the limiting case of a histogram with a huge number of buckets and a huge number of samples. With these distributions, again, the probability of a value being found in a particular range is proportional to the area under the curve in that range. And of course, the area under each one is the same -- 100% -- which is why the skinny bell is so much taller than the wide one. And notice also how the vast majority of the area is very, very close to the peak in every case. The normal distribution is a "thin, long tail" distribution.

There are other distributions as well. For example, the Cauchy distribution also has the characteristic bell shape, but its tail is a bit "fatter" than the normal distribution. Here, again from Wikipedia we have four Cauchy distributions:

Notice how much fatter those tails are, and how the "bell" correspondingly has to be narrower to ensure that the area still adds up to 100%.

You know something that is still a bit odd about these graphs though? Because the probability is proportional to the area under the curve, the actual value of the curve at any given point isn't really that meaningful. Another way to characterize a probability distribution is to work out the probability of a given number or any number less than it being chosen; that is the area under the curve to the left of that number. Of course, the area under the curve is simply the integral, so let's graph the integral. We know that such a curve is going to increase monitonically from a limit on the left of zero to a limit on the right of one, since the probability of getting any very, very small number is close to zero, and the probability of getting any number smaller than a very large number is close to 100%. If we graph the integral of these four Cauchy distributions we get:

That graph is called the cumulative distribution and notice how it is extremely easy to read! Consider the purple line; clearly the probability of getting a value of two or less is about 85%; we can just read it right off. This graph has exactly the same information content as the "histogram limit" probability distribution; its just a bit easier to read. It is quite difficult to tell from reading the original graph that about 85% of the area under the curve is to the left of the 2.

Apropos of nothing in particular, I note that we have a function here that is monotone increasing; that means that we can invert it. Let's swap the x and y axes:

This function -- the inverse of the integral of the probability distribution -- is called the quantile function. It tell you "given a probability p from zero to one, what is the number x such that the probability of getting a number less than x is equal to p?" That graph should look familiar to anyone who has taken high school trig; the quantile function of the Cauchy distribution is simply the tangent function rejiggered to go from zero to one instead of -π / 2 to π / 2.

So that's pretty neat; the Cauchy bell-shaped curve is in fact just the derivative of the arctangent! But so what? How is this relevant?

We started this fabulous adventure by saying that sometimes you want to generate numbers that are random but not uniform. The graph above transforms uniformly-distributed random numbers into Cauchy-distributed random numbers. It is amazing, but true! Check it out:

private static Random random = new Random();
private static IEnumerable<double> UniformDistribution()
{
while (true) yield return random.NextDouble();
}

private static double CauchyQuantile(double p)
{
return Math.Tan(Math.PI * (p - 0.5));
}

private static int[] CreateHistogram(IEnumerable<double> data, int buckets, double min, double max)
{
int[] results = new int[buckets];
double multiplier = buckets / (max - min);
foreach (double datum in data)
{
 double index = (datum - min) * multiplier;
 if (0.0 <= index && index < buckets)
 results[(int)index] += 1;
}
return results;
}

and now you can tie the whole thing together with:

var cauchy = from x in UniformDistribution() select CauchyQuantile(x);
int[] histogram = CreateHistogram(cauchy.Take(100000), 50, -5.0, 5.0);

And if you graph the histogram, sure enough, you get a Cauchy distribution:

So, summing up: if you need random numbers that are distributed according to some distribution, all you have to do is

(1) work out the desired probability distribution function such that the area under a portion of the curve is equal to the probability of a value being randomly generated in that range, then
(2) integrate the probability distribution to determine the cumulative distribution, then
(3) invert the cumulative distribution to get the quantile function, then
(4) transform your uniformly distributed random data by running it through the quantile function,

and you're done. Piece of cake!

Next time: a simple puzzle based on an error I made while writing the code above.

(*) A commenter correctly points out that the set of real values representable by doubles is not uniformly distributed across the range of 0.0 to 1.0, and that moreover, the Random class is not documented as guaranteeing a uniform distribution. However, for most practical applications it is a reasonable approximation of a uniform distribution.

(**) Using the awesome Microsoft Chart Control, which now ships with the CLR. It was previously only available as a separate download.

Bad Metaphors

Eric Lippert — Mon, 13 Feb 2012 17:15:00 GMT

The standard way to teach beginner OO programmers about classes is to make a metaphor to the real world. And indeed, I do this all the time in this blog, usually to the animal kingdom. A "class" in real life codifies a commonality amongst a certain set of objects: mammals, for example, have many things in common; they have backbones, can grow hair, can make their own heat, and so on. A class in a programming language does the same thing: codifies a commonality amongst a certain set of objects via the mechanism of inheritance. Inheritance ensures commonalities because, as we've already discussed, "inheritance" by definition means "all (*) the members of the base type are also members of the derived type".

Inheritance relationships amongst classes (**) are usually designed to model "is a special kind of" relationships. A giraffe is a special kind of mammal, so the class Giraffe inherits from the class Mammal, which in turn inherits from Animal, which inherits from Object. And that's great; this clearly represents "is a special kind of" relationships. I have always, however, had a problem with the fundamental metaphor of "inheritance". Why "inheritance"? You inherit genetic information, property, and if you're a titular lord, your peerage, from your parents. And if you make a diagram of a class hierarchy, it looks a bit like a "family tree" in which the derived class is the "child" of the base "parent" class. And indeed, people often speak of the base class as the "parent" class of a "child" derived class, particularly when speaking to beginners.

But the "parent-to-child inheritance" metaphor is awful. A giraffe is not "a child of mammal"; a giraffe is a child of Mr. and Mrs. Giraffe. A "child" is not "a special kind of parent". In reality, you only inherit half your genetic makeup from each parent, and you can inherit real property from any relation, or for that matter, from any non-relation. In programming languages you only "inherit" from related types, and you inherit all their members (*). In reality, everyone has two parents (***), but in programming languages some languages allow inheritance from arbitrarily many "parents", some allow exactly one. In reality, a single, specific person inherits specific property from a single, specific parent, and two different children can have entirely different inheritances from their parent; in programming languages, the "inheritance" relationship does not apply to individual objects, and every child inherits exactly the same thing from the parents. And in reality you only inherit real property when the decedent is dead!

But wait, it gets worse. The parent-child metaphor is ambiguous in any language that supports both lexical nesting and nominal subtyping of classes:

class B<T>
{
class D : B { }
}

Quick, what type is the "parent" of type B<string>.D<int>? Is it B<T> or B<string> or B<int>? That type is lexically inside B<T>, logically inside of B<string>, and derived from B<int>; which of those three is its parent? If you drew a graph showing either lexical or logical containment relationships, it would form a graph that looks every bit as much like a "family tree" as the graph showing inheritance relationships. And lexical containment allows access to all the properties of the container from the contained type, even including not-inherited and normally inaccesible members like private constructors! It is not at all clear that one kind of "parentage" is actually more "parent-like" than any other.

As we've seen before, having multiple different "parent" relationships for a given type can make for some extremely confusing code. We have to be extraordinarily careful when writing the specification and the compiler to ensure that we unambiguously describe precisely the relationship we wish to describe. I therefore try hard to avoid "parent-child" metaphors entirely; it is much more clear when writing an example to describe the type relationship as "base type and derived type", rather than "parent type and child type".

(*) Excepting constructors and destructors.

(**) I'm going to stick to talking about class-based inheritance here; my criticisms apply equally well to interface-based inheritance but I don't want to open the can of worms that is all the subtle differences between class and interface inheritance. And I've never much liked the inheritance metaphor on interfaces anyways; a "contractual obligation" metaphor is better.

(***) Assuming that we're talking about members of a sexually reproducing species.

What is "binding" and what makes it late?

Eric Lippert — Mon, 06 Feb 2012 18:39:00 GMT

"Late binding" is one of those computer-sciency terms that, like "strong typing", means different things to different people. I thought I might describe what the term means to me.

First off, what is "binding"? We can't understand what it means to bind late if we don't know what it is to bind at all.

A compiler is by definition a device which takes in a text written in one language and outputs code that "means the same thing" in another language. The compiler I work on, for example, takes in C# and outputs CIL(*). All the principle tasks performed by a compiler falls into one of three broad buckets:

Syntactic analysis of the input text
Semantic analysis of the syntax
Generation of the output text -- we will be unconcerned with this step in this article

Syntactic analysis is analysis of the input text that does not consider anything about the meaning of that text; the syntactic analyzer is concerned with first determining the lexical structure of the program (that is, where all the boundaries are between comments, identifiers, operators, and so on) and then from that lexical structure determining the grammatical structure of the program: where are the boundaries between classes, methods, statements, expressions, and so on.

Semantic analysis then takes the results of the syntactic analysis and associates meanings with various syntactic elements. For example, when you say:

class X {}
class B {}
class D : B
{
public static void X() { }
public static void Y() { X(); }
}

syntactic analysis determines that there are three classes, that one of them contains two methods, the second method contains a statement which is a call expression. Semantic analysis determines that the X in X(); refers to the method D.X(), rather than, say, the type X declared above. That's an example of "binding" in its most widely-agreed-upon sense: binding is the association of a syntactic element that names a method with a logical element of the program.

"Binding" in the sense of "early" or "late" binding is almost always used to refer to the evaluation of a name used as a method call. That, however, is far too strict a definition of "binding" for me. I would also use "binding" to describe how the compiler's semantic analyzer determines that class D inherits from class B; the name "B" is bound to the class.

Moreover, I would use "binding" to describe other analyses as well. If you had an expression 1 * 2 + 1.0 in your program then I would say that the "+" operator is "bound" to the built-in operator that takes two doubles, adds them, and returns a third. People do not normally think of that analysis as associating the name "+" with a method, but nevertheless I consider it to be "binding".

Speaking even less carefully, I might also use "binding" to describe the association of types with expressions that do not directly name the type. In the example above if speaking casually I might say that the syntax 1 * 2 is "bound" to the type int, even though obviously it does not name that type. The syntactic expression is strongly associated with that semantic element, even though it does not name it.

So, speaking generally I would say that "binding" is any association of some fragment of syntax with some logical program element. (**)

What then is "late" vs "early" binding? People talk about these two kinds of bindings as though it was a binary choice, either early or late. As we'll see, actually there is more of a spectrum than you might imagine; some bindings are entirely early, some are partially early and partially late, and some are very late indeed. But before we get into that, earlier or later than what?

Basically by "early binding" we mean "the binding analysis is performed by the compiler and baked in to the generated program"; if the binding fails then the program does not run because the compiler did not get to the code generation phase. By "late binding" we mean "some aspect of the binding will be performed by the runtime" and therefore a binding failure will manifest as a runtime failure. Early and late binding might better be called "static binding" and "dynamic binding"; static binding is binding performed using "static" facts known to the compiler, and dynamic binding is performed using facts "dynamically" known to the runtime.

So which is better? Clearly neither is unambiguously better than the other; if one was clearly the winner then we wouldn't be having this discussion in the first place. The benefit of early binding is that you gain confidence that your program will not fail at runtime; the down side is that you lose the flexibility that comes with late binding. Early binding requires that all information required to make the right binding decision be known before the program runs; but that information might not be available until runtime.

I said that early and late binding falls on a spectrum. Let's take a look at some examples in C# of how we can "turn the dial" on early-to-late binding.

We begin with our example above of calling the static method X. This analysis is entirely, unambiguously early. There is no doubt at all that when Y is called, it is going to call the method D.X. No part of that analysis is deferred until runtime and the call will unambiguously succeed.

Next, consider:

class B
{
public void M(double x) {}
public void M(int x) {}
}
class C
{
public static void X(B b, int d) { b.M(d); }
}

Now we know less. We do a lot of early binding here; we know that b is of type B and that the call is to B.M(int). But unlike the previous example, we have no guarantee from the compiler that this invocation will succeed. b could be null. We are essentially deferring the analysis of whether or not the receiver of the call is valid to the runtime to determine. One normally does not think of that as a "binding" decision though, because we are not associating syntax with a program element. Let's make the call in C; a little more late bound by changing B:

class B
{
public virtual void M(double x) {}
public virtual void M(int x) {}
}

We are now doing some binding analysis at compile time; we know that the invocation will be on the virtual method declared by B.M(int). We know that the call will succeed in the sense that there will be such a method to call. However, we do not know which method will actually be called at runtime! There could be a derived type that overrides that method; some completely other code could be called that appears nowhere in this program. Virtual dispatch is a form of late binding; the decision about which method to associate with the syntax b.M(d) is partially made by the compiler and partially made by the runtime.

How about this?

class C
{
public static void X(B b, dynamic d) { b.M(d); }
}

Now the binding is almost entirely deferred until runtime. The compiler generates code that tells the Dynamic Language Runtime that static analysis has determined that the static type of b is B and that the method being invoked is called M, but the actual overload resolution to determine whether it is B.M(int) or B.M(double) (or neither, if d is, say, a string) is done by the runtime based on that information. (***)

class C
{
public static void X(dynamic b, dynamic d) { b.M(d); }
}

Now the only portion of the binding performed early is the fact that this is a method call on a method named M. This is almost as late-bound as it gets, but we can in fact go one step further:

class C
{
public static void X(object b, object[] d, string m, BindingFlags f)
{
b.GetType().GetMethod(m, f).Invoke(b, d);
}
}

Now everything is late-bound; we don't even know what name we are going to be associating with a method. All we can possibly know is that the author of X expects that the object passed as b has a single method named by the string in m that match the flags in f, and that it takes the arguments given in d. There is nothing whatsoever we can do to analyze this call site at compile time. (****)

(*) Of course the output is encoded into a machine-readable binary format, rather than the human-readable CIL format.

(**) You might then ask whether "binding" and "semantic analysis" are not synonyms; surely semantic analysis is nothing more than the association of syntactic elements with their meanings! Binding is much of the semantic analysis phase of the compiler, but there are many analyses that we must perform after a method body is entirely "bound". Definite assignment analysis, for example, cannot by any reasonable stretch be called "binding"; it is not associating syntactic fragments with specific program elements. Rather, it is associating lexical locations with facts about program elements, facts like "the local variable blah is not definitely assigned at the beginning of this block". Similarly, optimizing arithmetic expressions is a form of semantic analysis but is clearly not "binding".

(***) The compiler could still do lots of static analysis here. For example, suppose B were a sealed class with no methods named M. Even with a dynamic argument to the call we could know statically that the runtime binding of M will always fail, and tell you that at compile time. And in fact the compiler does some such analyses; precisely how it does so is a good topic for another day.

(****) In some sense this example gives a counterexample to my definition of binding; we are no longer even associating a syntactic element with a method; we're associating the contents of a string with a method.

What's the difference? Trenchcoat vs Duster

Eric Lippert — Fri, 03 Feb 2012 14:52:00 GMT

Today, yet another episode in my ongoing series "What's the difference?" This time, a non-computer-related topic.

I am often complimented on my choice of outerwear in the Seattle rainy season, and I hate to respond to a well-meant compliment with a correction. So I usually let all those "Nice trenchcoat!" comments slide and just say "Thanks!" But as a public service, let me lay it out for you so that you don't make the same mistake. Here we see David Tennant as the Tenth Doctor wearing a classic example of a trenchcoat: (Click for a larger version.)

The trenchcoat is a long waterproof coat, traditionally made of gabardine. The term originated in the trenches of the First World War, due to the popularity of this style of coat amongst officers in the British armed forces. The trench coat is not merely a functional warm raincoat but also stylish, with long wide lapels and decorative buttons. The trenchcoat is often belted and might be tailored in at the waist, particularly for women's trenchcoats.

A duster is also a long waterproof coat that is often referred to as a "trenchcoat" -- but as you'll see, it is quite different in its details. Here's the duster I wear, an Australian-made Driza-Bone:

Note the lack of decorative elements, the flap over the closure, the no-lapel collar (which clasps shut, completely enclosing the neck if necessary) and the built-in extra rain protection on the shoulders. (*) Dusters are typically made of oilcloth and are built for handling the practicalities of herding sheep in the rain, not for style (**).

Not shown in this view: the interior includes straps that let you attach the bottom of the coat to your legs, so that it does not blow around when you are on horseback. Also, the back is cut in such a way that you can cover both your legs and the rear portion of the saddle with the coat. I usually take the bus and not a horse to work, but still it's nice to know that options are available should I need them. These practical elements are usually not present in trenchcoats.

Right, glad we got that sorted out. Next time: What is binding, and why is it always either early or late? Can't it ever be on time?

(*) Duster manufacturers always hasten to point out that the shoulders are already waterproof; the extra layer keeps your shoulders warmer by shedding rain more effectively.

(**) There are, of course, some dusters built for style; if you watch the "Matrix" series of movies you'll see the heroes wear an assortment of extremely stylish dusters and trenchcoats both.

Anonymous Types Unify Within An Assembly, Part Two

Eric Lippert — Mon, 30 Jan 2012 16:20:00 GMT

Last time I noted that any two usages of "the same" anonymous type within an assembly actually unify to be the same type. By "the same" we mean that the two anonymous types have the same property names and types, and that they appear in the same order. new {X = 1, Y = 2 } and new { Y = 2, X = 1 } do not unify to a single type.

Why is that? You'd think that we could make these unify.

The trouble is that doing so causes more problems than it mitigates. An anonymous type gives you a convenient place to store a small immutable set of name/value pairs, but it gives you more than that. It also gives you an implementation of Equals, GetHashCode and, most germane to this discussion, ToString. (*)

Imagine, for instance, that you have written a bunch of LINQ queries in your code that extract data from a table using an anonymous type. As part of your unit testing, you dump the results of the query as a string out to a file and compare it against a known baseline. Maybe you have hundreds of such tests. And then one day, someone in a completely different part of the code happens to write a LINQ query that has "the same" anonymous type, but with the properties in a different order. We have to pick some order for the properties to be written out by "ToString", and there is no telling which one we'd pick if forced to choose. It seems very strange that using an anonymous type in one part of the program would cause tests to fail in a completely different part of the program.

Well then, you might say, you could solve this problem by canonicalizing the implementation of ToString. Always write out the properties in alphabetical order, say. But that is hardly an attractive solution. First off, whose alphabetical order? There are dozens of different alphabetical orders, depending on what location in the world you are in. Should we choose the alphabetical order of the developer? The current user? The "culture neutral" order? Assuming we could solve that problem satisfactorily, we'd still be disappointing most users. Developers have a reasonable expectation that ToString will give them the properties in the order they appear in the source code.

Another option would be to not implement ToString for you at all. That is to say, remove a useful and relatively commonly used feature (dumping data to a string for testing or debugging) in order to effectively implement a less useful, rarely used feature (unification of types).

(*) We give you Equals and GetHashCode so that you can use instances of anonymous types in LINQ queries as keys upon which to perform joins. LINQ to Objects implements joins using a hash table for performance reasons, and therefore we need correct implementations of Equals and GetHashCode.

Anonymous types unify within an assembly, Part One

Eric Lippert — Mon, 23 Jan 2012 15:55:00 GMT

Back in my last post of 2010 I said that I would do an example of anonymous types unifying within an assembly "in the new year". I meant 2011, but here we are "in the new year" again, so, no time like the present.

The C# specification guarantees you that when you use "the same" anonymous type in two places in one assembly (*) the types unify into one type. In order to be "the same", the two anonymous types have to have the exact same member names and the exact same member types, in the exact same order. (**)

It is easy to see how this works in a method body; you could simply say:

var anon1 = new { X = 1 };
var anon2 = new { X = 2 };
anon2 = anon1;
Console.WriteLine(anon2.X); // 1

And it is easy to see how you could verify this fact with reflection across method bodies within the same assembly:

class C
{
    public static object Anon1() { return new { X = 1 }; }
}
class D
{
    static void M()
    {
        // True:
        Console.WriteLine(C.Anon1().GetType() == (new { X = 2 }).GetType());
    }
}

But... so what? Using reflection in this way seems supremely uninteresting. What would be more interesting is to merge the two examples together:

class C
{
 public static object Anon1() { return new { X = 1 }; }
}
class D
{
 static T CastByExample<T>(T example, object obj)
 {
 return (T)obj;
 }
 static void M()
 {
 var anon1 = CastByExample(new { X = 0 }, C.Anon1());
 var anon2 = new { X = 2 };
 anon2 = anon1;
 Console.WriteLine(anon1.X); // 1
 }
}

As you can see, you can share instances of an anonymous type around an assembly if you want to. We do not expect that a lot of people will do so; typically if this is the sort of thing you like doing, you'd use either a tuple or a custom-built nominal type. Still, it is not expensive for us to make this guarantee, and it is kind of a nice property.

(*) Technically not exactly true. You could have an assembly made up of many different netmodules compiled at different times that do not know about each other; anonymous types defined in one netmodule will not necessarily unify with those in others.

(**) Next time I'll discuss why we have this latter requirement.

What is the defining characteristic of a local variable?

Eric Lippert — Mon, 16 Jan 2012 14:48:00 GMT

If you ask a dozen C# developers what a "local variable" is, you might get a dozen different answers. A common answer is of course that a local is "a storage location on the stack". But that is describing a local in terms of its implementation details; there is nothing in the C# language that requires that locals be stored on a data structure called "the stack", or that there be one stack per thread. (And of course, locals are often stored in registers, and registers are not the stack.)

A less implementation-detail-laden answer might be that a local variable is a variable whose storage location is "allocated from the temporary store". That is, a local variable is a variable whose lifetime is known to be short; the local's lifetime ends when control leaves the code associated with the local's declaration space.

That too, however, is a lie. The C# specification is surprisingly vague about the lifetime of an "ordinary" local variable, noting that its lifetime is only kinda-sorta that length. The jitter's optimizer is permitted broad latitude in its determination of local lifetime; a local can be cleaned up early or late. The specification also notes that the lifetimes of some local variables are necessarily extended beyond the point where control leaves the method body containing the local declaration. Locals declared in an iterator block, for instance, live on even after control has left the iterator block; they might die only when the iterator is itself collected. Locals that are closed-over outer variables of a lambda are the same way; they live at least as long as the delegate that closes over them. And in the upcoming version of C#, locals declared in async blocks will also have extended lifetimes; when the async method returns to its caller upon encountering an "await", the locals live on and are still there when the method resumes. (And since it might not resume on the same thread, in some bizarre situations, the locals had better not be stored on the stack!)

So if locals are not "variables on the stack" and locals are not "short lifetime variables" then what are locals?

The answer is of course staring you in the face. The defining characteristic of a local is that it can only be accessed by name in the block which declares it; it is local to a block. What makes a local truly unique is that it can only be a private implementation detail of a method body. The name of that local is never of any use to code lexically outside of the method body.

Every public change is a breaking change

Eric Lippert — Mon, 09 Jan 2012 17:08:00 GMT

Here's an inconvenient truth: just about every "public surface area" change you make to your code is a potential breaking change.

First off, I should clarify what I mean by a "breaking change" for the purposes of this article. If you provide a component to a third party, then a "breaking change" is a change such that the third party's code compiled correctly with the previous version, but the change causes a recompilation to fail. (A more strict definition would be that a breaking change is one where the code recompiles successfully but has a different meaning; for today let's just consider actual "build breaks".) A "potential" breaking change is a change which might cause a break, if the third party happens to have consumed your component in a particular way. By a "public surface area" change, I mean a change to the "public metadata" surface of a component, like adding a new method, rather than changing the behaviour of an existing method by editing its body. (Such a change would typically cause a difference in runtime behaviour, rather than a build break.)

Some public surface area breaking changes are obvious: making a public method into a private method, sealing an unsealed class, and so on. Third-party code that called the method, or extended the class, will break. But a lot of changes seem a lot safer; adding a new public method, for example, or making a read-only property into a read-write property. As it turns out, almost any change you make to the public surface area of a component is a potential breaking change. Let's look at some examples. Suppose you add a new overload:

// old component code:
public interface IFoo {...}
public interface IBar { ... }
public class Component
{
public void M(IFoo x) {...}
}

Suppose you then later add

public void M(IBar x) {...}

to Component. Suppose the consumer code is:

// consumer code:
class Consumer : IFoo, IBar
{
   ...
   component.M(this);
   ...
}

The consumer code compiles successfully against the original component, but recompiling it with the new component suddenly the build breaks with an overload resolution ambiguity error. Oops.

What about adding an entirely new method?

// old component code:
...
public class Component
{
public void MFoo(IFoo x) {...}
}

and now you add

public void MBar(IBar x) {...}

No problem now, right? The consumer could not possibly have been consuming MBar. Surely adding it could not be a build break on the consumer, right?

class Consumer
{
 class Blah
 {
 public void MBar(IBar x) {}
 }
 static void N(Action<Blah> a) {}
 static void N(Action<Component> a) {}
 static void D(IBar bar)
 {
 N(x=>{ x.MBar(bar); });
 }
}

Oh, the pain. In the original version, overload resolution has two overloads of N to choose from. The lambda is not convertible to Action<Component> because typing formal parameter x as Component causes the body of the lambda to have an error. That overload is therefore discarded. The remaining overload is the sole applicable candidate; its body binds without error with x typed as Blah.

In the new version of Component the body of the lambda does not have an error; therefore overload resolution has two candidates to choose from and neither is better than the other; this produces an ambiguity error.

This particular "flavour" of breaking change is an odd one in that it makes almost every possible change to the surface area of a type into a potential breaking change, while at the same time being such an obviously contrived and unlikely scenario that no "real world" developers are likely to run into it. When we are evaluating the impact of potential breaking changes on our customers, we now explicitly discount this flavour of breaking change as so unlikely as to be unimportant. Still, I think its important to make that decision with eyes open, rather than being unaware of the problem.

He's So Dreamy

Eric Lippert — Mon, 02 Jan 2012 17:23:00 GMT

Happy New Year all!

It has just been brought to my attention that this blog and the Programmer Ryan Gosling photo blog share at least one reader:

I admit it, I LOL'd.

In the interests of total accuracy I'd like to point out that the first entry on the blog contains a subtle error:

.NET actually supported generic covariance and contravariance on interface and delegate types from the beginning; generics were introduced in version 2, and they always allowed variance. You could write programs in MSIL and compile them with ILDASM and have generic variance, no problem. No "mainstream" language supported the feature until v4, and none of the interfaces or delegates in the class libraries were marked as variant, so effectively variance did not become a well-used feature until v4, but the capability was always there.

As a response to the unknown reader to submitted the first photo above, I give you the following:

Next time: some depressing news about breaking changes: they're everywhere!

Shadowcasting in C#, Part Six

Eric Lippert — Thu, 29 Dec 2011 15:05:00 GMT

OK, let's finish up this year and this series. We have an algorithm that can compute what cells in the zero octant are in view to a viewer at the origin when given a function that determines whether a given cell is opaque or transparent. It marks the visible points by calling an action with the visible cells. We would like that to work in any octant, and for the viewer at any point, not just the origin.

We can solve the "viewer at any point" problem by imposing a coordinate transformation on the "what is opaque?" function and the "cell is visible" action. Suppose the algorithm wishes to know whether the cell (3, 1) is opaque. And suppose the viewer is not at the origin, but rather at (5, 6). The algorithm is actually asking whether the cell at (3 + 5, 6 + 1) is opaque. Similarly, if that cell is determined to be visible then the transformed cell is the one that is visible from (5, 6). We can easily transform one delegate into another:

private static Func<int, int, T> TranslateOrigin<T>(Func<int, int, T> f, int x, int y)
{
return (a, b) => f(a + x, b + y);
}

private static Action<int, int> TranslateOrigin(Action<int, int> f, int x, int y)
{
return (a, b) => f(a + x, b + y);
}

Similarly we can perform an octant transformation; if you want to map a point in octant one into a point in octant zero, just swap its (x,y) coordinates! Every octant has a simple transformation that reflects it into octant zero:

private static Func<int, int, T> TranslateOctant<T>(Func<int, int, T> f, int octant)
{
 switch (octant)
 {
 default: return f;
 case 1: return (x, y) => f(y, x);
 case 2: return (x, y) => f(-y, x);
 case 3: return (x, y) => f(-x, y);
 case 4: return (x, y) => f(-x, -y);
 case 5: return (x, y) => f(-y, -x);
 case 6: return (x, y) => f(y, -x);
 case 7: return (x, y) => f(x, -y);
 }
}

(And similarly for actions.)

Now that we have these simple transformation functions we can finally implement the code that calls our octant-zero-field-of-view algorithm:

public static void ComputeFieldOfViewWithShadowCasting(
 int x, int y, int radius,
 Func<int, int, bool> isOpaque,
 Action<int, int> setFoV)
{
 Func<int, int, bool> opaque = TranslateOrigin(isOpaque, x, y);
 Action<int, int> fov = TranslateOrigin(setFoV, x, y);

for (int octant = 0; octant < 8; ++octant)
 {
 ComputeFieldOfViewInOctantZero(
 TranslateOctant(opaque, octant),
 TranslateOctant(fov, octant),
 radius);
 }
}

Pretty slick, eh?

One minor downside of this algorithm is that it computes the visibility of the points along the axes and major diagonals twice; however, the number of such cells grows worst case linearly with radius. The algorithm as a whole is worst case quadradic in the radius, so the extra linear cost is probably irrelevant.

I've posted the project that builds the Silverlight control from the first episode here, if you want to get a complete working example.

Happy New Year everyone and we'll see you in 2012 for more Fabulous Adventures in Coding!

Shadowcasting in C#, Part Five

Eric Lippert — Tue, 27 Dec 2011 18:05:00 GMT

I hope you all had a pleasant Christmas and Boxing Day; we chose to not travel to see family this year and had a delightful time visiting friends. We'll finish up 2011 here with a bit more on shadowcasting, and then pick up with more C# language design facts and opinions in January.

OK, so we've found the top and bottom cells in a particular column portion, bounded by a top and bottom vector. Now we have two tasks. First, all cells in that portion that are in the radius need to be marked as visible. Second, we must figure out what portions of the next column are visible through this portion, and enqueue that work.

The first bit is easily done. Thanks to the great comments to my earlier entry I've learned that of course it is better to consider the question "is the bottom left corner of the cell within the visible radius?" That makes for a nicer looking circle. I've made a helper method "IsInRadius" that does that. (Note that of course this introduces yet another kind of artifact; suppose that of the four corners of a cell, only the bottom right corner of a cell is below the top vector, but only the bottom left corner is within the radius. There might be no point in the cell that is both within the radius and not blocked. We'll ignore this detail; the radius is inherently approximate.)

The second bit is harder. What we'll do is keep track as we move from top to bottom of this portion whether we have seen any transitions from transparent to opaque or opaque to transparent. If we find a transition from transparent to opaque then we have found a boundary for the next column portion; we'll enqueue that new portion. If we find a transition from opaque to transparent then we'll enqueue new work for the new region when either we find an opaque cell or the bottom of the portion.

bool? wasLastCellOpaque = null;
for (int y = topY; y >= bottomY; --y)
{
    bool inRadius = IsInRadius(x, y, radius);
    if (inRadius)
    {
        // The current cell is in the field of view.
        setFieldOfView(x, y);
    }

A cell that was too far away to be seen is effectively an opaque cell; nothing "above" it is going to be visible in the next column, so we might as well treat it as an opaque cell and not scan the cells that are also too far away in the next column.

    bool currentIsOpaque = !inRadius || isOpaque(x, y);
    if (wasLastCellOpaque != null)
    {
        if (currentIsOpaque)
        {

We've found a boundary from transparent to opaque. Enqueue more work for later.

if (!wasLastCellOpaque.Value)
{

The new bottom vector touches the upper left corner of opaque cell that is below the transparent cell.

                queue.Enqueue(new ColumnPortion(
                    x + 1,
                    new DirectionVector(x * 2 - 1, y * 2 + 1),
                    topVector));
            }
        }
        else if (wasLastCellOpaque.Value)
        {

We've found a boundary from opaque to transparent. Adjust the top vector so that when we find the next boundary or do the bottom cell, we have the right top vector. The new top vector touches the lower right corner of the opaque cell that is above the transparent cell, which is the upper right corner of the current transparent cell.

I normally don't modify a formal parameter like this, but it seems reasonably unconfusing in this context.

            topVector = new DirectionVector(x * 2 + 1, y * 2 + 1);
        }
    }
    wasLastCellOpaque = currentIsOpaque;
}

And finally, we enqueue work for the lowest opaque-to-transparent transition, if there is one.

if (wasLastCellOpaque != null && !wasLastCellOpaque.Value)
queue.Enqueue(new ColumnPortion(x + 1, bottomVector, topVector));

And there you go; that's shadowcasting from the origin in the first octant. Next time we'll deal with the other seven octants, and deal with points other than the origin.

Shadowcasting in C#, Part Four

Eric Lippert — Thu, 22 Dec 2011 17:18:00 GMT

Last time we saw how many different ways there were to get the calculation of the top cell based on the top vector wrong. Today we'll take a briefer look at determining the bottom cell.

We know from our discussion of last time that the right way to determine what is the top-most visible cell in a column portion is to consider where the top vector leaves the column. By similar logic, the right way to determine where the bottom-most cell is in a column portion is to look at where the bottom vector enters the column. Clearly where the vector enters the current column is precisely the same place that it left the previous column, and we already know how to calculate that.

What sorts of things go wrong if you, say, round down instead of rounding to the cell where the vector enters the column? In my implementation of the other day I made a deliberate mistake: for the bottom direction vector I do the division and round down. This introduces some artifacts. For example, it means that you can see immediately behind nearby pillars but not behind far-away pillars:

Notice how the pillar to the left casts a full 90 degree shadow. However, the pillar to the right permits me to see the square immediately behind it, and then casts a shadow. This is not very realistic; if I can see immediately behind the pillar then why can I not also see beyond it?

Note that this also presents a gameplay problem. Suppose there was a monster "hiding" behind the pillar east of me there. I could see the monster, but it could not see me! If the targeting system for arrow attacks requires line-of-sight, and line-of-sight is determined by simply computing the whole field of view and checking whether the cell in question is in the field, then I can shoot the monster but it cannot shoot me. By similar logic, a monster that is two cells to the west of the pillar west of me can shoot me, but I cannot see it or shoot it.

Does this problem go away if we rewrite the rounding algorithm to be less permissive by rounding more appropriately? No! We still have a symmetry problem in a room full of pillars. Let's put both the "round down" and the "round to lowest column entry" algorithms next to each other for a comparison. Click on the control to play the game "in stereo":

Notice how in both implementations it is possible to get into a position where you can see behind a pillar, but the monster standing there cannot see you:

Monsters standing at the blue arrow cells are visible from the player's location, but the monsters cannot see the player. Monsters standing at the orange arrow locations can see the player, but the player cannot see them.

The problem here is that the algorithm computes the set of cells where any point in the target cell is visible from the center of the player's cell. In order for the algorithm to be symmetric we need to allow any point in the target cell to be visible from any point in the player's cell. That is the "permissive field of view" algorithm. It uses the same concepts that we've described here; it progressively scans a region (a quadrant, rather than an octant) and keeps a set of line segments (not vectors, since they need not go through the origin) that track what regions are in view as you get farther and farther away from the origin. It's a rather tricky algorithm to get right, and so I'm not going to present it here.

Next time: Now that we know how to compute the top and bottom cells, actually running the algorithm is pretty straightforward. We'll go through the details of the code.

Shadowcasting in C#, Part Three

Eric Lippert — Mon, 19 Dec 2011 16:06:00 GMT

Before we get started, thanks for all the great comments to the previous couple of posts. I'll be updating the algorithm to try to make even better-looking circles of light based on the comments. Like I said, there's a lot of subtleties to these algorithms and I am just learning about them myself.

To that end, in today's episode I am going to spend the entire prolix article analyzing a single division operation. You have been warned.

Before we begin though, some jargon. A cell which is invisible that by our physical interpretation ought to be visible, or a cell which is visible that ought to be invisible we will call an "artifact". An "artifact" is the product of our algorithm (or some detail of its implementation) not being a sufficiently accurate model of real-world physics. Today's article will be all about artifacts.

The actual workhorse that implements the field-of-view algorithm is this method that we mentioned last time:

private static void ComputeFoVForColumnPortion(
 int x,
 DirectionVector topVector,
 DirectionVector bottomVector,
 Func<int, int, bool> isOpaque,
 Action<int, int> setFieldOfView,
 int radius,
 Queue<ColumnPortion> queue)
{

This method has two main purposes. First, it assumes that all points in the portion of column x bounded by the top and bottom vectors are in the field of view, and marks them accordingly; some of them might be outside the radius, but the rest of them are by assumption visible from the origin. Second, it determines which portions of column x+1 are in the field of view and adds them to the work queue for later processing.

We described the algorithm as working from top to bottom of the portion of the column under consideration. Therefore the very first question we must answer is "which exactly is the top cell in the column portion, given the column number and the top direction vector?"

If the center point of a cell in column x happens to fall exactly on the top direction vector then it is pretty clear which is the top cell. Suppose for the sake of argument that's the case. The top cell is then computed by x * topVector.Y / topVector.X. This division is exact. Proving that is an easy bit of algebra and is left as an exercise.

So perhaps we should say that even if the division is inexact, we compute the top cell by:

int topY = x * topVector.Y / topVector.X;

(Note that we'll assume throughout that the numbers we are multiplying and dividing are small compared to the range of int, and therefore do not overflow.)

What happens if the division is inexact? We know that in C# an inexact integer division always rounds towards zero; it rounds down if necessary.

Rounding down is a bad idea because it doesn't model the physical world well and makes for extraordinarily bad-looking gameplay. Consider this extremely common scenario:

Scenario One

After processing column one we lower the slope of the top direction vector to one-third. Is point (2,1) in the field of view? It sure seems light it ought to be since its entire bottom surface is within the field of view. But if we do 2 * 1 / 3 we get zero, so no, the top cell that is visible in this column is (2, 0). We mark that as visible and continue on to column three without changing the slope. The top direction vector now intersects the center of cell (3, 1), so it and (3, 0) are visible. We lower the slope of the top vector to one-seventh, and now cell (4, 1) is not visible, again because we are rounding down. After processing all the columns shown here the state of affairs would be:

This matches neither the desired physics nor the desired gameplay; a straight corridor should not have weird "gap" artifacts. Notice also that the resulting top vector is a little bit too steep; we never considered the opaque cell in column four to be possibly shadowing anything beyond it; the rest of the world is only in the shadow of cell (3,1), not (4,1). Rounding down is clearly unacceptable.

Well. What to do, if rounding down doesn't work? Maybe we should round up!

That solves the problem for long corridors; now what happens is cell (2,1) is determined to be visible by rounding up, so the top slope is lowered to one-fifth. Then cell (3, 1) is determined to be visible, so the slope is lowered to one-seventh. Then cell (4,1) is determined to be visible, and the slope is lowered to one-ninth. That seems to be much better.

Moreover, we now also have the nice property that the corners of a room are visible. Consider this common situation:

Scenario Two

Cell (5,2) will be visible, which will render nicely, particularly if "box drawing" characters are used to represent interior corners as is the case in many roguelike games. This is a desirable artifact.

But surely now we have the opposite problem; if we round up then we are potentially making cells visible that ought to be in the shadow of some opaque cell. Let's take a look at an example of that.

Scenario Three

Cells (3,2) and (4,2) are unambiguously in the shadow of cell (2,1). But look carefully at column five. Even though the top vector does not pass through any part of (5,2) it does pass slightly above point (5,1) and therefore the division will round up such that (5,2) is considered visible! With this rounding algorithm you can "peek around a corner" a little bit. Visible point (5,2) is an artifact.

Even worse, consider what happens when the algorithm discovers that there is an opaque-to-transparent transition between (5,2) and (5,1). The top vector will be moved up!

That top vector is now steeper than it used to be. (Also note that if this had been the top vector when processing column four then the point (4,2) ought to have been visible.)

Obviously this situation can continue; rounding errors in later columns can continue to make the top vector steeper and steeper. (Exercise for the reader: is there a maximum slope that the top vector can attain via repeated applications of rounding error?)

We could easily put a check into the algorithm implementation to say that the top direction vector must never go from a shallower slope to a steeper slope. If we decided to use always-round-up rounding then we might do that. But it gets worse. Consider this scenario that I mentioned last time:

Scenario Four

Last time I made the simplifying assumption that cell (5,4) was out of range, and therefore not visible. But suppose the radius is larger; let's analyze this one in more detail. We'll round up to determine the highest visible cell in the column portion bounded by these vectors, so cell (5,4) is visible. We then find transitions from visible (5,4) to opaque (5,3) and opaque (5,2) to visible (5,1) (assuming that (5,1) is the bottom cell of the range; we'll discuss that assumption next time.) Therefore we have to divide this up into two sub-portions for column six. To compute the upper portion we keep the top vector the same and move the bottom vector up; to compute the lower portion we keep the bottom vector the same and move the top vector down. The result is this godawful mess:

The top direction vector of the upper column portion is now below the bottom vector. Yikes!

This error again allows the player to "look around corners" in a weird way, but it really is not so bad. What will happen here is that as long as the mis-ordered vectors identify the same cell as the top and bottom cell of the visible portion for a particular column, that single cell will be visible. As soon as the portion is large enough that the top and bottom cells are different, the loop that goes from top to bottom will immediately exit.

Again, we could prevent this situation by doing a check that verifies that the bottom vector is never moved to be above the top vector. However, perhaps we'd decide that this situation is sufficiently rare, and the artifact is sufficiently benign, that we'd just allow it.

Rounding up seems better than rounding down, but this still isn't great. Hmm. What if we rounded to the nearest lattice point?

Scenario One is unchanged. We still correctly compute visibility of the entire long straight wall.

Scenario Two is unchanged. We still make the desirable "corner artifact".

Scenario Three is improved. Cell (5,2) is not treated as visible, which is good because it is entirely in shadow. The top vector is not made more steep.

Scenario Four is unchanged. We can still end up in a situation where the top and bottom direction vectors are mis-ordered.

That's no change in three scenarios and a great improvement in one, so this is an unambiguous win, right?

Not quite. Consider this scenario:

Scenario Five

If we round to nearest then (4,3) is not visible, even though a full 30% of its lower surface has line of sight from the origin. Furthermore, by not treating this cell as visible, we fail to lower the slope of the top vector from 3/5 to 5/9, possibly allowing more cells to be visible in higher columns that ought to be shadowed by (4,3). Round-up would have treated (4,3) as the topmost cell in the region, so round-to-nearest is not an unambiguous win over round-up.

At this point it would be wise to take a step back and ask ourselves if continuing to tweak how the division rounds is the right thing to do. When you propose three different plausible calculations and they all turn out to be wrong in different ways, there might be an invalid assumption somewhere in the mix.

The invalid assumption is that y = SomeKindOfRoundingOf(x, top.Y, top.X) is correct in the first place. It is not. This calculation, no matter how you round it, is fundamentally calculating where the vector intersects the center of the column. Why is the center of the column at all relevant? It is the edges of the cell that cast shadows!

What we want to compute is "what is the highest cell in the given column that is anywhere intersected by the top direction vector?" The slope of the top direction vector is always positive; the line is always "sloping up", so the top cell can be identified by figuring out where the vector leaves the column. What we should be doing is working out the intercept of the vector with x + 0.5, not with x.

How are we going to do that? The first thing to observe is that (x + 0.5 ) * top.Y / top.X is the same thing as (2 * x + 1) * top.Y / (2 * top.X). Now everything is in integers. Let's work out the quotient and the remainder in integers:

int quotient = ((2 * x + 1) * top.Y) / (2 * top.X);
int remainder = ((2 * x + 1) * top.Y) % (2 * top.X);

Let's look at a bunch of possible different possibilities. Suppose the direction vector is (5, 3), so we go five "right" for every three "up". The interesting points are the points where the vector exits the column on the right hand side. The quotient is the black horizontal line below the interesting point. In this example the remainder is the number of tenths the interesting point is above the quotient line. (Tenths because the denominator is 5 x 2.) The numbers at the bottom of each column are the remainders:

(Note that the dividend will always be an odd number and the divisor will always be an even number, and therefore the remainder will always be an odd number. Proving those assertions is left as an exercise. Hint: what possible y values can the top direction vector take on if restricted only to integers?)

So, how should we round? Consider the columns labeled 1 and 3. In those the rounded-down quotient correctly identifies the cell that the direction vector intersects. The columns labeled 7 and 9, however, have a problem; the quotient is one below the correct result; we have rounded down incorrectly. What about the column labeled 5? If the remainder is exactly the "run" value of the top direction vector then the vector passes exactly through the boundary where two cells meet; which one should be visible? Since this is the "top" bounding vector, we should round down; no area of the upper cell is visible.

So, in summary: use the rounded-down quotient as the top cell in the column if the remainder is top.X or less; otherwise, round it up by adding one to the quotient.

Does that solve our problems?

Scenario One: Good. We correctly put the whole corridor wall into the field of view.

Scenario Two: Good. We "correctly" put the invisible corner cell into the field of view.

Scenario Three: Good. Cell (5,2) is not identified as being visible, and therefore the top vector's slope is not increased.

Scenario Four: Bad. We incorrectly identify cell (5,4) as being visible through cell (5,3), and thereby produce not only an artifact, but an "inverted" set of top and bottom vectors for the next column.

Scenario Five: Good. We make cell (4,3) visible and lower the slope of the top vector accordingly.

This algorithm is not perfect; we still make some artifacts. How might we solve the issue of scenario four?

A couple ways come to mind. One is that we could check to see if the direction vector enters the column at (5,3) and exits at (5,4). If it does then (5,4) is only the top cell if (5,3) is transparent.

Another way would be to allow cell (5,4) to be visible regardless -- this might have nice properties for showing corners, even if the cell is technically an artifact -- but to detect whether the new bottom vector is steeper than the old top vector and not allow the recursion.

In my actual implementation of last week I decided that solving the problem of scenario four is not worth it to me; I allow the artifacts and the inverted range. The results seem pretty decent.

As I warned you, it took me an extremely long article with nine complicated diagrams to figure out how to divide two numbers to determine the top cell. I said this was going to be excessively detailed!

Next time we'll do the same analysis for determining the bottom cell in the column portion. Hopefully things will go a bit quicker now that we have the basic idea of how rounding produces artifacts down pat.