Indirection

Goals

• Understand the concept of indirection in computer science.
• Be able to apply indirection to a real-life situation.

Concepts

• agent
• delegate
• Domain Name System (DNS)
• DNS server
• domain name
• indirection
• IP address

Lesson

One of the most important concepts in computer science is that of indirection, permeating all areas of software development. It is so important that a famous computer scientist named David Wheeler (as recounted by Butler Lampson, who envisioned the personal computer) once said that all problems in computer science can be solved by another level of indirection. Without understanding indirection, your ability to write computer programs with any complexity or utility will be extremely limited.

What is indirection? Quite simply it means not direct. If there is a direct connection between two things, indirection means that something is placed in the middle so that another level of indirection is created.

Go ask your mother!

When you were a child, you might have gone to your father and asked, Dad, may I stay late at the beach today? He might have responded, Go ask your mother! Every family is different; perhaps your mother sometimes told you to go ask your father. Either way, this is an example of indirection—rather than give you an answer directly, you were told to go ask someone else.

Perhaps you work in a small restaurant, and you are given this schedule of chores. It is a small restaurant with few workers.

1. 12:00 p.m.: Set the tables
2. 1:00 p.m.: Wait on customers
3. 3:00 p.m.: Take a break
4. 4:00 p.m.: Clean the bathrooms
5. 5:00 p.m.: Wait on more customers

However some of the days at 4:00 p.m. the manager wants you to take out the trash, and another worker to clean the bathrooms. The manager might make several sets of chore lists. Or the manager might simply substitute step #4 with indirection:

1. 12:00 p.m.: Set the tables
2. 1:00 p.m.: Wait on customers
3. 3:00 p.m.: Take a break
4. 4:00 p.m.: Ask manager for chore
5. 5:00 p.m.: Wait on more customers

Changing Paths

Indirection is about adding intermediate steps to the procedure. It allows us to change parts of the procedure without changing the original plan. Consider a very old children's rhyme from the 1800s by Lydia Maria Child:

Over the river, and through the wood,
    To grandfather's house we go; …

If we consider the first lines as instructions for getting to grandfather's house, we might write them down like this:

1. Cross the river.
2. Go through the woods.
3. Arrive at grandfather's house!

But what if the river is frozen? What if the woods are on fire? These instructions aren't very flexible for the changing circumstances! Instead we could place signposts along the way, pointing to the next signpost. If we need to go around the woods because they are dangerous, we simply change the sign on the other side of the river to point to the detour.

1. Follow the first signpost in front of the river.

The original instructions can now simply say follow the first signpost in front of the river. Through the power of indirection, we never need to change these initial directions, as we can now change the intermediate steps if we need to.

Delegation

A simple example of indirection in real life can be seen in managing a store. If a person owns a small business, many times the owner has many roles to fill. The owner of a store may need to determine prices and purchase new stock, yet still find time to open the store and greet customers. The owner has a direct relationship with managing the store, and it looks like this:

As the business grows and responsibilities increase, the owner may hire a manager to unlock the store and greet customers. By using an agent (which is a general term for someone who acts on the behalf of someone else) to manage the store, the owner now has an indirect relationship withe day-to-day management duties.

Using indirection provides the owner with two big benefits, which you will see in other areas of software development:

delegation

The owner can delegate duties to the manager, who may do a better job at managing the store than the owner.

flexibility

If the manager is not doing a good job, the owner can replace the manager with a better manager.

Thus this single added level of indirection brings flexibility to the arrangement, potentially improving the job that gets done.

Localizing Changes

A large part of the flexibility of indirection is that it localizes changes. As you saw with the manager scenario, using an indirect relationship provides a single point where changes can be made. If the manager is not doing a good job, he/she can be replaced with a better one. The owner and the store do not need to be changed.

Imagine if a store owner has a safe with all the store's valuables. The safe is very strong and has a key that is very expensive to copy. If the owner has several employees, it will be costly to make so many copies of the key.

The problem grows bigger if the key is somehow compromised. Perhaps one employee leaves to work somewhere else and forgets to return the key. Now what? The owner has no choice but change the key to the safe, which is a huge expenditure—not to mention the high cost of making copies of the new key for all the employees.

Using a level of indirection makes the problem of key compromise easier to surmount. The owner can have two sets of keys: one key for the central safe, and many duplicate keys for a smaller safe that will hold the key to the main safe. The smaller safe need only be large enough to store a single key, and its keys are inexpensive to duplicate.

To gain access to the main safe, an employee must user his/her key (Key1) to open the smaller safe to gain access to the key to the main safe (Key2). This second key, Key2, may only be used on the premises and must be placed back in the smaller safe when finished accessing the main safe.

Now if one of the employees leaves the company or loses his/her copy of Key1, the owner merely needs to change the key to the smaller safe and make new copies for the employees—all at a much lower cost than changing Key2.

Preventing Redundancy

The other side of the coin of localizing change is preventing redundancy. A layer of indirection can gather together information in one place that might normally be spread out in several locations.

Let's imagine that a store keeps a list of its current stock of toys and furniture, along with the supplier it uses to procure additional items when stock runs low.

Notice that several items are sourced from the same suppliers, resulting in duplicated information in the table. What if Acme Furniture changed its address? The store owner would need to go through every item in this list that is purchased from Acme Furniture and update the address.

How can indirection help the owner here? By introducing a unique code for each supplier, the owner can maintain a separate table with information on each supplier with no information duplicated.

Because of the extra indirection of the supplier code, finding a supplier name and address takes the extra lookup step of following the supplier code from one table to the other. But the gain is that there is less duplicated information. Consequently if one of the suppliers has to change its address, this modification can be made on just a single line of the Suppliers list rather than multiple lines in the Item Stock list.

There is another benefit: the store owner now can keep track of suppliers even for which there are not yet any products. Here the store owner has added the name and address of Top Toys Corporation. If in the future there are toys purchased from Top Toys Corporation, the owner can simply add the code TOP to the Item Stock list for those new items.

DNS Resolution

The Internet Domain Name System (DNS) provides a good example of how indirection can be used to make connections flexible between computers. Every computer on the Internet is assigned a unique number called an IP address that (as of version 4) looks something like xxx.xxx.xxx.xxx, for example 1.2.3.4. But it would be tedious (not to mention hard to remember) if you were required to enter these number directly into your browser when you wanted to surf the web. Furthermore, you would have problems accessing the web site if the site's owners had to move the content to a different computer with a different IP address.

The DNS provides levels of indirection that address this problem. Simplified greatly, the DNS lives on a separate computer called a DNS server, and is essentially a big table containing domain names (the names used e.g. by web site servers) and their corresponding IP addresses. Conceptually in part it looks like this:

When you ask your computer to browse to http://www.myserver.com:

1. Your computer first goes out to a DNS server and asks for the IP address of www.myserver.com.
2. The DNS server responds that the IP address of www.myserver.com is 1.2.3.4.
3. Your computer then makes a connection directly to the computer with IP address 1.2.3.4 (the computer running the web site of www.myserver.com).

Although this indirection results in an extra lookup step for your computer, it provides a tremendous flexibility:

• It allows you to specify web sites in terms of easy-to-remember domain names instead of cryptic IP addresses.
• If a web site (e.g. www.myserver.com) decides to move its content from one server (e.g. with IP address 1.2.3.4) to another (e.g. with IP address 5.6.7.8), nothing has to change on your computer. Only the table on the DNS server needs to be updated. From your view the process looks exactly the same, you are never aware that the web site moved to another physical computer!

Review

Summary

Indirection makes the relationship between two things less direct by adding some additional lookup layer between them. While this makes the system more complex; it also brings flexibility by promoting delegation and consolidating redundant information, and providing for localized changes. Indirection is one of the fundamental concepts that permeates computer software development, but its overuse can make a system hard to understand and raise the risk of errors.

Gotchas

• Add as much indirection as necessary, but too much indirection can make a system too complicated to understand, which increases the risk of errors.

In the Real World

• Indirection is used everywhere in the real world, in day-to-day software development.

Think About It

• If you are designing a program and working with some entity doesn't provide enough flexibility, think about whether you should provide another entity in the middle—that is, an additional layer of indirection—to direct you to the original entity.

Self Evaluation

• What is indirection, in your own words?

Task

Imagine that you are the owner of the store described in the lesson. You decide to change the toy supplier for the toys and purchase them from Top Toy Corporation.

With the current design of the Item Stock list, you would have to look at all the toys in the list and change each of their suppliers, one for each line. With many toys, this could take some time and require changing many lines. But you have noticed in the Item Stock list that all of the furniture comes from one furniture supplier, and that all the toys come from one toy supplier. You would like to be able to change the furniture supplier for all the furniture items; or the toy supplier for all the toy items; just by changing one of the lines in one of the lists.

How might you introduce another level of indirection to make it possible, with your new set of lists, to change the toy supplier for all the toys from Bozo Toy Company to Top Toy Corporation by changing only one line in the Item Stock list? Think about the indirection used by DNS that allows server IP addresses to be changed without changing a web site's domain name.

• You must create another level of indirection to complete this task.
• Create a new set of tables representing same information contained in the the lists of Item Stock and Suppliers above, yet that uses an additional new level of indirection.
• Create a word processing document that provides all the new tables used to complete this task.
• Explain in detail how, using the new set of tables you have created, the owner could change the supplier for all the toys just by changing one line in a list. Imagine that the store owner is a complete imbecile, and that you must explain each step precisely. The explanation must include specific instructions such as these:
  1. The store owner would like to change the toy supplier for all the toys from Bozo Toy Company to Top Toy Corporation.
  2. To make the change, the store owner must change the single line line in the table table, changing the value in the column column from old value to new value.
• Email the finished document to your teacher.

See Also

• Indirection (Wikipedia)

References

• Principles for Computer System Design (Butler Lampson). Turing lecture, 1993-02-17.
• Another level of indirection (Diomidis Spinellis). In Andy Oram and Greg Wilson, editors, Beautiful Code: Leading Programmers Explain How They Think, chapter 17, pages 279–291. O'Reilly and Associates, Sebastopol, CA, 2007.

Acknowledgments

• Indirection, simply explained cartoon by Geek & Poke licensed under CC BY 3.0.
• Over the river, and through the wood … from The New-England Boy's Song about Thanksgiving Day by Lydia Maria Child, in the public domain.
• DNS lookup diagram from blog post by Liviu Tudor on the web site of Dyn, a company that provides DNS services. Used with permission from EMEA Marketing Coordinator on 2015-11-12.
• Some symbols are from Font Awesome by Dave Gandy.