Category Archives: Language design

Why are braces required in try-catch-finally?

Posted on by
69

Developers who use C-like languages typically conceive of if, while, for, and so on as taking either a single statement, or a group of any number of statements in a block:

if (x)
  M();
if (x)
{
  M();
  N();
}

However, that's not how programming language designers think of it. Rather, if and while and for and so on each take a single statement, and a braced block is a single statement.1

No matter how we choose to think about the grammar, it is certainly the case that try-catch-finally is different than if and while and for and so on; try-catch-finally requires a braced block. That seems inconsistent; is there a justification for this inconsistency?

Before we dig into the try-catch-finally case, let's first consider the problems with this approach. The looping structures are unambiguous:

while(A())
  while(B())
    C();

The inner while statement composes nicely with the outer while statement; no braces are required to make sense of this. But that is not the case with if, thanks to the famous "dangling else problem":

if (A())
  if (B())
    C();
else
  D();

OK, quick, is the indenting correct there? Is else D() associated with the inner if statement or the outer one?

It's associated with the inner one; the else matches the nearest containing if. But in a language where whitespace doesn't matter, it is very easy to accidentally indent this wrong and get the wrong impression when reading the code. I've also seen badly-written macros in C and C++ that caused the dangling-else problem to arise.

When adding try-catch-finally to the language, the designers wished to avoid adding a second kind of dangling else problem. Suppose that you could put any statement after a try, catch or finally, rather than having to put a block statement. How do you analyze this program fragment?

try
  try
    A();
  catch AException
    B();
catch BException
  C();

OK, quick, is the indenting correct there? Is B() protected? That is, should we parse this as

try
{
  try
  {
    A();
  }
  catch AException
  {
    B(); // protected by the outer try
  }
}
catch BException
{
  C();
}

Or is it this erroneous program?

try // try without associated catch!
{
  try
  {
    A();
  }
  catch AException
  {
    B(); // not protected
  }
  catch BException
  {
    C();
  }
}

Rather than attempt to come up with a rule to disambiguate the ambiguous parse, it is better to simply avoid the ambiguity altogether and require the braces. The last thing we need in this language is more ambiguity.

While we're on the subject, an interesting thing about the try block is that of course the try keyword is completely unnecessary from a grammatical perspective. We could simply have said that any block can be followed by any number of catch blocks or a finally block, and the block thus followed is implicitly a try block. This is a good example of how enforcing redundancy into the language makes it more readable; the try keyword calls the reader's attention to the fact that the control flow of this part of the method needs to deal with exceptional situations.

And one additional fun fact: in the initial design of C#, there was no such thing as try-catch-finally. There was try-catch and try-finally. If you wanted to have a try-catch-finally then you'd write:

try
{
  try
  {
    A();
  }
  catch AException
  {
    B();
  }
}
finally
{
  C();
}

The language designers realized that this was a common pattern and unnecessarily wordy, so they allowed the syntactic sugar of eliminating the outer try. The C# compiler actually generates the code as though you'd written the nested blocks, since at the CIL level there is no try-catch-finally.

Eric is on vacation; this posting was pre-recorded.

Next time on FAIC: What happens when unmanaged code holds on to a fixed pointer? Nothing good.

  1. C# has an additional rule that the statement in an if, while and so on may not be a single local variable declaration; that's a good subject for another day. ↩

Why is deriving a public class from an internal class illegal?

Posted on by
Reply

In C# it is illegal to declare a class D whose base class B is in any way less accessible than D. I'm occasionally asked why that is. There are a number of reasons; today I'll start with a very specific scenario and then talk about a general philosophy.

Suppose you and your coworker Alice are developing the code for assembly Foo, which you intend to be fully trusted by its users. Alice writes:

public class B
{
  public void Dangerous() {...}
}

And you write

public class D : B
{
  ... other stuff ...
}

Later, Alice gets a security review from Bob, who points out that method Dangerous could be used as a component of an attack by partially-trusted code, and who further points out that customer scenarios do not actually require B to be used directly by customers in the first place; B is actually only being used as an implementation detail of other classes. So in keeping with the principle of least privilege, Alice changes B to:

internal class B
{
  public void Dangerous() {...}
}

Alice need not change the accessibility of Dangerous, because of course public means "public to the people who can see the class in the first place".

So now what should happen when Alice recompiles before she checks in this change? The C# compiler does not know if you, the author of class D, intended method Dangerous to be accessible by a user of public class D. On the one hand, it is a public method of a base class, and so it seems like it should be accessible. On the other hand, the fact that B is internal is evidence that Dangerous is supposed to be inaccessible outside the assembly. A basic design principle of C# is that when the intention is unclear, the compiler brings this fact to your attention by failing. The compiler is identifying yet another form of the Brittle Base Class Failure, which long-time readers know has shown up in numerous places in the design of C#.

Rather than simply making this change and hoping for the best, you and Alice need to sit down and talk about whether B really is a sensible base class of D; it seems plausible that either (1) D ought to be internal also, or (2) D ought to favour composition over inheritance. Which brings us to my more general point:

More generally: the inheritance mechanism is, as we've discussed before, simply the fact that all heritable members of the base type are also members of the derived type. But the inheritance relationship semantics are intended to model the "is a kind of" relationship. It seems reasonable that if D is a kind of B, and D is accessible at a location, then B ought to be accessible at that location as well. It seems strange that you could only use the fact that "a Giraffe is a kind of Animal" at specific locations.

In short, this rule of the language encourages you to use inheritance relationships to model the business domain semantics rather than as a mechanism for code reuse.

Finally, I note that as an alternative, it is legal for a public class to implement an internal interface. In that scenario there is no danger of accidentally exposing dangerous functionality from the interface to the implementing type because of course an interface is not associated with any functionality in the first place; an interface is logically "abstract". Implementing an internal interface can be used as a mechanism that allows public components in the same assembly to communicate with each other over "back channels" that are not exposed to the public.

Dynamic contagion, part two

Posted on by
Reply

This is part two of a two-part series on dynamic contagion. Part one is here.

Last time I discussed how the dynamic type tends to spread through a program like a virus: if an expression of dynamic type "touches" another expression then that other expression often also becomes of dynamic type. Today I want to describe one of the least well understood aspects of method type inference, which also uses a contagion model when dynamic gets involved.

Long-time readers know that method type inference is one of my favourite parts of the C# language; for new readers who might not be familiar with the feature, let me briefly describe it. The idea is that when you have a method, say:

Select<A, R>(IEnumerable<A> items, Func<A, R> projection)

and a call to the method, say:

Select(customers, c=>c.Name)

then we infer that you meant to call:

Select<Customer, string>(customers, c=>c.Name)

rather than making you spell it out. In that case, we would first infer that the list of customers is an IEnumerable<Customer> and therefore the type argument corresponding to A is Customer. From that we would infer that lambda parameter c is of type Customer, and therefore the result of the lambda is string, and therefore type argument corresponding to R is string. This algorithm is already complicated, but when dynamic gets involved, it gets downright weird.

The problem that the language designers faced when deciding how method type inference works with dynamic is exacerbated by our basic design goal for dynamic, that I mentioned two weeks ago: the runtime analysis of a dynamic expression honours all the information that we deduced at compile time. We only use the deduced-at-runtime types for the parts of the expression that were actually dynamic; the parts that were statically typed at compile time remain statically typed at runtime, not dynamically typed. Above we inferred R after we knew A, but what if customers had been of type dynamic? We now have a problem: depending on the runtime type of customers, type inference might succeed dynamically even though it seems like it must fail statically. But if type inference fails statically then the method is not a candidate, and, as we discussed two weeks ago, if the candidate set of a dynamically-dispatched method group is empty then overload resolution fails at compile-time, not at runtime. So it seems that type inference must succeed statically!

What a mess. How do we get out of this predicament? The spec is surprisingly short on details; it says only:

Any type argument that does not depend directly or indirectly on an argument of type dynamic is inferred using [the usual static analysis rules]. The remaining type arguments are unknown. [...] Applicability is checked according to [the usual static analysis rules] ignoring parameters whose types are unknown.1

So what we have here is essentially another type that spreads via a contagion model, the "unknown" type. Just as "possibly infected" is the transitive closure of the exposure relation in simplistic epidemiology, "unknown" is the transitive closure of the "depends on" relation in method type inference.

For example, if we have:

void M<T, U>(T t, L<U> items)

with a call

M(123, dyn);

Then type inference infers that T is int from the first argument. Because the second argument is of dynamic type, and the formal parameter type involves type parameter U, we "taint" U with the "unknown type".

When a tainted type parameter is "fixed" to its final type argument, we ignore all other bounds that we have computed so far, even if some of the bounds are contradictory, and infer it to be "unknown". So in this case, type inference would succeed and we would add M<int, unknown> to the candidate set. As noted above, we skip applicability checking for arguments that correspond to parameters whose types are in any way tainted.

But where does the transitive closure of the dependency relationship come into it? In the C# 4 and 5 compilers we did not handle this particularly well, but in Roslyn we now actually cause the taint to spread. Suppose we have:

void M<T, U, V>(T t, L<U> items, Func<T, U, V> func)

and a call

M(123, dyn, (t, u)=>u.Whatever(t));

We infer T to be int and U to be unknown. We then say that V depends on T and U, and so infer V to be unknown as well. Therefore type inference succeeds with an inference of M<int, unknown, unknown>.

The alert reader will at this point be protesting that no matter what happens with method type inference, this is going to turn into a dynamic call, and that lambdas are not legal in dynamic calls in the first place. However, we want to get as much high-quality analysis done as possible so that IntelliSense and other code analysis works correctly even in badly broken code. It is better to allow U to infect V with the "unknown taint" and have type inference succeed, as the specification indicates, than to bail out early and have type inference fail. And besides, if by some miracle we do in the future allow lambdas to be in dynamic calls, we'll already have a sensible implementation of method type inference.

This is part two of a two-part series on dynamic contagion. Part one is here.

  1. That last clause is a bit unclear in two ways. First, it really should say "whose types are in any way unknown". L<unknown> is considered to be an unknown type. Second, along with skipping applicability checking we also skip constraint satisfaction checking. That is, we assume that the runtime construction of L<unknown> will provide a type argument that satisfies all the necessary generic type constraints. ↩

Is C# a strongly typed or a weakly typed language?

Posted on by
1

Presented as a dialogue, as is my wont!

Is C# a strongly typed or a weakly typed language?

Yes.

That is unhelpful.

I don't doubt it. Interestingly, if you rephrased the question as an "and" question, the answer would be the same.

What? You mean, is C# a strongly typed and a weakly typed language?

Yes, C# is a strongly typed language and a weakly typed language.

I'm confused.

Me too. Perhaps you should tell me precisely what you mean by "strongly typed" and "weakly typed".

Um. I don't actually know what I mean by those terms, so perhaps that is the question I should be asking. What does it really mean for a language to be "weakly typed" or "strongly typed"?

"Weakly typed" means "this language uses a type verification system that I find distasteful", and "strongly typed" means "this language uses a type system that I find attractive".

No way!

Way, dude.

Really?

These terms are meaningless and you should avoid them. Wikipedia lists eleven different meanings for "strongly typed", several of which contradict each other. Any time two people use "strongly typed" or "weakly typed" in a conversation about programming languages, odds are good that they have two subtly or grossly different meanings in their heads for those terms, and are therefore automatically talking past each other.

But surely they mean something other than "unattractive" or "attractive"!

I do exaggerate somewhat for comedic effect. So lets say: a more-strongly-typed language is one that has somerestriction in its type system that a more-weakly-typed language it is being compared to lacks. That's all you can really say without more context.

How can I have sensible conversations about languages and their type systems then?

You can provide the missing context. Instead of using "strongly typed" and "weakly typed", actually describe the restriction you mean. For example, C# is for the most part a statically typed language, because the compiler determines facts about the types of every expression. C# is for the most part a type safe language because it prevents values of one static type from being stored in variables of an incompatible type (and other similar type errors). And C# is for the most part a memory safe language because it prevents accidental access to bad memory.

Thus, someone who thinks that "strongly typed" means "the language encourages static typing, type safety and memory safety in the vast majority of normal programs" would classify C# as a "strongly typed" language. C# is certainly more strongly typed than languages that do not have these restrictions in their type systems.

But here's the thing: because C# is a pragmatic language there is a way to override all three of those safety systems. Cast operators and "dynamic" in C# 4 override compile-time type checking and replace it with runtime type checking, and "unsafe" blocks allow you to turn off type safety and memory safety should you need to. Someone who thinks that "strongly typed" means "the language absolutely positively guarantees static typing, type safety and memory safety under all circumstances" would quite rightly classify C# as "weakly typed". C# is not as strongly typed as languages that do enforce these restrictions all the time.

So which is it, strong or weak? It is impossible to say because it depends on the point of view of the speaker, it depends on what they are comparing it to, and it depends on their attitude towards various language features. It's therefore best to simply avoid these terms altogether, and speak more precisely about type system features.

Next time on FAIC: What happens when a dynamic call's method group has a single member?

Should C# warn on null dereference?

Posted on by
Reply

As you probably know, the C# compiler does flow analysis on constants for the purposes of finding unreachable code. In this method the statement with the calls is known to be unreachable, and the compiler warns about it.

const object x = null; 
void Foo() 
{
  if (x != null)
  {
     Console.WriteLine(x.GetHashCode());   
  }
}

Now suppose we removed the if statement and just had the call:

const object x = null; 
void Foo() 
{   
  Console.WriteLine(x.GetHashCode()); 
}

The compiler does not warn you that you're dereferencing null! The question is, as usual, why not?

The answer is, as usual, that the compiler team does not have to provide a justification for not doing a feature. Features cost money, time and effort, and take away money, time and effort from features that would benefit the user better; features have to be justified based on a cost-vs-benefits analysis. So let's think about that.

Something I find helpful when thinking about a particular feature is to ask "is this a specific case of a more general feature?" The proposed feature is essentially to detect that a particular exception is always going to be thrown. Do we want to in general be able to detect cases where an exception will always be thrown and warn about them? Well, doing so with certainty is equivalent to solving the Halting Problem, as we've already discussed. But even without that, we do not want to give a warning every time we know that an exception must be thrown; that would then make this program fragment produce a warning:

int M() { throw new NotImplementedException(); }

The whole point of throwing that exception in the first place is to make it clear that this part of the program doesn't work; giving a warning saying that it doesn't work is counterproductive; warnings should tell you things you don't already know.

So let's just think about the feature of detecting when a constant null is dereferenced. How often does that happen, anyway? I occasionally make null constants; perhaps because I want to be able to say things like 

if (symbol == InvalidSymbol)

where InvalidSymbol is the constant null; it makes the code read more like English. And maybe someone could accidentally say InvalidSymbol.Name and the compiler could warn them that they are dereferencing null.

We've been here before; in fact, I made a list. So let's go down it.

The feature is reasonable; the code seems plausible, it is clearly wrong, and the compiler could detect that without too much expense. However, the scope of this warning is very small; the vast majority of the time I've used null constants, I've used them for comparison, not for accessing members off of them. And the problem will be detected when we test the code, every time.

Could we perhaps then generalize the feature in a different way? Perhaps instead of constants we should detect any time that the compiler can reasonably know that any dereference is probably a null dereference. Solving the problem perfectly is, again, equivalent to solving the Halting Problem, which we know is impossible, but we can use some clever heuristics to do a good job.

In fact the C# compiler already has some of those heuristics; it uses them in its nullable arithmetic optimizer. If we can statically know that a nullable expression is always null or never null then we can do a better job of codegen. However, the existing heuristics are extremely "local"; they do not, for example, notice that a local variable was assigned null and then later used before it was reassigned. So again, the scope of this warning would be very small, probably too small.

To do a good job of the proposed more general feature, we'd want to modify the existing flow analyzer that determines if a local variable is definitely assigned before it is used, with one that also can tell you whether the value assigned was non-null before a dereference. That's a much more expensive feature; the benefits are higher, but so are the costs.

What it really comes down to me for this feature is that last item on my list. Yes, it is always better to catch a bug at compile time, but that said, null dereference bugs that the compiler could have told you about with certainty are the easiest ones to catch at runtime because they always happen the moment you test the code. So that's some points against the feature.

So basically the feature request here is to write a somewhat expensive detector that detects at compile time a somewhat unlikely condition that will always be immediately found the first time the code is run anyways. It is therefore not a great candidate for spending budget on to implement it; thus the feature has never been implemented. It's a lovely feature and I'd be happy to have it in the compiler, but it's just not big enough bang for the design, development and testing buck, and we have many higher priorities.

Now, you might note that tools like the Code Contracts feature that shipped with version 4, or Resharper, or other similar tools, all have various abilities to statically detect possible or guaranteed null dereferences. Which proves that it is possible to do a good job of this feature, and that's good to know. But that is also points against doing the warning in the compiler. As I point out on my list, if an existing analysis tool does a good job, then why replicate that work in the compiler? The compiler does not aim to be the be-all and end-all of code analysis; in fact, we are building Roslyn precisely to make it easier for third parties to develop such analysis tools. We can't possibly do every great code analysis feature, but we can make it easier for you to do so!

I am off for my annual vacation in Ontario and I have not written blog articles for the interim. We'll pick up when I get back.

Foolish consistency is foolish

Posted on by
Reply

Once again today's posting is presented as a dialogue, as is my wont.

Why is var sometimes required on an implicitly-typed local variable and sometimes illegal on an implicitly typed local variable?

That's a good question but can you make it more precise? Start by listing the situations in which an implicitly-typed local variable either must or must not use var.

Sure. An implicitly-typed local variable must be declared with var in the following statements:

var x1 = whatever; 
for(var x2 = whatever; ; ) {} 
using(var x3 = whatever) {} 
foreach(var x4 in whatever) {}

And an implicitly-typed local variable must not be declared with var in the following expressions:

from c in customers select c.Name
customers.Select(c => c.Name)

In both cases it is not legal to put var before c, though it would be legal to say:

from Customer c in customers select c.Name 
customers.Select((Customer c) => c.Name)

Why is that?

Well, let me delay answering that by criticizing your question further. In the query expression and lambda expression cases, are those in fact implicitly typed locals in the first place?

Hmm, you're right; technically neither of those cases have local variables. In the lambda case, that is a formal parameter. But a formal parameter behaves almost exactly like a local variable, so it seems reasonable to conflate the two in casual conversation. In the query expression, the compiler is going to syntactically transform the range variable into an untyped lambda formal parameter regardless of whether the range variable is typed or not.

Can you expand on that last point a bit?

Sure. When you say from Customer c in customers select c.Name that is not transformed by the compiler into customers.Select((Customer c) => c.Name) Rather, it is transformed into customers.Cast<Customer>().Select(c => c.Name)

Correct. Discussing why that is might be better left for another day.

Indeed; the point here is that regardless of whether a type appears in the query expression, the lambda expression in the transformed code is going to have an untyped formal parameter.

So now that we've clarified the situation, what is your question?

C# is inconsistent; var is required on an implicitly-typed local variable (regardless of the "container" of the local declaration), but var is illegal on an implicitly-typed lambda parameter (regardless of whether the lambda parameter is "natural" or is the result of a query expression transformation). Why is that?

You keep on asking "why?" questions, which I find difficult to answer because your question is secretly a "why not?" question. That is, the question you really mean to ask is "I have a notion of how the language obviously ought to have been designed; why is it not like that?"  But since I do not know what your notion is, it's hard to compare its pros and cons to the actual feature that you find inconsistent.

The problem you are raising is one of inconsistency; I agree that you have identified a bona fide inconsistency, and I agree that a foolish, unnecessary inconsistency is bad design. The C# language is designed to be easy to comprehend; foolish inconsistencies work against comprehensibility. But what I don't understand is how you think that inconsistency ought to have been addressed.

I can see three ways to address that inconsistency. First, make var required on lambdas and query expressions, so that it is consistently required. Second, make var illegal on all locals, so that it is consistently illegal. And third, make it optional everywhere. What is the real "why not?" question?

You're right; I've identified an inconsistency but have not described how I think that inconsistency could be removed. I don't know what my real "why not?" is so let's look at all of them; what are the pros and cons of each?

Let's start by considering the first: require var everywhere. That would then mean that you have to write:

from var c in customers 
join var o in orders...

instead of

from c in customers 
join o in orders...

And you have to write

customers.Select((var c) => c.Name)

instead of

customers.Select(c => c.Name)

This seems clunky. What function does adding var in these locations serve? It does not make the code any more readable; it makes it less readable. We have purchased consistency at a high cost here. The first option seems untenable.

Now consider the second option: make var illegal on all locals. That means that your earlier uses of var on locals would become:

x1 = whatever; 
for(x2 = whatever; ; ) {} 
using(x3 = whatever) {} 
foreach(x4 in whatever) {}

The last case presents no problem; we know that the variable declared in a foreach loop is always a new local variable. But in the other three cases we have just added a new feature to the language; we now have not just implicitly typed locals, we now have implicitly declared locals. Now all you need to do to declare a new local is to assign to an identifier you haven't used before.

There are plenty of languages with implicitly declared locals, but it seems like a very "un-C#-ish" feature. That's the sort of thing we see in languages like VB and VBScript, and even in them you have to make sure that Option Explicit is turned off. The price we pay for consistency here is very different, but it is still very high. I don't think we want to pay that price.

The third option -- make var optional everywhere-- is just a special case of the second option; again, we end up introducing implicitly declared locals.

Design is the art of compromising amongst various incompatible design goals. In this case, consistency is a goal but it loses to more practical concerns. This would be a foolish consistency.

Is the fact that there is no good way out of this inconsistency an indication that there is a deeper design problem here?

Yes. When I gave three options for removing the inconsistency, you'll notice that I made certain assumptions about what was and was not allowed to change. If we were willing to make larger changes, or if the original design team had made different decisions in C# 1.0, then we wouldn't be in this mess in the first place. The deeper design problem here is that the fact that a local variable declaration has the form

type identifier ;

This is not a great statement syntax in the first place. Suppose C# 1.0 had instead said that a local variable must be declared like this:

var identifier : type ;

I see where you are going; JScript.NET does use that syntax, and makes the type annotation clause optional. And of course Visual Basic uses the moral equivalent of that syntax, with Dim instead of var and As instead of :.

That's right. So in typing-required C# 1.0 we would have

var x1 : int = whatever; 
for(var x2 : int = whatever; ; ) {} 
using(var x3 : IDisposable = whatever) {} 
foreach(var x4 : int in whatever) {}

This is somewhat more verbose, yes. But this is very easy to parse, both by the compiler and the reader, and is probably more clear to the novice reader. It is crystal clear that a new local variable is being introduced by a statement. And it is also nicely reminiscent of base class declaration, which is a logically similar annotation.1

Then in C# 3.0 we could introduce implicitly typed locals by simply making the annotation portion optional, and allowing all of the following statements and expressions:

var x1 = whatever; 
for(var x2  = whatever; ; ) {} 
using(var x3  = whatever) {} 
foreach(var x4 in whatever) {}
from c in customers select c.Name 
from c : Customer in customers select c.Name 
customers.Select(c => c.Name) 
customers.Select((c : Customer) => c.Name)

If this syntax has nicer properties then why didn't you go with it in C# 1.0?

Because the designers wanted the syntax to be familiar to users of C and C++. So here we have one kind of consistency -- consistency of experience for C programmers -- leading a decade later to a problem of C# self-consistency.

The moral of the story is: good design requires being either impossibly far-sighted, or accepting that you're going to have to live with some small inconsistencies as a language evolves over decades.

Next time on FAIC: The best advice I ever got.

  1. You could have just as easily asked "Why does the constraining type come to the left of the identifier in a local, parameter, field, property, event, method and indexer, and to the right of the identifier in a class, struct, interface and type parameter?" Inconsistencies abound! ↩

Implementation-defined behaviour

Posted on by
Reply

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

Ref returns and ref locals

Posted on by
Reply

"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

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.

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

Never say never, part two

Posted on by
Reply

This is part two of a two-part series about determining whether the endpoint of a method is never reachable. Part one is here. A follow-up article is here.

Whether we have a "never" return type or not, we need to be able to determine when the end point of a method is unreachable for error reporting in methods that have non-void return type. The compiler is pretty clever about working that out; it can handle situations like

int M()
{
  try
  {
    while(true) N();
  }
  catch(Exception ex)
  {
    throw new WrappingException(ex);
  }
}

The compiler knows that N either throws or it doesn't, and that if it doesn't, then the try block never exits, and if it does, then either the construction of the exception throws, or the construction succeeds and the catch throws the new exception. No matter what, the end point of M is never reached.

However, the compiler is not infinitely clever. It is easy to fool it:

int M()
{
  int x = 123;
  try
  {
    while(x >= x / 2) 
      x = x / 2;
  }
  catch(Exception ex)
  {
    throw new WrappingException(ex);
  }
}

Here x is always going to be a small, non-negative integer, and a small, non-negative integer is always greater than or equal to half of it. You know that, I know that, but the compiler doesn't know that. The compiler complains that this method has a reachable end point, even though clearly the end point will never be reached. We could put that logic into the compiler if we really wanted to; we could be more clever.

How much more clever could we be? Is there any limit to our cleverness? Could we in theory produce a compiler that perfectly determined whether the end point of a method was reachable?

Turns out, no. A proof of that fact is a bit tricky, but we're tough, we can do it.

First off, let's restrict the problem to a particular pattern. Consider programs of this form:

class Program
{
  private static string data = @"some data goes here";
  public static int DoIt()
  {
    // some code goes here
  }
}

The question is "given values for 'some data' and 'some code', does DoIt have a reachable end point?" If we can't solve the problem for programs with this very restrictive format then we can't solve it in general, so let's explore whether we can solve problems in this limited format.

Let's suppose that we have a class in our compiler library with a public method that answers that question, and deduce a contradiction. We assume that "code" is a legal body of a C# program and "data" is the legal contents of a string literal.

public class Compiler
{
  public static bool HasReachableEndPoint(string code, string data)
  {
    // [Omitted: work out the result and return it]
  }
}

And now things get really weird. What if we call:

string weird = @"
  if (Compiler.HasReachableEndPoint(data, data))
    return 123;
"; 
// Recall that C# has multi-line string literals. 
// The "code" above is in the string.
bool result = Compiler.HasReachableEndPoint(weird, weird);

What does that do? It attempts to work out whether DoIt has a reachable end point in this program:

class Program
{
  private static string data = @"
    if (Compiler.HasReachableEndPoint(data, data))
    return 123;
  ";
  public static int DoIt()
  {
    if (Compiler.HasReachableEndPoint(data, data))
    return 123;
  }
}

What is the value of result? Suppose it is true. Then that means that DoIt has a reachable end point. Which means that when we run DoIt, the call in the conditional statement returns false. But data and weird refer to the same string, so why is result true if the result of the same call is going to be false? That's logically inconsistent, so result cannot be true. Clearly I cannot drink from the cup closest to me.

Suppose result is false. That means that DoIt does not have a reachable end point. Which means that Compiler.HasReachableEndPoint(data, data) always either returns true, or throws an exception, or runs forever. But again, data and weird are the same string, so why would it return true, throw, or run forever here, when by assumption it returns false normally when given that input? Clearly result is not false either, since that leads to a contradiction. Clearly I cannot drink from the cup closest to you.

Since result can logically be neither true nor false, HasReachableEndPoint must either throw or go into an infinite loop when given these inputs. But if it does that then there are some inputs for our reachability tester which cause the compiler to fail or run forever, which seems bad. The compiler needs to be able to compile all legal programs and error on all illegal programs; ideally we don't want to crash, run forever, or give a wrong answer for any possible input.

What we've shown here is, first, that you should never go up against a Sicilian when death is on the line, and second, that an endpoint reachability tester logically must either (1) sometimes give the wrong answer, or (2) sometimes fail to give an answer. The reachable endpoint problem is in general not reliably solvable by compilers no matter how clever the compiler writers are.

Now, you might reasonably push back on this proof, noting that the proof relies upon an absolutely crazy situation, namely, a program that contains part of its own code as data that itself calls the reachability analyzer in what Douglas Hofstadter calls a "strange loop". Even if you don't like the proof though, we have other evidence that a "perfect" reachable end point detector that always returns a correct result in finite time is probably impossible. Consider for example this totally trivial little method, with just five loops and some calculations on an arbitrary-precision integer type:

public static int DoIt()
{
  Integer max = 0;
  while(true)
  {
    max += 1;
    for (Integer x = 1; x <= max; ++x)
      for (Integer y = 1; y <= max; ++y)
        for (Integer z = 1; z <= max; ++z)
          for (Integer n = 1; n <= max; ++n)
            if (x.Power(n+2) + y.Power(n+2) == z.Power(n+2)) 
              goto done;
  }
  done: ;
  // Uh oh, we "forgot" to return an int.
  // But that's only a problem if the label is reachable.
}

Want to know if Fermat's Last Theorem is true? Just run your magical perfect C# compiler on a class containing that method and see if it compiles. If it fails with a "reachable end point in non-void-returning method" error then the goto must have been reachable, which means that there is a non-trivial solution to the equation, and Fermat's Last Theorem is false. If compilation succeeds (with a warning that there's an unreachable label!) then the goto was unreachable and the theorem is true. To answer the question you don't even need to run the program, you just have to run the compiler! The fact that this program is insanely inefficient in the amount of recalculation it performs is irrelevant, since we're not going to even run it.

Such a compiler would enable us to answer any open question in finite mathematics simply by writing a program that terminates if the hypothesis is true and runs forever if it is not. It seems inconceivable that we could even in theory construct a compiler that had the ability to answer all unsolved problems in the entire history of finite mathematics.

This famous problem is called the "Halting Problem" because it is usually posed for computational systems that do not have "throw an exception" as an option. The only alternatives are "halt with a result", or "go into an infinite loop".

The Halting Problem is of course solvable by heuristics provided that you can tolerate false positives. The C# compiler will cheerfully tell you if the end point of a method is absolutely guaranteed to be unreachable, but as we've seen, you can fool it into telling you that some unreachable end points are reachable. As long as it does not have false negatives (that is, sometimes tells you that the reachable end point of a method is unreachable) everything is fine.

This is part two of a two-part series about determining whether the endpoint of a method is never reachable. Part one is here. A follow-up article is here.

What's the difference? fixed versus fixed

Posted on by
Reply

I got an email the other day that began:

I have a question about fixed sized buffers in C#:

unsafe struct FixedBuffer 
{ 
  public fixed int buffer[100];

Now by declaring buffer as fixed it is not movable...

And my heart sank. This is one of those deeply unfortunate times when subtle choices made in the details of language design encourage misunderstandings.

When doing pointer arithmetic in unsafe code on a managed object, you need to make sure that the garbage collector does not move the memory you're looking at. If a collection on another thread happens while you're doing pointer arithmetic on an object, the pointer can get all messed up. Therefore, C# classifies all variables as "fixed" or "movable". If you want to do pointer arithmetic on a movable object, you can use the fixed keyword to say "this local variable contains data which the garbage collector should not move." When a collection happens, the garbage collector needs to look at all the local variables for in-flight calls (because of course, stuff that is in local variables needs to stay alive); if it sees a "fixed" local variable then it makes a note to itself to not move that memory, even if that fragments the managed heap. (This is why it is important to keep stuff fixed for as little time as possible.) So typically, we use "fixed" to mean "fixed in place".

But that's not what "fixed" means in this context; this means "the buffer in question is fixed in size to be one hundred ints" -- basically, it's the same as generating one hundred int fields in this structure.

Obviously we often use the same keyword to mean conceptually the same thing. For example, we use the keyword internal in many ways in C#, but all of them are conceptually the same. It is only ever used to mean "accessibility to some entity is restricted to only code in this assembly".

Sometimes we use the same keyword to mean two completely different things, and rely upon context for the user to figure out which meaning is intended. For example:

var results = from c in customers where c.City == "London" select c;

versus

class C<T> where T : IComparable<T>

It should be clear that where is being used in two completely different ways: to build a filter clause in a query, and to declare a type constraint on a generic type parameter.

We cause people to run into trouble when one keyword is used in two different ways but the difference is subtle, like our example above. The user's email went on to ask a whole bunch of questions which were predicated on the incorrect assumption that a fixed-in-size buffer is automatically fixed in place in memory.

Now, one could say that this is just an unfortunate confluence of terms; that "fixed in size" and "fixed in place" just happen to both use the word "fixed" in two different ways, how vexing. But the connection is deeper than that: you cannot safely access the data stored in a fixed-in-size buffer unless the container of the buffer has been fixed in place. The two concepts are actually quite strongly related in this case, but not at allthe same.

On the one hand it might have been less confusing to use two keywords, say pinned and fixed. But on the other hand, both usages of fixed are only valid in unsafe code. A key assumption of all unsafe code features is that if you are willing to use unsafe code in C#, then you are already an expert programmer who fully understands memory management in the CLR. That's why we make you write unsafe on the code; it indicates that you're turning off the safety system and you know what you're doing.

A considerable fraction of the keywords of C# are used in two or more ways: fixed, into, partial, out, in, new, delegate, where, using, class, struct, true, false, base, this, event, return and void all have at least two different meanings. Most of those are clear from the context, but at least the first three -- fixed, into and partial -- have caused enough confusion that I've gotten questions about the differences from perplexed users. I'll take a look at into and partial next.