Browse by Tags

Tagged Content List
  • Blog Post: Persistence, Facades and Roslyn's Red-Green Trees

    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...
  • Blog Post: Atomicity, volatility and immutability are different, part three

    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...
  • Blog Post: Atomicity, volatility and immutability are different, part one

    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...
  • Blog Post: Read-only and threadsafe are different

    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...
  • Blog Post: Graph Colouring With Simple Backtracking, Part Two

    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...
  • Blog Post: Graph Colouring With Simple Backtracking, Part One

    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...
  • Blog Post: Too much reuse

    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...
  • Blog Post: What is this thing you call "thread safe"?

    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...
  • Blog Post: Events and Races

    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...
  • Blog Post: Arrays considered somewhat harmful

    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...
  • Blog Post: Mutating Readonly Structs

    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...
  • Blog Post: Trivial Projections Are (Usually) Optimized Away

    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...
  • Blog Post: Protected Semantics, Part Five: More on immutability

    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...
  • Blog Post: Why Do Initializers Run In The Opposite Order As Constructors? Part Two

    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...
  • Blog Post: Why Do Initializers Run In The Opposite Order As Constructors? Part One

    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...
  • Blog Post: Immutability in C# Part Eleven: A working double-ended queue

    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...
  • Blog Post: deque.cs

    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...
  • Blog Post: Immutability in C# Part 10: A double-ended queue

    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...
  • Blog Post: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

    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,...
  • Blog Post: Immutability in C# Part Eight: Even More On Binary Trees

    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...
  • Blog Post: Immutability in C# Part Seven: More on Binary Trees

    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. ...
  • Blog Post: Immutability in C# Part Six: A Simple Binary Tree

    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;...
  • Blog Post: Immutability in C# Part Five: LOLZ!

    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!
  • Blog Post: Immutability in C# Part Four: An Immutable Queue

    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>...
  • Blog Post: Immutability in C# Part Three: A Covariant Immutable Stack

    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...
Page 1 of 2 (28 items) 12