When you override a virtual method in C# you are required to ensure that the stated accessibility of the overridden method – that is, whether it is public, internal, protected or protected internal(*) – is exactly re-stated in the overriding method. Except in one case. I refer you to section 10.6.4 of the specification, which states:

an override declaration cannot change the accessibility of the virtual method. However, if the overridden base method is protected internal and it is declared in a different assembly than the assembly containing the override method then the override method’s declared accessibility must be protected.

What the heck is up with that? Surely if an overridden method is protected internal then it only makes sense that the overriding method should be exactly the same: protected internal.

I’ll explain why we have this rule, but first, a brief digression.

A certain island is inhabited by only knights and knaves. Knights make only true statements and only answer questions truthfully; knaves make only false statements and only answer questions untruthfully. If you walk up to an inhabitant of the (aptly-named) Island of Knights and Knaves you can rapidly ascertain whether a particular individual is a knight or a knave by asking a question you know the answer to. For example “does two plus two equal four?” A knight will answer “yes” (**), and a knave will answer “no”. Knaves are prone to saying things like “my mother is a male knight”, which is plainly false.

It might seem at first glance that there is no statement which could be made by both a knight and a knave. Since knights tell the truth and knaves lie, they cannot both make the same statement, right? But in fact there are many statements that can be made by both. Can you think of one?

.

.

.

.

.

.

.

Both a knight and a knave can say “I am a knight.”

How does that work? The reason this works is because the pronoun “I” refers to different people when uttered by different people. If Alice, a knight, makes the statement “I am a knight”, she is asserting the truth that “Alice is a knight”. If Bob, a knave, makes the statement “I am a knight”, he is not asserting the true statement “Alice is a knight” but rather the false statement “Bob is a knight”. Similarly, both Alice and Bob can assert the statement “My name is Alice,” for the same reason.

And that’s why overriding methods in a different assembly aren’t “protected internal”. The modifier “internal” is like a pronoun; it refers to the current assembly. When used in two different assemblies it means different things. The purpose of the rule is to ensure that a derived class does not make the accessibility domain of the virtual member any larger or smaller.

An analogy might help. Suppose a protected resource is a car, an assembly is a dwelling, a person is a class and descendent is a derived class.

• Alice has a Mazda and lives in House with her good friend Charlie.
• Charlie has a child, Diana, who lives in Apartment.
• Alice has a child, Elroy, who lives in Condo with his good friend Greg.
• Elroy has a child – Alice’s grandchild — Frank, who lives in Yurt.

Alice grants access to Mazda to anyone living in House and any descendent of Alice. The people who can access Mazda are Alice, Charlie, Elroy, and Frank.

Diana does not get access to Mazda because she is not Alice, not a descendent of Alice, and not a resident of House. That she is a child of Alice’s housemate is irrelevant.

Greg does not get access to Mazda for the same reason: he is not Alice, not a descendent of Alice, and not a resident of House. That he is a housemate of a descendent of Alice is irrelevant.

Now we come to the crux of the matter. Elroy is not allowed to extend his access to Mazda to Greg. Alice owns that Mazda and she said “myself, my descendents and my housemates”. Her children don’t have the right to extend the accessibility of Mazda beyond what she initially set up. Nor may Elroy deny access to Frank; as a descendent of Alice, Frank has a right to borrow the car and Greg cannot stop him by making it “private”.

When Elroy describes what access he has to Mazda he is only allowed to say “I grant access to this to myself and my descendents” because that is what Alice already allowed. He cannot say “I grant access to Mazda to myself, my descendents and to the other residents of Condo”.

(*) Private virtual methods are illegal in C#, which irks me to no end. I would totally use that feature if we had it.

(**) Assuming that they answer at all, of course; there could be mute knights and knaves.

I’ve written a lot about this already, but I think one particular point bears repeating.

As we’re getting closer to shipping C# 4.0, I’m seeing a lot of documents, blogs, and so on, attempting to explain what “covariant” means. This is a tricky word to define in a way that is actually meaningful to people who haven’t already got degrees in category theory, but it can be done. And I think it’s important to avoid defining a word to mean something other than its actual meaning.

A number of those documents have led with something like:

“Covariance is the ability to assign an expression of a more specific type to a variable of a less specific type. For example, consider a method M that returns a Giraffe. You can assign the result of M to a variable of type Animal, because Animal is a less specific type that is compatible with Giraffe. Methods in C# are ‘covariant’ in their return types, which is why when you create a covariant interface, it is indicated with the keyword ‘out’ — the returned value comes ‘out’ of the method.”

But that’s not at all what covariance means. That’s describing “assignment compatibility” — the ability to assign a value of a more specific type to a storage of a compatible, less specific type is called “assignment compatibility” because the two types are compatible for the purposes of verifying legality of assignments.

So what does covariance mean then?

First off, we need to work out precisely what the adjective “covariant” applies to. I’m going to get more formal for a bit here but try to keep it understandable.

Let’s start by not even considering types. Let’s think about integers. (And here I am speaking of actual mathematical integers, not of the weird behaviour of 32-bit integers in unchecked contexts.) Specifically, we’re going to think about the ≤ relation on integers, the “less than or equal to” relation. (Recall that of course a “relation” is a function which takes two things and returns a bool which indicates whether the given relationship holds or does not hold.)

Now let’s think about a projection on integers. What is a projection? A projection is a function which takes a single integer and returns a new integer. So, for example, z → z + z is a projection; call it D for “double”.  So are z → 0 - z, call it N for “negate” and z → z * z, call it S for “square”.

Now, here’s an interesting question. Is it always the case that (x ≤ y) = (D(x) ≤ D(y))?  Yes, it is. If x is less than y, then twice x is less than twice y. If x is equal to y then twice x is equal to twice y. And if x is greater than y, then twice x is greater than twice y. The projection D preserves the direction of the comparison.

What about N? Is it always the case that (x ≤ y) = (N(x) ≤ N(y))?  Clearly not. 1 ≤ 2 is true, but -1 ≤ -2 is false.

But we notice that the reverse is always true!  (x ≤ y) = (N(y) ≤ N(x)). The projection N reverses the direction of the comparison.

What about S? Is it always the case that (x ≤ y) = (S(x) ≤ S(y))? No. -1 ≤ 0 is true, but S(-1) ≤ S(0) is false.

What about the opposite? Is it always the case that (x ≤ y) = (S(y) ≤ S(x)) ?

Again, no. 1 ≤ 2 is true, but S(2) ≤ S(1) is false.

The projection S does not preserve the direction of the comparison relation, and nor does it reverse it.

The projection D is “covariant” — it preserves the ordering relationship on integers. The projection N is “contravariant”. It reverses the ordering relationship on integers. The projection S does neither; it is “invariant”.

Now I hope it is more clear exactly what is covariant or contravariant. The integers themselves are not variant, and the comparison is not variant. It’s the projection that is covariant or contravariant with respect to the comparison.

So now let us abandon integers and think about reference types. Instead of the ≤ relation on integers, we have the ≤ relation on reference types. A reference type X is smaller than (or equal to) a reference type Y if a value of type X can be stored in a variable of type Y. That is, if X is “assignment compatible” with Y.

Now consider a projection from types to types. Say, the projection “T goes to IEnumerable<T>“.  That is, we have a projection that takes a type, say, Giraffe, and gives you back a new type, IEnumerable<Giraffe>. Is that projection covariant in C# 4 (with respect to assignment compatibility)?  Yes. It preserves the direction of ordering. A Giraffe may be assigned to a variable of type Animal, and a sequence of Giraffes may be assigned to a variable that can hold a sequence of Animals.

We can think of generic types as “blueprints” that produce constructed types. Let’s take the projection that takes a type T and produces IEnumerable<T> and simply call that projection “IEnumerable<T>“. We can understand from context when we say “IEnumerable<T> is covariant” what we mean is “the projection which takes a reference type T and produces a reference type IEnumerable<T> is a covariant projection on the assignment compatibility relation”. And since IEnumerable<T> only has one type parameter, it is clear from the context that we mean that the parameter to the projection is T. After all, it is a lot shorter to say “IEnumerable<T> is covariant” than that other mouthful.

So now we can define covariance, contravariance and invariance. A generic type I<T> is covariant (in T) if construction with reference type arguments preserves the direction of assignment compatibility. It is contravariant (in T) if it reverses the direction of assignment compatibility. And it is invariant if it does neither. And by that, we simply are saying in a concise way that the projection which takes a T and produces I<T> is a covariant/contravariant/invariant projection.

 UPDATE: My close personal friend (and fellow computer geek) Jen notes that in the Twilight series of novels, the so-called “werewolves” (who are not transformed by the full moon and therefore not actually werewolves) maintain their rigid social ordering in both wolf and human form; the projection from human to wolf is covariant in the social-ordering relation. She also notes that in high school, programming language geeks are at the bottom of the social order, but the projection to adulthood catapults them to the top of the social order, and therefore, growing up is contravariant. I am somewhat skeptical of the latter claim; the former, I’ll take your word for it. I suppose the question of how social order works amongst teenage werewolves who are computer geeks is a subject for additional research. Thanks Jen!

Original post.

The original post of this article is archived here.

IMPORTANT NOTE FROM 2023: the C# rules regarding overload resolution of static members have changed since this article was written in 2009; it is accurate for C# 1 through 5, but this rule was changed in a more recent version; I do not offhand recall which. This article should be considered to be of historical interest; see more recent documentation for the current behaviour.

Pop quiz: What does the following code do when compiled and run?

class C
{
  public static void M(string x)
  {
    System.Console.WriteLine("static M(string)");
  }
  public void M(object s)
  {
    System.Console.WriteLine("M(object)");
  }
}
class Program
{
  static void Main()
  {
    C c = new C();
    c.M("hello");
  }
}

(1) writes static M(string)
(2) writes M(object)
(3) uh, dude, this code doesn’t even compile much less run
(4) something else

Think about that for a bit and then try it and see if you were right. Scroll down when you’re ready.

.

.

.

.

.

.

.

In option (1), the compiler could decide that the best match is the static one and let you call it through the instance, ignoring the instance value. In option (2), the compiler could decide that the object version is the best match and ignore the static one, even though the argument match is better. But neither of those actually happens; the rules of C# say that the compiler should pick the best match based on the arguments, and then disallow static calls that are through an instance! The actual result here is therefore (3):

error CS0176: Member 'C.M(string)' cannot be accessed with an instance reference; qualify it with a type name instead

What is up with this craziness? If you believe that the rule “static methods should never be accessed through instances” is a good rule – and it seems reasonable – then why doesn’t overload resolution remove the static methods from the candidate set when called through an instance? Why does it even allow the “string” version to be an applicable candidate in the first place, if the compiler knows that it can never possibly work?

I agree that this seems really goofy at first.

To explain why this is not quite as dumb as it seems, consider the following variation on the problem. Class C stays the same.

class B
{
  public C C = new C();
  public void N()
  {
    C.M("hello");
  }
}

What does a call to N on an instance of B do?

(1) writes static M(string)
(2) writes M(object)
(3) compilation error
(4) something else

Again, scroll down when you’ve decided.

.

.

.

.

.

.

A bit trickier now, isn’t it? Does C.M mean “call instance method M on the instance stored in this.C?” or does it mean “call static method M on type C”? Both are applicable!

Because of our goofy rule we do the right thing in this case. We first resolve the call based solely on the arguments and determine that the static method is the best match. Then we check to see if the “receiver” at the call site can be interpreted as being through the type. It can. So we make the static call and write “static M(string)”. If the instance version had been the best match then we would successfully call the instance method through the property.

The reason that the compiler does not remove static methods when calling through an instance is because the compiler does not necessarily know that you are calling through an instance. Because there are situations where it is ambiguous whether you’re calling through an instance or a type, we defer deciding which you meant until the best method has been selected.

Now, one could make the argument that in our first case, the receiver cannot possibly be a type. We could have further complicated the language semantics by having three overload resolution rules, one for when the receiver is known to be a type, one for when the receiver is known to not be a type, and one for when the receiver might or might not be a type. But rather than complicate the language further, we made the pragmatic choice of simply deferring the staticness check until after the bestness check. That’s not perfect but it is good enough for most cases and it solves the common problem.

The common problem is the situation that arises when you have a property of a type with the same name, and then try to call either a static method on the type, or an instance method on the property. (This can also happen with locals and fields, but local and field names typically differ in case from the names of their types.) The canonical motivating example is a public property named Color of type Color, so we call this “the Color Color problem”.

In real situations the instance and static methods typically have different names, so in the typical scenario you never end up calling an instance method when you expect to call a static method, or vice versa. The case I presented today with a name collision between a static and an instance method is relatively rare.

If you’re interested in reading the exact rules for how the compiler deals with the Color Color problem, see section 7.5.4.1 of the C# 3.0 specification.

A number of people have asked me why there is no Microsoft-provided ForEach sequence operator extension method. The List<T> class has such a method already of course, but there’s no reason why such a method could not be created as an extension method for all sequences. It’s practically a one-liner:

public static void ForEach<T>(
  this IEnumerable<T> sequence, 
  Action<T> action)
{
  // argument null checking omitted
  foreach(T item in sequence) 
    action(item);
}

My usual response to “why is feature X not implemented?” is that of course as Raymond Chen said “Features start out nonexistent and somebody has to make them happen.” All features are unimplemented until someone designs, implements, tests, documents and ships the feature, and no one has yet spent the money to do so in this case.

It’s not much money though. Yes, though I have famously pointed out that even small features can have large costs, this one really is dead easy, obviously correct, easy to test, and easy to document. Cost is always a factor of course, but the costs for this one really are quite small.

Of course, that cuts the other way too. If it is so cheap and easy, then you can do it yourself if you need it. And really what matters is not the low cost, but rather the net benefit. As we’ll see, I think the benefits are also very small, and therefore the net benefit might in fact be negative. But we can go a bit deeper here. I am philosophically opposed to providing such a method, for two reasons.

The first reason is that doing so violates the functional programming principles that all the other sequence operators are based upon. Clearly the sole purpose of a call to this method is to cause side effects. The purpose of an expression is to compute a value, not to cause a side effect. The purpose of a statement is to cause a side effect. The call site of this thing would look an awful lot like an expression (though, admittedly, since the method is void-returning, the expression could only be used in a “statement expression” context.) It does not sit well with me to make the one and only sequence operator that is only useful for its side effects.

The second reason is that doing so adds zero new representational power to the language. Doing this lets you rewrite this perfectly clear code:

foreach(Foo foo in foos){ statement involving foo; }

into this code:

foos.ForEach((Foo foo)=>{ statement involving foo; });

which uses almost exactly the same characters in slightly different order. And yet the second version is harder to understand, harder to debug, and introduces closure semantics, thereby potentially changing object lifetimes in subtle ways.

When we provide two subtly different ways to do exactly the same thing, we produce confusion in the industry, we make it harder for people to read each other’s code, and so on. Sometimes the benefit added by having two different textual representations for one operation (like query comprehensions versus their underlying method call form, or + versus String.Concat) is so huge that it’s worth the potential confusion. But the compelling benefit of query expressions is their readability; this new form of foreach is certainly no more readable than the normal form and is arguably worse.

If you don’t agree with these philosophical objections and find practical value in this pattern, by all means, go ahead and write this trivial one-liner yourself.

Notes from 2020

This episode was, oddly enough, one of the more controversial things I’ve posted on this blog; it sparked a lot of comments and a lot of inbound links from people arguing about the points raised here. Some of the points made in the comments to the original were:

• The ForEach method does exist on lists, as I noted. Is there anything different about lists than sequences which makes it better on lists? My answer was that I found it still distasteful on lists, but with lists at least we can make the argument that lists are intended to be a mutable data structure, so maybe it makes more sense to have a method designed to have a side effect operating on a mutable data structure? But that’s a pretty weak argument because of course you’re still not supposed to mutate a list while you are iterating it!
• A commenter pointed out that the list implementation of the ForEach method iterates by index in a for loop; ironically it does not use a foreach.
• A ForEach extension method is allegedly more readable at the end of a long chain of sequence operators than a foreach statement is at the top.
• A ForEach extension method that introduces different semantics than regular foreach would have a clear benefit — like AsParallel().ForEach() does. Good point, though of course that is a sharp tool.
• You could make the extension method non-void by both causing a side effect on each element and then yielding it. There are usages for such a thing; in particular I have used that method for “dump this sequence to the debugger display”. It’s nice to be able to insert a debugging hook like that into the middle of a long chain of sequence operators that is going wrong. But I would still feel icky about putting it into production code.

A number of people have asked me, in the wake of my earlier posting about value types being on the stack, why it is that value types go on the stack but reference types do not.

The short answer is “because they can”. And since the stack is cheap, we do put them on the stack when possible.

The long answer is… long.

I’ll need to give a high-level description of the memory management strategies that we call “stack” and “heap”. Heap first.

The CLRs garbage-collected heap is a marvel of engineering with a huge amount of detail; this sketch is not actually how it works, but it’s a good enough approximation to get the idea.

The idea is that there is a large block of memory reserved for instances of reference types. This block of memory can have “holes” – some of the memory is associated with “live” objects, and some of the memory is free for use by newly created objects. Ideally though we want to have all the allocated memory bunched together and a large section of “free” memory at the top.

If we’re in that situation when new memory is allocated then the “high water mark” is bumped up, eating up some of the previously “free” portion of the block. The newly-reserved memory is then usable for the reference type instance that has just been allocated. That is extremely cheap; just a single pointer move, plus zeroing out the newly reserved memory if necessary.

If we have holes then we can maintain a “free list” – a linked list of holes. We can then search the free list for a hole of appropriate size and fill it in. This is a bit more expensive since there is a list search. We want to avoid this suboptimal situation if possible.

When a garbage collection is performed there are three phases: mark, sweep and compact. In the “mark” phase, we assume that everything in the heap is “dead”. The CLR knows what objects were “guaranteed alive” when the collection started, so those guys are marked as alive. Everything they refer to is marked as alive, and so on, until the transitive closure of live objects are all marked. In the “sweep” phase, all the dead objects are turned into holes. In the “compact” phase, the block is reorganized so that it is one contiguous block of live memory, free of holes.

This sketch is complicated by the fact that there are actually three such arenas; the CLR collector is generational. Objects start off in the “short lived” heap. If they survive they eventually move to the “medium lived” heap, and if they survive there long enough, they move to the “long lived” heap. The GC runs very often on the short lived heap and very seldom on the long lived heap; the idea is that we do not want to have the expense of constantly re-checking a long-lived object to see if it is still alive. But we also want short-lived objects to be reclaimed swiftly.

The GC has a huge amount of carefully tuned policy that ensures high performance; it attempts to balance the memory and time costs of having a Swiss-cheesed heap against the high cost of the compaction phase. Extremely large objects are stored in a special heap that has different compaction policy. And so on. I don’t know all the details, and fortunately, I don’t need to. (And of course, I have left out lots of additional complexity that is not germane to this article – pinning and finalization and weak refs and so on.)

Now compare this to the stack. The stack is like the heap in that it is a big block of memory with a “high water mark”. But what makes it a “stack” is that the memory on the bottom of the stack always lives longer than the memory on the top of the stack; the stack is strictly ordered. The objects that are going to die first are on the top, the objects that are going to die last are on the bottom. And with that guarantee, we know that the stack will never have holes, and therefore will not need compacting. We know that the stack memory will always be “freed” from the top, and therefore do not need a free list. We know that anything low-down on the stack is guaranteed alive, and so we do not need to mark or sweep.

On a stack, the allocation is just a single pointer move – the same as the best (and typical) case on the heap. But because of all those guarantees, the deallocation is also a single pointer move! And that is where the huge time performance savings is. A lot of people seem to think that heap allocation is expensive and stack allocation is cheap. They are actually about the same, typically. It’s the deallocation costs – the marking and sweeping and compacting and moving memory from generation to generation – that are massive for heap memory compared to stack memory.

Clearly it is better to use a stack than a GC heap if you can. When can you? Only when you can guarantee that all the necessary conditional that make a stack work are actually achieved. Local variables and formal parameters of value type are the sweet spot that achieve that. The locals of frames on the bottom of the stack clearly live longer than the locals on the frames of the top of the stack. Locals of value type are copied by value, not by reference, so the local is the only thing that references the memory; there is no need to track who is referencing a particular value to determine its lifetime. And the only way to take a ref to a local is to pass it as a ref or out parameter, which just passes the ref on up the stack. The local is going to be alive anyway, so the fact that there is a ref to it “higher up” the call stack doesn’t change its lifetime.

A few asides:

• This explains why you cannot make a “ref int” field. If you could then you could store a ref to the value of a short-lived local inside a long-lived object. Were that legal then using the stack as a memory management technique would no longer be a viable optimization; value types would be just another kind of reference type and would have to be garbage collected.

• Anonymous function closures and iterator block closures are implemented behind-the-scenes by turning locals and formal parameters into fields. So now you know why it is illegal to capture a ref or out formal parameter in an anonymous function or iterator block; doing so would not be a legal field.

Of course we do not want to have ugly and bizarre rules in the language like “you can close over any local or value parameter but not a ref or out parameter”. But because we want to be able to get the optimization of putting value types on the stack, we have chosen to put this odd restriction into the language. Design is, as always, the art of finding compromises.

• Finally, the CLR does allow “ref return types”; you could in theory have a method “ref int M() { … }” that returned a reference to an integer variable. If for some bizarre reason we ever decided to allow that in C#, we’d have to fix up the compiler and verifier so that they ensured that it was only possible to return refs to variables that were known to be on the heap, or known to be “lower down” on the stack than the callee. (NOTE FROM 2021: This feature was added to C# 7.)

So there you go. Local variables of value type go on the stack because they can. They can because (1) “normal” locals have strict ordering of lifetime, and (2) value types are always copied by value and (3) it is illegal to store a reference to a local anywhere that could live longer than the local. By contrast, reference types have a lifetime based on the number of living references, are copied by reference, and those references can be stored anywhere. The additional flexibility that reference types give you comes at the cost of a much more complex and expensive garbage collection strategy.

But again, all of this is an implementation detail. Using the stack for locals of value type is just an optimization that the CLR performs on your behalf. The relevant feature of value types is that they have the semantics of being copied by value, not that sometimes their deallocation can be optimized by the runtime.

I blogged a while back about how “references” are often described as “addresses” when describing the semantics of the C# memory model. Though that’s arguably correct, it’s also arguably an implementation detail rather than an important eternal truth. Another memory-model implementation detail I often see presented as a fact is “value types are allocated on the stack”. I often see it because of course, that’s what our documentation says.

Almost every article I see that describes the difference between value types and reference types explains in (frequently incorrect) detail about what “the stack” is and how the major difference between value types and reference types is that value types go on the stack. I’m sure you can find dozens of examples by searching the web.

I find this characterization of a value type based on its implementation details rather than its observable characteristics to be both confusing and unfortunate. Surely the most relevant fact about value types is not the implementation detail of how they are allocated, but rather the by-design semantic meaning of “value type”, namely that they are always copied “by value”. If the relevant thing was their allocation details then we’d have called them “heap types” and “stack types”. But that’s not relevant most of the time. Most of the time the relevant thing is their copying and identity semantics.

I regret that the documentation does not focus on what is most relevant; by focusing on a largely irrelevant implementation detail, we enlarge the importance of that implementation detail and obscure the importance of what makes a value type semantically useful. I dearly wish that all those articles explaining what “the stack” is would instead spend time explaining what exactly “copied by value” means and how misunderstanding or misusing “copy by value” can cause bugs.

Of course, the simplistic statement I described is not even true. As the MSDN documentation correctly notes, value types are allocated on the stack sometimes. For example, the memory for an integer field in a class type is part of the class instance’s memory, which is allocated on the heap. A local variable is hoisted to be implemented as a field of a hidden class if the local is an outer variable used by an anonymous method(*) so again, the storage associated with that local variable will be on the heap if it is of value type.

But more generally, again we have an explanation that doesn’t actually explain anything. Leaving performance considerations aside, what possible difference does it make to the developer whether the CLR’s jitter happens to allocate memory for a particular local variable by adding some integer to the pointer that we call “the stack pointer” or adding the same integer to the pointer that we call “the top of the GC heap”? As long as the implementation maintains the semantics guaranteed by the specification, it can choose any strategy it likes for generating efficient code.

Heck, there’s no requirement that the operating system that the CLI is implemented on top of provide a per-thread one-meg array called “the stack”. That Windows typically does so, and that this one-meg array is an efficient place to store small amounts of short-lived data is great, but it’s not a requirement that an operating system provide such a structure, or that the jitter use it. The jitter could choose to put every local “on the heap” and live with the performance cost of doing so, as long as the value type semantics were maintained.

Even worse though is the frequently-seen characterization that value types are “small and fast” and reference types are “big and slow”. Indeed, value types that can be jitted to code that allocates off the stack are extremely fast to both allocate and deallocate. Large structures heap-allocated structures like arrays of value type are also pretty fast, particularly if you need them initialized to the default state of the value type. And there is some memory overhead to ref types. And there are some high-profile cases where value types give a big perf win. But in the vast majority of programs out there, local variable allocations and deallocations are not going to be the performance bottleneck.

Making the nano-optimization of making a type that really should be a ref type into a value type for a few nanoseconds of perf gain is probably not worth it. I would only be making that choice if profiling data showed that there was a large, real-world-customer-impacting performance problem directly mitigated by using value types. Absent such data, I’d always make the choice of value type vs reference type based on whether the type is semantically representing a value or semantically a reference to something.

(*) Or in an iterator block.

A problem statement:

I am trying to loop though a sequence of strings. How can I determine when I am on the last item in a sequence? I don’t see how to do it with foreach.

Indeed, foreach does not make it easy to know when you are almost done. Now, if I were foolish enough to actually answer the question as stated, I’d probably say something like this:

You can do so by eschewing foreach and rolling your own loop code that talks directly to the enumerator:

IEnumerable<string> items = GetStrings();
IEnumerator<string> enumtor = items.GetEnumerator();
if (enumtor.MoveNext())
{
  string current = enumtor.Current;
  while(true)
  {
    if (enumtor.MoveNext())
    {
      // current is not the last item in the sequence.  
      DoSomething(current); 
      current = enumtor.Current;
    }
    else
    {
      // current is the last item in the sequence. 
      DoSomethingElse(current); 
      break;
    }
  }
}
else
{
    // handle case where sequence was empty
}

Yuck. This is horrid. A fairly deep nesting level, some duplicated code, the mechanisms of iteration overwhelm any semantic meaning in the code, and it all makes my eyes hurt.

When faced with a question like that, rather than writing this horrid code I’ll usually push back and ask “why do you want to know?”

I am trying to walk though a sequence of strings and build a string like “a,b,c,d”.  After each item I want to place a comma except not after the last item. So I need to know when I’m on the last item.

Well knowing that certainly makes the problem a whole lot easier to solve, doesn’t it? A whole bunch of techniques come to mind when given the real problem to solve:

First technique: find an off-the-shelf part that does what you want.

In this case, call the ToArray extension method on the sequence and then pass the whole thing to String.Join and you’re done.

Second technique: Do more work than you need, and then undo some of it.

Using a string builder, to build up the result, put a comma after every item. Then “back up” when you’re done and remove the last comma (if there were any items in the sequence, of course).

Third technique: re-state the problem and see if that makes it any easier.

Consider this equivalent statement of the problem:

I am trying to walk though a sequence of strings and build a string like “a,b,c,d”. Before each item I want to place a comma except not before the first item. So I need to know when I’m on the first item.

Suddenly the problem is much simpler. It’s easy to tell if you’re on the first item in a sequence by just setting an “at the first item” flag outside the foreach loop and clearing it after going through the loop.

When I have a coding problem to solve and it looks like I’m about to write a bunch of really gross code to do so, it’s helpful to take a step back and ask myself “Could I state the problem in an equivalent but different way?” I’ll try to state a problem that I’ve been thinking about iteratively in a recursive form, or vice versa. Or I’ll try to find formalizations that express the problem in mathematical terms. (For example, the method type inference algorithm can be characterized as a graph theory problem where type parameters are nodes and dependency relationships are edges.) Often by doing so I find that the new statement of the problem corresponds more directly to clear code.

Commentary from 2020

I should have anticipated when writing this that commenters would not focus on the general point I was making — that reformulating a specific problem can lead to a more elegant solution — but would rather get nerd sniped into solving the specific problem. I mean, it was 2009. I had read the comments to Jeff’s 2007 article on FizzBuzz, and I knew that, as Jeff said “it’s amusing to me that any reference to a programming problem immediately prompts developers to feverishly begin posting solutions.”

Unsurprisingly, the comments to this article were mostly alternative solutions for the comma-separated string problem, and then critiques of those solutions. I embraced this in my follow-up post, Comma Quibbling, where I explicitly solicited solutions to a harder version of the problem.

A selection of the solutions left in comments and some critiques is below.

Note that at the time this was written, string.Join did not take a sequence, it took an array. My preferred solution suggested by a reader would be to write your own extension method that has the pleasant interface you want:

public static string Join(
  this IEnumerable<string> source, string separator)
{
  return String.Join(separator, source.ToArray());
}

But I usually go one step farther and write something like:

public static string Comma(this IEnumerable<string> source)
{
  return source.Join(",");
}

Other solutions that were suggested and critiqued:

list.Aggregate((x, y) => x + "," + y) is a Schelmiel solution.

list.Skip(1).Aggregate(
  new StringBuilder().Append(list.First()),
  (buf, e) => buf.Append(",").Append(e),
  buf => buf.ToString());

is a non-Schlemiel solution that builds an iterator twice, which is considered inelegant.

This terrible solution calls a potentially linear count method twice on every iteration and is a Schlemiel solution:

string newString = string.Empty;
for (int i = 0; i < items.Count(); i++)
   newString += items[i] + (i == items.Count() - 1 ? string.Empty : ",");

If we know that the items are not empty strings, which seems reasonable, then we can use the length of the accumulated buffer as a “not first” flag:

StringBuilder sb = new StringBuilder();
foreach (var item in items)
{
 if (sb.Length > 0)
   sb.Append(",");
 sb.Append(item);
}

We can also avoid a flag entirely by doing an extra empty-string append:

StringBuilder sb = new StringBuilder();
String comma = "";
foreach(item in list) {
 sb.Add(comma);
 sb.Add(item);
 comma = ",";
}

A number of commenters pointed out that this problem becomes much easier in languages where lists are typically in head::tail form rather than arrays; one commenter even went so far as to implement an immutable stack in their comment! (I know how to write an immutable stack but thanks for the effort.) I’m not sure why this fact is relevant.

One commenter stated that the best solution is to treat the comma as coming before every item but the first, not after every item but the last, and gave a solution for that. The same commenter then pointed out in a follow-up comment that he had written the comment before reading the entire post. Since the title of the piece is “restating the problem” I suspect that this commenter also did not read the title before banging out a solution.

My favourite comment though was a link to Jon Skeet’s 2007 article where he solves the more general problem in an elegant way. If you want to enumerate a sequence and do something different if you are on the first or last item, just make an interface that provides that information. We are computer programmers; making abstractions that solve the stated problem is what we do.

[NOTE: Based on some insightful comments I have updated this article to describe more clearly the relationships between references, pointers and addresses. Thanks to those who commented.]

I review a fair number of C# books; in all of them of course the author attempts to explain the difference between reference types and value types. Unfortunately, most of them do so by saying something like “a variable of reference type stores the address of the object“. I always object to this. The last time this happened the author asked me for a more detailed explanation of why I always object, which I shall share with you now:

We have the abstract concept of “a reference”. If I were to write about “Beethoven’s Ninth Symphony”, those two-dozen characters are not a 90-minute long symphonic masterwork with a large choral section. They’re a reference to that thing, not the thing itself. And this reference itself contains references — the word “Beethoven” is not a long-dead famously deaf Romantic Period composer, but it is a reference to one.

Similarly in programming languages we have the concept of “a reference” distinct from “the referent”.

The inventor of the C programming language, oddly enough, chose to not have the concept of references at all. Rather, Ritchie chose to have “pointers” be first-class entities in the language. A pointer in C is like a reference in that it refers to some data by tracking its location, but there are more smarts in a pointer; you can perform arithmetic on a pointer as if it were a number, you can take the difference between two pointers that are both in the interior of the same array and get a sensible result, and so on.

Pointers are strictly “more powerful” than references; anything you can do with references you can do with pointers, but not vice versa. I imagine that’s why there are no references in C — it’s a deliberately austere and powerful language.

The down side of pointers-instead-of-references is that pointers are hard for many novices to understand, and make it very very very easy to shoot yourself in the foot.

Pointers are typically implemented as addresses. An address is a number which is an offset into the “array of bytes” that is the entire virtual address space of the process (or, sometimes, an offset into some well-known portion of that address space — I’m thinking of “near” vs. “far” pointers in win16 programming. But for the purposes of this article let’s assume that an address is a byte offset into the whole address space.) Since addresses are just numbers you can easily perform pointer arithmetic with them.

Now consider C#, a language which has both references and pointers. There are some things you can only do with pointers, and we want to have a language that allows you to do those things (under carefully controlled conditions that call out that you are doing something that possibly breaks type safety, hence “unsafe”.)  But we also do not want to force anyone to have to understand pointers in order to do programming with references.

We also want to avoid some of the optimization nightmares that languages with pointers have. Languages with heavy use of pointers have a hard time doing garbage collection, optimizations, and so on, because it is infeasible to guarantee that no one has an interior pointer to an object, and therefore the object must remain alive and immobile.

For all these reasons we do not describe references as addresses in the specification. The spec just says that a variable of reference type “stores a reference” to an object, and leaves it completely vague as to how that might be implemented. Similarly, a pointer variable stores “the address” of an object, which again, is left pretty vague. Nowhere do we say that references are the same as addresses.

So, in C# a reference is some vague thing that lets you reference an object. You cannot do anything with a reference except dereference it, and compare it with another reference for equality. And in C# a pointer is identified as an address.

By contrast with a reference, you can do much more with a pointer that contains an address. Addresses can be manipulated mathematically; you can subtract one from another, you can add integers to them, and so on. Their legal operations indicate that they are “fancy numbers” that index into the “array” that is the virtual address space of the process.

Now, behind the scenes, the CLR actually does implement managed object references as addresses to objects owned by the garbage collector, but that is an implementation detail. There’s no reason why it has to do that other than efficiency and flexibility. C# references could be implemented by opaque handles that are meaningful only to the garbage collector, which, frankly, is how I prefer to think of them. That the “handle” happens to actually be an address at runtime is an implementation detail which I should neither know about nor rely upon. (Which is the whole point of encapsulation; the client doesn’t have to know.)

I therefore have three reasons why authors should not explain that “references are addresses”.

1) It’s close to a lie. References cannot be treated as addresses by the user, and in fact, they do not necessarily contain an address in the implementation. (Though our implementation happens to do so.)

2) It’s an explanation that explains nothing to novice programmers. Novice programmers probably do not know that an “address” is an offset into the array of bytes that is all process memory. To understand what an “address” is with any kind of depth, the novice programmer already has to understand pointer types and addresses — basically, they have to understand the memory model of many implementations of C. This is one of those “it’s clear only if it’s already known” situations that are so common in books for beginners.

3) If these novices eventually learn about pointer types in C#, their confused understanding of references will probably make it harder, not easier, to understand how pointers work in C#. The novice could sensibly reason “If a reference is an address and a pointer is an address, then I should be able to cast any reference to a pointer in unsafe code, right?”  But you cannot.

If you think of a reference is actually being an opaque GC handle then it becomes clear that to find the address associated with the handle you have to somehow “fix” the object. You have to tell the GC “until further notice, the object with this handle must not be moved in memory, because someone might have an interior pointer to it”. (There are various ways to do that which are beyond the scope of this screed.)

Basically what I’m getting at here is that an understanding of the meaning of “addresses” in any language requires a moderately deep understanding of the memory model of that language. If an author does not provide an explanation of the memory model of either C or C#, then explaining references in terms of addresses becomes an exercise in question begging. It raises more questions than it answers.

This is one of those situations where the author has the hard call of deciding whether an inaccurate oversimplification serves the larger pedagogic goal better than an accurate digression or a vague hand-wave.

In the counterfactual world where I am writing a beginner C# book, I would personally opt for the vague hand-wave.  If I said anything at all I would say something like “a reference is actually implemented as a small chunk of data which contains information used by the CLR to determine precisely which object is being referred to by the reference”. That’s both vague and accurate without implying more than is wise.

In my recent request for “things that make you go hmmm”, a reader notes that you cannot use “var” on fields. Boy, would I ever like that. I write this code all the time:

private static readonly Dictionary<TokenKind, string> niceNames =
  new Dictionary<TokenKind, string>()
  {
    { TokenKind.Integer, "int" }, 
    ...
  };

Yuck. It would be much nicer to be able to write

private static readonly var niceNames = 
  new Dictionary<TokenKind, string>()...

You’d think this would be straightforward; we could just take the code that we use to determine the type of a local variable declaration and use it on a field. Unfortunately, it is not nearly that easy. Doing so would actually require a deep re-architecture of the compiler.

Let me give you a quick oversimplification of how the C# compiler works. First we run through every source file and do a “top level only” parse. That is, we identify every namespace, class, struct, enum, interface, and delegate type declaration at all levels of nesting. We parse all field declarations, method declarations, and so on. In fact, we parse everything except method bodies; those, we skip and come back to them later.

Once we’ve done that first pass we have enough information to do a full static analysis to determine the type of everything that is not in a method body. We make sure that inheritance hierarchies are acyclic and whatnot. Only once everything is known to be in a consistent, valid state do we then attempt to parse and analyze method bodies. We can then do so with confidence because we know that the type of everything the method might access is well known.

There’s a subtlety there. The field declarations have two parts: the type declaration and the initializer. The type declaration that associates a type with the name of the field is analyzed during the initial top-level analysis so that we know the type of every field before method bodies are analyzed. But the initialization is actually treated as part of the constructor; we pretend that the initializations are lines that come before the first line of the appropriate constructor.

So immediately we have one problem; if we have “var” fields then the type of the field cannot be determined until the expression is analyzed, and that happens after we already need to know the type of the field.

But it gets worse. What if the field initializer in a “var” field refers to another (static) “var” field? What if there are long chains, or even cycles in those references? There can be arbitrary expressions in those initializers, expressions which contain lambdas which contain expressions which require method type inference or overload resolution. All of these algorithms that are in the compiler were written with the assumption that when they run, the types of every top-level program entity is already known. All of those algorithms would have to be rewritten and tested in a world where top-level type information is being determined from them rather than being consumed by them.

It gets worse still. If you have “var” fields then the initializer could be of anonymous type. Suppose the field is public. There is not yet any standard in the CLR or the CLS about what the right way to expose a field of anonymous type is. We don’t have good policies for documenting them, versioning them, or interoperating with them across languages. Doing this feature would potentially cause huge costs across the division.

Inferred locals have none of these problems; inferred locals never have cycles or refer to things that haven’t been analyzed yet. Inferred locals never escape into public visibility.

So apparently this simple-seeming feature has the potential to cause really, really bad implementation issues in multiple ways, and all in order to avoid a small redundancy. This seems like it is possibly not worth the cost. If our goal is to remove the redundancy, I would therefore prefer to remove it the other way. Make this legal:

private static readonly Dictionary<TokenKind, string> niceNames =
  new()...

That is, state the type unambiguously in the declaration and then have the “new” operator be smart about figuring out what type it is constructing based on what type it is being assigned to. This would be much the same as how the lambda operator is smart about figuring out what its body means based on what it is being assigned to.

Reflections from 2020

• This was written in 2009; the compiler of course was rearchitected by the Roslyn project, and it is now much more “demand driven” in terms of what gets analyzed when, so some of the objections made in this article no longer apply. However, many of them still do. Changing how type inference works at the “global” level has large design, implementation and testing costs, and that is time, money and effort that gets taken away from more important features than saving a few keystrokes.
• The syntax I proposed at the end may be incorporated into C# 9; this idea has been coming up in the design team discussions for a long time now!

Raymond has had lots of great posts over the years on how to not get a question answered. Some of the ways he points out that help ensure that a question goes unanswered are:

• Use a difficult or meaningless subject line.
• Ask a grammatically unclear question.
• Forget to actually ask a question (this is a personal favourite of mine; back when I was working on scripting I would practically daily get an email consisting of a stack trace and a crash report, with no indication whatsoever of what the sender wanted me to do with it. Investigate it? Commiserate? Give career advice?)
• Ask an unanswerable question over and over again.

I would add that phrasing the question in terms of the attempted solution rather than the underlying problem is a great way to have a question remain unanswered. But I already did that. Today’s rant, rather, is:

A great way to not get your question answered is to treat the person that you’re asking to share their time and knowledge like they’re not a human being.

I understand that this is easy to do.

I understand that when someone is asking a technical question, it is almost always because they’re deeply frustrated by their inability to make some important specific complicated thing work the way they’d expect.

I understand that software makers are a big source of frustration in a more general sense. We all use imperfect software every day; little frustrations mentally accumulate in a way that little victories do not.

I understand that programming languages and software in general is often counterintuitive, and that understanding the complex reasoning behind a counterintuitive result is often seemingly of little practical import compared to just getting the problem at hand solved.

I understand that it is very easy to use an email client as an impersonal and automatic information resource something like a search engine, where you just type in your query, you get your result back, and you move on with your day.

I understand that there is an inherent and pervasive bias in pure-text communication which makes statements intended to be good-humoured sound sophomoric, makes statements which were intended to be friendly sound smarmy, makes statements which were intended to be enthusiastic sound brash, makes statements intended to be helpful sound condescending, makes statements which were intended to be precise and accurate sound brusque and pedantic, makes statements which were intended to be positive sound neutral, and makes statements which were intended to be neutral seem downright hostile.

Boy, do I ever understand that. For over four years I have deliberately tried to pitch the tone of this blog as good-humoured, friendly, enthusiastic, helpful, precise, accurate and positive; I suspect that most of the time I fail badly at most or all of those. Writing is hard.

I understand all that, from both sides; I’ve certainly been on both the sending and receiving ends of all of the above, many times.

Which is why I try very hard to be helpful to the complete strangers who send me overtly rude and frequently profane emails capped off with a request for me to to take time out of my day to explain something to them.

I try to see an upset or confused user as an opportunity to make a good impression; sometimes people do a complete 180 when you help them out and are appreciative and grateful. Sometimes they even send an unsolicited note to your manager, which is always pleasant.

But more often, I never hear from them again after their question is answered.

None of this is in their own best interests. It makes the human information sources they rely upon less likely to help them now and in the future.

So, just a friendly reminder. (A friendly, good-humoured, helpful, enthusiastic, positive reminder!) The people you are sending email to about your technical problems are people. It would be smart to briefly introduce yourself, describe your problem without insulting the people who created it, indicate what you’ve done to attempt to solve it yourself, actually ask for help, and later say thank-you for their time whether they manage to actually help you or not.

It’s smart because doing so is in your own best interests.

It would also be nice, but I actually am not particularly concerned about “nice” today. Nice is nice to have I suppose. But not being smart is just dumb.

Commentary from 2021:

Obviously this rant was born of frustration; one of my predecessors on the C# team, Anson Horton, recently told a story of the early days of answering C# questions internally at Microsoft that reminded me of this article. His story ended well but most of them did not. And of course it was similar answering JavaScript questions internally; it had nothing to do with C# as C#. The underlying problem was how Microsofties (and their customers!) were socialized to treat their colleagues with contempt, and not the software systems which facilitated it.

There were a lot of good comments posted on the original article; to summarize a few of them here:

• Commiseration from people whose time had also been imposed upon by people asking rude and often unanswerable questions.
• Some people said that this was post-it-note wisdom, and that was a compliment: they put a post-it note on their monitor that said “little frustrations accumulate, little victories do not”.
• More ranting from me; I pointed out in a follow-up comment that there were entire multi-week stretches when I worked on subtle problems in method type inference for eight hours a day, and that maybe if I don’t answer your question on that subject within five minutes, there’s a reason for that. It takes research to answer a question correctly, and research takes time, and must be prioritized against many other important concerns.
• A number of readers felt called out, and said yeah, sorry I never thanked you for solving my problem. One of which was a question I answered ten years previously! You’re welcome!

I was expressing some frustration here; I was not fishing for compliments or for thanks, but hey, I’ll take both if they’re offered.