So what does "volatile" mean, anyway? Misinformation abounds on this subject. First off, so as to not bury the lead: in C# the rules have been carefully designed so that every volatile field read and write is also atomic . (Of course the converse does not follow; it is perfectly legal for an operation...

I get a fair number of questions about atomicity, volatility, thread safety, immutability and the like; the questions illustrate a lot of confusion on these topics. Let's take a step back and examine each of these ideas to see what the differences are between them. First off, what do we mean by "atomic...

Here's a common problem that we face in the compiler realm all the time: you want to make an efficient immutable lookup table for mapping names to "symbols". This is in a sense the primary problem that the compiler has to solve; someone says "x = y + z;" and we have to figure out what "x", "y" and "z...

Before I begin a quick note: congratulations and best wishes to David Johnson, currently the president of my alma mater, the University of Waterloo. The Queen has appointed him to be the next Governor General of Canada come this October. For those of you unfamiliar with the Canadian political structure...

As regular readers know, I'm interested in learning how to change my C# programming style to emphasize more concepts from functional programming, like use of immutable rather than mutable data structures and use of declarative control flow like LINQ queries instead of imperative control flow in the form...

A recent user question: I have code that maintains a queue of pending work items waiting to be completed on various different worker threads. In certain unfortunate fatal error situations I complete each of these by throwing an exception. Can I create just one exception object? Are there any issues...

Caveat: I am not an expert on multi-threading programming. In fact, I wouldn't even say that I am competent at it. My whole career, I've needed to write code to spin up a secondary worker thread probably less than half a dozen times. So take everything I say on the subject with some skepticism. A...

Here’s a question similar to one I saw on stackoverflow the other day. Suppose you have an event: public event Action Foo; The standard pattern for firing this event is: Action temp = Foo; if (temp != null) temp(); What the heck is up with that? Why not just call “ Foo() ” ? First off...

I got a moral question from an author of programming language textbooks the other day requesting my opinions on whether or not beginner programmers should be taught how to use arrays. Rather than actually answer that question, I gave him a long list of my opinions about arrays, how I use arrays, how...

Consider this program which attempts to mutate a readonly mutable struct. What happens? struct Mutable { private int x; public int Mutate() { this.x = this.x + 1; return this.x; } } class Test { public readonly Mutable m = new Mutable(); static void Main(string[] args) { Test t = new Test(); System...

OK, computers aren't entirely dumb when it comes to LINQ. Here's an example of a place where we're a bit smarter. Consider the following query: IEnumerable<int> query = from n in number_array orderby n select n; Does this get transformed by the compiler into IEnumerable<int> query...

I asked a second follow-up question back in Part Two: Suppose you wanted to make this hierarchy an immutable collection, where "Add" and "Remove" returned new collections rather than mutating the existing collection. How would you represent the parenting relationship? The short answer is "I wouldn't...

As you might have figured out, the answer to last week's puzzle is "if the constructors and initializers run in their actual order then an initialized readonly field of reference type is guaranteed to be non null in any possible call. That guarantee cannot be met if the initializers run in the expected...

Pop quiz! What do you expect the output of this program to be? using System; class Foo { public Foo(string s) { Console.WriteLine("Foo constructor: {0}", s); } public void Bar() { } } class Base { readonly Foo baseFoo = new Foo("Base initializer"); public Base() { Console.WriteLine("Base...

At long last, let's get to that double-ended queue. Sorry for leaving you in suspense! Last time we came up with a non-solution -- as commenters immediately discovered, the given algorithm and data structure are deeply inefficient. However, the basic idea is sound. There are a number of ways to solve...

public interface IDeque<T> { T PeekLeft(); T PeekRight(); IDeque<T> EnqueueLeft(T value); IDeque<T> EnqueueRight(T value); IDeque<T> DequeueLeft(); IDeque<T> DequeueRight(); bool IsEmpty { get; } } public sealed class Deque<T> : IDeque<T> { private sealed...

Based on the comments, the implementation of a single-ended queue as two stacks was somewhat mind-blowing for a number of readers. People, you ain't seen nothing yet. Before we get into the actual bits and bytes of the solution, think for a bit about how you might implement an immutable queue which could...

Good Monday morning all. I have received a lot of good comments on this series so far that I thought I would speak to a bit. Academic? First and foremost, a number of people have asked questions which could be summed up as "isn't this just an academic exercise? I have a job to do here!" No,...

Last year we declared a relatively simple interface to represent an immutable binary tree. We noticed that it was different from every other interface that we've declared so far, in that it really said nothing at all about the immutability of the tree. One normally thinks of immutable data types not...

Lots of good comments on my previous post. To briefly follow up: One of the downsides of immutable tree implementations is that usually the tree must be built from the leaves up, which is not always convenient. We'll look at implementations which hide this fact from the user in future posts. ...

OK, we've gotten pretty good at this by now. A straightforward implementation of an immutable generic binary tree requires little comment on the basics. A binary tree is either empty, or a value, left tree and right tree: public interface IBinaryTree<V> { bool IsEmpty { get; } V Value { get;...

My sadly soon-to-be-erstwhile coworker Cyrus made me a lolgeek shirt to go with this series of blog articles: Cyrus, needless to say, is a big goof. Thanks, dude!

An immutable queue is a bit trickier than an immutable stack, but we’re tough, we can handle it. First off, the interface is straightforward; enqueuing or dequeuing results in a new queue: public interface IQueue<T> : IEnumerable<T> { bool IsEmpty { get; } T Peek(); IQueue<T>...

Now suppose we had a hypothetical future version of C# in which interface covariance worked, and we wanted a covariant immutable stack. That is, we want to be able to implicitly convert an IStack<Giraffe> to IStack<Mammal> . As we've already discussed, this doesn't make much sense in an array...

Let’s start with something simple: an immutable stack. Now, immediately I hear the objection: a stack is by its very nature something that changes. A stack is an abstract data type with the interface void Push(T t); T Pop(); bool IsEmpty { get; } You push stuff onto it, you pop stuff off of...