As I’ve mentioned several times on this blog before, C# has been carefully designed to eliminate some of the “undefined behaviour” and “implementation-defined behaviour” that you see in languages like C and C++. But I’m getting ahead of myself; I should probably start by making a few definitions.

Traditionally we say that a programming language idiom has undefined behaviour if use of that idiom can have any effect whatsoever; it can work the way you expect it to or it can erase your hard disk or crash your machine. Moreover, the compiler author is under no obligation to warn you about the undefined behaviour. (And in fact, there are some languages in which programs that use “undefined behaviour” idioms are permitted by the language specification to crash the compiler!)

An example of undefined behaviour in C, C++ and C# is writing to a dereferenced pointer that you have no business writing to. Doing so might cause a fault that crashes the process. But the memory could be valid, and it could be an important data structure of the runtime software. It could be code that you are now overwriting with code that does something else. And hence, anything can happen; you’re rewriting the software that is running right now into software that does something else.

By contrast, an idiom that has implementation-defined behaviour is behaviour where the compiler author has several choices about how to implement the feature, and must choose one. As the name implies, implementation-defined behaviour is at least defined. For example, C# permits an implementation to throw an exception or produce a value when an integer division overflows, but the implementation must pick one. It cannot erase your hard disk.

All that said, for the rest of this article I’m not going to make a strong distinction between these two flavours of underspecified behaviour. The question I’m actually interested in addressing today is:

What are some of the factors that lead a language design committee to leave certain language idioms as undefined or implementation-defined behaviours?

The first major factor is: are there two existing implementations of the language in the marketplace that disagree on the behaviour of a particular program? If FooCorp’s compiler compiles M(A(), B()) as “call A, call B, call M”, and BarCorp’s compiler compiles it as “call B, call A, call M”, and neither is the “obviously correct” behaviour then there is strong incentive to the language design committee to say “you’re both right”, and make it implementation defined behaviour. Particularly this is the case if FooCorp and BarCorp both have representatives on the committee.

The next major factor is: does the feature naturally present many different possibilities for implementation, some of which are clearly better than others? For example, in C# the compiler’s analysis of a “query comprehension” expression is specified as “do a syntactic transformation into an equivalent program that does not have query comprehensions, and then analyze that program normally”. There is very little freedom for an implementation to do otherwise. For example, you and I both know that

from c in customers 
from o in orders 
where c.Id == o.CustomerId 
select new {c, o}

and

from c in customers 
join o in orders 
  on c.Id equals o.CustomerId 
select new {c, o}

are semantically the same, and that the latter is likely to be more efficient. But the C# compiler never, ever turns the first query expression syntax into a call to Join; it always turns it into calls to SelectMany and Where. The runtime implementation of those methods is of course fully within its rights to detect that the object returned by SelectMany is being passed to Where, and to build an optimized join if it sees fit, but the C# compiler does not make any assumptions like that. We wanted the query comprehension transformation to be syntactic; the smart optimizations can be in the runtime.

By contrast, the C# specification says that the foreach loop should be treated as the equivalent while loop inside a try block, but allows the implementation some flexibility. A C# compiler is permitted to say, for example “I know how to implement the loop semantics more efficiently over an array” and use the array’s indexing feature rather than converting the array to a sequence as the specification suggests it should. A C# implementation is permitted to skip calling GetEnumerator.

A third factor is: is the feature so complex that a detailed breakdown of its exact behaviour would be difficult or expensive to specify? The C# specification says very little indeed about how anonymous methods, lambda expressions, expression trees, dynamic calls, iterator blocks and async blocks are to be implemented; it merely describes the desired semantics and some restrictions on behaviour, and leaves the rest up to the implementation. Different implementations could reasonably do different codegen here and still get good behaviours.

A fourth factor is: does the feature impose a high burden on the compiler to analyze? For example, in C# if you have:

Func<int, int> f1 = (int x)=>x + 1; 
Func<int, int> f2 = (int x)=>x + 1; 
bool b = object.ReferenceEquals(f1, f2);

Suppose we were to require b to be true. How are you going to determine when two functions are “the same”? Doing an “intensionality” analysis — do the function bodies have the same content? — is hard, and doing an “extensionality” analysis — do the functions have the same results when given the same inputs? — is even harder. A language specification committee should seek to minimize the number of open research problems that an implementation team has to solve! In C# this is therefore left to be implementation-defined; a compiler can choose to make them reference equal or not at its discretion.

A fifth factor is: does the feature impose a high burden on the runtime environment?

For example, in C# dereferencing past the end of an array is well-defined; it produces an array-index-was-out-of-bounds exception. This feature can be implemented with a small — not zero, but small — cost at runtime. Calling an instance or virtual method with a null receiver is defined as producing a null-was-dereferenced exception; again, this can be implemented with a small, but non-zero cost. The benefit of eliminating the undefined behaviour pays for the small runtime cost. But the cost of determining if an arbitrary pointer in unsafe code is safe to dereference would have a large runtime cost, and so we do not do it; we move the burden of making that determination to the developer, who, after all, is the one who turned off the safety system in the first place.

A sixth factor is: does making the behaviour defined preclude some major optimization? For example, C# defines the ordering of side effects when observed from the thread that causes the side effects. But the behaviour of a program that observes side effects of one thread from another thread is implementation-defined except for a few “special” side effects. (Like a volatile write, or entering a lock.) If the C# language required that all threads observe the same side effects in the same order then we would have to restrict modern processors from doing their jobs efficiently; modern processors depend on out-of-order execution and sophisticated caching strategies to obtain their high level of performance.

Those are just a few factors that come to mind; there are of course many, many other factors that language design committees debate before making a feature “implementation defined” or “undefined”.

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.

Continue reading →

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

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

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

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

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

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

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

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

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

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

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

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

Here’s a question I got from a user recently:

The foreach loop in C# uses a pattern-based approach to semantic analysis. LINQ in C# also uses a pattern-based approach. Why don’t other features, such as the using statement, also use a pattern-based approach?

Great question. First off, what do we mean by a “pattern-based approach”? Continue reading →

“Ref returns” are the subject of another great question from StackOverflow that I thought I might share with a larger audience.

Ever since C# 1.0 you’ve been able to create an “alias” to a variable by passing a “ref to a variable” to certain methods:

static void M(ref int x)
{
  x = 123;
}
  ...
  int y = 456;
  M(ref y);

Despite their different names, x and y are now aliases for each other; they both refer to the same storage location. When x is changed, y changes too because they are the same thing. Basically, “ref” parameters allow you to pass around variables as variables rather than as values. This is a sometimes-confusing feature (because it is easy to confuse “reference types” with “ref” aliases to variables,) but it is generally a pretty well-understood and frequently-used feature.

However, it is a little-known fact that the CLR type system supports additional usages of ref, though C# does not. The CLR type system also allows methods to return refs to variables, and allows local variables to be aliases for other variables. The CLR type system however does not allow for fields that are aliases to other variables. Similarly arrays may not contain managed references to other variables. Both fields and arrays containing refs are illegal because making it legal would overly complicates the garbage collection story.[1. I also note that the “managed reference to variable” types are not convertible to object, and therefore may not be used as type arguments to generic types or methods. For details, see the CLI specification Partition I Section 8.2.1.1, “Managed pointers and related types” for information about this feature. See also my numerous articles on memory management for more discussion of why C# and the CLR do not allow long-term storage of refs.]

As you might expect, it is entirely possible to create a version of C# which supports both these features. You could then do things like

static ref int Max(ref int x, ref int y)
{
  if (x > y)
    return ref x;
  else
    return ref y;
}

Why do this? It is quite different than a conventional “Max” which returns the larger of two values. This returns the larger variable itself, which can then be modified:

int a = 123;
int b = 456;
ref int c = ref Max(ref a, ref b);
c += 100;
Console.WriteLine(b); // 556!

Kinda neat! This would also mean that ref-returning methods could be the left-hand side of an assignment — we don’t need the local “c”:

int a = 123;
int b = 456;
Max(ref a, ref b) += 100;
Console.WriteLine(b); // 556!

Syntactically, ref is a strong marker that something weird is going on. Every time the keyword ref appears before a variable usage, it means “I am now making some other thing an alias for this variable”. Every time it appears before a declaration, it means “this thing must be initialized with a variable marked with ref“.

I know empirically that it is possible to build a version of C# that supports these features because I have done so in order to test-drive the possible feature. Advanced programmers (particularly people porting unmanaged C++ code) often ask us for more C++-like ability to do things with references without having to get out the big hammer of actually using pointers and pinning memory all over the place. By using managed references you get these benefits without paying the cost of screwing up your garbage collection performance.

We have considered this feature, and actually implemented enough of it to show to other internal teams to get their feedback. However at this time based on our research we believe that the feature does not have broad enough appeal or compelling usage cases to make it into a real supported mainstream language feature. We have other higher priorities and a limited amount of time and effort available, so we’re not going to do this feature any time soon.

Also, doing it properly would require some changes to the CLR. Right now the CLR treats ref-returning methods as legal but unverifiable because we do not have a detector that detects and outlaws this situation:

static ref int M1(ref int x)
{
  return ref x;
}
static ref int M2()
{
  int y = 123;
  return ref M1(ref y); // Trouble!
}
static int M3()
{
  ref int z = ref M2();
  return z;
}

M3 returns the contents of M2‘s local variable, but the lifetime of that variable has ended! It is possible to write a detector that determines uses of ref-returns that clearly do not violate stack safety. We could write such a detector, and if the detector could not prove that lifetime safety rules were met then we would not allow the usage of ref returns in that part of the program. It is not a huge amount of dev work to do so, but it is a lot of burden on the testing teams to make sure that we’ve really got all the cases. It’s just another thing that increases the cost of the feature to the point where right now the benefits do not outweigh the costs.

If we implemented this feature some day, would you use it? For what? Do you have a really good usage case that could not easily be done some other way? If so, please leave a comment. The more information we have from real customers about why they want features like this, the more likely it will make it into the product someday. It’s a cute little feature and I’d like to be able to get it to customers somehow if there is sufficient interest. However, we also know that “ref parameters” is one of the most misunderstood and confusing features, particularly for novice programmers, so we don’t necessarily want to add more confusing features to the language unless they really pay their own way.