On Ada Lovelace Day, one is encouraged to write about a great woman involved in computer science. That’s today, and I’ll take Barbara Liskov! She figured out what she, in her book “Program Development in Java”, modestly calls “the substitution principle”, but everyone else in the world calls “the Liskov substitution principle”.

It’s an insight that, like all good insights, ends up seeming obvious in retrospect. In particular, it states that if you have some new code which you would like to use to replace some old code, then, if you want to have a safe program and not touch any other parts, the following conditions must hold:

  • The new code isn’t more particular about it’s input than the old code
  • The new code doesn’t output things which would be invalid coming from the old code
  • The new code preserves all of the promises of the old code
  • If you couldn’t change a part of the old code, then you can’t change it in the new code either.

These rules are a little intimidating — but they start making sense when you think about them. Imagine, for instance, substituting one piece of A/V equipment for another. You couldn’t do a straight substitution if the new one couldn’t accept signals that the parent was okay with, and this corresponds to condition 1. You couldn’t do a straight substitution if the output of the new piece of equipment was in a format that the parent couldn’t output, and this corresponds to condition 2. The last two conditions are more peculiar to programming, but have a similar level of intuitiveness.

She figured out exactly what it means for software to be “swappable”, and for that and other reasons she was awarded the Turing award. But in particular, her research is of a kind that I think we need more of in CS: the formalization of observational research on how people program and what trips them up. As a science, we are still at the Linnaeus “naming things” stage. We need larger and better and more-full taxonomies of problems and solutions. For figuring out how a piece of the programming taxonomy could work, Liskov gets my vote for Ada Lovelace day…