In this post, author Martin Erwig discusses the process of writing his new book Once Upon an Algorithm: How Stories Explain Computing.
No, I did not write the book in less than seven minutes; it took me more like two or three years. Seven minutes is the time I typically spend riding the bus on my morning commute to work. Of the many interesting discussions I have had with the people I regularly meet on the bus, some ended abruptly when I had to get off at my stop. “To be continued” is not a satisfactory strategy to cope with the time constraint, because it’s often not clear when you will meet the same group of people again, and more often than not another topic has come up and occupies the conversation.
This problem nagged me especially when we were discussing questions related to my work as a computer scientist, including topics from my research or questions about specific computing concepts. Computer science affects almost everybody today, and does so in many different forms. Thus, people are naturally curious about it, and I enjoy answering their questions. However, while the impact of computing is concrete, the underlying concepts are often abstract and difficult to explain in a few words.
A typical approach employed in the classroom is to introduce a series of definitions, layering concept upon concept, which will then allow one to describe a particular problem and its solution precisely and succinctly. But while this might work well in a classroom setting where more time is available and the audience can be expected to be more accepting of longer threads of explanations, it often fails when talking with laypeople. During my bus rides, I experienced this first hand. And it was not just the 7 minute time limit that posed a problem; it is also hard to keep explanations intriguing over a period of time, so that people don’t lose interest and want to change the subject.
I came up with a different approach to effectively deliver explanations of computing ideas, namely to identify computer science concepts in everyday situations and stories. When the example scenarios are well known and well understood, you don’t have to construct a nexus of definitions—you can simply point to the elements in the scenario and exploit the understanding of the relationships to explain the corresponding computing concept.
The first example that came to mind was the fairy tale of Hansel and Gretel, specifically the part where they found their way back home from the forest by following a path of pebbles. This episode alone can be used to explain several different aspects of computing. First, there is a problem to be solved, namely finding the way home. Second, the process of actually finding the way is the result of executing an algorithm that describes how to go from pebble to pebble. Third, the process, which is called a computation, takes time and requires resources (the pebbles). Finally, Hansel and Gretel have to be careful to avoid previously visited pebbles because they could otherwise end up in a nonterminating loop. The story illuminates several other more intricate aspects as well, such as the fact that pebbles serve as a representation or that the order in which the pebbles are dropped and then visited corresponds to a stack data type.
Once I had found a story that could explain some concepts of computing, the natural thing to ask was whether there are other stories for explaining these and further concepts and which computing concepts can be explained in this way at all.
The next topic I wanted to tackle was that of languages. While the idea of an algorithm is probably the most prominent notion associated with computing, algorithms cover only part of computing. To get a more complete picture of what computer science is about, one has to realize that algorithms are typically expressed in some language, which opens the door to concepts such as loops and termination, recursion, types, and abstraction.
Finding a suitable story for explaining language concepts took quite a while. I read and re-read George Bernard Shaw’s Pygmalion, Lewis Carroll’s Alice in Wonderland and Through the Looking-Glass, and several stories by Jonathan Swift. While these all deal with language in interesting ways, I thought they fell short in exposing those aspects that are important in the context of computing, including syntax, ambiguity, and semantics. Ultimately, I chose a music piece to illustrate language concepts. The choice fell on Over The Rainbow, one of America’s most popular songs. A music piece also provided sufficient distance to not confuse the language concepts to be explained with the music example used as explanation. At the same time music contains much of the structure of textual languages.
Many of the other story choices arose rather naturally—heavily influenced, of course, by my own taste in movies and stories. I simply had to use the movie Groundhog Day to illustrate loops and the Halting Problem, and the adventures of Indiana Jones seemed to be just right for talking about searching, sorting, and also problems that are too difficult to solve. Once I had decided to explain recursion through time travel, the choice of the Back To the Futuremovie trilogy was a no-brainer. It was also a good excuse to rewatch all the movies—after all, this was serious research.
One distinction between math and computer science is that math is concerned with relationships between quantities whereas computer science also asks how efficiently such quantities can be determined. Some algorithms and representations, despite being able to yield correct results, are simply too slow to solve problems in practice. In these cases computer scientists look for more efficient solutions. In some way, I was confronted with the same problem on my bus rides: Not only did I have to find explanations of computing concepts, but I had to find a way of explaining that met the time limit of 7 minutes. The solution was to employ stories as more efficient representations for the task.
Interestingly, the story about the bus rides itself illustrates another concept that plays an important role in computer science, namely that of “meta” (metavariables, metaprogramming, metamodels, etc.). In this particular case, it is the use of computer science to facilitate the explanation of computer science. This is similar to metafiction as in Chaucer’s The Canterbury Tales or Margaret Atwood’s The Handmaid’s Tale. But I better stop here so that this blog post can be read in less than seven minutes.