by ·0 Comments

From the “things that really shouldn’t be difficult, but for some reason are anyway” department comes the following. Do you think you know how to program in C++? Familiar with objects and polymorphism and templates and everything? Then this should be dead easy. Should, I said.

Problem: Write a function that takes in a std::istream and a size n and returns a std::string. The string should contain the first n characters of the input stream, with all formatting (whitespace, newlines, etc) preserved.

You can ignore all concerns about multi-byte characters for the sake of this problem. Sounds simple, right? You’d be able to crank this out in ten seconds if someone asked you this in an interview, right? Okay, now try it with this caveat.

Caveat: You must do this in a purely C++ “style”. To be precise, you must do this without using any character variables or character arrays. Use only a std::string object (or some other memory-managed object in the standard library) as your input buffer.

For as much as the C++ STL tries to encourage you to use RAII-oriented containers instead of raw arrays, this seemingly trivial task requires some surprisingly baroque coding. If you want to test yourself, try writing the function before you click more.

Continue reading

by ·0 Comments

While catching up on recent postings to Lambda the Ultimate, I was rather surprised to discover that last week concepts were, by a vote of the committee members, completely removed from the C++0x draft specification.

On Monday, July 13th 2009 Concepts were dramatically voted out of C++0x during the C++ standards committee meeting in Frankfurt. […] When I first heard the news, I couldn’t believe it. Concepts were supposed to be the most important addition to core C++ since 1998. Tremendous efforts and discussions were dedicated to Concepts in every committee meeting during the past five years. After dozens of official papers, tutorials and articles — all of which were dedicated to presenting and evangelizing Concepts — it seemed very unlikely that just before the finishing line, Concepts would be dropped in a dramatic voting.

C++0x is the next version of the C++ language standard. It should more properly be called C++1x, since the chances of it being released within the year are like the chances that Microsoft would contribute code to the Linux kernel — er, bad example. Anyway, the point is that it’s not going to be done this year.

While I’ve been following the development of C++0x with interest, I haven’t been immersing myself in the implementation details. In essence, I want to know what’s coming up, but I’m not too interested in committing to memory the nuts and bolts of a specification that is likely to be revised several more times before it is finalized. I’m not totally abstaining from C++0x until it’s done. I do use some features where they are useful and already implemented, for example I am using unordered_map, the standard library’s version of a hash table, in the latest iteration of my work on the lottery problem. However, my understanding of the majority of C++0x features has been relatively, for lack of a better word, “conceptual”.

The layman’s understanding that I had of the C++0x concepts feature led me to react with shock to learning of it’s removal. It sounded incredibly useful, and I didn’t see what could be such a big problem that it would have to be ripped out entirely. That changed when I read more about concepts as they (were going to) exist in C++0x.

Continue reading

by ·2 Comments

In the final installment of the portion of The Lottery Problem article series that has to do with the simple greedy wheel generator, I give a brief complexity analysis of my generation algorithm, and I report on the successes and the failures of the implemented generator:

On a 2.66 GHz Intel Core 2 Duo (though only using a single core), the generator consumed a peak of 1.87 GB of RAM and ran for approximately 36 hours before returning its wheel for 3-matches in a 6-from-49 lottery. […] The wheel that it generated for my target 6-from-49 3-match lottery was 325 tickets long. While this is in my opinion a pretty good wheel, it is not optimal.

You can read the whole article here. The long and the short of it is that the generator is indeed as efficient as I hoped it would be, but that it is not an optimal generator, as I suspected it would not be. The above-linked article includes a link to download the code for my implementation of this generator, if you wish to download it to play around with it or try to improve upon it.

My hunch is still that this problem is NP-Hard, and so I do not expect that any such simple generator will consistently produce optimal wheels. However, this is not the end of my series of articles on this problem. I do have hope that I can improve the generated wheels substantially by including a heuristic function that avoids the pitfalls of my current generator. Ultimately I would like to produce a generator that produces wheels that are guaranteed to be within a small approximation factor of optimal, or a randomized generator that is optimal with a reasonably high probability.

One small confession is that while I have posted the six articles in the current Lottery Problem series over the course of about six weeks, I had in fact written the entire greedy generator and knew its results before I even began writing the articles. For the heuristic and/or randomized generator that I am considering, I have so far done little more than pondering, so it may well be more than a week or two until the next article is posted.

by ·3 Comments

Autotools, more properly known as the GNU Build System is a set of shell script-based utilities that automate parts of the configuration and compilation process for software that is distributed as source. The autotools are, in my opinion, a bit over-complex and fragile, but they remain the most portable and standardized way of allowing software to be compiled on UNIX-like (and especially Linux) systems.

One of the parts of autotools, called autoconf, is responsible for creating the “configure script” for a source package. If you’ve ever built a piece of free software from source, you have almost certainly encountered the following venerable triumvirate of commands:

./configure
make
sudo make install

That first command runs the script that is the output of autoconf, and it is responsible for detecting the capabilities and details of the system that the software is being compiled on. It, for example, will check that a sufficiently-recent compiler is available, and what system headers are necessary for various semi-standardized functions that the program uses. One other major function of the configure script is to detect whether or not libraries that the software depends on are available on the system.

The library detection mechanism, however, is biased heavily towards libraries written in C. Since C is of course the lingua franca of the UNIX world, this is understandable. Without cajoling, it really won’t detect libraries written in anything else, unless they have C bindings, and that includes C++. What then do you do if you have a C++ library that you wish to detect using autoconf? If you’re interested in the answer to this question, you probably already know what the problem is, and here I will give two workable solutions.

Continue reading

by ·6 Comments

I thought of a quick addendum to Monday’s article on covariant, templatized copy constructors. The end of that article said

[T]here is a large caveat that you may have noticed. Due to the the inversion of the inheritance hierarchy around the cloning mixins, we have completely lost the ability to construct derived objects using anything but the default constructor. If you need to construct a Derived (which is really a Cloneable<Derived_>) and pass an argument to the Derived_ constructor, you cannot.

And then I go on to suggest using a factory pattern that is aware of the quirky type hierarchy described in that post. But in fact there is a relatively elegant way around this problem without using factories.

Continue reading

by ·1 Comment

I’d like to address something that I’ll call the “I’ll tell you when you’re older” phenomenon in computer science education. This mostly has to do with programming, but there are also situations in theory education where this happens as well. Specifically here I’m going to discuss how it can affect the choice of a teaching language.

As is often the case with something so complex and with such a storied history, programming languages have quirks, gotchas, and many layers of operation. Therefore, it turns out to be extremely tempting when introducing an aspiring programmer to his or her first computer language to try as much as possible to avoid confusing the student by eliding material that isn’t relevant to the lesson at hand. Essentially, this means deflecting tangential questions, or anticipated questions, with the educational equivalent of the commonly experienced childhood situation where your parent promises to explain to you what some mature or risque term means “when you’re older.” In this sense, the instructor is requiring the student to wait until a later point in the course before explaining the meaning of a particular concept or construct.

In the abstract, this seems to be an advisable thing to do, but (though I certainly haven’t done formal study to back up this assertion) I suspect that it encourages the dreaded practice known as cargo-cult programming. Cargo-cult programming is the software engineering manifestation of an appeal to authority. It entails the use of patterns or code fragments when one does not really understand what they do or why they are being used, simply because one has been instructed to use them, or has seen an instructor silently do so.

It is my belief that a programmer, be he a student or a professional, should never, ever write a line of code without understanding what it does or why they wrote it. This maxim is fundamentally incompatible with the “I’ll tell you when you’re older” educational tactic because that tactic necessarily entails that the student use something without having understood it. So this tactic should be avoided whenever possible, and it should absolutely be avoided in a student’s very first lesson.

Continue reading

by ·6 Comments

One problem that programmers new to C++ often run into when they begin to write non-trivial programs is that of slicing.

In object-oriented programming, a subclass often holds more information than its superclass. Thus, if we assign an instance of the subclass to a variable of type superclass, there is not enough space to store the extra information, and it is sliced off.

The simple way to avoid slicing is to avoid making copies. Simply pass polymorphic objects around by reference (or by pointer) rather than by value, and one never has to worry about slicing. But sometimes the need to copy is unavoidable. In particular, when the need arises to make a copy of a derived object and all you have is a base pointer, things get hairy. How do you know which derived class the pointer’s target really belongs to, in order to make a proper, deep, non-sliced copy?

Fortunately, this problem has a well-known solution pattern called the virtual copy constructor idiom. One implements a virtual clone() method that makes a proper deep, non-sliced copy. There’s nothing wrong with this idiom, but it does entail the inelegance of having to repeat near-identical code for the clone() method in each derived class.

C++ programmers encountering this pattern for the first time often get the bright idea that this code can be centralized through the use of templates. Doing this while maintaining all the advantages of a non-templatized virtual copy constructor turns out to be much trickier than it first appears. This post will explain the problem, and how to do something that I have not yet found described on the Internet: implement the virtual copy constructor idiom using templates without sacrificing covariance.

Continue reading

by ·0 Comments

In Monday’s post, “Out-of-Band Error Reporting Without Exceptions”, I described a method for elegantly obtaining three out of five major advantages of C++ exceptions without actually using them. Now I’ll tell you how to go about grabbing a fourth advantage: exception type hierarchies.

C++ exceptions are hierarchical, and their hierarchy is a type hierarchy such that a more-derived exception can be treated, if desired, as one of its base exception types. For example, a FileNotFoundException might be derived from FileIOException. Some code may choose to handle FileNotFoundExceptions distinctly from other FileIOExceptions. Other code might delegate all FileIOExceptions to a common handler. In C++ this is done with implicit typecasting in the catch statements in a try block.

Wouldn’t it be useful if we could do something similar with the ErrorReport and CheckedValue classes that were defined in Monday’s post, instead of just having an error/not-an-error indicator and a human-readable message? Well, we can. It’s easy to use but a little tricky to set up.

Continue reading

by ·0 Comments

The newest article in my series on the Lottery Problem describes the design decisions I made when making my first attempt at an implementation of an efficient wheel generator based on the simple greedy algorithm for set cover. The design decisions described were influenced by three key insights I had when considering how one might attempt to generate a close-to-optimal wheel for a 6-from-49 lottery in a reasonable amount of time.

  1. Once the relationships between tickets have been completely expressed, the actual numbers that constitute the tickets are of no significance and can be discarded.
  2. It is only necessary to keep track of how many uncovered tickets an unselected ticket could potentially cover if selected. It is unnecessary to know exactly which tickets those are.
  3. Every ticket initially covers the same number of other tickets, and this number can be computed through combinatorics alone.

You can read the full article here. It primarily addresses the challenges involved in expressing the problem within a reasonable amount of memory, and gives an overview of how the computation will be approached. The computation itself will be described in detail in the next article.

by ·1 Comment

Let’s say, for the sake of argument, that you’re working in C++ and you happen to be in an environment where exceptions don’t work. In my case, it was an embedded environment where the miniaturized C++ standard library didn’t support them, but in your case it may be that you can’t use them for performance reasons, or they’re against policy or something else.

As opposed to the old C-style return codes, C++ exceptions offer five major advantages:

  1. They are out of band (that is, a function returning an integer need not assign a special value, e.g. -1, to mean “error”).
  2. They can carry information about the specific error that occurred, as opposed to simply a code with a general meaning.
  3. They exist in a type hierarchy. A FileNotFoundException may be derived from a FileIOException, and a handler for the latter can handle the former.
  4. If you ignore them, your program blows up. This is a good thing – an undetected error is far worse than a fatal error.
  5. They automatically unwind the stack to find a handler.

And these are all reasons why, unless you have a good reason not to, you should prefer using exceptions. But in the case when you can’t, it turns out that point 5 is really the only advantage that you have to do without. There’s a relatively elegant method that you can use to achive the first four advantages without using exceptions at all.

Continue reading