Does Not Compute

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…


Generating Random Non-Uniform Data In C#

When building simulations of real-world phenomena, or when generating test data for algorithms that will be consuming information from the real world, it is often highly desirable to produce pseudo-random data that conform to some nonuniform probability distribution. But perhaps I have already lost some readers who do not remember STATS 101 all those years…


What is this thing you call a "type"? Part Two

Well that was entirely predictable; as I said last time, if you ask ten developers for a definition of “type”, you get ten different answers. The comments to the previous article make for fascinating reading! Here’s my attempt at describing what “type” means to me as a compiler writer. I want to start by considering…


What is this thing you call a "type"? Part one

(Eric is out camping; this posting is prerecorded. I’ll be back in the office after Labour Day.) The word “type” appears almost five thousand times in the C# 4 specification, and there is an entire chapter, chapter 4, dedicated to nothing but describing types. We start the specification by noting that C# is “type safe”…


Never Say Never, Part Two

Whether we have a “never” return type or not, we need to be able to determine when the end point of a method is unreachable for error reporting in methods that have non-void return type. The compiler is pretty clever about working that out; it can handle situations like int M(){  try  {    while(true) N(); …


What’s the difference between covariance and assignment compatibility?

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…


Five-Dollar Words For Programmers, Part Three: Homoiconic

Jeff Atwood was kind enough to once more give me the shout-out in his blog the other day. Thanks Jeff! This inspires me to continue my series on five-dollar words for programmers. Here’s one that I only learned relatively recently, when I helped write the code that translates a lambda expression into an expression tree…


Path Finding Using A* in C# 3.0, Part Four

Finally we are ready to translate our pseudocode into C# 3.0.  What do we need to make the algorithm run? We need a start node, a destination node, a function which tells us the exact distance between two neighbours, and a function which tells us the estimated distance between the last node on a proposed…


Path Finding Using A* in C# 3.0, Part Three

In order to make the A* algorithm work we need to get the lowest-estimated-cost-path-discovered-so-far out of the list of paths under consideration. The standard data structure for doing so is called a “priority queue”. Priority queues are so-called because they are typically used to store a list of jobs where each job has an associated…


Path Finding Using A* in C# 3.0, Part Two

In order to implement the A* algorithm in C# 3.0 I am going to need to implement some custom data structures. Today we’ll consider how to implement the “path”. You’ll notice in my description of the algorithm that the only operations we perform on paths are: Make a new path consisting of a single node….