Update 11 July 2010: The move was a lot more painless than I had anticipated, and is already done. If you’re reading this, then your DNS has updated and you are accessing the new server. Hooray! See below about user accounts if you missed the original announcement.

Sometime later this month, Nerdland will be moving. The content and URL of the site won’t change; only the hosting provider will. The new host will be a Rackspace Cloud Server. This probably doesn’t affect you directly unless you are one of the people to whom I gave a Nerdland “user account” with web hosting space and e-mail over the past eleven years. If you are one of those people, please read the next few paragraphs.

As part of the move, I’m going to take the opportunity to clean out a lot of cruft that’s been building up on the Nerdland server over the past half-decade since the last hosting change. Most of the user accounts that I provided for friends and relatives aren’t being used anymore, and aren’t linked from anywhere on the Internet, so there’s no reason to migrate them. Rest assured, nothing will be permanently deleted. I’m an incorrigible data pack-rat, so I’m of course going to archive and back-up everything, including what I don’t move to the new server. If you had data stored on Nerdland, you can always contact me in the future, and I will gladly send you a copy of your old files and unretrieved e-mail, or restore your data and account to the server.

If you do still actively use your Nerdland web hosting space and/or e-mail address, please contact me as soon as possible and tell me that, and I will ensure that all of your data is moved and set you up with an account on the new server. Otherwise, I will only be migrating data which is linked from elsewhere on the Internet (according to Google’s index) or has been accessed recently (according to the server logs).

The primary reason for this move is that there is a project that I’m currently working on (that I will post about soon) for which I am going to need a server, and the shared hosting service that Nerdland is currently running on is not up to the task. In particular, it requires custom software (which isn’t possible on a shared host to which you don’t have SSH access, let alone root access), and it requires faster response times than this frankly oversold server is capable of. But since my project’s server is not going to require all of the resources available to me on a Rackspace Cloud Server VPS instance, I figured I may as well save a bit of money by hosting Nerdland on the instance as well. Hopefully, as a result, Nerdland itself will also load and respond faster.

To be honest, I probably would have done something like this a long time ago, if only just to play with it, had I been aware of the Rackspace Cloud before last month. Until I began researching hosting providers for this service that I’m writing, the only dynamic VPS provider that I was cognizant of was Amazon EC2. Not that there’s anything wrong with EC2, but it’s minimum instance size is 1.7 GiB of memory and 160 GB of disk space, which is far more than I would require for experimentation or a personal project, and it comes with a price to match. Rackspace’s VPS instances can start as small as 256 MiB of memory and 10 GB of space, at very reasonable prices, which will allow me to pay for more as I need it without having to lay out a fortune just to start.

Aside from having the resources I need to host my project and my website, it will be a lot of fun to have root access to an always-up server with a fixed, public IP once again. It already reminds me of the bad old days of the late 1990s and early 2000s, when I hosted Nerdland from Osric, a spunky little computer under my desk connected to the @Home Network (I still remember the IP: 24.3.98.206). Before @Home collapsed and I lost my static IP, I experimented with installing and running just about every sort of server under the sun on that dusty old box.

Dynamic DNS just wasn’t the same, and these days, electricity costs alone make it a bit silly to run a separate computer on a consumer-grade broadband connection rather than just paying for a real server. So finally, with the advent of affordable cloud-based VPS hosting, I can regain all the benefits of a real server once again. And now that I’m a more educated and accomplished programmer, I can instead experiment with writing my own software to run on my shiny new (virtual) box.

This brings me to the word “code”.

Used in its computer programming sense, “code” is always a mass noun in English: “I stayed up writing code until midnight.” “I had to read through four thousand lines of code to find the bug.” “Dammit, what is wrong with all of this code now?” Code is thought of as an continuous mass. Code is what you pour into the engine of your computer to make it run. Aside from the very first few instructions that run as part of your system’s bootstrap, no code stands alone, and you can’t divide code without encompassing it in some larger concept. You can have “two programs” but you can’t have “two codes.”

This sense of the word “code” likely derives from the older sense in which “code” is a synonym for “protocol”, or “structured communications mechanism”, e.g. “Hamming code“, or “Morse code“. Code is the protocol which the programmer uses to communicate with the computer. It has a usually rigid syntax, and its purpose is to give the programmer a mechanism for specifying what he or she wants done in a manner that a dumb box of circuits can make sense of. Code is a series of very clear, unambiguously meaningful instructions.

But the word “code” has other definitions. One is a synonym for “laws” or “rules”, but the other, as listed in Merriam-Webster online, is

3 b: a system of symbols (as letters or numbers) used to represent assigned and often secret meanings

Of all the meanings of the word “code”, this is the only one that functions as a count noun: “What is the code to open this lock?” “During World War II, British spy agencies cracked dozens of German codes.” “The teenage girls devised four different codes to use in passing notes.”

This is why it always disturbs me just a little when I read programming questions or discussion in which someone uses “code” as a count noun: “Please send me the codes.” “What are the codes for displaying a context menu?” “What is wrong with these C++ codes?” I’m sure many of these are simply non-native English speakers who are doing their best to work in this baroque tongue of ours, but I can’t help but shake the feeling that some of these people are native English speakers who are conflating the two senses of the word “code”.

The reason that this disturbs me is not because it’s some grammar peeve of mine. Rather, I suspect that native or fluent English speakers who use “code” as a count noun are subtly revealing their perception of code as something secret and unknowable. For example, the aspiring programmer who asks “What are the codes for displaying a context menu?” might be thinking that there is some particular set of magical incantations hidden somewhere in a dusty, forgotten tome which need to be recited precisely in order to conjure up a context menu. Similarly, one who requests that I, “please send [him] the codes,” is more than likely not interested in understanding how to accomplish the task he is asking about, but is instead interested in obtaining what he sees as an opaque sequence of characters that, when compiled, will make the computer do what he wants.

In short, the use of “code” as a count noun, rather than a mass noun, and when not explainable by imperfect mastery of the English language, is a potential red flag for impending cargo cult programming (which I consider one of the biggest issues in Computer Science education, and have complained about before).

But the little stuff can trip you up just as easily, and if you don’t have a solid understanding of the different facets of cryptography, you may well think that a system meets your security requirements when it does not. After all, modern cryptography is just mathematics. There’s no inherent application for it. Security isn’t a tangible property either; it’s an umbrella term for a whole class of goals. Rather, privacy, authentication, identification, trust, and verification — mechanisms of applied cryptography — are what provide the most commonly desired types of security. Understanding what these terms really mean, how they are implemented, and how they are different is essential to a true understanding of how encryption works to assure your security on the Internet, and even within a single computer.

This article assumes you are familiar with the fundamentals of cryptography: that you know what constitutes encryption, that you know what a key is, and that you know the basic difference between symmetric key cryptography and public key cryptography. I am concerned with describing and clearing up some misconceptions about the practical applications of cryptography to modern computing.

1. Privacy

Privacy (or “secrecy”) is the cornerstone of applied cryptography. A commonly desired form of security is making data readable only by certain intended recipients. Whether symmetric or public key cryptography is in use, a person (or machine) proves that they are an intended recipient by possessing the key that can be used to decrypt the message. In the case of simply achieving privacy, it really doesn’t matter whether symmetric or public key encryption is used; public key encryption is very slow, so in practice, it’s only used to encrypt a symmetric key that is used to encrypt the rest of the data.

Privacy is commonly desired when sensitive data is being transmitted. In the case of web browsing, this is one of the purposes of the Secure HTTP (HTTPS) protocol. When communicating with, for example, your bank’s website, it is important that the information being transacted is private. It is highly undesirable for any other person, even a professional network administrator at your ISP, who happens to control a computer on the Internet through which the data between you and your bank passes, to be able to look at your account numbers and balances.

Similarly, if you store sensitive corporate information or highly personal documents on a laptop, you would want to make sure that these documents remain private if the laptop were ever lost or stolen. For this, you would encrypt the files (or better yet the entire hard drive) and either keep the decryption key outside of the laptop, or keep it protected with a strong passphrase. In the latter case, the passphrase itself is the key to a cryptographic algorithm will provide the unencrypted version of the decryption key for your files or hard drive, and the passphrase is ideally stored only in your head.

This is privacy: no third parties can read your data. No more, and no less. A common problem is that users, even technically savvy users, often make the false assumption that privacy implies authentication and verification. While the ability to create privacy is a prerequisite for authentication and verification, and they are often used in conjunction, it is not the case that obtaining privacy implies that the other two types of security have also been obtained.

2. Authentication

Authentication is the act of proving who you are, or challenging someone else to prove who they are. The underlying technology for modern authentication schemes is public key cryptography. I said earlier that I was assuming familiarity with public key cryptography, but let me reiterate the most salient aspect of it for the purposes of authentication: In public key cryptography, only Alice’s private key is able to decrypt messages that have been encrypted with Alice’s public key, and only Alice’s private key is able to create encrypted messages that can be decrypted by Alice’s public key. Specifically, a message encrypted with any other private key will produce different (usually meaningless) unencrypted data if Bob attempts to decrypt it using Alice’s public key.

The fundamentals of authentication consist of a challenge-response exchange. If Bob presents (“challenges”) Alice with a piece of arbitrary data, and Alice responds with a piece of encrypted data that decrypts to Bob’s original arbitrary data when decrypted using Alice’s public key, this proves that Alice possesses Alice’s private key. Nobody else other than the person who possesses Alice’s private key (presumably only Alice) could produce encrypted data that would decrypt back to Bob’s initial data using Alice’s public key. If Bob presented Mallory with arbitrary data, and Mallory wanted to impersonate Alice, he could not; without Alice’s private key, he would not be able to produce the expected response that Bob was looking for.

It is clear from this, however, that authentication is only useful if you already know the public key of the person you are hoping to communicate with. One common application of cryptographic authentication on computer networks is Secure Shell (SSH) logins. Commonly, a user will install his or her public key on a server that they wish to log into via SSH, and will keep his or her private key on a personal machine. When logging into the server, the server challenges the client to prove that it holds the private key corresponding to the username that the client is trying to log in as. If the client satisfies the challenge with an appropriate response, the login is allowed without requiring a password for the user.

This is more secure and often more convenient than prompting for a password, since the private key is much harder to steal or guess than a password, and the same public key can be used on multiple servers with none of the security risks that apply to re-using the same password in multiple places. The same sort of thing can be done with web servers using something a little more complicated called a client-side certificate (see below about certificates), although these are uncommon on the public Internet and more often used on corporate intranets.

This is authentication: you can know with certainty who you are talking to. That is all; no more, no less. Note that this carries no implication of privacy. It is perfectly possible to authenticate your counterpart in a conversation and then proceed to have a non-private conversation. That wouldn’t be a common choice, but there’s nothing that prevents it.

More importantly, it is perfectly possible to have a private conversation without authenticating your counterpart. This is where a danger of a false sense of security lies. Bob could be talking over a perfectly private, encrypted connection, but if the person on the other end is Mallory and not Alice, Bob would never know that he is sending his sensitive data to, or receiving critical information from, a different and potentially malicious person.

In other words, just because you are sending your credit card number over a private, encrypted connection, doesn’t mean you aren’t unknowingly sending it directly to a criminal.

3. Identification

Identification is the aspect of applied cryptography that addresses the flaw in the above-described authentication process wherein you must know a priori the public key of the person you wish to communicate with. Perhaps surprisingly, this is the most complex common application of cryptography to security. If Alice and Bob wish to authenticate each other over the Internet, they must first exchange public keys. But they can’t just send them to each other over the Internet! If Bob received a message that purports to be from Alice and to contain Alice’s public key, he has no way to authenticate that the message actually came from Alice (and not from Mallory pretending to be Alice) without already knowing Alice’s public key. It’s a chicken-and-egg problem.

The direct solution to the problem is for Alice and Bob to exchange public keys off-line; to meet at Starbucks and hand each other CDs with their respective public keys on them. But this is not practical if Alice and Bob live thousands of miles apart, it is not practical if Alice is a banking institution and not a person, and it is still not practical if Alice and Bob do not already know each other.

If Alice and Bob are strangers (but still wish to authenticate one another) meeting to exchange CDs at Starbucks still, even if physically feasible, still isn’t secure. Mallory could show up at Starbucks a few minutes before Alice and, pretending to be Alice, give her public key to Bob, and now Bob will authenticate Mallory as Alice in future conversations. A way to fix this loophole is to have Bob check Alice’s driver’s license before accepting the CD. This is identification: you can know that a public key purporting to belong to a particular person or entity actually does.

Now, meeting in person and checking driver’s licenses is a human solution to a computing problem. There are of course computer-based solutions to this same problem that will also avoid the impracticalities of first having to meet in person with everyone whom you wish to authenticate later. But these solutions are based on the same principle as the driver’s license check: trust. The reason that Bob is willing to accept Alice’s driver’s license as proof that Alice is who she says she is because Bob trusts that the state government would not issue a license in a false name or with a false photograph (ignoring for the moment the possibility that the license itself is a fake and not issued by the state). Computational identification is based on the same notion of trust.

4. Trust

Ultimately, to accept that a public key belongs to the person it claims to, you must trust that it does. Trust can be simple, if for example the key was given to you in person by your friend Charlie who you are sure is not being impersonated by a shape-shifting alien. Trust can also be more indirect. If Charlie gives you his brother Dan’s public key, and you trust your that Charlie is honest and has good reason himself to trust that the key legitimately belong to Dan, then you can accept Charlie’s assertion that the key belongs to Dan as identification of Dan’s public key.

Computationally, this identification process is based on signatures and certificates. A certificate is like a driver’s license: it identifies a public key as belonging to a named individual, entity, company, or organization. The fundamentals of a certificate are simple. The person wishing to be certified generates a file with their identifying information (in a standardized format), and appends to it their public key. That’s all. But, of course, this certificate is worthless without trust. If a stranger just handed me a card saying “I am Alice, my public key is …”, I would not accept that as their identification, would you?

To be worth anything, certificates must be signed. I’ll get to the mechanics of signatures in the next section, but suffice to say that the goal of a cryptographic signature is to use a private key to produce a non-forgeable endorsement. If Dan produces a certificate for himself, and Charlie signs the certificate using his own private key, this functions as an assertion by Charlie that the contents of Dan’s certificate are accurate. Then, since I already trust my friend Charlie, Dan can simply present me with the signed certificate containing his public key to identify himself to me. I can check Charlie’s signature against Charlie’s public key (which I already have), and from that know that Charlie asserts that Dan’s certificate is accurate, and therefore that Dan’s purported public key actually belongs to him.

This is trust: you can know that a public key belongs to who it purports to by means of endorsement by a third party. What’s important is that this can all be done without ever actually contacting Charlie, beyond once to obtain and identify his public key in the first place.

Further yet, let’s say that Erin presents a certificate with her public key to me and this certificate is signed by Dan. If I trust that Charlie would only sign Dan’s certificate if Dan himself were trustworthy, then I can trust that Erin’s certificate is valid as well. This sort of peer-to-peer trust acquisition, where an identity certificate can be signed by any number of other individuals who trust the holder (with varying levels of expressed trust), is known as a web of trust, and is commonly used for personal communications amongst security-sensitive Internet users.

But most Internet users never encounter a web of trust explicitly, and don’t really need to know how it works. What they do encounter frequently, however, is the similar notion of a public key infrastructure. This is used to establish Secure HTTP (or, more generally, TLS) connections. When establishing a secure connection to, say, Bank of America, it really does no good just to make the connection private. You must authenticate that the server you are communicating with really does belong to Bank of America. The server will send your browser its public key for authentication, but in order for the authentication to mean anything, the public key itself must first be identified. To facilitate identification, the server will send you a certificate.

In order to be identifiable, the certificate will be signed by a “certificate authority“. A certificate authority is a company who sells certificate endorsements and who has the responsibility to do whatever is necessary to assure that the contents of the certificates they are signing is truthful. Part of this process may be to ask for a faxed-in copy of a driver’s license, or to call the company’s well-known phone number and check with their IT department. The price of the endorsement can itself be a means of ensuring that an applicant is not fraudulent; a large company will have no problem paying over a thousand dollars annually for an endorsement, but to a small-time impersonator, this might be prohibitive.

A public key infrastructure (PKI) differs from a web of trust in two major ways. First, in a PKI, a certificate is signed by only one endorser, while in a web of trust a certificate may have multiple endorsers. Second, while in a web of trust a user is interested in tracing the endorsement chain back to someone that he or she knows personally, in a PKI the browser is interested in tracing the endorsement chain back to a “root” Certificate Authority. What makes a certificate authority a functional “root” in the context of HTTPS is that the root authorities’ certificates and public keys are pre-installed in the browser, and signed only by themselves. And so, ultimately, you are trusting that the manufacturer of your browser (Microsoft, the Mozilla foundation, Apple, Google, Opera, etc) is pre-installing root certificates only for trustworthy certifying authorities.

By now, you should know enough about privacy, authentication, and identification to understand what those HTTPS certificate error messages you receive from your browser mean. A browser error or warning message about an HTTPS certificate almost always indicates that a problem was encountered while attempting to use the certificate to identify the remote server (the actual authentication or encryption of the data almost never fails). The most common errors encountered are that a certificate has expired, or that a certificate’s chain of endorsements cannot be traced back to a known root certifying authority. A special case of the latter is a self-signed certificate, which is not signed by any certifying authority, root or otherwise.

These errors are important because they mean that the certificate presented by the server cannot be trusted as identification. You should afford them the same level of trust as identification that you would afford the “I am Alice” card that was handed to you; that is to say, none. And without identification of the public key, any authentication you attempt to perform on the remote server is equally worthless. The person handing you the “I am Alice” card could easily be Mallory and you would never know the difference. Note, however, that this says nothing about the compromise of privacy.

An HTTPS (or TLS) connection using an expired, self-signed or otherwise untrusted certificate allows for private communication, but does not provide authenticated communication.

That is, your data is protected against third-party snoopers on its transit through the Internet, but it is most certainly not protected against your counterpart being a malicious imposter.

I took so much space writing about trust and certificates largely to get to that point, because it is perhaps the most widespread and dangerous misconception about cryptography on the Internet. It is perfectly possible to have a cryptographically private conversation with a cryptographically unauthenticated, unidentified, and untrusted server. Just because you have obtained the “privacy” form of security does not imply that you have all of these other forms of security that you may also desire, so you shouldn’t assume that you do.

5. Verification

This will almost seem like a post-script considering how simple it is compared to identification and trust, and really it should logically appear between identification and trust, since it is the basis for signatures, but I didn’t want to break up the narrative.

Above, I glossed over the fact that a person (in a web of trust) or a certifying authority (in a public key infrastructure) is able to endorse a certificate by “signing” it. But what does that mean, exactly? Cryptographic signatures provide verification, the final common form of cryptographic security in modern computing.

Suppose that Bob writes a will leaving half his estate to Alice and half to Charlie, and disinheriting Mallory. Suppose then that Mallory sneaks into Bob’s home office, finds his will in his desk drawer, and modifies it such that it now leaves the entire estate to Mallory and disinherits Alice and Charlie. When Bob dies and the will is read, how can the executor verify that the will is what Bob wrote and has not been tampered with? In this non-computing situation, the will will have been signed by a witness or a notary public, and the executor will trust the witness or notary to inform him if the document differs from the document that they signed.

In computing, things work essentially the same way. If an e-mail (or document, or certificate) needs to be verified as having not been tampered with, it will be cryptographically signed, and the public key of the signer will be used to verify that the contents of the e-mail, document, or certificate have not changed since the signature was applied. This is verification: you have assurance that the data has not changed since a trusted party signed it. Again, don’t infer that this means more than it does. The document need not be private, and it is important that the signature be authenticated with an identified, trusted key in order to mean anything.

The mechanics of a cryptographic signature are simple. First, a cryptographically secure hash function is applied to the document to obtain a relatively short sequence of bytes. Normally, the function used today is SHA-1. The important part about the sequence of bytes produced is that it would be incredibly difficult to create a meaningful document with different contents which would generate the same sequence when the cryptographic hash is applied to it. The output of the cryptographic hash is then encrypted using the signer’s private key and attached to the document.

The recipient can then use an identified and trusted public key belonging to the signer to decrypt the output of the cryptographic hash. If the recipient re-computes the hash on the data and compares it to the decrypted hash output, he can be assured that the document was not tampered with if the outputs match. In the case of certificates, the certifying authority’s signature of the certificate verifies that the identifying information contained within the certificate has not been altered since the time at which the certifying authority validated that the information was true.

In cases other than certificates, for example documents and e-mails, data is usually signed by its own author. For example, Alice sends an e-mail to Bob and signs it with her own private key. Then, presuming Bob already has an identified, trusted copy of Alice’s public key, he can not only verify that the message has not been tampered with, but he can also authenticate Alice as the author of the message, since no one but Alice could have produced a signature that would decrypt properly using Alice’s public key. If the message or document were signed by someone other than Alice, Bob would have to trust that the signer was being honest when endorsing that the message came from Alice.

What’s important to note is that if Alice simply sends a private message to Bob, this provides neither verification that the message has not been altered nor authentication that the message is actually from Alice. When Alice sends a private message to Bob, she encrypts it using Bob’s public key. This provides privacy and ensures that only the intended recipient (Bob) can read the message. But to provide verification and authentication, Alice must also sign the message with her own private key.

Summary

Hopefully, this article has helped the reader understand the similarities, differences, and interrelations between the five most common applications of cryptography to modern computing. To wrap up, I’ll repeat the most salient points about each:

Privacy

No third parties can read your data. Nothing is implied about the identity or trustworthiness of you or your counterpart. Neither you nor your counterpart can know that messages are not being altered or replaced in transit.

Authentication

You know with certainty that your counterpart possesses a particular private key. Nothing is implied about the identity or trustworthiness of your counterpart. The conversation may not be private, and neither you nor your counterpart can know that messages are not being altered or replaced in transit.

Identification

You know (somehow) that a particular private key corresponds to a particular identity. There is no “conversation” involved.

Trust

Due to an endorsement by an already-identified and already-trusted third party, you know that a particular private key corresponds to a particular identity. There is no “conversation” involved, but trust can be securely conveyed over insecure computer networks.

Verification

You know with certainty that messages between you and your counterpart are not being altered or replaced in transit. The conversation may not be private, and nothing is implied about the identity or trustworthiness of your counterpart.

Ideally, you want all of these things at once, and that’s exactly what HTTPS (or other protocols on top of TLS) give you. That’s why it’s completely secure to give your credit card number and personal details to a bank or other merchant over the Internet, so long as you are using HTTPS and you are not otherwise worried that the bank or merchant will misuse or mishandle this information in some way completely unrelated to having transmitted it over the Internet.

The certificate given by the web server is trusted by your browser because it is identified by a certificate which has its contents verified by a certifying authority’s signature. Thus, the certificate can be used to authenticate that you are communicating with the server that the certificate describes. Once all of that that is ascertained, the cryptographic key in the certificate is used to ensure that the conversation between you and the web server is private with respect to third parties along the route of data transit.

But, of course, to be truly secure, all of these aspects must be present, and a savvy Internet user must recognize that an HTTPS error displayed by the browser indicates that that is not the case. Moreover, when using or devising security systems that are not as well automated as TLS, one must be sure that each desired aspect of security is in place, and not make the assumption that one aspect implies the others, which is most certainly not the case.

The point of this post is not to give a guideline for how to design protocols that work well, or are efficient. That is a topic of much larger scope, and if you’re interested in that, RFC 3117 is a good jumping-off point. Rather, this post aims to give a set of suggestions for how to design protocols that will be the least painful for yourself and other programmers to implement, debug, and apply. There is an underlying assumption here that you have already spent the time to decide what your protocol is trying to accomplish and that you have found a way to make it work well (assuming that it is implemented correctly).

1. Don’t Re-invent the Wheel

If you can get away with using an existing protocol, do so. “Don’t re-invent the wheel” is not exactly a protocol-design axiom; it’s more or less a computer programming axiom in general. The premise is that, even if it doesn’t fit your purpose to a T, a well-worn (and therefore well-tested and well-debugged) existing protocol, hopefully with an existing implementation, will save you more in time and avoided headaches than rolling your own would ever save you in efficiency.

The corollary to this rule is that if you can’t use an existing protocol, at least use an existing framework. In particular, if your protocol takes the form of a remote procedure call, there are a wealth of solutions including SOAP and Google’s Protocol Buffers that can ease the effort.

2. Prefer determinism

I initially wanted to title this point “prefer simplicity”, but on reflection I realized that that isn’t really what I meant to say. Some protocols are inherently complicated, and there isn’t much that can be done about that. But even complicated protocols can have their complexity made tractable by proper modularization, and modularization is almost impossible without determinism.

The most familiar example of modularization in software is the encapsulation principle in object-oriented programming. The idea is that data is packaged into objects which can only be accessed through well-defined interfaces. This protects against unexpected operations on the data, and leads to less uncertainty (more determinism) about the state of the data and what could potentially happen to it next.

A fantastic example of a complex yet highly deterministic protocol is one half of the backbone of the modern Internet, TCP. The Transmission Control Protocol underlies most of the Internet communications we rely on daily. It provides ordered, reliable delivery with adaptive flow control to handle varying network conditions. Without TCP, hundreds of higher-level protocols would have to waste effort and add complexity by re-implementing some subset of its features. Yet, for all its power and complexity, its macro-operation can be accurately summarized in the following diagram:

TCP State Diagram. (see footer for credits)

The main thing to note about this diagram is that, given any state, there is usually only one, sometimes two, and at most three other states that can be transitioned to. Any other action is illegal. A SYN packet received in the FIN WAIT 2 state doesn’t have to be interpreted meaningfully.

In contrast, a poorly designed protocol might have the concept that “anything can happen at any time”, forcing an implementer to litter his or her code with complex state tracking and excessive case checks. Worse, non-determinism forces the implementer to consider how the implementation must respond in bizarre and unusual situations. In a deterministic protocol, these situations would either have their reactions explicitly defined, or be declared illegal and free an implementation from the requirement to make a meaningful response. In a non-deterministic protocol, failing to consider some obscure case or another becomes a sure source of bugs, incompatibilities, and potential exploits in young implementations.

Yes, an anything-goes non-deterministic protocol is quicker to design, but by doing so you shift all the effort of thinking out the implications of your design choices to the potentially numerous implementers, all of whom become encumbered with the burden of thinking out consistent reactions to every possibility, and none of whom have the luxury of being able to change the protocol’s design when a failing becomes apparent. They are forced simply to throw more code at the problem, leading to fragile, buggy, and generally poor implementations.

3. Prefer human readability

Premature optimization is the root of all evil. Unless your protocol needs, for some reason, to be blazing fast, and you know from testing that squeezing a few extra bytes of of each message will give you the speed you need, just use plain, simple text.

There are a number of advantages to a text protocol over a binary protocol. First is debugging. When your protocol implementation is behaving unexpectedly, it is much easier to read a captured stream of data and be able to immediately understand its contents than it is to be forced to write a protocol dissector that may have its own bugs getting in your way.

Second is discover-ability. A human-readable protocol is much easier for others to understand and learn. Unless you are attempting to intentionally impair interoperability (which is usually a misguided idea), this is a benefit. In lieu of, but preferably in addition to, formal documentation, a discover-able protocol is one for which someone wishing to write their own implementation can easily observe the behavior of two existing implementations, and learn how they communicate. Here, clear commands like LOGIN or GOODBYE make things a lot easier than raw numeric codes, in the absence of a protocol dissector.

Now, this doesn’t mean “don’t also be machine-readable”. You can combine the two approaches by using very structured syntax and/or keywords that can be machine-parsed with minimal effort, but which can still be read directly by humans.

One final note: if the human-readable part of your protocol is going to contain free-form text (i.e. strings that are not spelled out explicitly in the protocol specification), your protocol really should use Unicode. Next week we will be in the second decade of the twenty-first century, and English is most definitely not the only language on the Internet anymore.

4. Insist on network byte ordering

This one is not a suggestion; it’s a rule. If your protocol uses multi-byte binary-encoded numbers, and it does not use network byte ordering, then you have committed a mortal sin. Network byte ordering is called what it is for a reason – so that machines communicating on a network have a common standard for which byte ordering to use when interchanging data with one another. If new protocols don’t adhere to this standard, then what’s the point of having a standard?

The unfortunate part about network byte ordering is that it is big-endian, and as logical as big endianness is, the fact is that most of us program on little-endian machines. So the catch is that if we programmers don’t stop and think about what we’re sending out into the network, our numbers will more likely than not end up with little-endian byte ordering. The reason that this is a problem is that there are standard, portable functions that convert native byte ordering (whatever that may be) to big-endian, but there are no such things for native to little-endian. Speaking as someone who has more than once had to write an implementation of a little-endian protocol that will run on either architecture, this bites, so please be kind and use the standard.

Oh, and this relates to point 9 below as well, but please specify your protocol’s byte ordering in your documentation, even if it is little-endian for some (hopefully historical) reason. Otherwise, you will end up with people who write implementations that don’t do any conversion at all from their native ordering, and then then devices with different endianess can’t even talk over your protocol at all.

5. Make magic numbers meaningful

Let’s say your protocol can send some fixed set of message types. The simplest thing to do is just number them 1, 2, 3, 4, 5, etc, and be done with it. But you could be doing so much more with your numbers! Remember point 3, “Prefer Human Readability.” You can strike a happy compromise between human and machine readability by making your numbers meaningful, and then sparing a few extra bytes to encode them in text rather than as raw binary.

What do I mean by meaningful? Take for example the protocol that you probably just used to read this post, HTTP. Every HTTP response comes equipped with a numeric status code. These codes are not arbitrary. The code that every Internet denizen is most familiar with is 404 (File Not Found). The meaning embedded in this code is the first digit. HTTP response codes beginning with 4 indicate a client error. This contrasts with the ’1′ prefix indicating information, ’2′ indicating content, ’3′ indicating redirection, and ’5′ indicating a server error.

The FTP protocol goes even farther than this. The second digit gives an analogous summary of the response’s purpose, and the first digit gives an indication of which state the protocol instance should be in as a result. For example a response code beginning with 20 indicates that the client may now send more commands (2) and that the previous command failed due to some kind of syntax error (0). A code beginning with 12 indicates that another response message is forthcoming (1), and that the response content pertains to server status (2).

This method of classifying machine-readable numeric representations of information into meaningful numeric ranges yields two important advantages. First, it is much easier for a human debugging the protocol to remember what the numerically-indicated semantic categories are than to remember each of a few dozen arbitrarily enumerated values individually. Second, it gives logically similar values numerically similar numbers. In other words, you’re not going to end up assigning “Vanilla Ice Cream” to 3, and then when you realize later that you forgot about chocolate, assigning “Chocolate Ice Cream” to 417, right between “Cyanide” and “Adult Diapers”.

Which brings me to my next point…

6. Design for expansion

If your protocol is worth anything, it will be revised. And it will be revised again and again. In fact, the more useful you protocol is, the more likely it is to have multiple revisions and numerous extensions. Prepare for this from the state.

There are two ways to go about this, and you can do both. One is to reserve space for expansion. One form of this is to assign meaningful numbers as described above. If you decree that all numbers beginning with 3 mean “A Type of Ice Cream”, then you’ll have plenty of room to add Pistachio and Rocky Road when you remember them in version 2.0. A similar idea is to explicitly assign some values (or bit positions, in the case of flags) as “reserved” initially, and assign them to something meaningful when the time comes and they are needed.

Another way to go is to explicitly indicate your protocol version. I’d say that it’s probably always a good idea to do this. This way, one end of the connection (or both) can announce its version, and if the versions mismatch, the implementations can either decide not to communicate, or better, agree on a highest commonly-supported version to use.

The benefit to this is that from the point of agreement forward, the implementations don’t have to worry about backwards-compatibility, even for very basic things such as message structure. Reserving numbers and bits is nice, but once you run out of numbers or bits, you have to change the message format in a way that can’t be pre-determined. To get maximum benefit out of agreeing on a version to use, the version negotiation (or announcement) should occur as soon as possible in the exchange. If possible, the version should be the very first byte (or bytes) sent so that everything else about the protocol can be changed with wild abandon if desired. The other backbone protocol of the Internet, IP, does exactly this, and that helps makes IPv6 possible.

7. Don’t be stingy with information

Except to the extent that it becomes a security concern, one end of your protocol should never hide relevant information from the other. In other words, each end of the connection should have within the protocol a mechanism for querying the other end for information. Relying on assumptions about the properties or state of the connection parter will only lead to increased fragility and more backwards-compatibility headaches. In fact, the version announcement mechanism described in the previous point is almost a special case of this. Each end of the connection preemptively answers the implicit query “which version(s) of the protocol do you support?”

For example, consider a case where you are a client trying to retrieve a piece of data from a remote server. The protocol first makes you select a data set, and then the client may either retrieve a specific datum by key, or retrieve the entire set. There are several practical queries that the server should be prepared to respond to, and which the protocol should make possible:

• Which data sets exist on the server?
• Which data sets does this client have permission to access?
• Which data set is currently selected?
• Which keys are available in this data set?

In the absence of these queries, the client may have to behave inefficiently, or be unable to operate at all. If there is no query to determine the available data sets, the protocol has made the assumption that the client and the server will always both know and agree upon the names of the available datasets, which makes it hard to modify the data structure without modifying both sides of the protocol. Similarly, if there is no mechanism to query for keys, a client may in some circumstances need to retrieve the entire data set when it could have gotten away with much less traffic. The ability to determine the currently selected set, while seemingly unnecessary, may allow a simplified client implementation with less explicit state tracking, depending on the details of this imaginary protocol.

In general these sorts of things are dead simple to include, and (again aside from security concerns) confer only benefits.

8. Document your protocol precisely

Code programs computers, and specifications program programmers. Much like you cannot expect a computer to do what you want it to do in the absence of specific, precise code explaining exactly what it should do, you cannot expect a programmer to do what you want him or her to do in the absence of a specific, precise specification explaining exactly what you want him or her to do.

If you ever hope to have other programmers write implementations of your protocol that are interoperable with yours, your protocol had better have good documentation. The documentation needs not only to specify what the packet layout or command syntax is, but also what the observable semantics of the messages should be.

For example, it is a really bad idea to create a flag in one of your packets named “restart connection”, and give no further documentation on what should happen when a packet with that flag set is received. You may know what you mean by that, but another programmer working only from your documentation, will not know whether this requires a confirmation packet, whether this is a request or a command, what will happen if another packet is sent without restarting the connection, what state the protocol should be in upon being reset, whether there should be a limit to the number of consecutive restarts before giving up.

Better documentation for such a flag (using RFC 2119 keywords) would be:

Restart Connection Flag. If a packet with the Restart Connection Flag set is received, the receiver MUST NOT send any further packets to the remote host. If any further packets with this connection ID are received by the remote host, they will be rejected with an Invalid Connection ID error. The host receiving the Restart Connection command SHOULD immediately restart the connection by sending a Hello packet to the remote host. No state information from the current connection will be retained in the new connection.

This makes it clear that this is a command, not a request, and does not require (and in fact forbids) a response. It makes clear what will happen if the request is ignored, and tells you exactly how to take the action that the command requires. It also implies (by using SHOULD rather than MUST), that an implementation may choose not to restart and instead just cease communication. Permitting this behavior allows an implementation to, for example, escape from an infinite loop of restarts without violating the protocol semantics.

9. Follow the Robustness Principle

Also known as Postel’s Law, the states: “be conservative in what you do, be liberal in what you accept from others.” This was originally coined in RFC 761, the document specifying TCP. This is a very important, and widely known, yet also widely misunderstood aphorism.

The most notorious misapplication of this principle was in the implementation of early HTML parsers. Based on this idea, the parsers would take in any old junk that vaguely resembled HTML and try as hard as possible to make something legible out of it when displaying the results. The result of this extreme laxity was more than a decade of the nightmare known as “tag soup” which is only now beginning to abate.

The real meaning of the Robustness Principle is not that erroneous input should be accepted as valid, but that erroneous input should not cause catastrophic failure, that any valid parts of a partially-erroneous input should be accepted if possible, and that diagnostics should be given for erroneous input when feasible. An HTML parser implementation that properly followed this rule would, upon receiving “tag soup” HTML, produce a warning message that the HTML was invalid, hopefully display some sort of information about what about it was wrong (e.g. unclosed anchor tag, missing doctype, etc), and only then try to (or give the option to) display the parser’s best approximation of what the author meant.

An HTML parser is not a protocol, but a protocol should behave similarly. Given an illegal command or request, or a set of conflicting options, what a protocol implementation should not do is: crash, silently ignore the problematic messages, or arbitrarily choose one of the conflicting options to ignore. Instead, the implementation should respond with a diagnostic indicating why the message could not be fully processed, and should process any part of the message that was valid if it can be done safely and unambiguously.

Keep in mind that the diagnostics need not be completely machine readable. A set of mutually exclusive options specified together could be responded to with a message like “573 Illegal Options – Foo and Bar cannot be specified at the same time”, where 573 is a machine-readable code indicating that the message was not processed due to an error in the options field, and the rest is something that can be understood by a human programmer when debugging his or her implementation.

The only significant exception to the applying robustness principle is in avoiding denial-of-service attacks. Responding verbosely to malformed input may exacerbate the effects of a denial-of-service attack, and so it is for example reasonable to cease this behavior in the face of repeated offenses originating from the same host in a short period of time.

10. Design for security from the start

In the nine points above I have referenced numerous protocols from the standard Internet protocol suite. I did this not just because they are well-known but also because they are for the most part well-designed (otherwise they would not have survived the explosion in the size of the Internet in the past twenty years).

However, one shortcoming is common to many of them, and we live with its detrimental effects every day. These protocols, designed when the Internet was in its infancy as an academic and governmental experiment, were not designed with security in mind. This is what facilitates spam, denial-of-service, phishing, privacy invasion, and all other sorts of malfeasance on the Internet.

Today, however, the Internet is relatively mature and very, very public, so there is absolutely no excuse to design a new, security-free protocol. Neither is it acceptable to defer the addition of security features to a later version of the protocol. Another vital lesson that we have learned from the Internet protocol suite is that it is incredibly difficult to adopt secure protocol enhancements after a protocol has been widely deployed. If this were trivial, then the entire Internet would be running over IPsec already.

This isn’t to say that all traffic should be encrypted. Of course it is acceptable to forgo encryption if the traffic isn’t sensitive, but things that are completely unacceptable in the modern Internet include sending passwords in the clear, using predictable sequence numbers, and assuming good behavior from the other end of the connection. If you simply avoid those security pitfalls and make use of some established mechanism (e.g. TLS) for producing a cryptographic layer when you need to transmit sensitive information, your protocol will be much, much better off for it.

Note well, though, that to be secure does not mean to be obscure. Encrypting your protocol is quite different from making it incomprehensible. Encryption should be a layer. Once the encryption layer is removed, the protocol should continue to adhere to the design principles articulated above, including human-readability, discover-ability, meaningful magic numbers, etc.

TCP State Diagram © 2009 Sergiodc2 and Marty Pauley. Some rights reserved.

The deck is divided evenly between the players face-down. Each player reveals his top card, and the player with the higher card puts both the cards on the bottom of his deck. If the cards are of equal value, each player plays three face-down cards and a fourth face-up card, and the higher-valued card wins all the cards on the table. This is known as a war. In the case of another tie, the process is repeated until there is no tie.

A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck face-up and still have a chance to stay in the game.

As you can see, since the player has no knowledge of which cards are in their initial hand, and no choice in which cards to play, this game could just as easily be played by a properly trained parakeet. The mechanical gameplay and lack of strategy, however, makes certain questions about the game mathematically interesting.

The other day when this game popped into my head, one of the first things I remembered about it was how many games I left unfinished due to their sheer length. I suddenly became curious about the expected number of turns required to finish a game of War.

It turns out that the answer is “about 277″ (which is considerably less than I expected). You see, people on the Internet tend to be pretty big nerds, and certainly I wasn’t the first one to consider writing a War simulation to figure out these kind of statistics. What I didn’t see discussed, though, is any treatment of the structure of a game of war.

The vital step to the game turns out to be re-integrating your captured cards back into your active deck. If this re-integration is entirely deterministic, the progress and outcome of the game is completely determined by the initial deal. However, as is mentioned on any page discussing War simulation, if the re-integration is deterministic, it can (and with surprising frequency does) lead to games of War which will never terminate.

There are essentially three major non-deterministic ways to re-integrate captured cards into the active deck:

1. Add the captured cards to the bottom of the active deck in random order
2. Add the captured cards to random positions in the active deck
3. Pool the captured cards in a “capture deck” until the active deck is empty, then shuffle the capture deck, and make it the new active deck.

When I used to play War, I played using method 3, and I’m not sure anyone actually uses method 2 (it would be very prone to bias and deliberate cheating in the hands of a human rather than a simulation), but it is interesting to think about. I’ll refer to 1 as Standard War, 2 as Continuous-Shuffle War, and 3 as Pooled-Capture War.

It turns out that, regardless of the re-integration method, a game of war can be accurately and completely modeled as a Markov chain. This isn’t actually all that surprising. A Markov chain is really just a technical name for a series of states where the next event depends probabilistically only on the previous state and no states prior to that. Since children’s games often intentionally minimize strategy and state memory, it turns out that several well-known and popular children’s games are in fact nothing more than brightly-colored Markov chains; for example, Candyland, Chutes and Ladders, and Hi-Ho Cherry-O. War stands out among these, though, because the state space for War is absolutely enormous.

The smallest state space belongs to Continuous-Shuffle War. In this game, a state can be uniquely identified by specifying which player has which cards. Order is irrelevant. Therefore, the number of possible states is where the brace notation in within the sum denotes a Stirling number of the second kind, with parameters the number of cards, and the number of players. This is just shorthand for asking “How many different ways can we divide items into non-empty groups?” The factor of is there because Stirling number does not take order into account, and in this game two states where the players’ decks are swapped around are not equivalent. The sum is necessary because Stirling numbers of the second kind only count divisions into non-empty groups, and so we have to account for a -player game devolving into a -player game when one player runs out of cards. The exists to take into account which players have run out of cards in a reduced game. The additional is for the number of finishing states in which one player has all the cards. How many states are there in this chain, then? For a typical game with a 52-card deck and 2 players, there are 4 503 599 627 370 496.

Next, there is Pooled-Capture War. Here, we still don’t have to concern ourselves with order, but each player essentially maintains two decks – the active deck and the capture deck. The reason we don’t concern ourselves with order is that the active deck is always essentially drawn from in random order, owing to the fact that the player plays repeatedly plays through an entire freshly-shuffled active deck, rather than adding cards to the active deck as he goes. In this case, there is really no difference between shuffling the capture deck when it becomes active, and drawing from the active deck at random. Therefore the number of states for Pooled-Capture War is almost the same as for four-player Continuous-Shuffle War, but not quite. The difference is that since each player has two decks, the number of finishing states increases from to , because when one player has all the cards, they can be divided between the active and capture decks in different ways. Therefore, the number of possible states in Pooled-Capture War is . For a typical game, this works out to 1 690 198 646 610 354 052 103 573 055 990 states.

Finally, for Standard War, a state can only be uniquely identified by specifying the active decks of both players, where order is this time relevant. This means that the total number of states is expressed as a sum of of all possible permutations of hands over the different quantities of cards each player might have. In other words,

(If anyone can think of a more compact way to write this, please let me know.) This formula essentially takes all choices of how to assign cards to players, and then sums the distinct permutations within each of these possibilities. This works out to right around 164 548 210 943 005 434 162 687 272 511 830 757 530 229 530 638 988 932 546 560 000 000 000 distinct states for a typical game.

In order to work out the answer to my initial question of the expected number of rounds in a game of War and other mathematical questions about War, the approach would be to compute a transition table where cell answers the question: Given that you are now in state , what is the probability that after the next turn you will be in state ? The difficulty of working out this table is easiest for Standard War, and hardest for Pooled-Capture War.

In Standard War, we know based on the state alone which cards will be played, and therefore exactly what the result of the upcoming turn will be. Probability only comes into play when deciding in what order the captured cards will be added to the winner’s deck. This probability is also simple; each integration order is equally likely, and so has probability where is the number of cards captured. The number of states that you can reach in any one turn is relatively small, and so the matrix for Standard War, while huge, is very sparse.

In Continuous-Shuffle War, we don’t know which cards will be played just by inspecting the state. This isn’t by itself that complicating since we can assume each player will draw from their cards with equal probability of drawing any given card. The complicating factor is that because “wars” can go on for an arbitrary number of draws, any given state can reach almost any other state in a single turn, albeit with very small probability for most of them. Still, since these probabilities are nonzero, the smaller matrix for Continuous-Shuffle War is very densely populated.

In Pooled-Capture War, we have all the problems of Continuous-Shuffle War, plus when computing the probabilities, one has to deal with the fact that the capture deck can become the active deck in the middle of a turn. This doesn’t make the matrix any more densely populated, but it does severely complicate the probability calculation algorithm.

Were we able to compute , we could answer my original question in this manner: In a Markov chain, the th power of , , gives the transition probabilities of ending up in particular states after turns. We then compose a begin row-vector where probabilities are distributed uniformly among the states which could correspond to an initial deal. Then, for each turn , we can compute and add up the probabilities of all final states to get , the probability that the game has ended by turn . The expected number of turns the game will last is then . We could also use vectors that specify a single particular initial deal to compute the probabilities that each player will win, given that initial deal.

However, my conclusion after thinking all of this through is that it probably isn’t worth it to try to write a program to compute these kinds of things. The time required to iterate through the states of any of these methods, let alone the space required for (which has size the square of the number of states, times the size of the datatype used to store the probability value), makes this endeavor completely intractable for all but pathetically small decks of cards (around 10 or so). I figure that while the simulation-discovered answer of 277 is somewhat less accurate than a probabilistically computed answer would be, it’s likely to be accurate enough for any future application of this information.

(Thanks to Wolfram Alpha for making possible the giant scary numbers in this post.)

First, on the left hand side you will see a link to a new section entitled “Unstumping the Internet“. The purpose of this section, as its index page explains, is

This set of pages is for cataloging relatively brief answers to questions that I had to figure out myself after being unable to find the answer on the Internet. [...] When I encounter a question that I cannot find an answer for on the Internet, and especially if in my searching I notice that several other people have asked this question with no satisfactory answer, I will post the answer here when I discover it. The hope is that next time someone searches the Internet for this question, they will find my answer.

So this section is not something that I expect anyone to read frequently, or even at all. I’m not going to be posting to the front page when I add new articles there, as the whole point of this section is to not clutter the front page with items of limited interest and minimal depth. Instead, I hope that these pages will visited primarily as the results of search engine queries.

Secondly, on the right hand side, there is a new section of links entitled “Interesting Items Elsewhere”. This is a listing of the last few items from other weblogs (or other sorts of feeds) that I have found most interesting. This is in fact tied to my Google Reader account, and displays items that I have “shared”, so these may not always be completely serious or computer-related. You can click on the “more” link at the bottom to see everything I’ve shared, as opposed to just the few most recent items.

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.

As much as we’d all like it to be, the following is not the right answer:

The main reason that this is so much harder than it needs to be is that the istream::get() function does not provide an overload that reads directly into a string. You have only three choices if you go that route. You may either read character-by-character, or you may read into a character array, or you may read into a streambuf object. No strings for you.

A streambuf, you say! Aha! Well you may happen to remember that there is a standard class called std::stringbuf which derives from streambuf, and you could read into that and then extract the string. The problem with this, though, is that unlike the istream::get() overloads that use character arrays, the overloads that use streambufs conveniently leave out an optional size parameter. If you want to read from the stream with a stringbuf, you are obligated to read everything it has to give you, up to some delimiter. The istream class’s other unformatted data-reading functions, read() and readsome(), don’t give you any choice other than character arrays. So using an istream member function is right out.

What to do instead, then? We can turn to every C++ programmer’s best buddy, the iterator. istream objects can do more than stream extraction. Much like everything else in the C++ standard library, they have iterators. A really brute-force way to write this function is then to do this:

Note the end-of-stream check in the conditional section of the for statement. Incrementing the end-of-stream iterator is not valid, so we have to check the istream at each iteration to make sure that it is still readable. Recall that istream objects can be implicitly converted to bool (by means of a conversion to void*), which indicates whether or not they are still good to read from.

We could add a call to string::reserve() to make the above slightly more efficient, but efficiency aside, the above function is aesthetically gross. How might we make this look a bit more elegant, and be more expressive of what we’re trying to accomplish (initializing a string with the first n characters of a stream) and no so explicitly expressive of the mechanics of how that gets done?

You might remember that std::string has a constructor which takes two input iterators and uses them to construct the string. This is a really easy way to initialize a string with the whole contents of a stream, for example if your istream in is really an ifstream and you want the entire file read into a string.

Two notes on the above: First, the parentheses around the first argument are, unfortunately, necessary. This is to prevent the parser from mis-parsing this as line a function declaration, much like how you cannot use empty parenthesis for default-constructing a variable without new. Second, the second argument, a default-constructed istreambuf_iterator is a special value which represents end-of-stream for any input stream. This specialness is why this pattern, while it works great for reading the whole stream, doesn’t work at all for reading only a fixed number of characters. What happens when you try to use this string constructor to solve the problem I initially posed?

The compiler doesn’t like that. It will tell you that there is no operator+ defined for istream_iterators, and it will be right. Remember, istream_iterators are not models of random-access iterators. Okay, so why don’t we just then use the old standby std::advance, even if it might be a little inefficient?

A little prettier, but unfortunately it doesn’t work. It does compile, but it will give you an empty string at best and a segmentation fault at worst. The use of begin after we have called std::advance on end is undefined behavior. This is because istreambuf_iterators are not just not models of random-access iterators, they aren’t even models of forward iterators. They are only models of input iterators. That means that you can only move forward, and once you move forward you can never go back, even if you’ve saved a previous iterator like we did above. Input iterators only guarantee that you may pass over the range once, and that makes sense given the nature of streams.

If you look around at other standard library functions that might fit the bill instead of string‘s constructor, similar problems arise. The string object’s append() method requires a forward iterator. The std::copy() function can work with input iterators, but requires an explicit end iterator, which we can’t provide except for the special end-of-stream iterator. For some reason, unlike std::fill() / std::fill_n() and std::generate() / std::generate_n(), there is no such function as std::copy_n(). It’s almost as if the authors of the standard library are teasing us!

Just to spite the standards authors, here’s something clever you could do

This will actually work, except that, strictly speaking, it is also undefined behavior. Every modern C++ compiler makes std::string‘s internal storage contiguous, so unlike the string constructor example, this will probably work in practice. But, rather surprisingly, std::string is not required to have contiguous internal storage by the current C++ standard. This will required of std::string in C++0x, and so the above will be legal in C++0x, but while it is convenient, it is currently not standards-conforming.

Sadly, as far as I can tell, there is absolutely no standards-conforming way to write this function without raw character arrays, other than by explicitly writing out the nuts and bolts of a character-by-character iteration over the istream or doing something even more long-winded like writing a wrapper around istreambuf_iterator that returns an end-of-stream iterator after a fixed number of advances. I’ll repeat the “brute force” solution (with the small optimization included) below, and if anyone can find a more elegant way to accomplish this seemingly trivial task, please post it in the comments. It’s things like this that sometimes make me think that all the C++ nay-sayers out there might be on to something.

This post was inspired by this question on StackOverflow. My answer to this question in part encourages the questioner to use C++-style I/O rather than C-style I/O, but shortly after posting I realized that I did not quite know how to do what he wanted in a truly “C++ style”. I still don’t.

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.

According to the InformIT article that I linked above, the straw that broke the camel’s back was a paper by Bjarne Stroustrup entitled “Simplifying the Use of Concepts”. This paper, ironically, was intended to champion the retention of the concepts feature, and to propose solutions for some of the feature’s outstanding problems. According to that article, this paper “scared folks.” That’s a description that’s hard to interpret until you read the paper itself, which if you have any interest in C++0x or any curiosity about why concepts were removed, I strongly suggest you do. Let me give my reaction to it.

First, some background. The current C++ standard library already has concepts, and uses them heavily. The most easily demonstrable example of concepts in the current C++ standard library is iterators. You have ForwardIterators, BidirectionaIterators, RandomAccessIterators, etc, etc. These each specify behavior semantics and usage syntax for different kinds of iteration. For example, a ForwardIterator must (among other things) support operator++ and be re-usable over the same collection. Yet if you go looking for a class called ForwardIterator to use as a superclass of your iterator, you will find nothing.

The fundamental difference between the concepts currently in the standard library and the concepts that were until recently part of the C++0x draft is that the compiler is totally ignorant of concepts as they exist in C++ today. Today, concepts exist only in the documentation for the standard library; the compiler is completely ignorant of them. The only ways for a programmer to be sure that he or she has conformed to a required concept is to either read the documentation, to read the implementation code and infer the concept requirements, or to guess what the concept requirements are and to refine that guess as a result of each compiler error that arises. C++0x concepts aimed to give a language-supported and compiler-understood mechanism for defining the requirements of a concept in code.

Years ago, my first reaction to concepts, both in C++98 and C++0x forms, was “that’s neat, but why don’t they just use interfaces?” After all, generics in Java accomplish this rather elegantly through the use of interfaces, wildcards, and wildcard binding. The answer is that interfaces are inherently an object-oriented construct, and C++ is not just an object-oriented programming language.

Sure, interface-based template restriction would work fine for classes, but not requiring the use of classes when it is not necessary is a fundamental part of the multi-paradigm nature of C++. In fact, even though Java is object-oriented, its interface-based generics implementation has an obvious and annoying artifact in the completely unintuitive rule that you cannot use fundamental types (such as int) for generic type parameters. In C++, aside from wanting to avoid Java-like autoboxing, it is essential that code like this be legal:

This uses the templated std::sort function to sort a raw C-style array. The arguments to std::sort are RandomAccessIterators, which is a concept, not an interface. If RandomAccessIterator were an interface, then we would need either need to convert numbers into a random access container object (e.g. std::vector), or we would need to wrap the pointers that we passed to std::sort in iterator objects that implemented the RandomAccessIterator interface. Instead, since RandomAccessIterator is a concept, passing two int*s to std::sort works just fine with no behind-the-scenes magic, since pointers into an array support all the syntax that RandomAccessIterators must support, and they have equivalent semantics.

The big idea to take away from this set-up is that C++ templates differ from other similar systems (like Java generics) because they rely on structural typing, rather than nominal typing. That is, template arguments are validated based on whether or not they support the required syntax (operators and/or method calls). Not only is this different from other languages, it is radically different from other parts of C++, such as function arguments, which are validated based on whether or not they derive from the appropriate class. Because of this, the idea of adding formal concepts to C++0x was necessarily more than just a way to bring documentation into code that the compiler could understand and enforce. Concepts in C++0x were supposed to unify structural and nominal typing in C++.

Formal concepts are a way to give symbolic names to structural properties. Given this, a templated function or class can specify the symbolic name(s) for the collection of structural properties that it requires of its template argument(s). These names can then by looked up by the compiler, or the programmer, or the programmer’s IDE, to determine if a given type is appropriate as a template argument to that function or class. However, concepts are not nominal types, so there is no need for the type of the template argument to itself know anything about the concept that it is structurally conforming to.

The problem is that unifying the almost diametrically opposite notions of structural and nominal typing, of course, quite hard, which implies that formalized concepts are going to be quite difficult to define in just the right way.

What Bjarne addresses in his paper (linked above) is a series of problems that are caused by what the C++0x comittee had been referring to as “explicit concepts”. These are concept definitions which types must explicitly declare their support for, rather than implicitly supporting by means of providing the appropriate strucutral properties. An explicit concept is a nominal type, no two ways about it. It’s very much like an interface, except that there is a mechanism called a concept map which can be used to specify that a type supports the explict concept without requiring the type (which may not even be a class) to modify its own definition to declare support, as one would do when inheriting from an interface.

Concept maps have other uses, but the problem in using them in this particular way is that the extremely loose coupling between a concept map and the type that it is acting on leads to tricky problems of ambiguity and inconsistency. You can read Bjarne’s paper to understand this in more detail. Furthermore, writing concept maps is frankly a chore, and the more explicit concepts there are, the more often the average programmer is going to face the choice of put up with this annoyance or avoiding concepts altogether.

It becomes clear from the paper that there are several showstopper-level design bugs in the then-current C++0x draft specification of concepts. The core of Bjarne’s proposed solution is to eliminate explicit concepts altogether, and instead rely only on explicit or implicit relationships between concepts to resolve situations where wholly implicit concepts are inappropriate.

The example that Bjarne uses is the relationship between the concepts of RandomAccessIterator and a derivative concept called ContiguousIterator, which is a RandomAccessIterator guaranteed to use contiguously-allocated memory storing only plain data. They have exactly the same semantics, and so the compiler would have no way of knowing (without a concept map) whether or not a given iterator that matches these semantics actually conforms to the additional logical requirement of being a ContiguousIterator. The existing solution was to make them both explicit concepts, but this leads to a proliferation of concept maps to distinguish between the two concepts. Bjarne’s proposed fix is to make the derivation of ContiguousIterator from RandomAccessIterator explicit, with the effect that all types which match their common syntax are treated only as RandomAccessIterators unless there is a concept map stating otherwise.

While Bjarne’s proposed fix for this problem would work just fine, what I think is missed is this: Concepts as they were defined for C++0x were effective at capturing structural properties and assigning symbolic names to them. However, in a nominal type system, the class and interface hierarchy provides more than just symbolic names that capture a collection of method signatures. A nominal type represents a semantic contract that goes above and beyond the structure of the type. For example, a Shape class and a Cowboy, may both have a draw() method, but the two methods have completely different semantics. Bjarne mentions this shortcoming and dismisses it:

[W]e have lived happily with class hierarchies and templates for decades without [this issue] reaching anyone’s top 100 list of traps and pitfalls, so it is not on my top 100 list of C++ problems needing solution. One reason “accidental match” hasn’t been a major problem is that we rely on simultaneous matches of both names and types. For example, only if the Cowboy’s draw() has the same argument and return types as Shape’s draw() and the same holds for every other function in the concept/type can the problem slip past the compiler (to be caught be the simplest testing). Also, unrelated types tends to get muddled only when they are used for similarly named functions, so that overload resolution often catches the mistakes as ambiguities.

But the disturbing fact that remains is that without explicit concepts, formal concepts become unable to fully capture the notion of a semantic contract in a design-oriented manner. Explicit concepts provide a way to say “this concept has an important semantic contract”, whereas explicitly derived concepts provide only the much weaker and much more language-technical statement of “this concept’s semantic contract differs in some important way from that of its nominal parent”. That loss of expressiveness is what scared me when I read his paper. The two statements are similar from a language perspective (i.e. getting your program to compile), but from the more important design perspective (i.e. expressing the meaning of your code in your code) it doesn’t let you express things that you will very likely want to express.

Because of that deficiency, it really can’t be said that implicit concepts alone accomplish the goal of unifying structural and nominal typing. Bjarne’s “simplified” concepts are not a meaningful advancement over symbolic names for a collection of syntax requirements. Symbolic syntax naming is nice, and a mild improvement over the status quo, but it fails to fill the whole gap that concepts in C++0x were supposed to fill.

Furthermore, since they don’t fully capture semantic contracts, the explicit relationships between concepts that Bjarne proposes to avoid problems like the ContiguousIterator issue are basically just fix-ups for conflicts between concept rules and other existing C++ rules like overload resolution. This part of “simplified” concepts just doesn’t feel like an elegantly designed solution. Instead, it feels like what it is: an effort to save as much as possible of the original C++0x concept proposal while rather unceremoniously hacking off the parts of that design that led to the unacceptable explicit concept bugs.

Don’t get me wrong, I’m not defending explicit concepts. Aside from the bugs, I think they and their associated concept maps are a rather tedious way to express semantic contracts. And neither am I claiming to be smarter than Dr. Stroustrup or that I know a better way to express semantic contracts in concepts. What I mean to say is that in the end, I have to agree with the C++0x committee that concepts probably need some kind of fundamental redesign, and that a poorly-designed or incomplete concepts implementation which fails to truly unify structural and nominal typing would be markedly worse for the C++ language than maintaining, for the time-being at least, the status quo of having no formal concepts at all.

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.

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.

When you want to detect a C library with autoconf, it’s easy enough. You invoke the AC_CHECK_LIB macro. According to it’s documentation, it works like this:

Macro: AC_CHECK_LIB (library, function, [action-if-found], [action-if-not-found], [other-libraries])

Test whether the library library is available by trying to link a test program that calls function function with the library. function should be a function provided by the library. Use the base name of the library; e.g., to check for -lmp, use `mp’ as the library argument.

The problem should jump out at you from this. AC_CHECK_LIB is going to create a test program. That test program will be in C, the function you provide as the function argument had better be callable from C. Obviously, if your C++ library is a library consisting solely of classes, there’s nothing in there at this callable from C, since C doesn’t understand C++ classes. Worse yet, even if there are functions in your library that are not members of classes, these functions probably are still not callable from C.

The reason that even “free” (i.e. non class member) functions in C++ are not callable from C programs is because of name mangling. Since C++ was originally built to compile down to C (and later to compile on its own but still link as C), the developers of the C++ language had to devise a way to cram information about function-related C++ features that C did not support into function identifiers that C allowed. For example, C++ had to have some way to differentiate ClassA::foo() from ClassB::foo() when passing off object code to the linker, given that a C-oriented linker would have no concept of classes. Even outside of class members, C++ added support for function overloading, which was similarly alien to C linkers.

Early C++ compilers worked around these limitations of their linkers by encoding this information into a “mangled” function name. To swipe a good example from the Wikipedia article I linked above:

Consider the following two definitions of f() in a C++ program:

1. int  f (void) { return 1; }
2. int  f (int)  { return 0; }
3. void g (void) { int i = f(), j = f(0); }

These are distinct functions, with no relation to each other apart from the name. If they were natively translated into C with no changes, the result would be an error — C does not permit two functions with the same name. The compiler therefore will encode the type information in the symbol name, the result being something resembling:

1. int  __f_v (void) { return 1; }
2. int  __f_i (int)  { return 0; }
3. void __g_v (void) { int i = __f_v(), j = __f_i(0); }

Notice that g() is mangled even though there is no conflict; name mangling applies to all symbols.

These days, C++ is its own language, but this mechanic remains as a vestige of its early days. Worse, C++ compilers are notoriously inconsistent about how names are mangled. There is no standardized conversion between a native C++ function identifier and its mangled equivalent.

So getting back to autotools, this leaves us with two problems when trying to detect a C++ library using AC_CHECK_LIB:

1. C++ functions, even free functions, cannot be called from C using their C++ identifiers since their names (in the library binary) will be mangled from what they were in the C++ source code.
2. Even if you knew what the mangled identifier produced by your compiler was, the mangling schema is far from standardized, so checking for the mangled identifier is extremely non-portable, defeating the whole point of using autotools.

How then do we get around this? Here are two solutions:

Solution One: Find (or create) a function with C calling conventions in the library

This is by far the easiest method if you are also the developer of the library. It is possible (and easy) to create a free function in a C++ program that is not mangled. You do it like this:

This declares a function called libfoo_is_present that has C-style linkage. That is, the name will not be mangled whatsoever by your C++ compiler. The tradeoff is, of course, that anything within an extern "C" block cannot use any C++ features such as classes or overloading. That’s fine though – all we want for this purpose is a single function with a relatively unique name that we can search for in this library. Note that since autotools will try to link with the library using this function, you are going to want to give the function an implementation as well, which can be empty.

If you’re not in control of the library sources, you might still be in luck. Some libraries have both C and C++ bindings. The C bindings are going to have C linkage, even if the library was built with a C++ compiler. Choose some function from the C bindings to search for with the AC_CHECK_LIB macro. Even if a library does not have explicit C bindings, you might still be able to find a function with C linkage hidden in the library. For this, you can use the nm tool (if you have a static library), or the readelf tool if you have a dynamic library. It should be fairly simple to tell C symbols from mangled C++ symbols. For example, using readelf on a C library produces

tyler@kusari /lib $ readelf --dynamic --symbols libncurses.so.5 | grep FUNC | tail
548: 000000000001e1d0 42 FUNC GLOBAL DEFAULT 11 slk_touch
549: 0000000000015ce0 15 FUNC GLOBAL DEFAULT 11 erase
550: 0000000000027ae0 120 FUNC GLOBAL DEFAULT 11 _nc_free_termtype
551: 000000000002c6f0 108 FUNC GLOBAL DEFAULT 11 _nc_outch
552: 000000000002ac50 1095 FUNC GLOBAL DEFAULT 11 _nc_tparm_analyze
553: 0000000000028940 149 FUNC GLOBAL DEFAULT 11 _nc_keypad
554: 0000000000014d70 15 FUNC GLOBAL DEFAULT 11 refresh
556: 0000000000014cf0 10 FUNC GLOBAL DEFAULT 11 touchline
558: 0000000000024c40 2 FUNC GLOBAL DEFAULT 11 _nc_freeall
559: 0000000000012d50 73 FUNC GLOBAL DEFAULT 11 beep

While using it on a C++ library produces

tyler@kusari /lib $ readelf --dynamic --symbols libboost_regex-gcc43-mt.so | grep FUNC | tail
1403: 00000000000a1f70 1498 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail18basi
1404: 0000000000090cd0 62 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail12perl
1405: 0000000000091f50 166 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail19basi
1407: 0000000000072fe0 15 FUNC WEAK DEFAULT 11 _ZN5boost6detail17sp_coun
1408: 000000000008cbb0 381 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail19basi
1409: 0000000000042320 75 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail12perl
1411: 0000000000043410 15 FUNC WEAK DEFAULT 11 _ZN5boost6detail17sp_coun
1412: 0000000000083d80 239 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail12perl
1414: 0000000000042680 19 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail12perl
1415: 00000000000980a0 775 FUNC WEAK DEFAULT 11 _ZN5boost9re_detail12perl

The “_ZN5″ prefix being a token that designates g++ name mangling.

Not all C++ libraries will have C symbols, but if you find one, just use AC_CHECK_LIB as usual. As a real-world example, the Google Unit Testing Framework is a C++ library, but the gtest_main library that comes with it provides a main() function which always has C linkage. Therefore you can check for googletest like this:

This checks for googletest by way of checking for libgtest_main by trying to link against its main function. If the library is found, it sets HAVE_GTEST and adds libgtest to the TEST_LIBS variable, and if not it emits a warning.

Solution Two: Roll your own test

If you are out of luck and the library source is not in your control and it has no functions with C linkage, you are not out of luck. Autoconf is quite extensible. Recall that the main issue causing this whole mess is that autoconf’s test programs are C programs. Well, that’s the default, but it doesn’t have to be that way. You have to do it by hand, but it is possible to make autoconf use a C++ test program by way of the AC_LANG_PROGRAM macro.

The semantics of this macro are a bit too lengthy for me to quote here, so just go read the documentation. In summary, this macro takes a bit of code, and wraps it in the usual boilerplate common to C and C++. That is, the code snippet you provide will be treated as the body of a main function. This provides a lot of flexibility. You’re no longer limited to trying to call a function. If your library has no free or static functions, that may not be possible. Instead, you might test the library by trying to instantiate one of its objects.

To use a similar real-world example to the previous solution, consider the Google C++ Mocking Framework, which contains no symbols with C linkage. Here’s how we would construct a test for gmock, starting with the call to AC_LANG_PROGRAM:

Simple enough. The prologue argument (the first argument) gives the include directive necessary for using the gmock library. The body argument gives a simple instantiation of a dummy object from the library. I chose the Cardinality class largely because it was default-constructable and therefore simple to use.

To make AC_LANG_PROGRAM act like AC_CHECK_LIB, you need to wrap it in AC_LINK_IF_ELSE like so:

The AC_IF_ELSE macro simply gives us the ability to do something if the test passed, or if it failed, much like the final two arguments to AC_CHECK_LIB.

Finally, there are two details left out. First, the above AC_LINK_IF_ELSE macro doesn’t know to provide -lgmock to the linker. In order to do that, we have to set -lgmock in LDFLAGS, and remember to restore the original LDFLAGS afterwords.

Second, we need to tell autoconf to compile this test program with a C++ compiler, or else it’s going to fail for the same reason that using AC_CHECK_LIB would have. This is accomplished using the AC_LANG macro, documented here, along with documentation about how to use multiple languages in test programs in the same configure script.

In total, the whole test for libgmock looks like this:

Tada!

This should, however, leave you with the same question I had when I went through the process of figuring this out. Namely: why in the hell does AC_CHECK_LIB not respect AC_LANG when creating its test programs?. If you look at the config.log that the configure script generates, it always uses C programs and the C compiler to run AC_CHECK_LIB test, even when the language has been set to C++. If this were not so, things would be much simpler, except in the case where a C++ library had absolutely no free or static functions to test for.

If anyone knows why autoconf behaves like that, please enlighten me (or better yet, explain how to make it behave otherwise!).

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (Whitaker 1990)

This, much like airplane on a treadmill, and 0.999… == 1 are common topics of long, drawn-out arguments on the Internet. But what I want to talk about is not the problem itself (which has been done to death), or Jeff’s post. Rather, I want to discuss a variant problem humorously called the “Monty Fall Problem” proposed by Professor Jeffrey S. Rosenthal of the University of Toronto, which is included in an article titled “Monty Hall, Monty Fall, Monty Crawl”, which was linked from the Coding Horror article.

The Monty Hall problem in its most common form has never really seemed all that unintuitive to me. Admittedly, yes, when I first heard the problem my immediate reaction was to claim that the probability of winning was 50-50, but the logic behind why that is not correct was clear when it was explained.

When I explain the solution to this problem to others, I use a variant of what Rosenthal refers to as “The Shaky Solution”. He gives it that derogatory name because the logic employed in that explanation is not readily generalizable to variants of the Monty Hall problem. Indeed, the main subject of his article is to present a method of reasoning that does generalize to variants. But the explanation I use (which is perfectly valid for the vanilla problem) is as follows:

In the Monty Hall problem, the option to switch is equivalent to the option of trading the contents of your original door for the contents of both other doors. From this it is obvious that picking two doors (switching) improves your chances of winning over picking only one.

Put another way, the choice to switch asks you to wager on whether you were right or wrong, and when you made your original selection, you had a 1/3 chance of being right.

So that is straightforward enough. I read Rosenthal’s article, and most of the other examples seemed similarly straightforward when they were explained. But the solution given to the “Monty Fall” problem made me pause and briefly doubt that the argument he was using was necessarily correct. The Monty Fall problem is stated as:

In this variant, once you have selected one of the three doors, the host slips on a banana peel and accidentally pushes open another door, which just happens not to contain the car. Now what are the probabilities that you will win the car if you stick with your original selection, versus if you switch to the remaining door?

And his solution, which claims that there is an equal probability of winning whether you switch or not, is given as:

In the Monty Fall problem, suppose you select Door #1, and the host then falls against Door #3. The probabilities that Door #3 happens not to contain a car, if the car is behind Door #1, #2, and #3, are respectively 1, 1, and 0. Hence, the probabilities that the car is actually behind each of these three doors are respectively 1/2, 1/2, and 0. So, your probability of winning is the same whether you stick or switch.

The question that came to mind is this: The Monty Fall problem seems to give no information beyond that which is available in the traditional Monty Hall problem. In particular, both problems seem to say only that a door other than the selected door was opened, and a goat was revealed. If the game is the same and the information is the same, then it would follow that the probabilities involved cannot possibly differ.

The key is, of course, that the information is not the same, and I will now go through the reasoning I used to convince myself that Rosenthal’s solution to the Monty Fall problem is indeed correct.

First, the problem statement as presented by Rosenthal elides what is actually a key piece of information. The problem says that we, the player, are operating under the assumption that Monty fell, and that the door he opened as a result of his spill was not the door that we selected, and also did not contain a car. But wait – Monty’s fall itself is implicitly described as a probabilistic event! Why are we allowed to ignore the other possibilities?

Let’s work this through, using Rosenthal’s own method of applying the Proportionality Principle. Rosenthal’s generalizable method for the Monty Hall problem is, in essence: For each door, calculate the probability that the described situation occurred given that the car is behind the door in question. Then, if you normalize the probabilities, the probability of winning by not switching is the probability that the described situation occurred given that the car was behind the door you originally selected.

But here, there are actually four possible “situations”. There are two binary choices associated with Monty’s fall. Either the door he opens is the player-selected door, or it is not. And either the door he opens contains the car, or it does not. In lieu of any other stipulations, I’ll make the reasonable assumption that the door that Monty falls into is chosen uniformly at random from all three available doors.

Then, the probability that he opens the player selected door is 1/3 (since the player selects only of three doors), and the probability that he opens the car door is also 1/3 (since the car is placed behind only one door). From this, we can draw up a table of the probability of being in any given situation after the fall:

The values given are simply the products of the probabilities of the two events in the row and column headers. Rosenthal’s explanation is limited to the case of Opens Other / Reveals Goat, which I will abbreviate as OO/RG.

Now, to use Rosenthal’s method, we must determine, for each situation, the door-by-door probability that each situation occurs, given that the car is behind the door. Without loss of generality, let’s denote the door we the player choose as Door #1. If Monty falls into a door other than yours, we call that Door #3.

We can compute this in two steps. First, we list the situation/door combinations, and mark a 1 when the combination is possible and a zero when it is not.

This gives us a description of all possible car-placement / situation pairs. For example, the intersection of the Opens Selected / Reveals Goat situation and the Door 1 car placement has a zero because it is impossible that the selected door (Door #1 by assumption) has the car and is also opened to reveal a goat.

Now, if we multiply the contents of each row by the probability that the situation occurs, we get this:

And if we normalize these probabilities (so that they add to one) we get

What this table describes is the complete, original state of the Monty Fall problem before Monty falls. For example, there is a 2/15 chance that the car has been placed behind Door #2 and also that Monty will fall into Door #1 (the player-selected door) to reveal a goat.

The important point is that this table is based on zero information beyond what is known in the vanilla Monty Hall problem. It is just as if we are speculating on what might happen if Monty were to fall. Therefore, we should expect that the probabilities implied by this table should be identical to the probabilities of the orignal problem. In particular, this table should tell us that if we must commit to a strategy before the game begins, the strategy of “pick a door and stick with it” works 1/3 of the time, and “pick a door and switch” works 2/3 of the time.

Does it? Add up the columns to find out the probabilities of the car being behind each door.

Now, recall that we “Door #1″ is just a label for “the door the player selected”. According to my version of the so-called “Shaky Solution” logic, the choice of whether to switch or not amounts to the choice between door 1 or both of doors 2 and 3. If we add the probabilities (and reduce the fractions), we get:

Which is exactly what one would expect. We have added no information to the problem, and so we have come up with precisely the same solution, even with all that mumbo-jumbo about what might happen if Monty were to fall.

But the key realization is this: While the knowledge that Monty will fall gives you no additional information, the knowledge of exactly how he fell (once he falls), does indeed give you new information. In particular, knowledge of how exactly Monty fell eliminates 3 of 4 situations from the speculative probability table above.

From a numerical standpoint, when Monty actually does fall into Door #3 and reveals a goat, the new information that you have been given is that all car-placement / situation pairs other than Opened Other / Revealed Goat are impossible, and should have their probabilities in the full table updated to zero. When you recompute from that point, you end up with the 1/2 probability of winning by staying that Rosenthal gives.

From a logical standpoint, when Monty actually does fall into Door #3 and reveals a goat, the player can infer that certain placements of the car were more likely to cause the random event of Monty’s tumble to reveal exactly what it did. That constitutes new information through indirect observation. A non-rigorous analogy would be that hearing your doorbell ring constitutes new information about whether or not someone is standing outside your door. It is possible that it rang of its own volition, or that a child many yards away just struck your ringer with a baseball, but it is more likely that someone is standing there ringing it.

In summary, the difference between the vanilla Monty Hall problem and the Monty Fall variant is that in both problems it is known a priori that Monty will attempt to open a door other than your selection which contains a goat. But in the Monty Fall problem, the extra information is that Monty failed to do this in a very specific way, and that his exact method of failure is something that is strongly influenced by the position of the car that you are trying to find.

In the previous article, I discussed the design decisions that were made in the greedy lottery wheel generator in order to get around the computational problems inherent in even a simple greedy generator for realistically-sized lotteries. In this article, I will walk through the mechanics of generating all tickets and matches, selecting a ticket for the wheel, and updating ticket meta-data in order to allow the next selection.

You can read the whole article here. In essence, this is a walkthrough, using text, diagrams, and pseudocode, of how exactly I went about implementing a greedy algorithm based lottery wheel generator. This article addresses my solutions to problems of time complexity, much as the previous article largely addressed the solutions to problems of space complexity.

The actual generator was implemented in, of course, C++. However this article contains no actual code, only pseudocode, so as to put emphasis on the algorithms and not the details. Besides, full details of any program can only really be understood by reading code itself, not descriptions of it with snippets. I have still not yet made available the source code to this generator, although that will be forthcoming. Hopefully I will have it cleaned up enough to be suitable for public consumption before the next article in the series is posted.

[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.

If you look back at the definition of the Cloneable<T> class from Monday’s post, you will notice that its sole constructor is a “copy” constructor that is not really a copy constructor at all but an implicit conversion constructor from the wrapped type T. This was intentional, and intended for convenience (although I also left out a true copy constructor, which was an error).

Since we can implicitly convert T to Cloneable<T> it should be trivial enough to construct a T any way we like and have it magically turn into a Cloneable<T>. The tricky part is that the pattern requires that the typedef for Cloneable<T> be the meaningful name, and true name of the type T be somewhat obfuscated. So it becomes inelegant to refer to T directly.

But all is not lost. We can extend Cloneable<T> and AbstractCloneable<T> like this (and note that I have added the missing copy constructors).

The key is on line 5. Now, if we have a class with a non-default constructor like so

We don’t need a factory to make a Derived. We can just do this

It’s not exactly the usual constructor syntax, but you are indeed accessing the constructor directly and not through a factory method.

So it turns out that the idea from Monday’s post is a lot more generally applicable than I originally thought. I think I’ll start using it myself.

Edit: This post originally ended here, but as commenter Matthias points out below, this is not quite complete. In particular, calling Derived::construct doesn’t work because it constructs a raw Derived_ object outside of its Cloneable wrapper. Derived_ inherits from AbstractCloneable<Base_>. As the name implies, AbstractCloneable<Base_> is abstract, and outside of its wrapper, the Derived_ object does not provide an implementation for the abstract clone method in AbstractCloneable<Base_>.

The solution is adding one more small shim, a wrapper class to be used when deriving from AbstractCloneable classes:

(If you find the use of T::construct above to be confusing, you could always add a second typedef in AbstractCloneable that calls the base class something that seems more intuitive in this kind of circumstance.)

This provides an implementation of clone() in Derived_ for the sole purpose of appeasing the compiler in order to allow the creation of temporary Derived_ objects. Keep in mind that the Derived_ class is internal, and is not intended to be used by consumers of this class hierarchy, so the only time that a raw Derived_ object should exist is temporarily when invoking Derived::construct to create a Derived object.

Note that the implementation of clone in AbstractCloneableParent is private. That is because in all cases invoking this implementation is an error. It is a function called “clone” which does not clone at all, and in fact slices the object. Therefore we want to be sure that if someone ever does create a Derived_ object that at least they will get an error if they try to call clone() on it, rather than having it behave in an unintuitive manner. Granted, one could still access that clone() implementation through a Base* that points to a raw Derived_ object, but in the end there’s only so much you can do to protect people from themselves.

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.

Now, I’m not trying to say that simplification is wrong. For example, when introducing STL containers to a student of C++, it would be sufficient to explain that vector is a container whose elements must all be of one type, and that the notation vector<string> means that this particular vector will contain string objects. This gets across the idea of exactly what the angle-bracket notation means in the context of containers, and a student can extrapolate from that with success. One need not launch into a detailed explanation of the C++ templating system in order to provide an adequate and non-evasive explanation.

The key is not so much to be exhaustive but to give the student a sense of control. When I was ten years old, I experienced an epiphany regarding computers. A friend of mine came to my house, sat at my computer, and showed me how to rearrange groups in Windows 3.1′s program manager, and how to change settings in the control panel. Before that point, I felt like I was operating in an environment that I could not control – that the rules of the system were hidden from me, and that as a consequence I had to interact with the operating system in a very specific, scripted, inflexible way. By showing me how things worked, and how they were configured, and demonstrating that the operating system was truly under my control.

From then on, I had a much easier time learning how more complicated interactions with the computer worked. The explanation gave me a foundation of knowledge to build on, rather than just a script, and the feeling of control and understanding gave me confidence to experiment. So it is also with programming. A novice programmer must be comfortable in his or her language environment in order to be an effective learner.

As I mentioned above, a particularly crucial point where a student should be told everything up front, is a first introduction to a programming language – in particular, a first introduction to a first programming language.

Here, there is a distinct difference between which language is used to teach. Consider the “boilerplate” code that a language requires — the minimum framing code that must go before, or around, any executable code that the instructor wishes to demonstrate in order to make a complete, valid program.

In some languages, this is quite minimal and easy to explain. For example, in Python (or analogously in Perl, Ruby, Bash, or almost any other interpreted language), all you need is something like

Or in fact nothing at all if you use the interpreter interactively, or provide the source file as an argument to the interpreter. When the shebang line is needed, the explanation can be terse: “This line tells the computer which programming language interpreter should be used to run this program.” Though you may still need to explain the term interpreter if you have not yet already.

In C or in C++, you end up with something a bit more involved, like:

The return statement is not strictly necessary but in my opinion things are more confusing without it. Here, to give the student an understanding of the boilerplate code, you must explain the concept of a function. With a simple function like this, such a thing can be done with an analogy to mathematical functions with which the student is likely familiar. The only sticking points would be giving a rationale for why a function may take no arguments (which does not happen in mathematics), and perhaps explaining the concept of side-effects lest the student take the analogy with mathematical functions too literally. This level of explanation can easily be done within the prologue to a first lesson.

But then you get to something like Java (or similarly, C#), wherein the minimal boilerplate code is the following:

Here, the requirements for fully understanding the boilerplate code balloon substantially. To fully understand this code, in addition to everything that needs to be explain in the C/C++ example, one must understand what access modifiers are, what a string is, what an array is, where the args parameter will come from, what a class and an object are, what a method is, and how a static method differs from a non-static method. This goes far beyond what one could, or would want to, explain as introductory material, and here the temptation to say, “Just write this around your code. Don’t worry about what it does, I’ll tell you when you’re older,” becomes very great indeed.

For this reason I think that Java and C# (and other purely object-oriented languages) suffer a severe handicap as first teaching languages. In order to write code in an object-oriented language and understand what it is that you are writing, one must first understand the concept of objects, which is a very difficult thing to explain without first teaching other programming concepts. This handicap applies not only to the boilerplate code, but extends into any introductory instruction, as so many language features revolve around objects. One must continue to put off the explanation of what objects are and why they are employed while still instructing the student to use and create them frequently.

These languages are nevertheless popular as starter languages because they feature automatic memory management and enforce object-oriented design. While both of these are indeed important, in my opinion they do not warrant the sacrifice of having to teach beginners that cargo-cult programming is sometimes acceptable. Besides, one can get quite far even in C++ without needing to touch manual memory management (which any serious programmer must eventually learn anyway), and object-oriented design can be taught independently of language once a sufficient familiarity with programming in general has been established.

In my opinion, an ideal teaching language is a multi-paradigm language so that instruction can begin with imperative programming, which is the simplest to explain in full, move on to procedural programming, and then finally to object-oriented programming and beyond, all without changing syntax. This allows knowledge to build, and encourages the student to comprehend what it is that he or she is writing, knowing that it will be built on later, rather than (as I discussed earlier) feeling like the program is not fully within his or her control.

Of course, there is a language that has the benefits of being multi-paradigm and memory-managed, and also has a very minimal boilerplate: Python, which I mentioned earlier. I’m curious as to why it is not more often used in formal education as an introductory language, given its excellence at being both straightforward to explain to a beginner and powerful when used by a professional. Perhaps it is a systematic bias against interpreted languages? Or maybe the faculty of Computer Science departments have all experienced one too many irritating Makefile typos and retain a vehement hatred for significant whitespace.

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.

First, let’s take a look at a simple, straightforward use of the virtual copy constructor idiom

(Virtual destructors, while extremely necessary in real code like this, have been omitted for space). This allows a proper deep copy to be made in this situation:

Here, b_copy will point to an object of whatever Base-derived class b originally pointed to, and no information will be sliced.

Note something that might seem peculiar about the signature of the clone() method. In Base it is declared to return a Base*, but in Derived it is declared to return a Derived*. This is made possible by a feature of C++ called covariant return types. Without these, the following would not be possible, even though it is obviously desirable.

So now to the question of how we implement clone() in a generic way that does not require its implementation to be repeated in each derived class. This can be done using a templatized Cloneable mix-in class.

Now, all Derived has to do is inherit from Cloneable<Base, Derived> in addition to Base directly, and the clone() method is automatically added

You can go further by defining a purely abstract ICloneable interface and having Base and Cloneable both inherit virtually from it, but we’ll save on complexity and avoid that here.

The practice of a derived class inheriting from a templatized class where the derived class itself is one of the template arguments is known as the curiously-recurring template pattern. This works great, except for one thing – we’ve lost covariancy.

If you don’t really care about this, then the above implementation of the virtual constructor idiom is by far the cleanest solution to the slicing problem. But a lack of covariancy in the clone() method pretty annoying not to have in a lot of cases, so you would be right to want it back.

As you might guess, the obvious solution of defining the Cloneable mix-in as

doesn’t work, otherwise we would have done that in the first place. The error you will get if you try this is that the compiler will complain that it is illegal override clone() returning Base* with clone() returning Derived*. That seems odd, since we did that successfully in the very first non-templatized example.

The reason why this doesn’t work has to do with the “timing” involved in how the curiously-recurring template pattern works. In short, when we declare Derived to derive from Cloneable<Derived>, the compiler doesn’t necessarily know that Derived also derives from Base and so can’t be sure that covariancy between Base* and Derived* is legal.

In order to get around this – and this is, from what I can tell, the novel part of this post – we must instead add the clone() method after we have already defined a complete Derived class that is fully recognizable as a subclass of Base. We do this by inverting the mixin pattern. Instead of having a Derived inherit from a Cloneable, we instead have a Cloneable class inherit from a Derived. Or, to be more generic, we define a templatized Cloneable class that can inherit from any copy-constructable class.

The AbstractCloneable class exists so that we can also use this pattern on abstract base classes that cannot be directly instantiated, as the clone() method’s implementation requires.

Now, instead of having Derived inherit from Base and from Cloneable<Derived> we invert the pattern and define an intermediate Derived_ class that inherits from Base, and then use a typedef to make Cloneable<Derived_> masquerade as Derived. We also do this analogously with Base and AbstractCloneable.

If you don’t like the appended-underscore convention, you can use whatever convention of your own you like, or even a separate namespace.

Covariancy is accepted by the compiler in this case because the initially-declared return type of clone() is AbstractCloneable<Base_>, and the return types of all overrides are types that are fully and unambiguously defined to be subclasses of AbstractCloneable<Base_> before being used as template arguments.

This implementation conquers the problem we set out to solve: we now have a way to add virtual copy constructors to a class hierarchy while avoiding re-implementing the clone() method for each derived class, and without sacrificing covariancy. All you have to do is add a typedef after each derived class. This is quite convenient, assuming you don’t mind too much the slight obfuscation of class names involved in using this method. With the above pattern, all of the following work

However, there 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. Therefore, this pattern is completely inappropriate unless you are using a factory pattern to construct your derived objects, and the factory is aware of the quirky type hierarchy. Fortunately, using a factory pattern is quite common in cases where one would run into this problem, so this restriction does not entirely defeat the point of this exercise. [Ed: you may want to read the addendum to this article that I posted, which further addresses this issue.]

Whether this new pattern is useful or not is debatable. It adds a fair bit of complexity and obfuscation in order to eliminate a relatively small amount of code duplication. It may be more useful if the code necessary to clone an object were for some reason more complex than simply calling a copy constructor, but I cannot immediately think of a situation in which this might be the case. Nevertheless, the above demonstrates that covariant, templatized virtual copy constructors are at least possible in C++ under a not-unreasonably-restrictive set of circumstances.