by Martin Erwig
David Mitchell’s book Cloud Atlas consists of several stories that are nested within one another. Nested stories play a central role in the movie Inception, where a group of people steal ideas from other people’s minds by infiltrating and manipulating their dreams. For a difficult mission, they have to perform their dream manipulation recursively, that is, once being within the dream of their victim, they have to perform the manipulation to the person in the dream.
Mutual recursion occurs in Richard Cowper’s Worlds Apart, which tells two stories, one of a married school teacher on earth who invents a world with a married couple, and the other of a married man on another planet who invents a story about a married school teacher on earth. A similar story unfolds in the movie The Frame, which is about a paramedic who watches a TV show about a thief who himself watches a TV show about the life of the paramedic. Mutual recursion also appears in Lewis Carroll’s Through the Looking-Glass when Alice encounters a Unicorn and both consider each other fictional creatures.
Types and Abstraction
Harry Potter
Time for Dinner
After finishing the work on your quilt, it is time to prepare dinner. Which silverware you need to set the dinner table depends on what will be served. If you prepare soup, you will use spoons, for spaghetti you will need (also) forks, and for meat you will need both knives and forks. The properties of different dishes call for different features of eating utensils. The shape of the spoon supports carrying liquids, the tines of the fork help with catching and holding on to the spaghetti strands, and the blade of the knife makes it easy to cut the meat into pieces. The rules about when to use spoons, forks, and knives illustrate several important aspects about language.
First, the rules talk about types of eating utensils, that is, they do not distinguish between different individual spoons, forks, or knives. All those are grouped together into categories, and the rules talk about arbitrary members of those categories. This is important, since it allows for an economical description that employs as few rules as possible. Suppose the word fork were not available to collectively describe all the forks in your kitchen drawer, and instead you had names for each fork, say, Pointy, Spiky, Sharpy, and so on. To express a rule about needing a fork for eating spaghetti, you would need to mention each individual fork. If you had to talk in the same way about spoons, knives, plates, and so on, you would have a hard time coming up with names and remembering them all, and the rules would become quite complicated. If this sounds ridiculous, that’s because it is—and it illustrates how important types are in making language effective. The words soup, spaghetti, and meat are also used as types in the rules, since they refer to general food categories, not to a particular dish made at a particular time and place. You may notice that the word food is also a type, which encompasses soup, spaghetti, and meat; it is a type at a higher level. This shows that types and individual objects can organize concepts into hierarchies, which make languages more efficient through generalizations. Types are a powerful linguistic tool for organizing knowledge in support of effective reasoning.
Second, the rules express relationships between different types, such as food and eating utensils. Rules put to work the knowledge about objects represented in types. In particular, they facilitate reasoning about objects and allow us to draw conclusions about objects’ behavior. The rule about using a fork to eat spaghetti indicates that using a fork for that purpose will be successful but using a spoon probably won’t be. The rule encodes prior experiences about the interaction of objects, and by using types it can represent these experiences in a succinct form.
Third, the rules are predictive, which means that you can pick the silverware and set the table even before the meal is ready and still be certain that the chosen eating utensil will be appropriate for the dish. (It also means that by violating the rules, you may go hungry.) This matters, since it makes the dinner algorithm more efficient: it allows you to set the table while the meal is still cooking. Since the rule is a reflection of previous eating experiences, it saves you from having to find out every time you have soup that a fork or knife won’t do the job.
Using a fork or knife to eat soup would be a mistake. This insight can be derived from the rules about proper eating utensils. Since the rules talk about the types of objects, irrespective of which individual spoon or fork or soup is used, any action that violates such a rule is called a type error. There are two kinds of type errors. First, there are errors that have failure as an immediate consequence. For example, using a fork to eat soup is such a failure. These errors are real in the sense that they make an intended action, such as eating, impossible. The algorithm gets stuck, and since no progress is possible, it has to be aborted. Second, there are errors that do not lead to failure but describe situations that are nevertheless considered wrong or ill advised. For example, it is possible to use a spoon to drink water, but few people would normally do that, probably because it’s inefficient and doesn’t provide a satisfying drinking experience. Similarly, while it is not unusual to use a straw for drinking water, this would be rather weird for wine. Again, this is not a mistake that makes the action impossible, but it is nevertheless considered foolish.
In computation, operations are applied to values. With their ability to impose structure, type-based rules about the composition of computation can help make sense of algorithms, predict their behavior, and identify errors in their execution. Just as phone jacks and electrical outlets have different shapes to protect appliances from damage and people from injuries, rules about types in algorithms can prevent computations from causing bad consequences. Chapter 14 examines the magical power of types through some of the adventures of Harry Potter and his friends.
14
The Magical Type
Of all the stories in this book, the tale of Harry Potter may be the one most widely known. Among the many factors that contribute to its popularity is that the story revolves around magic, which obeys different laws than the rest of the physical universe. Therefore, these stories must develop rules about what is and what is not possible in the realm of magic and indicate how these rules interact with the ordinary laws of nature. This last aspect is particularly important for the Harry Potter adventures because they, unlike many other stories involving wizards and magicians, take place in present-day England, not in some distant place or time.
If the magic in the Harry Potter books were arbitrary and not governed by laws, the stories would quickly become pointless. When readers cannot form reasonable expectations of what happens next or what the unknown cause for a particular event could be, they are less motivated to read on. Rules that capture the laws of nature, the “laws” of magic, and other regularities in our lives are important for understanding events and their causes. They are also essential for planning ahead. These laws are necessarily general and refer to types of things, not individuals, because a law’s power lies in its ability to represent a large number of individual cases. Types not only characterize objects but also categorize actions. For example, teleportation, a train ride, or Hansel and Gretel’s walk through the forest are all examples of movements. A simple law for movements is that moving something changes its position. Since this is true for any movement and any object, this law is about types, not individuals.
In the realm of computing, laws that describe regularities of computations are called typing rules. These constrain the admissible inputs and outputs of algorithms and thereby can find mistakes when executing algorithms. Moreover, since types operate on a fine-grained level, that is, for operations and their arguments in each step of an algorithm, typing rules can be employed to find type errors in algorithms. This is such an important task that it is done itself by algorithms that are called type checkers. If an algorithm doesn’t violate any of the typing rules, it is said to be type correct, and its execution is guaranteed to be free of certain errors. Types and typing rules go a long way toward ensuring that algorithms behave as intended, and they can serve
as guidelines for building reliable algorithms.
The Types of Magic and the Magic of Types
The most fascinating aspect of magic is probably that it makes the impossible possible. The transformation of objects or people beyond what is reasonable under natural laws is captivating and stimulates the imagination. The Harry Potter books are, of course, full of such examples. However, the employed magic is subject to many restrictions and obeys a number of laws. One reason for limiting the power of the magic is that this makes the stories more mysterious and intriguing. Since not everything logically conceivable is actually possible in the world of Harry Potter, the reader has to wonder how Harry Potter and his friends will be able to master particular challenges in the different adventures. If they could always use some kind of superspell to solve any particular problem, the story would become boring. Since the magic is not all-powerful, a significant part of the Harry Potter books is devoted to explaining its rules, including its possibilities and limitations.
To help make sense of the magical world, it is categorized into a number of related concepts. For example, a person who can perform magic is called a wizard (or a witch), whereas an ordinary person who cannot perform magic is called a muggle. Wizards are further distinguished into different professions such as aurors, arithmancers, curse breakers, herbologists, and many others. Magical actions are called spells and are further classified into charms, curses, transfigurations, and other categories. The name assigned to a category is rather arbitrary and doesn’t really matter; what is important are the properties and behaviors that all objects in one category have in common. And just as important as the meaning of individual magic categories are the relationships between them. For example, spells can be cast only by wizards, but a spell can affect wizards and muggles alike. The magic in Harry Potter can be quite complicated. To effectively cast a spell, a wizard typically needs to employ a wand and has to make an incantation. However, experienced wizards can also cast nonverbal spells without wands. The effect of a spell is usually temporally bound, and it can also sometimes be protected against through a counterspell. Magic can also be conserved in potions, and this enables even muggles to perform magic if they have access to potions. That magic is not a trivial matter is also reflected in the fact that young wizards and witches have to attend wizarding school for seven years to master the subject.
The classification of people or objects into different categories according to particular properties or abilities applies, of course, not only to magic; it happens in virtually all domains of life. Classification is ubiquitous in science, and it is a basic component of our everyday understanding of the world; we employ it unconsciously in our reasoning all the time. Examples range from rather mundane tasks, such as selecting silverware for dinner or clothes according to the weather, to more abstract realms, such as classifying and reasoning about philosophical and political ideas. The process of classification itself is studied systematically in computer science because it can greatly enhance our understanding of computation and help us create more reliable software in practice.
In computer science, a class of objects that behave in a certain way is called a type. We have encountered types already in several different ways. In chapter 4 we saw different data types (set, stack, and queue) for storing and maintaining collections of objects. Each such data type has a distinctive way of inserting, retrieving, and removing elements from a collection. For example, a stack retrieves objects in the reverse order in which they were put into the stack (last in, first out), and a queue retrieves them in the order they were entered (first in, first out). Thus, a particular data type encapsulates a specific behavior for manipulating collections of elements. The behavior of a data type makes it suitable to support specific computation tasks. For example, in chapter 13, I used a stack data type to explain how an interpreter works and keeps track of different arguments when algorithms are invoked recursively.
Another use of types is in describing the required or expected input and output for algorithms. For example, the type of an algorithm for adding two numbers can be described as follows:
(Number, Number) → Number
The type of the algorithm’s argument(s) is shown to the left of the arrow and the result type to its right. Thus the type says that the algorithm takes a pair of numbers and produces a number as a result. Note that the type of algorithms for subtracting, multiplying, or any other binary operation on numbers would be the same as that for addition. This shows that a type is not tied to a particular algorithm or computation, which is consistent with types being descriptions of classes of things. In this case, the type describes a wide range of computations.
As another example, consider the getting-up algorithm in chapter 2, which has the parameter wake-up-time to tell the algorithm when to sound the alarm. This parameter needs as input a time value, that is, a pair of numbers indicating the hour and minute of the wake-up time. Moreover, the two numbers cannot be arbitrary: the hour value must be a number between 0 and 23,1 and the minute value must be a number between 0 and 59. Numbers outside these ranges are meaningless and would cause the algorithm to behave in unexpected ways. We could therefore describe the type of the getting-up algorithm as follows:
(Hour, Minute) → Alarm
Here Hour and Minute are types for subsets of numbers as described, and Alarm is a type for alarm behaviors. An alarm behavior is making a particular sound at a specific time, and just as the type Minute contains the numbers 0 through 59, the type Alarm contains 24 × 60 = 1,440 different alarm behaviors, one for each minute of a day. If the alarm sound is configurable, then the algorithm needs another parameter, which must be reflected in the type as well, and the result type Alarm has to be more general as well and incorporate different sounds.
We can see that the type of an algorithm tells us something about the algorithm. It doesn’t tell us precisely what the algorithm does, but it narrows down its functionality. This is often enough to choose between algorithms. One would obviously not use an algorithm for addition for the problem of sounding an alarm at a specific time. Without even looking at the details of the addition and getting-up algorithms, one can tell this already from their different types. The type of an algorithm contains an arrow to separate the type of its arguments (to the left) from the type of its result (to the right). It says that the corresponding computation transforms input of one type into results of the other. The result type can be a value, as in the case of addition, or an effect, as in the case of the getting-up algorithm.
Since spells are transformations too, we can apply types to characterize their effects as well. For example, in the Harry Potter books, objects can be levitated using the Wingardium Leviosa spell, in which the wizard has to move the wand, point it toward the object, and use the incantation “Wingardium Leviosa.” Assuming that the types Object and Levitating denote arbitrary and levitating objects, respectively, the type of the spell can be described as follows:
(Wand, Incantation, Object) → Levitating
Types are a useful notation to talk and reason about properties of algorithms and computations. The arrow to separate arguments from result types is one critical part of that notation. The use of type parameters is another. As an example, consider the sorting algorithms discussed in chapter 6. A sorting algorithm needs as input a list of items, and it produces a list of the same items as a result. Moreover, the items must be comparable in some way, that is, we must be able to determine for two items whether they are equal or whether one is larger than the other. Since numbers are comparable, the following type is a valid type for any sorting algorithm that sorts lists of numbers:
List(Number) → List(Number)
Writing the type for lists of numbers as List(Number) indicates that different list types can be obtained by replacing Number. For example, since we can also sort textual information, a sorting algorithm can also have the type List(Text) → List(Text). To express that sorting algorithms can have a number of different though relate
d types, we can replace any specific item type such as Number or Text by a type parameter, which can be substituted by a specific type. We can thus express the type of sorting algorithms by the following template, where comparable stands for any type whose elements can be compared:2
List(comparable) → List(comparable)
Any specific type, such as List(Number) → List(Number), can be obtained from this type template by substituting an item type for the type parameter comparable.
By attaching a type to the name of an algorithm with a colon, one can assert that the algorithm has that particular type. For example, to assert that the sorting algorithm Qsort has this type, we would write the following:
Qsort : List(comparable) → List(comparable)
The Count algorithm in chapter 12 also takes a list of items as inputs, but it doesn’t require the items to be comparable, and it returns a number as a result. Thus the type of Count can be described as follows, where any is a type parameter that stands for an arbitrary type:
Count : List(any) → Number
To know the type of something tells us what it can do and what can be done with it. Knowing the types of algorithms helps us select and apply them appropriately. The type information can help with that in several different ways.
First, if we want to execute a particular algorithm, its input type tells us what kind of arguments we need to supply. For example, a spell needs an incantation and a wand to be applied, whereas a potion has to be drunk. It makes no sense to drink a spell or to use an incantation and wand movement on a potion. Similarly, a sorting algorithm such as Qsort can be applied to a list, but it makes no sense to apply it to a time value. Without arguments of the required types, an algorithm cannot be executed.