Once Upon an Algorithm
Page 31
It’s worthwhile reflecting on what has been accomplished here. Suppose you want to quickly explain to somebody the gist of the story of Hansel and Gretel. You can do this by first saying that it is a story, that is, by referring to the Story abstraction. This works, of course, only if the other person knows what a story is, that is, if they understand the Story abstraction. In that case, a reference to the abstraction invokes in the other person the description of what a story is. Then you provide details to fill in the roles represented by the parameters protagonist and challenge, which turns the generic description of a story into a more specific one.
Technically, the application of the Story abstraction leads to replacement of the abstraction name by its definition and the substitution of the values “Hansel and Gretel” and “finding their way home” for the two parameters in the definition (see chapter 2). This substitution leads to the following instance:
How Hansel and Gretel solve(s) the problem of finding their way home
The relationship between instance and abstraction is illustrated in figure 15.1.
Once we have given a summary for the story of Hansel and Gretel in terms of the Story abstraction, we may want to refer to it even more succinctly by assigning it a name. In this case, the name of the story happens to be the same as that of the protagonists:
Hansel and Gretel = Story(Hansel and Gretel, finding their way home)
This equation says that Hansel and Gretel is the story of Hansel and Gretel solving the problem of finding their way home. That the story name and the names of the protagonists agree is purely coincidental, even though this actually happens fairly often. Here is an example where it doesn’t occur:
Groundhog Day = Story(Phil Connors, escaping an endlessly repeating day)
Again, the instance represented by the application of the abstraction can be obtained by replacing the abstraction name with its definition and by substituting values for the parameters:
Figure 15.1 Definition and use of abstractions. The definition of an abstraction assigns it a name and identifies parameters that are referred to by its definition. The name and parameters are the abstraction’s interface, which prescribes how the abstraction is to be used: through its name and by supplying arguments for its parameters. Such a use generates an instance of the abstraction, which is obtained by substituting the arguments for the parameters in the definition of the abstraction.
Groundhog Day = How Phil Connors solve(s) the problem of escaping an endlessly repeating day
In the story of Hansel and Gretel, finding their way home is not the only challenge they face. Another salient part of the story is that they have to escape the witch who tries to eat them. Thus the story could be described in the following way:
Story(Hansel and Gretel, escaping the witch)
This description uses the same Story abstraction. Only the argument for the second parameter is changed. This fact raises several questions about abstractions. First, what do we make of ambiguity in abstractions? Since the story of Hansel and Gretel can be regarded as an instance of the Story abstraction in different ways, and since both of the shown instances provide accurate information about the story, neither one of the two could be said to be more correct than the other. Does this mean that the definition of the abstraction is flawed? Second, the Story abstraction does not just abstract from the details of one particular challenge; it also focuses on one particular challenge (at least, for stories that contain several). For example, describing Hansel and Gretel with the Story abstraction leaves at least one challenge unmentioned, which raises the question of whether we could define the Story abstraction so that it accounts for multiple challenges in a story. This is not difficult, but what is the right level of detail for such an abstraction?
Say When
When is an abstraction general enough to cover enough instances? When does it leave out too many details and lack precision? Whenever we are forming an abstraction, we have to decide how general it should be and how much detail it should provide. For example, we could use the description “sequence of events” instead of the Story abstraction to characterize the stories in this book. This would be accurate, but it would leave out some important aspects and be less precise. On the other hand, we could use more specific abstractions, such as “fairy tale” or “comedy.” However, while these provide more details than the Story abstraction, they are not general enough to apply to all stories. In fact, even the fairly general Story abstraction is not general enough to cover stories in which the protagonists fail to solve the problem. We could address this shortcoming by adding another parameter that can be substituted by either “solve” or “don’t solve,” depending on the situation. Whether generalizing Story in this way is a good idea depends on the usage of the abstraction. If the “don’t solve” case never comes up, the extra generality is not needed, and the current simpler definition is preferable. However, the usage context for abstractions may change, and thus one can never be absolutely sure about the chosen level of generality.
In addition to finding the right level of generality, another problem in defining an abstraction is deciding how many details to provide in the description and how many parameters to use. For example, we could add a parameter to the Story abstraction that reflects how the challenge was overcome by the protagonists. On the one hand, adding parameters to an abstraction makes it more expressive, since it provides a mechanism to expose more subtle differences between different instances. On the other hand, it makes the interface of the abstraction more complicated and requires more arguments when the abstraction is used. A more complex interface not only makes an abstraction more difficult to use but also makes applications of the abstraction more difficult to understand, because more arguments have to be substituted for parameters in more places. This counteracts one of the major reasons for using abstractions, which is to provide concise and easy-to-grasp summaries.
Balancing the complexity of interfaces and the precision of abstractions is one of the core problems in software engineering. We could actually characterize the plight of programmers through an instance of the Story abstraction:
Software Engineering = Story(Programmers, finding the right level of abstraction)
Of course, there are many other challenges for programmers, and some can be neatly summarized using the Story abstraction as well. Here is one more struggle that every programmer can empathize with:
Correct Software = Story(Programmers, finding and eliminating bugs)
Finding the right level of abstraction is also an issue for the Story abstraction. There are two different ways to define Hansel and Gretel as an instance of the Story abstraction. Picking one instance that focuses on one challenge means abstracting from (ignoring) the other. But what if we want to use both instances to provide a more comprehensive account of the Hansel and Gretel story? This can be done in different ways. First, we can simply mention both instances side by side:
Story(Hansel and Gretel, finding their way home) and
Story(Hansel and Gretel, escaping the witch)
This looks a bit clunky. In particular, the repeated mention of the protagonists and the Story abstraction seems redundant. This is apparent when we perform the substitution and generate the following instance:
How Hansel and Gretel solve(s) the problem of finding their way home, and how Hansel and Gretel solve(s) the problem of escaping the witch
Alternatively, we could simply combine both challenges into one argument for the challenge parameter:
Story(Hansel and Gretel, finding their way home and escaping the witch)
This works reasonably well. You may have noticed that the same thing was done with the protagonists: Hansel and Gretel were grouped together and substituted as one text unit for the protagonist parameter. But we can also see that the flexibility of using single or multiple protagonists does not come for free. In the definition of the Story abstraction the use of protagonist(s) and solve(s) had to work grammatically with both singula
r and plural subjects. (To allow for multiple challenges this also had to be done with problem(s).) It would be nice if the Story abstraction could generate separate, grammatically correct instances for each case.
This can be achieved by defining the Story abstraction so that its first parameter is a list of protagonists. Then two slightly different definitions are given, depending on whether the parameter is a single protagonist or a list of two:2
Story(protagonist, challenge) = How protagonist solves the problem of challenge
Story(protagonist1→protagonist2, challenge) = How protagonist1 and protagonist2 solve the problem of challenge
Now if Story is applied to a single protagonist, such as Phil Connors, the first definition using the singular verb is chosen, whereas when Story is applied to a list of two protagonists, such as Hansel→Gretel, the second definition with a plural verb is selected. In that case the second definition decomposes the list into its two elements and inserts and between them.
It seems that the Story abstraction provides a means to create English sentences. In chapter 8, I demonstrated grammars as a mechanism to do just that. So couldn’t we alternatively define a grammar for story summaries? Yes. Here is one possible grammar that corresponds to the latest definition of Story.3 Apart from minor notational differences, such as using an arrow instead of an equal sign or using dotted boxes to mark nonterminals rather than dotted lines to mark parameters, the two mechanisms basically operate in the same way by substituting values (or terminals) for parameters (or nonterminals).
story
→ How protagonist solves the problem of challenge
story
→ How protagonists solve the problem of challenge
protagonists
→ protagonist and protagonist
Table 8.1 in chapter 8 compares grammars, equations, and algorithms. It shows the common roles of the constituting parts of the different formalisms and thus emphasizes that grammars, equations, and algorithms are different but similar mechanisms for describing abstractions.
The preceding discussion shows that the design of an abstraction is not a straightforward task. By encountering new use cases one may recognize changing requirements that force changes in the definition of the abstraction. Such changes can lead to a more general abstraction or to one that exposes different details. In some cases, this might cause a change to the interface, for example, when a new parameter is added or when its type is changed. An example is the change of the protagonist parameter from a single value to a list. When the interface of an abstraction changes, all existing uses of the abstraction have to be changed as well to conform to the new interface. This can be a lot of work and might have a ripple effect of causing changes to other interfaces as well. Therefore, software engineers try to avoid changing interfaces whenever possible and consider it often only as a last resort.
A Run of Abstractions
Consider the last definition of Story that uses a list of protagonists. While the equations work only for lists that contain either one or two elements, the definition can be easily extended to work for lists with an arbitrary number of elements using loops or recursion, as demonstrated in chapters 10 and 12. Using separate equations to distinguish between different cases and the idea of processing lists indicate that the Story abstraction might actually be an algorithm for producing short story descriptions. As it turns out, there is more to this than meets the eye, and I next discuss the relationship between algorithms and abstractions in more detail.
Given the importance of abstraction in computer science, it isn’t surprising that one of its central concepts, the algorithm, is itself an example of an abstraction. An algorithm describes the commonality of a number of similar computations, whether following pebbles or sorting lists; see figure 15.2.4 Different individual computations result when the algorithm is executed with different arguments substituted for its parameters.
The Story abstraction seems to be a post hoc generalization, that is, the summarizing description is created after having seen many existing stories. This may happen occasionally for algorithms as well. For example, after you have repeatedly prepared a certain meal, changing the ingredients and modifying the method to improve the outcome, you may finally decide to write down the recipe to ensure that the culinary experience can be repeated in the future. However, in many other cases an algorithm is a solution to an unsolved problem and is created before any computation is ever run. And this is what makes the algorithm abstraction so powerful. In addition to describing computations that have already happened, an algorithm can generate completely new computations as needed. An algorithm has the power to solve new problems not encountered before. In the context of the Story abstraction, think of some arbitrary protagonists and a specific problem, and you have the beginning of a new story.
Figure 15.2 An algorithm is an abstraction from individual computations. Each algorithm transforms representations. A type abstracts from individual representations. If Input is the type of representations accepted by an algorithm, and Output is the type of representations produced by it, then the algorithm has the type Input → Output.
The following analogy illustrates this point further. Consider a simple network of roads, and assume that two roads were built to connect the cities A and B and C and D, respectively. It so happened that the two roads cross each other and that an intersection was built as well. Suddenly, new connections become possible, and we can travel from A to C, from B to D, and so on. The road network facilitates not only the trips it was built for, but also potentially many others that were not anticipated.
The observation that algorithms are abstractions can be understood in two ways. First, the design and use of algorithms enjoys all the benefits of abstractions but also bears all the costs. In particular, the problem of finding the right level of abstraction is relevant to the design of algorithms because the efficiency of an algorithm is often affected by its generality. For example, mergesort takes linearithmic time. Mergesort works on any list of elements and only requires that elements can be compared to one another. It is thus the most general sorting method imaginable and is widely applicable. However, if the elements of the list to be sorted are drawn from a small domain, then bucket sort can be used (see chapter 6), which runs faster in linear time. Therefore, in addition to the potential trade-off between generality and precision, algorithms also have the trade-off between generality and efficiency.
Second, we can exploit algorithmic elements in the design of abstractions. The Story abstraction provides a good example of this. Its sole purpose is to produce descriptions of stories; no computation is intended. However, since a well-designed abstraction identifies key aspects of individual stories through the use of parameters, we notice the need for dealing with lists of protagonists and challenges in a more flexible way. In particular, the distinction between lists having different numbers of elements proves useful in producing specialized story descriptions.
Since the execution of algorithms is tantamount to functional behavior, algorithms are also called functional abstractions. But algorithms are not the only example of functional abstractions. Spells in Harry Potter are functional abstractions of magic. When executed by a wizard, a spell brings about magic. Each time it is executed, it brings about a different effect, depending on whom or what it is directed at and how well the spell was performed. Similar to an algorithm, which is expressed in some language and can be executed only by a computer that understands that language, a spell is expressed in the language of magic, which includes incantations, wand movements, and so on, and it can be executed only by a skilled wizard who knows how to perform that spell. Potions are another abstraction of magic. They are different from spells in that their execution is much easier. It doesn’t take a wizard to unleash the effect of a potion. Anybody, even muggles, can do it.
Many machines are functional abstractions too. For example, a pocket calculator is an abstraction of arithmetic operations. As a potion expands access t
o magic beyond wizards, a calculator expands access to arithmetic to people who do not have the necessary skills to perform calculations. It can also expand access by accelerating the process even for people who do have those skills. Other examples are coffee makers and alarm clocks, which are machines that can be customized to reliably perform specific functions. The history of transportation vehicles illustrates how machines enhance the efficiency of the abstracted method (in this case traveling) and sometimes also simplify the interface to expand the access to more people. Carriages needed a horse and were relatively slow. Cars have been a big improvement but still require driving skills. Automatic transmissions, safety belts, navigation systems—all make the use of cars as a transportation method more accessible and safer. We can expect even more expanded access in the coming years with the advent of self-driving cars.
One Type Fits All
Algorithms and machines (and spells and potions) are examples of functional abstractions, since they encapsulate some form of functionality. The passive representations that are being transformed in computations are also subject to abstraction, called data abstraction. In fact, the concept of a representation is inherently an abstraction, since it identifies some features of signs to stand for something (see chapter 3) and by doing so actively ignores other features, that is, it abstracts from those features.
When Hansel and Gretel find their way home by tracing pebbles, the size and color of the pebbles don’t matter. The use of the pebbles as a representation for locations creates an abstraction that ignores the differences in size and color and focuses instead on their feature of reflecting the moonlight. When we say that Harry Potter is a wizard, we emphasize the fact that he can perform magic. In contrast, we do not care about his age or that he wears glasses or any other interesting piece of information about him. By calling Harry Potter a wizard we abstract from all those details. The same applies when we point out that Sherlock Holmes is a detective or that Doc Brown is a scientist. We highlight features commonly associated with those terms and temporarily ignore everything else about the person.