Browse by Tags

Tagged Content List
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: 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...
  • Blog Post: Path Finding Using A* in C# 3.0, Part One

    As we get into the home stretch for the Orcas release I’ve been spending a little time lately just playing around implementing some “classic” algorithms and data structures in C#. The one I implemented today is the famous A* algorithm. Surely you’ve played games like Age of Empires. You know the kind...
  • Blog Post: What exactly does 'lifted' mean?

    (Note: all type placeholders S , T , U that I mention in this article are non-nullable value types.) I got a question the other day from a reader who had been taking a close look at the C# 2.0 standard. He noticed that when we talk about nullables in the standard we talk about "lifting", but we do...
  • Blog Post: Lambda Expressions vs. Anonymous Methods, Part Five

    Last time I demonstrated that the compiler could have to do an exponential number of bindings in order to determine whether there was a unique best overload resolution for a function call that takes a lambda. Some of you may have wondered whether we simply were not being clever enough in the compiler...
  • Blog Post: Every Number Is Special In Its Own Special Way

    I got a question recently about where in the .NET framework the "special numbers" were defined. The questioner was actually asking about the Double.NaN , Double.PositiveInfinity , etc, special values for floating point numbers. Of course there are other "special numbers" defined by the framework, such...
  • Blog Post: Regular Expressions From Scratch, Part Twelve: Superposition of States

    Happy New Year everyone. Over the break I had a wonderful time reconnecting with my friends and family. And of course I came back to a huge pile of work! We're going through the flaws that were discovered in C# 2.0 too late in the cycle to risk fixing, and some of them illustrate interesting corner...
  • Blog Post: Regular Expressions From Scratch, Part Eleven: Eliminating Multi-Symbol Rules

    The story so far: we have deterministic and nondeterministic finite automata. DFAs follow a rigid, fully specified set of rules which, on any string, yield either an accept or reject state after exactly as many moves as the string has characters. NFAs, on the other hand, are poorly specified. ...
  • Blog Post: Regular Expressions From Scratch, Part Ten: Magic!

    Let's recap the story so far. Starting only with basic set theory, sequences, symbols and numbers, we've defined alphabets, languages, regular expressions, and the mapping between regular expressions and regular languages. We've also defined deterministic finite automata as machines that take in...
  • Blog Post: Regular Expressions From Scratch, Part Nine: A Dream of a Machine

    I want to come up with the simplest possible device that can identify whether a given string is a member of a given regular language. We need some kind of computer, but to make it easy to analyze, I want to put as many restrictions upon it as possible. For example, I want there to be very limited...
  • Blog Post: Regular Expressions From Scratch, Part Eight: The Diagonal Argument

    As we know, each regular expression is associated with a language by our function L. We also determined last time that we could list all members of S* and R in order first by length and then by alphabetical order. Here's a weird question: is the nth string in S*'s alphabetical ordering a member of...
  • Blog Post: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

    Regular languages are by definition those languages which can be described by a regular expression. It should be clear from the definition that the union of any finite number of regular languages is a regular language, the concatenation of any finite number of regular languages is a regular language...
  • Blog Post: Regular Expressions From Scratch, Part Six: The Insanely Clever Bit

    Let's start with an easy one today, because things are about to get a little tricky. Definition 10 : a pair is a finite sequence with exactly two members. Definition 11 : a function is a set of pairs, where the second member of each pair is the value associated with the first member...
  • Blog Post: Regular Expressions From Scratch, Part Five: The Regular Expression Language

    Now things start to get really weird. Definition 9 : Take any alphabet S. The regular expression alphabet of S is S plus a bunch of extra symbols; it's S ∪ { ( , ) , * , ∪ , Ø } (I assume that none of those symbols are already in S.) I'm doing something...
  • Blog Post: Regular Expressions From Scratch, Part Four: The Kleene Closure of a Language

    Languages are sets, so we can take any two languages (over the same alphabet) and take their union to form a new language. Just as a reminder: Definition 7 : The union of two sets L and K is the set with all the members found in either , and is written L ∪ K. We're going to take...
  • Blog Post: Regular Expressions From Scratch, Part Three: Concatenation

    You probably intuitively understood concatenation already, but let me define it anyway. Definition 5 : The concatenation of two strings w and u (over the same alphabet) makes a string consisting of the sequence of every element in w followed by every element in u. We write concatenations...
  • Blog Post: Regular Expressions From Scratch, Part Two: Some Examples of Languages

    Let's look at some sample languages to get a sense of just how flexible languages can be. For example, here are some languages over the alphabet S = { 0 , 1 } L 1 = all members of S*, period -- the language where every string is in the language L 2 = all members of S* such that...
Page 1 of 3 (53 items) 123