Fabulous Adventures In Coding

A new fabulous adventure

Eric Lippert — Thu, 29 Nov 2012 15:00:00 GMT

Tomorrow, the 30th of November, 2012, is the first day of my fifth decade here on Earth, and my last day at Microsoft. (*)

I've been working at Microsoft full-time since 1996 and had two years of internships before that. Microsoft is an awesome company. We do great work here: work that changes the way people interact with information in a fundamental way. And I in particular, have had the pleasure and the privilege to work on technologies that change how developers like me get their jobs done. There is no place doing better work on the design and implementation of real-world, production-strength programming languages that ship to millions of developers.

A number of those developers read this very blog, which I've been writing for nine years now. Sharing my fabulous adventures in coding with you all has been one of the most enjoyable parts of this job. I mean to continue writing it, but unfortunately, Microsoft's (entirely sensible) policy is that only full time employees get to post to MSDN blogs. I am therefore, effective right now, moving my blog to ericlippert.com. Please subscribe to the RSS feed, which is at http://ericlippert.com/feed/. (**)

I also intend to finally start "tweeting" occasionally; if you haven't already, please follow me on Twitter where I am @ericlippert.

A number of people have asked me what motivated this decision. Of course any life decision of this magnitude has a lot of reasons behind it, but the biggest one is simply: I've been here for 40% of my entire life, I've been feeling for some time that it would be good to take on a new challenge, and an opportunity has arisen that is tailor-made to my skills and interests. I'll describe that new opportunity in the first post on my new blog. As you'll see, I am very pleased that it will still involve supporting the C# development community, just in a different way.

Were I to try to make a list of current and erstwhile coworkers to thank it would be extremely long and I would undoubtedly embarrass myself by omitting someone. I've had the opportunity to learn about programming languages and developer tools from literally hundreds of developers, testers, writers, editors, program managers, managers, mentors, architects, distinguished engineers and at least a couple of technical fellows. (***) Thank you all; I hope to continue to work with you in the future.

And thanks to you all, who have been reading this blog these past nine years. Your comments, praise and always constructive criticism have helped me learn what customers need and helped everyone here shape C# into the amazing tool it is today. I hope we can continue sharing this adventure; see you at ericlippert.com.

Eric Lippert

UPDATE: Holy goodness, the outpouring here, on the new blog, on reddit, hacker news and twitter of both well-wishing and FUD is delightful for the former and distressing for the latter.

Regarding the former: thank you all for your kind thoughts; I appreciate it very much.

To dispel some of the rumours that are floating around regarding the latter:

(1) C#, Roslyn and .NET in general are doing fine; rumours of their deaths are greatly exaggerated. I certainly would not go to work on yet another C# static analyzer if I did not think there was a bright future to all of them, and to the Microsoft ecosystem in general. The C# language is in good hands; Anders and Mads are still deeply engaged in that process, and I am just one (albeit highly visible) member of a kick-ass team of dozens of people who are building Roslyn. I am leaving it in excellent hands and in excellent shape.

(2) As I said, this was a personal decision based on many factors; the main factor was a desire to pursue a new set of challenges that use my existing skill set. I certainly was not fired, and I look forward to having a close working relationship with the C# team in the future.

And finally:

(3) The first day of my first decade was the day I was born. So tomorrow being the first day of my fifth decade makes me 40, not 50.

Thank you again for your kind thoughts.

Eric

(*) That timing is not coincidental.

(**) Since I will no longer have the ability to reply to comments, they are shut off as of now. If you have comments, please leave them on the new blog. Thanks!

(***) The most hilarious job title at Microsoft as far as I'm concerned.

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

Eric Lippert — Tue, 13 Nov 2012 17:32:26 GMT

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

It's still essential!

Eric Lippert — Fri, 09 Nov 2012 20:00:00 GMT

I am pleased to announce that Essential C# 5.0 by Mark Michaelis, and, new for this edition, yours truly, is available for pre-order now. It will be in stores in early December.

As long-time readers of this blog know, I was one of the technical editors for Essential C# 4.0 and Essential C# 3.0. Mark was kind enough to ask me if I would like to take a larger role in the process of updating the text for the new edition, which I gladly agreed to. There is no easier way to get a byline in a book than to assist with an update to a well-written series that you already know inside-out! Many thanks to Mark, as well as to Joan and everyone else at Addison-Wesley who made this process so smooth; you are all a pleasure to work with. Special thanks also to my coworker, C# specification guru Mads Torgersen, who wrote a very nice foreword for us, and to my colleague Stephen Toub who thoroughly reviewed the chapters dealing with asynchrony.

Dynamic contagion, part two

Eric Lippert — Thu, 08 Nov 2012 14:43:00 GMT

Last time I discussed how "dynamic" 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 say 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. (*)

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

Next time on Fabulous Adventures in Coding: Fabulous Adventures!

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

Dynamic contagion, part one

Eric Lippert — Mon, 05 Nov 2012 14:47:00 GMT

Suppose you're an epidemiologist modeling the potential spread of a highly infectious disease. The straightforward way to model such a series of unfortunate events is to assume that the population can be divided into three sets: the definitely infected, the definitely healthy, and the possibly infected. If a member of the healthy population encounters a member of the definitely infected or possibly infected population, then they become a member of the possibly infected population. (Or, put another way, the possibly infected population is closed transitively over the exposure relation.) A member of the possibly infected population becomes classified as either definitely healthy or definitely infected when they undergo some sort of test. And an infected person can become a healthy person by being cured.

This sort of contagion model is fairly common in the design of computer systems. For example, suppose you have a web site that takes in strings from users, stores them in a database, and serves them up to other users. Like, say, this blog, which takes in comments from you, stores them in a database, and then serves them right back up to other users. That's a Cross Site Scripting (XSS) attack waiting to happen right there. A common way to mitigate the XSS problem is to use data tainting, which uses the contagion model to identify strings that are possibly hostile. Whenever you do anything to a potentially-hostile string, like, say, concatenate it with a non-hostile string, the result is a possibly-hostile string. If the string is determined via some test to be benign, or can have its potentially hostile parts stripped out, then it becomes safe.

The "dynamic" feature in C# 4 and above has a lot in common with these sorts of contagion models. As I pointed out last time, when an argument of a call is dynamic then odds are pretty good that the compiler will classify the result of the call as dynamic as well; the taint spreads. In fact, when you use almost any operator on a dynamic expression, the result is of dynamic type, with a few exceptions. ("is" for example always returns a bool.) You can "cure" an expression to prevent it spreading dynamicism by casting it to object, or to whatever other non-dynamic type you'd like; casting dynamic to object is an identity conversion.

The way that dynamic is contagious is an emergent phenomenon of the rules for working out the types of expressions in C#. There is, however, one place where we explicitly use a contagion model inside the compiler in order to correctly work out the type of an expression that involves dynamic types: it is one of the most arcane aspects of method type inference. Next time I'll give you all the rundown on that.

A method group of one

Eric Lippert — Mon, 22 Oct 2012 13:24:00 GMT

I'm implementing the semantic analysis of dynamic expressions in Roslyn this week, so I'm fielding a lot of questions within the team on the design of the dynamic feature of C# 4. A question I get fairly frequently in this space is as follows:

public class Alpha
{
public int Foo(string x) { ... }
}
...
dynamic d = whatever;
Alpha alpha = MakeAlpha();
var result = alpha.Foo(d);

How is this analyzed? More specifically, what's the type of local result?

If the receiver (that is, alpha) of the call were of type dynamic then there would be little we could do at compile time. We'd analyze the compile-time types of the arguments and emit a dynamic call site that caused the semantic analysis to be performed at runtime, using the runtime type of the dynamic expression. But that's not the case here. We know at compile time what the type of the receiver is. One of the design principles of the C# dynamic feature is that if we have a type that is known at compile time, then at runtime the type analysis honours that. In other words, we only use the runtime type of the things that were actually dynamic; everything else we use the compile-time type. If MakeAlpha() returns a derived class of Alpha, and that derived class has more overloads of Foo, we don't care.

Because we know that we're going to be doing overload resolution on a method called Foo on an instance of type Alpha, we can do a "sanity check" at compile time to determine if we know that for sure, this is going to fail at runtime. So we do overload resolution, but instead of doing the full overload resolution algorithm (eliminate inapplicable candidates, determine the unique best applicable candidate, perform final validation of that candidate), we do a partial overload resolution algorithm. We get as far as eliminating the inapplicable candidates, and if that leaves one or more candidates then the call is bound dynamically. If it leaves zero candidates then we report an error at compile time, because we know that nothing is going to work at runtime.

Now, a seemingly reasonable question to ask at this point is: overload resolution in this case could determine that there is exactly one applicable candidate in the method group, and therefore we can determine statically that the type of result is int, so why do we instead say that the type of result is dynamic?

That appears to be a reasonable question, but think about it a bit more. If you and I and the compiler know that overload resolution is going to choose a particular method then why are we making a dynamic call in the first place? Why haven't we cast d to string? This situation is rare, unlikely, and has an easy workaround by inserting casts appropriately (either casting the call expression to int or the argument to string). Situations that are rare, unlikely and easily worked around are poor candidates for compiler optimizations. You asked for a dynamic call, so you're going to get a dynamic call.

That's reason enough to not do the proposed feature, but let's think about it a bit more deeply by exploring a variation on this scenario that I glossed over above. Eta Corporation produces:

public class Eta {}

and Zeta Corporation extends this code:

public class Zeta : Eta
{
public int Foo(string x){ ... }
}
...
dynamic d = whatever;
Zeta zeta = new Zeta();
var result = zeta.Foo(d);

Suppose we say that the type of result is int because the method group has only one member. Now suppose that in the next version, Eta Corporation supplies a new method:

public class Eta
{
public string Foo(double x){...}
}

Zeta corporation recompiles their code, and hey presto, suddenly result is of type dynamic! Why should Eta Corporation's change to the base class cause the semantic analysis of code that uses a derived class to change? This seems unexpected. C# has been carefully designed to avoid these sorts of "Brittle Base Class" failures; see my other articles on that subject for examples of how we do that.

We can make a bad situation even worse. Suppose Eta's change is instead:

public class Eta
{
protected string Foo(double x){...}
}

Now what happens? Should we say that the type of result is int when the code appears outside of class Zeta, because overload resolution produces a single applicable candidate, but dynamic when it appears inside, because overload resolution produces two such candidates? That would be quite bizarre indeed.

The proposal is simply too much cleverness in pursuit of too little value. We've been asked to perform a dynamic binding, and so we're going to perform a dynamic binding; the result should in turn be dynamic. The benefits of being able to statically deduce types of dynamic expressions does not pay for the costs, so we don't attempt to do so. If you want static analysis then don't turn it off in the first place.

Next time: the dynamic taint of method type inference.

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

Eric Lippert — Mon, 15 Oct 2012 16:26:00 GMT

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 some restriction 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.

High Altitude

Eric Lippert — Fri, 12 Oct 2012 14:38:00 GMT

No computer programming stuff today; just some fun for Friday.

As I'm writing this Felix Baumgartner's attempt to set the world record for skydiving height by diving from a helium balloon has been scrubbed due to bad weather. This attempt has got me thinking of my good friend JB, who back in 1982 set the world record (*) for hang gliding height by similarly using a helium balloon.

JB is one of those people who proves the truth of the saying that you really can do anything you put your mind to, as he's been a world-record breaking hang glider pilot, skydiver, balloonist, airplane pilot, ultra-marathon runner, shuttle astronaut candidate (**), upper-atmosphere physicist, microgravity physicist, nuclear physicist, father, and I'm probably missing a dozen more accomplishments in there. And teacher! When I was a child he taught me useful skills like how to estimate large numbers, how to do trigonometry, and how to do calculus, usually by pointing out things on the beach and then doing math in the sand, like Archimedes. How many grains of sand are on this beach? How far away is the horizon when you stand on the roof of the cottage? What shape path does this rock make in the air when you throw it? These sorts of questions fascinated me as a child, and, I suppose, still do.

Anyway, I recently learned that JB has uploaded the short film his brother Bims made to document the successful attempt at the record. Check it out, and enjoy the hairstyles of the 1980s: Project Hang Glide

(*) It's in the 1988 Guinness Book of World Records.

(**) His microgravity experiment ended up flying on the Vomit Comet rather than the shuttle.

Does Not Compute

Eric Lippert — Wed, 10 Oct 2012 13:27:00 GMT

One of the most basic ways to think about a computer program is that it is a device which takes in integers as inputs and spits out integers as outputs. The C# compiler, for example, takes in source code strings, and those source code strings are essentially nothing more than enormous binary numbers. The output of the compiler is either diagnostic text, or strings of IL and metadata, which are also just enormous binary numbers. Because the compiler is not perfect, in some rare cases it terminates abnormally with an internal error message. But those fatal error messages are also just big binary numbers. So let's take this as our basic model of a computer program: a computer program is a device that either (1) runs forever without producing output, or (2) computes a function that maps one integer to another.

So here's an interesting question: are there functions which cannot be computed, even in principle on a machine with arbitrarily much storage, by any C# program (*)?

We already know the answer to that question. Last year I pointed out that the Halting Problem is not solvable by any computer program, because the assumption that it is solvable leads to a logical contradiction. But the Halting Problem is just a function on integers. Let's say that the input of our function H is a number which when written out in binary is a Unicode string that might contain a C# program. The output is 1 if the program is an illegal C# program, 2 if it is a legal C# program which halts, and 3 if it is a legal C# program which does not halt. If it were possible to write a program that reliably computes function H and always terminates then it would be possible to use it to solve the Halting Problem, which we've shown is impossible. Therefore H is not a computable function.

Let's explore this a bit further. The "Turing Machine" model of computing is that a computer is a machine that has three kinds of storage: first, there's a fixed amount of "internal" storage that describes the current state of the processor, second, there is arbitrarily much "external" storage in the form of paper tape, disk drives, or whatever, that can contain binary data, and third, there is some way of identifying the "current position" being manipulated in the external storage. The Turing Machine also has strict rules that describe how to change the internal state, the external state, and the current position. One of the internal states is the "start" state, and one of the internal states is the "halt" state; once the machine gets to the halting state, it stops. Otherwise, it runs forever.

Without loss of generality, let's suppose that our Turing Machine's external storage is arbitrarily many bits, either zero or one, and that the internal storage is some fixed number of bits, say n. This is pretty restrictive, but we haven't actually lost anything fundamental here. Real computers of course give the appearance of manipulating storage that consists of 32 bit integers or 64 bit doubles or whatever, but at some level inside the processor, it is manipulating individual bits. There is no difference in principle between a machine that manipulates one bit at a time and a machine that manipulates 64 bits at a time; the latter is simply more convenient.

So then how many rules do we need to come up with for our Turing machine? A Turing machine with n bits of internal state has 2ⁿ possible states, and there are two possibilities for the value at the "current position" in the external state. (**) So that means that there are 2ⁿ⁺¹ state transition rules. Each transition rule will have to encode three things: (1) what are the n bits of the new internal state? (2) what value should the external state be changed to? and (3) how should we update the current position?

Again without loss of generality, we can update the current position by decreasing it by one, increasing it by one, or leaving it the same. In practice that is inconvenient, but in principle that is enough. So those are three possibilities. Thus, each state transition rule is one of 2 x 2ⁿ x 3 possibilities. There are 2ⁿ⁺¹ state transition rules. Therefore the total number of possible Turing Machines that have n bits of internal storage is 3 x 2ⁿ⁺¹ raised to the 2ⁿ⁺¹power, which, yes, grows pretty quickly as n gets large, but which is clearly a finite number.

Each one of these n-bit Turing Machines essentially computes a function. You start it up with the external storage in a particular state and the machine either runs forever, or after some finite number of steps it halts. If it halts, then the output of the function is the value left behind in the external storage.

Again without loss of generality, let's consider the value computed by each one of those possible Turning machines when the external storage is initially all zeros. When given that starting configuration, each of those Turing machines either runs for some number of steps and then halts with the result, or it runs forever. Let's ignore the ones that run forever. Of the ones that are left, the ones that terminate, one of them must run the longest (***). That is, one of those machines that halts must have the largest number of steps taken before entering the halting state.

We therefore can come up with a function S that goes from integers to integers. The function S takes in n, the number of bits in the Turing Machine internal state, and gives you back the largest number of steps any of the possible n-bit Turing Machines that halts takes to halt. That is, S takes in the number of bits of internal storage and gives you back the amount of time you have to wait for the slowest of the n-bit machines that actually terminates, when it is started with empty external storage.

Is S a computable function? Can we write a computer program that computes it?

Your intuition should be telling you "no", but do you see why?

Because if S were computable then H would be computable too! All we'd have to do to compute H is to make a computer program that compiles a given C# program into a Turing Machine simulator that starts with an empty tape. We take the number of bits of state, n, of that Turing Machine, and compute S(n). Then we run the Turing Machine simulator and if it takes more than S(n) steps then we know that it must have been one of the n-bit Turing machines that runs forever. We'd then be able to reliably compute H in finite time. Since we already know that H is not reliably computable in finite time then we know that S must not be computable either.

The argument that I'm advancing here is known as the "Busy Beaver" argument because the n-bit Turing Machine that runs the longest is the "busiest beaver". I've tweaked the way that it is usually presented; rather than the n-bit Turing Machine that runs the longest before terminating, the "busiest beaver" is traditionally defined as the k-state Turing Machine that produces the largest output. The two characterizations are essentially equivalent though; neither version of the function is computable.

An interesting fact about the busy beaver function (either way you characterize it) is that the function grows enormously fast. It's easy to think of functions that grow quickly; even simple functions like n! or 2ⁿ grow to astronomical levels for relatively small values of n, like 100. But our busiest beaver function S(n) grows faster than any computable function. That is, think of a function that grows quickly where you could write a program to compute its value in finite time; the busiest beaver function grows faster than your function, no matter how clever you are in coming up with a fast-growing function. Do you see why? You've got all the information you need here to work it out. (****)

(*) Of course, there is nothing special about C#; it is a general-purpose programming language. We'll take as given that if there is a function that cannot be computed in C# then that function cannot be computed by any program in any programming language.

(**) Of course, we don't need to state transitions from the halting state, but, whatever. We'll ignore that unimportant detail.

(***) Of course, there could be a tie for longest, but that doesn't matter.

(****) Of course, even if the busiest beaver function did not grow absurdly quickly, the fact that it clearly grows more than exponentially is evidence that our proposed technique for solving the Halting Problem would be impractical were it not impossible. Compiling a non-trivial C# program to a Turing Machine simulator would undoubtedly produce a machine with more than, say, 100 bits of state. There are an enormous number of possible Turing Machines with 100 bits of internal state, and the one that runs the longest before it halts undoubtedly runs longer than the universe will last.

How do we ensure that method type inference terminates?

Eric Lippert — Tue, 02 Oct 2012 16:48:31 GMT

I missed the party. I was all set to be on that massive wave of announcements about TypeScript, and then a family emergency kept me away from computers from Thursday of last week until just now, and I did not get my article in the queue. Suffice to say that I am SUPER EXCITED about TypeScript. Long-time readers of this blog know that I have a long history with ECMAScript, and I've wanted features like this for quite some time. Since I've missed the first wave I'm going to digest some of the initial reactions and hopefully post something a bit more thoughtful farther down the road.

Therefore, rather than talking about TypeScript today, here's a question I got from a coworker recently: since it is obviously important that the C# compiler not go into infinite loops, how do we ensure that the method type inference algorithm terminates?

The answer is quite straightforward actually, but if you are not familiar with method type inference then this article is going to make no sense. Check out my type inference archive, and specifically this video, if you need a refresher.

Method type inference since C# 3.0 basically works like this: we create a set of bounds on each method type parameter. We then "fix" each type parameter to a member of its bounds set. Once every type parameter is fixed, method type inference has succeeded. If any type parameter cannot be fixed for some reason then type inference fails. We ensure that type inference terminates by going into a loop. If we manage to make it through the body of the loop without fixing at least one type parameter then type inference fails. Therefore, the type inference loop can run at most n times if the method has n type parameters.

That's a bit highfalutin; let me flesh that out a bit. A "bound" is nothing more than a type, and a bound can be "upper", "lower" or "exact". For example, suppose we have a type parameter T with three bounds: a lower bound of Giraffe, an exact bound of Mammal, and an upper bound of Animal. Let's say that Animal is a "larger" type than Mammal (because all Mammals are Animals but not all Animals are Mammals, thus Animal must be the larger type), and Giraffe is a "smaller" type than Mammal. Given this set of bounds we know that T must be inferred to be first, either Giraffe or a type larger than Giraffe, because Giraffe is a lower bound; you can't infer a type smaller than Giraffe. Second, we know that T must be Mammal, exactly. And third, we know that T must be either Animal or a type smaller than Animal, because Animal is an upper bound. We cannot infer a type larger than Animal. The C# compiler deduces that Mammal is the only type in the set that meets all three requirements, and so T would be fixed to Mammal. If there are multiple types in the set that meet all the requirements (which of course cannot happen if there are any exact bounds!) then we pick the largest such type. (*)

The interesting part of method type inference is how we deal with lambdas. Suppose we have a method Select<A, R>(I<A>, Func<A, R>) where the second argument is c=>c.Name. We say that A is an "input" type parameter and R is an "output" type parameter. (It is of course possible for a type parameter to be both an input and output type parameter!) Furthermore, we say that R "depends on" A, because the type of A could possibly determine the type of R. (Of course the "depends" relationship can be cyclic.)

The type inference algorithm, at a high level, goes like this:

Add bounds to type parameters based on all non-lambda arguments, and all lambda arguments where the delegate type has no type parameters in its inputs.
Loop
- Is every type parameter fixed?
  - Type inference has succeeded. Terminate the algorithm.
- Is there any lambda argument converted to a delegate type where the inputs of the delegate type are all known and the output type involves an unfixed type parameter?
  - Deduce the return type of all such lambdas and make inferences that add bounds to the corresponding delegate's output types.
- Is there any unfixed, bounded type parameter that does not appear in an output type of a delegate that has unfixed input types?
  - Fix all such type parameters and go back to the top of the loop.
- Is there any unfixed, bounded type parameter such that an unfixed type parameter depends on it, directly or indirectly?
  - Fix all such type parameters and go back to the top of the loop.
- If we make it here then we failed to make progress; we have just as many fixed type parameters as we started with. Type inference fails. Terminate the algorithm.

So, for example, if we had Select(customers, c=>c.Name); where customers implements I<Customer> then we start by inferring that A has a lower bound of Customer (**). We have no lambda arguments that correspond to formal parameters where the delegate type has no type parameters in its inputs, so we enter the loop.

Is every type parameter fixed? No.

Is there any lambda argument converted to a delegate type where the inputs are known and the output involves an unfixed type parameter?

No. There is a lambda argument converted to a delegate type, and the output involves unfixed type parameter R, but the input type is A and A is not fixed. So we have no inferences to make.

Is there an unfixed type parameter that has bounds and does not appear in an output type of a delegate that has unfixed input types?

Yes. A has bounds and does not appear as an output type, period.

Therefore we fix A. It has only one bound, Customer, so we fix it to Customer. We have made progress, so we go back to the top of the loop.

Is every type parameter fixed? No.

Is there any lambda argument converted to a delegate type where the inputs are known and the output involves an unfixed type parameter? Yes!

So now we make an inference. A is fixed to Customer, so we add the type of Customer.Name, say, string, as a lower bound to R.

Now we must fix something. Is there an unfixed type parameter that has bounds and does not appear in an output type of a delegate that has unfixed input types?

Yes. R is unfixed, it has bounds, and it appears as an output type of a delegate that has fixed input types, so it is a candidate for fixing. We fix R to its only bound, string, and start the loop again.

Is every type parameter fixed? Yes. So we're done.

This technique of preventing infinite loops by requiring that each loop iteration make progress is quite useful, and clearly in this case it guarantees that the algorithm executes the loop no more times than there are type parameters to fix.

You might wonder if it is therefore the case that method type inference is O(n) in the number of type parameters. It turns out that it is not, for several reasons. First, as a practical matter it only makes sense to determine the asymptotic order of an algorithm if the size of the problem is likely to become large. I've never seen a method with more than five type parameters in the wild, and even that is pretty unusual. Most generic methods have one or two type parameters. Second, doing the analysis of the lambdas is the expensive part, and it only really makes sense to analyze the behaviour of the most expensive part. We already know that analyzing lambdas is, worst case, an NP-HARD problem so whether or not method type inference is O(some polynomial) is possibly not that relevant. Third, you'll notice that in my sketch of the algorithm we have to answer questions like "is there any unfixed type parameter that has an unfixed type parameter that depends on it?" This requires solving a graph-traversal problem, whose asymptotic cost we have not analyzed! I won't take you through the boring analysis, but suffice to say there could be O(n²) dependency relationships that each cost O(n) to analyze, and we could go through the loop n times, for an extremely unlikely worst case of O(n⁴). The implementation of this algorithm is actually O(n²) in the common case; because n is likely to be small, as I said, we have not put the effort into more sophisticated algorithms that can solve these graph problems even faster in the asymptotic case.

(*) Note that this algorithm is consistent with other type inference features in C# in two ways. First, when asked to infer a best type from a set of types, we always choose a type from the set. We never say "well we have Dog and Cat in the set so let's infer Mammal". Second, when faced with multiple possible "best" types, we pick the largest. There is an argument to be made for picking the smallest, but picking the largest seems to match more people's intuitions of what the right choice is.

(**) Assuming that the type I<T> is covariant in T. If it were contravariant then we would deduce an upper bound, and if it were invariant then we would deduce an exact bound. See my series on variance if that is not clear.

Roslyn September 2012 CTP is now available

Eric Lippert — Mon, 17 Sep 2012 18:58:15 GMT

I am super excited to announce that we have just released a third "Community Technology Preview" of Roslyn. Roslyn, in case you have not heard, is the code name for the project I work on; we are re-architecting the C# and VB compilers so that they are no longer "black boxes" where code goes in, a miracle happens, and then IL comes out. Rather, the box is now glass and you can use the lexical, syntactic and semantic analysis engines that we write for your own purposes.

We have implemented semantic analysis of most of the C# and VB language features now. On the C# side we are through most of the C# 3 features; we still lack "dynamic" from C# 4 and "await" from the recently-released C# 5. We've also made many changes (hopefully all improvements) to the APIs. For a complete list of the updates, to access the Roslyn question-and-answer forum, or to download it and try it for yourself, go to msdn.com/roslyn.

We would love to get your feedback on the forum or on connect.microsoft.com/visualstudio about what you do and do not like about the APIs; that's why we do these technology previews so often. (Please leave feedback on the forum rather than as a comment to this blog; we have a team of program managers who read the forums.) I hope you enjoy this latest CTP; we enjoyed building it.

Static analysis of "is"

Eric Lippert — Wed, 12 Sep 2012 18:10:00 GMT

Before I get into the subject of today's fabulous adventure, I want to congratulate the whole rest of Developer Division on the tremendously exciting product that we are formally launching today. (I've done very little actual coding on Visual Studio 2012 and C# 5.0, being busy with the long-lead Roslyn project.) Asynchronous programming support in C# and VB is of course my favourite feature; there are far, far too many new features to mention here. Check out the launch site, and please do send us constructive feedback on what you do and do not like. We cannot respond in detail to all of it, but it is all appreciated.

Returning now to the subject we started discussing last time on FAIC: sometimes the compiler can know via "static" analysis (that is, analysis done knowing only the compile-time types of expressions, rather than knowing their possibly more specific run-time types) that an "is" operator is guaranteed to produce a particular result.

But before we get into that, let's briefly review the meaning of "is" in C#. The expression

x is T

for an expression x and a type T produces a bool. Generally speaking, if there is a reference, boxing or unboxing conversion from the runtime value of x to the type T then the result is true, otherwise the result is false. Note that in particular user-defined conversions are not considered. The intention of the operator is to determine if the runtime value of x is actually a useful value of the type T, (*) and therefore we add a few additional caveats:

T may not be a pointer type
x may not be a lambda or anonymous method
if x is classified as a method group or is the null literal (**) then the result is false
if the runtime type of x is a reference type and its value is a null reference then the result is false
if the runtime type of x is a nullable value type and the HasValue property of its value is false then the result is false
if the runtime type of x is a nullable value type and the HasValue property of its value is true then the result is computed as though you were checking x.Value is T

So, knowing that, try to think of some situations in which you know for certain that "x is T" is going to always produce true, or always produce false. Here are a few that you and I know are always true:

int i = 123;
bool b1 = i is int;
bool b2 = i is IComparable;
bool b3 = i is object;
bool b4 = "hello" is string;

Here in every case we know first, that the operand is not null, and second, that the operand will always be of the given type, and therefore the operator will always produce "true".

Before we go on, another aside! I want to briefly review our criteria for when to make a warning: the warning in question has got to be (1) thought of, (2) possible to implement cheaply, (3) identify code that is both plausibly written by a real user and almost certainly wrong, but non-obviously wrong (4) be work-around-able should the code actually be correct and (5) not turn huge amounts of existing code into spurious errors.

Of these four lines, only the third strikes me as plausibly written by a real user and almost certainly wrong; the user must not realize that every int always implements IComparable. The other ones are just weird. Interestingly enough, the C# 5 compiler warns about the first three, but not the fourth.

There are a lot more situations where you know that the result will always be false. Can you think of some? Here are just a few off the top of my head:

bool b5 = M is Func<object>; // M is a method group
bool b6 = null is object;
bool b7 = b5 is IEnumerable;
bool b8 = E.Blah is uint; // E is an enum type
bool b9 = i is double;

The first two follow the rules of the spec. The latter three are cases where we can know via static analysis that the value cannot possibly be converted to the given type by a reference, boxing or unboxing conversion. We produce a warning for all these trivially-analyzed cases. (Though of course again some of these examples -- b6 in particular -- are unlikely to show up in real code.)

That was a whole lot of preamble to the question I actually want to consider today, which is "how far should we go?" when making these sorts of static analyses for the purpose of warning that an "is" expression is always false. We could go a lot farther! I started this series off with a puzzle about the cases where there is no compile-time conversion from x to T, but nevertheless "x is T" can be true; today I want to talk about what we do when there is no compile-time conversion from x to T, and hey, x is T really cannot possibly be true as a result. There are lots of cases where you and I know that a given expression will never be of a given type, but these cases can get quite complex. Let's look at three complex ones:

class C<T> {}
...
static bool M10<X>(X x) where X : struct { return x is string; }
static bool M11<X>(C<X> cx) where X : struct { return cx is C<string>; }
static bool M12<X>(Dictionary<int, int> d) { return d is List<X>; }

In case M10 we know that X will always be a value type and no value type is convertible to string via a reference, boxing or unboxing conversion. The type check must be false.

In case M11 we know that cx is of type C<some-value-type>, or a type derived from C<some-value-type>. You and I know that there is no way to get the same generic class type into a type hierarchy twice; there is no way to make something derive from both C<some-value-type> and C<string>. So the type check must be false.

In case M12 we know that there is no way to make an object that inherits from both the dictionary and list base classes, no matter what X is. The type check must be false.

In all these cases we could produce a compiler warning, but we are rapidly running up against the "possible to implement cheaply" criterion! I could spend a lot of expensive time coming up with heuristics which would not make a difference to real users writing real code. We have to draw the line somewhere.

Where is that line? The heuristic we actually use to determine whether or not to report a warning when we detect that there is no compile-time conversion from x to T is as follows:

If neither the compile time type of x nor the type T is an open type (that is, a type that involves generic type parameters) then we know that the result will always be false. There's no conversion, and nothing to substitute at runtime to make there be a conversion. Give a warning.
One of the types is open. If the compile time type of x is a value type and T is a class type then we know that the result will always be false (***). (This is case M10 above.) We give a warning.
Otherwise, give up on further analysis and do not produce a warning.

This is far from perfect, but it is definitely in the "good enough" bucket. And "good enough" is, by definition, good enough. Of course, this heuristic is subject to change without notice, should we discover that some real user-impacting scenario motivates changing it.

(*) And not to determine the answers to other interesting questions, like "is there any way to associate a value of type T with this value?" or "can the value x be legally assigned to a variable of type T?"

(**) There are some small spec holes here and around these holes are minor inconsistencies between the C# 5 compiler and Roslyn. We do not say what to do if the expression x is a namespace or a type; those are of course valid expressions. The compiler produces an error stating that an expression with a value is expected. Similarly for write-only properties and write-only indexers. The C# 5 compiler produces an error if the expression is a void-returning call, which technically is a spec violation; Roslyn produces a warning, though frankly, I'd be more inclined to change the spec in this case. The specification does say that "x is T" is an error if T is a static type; the C# 5 compiler erroneously allows this and produces false whereas the Roslyn compiler produces an error.

(***) This is a lie; there is one case where the compile time type of x is an open value type and T is a class type, and there is no compile-time conversion from x to T, and "x is T" can be true, and therefore the warning must be suppressed. Can you write a program that demonstrates this scenario?

An "is" operator puzzle, part two

Eric Lippert — Mon, 27 Aug 2012 16:59:56 GMT

As I said last time, that was a pretty easy puzzle: either FooBar, or the type of local variable x, can be a type parameter. That is:

void M<FooBar>()
{
int x = 0;
bool b = x is FooBar; // legal, true if FooBar is int.
FooBar fb = (FooBar)x; // illegal
}

struct FooBar { /* ... */ }
void M<X>()
{
X x = default(X);
bool b = x is FooBar; // legal, true if X is FooBar
FooBar fb = (FooBar)x; // illegal
}

This not only illustrates an interesting fact about "is" -- that an "is" expression can result in true even if the corresponding cast would be illegal -- but also an interesting fact about casts. Generally speaking, a cast is allowed if the conversion either is know at compile time to always succeed, or possibly succeed. But in these cases we have a situation where the cast could possibly succeed but is still illegal. What's up with that? There are two main factors that come to mind, based on the dual nature of casts that I've mentioned before: a cast can mean "I know that this value is of the given type, even though the compiler does not know that, the compiler should allow it", and a cast can mean "I know that this value is not of the given type; generate special-purpose, type-specific code to convert a value of one type to a value of a different type."

But neither of these things are logical when type parameters are involved. In the context of the first meaning, a cast between a type parameter and a regular type essentially means "I know that the type parameter supplied is of the given type." But in that case, why do you have a type parameter in the first place? It's like having an integer formal parameter and then asserting that it is always twelve. Why did you have the parameter at all if you know ahead of time what the argument will be?

And in the context of the second meaning, in generic code we have no way to generate the special-purpose conversion logic. Let's take our first example code, above. If FooBar is double then we have to generate different code for int-to-double than if FooBar is long. We don't have a cheap and easy way to generate that code, and if user-defined conversions are involved then we need to do overload resolution at runtime. We added that feature to C# 4; if you want to generate fresh code at runtime that can do arbitrary conversions, use dynamic.

Next time: we'll explore the question "under what circumstances will the "is" operator give a warning at compile time stating that the "is" is unnecessary?"

Fabulous Adventures In Casting

Eric Lippert — Mon, 27 Aug 2012 15:47:46 GMT

I've written a lot about casting over the years in this blog, but always in the context of the "cast operator": the operator that instructs the compiler to make an explicit conversion from a value of one type to a value of another type. I have recently taken up a new hobby that is casting of an entirely different sort: the casting of molten metal into a mold made of sand to form a desired shape.

I have no experience whatsoever with any kind of metalworking, so I'm learning as I go here and making mistakes along the way. I'm going to document the results of these experiments on my new blog, Fabulous Adventures In Casting. If this subject interests you, check it out!

We now return to our regularly scheduled discussion of the "is" operator in C#.

An "is" operator puzzle, part one

Eric Lippert — Thu, 23 Aug 2012 17:12:00 GMT

It is possible for a program with some local variable x:

bool b = x is FooBar;

to assign true to b at runtime, even though there is no conversion, implicit or explicit, from x to FooBar allowed by the compiler! That is,

FooBar foobar = (FooBar)x;

would not be allowed by the compiler in that same program.

Can you create a program to demonstrate this fact? This is not a particularly hard puzzle but it does illustrate some of the subtleties of the "is" operator that we'll discuss in the next episode.

Wackiness ensues

Eric Lippert — Fri, 17 Aug 2012 16:48:58 GMT

No tech today, but this is too funny to not pass along, so consider this your fun for Friday.

What would happen if Anders Hejlsberg and Barbara Liskov were forced to share an apartment in an "odd couple" sitcom? (*)

Apparently I'm the "Kramer" of this sitcom. I hope I'm played by Ryan Gosling. Additional suggestions on casting the principal roles can be left in the comments.

(*) A single-threaded apartment, I'd assume.

Out parameters and LINQ do not mix

Eric Lippert — Tue, 14 Aug 2012 19:05:19 GMT

I am back from my annual vacation in beautiful southwestern Ontario; before I get into the subject of today's post, check out this shot I took with my Windows Phone camera from the plane on the trip home. We are at 37000 feet, just outside of Billings, Montana, a few minutes before sunset:

The whole thing was chock full of immense lightning arcs which unfortunately I did not capture in the image. This is certainly the largest isolated thunderstorm I've ever seen from the outside. Notice the characteristic anvil shape; as I've described before, we've got a huge heat engine here that is extracting the latent heat from the gaseous and liquid water, and then using that heat to power the updraft that sucks more warm water vapor upwards. Quite beautiful.

Well, enough chit-chat about the weather. Today: what's wrong with this code?

var seq = new List<string> { "1", "blah", "3" };
int tmp;
var nums =
from item in seq
let success = int.TryParse(item, out tmp)
select success ? tmp : 0;

The intention is pretty clear: take a sequence of strings and produce a sequence of numbers by turning the elements that can be parsed as numbers into those numbers and the rest into zero.

The C# compiler will give you a definite assignment error if you try this, which seems strange. Why does it do that? Well, think about what code the compiler will translate the last statement into:

var nums =
seq.Select(item=>new {item, success = int.TryParse(item, out tmp)})
.Select(transparent => transparent.success ? tmp : 0);

We have two method calls and two lambdas. Clearly the first lambda assigns tmp and the second reads it, but we have no guarantee whatsoever that the first call to Select invokes the lambda! It could, for some bizarre reason of its own, never invoke the lambda. Since the compiler cannot prove that tmp is definitely assigned before it is read, this program is an error.

So is the solution then to assign tmp in the variable declaration? Certainly not! That makes the program compile, but it is a "worst practice" to mutate a variable like this. Remember, that one variable is going to be shared by every delegate invocation! In this simple LINQ-to-Objects scenario it is the case that the delegates are invoked in the sensible order, but even a small change makes this nice property go out the window:

int tmp = 0;
var nums =
from item in seq
let success = int.TryParse(item, out tmp)
orderby item
select success ? tmp : 0;
foreach(var num in nums) { Console.WriteLine(num); }

Now what happens?

We make an object that represents the query. The query object consists of three steps: do the "let" projection, do the sort, and do the final projection. Remember, the query is not executed until the first result from it is requested; the assignment to "nums" just produces an object that represents the query, not the results.

Then we execute the query by entering the body of the loop. Doing so initiates a whole chain of events, but clearly it must be the case that the entire "let" projection is executed from start to finish over the whole sequence in order to get the resulting pairs to be sorted by the "orderby" clause. Executing the "let" projection lambda three times causes "tmp" to be mutated three times. Only after the sort is completed is the final projection executed, and it uses the current value of tmp, not the value that tmp was back in the distant past!

So what is the right thing to do here? The solution is to write your own extension method version of TryParse the way it would have been written had there been nullable value types available in the first place:

static int? MyTryParse(this string item)
{
    int tmp;
    bool success = int.TryParse(item, out tmp);
    return success ? (int?)tmp : (int?)null;
}

And now we can say:

var nums =
from item in seq
select item.MyTryParse() ?? 0;

The mutation of the variable is now isolated to the activation of the method, rather than a side effect that is observed by the query. Try to always avoid side effects in queries.

Thanks to Bill Wagner for the question that inspired this blog entry.

Should C# warn on null dereference?

Eric Lippert — Tue, 17 Jul 2012 16:25:40 GMT

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 we do 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, so 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 we 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. (And how we do so would be a great future blog topic.) 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!

When is a cast not a cast?

Eric Lippert — Tue, 10 Jul 2012 16:01:32 GMT

I'm asked a lot of questions about conversion logic in C#, which is not that surprising. Conversions are common, and the rules are pretty complicated. Here's some code I was asked about recently; I've stripped it down to its essence for clarity:

class C<T> {}
class D
{
public static C M(C<bool> c)
{
return something;
}
}
public static class X
{
public static V Cast<V>(object obj) { return (V)obj; }
}

where there are three possible texts for "something":

Version 1: (C)c
Version 2: X.Cast<C>(c);
Version 3: (C)(object)c

Version 1 fails at compile time. Versions 2 and 3 succeed at compile time, and then fail at runtime if U is not bool.

Question: Why does the first version fail at compile time?

Because the compiler knows that the only way this conversion could possibly succeed is if U is bool, but U can be anything! The compiler assumes that most of the time U is not going to be constructed with bool, and therefore this code is almost certainly an error, and the compiler is bringing that fact to your attention.

Question: Then why does the second version succeed at compile time?

Because the compiler has no idea that a method named X.Cast<V> is going to perform a cast to V! All the compiler sees is a call to a method that takes an object, and you've given it an object, so the compiler's work is done. The method is a "black box" from the caller's perspective; the compiler does not look inside that box to see whether the mechanisms in that box are likely to fail given the input. This "cast" is not really a cast from the compiler's perspective, it's a method call.

Question: So what about the third version? Why does it not fail like the first version?

This one is actually the same thing as the second version; all we've done is inlined the call to X.Cast<V>, including the intermediate conversion to object! That conversion is relevant.

Question: In both the second and third cases, the conversion succeeds at compile time because there is a conversion to object in the middle?

That's right. The rule is: if there is a conversion from a type S to object, then there is an explicit conversion from object to S. (*)

By making a conversion to object before doing the "offensive" conversion, you are basically telling the compiler "please throw away the compile-time information you have about the type of the thing I am converting". In the third version we do so explicitly; in the second version we do so sneakily, by making an implicit conversion to object when the argument is converted to the parameter type.

Question: So this explains why compile-time type checking doesn't seem to work quite right on LINQ expressions?

Yes! You would think that the compiler would disallow nonsense like:

from bool b in new int[] { 123, 345 } select b.ToString();

because obviously there is no conversion from int to bool, so how can range variable b take on the values in the array? Nevertheless, this succeeds because the compiler translates this to

(new int[] { 123, 345 }).Cast<bool>().Select(b=>b.ToString())

and the compiler has no idea that passing a sequence of integers to the extension method Cast<bool> is going to fail at runtime. That method is a black box. You and I know that it is going to perform a cast, and that the cast is going to fail, but the compiler does not know that.

And maybe we do not actually know it either; perhaps we are using some library other than the default LINQ-to-objects query provider that does know how to make conversions between types that the C# language would not normally allow. This is actually an extensibility feature masquerading as a compiler deficiency: it's not a bug, it's a feature!

(*) You'll note that I did not say "there is an explicit conversion from object to every type", because there isn't. Can you think of a type S that cannot be converted to object?

The Best Advice I Ever Got

Eric Lippert — Wed, 27 Jun 2012 20:08:52 GMT

Just a quick link today:

The super nice people over at InformIT (*) are running a series of short articles with the theme "the best advice I ever got", which I think should prove to be an interesting series. They were kind enough to ask me to give an example of some good advice I got that helped my programming career, though as you'll see it is not actually about programming at all.

(*) You may recall that they also recently asked me for my advice on good books for C# programmers. In the interests of full disclosure, I note that in my spare time I write and edit C# programming books for Addison-Wesley, which is owned by the same company that owns InformIT.

Foolish consistency is foolish

Eric Lippert — Mon, 25 Jun 2012 17:18:00 GMT

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. Our 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 we had made different design 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. (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!)

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 we wanted 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.

Eric Rambles On About C#, Again

Eric Lippert — Thu, 21 Jun 2012 15:51:40 GMT

Rachel Roumeliotis, who amongst other things edits C# books for O'Reilly, recently did an interview with me where I ramble on about async/await, Roslyn, performance analysis as an engineering discipline, and some broad-strokes ideas for future language research areas. If you have sixteen minutes to burn, check it out! The O'Reilly Radar blog post is here, and the video has also been posted to YouTube here.

A couple things to mention here; first, I say in the video that we've shipped one preview release of Roslyn; in fact we have shipped two. The video was recorded before we had announced the new release. And second, I want to re-emphasize that the end bit where you get more of Eric's musings about ideas for future language research areas are for your entertainment. We have not announced any product beyond Roslyn, and we are certainly making no promises whatsoever about the feature sets of unannounced, entirely hypothetical products. Enjoy!

Implementation-defined behaviour

Eric Lippert — Mon, 18 Jun 2012 17:30:03 GMT

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 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. You will always get a call to SelectMany out of the first syntax, and never a call to Join. 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".

Persistence, Facades and Roslyn's Red-Green Trees

Eric Lippert — Fri, 08 Jun 2012 19:00:50 GMT

We decided early in the Roslyn design process that the primary data structure that developers would use when analyzing code via Roslyn is the syntax tree. And thus one of the hardest parts of the early Roslyn design was figuring out how we were going to implement syntax tree nodes, and what information they would proffer up to the user. We would like to have a data structure that has the following characteristics:

Immutable.
The form of a tree.
Cheap access to parent nodes from child nodes.
Possible to map from a node in the tree to a character offset in the text.
Persistent.

By persistence I mean the ability to reuse most of the existing nodes in the tree when an edit is made to the text buffer. Since the nodes are immutable, there's no barrier to reusing them, as I've discussed many times on this blog. We need this for performance; we cannot be re-parsing huge wodges of text every time you hit a key. We need to re-lex and re-parse only the portions of the tree that were affected by the edit (*), because we are potentially re-doing this analysis between every keystroke.

When you try to put all five of those things into one data structure you immediately run into problems:

How do you build a tree node in the first place? The parent and the child both refer to each other, and are immutable, so which one gets built first?
Supposing you manage to solve that problem: how do you make it persistent? You cannot re-use a child node in a different parent because that would involve telling the child that it has a new parent. But the child is immutable.
Supposing you manage to solve that problem: when you insert a new character into the edit buffer, the absolute position of every node that is mapped to a position after that point changes. This makes it very difficult to make a persistent data structure, because any edit can change the spans of most of the nodes!

But on the Roslyn team we routinely do impossible things. We actually do the impossible by keeping two parse trees. The "green" tree is immutable, persistent, has no parent references, is built "bottom-up", and every node tracks its width but not its absolute position. When an edit happens we rebuild only the portions of the green tree that were affected by the edit, which is typically about O(log n) of the total parse nodes in the tree.

The "red" tree is an immutable facade that is built around the green tree; it is built "top-down" on demand and thrown away on every edit. It computes parent references by manufacturing them on demand as you descend through the tree from the top. It manufactures absolute positions by computing them from the widths, again, as you descend.

You, the consumer of the Roslyn API, only ever see the red tree; the green tree is an implementation detail. (And if you use the debugger to peer into the internal state of a parse node you'll in fact see that there is a reference to another parse node in there of a different type; that's the green tree node.)

Incidentally, these are called "red/green trees" because those were the whiteboard marker colours we used to draw the data structure in the design meeting. There's no other meaning to the colours.

The benefit of this strategy is that we get all those great things: immutability, persistence, parent references, and so on. The cost is that this system is complex and can consume a lot of memory if the "red" facades get large. We are at present doing experiments to see if we can reduce some of the costs without losing the benefits.

(*) Determining what those portions of the tree are is quite tricky; I might blog about that at a later date. An edit that, for example, adds "async" to a method can cause the parse of "await(foo);" in the method body to change from an invocation to a usage of the await contextual keyword.

Announcing Microsoft Roslyn June 2012 CTP

Eric Lippert — Tue, 05 Jun 2012 19:55:00 GMT

Good afternoon all, I am happy to announce that we are releasing a second Community Technology Preview release of Roslyn, the project I actually work on, today. I am super excited!

So, let's cut to the chase. Key facts:

Roslyn is a library of code analysis APIs useful for building compilers, development environments, refactoring engines and so on. It supports lexical, grammatical and semantic analysis of C# and Visual Basic. And it is awesome.
This version of the CTP works well with the Visual Studio 2012 Release Candidate that was recently made available for download.
The C# semantic analysis engine now supports most, but not all, the C# language features. In particular, query expressions, anonymous types, anonymous functions and iterator blocks are now supported. The largest not-yet-implemented features are the "dynamic" feature from C# 4 and the "await" feature from C# 5. Nullable arithmetic mostly works but the code we generate is non-optimal; I haven't had time to write an optimizer yet.
We are giving you this sneak peek in order to get your feedback on the API design and related features such as the interactive window. Please post any comments you have to the Roslyn forum, and not to this blog. We have a team of awesome program managers who are gathering feedback from the forums and using it to help us tune the APIs to be as useful as possible for you all. We'll certainly take bug reports, but constructive feedback on the APIs is what we are going for here.
For a longer overview of this release, see Jason's blog post. You can get all the details and download the CTP from msdn.com/roslyn.