by Martin Erwig
Determining the precise typing behavior of an algorithm is, like determining its termination behavior, an undecidable problem (see chapter 11). Consider, for example, an algorithm in which only the “then” branch of a conditional contains a type error. This algorithm contains a type error only when the condition of the conditional evaluates to true and selects that branch. The problem is that figuring out the value of the condition might require an arbitrarily complicated computation (for example, the condition could be a variable whose value is computed in some loop). Since we cannot be sure whether such a computation terminates (since we cannot solve the halting problem), we cannot know in advance whether the condition will be true, and thus we cannot know whether the program will exhibit a type error.
To deal with this inherent inability to predict the behavior of an algorithm, static type checking approximates the types within an algorithm. To avoid computations that could lead to nontermination, static type checking is overcautious and reports a type error whenever there could be one. In the case of the conditional this means that a static type checker would require both alternatives to not contain a type error, since it can’t compute the value of the condition. It would thus report a type error even if only one branch of the conditional contained one. Even though the algorithm might not exhibit any type error when executed, a static type checker would flag the algorithm as type-incorrect and not execute it. This is the price to be paid for the safety of static type checking: Some algorithms will be rejected even though they might not actually produce an error when executed.
Static type checking trades immediacy for accuracy. While an error might not necessarily happen later, it could. If the computation is important enough to not risk failure, it is better to fix the potential error in the algorithm before executing it. The cautious approach of static type checking is not unique to computing. There are many other domains in which checks are performed in advance. If you are boarding a plane, you rely on the pilots making sure there is enough fuel on board and that all important systems function. You are expecting static type checking of the rules for a successful flight. Consider the alternative of checking the systems after take-off. Detecting a problem at that time could be too late. Or, if you are to receive a medical procedure or prescription, the doctor should make sure that any contraindication is determined before the treatment to prevent any harm. Static type checking follows the maxim “Better safe than sorry.” Following static typing, Ron should not have used the Eat Slugs spell; because of his broken wand the rule for applying magic is not applicable and foreshadows a mistake during the execution of the spell. In contrast, dynamic typing is a less aggressive approach for enforcing typing rules that doesn’t let any opportunity for computation pass, thereby running the risk of encountering errors during the execution of an algorithm. This is what Ron did. He took a chance, and it didn’t work.
Building Code
The violation of a typing rule is a sign that something is wrong. A type error in an algorithm indicates that it probably won’t work correctly. Viewed positively, when all parts of an algorithm satisfy the typing rules, then some kinds of mistakes cannot happen, and the algorithm is correct to a certain extent. Of course, the algorithm can still produce incorrect results. For example, if we need an algorithm for adding two numbers, which has the type (Number, Number) → Number, but we accidentally create an algorithm for subtracting numbers, then this algorithm still has the correct type, but it doesn’t compute the right values. Nevertheless, in a type-correct program a large number of errors have been ruled out, and one can be sure that the steps of the algorithm conform to an important level of consistency.
Shielding against incorrect or meaningless computation is an important role of types and typing rules, but it is not the only benefit they offer. Types also act as explanations of the steps of an algorithm. Without understanding the details of every step in an algorithm, we can get a high-level picture of what is being computed when we just look at the types. The ability to differentiate between computations by their types was illustrated by the task of picking the envelope with the right algorithm. The ability of types to summarize a large number of computations provides insights that cannot be gleaned by just looking at a few examples. Thus, types and typing rules also have explanatory value.
To illustrate, let’s take another look at the game of Quidditch. The game can be explained without showing an actual game by describing the general rules and the roles of different players. This is, in fact, how Harry learns it from Oliver Wood in Harry Potter and the Sorcerer’s Stone.5 The rules of the game constrain the valid actions in the game and define how the score is kept. The important aspect is that the rules of the game are typing rules that use types for the roles of players (such as “seeker”) and kinds of objects (such as “quaffle”). While seeing an example game would be helpful, it is not enough to understand the game. In particular, even after having watched many games, someone who doesn’t know the rules can be easily surprised. For example, a Quidditch game ends immediately when a seeker catches the Golden Snitch. This may not have occurred in the examples that have been watched, so it would surprise an observer the first time it happened. Other games have special rules that can be surprising, for example, the offside rule in soccer or the en passant move in chess. It is difficult to learn a game by just watching examples, and it can take a very long time for all the rules to be acted out.
Similarly, it can be quite hard to understand what an algorithm does just by watching its inputs being transformed into corresponding outputs. While types are generally not sufficient to precisely describe the effect of an algorithm, they explain some of its behavior on a high level, and they support the understanding of how its parts (the individual steps and control structures) fit and work together.
Types structure the objects of a domain, and typing rules explain how they can be combined in meaningful ways. In computer science, types and typing rules ensure the meaningful interaction of different parts of an algorithm. They are thus important tools for building larger systems out of smaller ones. This is explored in chapter 15.
At the End of the Day
As a long day of computing comes to an end, you reflect on all that has happened, and you note some of the events in your diary. Getting up in the morning wasn’t really different from other days in any way. Nothing extraordinary happened that would warrant mention in the diary. Brushing your teeth a little longer than normal or even running out of toothpaste—these are not events that you would like to be reminded of years from now. The same is true for most of what happened during the day. Since you have breakfast every day and commute to work every workday, starting the diary entry with something like “This was mostly another ordinary workday” implies a standard getting-up and breakfast routine. Specifically, the name workday refers to a whole detailed description of getting up, having breakfast, commuting to work, and all the other routines that occur during an ordinary workday.
Assigning a (short) name to a (long) description and then using the name to refer to the description is a form of abstraction. Like representing different cities by the same kind of point on a map, the name workday ignores differences between weekdays and regards them as all the same. However, since the points on the map appear at different locations, they are not identical. Similarly, different mentions of workday occur at different times, so they are not identical either. The different positions in space and time provide context and additional meaning to references. For example, one city is located by the sea or can be reached by a particular highway, and one workday falls on election day or follows a holiday.
While effective in many situations, a plain name or symbol can sometimes be too abstract a representation. To supply different references with additional information, names and symbols can be extended by parameters. For example, points for representing cities are sometimes parameterized by size or color to distinguish larger from smaller cities. Or the shape of the symbol is varied to distinguish the c
apitals of states, and so on. Similarly, the name referring to a day can be parameterized. In fact, the name workday already distinguishes that day from, say, a holiday, on which you would not commute to work.
The full potential of parameters unfolds when they are referenced in the abbreviated descriptions. For example, suppose you want to add to your diary an entry about an important meeting or your visit to the doctor’s office. Like workday, the terms meeting and doctor’s appointment are abstractions that stand for a number of things that typically happen during such events. Most likely, in addition to writing that you had an important meeting, you would add whom you met with and what the purpose of the meeting was, and for the doctor’s appointment you would probably mention what kind of doctor you had to consult and for what reason. This information would be represented by a parameter for the abstraction and used in its description. Just as when a bakery offers to customize birthday cakes with decorations for name and age, the abstraction meeting is extended by the parameters who and purpose, which then are referred to in the description of the abstraction. When you use an abstraction as in “meeting with Jill about hiring,” the parameters are replaced by “Jill” and “hiring,” and the description reads as if it were written just for this particular meeting.
Abstractions identify patterns and make them reusable. Through parameters, abstractions can be flexibly adapted to specific situations and still convey a lot of information in a concise form. Assigning a name to an abstraction and identifying its parameters defines its interface, which determines the proper use of the abstraction. Much of what computer scientists do on a daily basis is identifying, creating, and using abstractions to describe and reason about computation. Computer science studies the nature of abstractions and formalizes their definitions and uses to empower programmers and software engineers to develop better software.
In the final chapter of this book I explain what abstractions are and the role they play in computing. Since abstractions play an important role in natural languages and computer science, it is not surprising that stories can explain a lot about computing.
15
A Bird’s Eye View: Abstracting from Details
The examples of computation in this book were all rather small, which is good for illustrating concepts and principles, but do they scale up? The question of scalability arises in different places.
First, there is the question of whether algorithms work for large inputs. This problem is addressed by analyzing the runtime and space complexity of algorithms, discussed in the first part of this book, in particular, in chapters 2, 4, 5, 6, and 7. While some algorithms scale quite well (following a path, making coffee, searching, and sorting), others don’t (optimizing a lunch selection with a limited budget). As explained in chapter 7, the runtime of exponential algorithms effectively prohibits the solution of some problems.
Second, there is the question of how to create, understand, and maintain large software systems. Designing and writing a small program is relatively easy, but producing large software systems still poses a major challenge for software engineers.
To see what the problem is, imagine a map of the city or country you live in. What would be a good scale? As explained by Lewis Carroll in his last novel Sylvie and Bruno Concluded, a scale of one to one is useless since, if the map were spread out, “it would cover the whole country and shut out the sunlight!” Thus any useful map has to be much smaller than what it represents, and it therefore has to omit many details. An important question in creating a map is, What scale is small enough to be manageable yet large enough to represent sufficient detail? Moreover, which details should be ignored and which should be kept? The answer to the latter question often depends on the context in which the map is used. Sometimes we need to see the roads and parking garages; in other situations we’re interested in the bike paths and coffee shops. This means that the map should be configurable to individual needs.
Any description that is shorter than what it talks about faces these challenges of finding the right level of generalization and providing means for configuration. Such descriptions are called abstractions. Much of computer science is concerned with the question of how to define and effectively use abstractions. Most prominently, an algorithm is an abstraction of many different computations, and its parameters determine what particular computation will unfold when the algorithm is executed. An algorithm manipulates representations, which are also abstractions that preserve details to be exploited by the algorithm and ignore others. The level of abstraction in an algorithm and its arguments are related. Finding the right level of generality for an algorithm often involves a trade-off between generality and efficiency. To handle a wider range of inputs often requires a higher level of abstraction for the inputs, which means the algorithm has fewer details to exploit.
An algorithm is expressed in a language and is executed by a computer. All these concepts make use of abstractions too. And finally, the abstraction from individual computations achieved by algorithms requires abstraction also for the concepts of runtime and space efficiency because an effective characterization of an algorithm’s efficiency needs to be independent of the size of the different inputs.
This chapter illustrates that abstraction permeates all major concepts of computer science. I first discuss the issues that arise in defining and using abstractions by contemplating an abstraction for the stories used in this book. Then I explain how abstraction applies to algorithms, representations, runtime, computers, and languages.
To Make a Long Story Short
A variety of stories were mentioned in this book: a fairy tale, a detective story, an adventure story, a musical fantasy, a romantic comedy, a science fiction comedy, and a fantasy novel. While these stories are all quite different, they do have several things in common. For example, they all center on one or more protagonists who must face and overcome a challenge, and they all have a happy ending. All but one of the stories exist in book form, and all but one involve some form of magic or supernatural force. Even though these brief descriptions omit details from each individual story, they still deliver some information that helps to distinguish stories from, say, sports reports. However, there is a clear trade-off between the level of detail a description reveals and how many examples it applies to. There seems to also be a trade-off between the amount of detail provided and the time required to understand the description because more details lead to longer descriptions. This problem can be addressed by introducing names for specific descriptions, such as detective story, in which the protagonist is a detective who investigates a crime. Tag lines, movie previews, and other short summaries are important because they are an effective way to deliver relevant information about what to expect of a particular story, and they help us make faster decisions. For example, if you don’t like detective stories, you can anticipate that you probably won’t enjoy reading The Hound of the Baskervilles.
How would you go about generating a summary statement for a collection of stories? You could start by comparing two of the stories and remember all the aspects they have in common. Then you could compare the result with what is contained in the third story and keep those things all three stories have in common, and so on. This process filters out, step by step, aspects that do not apply to a particular story and keeps those that are common to all of them. This elimination of distinguishing details is called abstraction, and one also sometimes talks about the “abstraction from details.”1
In computer science, the description that is the result of an abstraction is itself also called an abstraction, and the examples are called instances of the abstraction. Using the same name, abstraction, for the process and the result might be confusing. Why don’t we just use a similar term, such as generalization? This seems to be fitting, since a generalization is also a summary that matches a number of specific instances. However, the term abstraction in computer science means more than generalization. In addition to the summarizing description, it typically has a name a
nd contains one or more parameters that can be identified with concrete values in the instances. The name and the parameters are called the abstraction’s interface. The interface provides a mechanism for using an abstraction, and the parameters link key elements of the instances to the abstraction. While generalization is solely driven by the instances, the need for defining an interface makes abstraction a more deliberate process that involves decisions about what details to omit. For example, we can elevate a story generalization “How protagonists overcome a challenge” to a story abstraction by giving it the name Story and identifying the parameters protagonist and challenge:
Story(protagonist, challenge) = How protagonist(s) solve(s) the problem of challenge
Like the parameters of an algorithm, the parameters of the Story abstraction are used in the description as placeholders to be substituted by whatever arguments Story will be applied to. (The potential singular/plural in protagonist(s) and solve(s) is used to have the description match both single and multiple protagonists, and replacing “overcome a” with “solve(s) the problem of” makes the following examples easier to read.)
In the story of Hansel and Gretel the protagonists are Hansel and Gretel, and the challenge is to find their way home. We can express this fact through an application of the Story abstraction to the corresponding values for the parameters:
Story(Hansel and Gretel, finding their way home)
This application denotes a story of two protagonists, Hansel and Gretel, who solve the problem of finding their way home.