The Sweet Heartbreak of Parenting

Tonight, my son made cry more (and harder) than I have in years.

He doesn't even realize it (in fact, he's not even home right now), and would probably think I was a little crazy for its affecting me at all. Who knows, maybe I am a little crazy, but I decided I needed to write it down somewhere. Who knows--somebody might find it a little entertaining or informative, or something.

My wife took my kids on vacation, so they're not around the house right now. I was doing a little house-cleaning (yes, I actually do that, regardless of what my wife claims). Cleaning the bedroom shared by my two youngest sons (8 years old and 5 years old), I noticed that all their stuffed animals were on one of the beds. Usually they fight over the stuffed animals, and who can get the most on any given night. Once they've divided them up, each jealously guards his treasure trove with little short of his life. Seeing them all on one bed was a little surprising, to say the least.

I started to pick up a couple of the animals to put them back where they belonged, and saw there was a slip of paper under them. On it was written, in an 8 year-old's handwriting: "Here Ben. I'm almost nine now. I don't need stuffies any more."

I can't help thinking that my sweet little boy just declared that his childhood is over. He's a big boy now. I guess I can understand that. I remember when I too wanted more than anything in the world to be "big"--to be a grown-up. In some ways, I can't blame him. Being a grown-up definitely has some good points to it. I love being a father. Having a family is by far the greatest privilege of my life.

Even so, I hope--almost more than anything else I can think of right now, that by the time they get back from vacation, he's forgotten the note, and they fight at least a little bit over the stuffed animals. The fighting may upset my wife a little bit, but if they don't fight, it really does mean he's leaving behind a little more of the sweet baby boy I remember. I know that's inevitable anyway, but I hope he hangs on to a little bit of it at least a little longer.

You've probably heard it before, but I'll repeat it again: if you're a parent, treasure the time with your children. Even when they drive you crazy with noise and fighting and running and being out of control, try to remember: that'll end soon enough. Do your best to be happy with it while it lasts.

Privilege and Idiocy

My sister recently posted a link to a test (How Privileged Are You) on her FaceBook page. She’d taken the test and posted her score. A number of her friends commented with their scores as well. Sadly (at least in my opinion) none of them posted a critique of the test itself, only scores that it had produced, seemingly taking it for granted that those scores were meaningful.

I was curious, so I looked at the test. It struck me as one of the most idiotic things I’d seen in quite a while (not sure if that means I'm picky or just lucky). A lot of online tests are pretty awful, but at least among those I’ve seen, this truly does take the prize for the worst of them all.

The directions for the test tell you to “Check off all the statements that apply to you.”

The first few statements

1. I am white.

This at least tells us the nature of the test—the more items you check, the more “privileged” it’s going to claim you are. Other than that, it’s pretty close to pure idiocy. Just for example, if a child is (roughly) half Caucasian and half Filipino, do they count as “white” or not? The simple reality is that trying to draw clear lines between races is difficult and error prone at best. Yes, if you’re careful enough to define what “white” means, you can find people who do and don’t qualify—but by the time you decided on a clear-cut definition to which people can give an accurate and meaningful answer, you’re going to lose the ability for it to do what’s really intended: create division and discrimination.

2. I have never been discriminated against because of my skin color.

This is essentially impossible for anybody to truly answer. There are clear-cut cases where somebody can state with certainty that they were discriminated against because of their skin color (the US in the 1950s or earlier, South Africa under Apartheid, etc.)

It's impossible, however, for anybody to know that they were *not* discriminated against because of skin color. That time in third grade when nobody wanted to choose me for their team at recess? Probably because I was skinny and nerdy--but I can't say with certainty that nobody ever thought "let's skip the pasty white guy".

3. I have never been the only person of my race in a room.

This reaches a level of excrescence I’d never previously experienced. Allow me a bit of a digression to attempt to explain why that’s true¹.

I grew up in Aberdeen, South Dakota. I don’t have any official statistics on its demographics at that time, but my guess would be that its population was at least 90% western Europeans (and over 95% wouldn’t surprise me even a tiny bit). I was something like 14 years old before the first time I actually traveled outside South Dakota at all—and that was to a small town in Minnesota, where the population was about equally white (maybe even more so, though I don’t really know).

So, in the view of the people who wrote this test, at that time I was apparently almost supremely privileged. Essentially any and every time I’d been in a room full of people, not only had there been at least one other Caucasian, but in most cases, the vast majority (or all) of them were Caucasian.

Much more recently, I’ve traveled to (for one example) the Philippines. While I was there, it was quite common that I was the only Caucasian in the room, and in some cases probably the only Caucasian within a few miles.

So if we treat this test as meaningful, we believe that I’m actually less privileged now than I was as a child.

In reality, exactly the opposite is true. Going to the Philippines was a huge privilege, and having members of my wife’s family to lead me around, show me the sights, and expose me their viewpoints on life was an even greater one. At least for a child like me who was curious about the world, growing up in a white ghetto was far from a privilege, and getting to see other parts of the world far from repressive.

4. I have never been mocked for my accent.

When I was a kid in South Dakota, we were often visited by our cousins from Minnesota. Each of us thought the other had a funny accent, and yes, each group mocked the others’ accents.

Apparently in the minds of the people who wrote this test, I’d have been more privileged if my cousins had never visited. I’m left wondering what sort of lunacy would lead somebody to this conclusion. Does anybody honestly think that a little good-natured mocking actually hurt me? Would I have been better off in any way if my cousins hadn’t visited?

5. I have never been told I am attractive “for my race.”

Like pretty nearly everybody in the US close to my age, there was a period of about six months (or so) when I’d have had to live by myself under a rock in the mountains to avoid hearing that I was “Pretty Fly for a White Guy”, usually several times in fairly quick succession.

Does somebody honestly think that hearing that silly song somehow made me “less privileged”? Seriously?

More selections

I guess I’ll stop with the point by point critique here, but not without pointing out one more detail: no, I did not go through the list and cherry-pick these particular statements out of a long list that actually made more sense.

Having done that, now I really am going to cherry pick a few that I think are particularly egregious, for various reasons.

• I have never been raped.

First, I’m utterly horrified that anybody would imply that living without being raped is a privilege. This is not a privilege—it’s a right! Anybody who even hints at the possibility that living without being raped is a privilege really needs to get a clue.

Second, looking at the definition some people use of “rape”, my initial reaction of “of course I’ve never been raped” was apparently wrong.
When I went into the military (US Air Force, in 1984) part of the medical examination involved a doctor pushing a finger in your sphincter. To my thinking, this was simply a normal part of a medical examination, to which tens of thousands of people are subjected every year.

Looking through the post-modern definition of rape, however, it was actually rape, as some people define the term.

Was there penetration? Yeah, pretty definitely.

Was this something I really wanted to have happen? Definitely not.

Was there “coercion or economic inducement” applied to get me to consent? Well, yeah—if I hadn’t consented, I couldn’t get the job or the pay that went with it.

At least in my opinion, calling this rape is utterly idiotic. The reality is that yes, there was a level of “coercion” involved—but if I’d decided to, I could still have refused, and it wouldn’t have happened. I’m reasonably certain that many of the people who consider themselves to have been raped were in roughly similar situations. They gave consent to something with which they were at least mildly uncomfortable, but could have refused—and if they had, what they’re terming as “rape” wouldn’t have happened.

Of course, there are people who define rape even more broadly than that—in some cases, that the “inherent differences in power” between men and women are so great that even when a woman thinks she’s consenting (or even wildly enthusiastically initiating the sexual encounter) that it’s still rape.

• I’ve never been told that I’m overweight or “too skinny.”

I’ve actually been told both of these things—and in both cases, it was clearly true. As a teenager I was underweight. I’m now rather overweight. This isn’t a result of “privilege”; it’s a result of having been too skinny at one time, and now being overweight.

Regardless of people talking about “body types” and such, the simple fact of the matter is that I’m overweight for a couple pretty simple reasons. First, I eat too much—especially snacks. Second, I don’t get enough exercise. If there’s any blame to be laid here, it’s certainly not on anybody else for having the nerve to point out the simple fact that I’m overweight—quite the contrary; instead of writing this, I should probably be going for a healthy walk right now.

I have a little more sympathy for people who are severely underweight. This can be much more difficult to deal with. If you're honestly anorexic, seek help if you aren't already getting it.

If your weight is actually reasonably normal and you're healthy, somebody saying otherwise--well, now you know at least some people to avoid. Seriously, in schools (for example) people being nasty and mean to each other has been happening for a long time. You may feel that you lack "privilege" because people pick on you--but I can pretty much guarantee that the people you think of as "privileged" are being picked on as well. Even the head cheerleader, homecoming queen, center of the basketball team, quarterback of the football team, etc., are getting picked on by somebody. There may be somebody, somewhere, sometime who honestly went through school without anybody every picking on them, and if so I guess they really are privileged--but personally, I doubt it's ever happened, even once.

• I have never been cyber-bullied for any of my identities.

I find this egregious for a number of reasons. First of all, when I was a child, cyber bullying didn’t exist. Apparently, these people think that made everybody “privileged”. Again, the reality is quite the opposite. Having an immense treasure of knowledge like the Internet easily available is a truly massive privilege. If you choose to waste your time on some social media site where cyber-bullying happens...well, don’t do that! Seriously, I don’t mean to say people should be excused for cyber-bullying, but the simple fact is that in a case like this, self defense is utterly trivial, and you'll be better off for it anyway.

Second, the people who wrote this idiocy have (like with many other things) taken “identity”, which used to have a clear definition, and abused it horribly, to the point that it doesn’t really mean anything any more. What’s worse, they’re apparently proud of having done so—they refer to a single person as having multiple “identities” in at least a half dozen of their statements.

Now, it may be open to argument that in the specific case of dissociative identity disorder (previously known as multiple personality disorder), that a single body could be “home” to multiple personalities, each of which should be treated as having its own identity.

Dissociative identity disorder, however, is a serious and fairly rare psychiatric condition. Exactly how rare is open to some debate—the highest estimate I’ve heard is that it might be as great as 1% of the population; most estimates are substantially lower.

In any case, taking for granted that everybody who takes the test (or even most of them) have multiple identities is abusing the word to mean essentially the opposite of what it really does. What they’re apparently getting at is something like "characteristics", rather than actual identity (of which, by nature, I have exactly one—and there’s a solid case to be made that even in a case of DID, there’s still really only one identity, albeit of a personality that’s been badly damaged by abuse).

The Verdict on the Test

Worse than the individual items in this list is the basic attitude it shows in general. Essentially all of the questions really seem to revolve around one point: a belief that if people act as if they like or admire me, that’s “privilege”. It seems to me that it does a fair job of testing one thing. I’m not a psychiatrist, but I see little choice but to conclude that regardless of the actual score you get in this test, if you consider the test or score as having even the slightest bearing on reality, you should probably seek professional help immediately (no, I’m not being sarcastic at all—I’m 100% serious).

Real Privileges

I believe I am extremely privileged. Let me list a few of the factors in my life that I think have been real privileges:
1. I learned to read at an early age.
2. I had a large supply of books available at an early age (for people less ancient than myself, feel free to substitute Internet access—it not only provides much more information, but makes it dramatically easier to access as well).
I’ve lumped these together because they largely go hand in hand. They are also absolutely immense privileges—if you checked off every one of the items in the test under discussion, it still means far less than having learned to read.

Most learning comes from reading. Somebody who’s been taught to read can learn nearly anything and everything else s/he desires.

3. Other early education

I lump all the other early education together. Don’t get me wrong: learning about history, geography, mathematics, etc., is all important—but somebody who knows how to read can learn them independently, so all the other education is still minor compared to learning to read and having reading material available.

4. Having children

I think having children is the single greatest privilege of my adult life. I don’t know of a way to describe what a huge privilege this really is, at least for me. The test at hand would undoubtedly (correctly) conclude that I’m highly privileged—but everything it attempts to measure, combined, is still utterly trivial compared to the privilege of having children.

5. Being intelligent

Years ago (from 1988 to 1991) I spent three years helping teach/train developmentally disabled people to help them live as independently as possible. Just to give an example that’s obvious to me, seeing the immense difference between how quickly my children have learned and how much slower and more difficult it is for people who are even mildly handicapped has given me a tremendous appreciation for the degree to which intelligence smooths the way through modern life, and makes nearly everything easier.

6. Living in modern times
For the vast majority of human history, large parts of the population were in danger of starving to death, or being a casualty of war (or both)--often many times in their lives. Although I’ve never actually been in danger of starving to death, I’ve gone for two or three weeks at a time without an actual meal. Even that degree of hunger dwarfs the trivial nonsense discussed in this test.
Even for people whose lives weren’t directly endangered, anything approaching “fulfillment” from life was far beyond most peoples’ dreams throughout most of human history. Slaves and serfs frequently had no choice at all in their lives, and even nominally “free” people frequently had little real choice, and essentially no chance at “upward mobility’ at all.
Even compared to when I was a child growing up, the amount of information people have easily accessible is absolutely astounding. Being able to type a paper for school on a computer and correct spelling errors easily instead of writing it by hand and starting over if you made too many spelling mistakes--there's no way to meaningfully compare these.
7. Living in the western world
Even today, many people are raised in enforced ignorance. There are still people in danger of dying from starvation or diseases to which cures and/or effective vaccinations are well known. A great deal has been done relatively recently (much thanks to the Bill and Melinda Gates Foundation, among many others), but there’s seriously a lot left to do, and areas where such assistance is routinely refused as well.

Conclusions

1. The test is utter nonsense
2. There are real privileges—and they’re huge compared to the trivial nonsense covered by the test questions. They’re also very close to universal among essentially everybody with access to the test though. We, the people with easy access to the Internet are much more alike than different—and all of us are almost supremely privileged.

1 I’m trying to ignore the obvious logical problem here: anybody who’s ever been alone in a room has clearly been the only person of their race in the room, so it's nearly inevitable that at some time or other, *everybody* has been the only person of their race in a particular room.

Raw loops vs. standard algorithms revisited

I was recently reading a Post on Meeting C++ about raw loops vs. STL algorithms.

I didn't think his solution using STL algorithms took full advantage of what the library really has to offer. He did use std::mismatch to find the point at which items mismatched, which is clearly a good thing. The rest of the code, however, looked to me like he was thinking primarily in terms of loops, and merely changed the syntax from a for loop to use std::for_each instead.

At least in my opinion, this doesn't really gain much. At least in my observation, using `std::for_each` is most often a mistake. It's still little more than a generic loop. The name of algorithm used should usually give me a good idea of what some code is doing, but `std::for_each` really doesn't--I have to look at the content of the "loop" to get any idea of what it's really doing.

In this case, the basic idea (simplifying a tiny bit) is to take the paths to two files, and find a relative path from one to the other. The two paths have already been parsed into components held as strings in a vector, so our job is to generate a path with "../" for all the leading components that are identical, then copy the components from one of the vectors into the output after that (and finally append a file name on the end).

Just going from that description, some choices seem fairly obvious, at least to me. To generate the leading part of the path, we probably want to use `std::generate`. Then to copy the remaining elements, we probably want to use `std::copy`. Although it may not be quite as obvious just from the wording, `std::fill_n` actually works out a little better than `std::generate_n`.

Our result is going to be in the form of a string. We want to append strings together to create the whole output. One obvious way to do that is to use an `std::stringstream`. So, let's start by doing a tiny bit of fudging to turn this into a standalone example (I don't think this has a significant effect on what we're doing). Rather than extract the vectors from a cache as he did, let's start with a couple of fixed vectors:

    std::vector a = { "dir1", "dir2", "dir2_1", "p" };
    std::vector b = { "dir1", "dir2", "dir2_2", "p" };

Then we do the step that (I think) he got right:

    auto pos_p = std::mismatch(a.begin(), a.end(), b.begin(), b.end());

From there, we can define our stringstream, and an iterator to give us access to it in a way that's friendly to standard algorithms:

std::ostringstream path;

std::ostream_iterator(path, "/");

Then we want to generate the leading part, then copy the trailing part of the result path:

std::fill_n(out, pos_p.first - a.begin(), "..");
std::copy(pos_p.second, b.end(), out);

At least in my opinion, this makes it much more apparent that the first part of the path is composed of instances of ".." separated by "/", and the second part is composed of elements from the second vector (again, separated by "/").

This hasn't shortened the code a lot (maybe not at all), but it has (at least in my opinion) made the actual intent much clearer.

For better or worse, I've seen a fair number of arguments/claims that using a stringstream and an ostream_iterator can produce substantially slower code that doing the job by appending data directly to a string. I haven't tried to run a benchmark to verify this, but for the moment, let's assume you were working with a compiler for which it really was true (and true to an extent that the slow-down was a serious concern).

If so, we could still use roughly the same structure--we just have to define our own iterator to handle appending things to a string instead of inserting them into a stringstream. We lose some versatility (we can only insert things that are already strings, rather than handling all sorts of conversions to strings like a stream can), but maybe we gain enough speed for that to be worthwhile. So, if we decide this is really worth doing, implementing it is pretty straightforward (moreso than most people seem to think).

Our iterator to append to a string (with a little front-end function to avoid having to pass template parameters explicitly) can look something like this:

#include 

template 
class appender_t : public std::iterator{
    String *s;
    String sep;
public:
    appender_t(String &s, String sep) : s(&s), sep(sep) { }

    appender_t operator=(String const &add) {
        *s += add + sep;
        return *this;
    }

    appender_t operator++() { return *this; }

    appender_t &operator *() { return *this; }
};

template 
appender_t appender(String &s, String sep) {
    return appender_t(s, sep);
}

Most of this is boilerplate--the only parts that really implement any logic at all are the constructor and `operator=`. The constructor is still pretty trivial: it just saves a pointer to the two strings used to initialize it. The assignment operator isn't much more complex--it just says when a string is written through the iterator, we append that string plus the specified separator to the string we stored.

Using this, the rest of the code barely changes at all. We define our output and iterator a tiny bit differently:

    std::string path;

    auto out = appender(path, "/"s);

From there, however, virtually nothing has changed (which is pretty much the point of using iterators to start with--they isolate the algorithm from the container, so algorithms can work with different kinds of containers.

So anyway, using that we can eliminate the pesky `std::stringstream` intermediary, so we're just appending directly to a string, just like we were to start with--but now doing it with algorithms that actually fit the task at hand.

A complete, working copy of the final code is available on Coliru.

I should probably add that this code is purely an attempt at producing exactly the same result as the code in the original article. As Luigi Ballabio was kind enough to point out in a comment, that's not really the right thing to do.

Do Quora users actually have brains at all?

Right now I'm somewhat ashamed to admit it, but I have an account on Quora. Every week (or so--I don't pay very close attention) they send me an email digest of popular questions and answers. It might be an exaggeration (but if so, only a fairly small one) to say I was shocked by the question and answer that were most highly featured in their most recent email.

The question was: "Why do Americans seem to be so scared of a European/Canadian style of healthcare system?" The top-voted answer (at least as I read this) is: "In a word - fear" (yes, I cut and pasted that--if you think I must be making this up, I'd consider that entirely forgivable). Now, it's true that the author does go into more about detail about what he thinks drives that fear, but "fear" is what he gives as the actual answer. So, "Why do Americans seem to be so scared" is answered with "fear", and (at least as I write this) that has received literally thousands of up-votes.

Unfortunately, the "answer" goes downhill from there. The author (a "Dan Munro", who gives an unsupported claim of "knows some healthcare stuff"). He gives four supposed reasons for his claim of "fear":

1. A false assumption (with big political support) that a system based on universal coverage is the same thing as a single payer system.
2. A fear of "rationing" - which was set ablaze by Sarah Palin and her cavalier remarks about "death panels."
3. An attitude and culture of what's loosely known as American Exceptionalism.
4. A fierce independence that has a really dark side (which he goes on to explain as an attitude that when/if anybody "fails", it's considered their own fault).

To put it simply, I've yet to see any real support for any of these. The only one that seems to have even the slightest basis in reality is the second. It us true that a few (Sarah Palin being the most obvious) have tried to generate fear on this basis. It may even be true that it has succeeded in at least some tiny number of cases. The vast majority of people who oppose (further) government regulation of healthcare, however, seem to find it nearly laughable.

The most ridiculous, by far, is the claim of "American Exceptionalism". While frequently advanced (relative to an almost surprising range of subjects), this seems to be a pure straw-man at least with respect to this question. I have quite literally never heard anybody dismiss an argument on the basis that "it came from Canada, Europe, or outside the US in general, and we can't possibly learn anything from 'them'." At least in my experience, it simply doesn't happen. I obviously can't possibly know exactly what every single person in the US believes or feels, but I've yet to see or hear anything that gives even the slightest shred of support for this particular belief.

He then goes on to quote some of the usual statistics about how much of the US GDP is spent on healthcare, and a study about deaths from preventable medical errors in US hospitals.

Unfortunately, the numbers he quotes (210,000 to 440,000 annually) seem to be open to a great deal of question. Depending on which study you prefer to trust, the number is might be as low as 32,500 annually (and no other study I can find gives a number any higher than about 100,000 annually). Despite this, the largest number he can find is quoted as if it were an absolute fact that's not open to any question at all.

Worse, however, is a much simpler fact: he makes no attempt at comparing this result to the numbers for other countries, and (perhaps worst of all) he makes absolutely no attempt at telling us how the change(s) he apparently advocates would improve this in any way. So, even if we assume he's gotten the factual part right, we have absolutely *no* reason to believe any particular plan will improve it in any way.

Although I can't claim to speak for the US in general (or anybody else at all) in this regard, that leads directly toward a large part of the reason I have personally found it impossible to generate any enthusiasm for the plans that have been advanced to change healthcare in the US.

The usual argument seems to run something like this. The advocate starts by pointing to US citizens paying far more than others for healthcare, and having shorter average life spans. He then uses that to support his claim that we need to pass some particular health care plan he supports.

Unfortunately, nobody making such arguments seems to (even try to) "connecting the dots" to show exactly how or why *their* plan will improve the problems they ascribe to the current system. Virtually none can provide any real breakdown of US healthcare costs vs. costs elsewhere, to indicate exactly what is driving the higher costs in the US. Absolutely none (that I've seen) takes any next step toward showing how their plan will fix those problems.

When I've participated in a discussion, it usually runs like this:
Them: Our current system is broken. We need to pass bill X to fix it.
Me: What will X fix, and how will it fix it?
Them: Didn't you listen? It's really broken!
Me: Okay. What will X fix and how will it fix it?
Them: I'm telling you, it's seriously broken!
Me: Yes, I hear that. Now, can you tell me what X will fix and how it will fix it?
Them: [usually starting to get pretty loud by now] Damn it! What will it take to get it through your head that it's broken? Are you a complete idiot?

This seems to go on about as long as I'm willing to participate. I've yet to hear a single advocate of a single system actually answer a single real question about what it will fix, how it will fix it, what costs will be reduced, how much they will be reduced, etc. No matter how often you ask, even about relatively simple details of any proposed program, nobody seems to have a single answer about what they think it will accomplish, not to mention providing any reason for me to believe that it really will accomplish that.

If you'll forgive a (mildly) medically-oriented metaphor, Quora seems to be infected with a similar culture. Questions pre-suppose a given answer (in this case, that resistance to changes in health-care stems from fear rather than things like lack of information). This is certainly far from the only answer that seems to do little beyond echoing back the question, with only straw man arguments to support it, then a rather disjointed attempt at denigrating what the author dislikes, without even an attempt at claiming that his "solution" would really fix the supposed problem(s) he cites, not to mention actually providing anything similar to real evidence that of improvement.

So yes, although Quora users undoubtedly do have brains, it certainly appears to me that failure to actually put them to use is somewhere between common and rampant.

Considering questions more specifically about health care: I, for one, am fairly open to the possibility of reforming how healthcare is run in the US. So far, however, I've yet to hear anybody advance a coherent, understandable argument in favor of any proposed plan. Most simply seem convinced that the current system is *so* badly broken that absolutely any change would have to be an improvement. Even the slightest study of history, however, indicates that there is no such thing as a situation so bad that it really can't get worse.

Inheritance, templates, and database models

Some years ago (around 1991, as a matter of fact) I observed that object oriented programming, and C++ in particular, was following a path similar to that followed by databases decades before.

At the time, multiple inheritance had recently been added to C++. I noted that single inheritance corresponded closely to the hierarchical database model, and multiple inheritance corresponded closely to the network model.

As I'd guess most people reading this are well aware, most databases have long-since switched to (something at least intended to be similar to) the relational model and there are formal proofs that the relational model is strictly more powerful than either the hierarchical or the network model. That led to an obvious question: what sort of program organization would correspond to the relational model?

I would posit that C++ templates (especially function templates) correspond closely to the relational model. Rather than being restricted to situations like "X is derived from Y", we can instantiate a template over any type satisfying some relation--though in the case of a template, the relation is basically a set of operations that must be supported by the type rather than a set of values that must be stored in the database.

The major problem with templates (by themselves) is that we have very little control over how that matching is done. The matching criteria are difficult for most people to understand, and even harder to control. Even at best, the control currently available (e.g., via static_assert) is clumsy use and hard to read.

Concepts refine that capability considerably. Concepts are similar to defining foreign keys in a database. Right now, what we have is similar to a bunch of tables, with some fields (or sets of fields) in some of those tables used as foreign keys in other tables--but no declarations of what is supposed to be used as a foreign key, and therefore no way for the compiler to (a C++ equivalent of) enforce referential integrity.

As I'm sure most programmers are already well aware, a key (no pun intended) capability of a relational database is defining relationships between tables so the database manager can enforce referential integrity. That is similar to what C++ Concepts add--something at least roughly equivalent to foreign key declarations in a database, defining what relations are intended and should be enforced by the compiler.

Now don't get me wrong: I'm not trying to write a sales-pitch for Concepts, or anything like that. Rather the contrary, I think quite a few people have probably done a better job of explaining them and how they improve C++ than I've even attempted. What I find much more interesting is seeing (or maybe just imagining--others may disagree with my ideas) a fairly clear similarity between two types of programming that (I think) many probably see as quite unrelated or perhaps even directly opposed.

When is a question about a puzzle, and when is it really about programming?

The following question was recently asked on Stack Overflow:

This is the problem: There are two players A and B. Player A starts and chooses a number in the range 1 to 10. Players take turn and in each step add a number in the range 1 to 10. The player who reaches 100 first wins.

In the program, player A is the user and player B is the computer. Besides that the computer must force a win whenever possible. For instance, if the player A reaches 88 at some point, the computer must choose 89, as this is the only way to force a win.

A user then voted to close the question, with the comment that it was about a logic or math problem rather than about programming.

Personally, I disagree with that. In fact, I think it's an unusually good example of a problem for learning to program.

Allow me to digress for a moment. The first step in learning to program is learning to take some algorithm, and transcribe it into the syntax of a chosen programming language. Now, it's certainly true that being able to express an algorithm in a chosen programming language is important. It's not just about syntax either. Just for example, expressing an algorithm well often involves knowing a great deal about the accepted idioms of that language as well. Nonetheless, the whole business of simply writing code is only the last step in a larger, usually much more involved process.

That larger, more involved process deals primarily with finding solutions to problems. Only once we've found a way to solve the problem can we write code in our chosen language to carry out that solution. Now, it's certainly true that in many cases, we want to use an iterative approach to a solution -- we don't expect the first code we write to be the final an ultimate solution to a real problem for real users. Nonetheless, when we write code, we need to write it to do something, and we need to decide on that something before we can write code to do it.

Now, the question already notes that 89 is a winning "position". That immediately leads us to two questions: 1) why is it a winning position? 2) Based on that, can we force a score of 89?

The answer to the first is simple: 89 is a winning position, because from there our opponent can't reach the goal of 100, but no matter what move he makes, in the subsequent move we can reach 100. That is so because 100-89 = 11. The smallest move the opponent can make is 1 and the largest is 10, so no matter what he chooses, the remainder will be between 1 and 10, and we can win.

That leads fairly directly to the next step: we can force a score of 89 if we can reach a score of 78 -- and we can force a score of 78 if we can reach a score of 67 (and so on, counting backwards by 11 until we reach 12 and finally 1.

Therefore, the first player can force a win if and only if he chooses 1 in his first turn. If he chooses anything larger, the second player can choose a number that gives a result of 12, guaranteeing himself the win.

This is a large part of why many of the better computer science programs have classically used (more or less) functional languages like Scheme, and emphasized recursion as a basic primitive. It's not really about recursion as a flow control primitive or anything like that. Yes, we've known for years that a for loop, while loop, etc. can be expressed via recursion (and likewise that anything we can do with recursion can also be done via other flow control primitives).

What's important isn't that recursion allows arbitrary flow control. What's important here is the way of thinking about and approaching the problem. Recursion just gives a simple and direct way to approach the problem: instead of solving for 100, if we know that 89 is a winning position we can solve for 89 instead. Note: we could just about as easily think of it mathematically. Instead of thinking of this as a case of recursion, we could think of it as an inductive proof. The steps I've outlined above are essentially the same as those for an inductive proof.

Now, it's certainly true that this approach isn't suitable for every programming problem. If you're dealing with something like: "why is this text field being computed as 134 pixels wide when it should be 135?", chances are recursion isn't going to enter into your thinking, and might not be a lot of help if it did.

Nonetheless, if you're trying to solve a problem, and can define one step toward a solution, chances are very good that an inductive/recursive approach will be useful in solving the whole problem. It's most obvious in a case like this where the problem and solution are mathematical, so we have a well-defined line from problem to solution, but it can also apply to quite a few other cases as well (including the previous problem about text width, which it's sometimes useful to think of in terms of "some arbitrary string followed by one character", and continue with shorter and shorter strings until we reach only one or two characters).

Word frequency counting

Eric Battalio recently posted about Jumping into C++. Like many people who've written C++ at times, I found his post quite interesting and entertaining. A fair number of people posted their own ideas about how to accomplish the same task -- some concentrating on minimal source code, others on maximum speed, and so on.

After seeing his follow-up After the Jump, I decided one point could stand being addressed. In his followup, he says: "About reading a file using iostream. Don't. It is slower and difficult to manage for complicated file formats. This application was trivial but I will avoid in the future."

On this subject, I have to disagree. Iostreams do have some shortcomings, and some implementations are also (un-)fairly slow. Nonetheless, they also have some pretty major advantages if (a big if, here) you use them well. I hope he won't feel insulted if I point out that (at least in my opinion) there are better ways to use iostreams than the way he did it.

For those who haven't read his posts, the task he set was quite simple: count the unique words in a file. He decided to do a bit of parsing, however, so that something like "one,two" would not include the comma. Unfortunately, he didn't (IMO) do this very well, so that would be counted as "onetwo" instead of treating "one" and "two" as separate words.

That brings up the obvious question: can we read those correctly, without doing extra parsing to patch things up after the fact? Of course, there's not a whole lot of suspense -- pretty much anybody with an IQ higher than a mosquito's can probably figure out that I wouldn't ask the question in the first place unless the answer was yes.

The way to do this (or the way I'm going to advocate in this post, anyway) depends on part of how iostreams are designed. When you read a string from a stream, any leading whitespace characters in the stream are ignored, then non-whitespace characters are read into the string, and reading stops at the first whitespace.

About now, you're probably thinking: "Yes Jerry, we already got past the 'IQ higher than a mosquito's' question; I already knew that!" What you may not know, or at least may not have seriously considered (though a few of you probably have) is exactly how the iostream determines what is or is not whitespace. The answer to that is a little complex: the iostream has an associated locale. The locale, in turn, contains a ctype facet -- and the ctype facet is what determines classes of characters.

So, to ignore those commas (and hyphens, etc.) we simply need a ctype facet that classifies them as white space, tell the iostream to use a locale containing that ctype facet, and we can just read words. Since it seems reasonable to me that (for example) "Jerry's blog" should be read as two words, not three, I'll classify upper and lower case letters and apostrophes as "alphabetic" and everything else as "white space".

Using that, the code we get code that's fairly simple, readable, and as a bonus, even a bit faster (though that wasn't really the intent).

Heaps and heapsort

Like most programmers, quite some time ago I'd read about heaps and the heapsort. Being a dutiful student, I could quote the standard line, saying that a heap was an implicit tree where node N was less than (or greater than, depending on the type of heap) nodes 2N and 2N+1. Like (I think) most, I'd also implemented a heapsort -- but to be honest, most of really came down to a line by line translation from the description in Knuth Volume 3 into the syntax of the programming language I was using at the time (Pascal, the first time around, and later the same again in C).

For years, given that I'd written a Heap sort that worked, I considered my knowledge of heaps and the heap sort entirely adequate. To be entirely honest, however, during most of that time I never really fully understood heaps. In particular, I never really understood the 2N and 2N+1 -- why those particular numbers/nodes? What was the significance of 2N and 2N+1? Why not 3N or 1.5N+65 or something? In short, that "implicit tree" had never really gelled for me -- I'd read the words, but never truly understood what they meant or how the "tree" worked.

For some reason a few months ago my lack of understanding on that particular subject bubbled to the top of the heap (I know: puns are the death of real humor) and I decided to implement a heap (and heap sort) entirely on my own, based only on my recollection about 2N and 2N+1. Instead of going to the book and translating syntax, I sat down with a supply of paper and pencils (the most underrated programming tools ever) and re-invented the heap and the algorithms to create and maintain a heap from first principles.

So, what did I do to finally and truly understand a heap? It ultimately came down to one piece of paper:

And from there came true understanding at last. If we arranged the nodes by layers, it "just happened" that the children of every node N were nodes 2N and 2N+1. Better still, after three layers of the tree, it was pretty apparent that as/if I added more to the tree, the same relationships would hold. Only 30 years (or so) after I'd first written a heap sort, I finally understood what I was doing!

I finally also understood why people who understood heaps thought they were cool: since the "links" in the tree are all based on (relatively simple) math, it's a tree you can walk almost any direction you'd care to think about by simply doing the right math. Just for example, in a normal binary tree, the only way to get from a node to its parent is to traverse down the tree, and remember the parent on the way there so when you need it back, you can recall it from wherever you have it stored. Likewise, getting to the sibling of a node requires that you get back to the parent (see above) and then take the other branch downward to get to the sibling.

With a heap, however, both of these are simply trivial math: the children of node N are nodes 2N and 2N+1, so the parent of node M is node M/2 (using truncating/integer math). Likewise, the sibling of node N is either node N+1 or N-1 -- if N is even, the sibling is N+1, and if N is odd, the sibling is N-1.

So, for any given node, we can walk through the tree up, down, or sideways (literally) with a single, simple math operation. Better still, all the nodes are contiguous in memory, with no space used up on links, so it's also pretty cache-friendly in general.

There was one other point I ran into repeatedly as I worked at understanding what I was doing well enough to produce working code: the math all depends on 1-based indexing. Making it work right with 0-based indexing like most currently languages use was not trivial. In fact, I finally decided that for this purpose it was better to maintain the illusion of 1-based addressing for most of the code, and since I was writing this in C++, have a truly trivial class to handle the translation from 1-base to 0-based addressing (i.e., subtract one from every index I used). As simple of an operation as that seems like it should be, keeping it in one place still simplified the rest of the code tremendously (and made it much easier to see the relationship between the code and that fundamental 2N/2N+1 relationship that defines the heap).

Anyway, in case anybody cares to look at the resulting code, I've decided that trying to post significant amounts of code directly here is too painful to be worthwhile, so here is a link to it on ideone.com. I think this is long enough for now, but sometime soon I'll probably write a post going through that code in more detail, explaining how it works and why I did things the way I did.

Adventures in monitors

Friday I broke with my usual habit of staying home on the big shopping days, and went to Best Buy. I had some store credit, and was (and should still be) working on a project where I'd get a pretty major benefit from having another monitor attached to my computer. Besides, while my current monitor was quite high-end when it was new (a LaCie 321), it was getting quite old -- something like 7 or 8 years, if I recall correctly. Over the last few years, nearly anytime somebody heard about my ancient monitor, they'd tell me about how much better monitors had gotten since then, so even a really cheap, entry-level monitor would be a huge improvement.

In terms of specs, almost an new monitor should be a pretty serious upgrade. Just for one obvious example, the LaCie is only rated at 500:1 contrast ratio. Definitely pretty unimpressive compared to the ratios claimed by nearly all new monitors (anymore, the bare minimum seems to be at least a few million to one, and five or even ten million to one isn't particularly hard to find). Granted, those are "dynamic" contrast ratios, but the static ratios are still better than my ancient LaCie

After looking around a bit, I found an HP W2071d, which is a 20" wide-screen monitor, that was marked down to only $79.95 (from a list price of $149.95, for whatever that's worth). Seemed like a decent enough deal, so I picked one up, brought it home, and connected it up. As usual for me, just about as soon as it was connected it up, I pulled out my trusty Eye-one display 2 and calibrated it so the brightness, contrast, color (etc.) should match up with the LaCie (in case anybody cares: 5200K whitepoint, 110 cd/m² luminance, gamma of 2.2).

Anyway, let's get to the meat of things: just how big of an improvement did the new monitor bring? Well, let me show you a couple of pictures. The HP is on the left, the LaCie on the right:

Here, the two don't look drastically different -- the background in both is reasonably black (though in person, the background of the LaCie is definitely blacker). The picture on the HP is a bit dark, but not too terrible. But now look what happens when I quite crouching down quite as far, and aim the camera down at the screen at something like a 30 degree angle:

Now, especially toward the bottom right corner, the HP's background isn't even close to black. Despite a higher claimed contrast ratio (600:1 static, 5000000:1 dynamic) the contrast between the picture and the background on the HP is looking pretty minimal. Worse, while the picture looks pretty much the same from either angle on the LaCie, on the HP it's gone from a bit dark and shadowy to completely washed out -- to the point that the stripes on the sweater have almost completely disappeared!

My conclusion: both the specifications and people claiming current entry-level monitors have surpassed high-end monitors from yesteryear are basically full of crap¹. The new monitor undoubtedly works for spreadsheets or word processing, but the LaCie retains a significant edge in contrast, color accuracy and ability to view from different angles.

¹ No, I'm not accusing HP of lying in the specifications -- I'm sure under the right circumstances, it meets its specification. Nonetheless, even after years of regular use, the blacks on the LaCie look deep and rich, while those of the brand new HP look weak and wimpy at best.

Software patents, part II.

In my last post, I promised a post about what I think needs changing in the patent system. This necessarily gets considerably more detailed, so it's likely to be harder to apply it to different patent systems. Nonetheless, when people talk about problems with software patents, the US seems to be (by far) the most often cited culprit, so I doubt that being specific to it is really a major problem. Anyway, on with the show.

The first problem I see is that the US patent office is basically run as a business -- it's profitable to the government, and most of the profit comes from issued patents. Worse, what's really intended to be the primary job of the patent office (searching through prior art to figure out whether something is really original) is apparently run at a loss. The profit comes from "maintenance fees" on patents after they're issued.

The patent office has suggested a way to try to streamline the patent examination process that would involve the inventor either citing only a few sources of related art, or (if they know of too many) specifically pointing to those they think are most relevant, including specific citations of the parts they consider relevant.

At least to me, this seems utterly insane. First of all, it's simply attempting to shift the burden of the patent office's job from the patent office to the inventor. Second, it's asking the inventor to predict what the patent examiner will find the most useful. If, for example, the patent examiner looks at some other reference and finds it more relevant than the ones the applicant pointed to as most relevant, would the patent become invalid? If so, the patent system basically becomes a lottery. But, if there's no penalty, what's to prevent an applicant from citing something utterly irrelevant as the most relevant art related to his patent?

The simple fact is fairly simple: as it stands right now, the patent office simply isn't complying with the requirements of patent law. The law says the fees they charge should cover the cost of examining the patent. If their fees aren't high enough to do that, then the fees need to be raised. Another point that's routinely cited is that an examiner has only about 20 hours to examine a given application (there's some disagreement about the exact number, but at least it's at what I'd consider the noise level -- there's little question that it's between  15 and 25 in any case). Another common complaint is that patent examiners simply aren't competent -- that they often just don't know enough about the technology to sort out (for one example) truly new techniques from simply new and different terminology for existing techniques.

These have a simple solution though: simply increase the fees for a patent application to the point that they can/will cover the costs of hiring competent examiners, and giving them enough time to do a good job. Along with funding the process properly, higher fees, all by themselves, would probably do quite a bit to encourage companies to look more carefully at their applications before filing, to ensure that what they're filing is truly novel and useful, before wasting others' time finding prior art to show that it's invalid.

The second major problem I see is that it's much easier to get a patent granted than to get that same patent invalidated after it's been granted. The patent office has been taking some steps that attempt to balance this a bit better, but at least personally, I don't think they've done quite enough yet.

Classically, the situation was that the inventor filed his application, and the patent examiner (usually only one, though sometimes two) tried to find prior art. Under most circumstances, almost nobody else participated in the process at all. The patent office does now publish (most) patent applications, so normal people can review them, but it's still basically provided as a one-way communication -- if you look at an application on the patent office's web site, there's not (for example) a button on the page to let you send an email to that examiner citing what you think is prior art on that patent application. Right now, however, instead of treating prior art submissions as what they really are (normal people doing them a favor to make their job easier) they seem to treat it as if they're doing me a big favor by allowing me to submit anything at all, and it's perfectly reasonable to make me jump through flaming hoops before I can be granted such a privilege.

Even so, the patent office follows a "preponderance of the evidence" rule in deciding whether to issue the patent. That basically means only a simple majority of the evidence needs to point toward its being novel for the application to be accepted, and the patent to issue. If 51% of the evidence says it's original, and 49% says it's not, the patent can be issued. Keep in mind that in most cases, it's up to one person to find any and all evidence of invalidity (in roughly 20 hours of work or less), but a large company may easily have a dozen people working hundreds of hours (if necessary) to get the patent issued, and it's quickly apparent that the system is heavily loaded in favor of issuing the patent unless it's quite obviously bad (and sometimes even if it is quite obviously bad).

Once the patent issues, however, the courts are required to give the patent a presumption of validity. To invalidate the patent, you don't simply need to provide a preponderance of evidence in the other direction. It's not enough at that point to show that 51% of the evidence points toward invalidity, and only 49% toward validity -- instead, the courts require "clear and convincing" evidence that the patent is invalid before they will declare it invalid. I've never seen a court attempt to specify a percentage of the evidence necessary to meet the clear and convincing hurdle, but it's clearly a lot higher than a mere preponderance of the evidence. If I had to characterize it, I'd probably put the number at around 90% -- still somewhat short of the "beyond a reasonable doubt" (that's supposed to be) used in criminal courts, but much higher than than 51% used as the basis for issuing the patent in the first place.

We end up with a system that deprives most people of much ability to provide evidence that a patent application isn't valid, issuing the patent even when/if there's a substantial chance that it's not valid, and maintaining it as valid even when most of the evidence indicates that it's really not.

Though I don't think those are (probably) the only two problems with the patent system as it stands today, I think addressing those two points would go a long ways toward redressing much of the current imbalance in the patent system. Interestingly, neither of these requires any change to the actual patent laws at all, only changes in procedures about how the existing law is enforced. Over the past several years I've seen many proposals that included what initially seem like much larger changes (nearly all including substantial changes to the patent law itself). I believe most of these would do little to cure existing problems, and quite a few would add many more problems of their own as well.

From a programmer's point of view, most of the proposals strike me as doing nothing to try to find or fix actual bugs, and instead advocate changing indentation and naming conventions throughout the code. They'll change how the code looks, and might (conceivably) make it more readable, to at least some degree, but they're almost certain to introduce at least a few new bugs in the editing, but fail (except, perhaps incidentally) to fix existing bugs. Just as with code, to do real good, you need to identify the real problems, prioritize them, and (usually) attempt to make the smallest changes that fix those problems.

I'd also note that almost none of this is specific to software patents at all. Most of the problems I see apply at least equally to areas outside of software. As noted in my previous post on the subject, I think most of the arguments attempting to separate software patents from other patents lack merit.

Why most programmers are wrong about software patents.

Many (probably most) computer programmers favor elimination of patents that apply to software. I believe, as is often the case, that they're well on their way to repeating a dark history they've blithely ignored.

Patents were invented as a service to society -- the basic intent was (and remains) fairly simple: give an inventor exclusive rights to his/her invention for some limited period of time in exchange for agreeing that as soon as that limited period of time expires, the invention goes into the public domain -- anybody can freely use it. By itself, that wouldn't mean much: after all, if the patent didn't exist to start with, anybody would be able to make free use of the invention immediately, instead of waiting for the patent to expire.

The benefit to society comes from another requirement for a patent: that the patent describe the invention so others can use it. The exact phrasing varies by country, but in the US the requirement is that the patent contain a description of the invention sufficient for a person of ordinary skill in the art to implement the patented invention.

Going a step beyond that, US patent law also includes a "best mode" clause that says the inventor must reveal what he believes to be the best method of implementing/deploying/using the invention. For example, if he's thought up a new type of oil for lubricating automobile engines, he can't patent it, but in the patent claim that it's intended to be used as cooking oil (which could deprive society of the benefit, because they ignore it after finding that it makes food taste terrible). Obviously the example of a cooking vs. lubricating oil is a bit extreme, and probably easily seen through -- most people would probably think something was a bit odd about Exxon patenting what they claimed was a cooking oil, for example.

Anyway, let's take at least a quick glance at that dark history they're ignoring. Before patents were invented, most crafts were governed by guilds. To learn how to carry out a particular craft, you had to be admitted into the proper guild. The guild guarded the secrets of its craft quite carefully in most cases -- to the point of sometimes murdering people who were suspected of revealing guild secrets, and refusing admittance to others because they were seen as too dangerous. In other cases, there were literally wars between competing guilds. These not only get people killed, but in some cases when a guild was destroyed, its secrets died with it. Archaeologists have found artifacts showing techniques we don't quite know how to duplicate to this day.

As many problems as they had, guilds were a substantial improvement over the previous system: one of individual craftsmen keeping secrets entirely to themselves, to be passed onto their children, sometimes on their deathbed -- or taking their secrets to the grave, if their children weren't handy at the right time, or were estranged, etc.

Most arguments programmers level against this fall into three broad groups. The first is that programming techniques (algorithms, protocols, etc.) get published even when there are no patents. The second is rarely quite so clearly articulated, but basically comes down to the notion that if one person invented something, they can invent something at least equally good when and if they need to. The third is that software moves so quickly that by the time a patent has expired, it's no longer of any value.

The first is partly true. They can point, for example, to the fact that European companies continue to publish despite the European policy against software patents. This, however, ignores reality. What's happening right now is that Europe is basically "freeloading" off of the patent systems of other countries (US, Japan, etc.) If, for example, Seimens or Philips wants a patent in the US and/or Japan, they need to publish all the details of that invention in their US/Japanese patent application. That means the invention is no longer secret -- and given current communications, the minor detail that it's published in the US/Japan instead of somewhere in Europe adds (at most) a few milliseconds for a European citizen to download the patent application. As such, Europeans enjoy the benefit of inventions being published, without (themselves) giving the inventor anything in return.

The second strikes me as simple conceit. Yes, there are patents running the gamut from utter stupidity to simply being something nobody else thought was important or original enough to bother patenting. Being at all honest, those constitute only a fairly small percentage of patents overall though. Much of this stems from a problem I've seen many times: somebody will draw a badly mistaken conclusion about what the patent covers, often based on looking at nothing other than the patent's title. They see a title that says something like "A method for run-length compression", and they think something like "good lord what insanity -- everybody's known about RLE for ages -- obviously the patent office is a bunch of idiots!" Though it's barely possible they're (at least sort of) correct, and this really is a patent on something everybody's known about for decades, chances are it's something else entirely -- some (possibly minor) improvement that allows the job to be done a little faster, or using a little less memory, etc. In a typical case, it's not earth-shaking, but is original and at least mildly useful.

The third argument may sometimes have some degree of validity as well, but often doesn't. This argument, however, ignores that fact that if the invention becomes obsolete quickly, the cost of the patent (to the people) is also low -- if an invention is only meaningful for a year or two, the cost to society of the fact that an inventor (theoretically) gets exclusive use of it for years afterwards costs society essentially nothing. At the same time, people have invented and patented algorithms that retain value well after the patent expires. An obvious case in point would be RSA encryption. The US patent on RSA expired well over a decade ago, but it's still almost certainly the most widely used from of PK cryptography. RSA remains (roughly) as valuable today as ever, although there are alternatives that could be used if RSA were not available.

Now, don't get me wrong: I don't think the US patent system (or probably any other) is anywhere close to perfect. Some time soon, I'll write a post about what I see as problems in the system, and at least some ideas about how to fix those problems. To give fair warning: I believe many of the problems can be fixed with much less drastic changes than most people seem to think are necessary. In fact, some of the changes are (or at least initially seem) so minor that they're probably almost invisible except to attorneys who specialize in intellectual property law. Nonetheless, I think some seemingly trivial modifications can have fairly serious consequences.

C++ dynamic arrays

I've seen dozens (at least) of questions and proposed answers about how to create a dynamic array in C++. The typical reply recommends using the array form of the `new` operator to allocate space, something on this order (but usually less complete):


template
class dynamic_array {
    T *data;
    size_t size;
public:
    dynamic_array() :data(0), size(0) {}

    dynamic_array(T *init, size_t i_size) :size(i_size) {
        data = new T[size];
        for (size_t i=0; i<size; i++)
            data[i] = init[i];
   }

    bool add(T const &new_item) {
        T *temp = new T[size+1];
        for (size_t i=0; i<size; i++)
            temp[i] = data[i];
        ++size;
        delete [] data;
        data = temp;
    }
     
    T &operator[](size_t index) {
         assert(index < size);
         return data[index];
    }
    // We also want a const version of operator[].
    // We also probably want something like get()
    // in std::vector, that throws if index is out of bounds.

    size_t get_size() { return size; }

    void clear() { size=0; delete [] data; }

    ~dynamic_array() { delete [] data; }
};

Now, it's certainly true that you could do worse than this. I believe it manages memory correctly (doesn't leak memory or create dangling pointers), and it is dynamic (to some degree -- it allows adding, but not currently removing, elements dynamically). While it's not currently written to be exception safe, that's mostly to keep it from getting too long -- making it exception safe wouldn't be particularly difficult.

It still has some pretty serious problems though. First of all, it requires that T be default constructible and assignable. Assignable isn't so bad (though in C++11, we'd prefer movable), but default constructible is kind of a pain, especially since we never actually *use* any default objects -- but when we expand the allocation, we have no real choice but to default construct the objects, then assign each value from the old array into the new one. That can be a pretty serious burden if creating a default object is slow, and worse still if assigning objects is slow as well. Since it's a template, we don't know much about T. Either or both might be true.

That points to a much bigger problem: adding an item to the array is slower than we'd like, and the bigger it gets, the slower adding items gets. In computer science terms, adding a single item has complexity that's linear on the current size of the array.

Unfortunately, we can't just do a minor rewrite inside of add() to improve the situation. In fact, the basic premise of how this dynamic array works turns out to be wrong. The only way to fix the biggest problem is to start over with something that works a bit differently from the beginning.

Our big problem here is that when/if we use `new whatever[size]`, we not only get enough space to store the specified number of objects, but code is inserted to create that number of objects in the storage. Generally speaking, we don't want that. Unless we change the interface at least a little bit, there's never a circumstance in which we really want objects in that memory. Even if they're created, immediately after allocating those objects, we're going to assign some other object to that position anyway. We'd really prefer to copy construct the new objects from the old objects (or, in C++11, move-construct). This way a new object is created with the correct value instead of being created with a value we know is wrong, then immediately assigning the correct value to the new object.

We'd also prefer to avoid re-allocating space every time we add a new item. We really want to allocate a chunk of raw memory, turn that raw memory into new objects as they're added, and only allocate more space once in a while, when our memory is all used up.

Using new T[size] won't let us do either of those though. Instead, we need to use something (usually operator new, but malloc would also work) that lets us allocate raw memory, then use placement new to create objects in that raw memory.


template
class dynamic_array {
    T *data;
    size_t allocated;
size_t in_use;

size_t round_up(size_t input) {
size_t ret = 1;
while (ret < input)
ret <<= 1;
return ret;
}

void alloc(T *init, size_t current_size, size_t new_size) {
char *temp = (char *)operator new(new_size * sizeof(T));
allocated = new_size;
for (size_t i=0; i<current_size; i++)
new(temp+i*sizeof(T)) T(init[i]);
in_use = current_size;
data = (T *)temp;
}

void destroy(size_t b, size_t e) {
for ( ;b!=e; ++b)
data[b].~T();
}

public:

    dynamic_array() :data(0), allocated(0), in_use(0) {
alloc(0, 0, 10);
}

    dynamic_array(T *init, size_t i_size) {
alloc(init, i_size, round_up(i_size));
}

    void add(T new_item) {
if (in_use == allocated)
alloc(data, allocated, allocated * 3 / 2);
new ((char *)data + in_use++ * sizeof(T)) T(new_item);
    }

    ~dynamic_array() {
destroy(0, in_use);
operator delete(data);
}

    T &operator[](size_t index) {
        assert(index < in_use);
        return data[index];
    }

    size_t size() { return in_use; }

    void clear() {
destroy(0, in_use);
in_use = 0;
}
};

This is starting to run pretty long, so I'll leave further embellishment of this class for a later post. This is still quite a ways short of what std::vector already provides though -- thus the standard advice to just use a standard container if at all possible. Even for something as simple as a dynamic array, the amount of code involved becomes fairly substantial. For a more complex container like std::set or std::map, the savings is greater still.

Herb's wrong, I'm right, and here's why.

Microsoft's MSDN Channel 9 recently released a video of Herb Sutter, Andrei Alexandrescu, and Scott Meyers from C++ and Beyond 2012. In this video Herb (in particular) argues that further support for meta-programming should not be added to C++.

He points out (quite rightly) that meta-programming is basically used to add features to the language. He argues that rather than supporting meta-programming, we should look at what features meta-programming is used to implement, and add those features directly to the language itself.

In my opinion, there is really only one reasonable answer to this: wrong!

This is utterly and absolutely wrong for a number of reasons, most of which (interestingly enough) have been expounded many times before. One of the mantras of C++ development for years has been that the committee does not and cannot know all the purposes to which the language might be put. Rather than adding features to the language specifically for every individual purpose and each end user, there has been a concentration on adding features to support things like writing libraries so that adding a relatively small number of features can support a wide variety of uses.

Trying to look at all uses of meta-programming and find the features being created with it, then trying to add those features to the language would be a 180 degree reversal of this decision. The problems already cited would become all too real and all too problematic essentially immediately.

Consider what would happen if I wanted to write a library using features not currently included in the base language. My choices would be to implement that code using meta-programming, or else petition the committee to please, please consider my proposal for a new language feature. For the sake of argument, let's assume that the C++ committee starts to produce revisions twice as fast as they have in the past -- or than essentially any other ISO standard committee for any other programming language has either -- and produces an update every five years instead of roughly once every ten years.

That means, on average, the programmer has to wait 2.5 years before he can even get started on his library. Given that the standard is typically frozen for a year or so before being approved, it's really a bit longer than that, but let's just leave it at 2.5 for the sake of argument. I hope I don't have to spend any time convincing anybody that a two and a half year delay in getting started would be unacceptable for many projects.

That's probably the least of the problems though. Much worse is the fact that accepting any more than a minuscule number of such proposals would quickly lead to C++ becoming substantially larger and more complex. Virtually everybody agrees that C++ is already larger and more complex than anybody would like, and going this direction would unavoidably lead to amplifying that problem.

I do agree with Herb that the current meta-programming facilities have serious problems. The code itself, the compile times, and especially the error messages can all be truly horrific. More importantly, these aren't just remote possibilities; they happen on a regular and routine basis.

That does not, however, mean that template meta-programming in general is a problem and should be avoided. It means that the current facility has problems, most of which stem from the fact that its intent was never to support meta-programming at all.

These problems should not lead us to conclude that meta-programming is evil in general and should, therefore, simply be avoided entirely. They should convince us that the current meta-programming facilities are inadequate and in need of replacement. What we should be doing now is looking for a simple, small, relatively easy to understand set of features that will support meta-programming more sanely. I won't try to propound here exactly what features are necessary, much less what form those features should take. This is, however a basic engineering problem. It's the kind of thing that's been solved before, and can be solved again -- and while the result undoubtedly won't be perfect, it will be good enough to fix the problems that are now obvious (and probably quite a few nobody's thought of yet).

Early in the history of programming, many thought of it as a priesthood. It was liberated largely by improvements in tools and education. At least in my opinion, the situation here is similar.
I guess if I were a great leader of men, at this point I'd come up with some ringing phrases about "when faced with such a challenge, do we shrink in fear, or do we rise up and vanquish the foes of free computing everywhere?"

Since I'm an engineer, though, I'll simply reiterate that this type of problem has been met and overcome before, and can be again. What's necessary isn't vilifying template meta-programming or its current users, but to make sound engineering decisions to fix a problem in the most reasonable fashion possible to make meta-programming dependable, accessible, and understandable, so it becomes the tool that can fulfill the promise shown by the current uses of template meta-programming.

A rant on operating systems and development.

I guess I'm overdue on playing my role as an Andy Rooney imitator, whining about crap that should be taken out behind the barn and put out of everybody's misery.

This time I'm going to talk about operating systems. I think the operating system situation has gotten completely out of hand. Every one of them seems to be competing at being the worst it can be. I'm still using Windows, but only because the people writing OS/X, Linux, *BSD, etc., seem to be doing everything in their power to make them even less attractive than Windows, so I can't reasonably switch to anything else, no matter how much I'd love to.

Let's start with the fact that I'm a developer. Every operating system seems to be intent on making itself as hostile to developers as humanly possible. The new stuff in Windows 8 is (almost?) all COM based, and COM is one of those things pretty much guaranteed to make any developer with even a shred of self respect and/or sanity wretch uncontrollably every time he gets close to it. Think of the people who refuse to drink some particular liquor because of the time in college (or whenever) that they got horribly drunk on it, and then even more horribly hung over, and have never touched it since.

Well, COM is pretty much like that, except you don't even get that one night of having a little fun acting stupid first. COM is just a horrible hangover that starts from the first time you see it, and apparently won't ever go away! To make it worse, not only is COM itself badly designed, but virtually everything Microsoft does with COM seems to be even worse. You end up with a full page of code to do what should have taken one simple function call. Basing all that's shiny and new in Windows 8 around COM has to be just about the most colossally stupid blunder yet, from a company that seems to have adopted the military attitude toward blunders ("we must plan with exquisite care to ensure against any minor problems getting in the way of committing the most massive blunder in human history.")

"Okay", you say, "why don't you just switch to OS/X?" The answer is simple: in its own, entirely different way (yes, we all know, "different is good" -- but not this time) Apple has done even worse. Microsoft makes you deal with COM -- but Apple makes you deal with Objective-C. If COM is the hangover that never goes away, Objective C is the nightmare that never ends. Where COM is all very "real" and far to nitty-gritty, Objective-C has a bit of a surreal feeling (at least to me). Every time I write anything for MacOS, I get a little of that nightmarish "I just can't believe this" feeling. The problem is that in a nightmare, you eventually wake up, but with OS/X and Objective C, you get your face rubbed in the fact that yes, it really and truly is this badly messed up. The infuriating part is that they come close enough to doing things right that it seems like it must almost be an intentional bait and switch.

Well, perhaps Linux would really be the way to go. In a lot of ways, this *should* be the best choice. Unfortunately, for at least some of what I do, I wrote OpenGL code. On Linux, pretty much the only choice there is Mesa3D. The Mesa project has done some pretty amazing things, and accomplished a lot. Despite that, Mesa3D basically only implements OpenGL 2.1, and I really want support for OpenGL 4. Unfortunately, the gap from 2.1 to 4 is big enough that I can't very well just look the other way, or make do with what it provides.

If OpenGL was the only problem, I could probably manage to live with it, but that's a long ways from reality. Any programmer who's been around for more than a week or two knows about the holy wars between advocates of vi and advocates of emacs that have been going on since "eight megs and constantly swapping" was intended to refer to a simply massive amount of memory, rather than so little that modern script kiddies think "well, of course with only eight megs you couldn't hope to do anything!" In any case, having used both I'm fully prepared to say this: they're both right. Vi and emacs are both awful. The world would clearly be a lot better place if neither of these horrible pieces of garbage had ever been invented.

Now, for any non-programmer who might happen upon this (hunh? Why would a non-programmer read this?) I'll point out that programmers aren't merely religious about text editors. Many people who consider themselves religious might only go to church once or twice a week. Even people who devote their lives to religion rarely pray (or meditate, etc.) for more than 8 or 10 hours a day. A typical programmer spends about 16-18 hours per average day with his text editor (and may easily go 30 hours straight at times). Worse, unlike religious people, programmers absolutely demand immediate, tangible results from that time.

In short, a programmer who doesn't like the editor (or IDE) he's forced to use, is likely to become a bit like some crazed middle-ages crusader, starting to hate life, and trying to make everybody around him do the same. While there are alternatives to Vi and emacs available for Linux, most seem to be in about the same position as I'm dealing with right now about operating systems. They all suck so badly that everybody sticks with what they know, because everything else is too horrible to even contemplate.

Oh, before I leave off on Linux I should add a bit of a rant on one more thing: the other tool that programmers are stuck with using at times is a debugger. Pretty nearly the only debugger available for Linux is gdb. This horrendous piece of garbage is the one thing that can make the editors and IDEs available for Linux almost seem bearable. Yes, they're awful, but it's many times worse. Consider this: back in the early 1980's I did some programming on a Control Data mainframe, mostly using Fortran (and when I could, Pascal). This was roughly three decades ago, on hardware that was pretty much obsolete even then, using an operating system that was mostly a relic from at least a couple of decades before. Even so, its debugger was still better than gdb. It was bad (bordering on awful), but gdb is even worse. This particularly rankles because there were at least reasons for most of the shortcoming in Control Data's debugger -- but gdb doesn't have to fit (along with the program being debugged) into a machine with less than a megabyte of RAM, or somehow protect itself from the target program without benefit of hardware memory protection.

So, that takes us pretty much back to where we started. Much like with editors/IDEs, I find the very notion of continuing to deal with COM loathsome and horrible -- but all the alternatives seem to be even (quite a bit) worse. I'm still left wondering, though, why it is that everybody involved seems so intent on doing the job so badly. At least as far as I can see, Microsoft came to dominance by being the one company that did just a mediocre job instead of a truly awful one, but nowadays they seem to be doing things just as badly as everybody else. If just one OS could rise to the level of just being mediocre, I'm pretty sure every programmer around would flock to it, because even mediocre would be so many times better than the messes we deal with now.