Producing combinations, part two

Last time we saw that producing all the subsequences of a given size k from a given sequence of size n is essentially the same problem as computing all the sequences of n Booleans where exactly k of them are true. How do we do that?

An approach that I often see is “enumerate all sequences of n Booleans, count the number of on bits, and discard those which have too many or too few”. Though that works, it’s not ideal. Suppose we are seeking to enumerate the combinations of 16 items chosen from a set of 32. There are over four billion possible combinations of 32 bits, and of those over three billion of them have more or fewer than 16 true bits, so that’s a lot of counting and discarding to do. We can do better! To do so, we’ll use a combination of all my favourite techniques:

  • Immutable data structures
  • Abstract classes with derived nested classes
  • Recursion

Long-time readers of this blog will have seen me use these techniques before, but for new readers, a quick introduction is in order. Continue reading

About these ads

Confusing errors for a confusing feature, part three

One of the nice things about a project as large as the Roslyn project is that you have an opportunity to really think hard about your past mistakes and hopefully fix them. When I was working on getting these error messages reported in Roslyn I realized that trying to match exactly the behavior of the original compiler would be actively making the world a worse place, so I took a big step back and started sending a lot of emails to Mads, Neal, Anthony and the rest of the Roslyn gang to try and get a better design worked out. All the godawful nonsense I told you about in the previous two episodes will be fixed in Roslyn.

Continue reading

Confusing errors for a confusing feature, part two

Last time I gave you the challenge to find a case where the same simple name means two different things, without introducing a new local/parameter/range variable into scope, that produces an error. It seems like it ought to be impossible; if nothing new has been introduced to a local scope then how can name resolution choose two different things? The relevant section of the C# specification ( Invariant meaning in blocks) only gives the example I gave last time, of a local having the same name as a field.

The key to solving the riddle is a little-known rule about resolving a name from a set of possible class members: Continue reading

Confusing errors for a confusing feature, part one

There’s a saying amongst programming language designers that every language is a response to previous languages; the designers of C# were, and still are, very deliberate about learning from the mistakes and successes of similar languages such as C, C++, Java, Scala and so on. One feature of C# that I have a love-hate relationship with is a direct response to a dangerous feature of C++, whereby the same name can be used to mean two different things throughout a block. I’ve already discussed the relevant rules of C# at length, so review my earlier posting before you read on.

OK, welcome back. Summing up:

  • C++ allows one name to mean two things when one local variable shadows another.
  • C++ allows one name to mean two things when one usage of a name refers to a member and a local variable of the same name is declared later.
  • Both of these features make it harder to understand, debug and maintain programs.
  • C# makes all that illegal; every simple name must have a unique meaning throughout its containing block, which implies that the name of a local variable may not shadow any other local or be used to refer to any member.

I have a love-hate relationship with this “unique meaning” feature, which we are going to look at in absurd depth in this series.
Continue reading

ATBG: randomness

Today on the Coverity Development Testing Blog’s continuing series Ask The Bug Guys I’m turning it around and asking you to figure out why a seemingly correct and totally awesome implementation of random.Next has a serious bug. That’s right, it’s everyone’s favourite game, Spot the Defect! Can you figure out where I wrote a bug without running the program? Check it out.

Continue reading