Chapter 2 — Abstraction: An Introduction to Design

Site Index

Each of chapters 2, 3, and 4 of Algorithms and Data Structures: The Science of Computing delves into one of computer science’s methods of inquiry by exploring one element of that method in detail. In chapter 2, the method of inquiry is design, and the element is the role of abstraction in making design manageable. This chapter also introduces object oriented programming (or reviews it, for readers who have seen it before) as a vehicle for expressing design abstractions.

Interacting Methods of Inquiry

While chapters 2, 3, and 4 nominally place each method of inquiry into its own chapter, they also illustrate that the methods are not really as easily separable as this organization suggests. Thus the relatively formal notions of pre- and postconditions are almost as prominent in chapter 2 as the more pragmatic elements of crafting object oriented algorithms are. Indeed, an important message of the chapter is that using those formal notions to develop pragmatic algorithms from formal problem specifications is an important ingredient in designs that work correctly. This idea re-emerges more explicitly in chapter 3’s proofs of correctness; chapter 3 will draw on (and even expand) chapter 2’s design ideas. Instructors should therefore ensure that students study both the formal and the pragmatic aspects of design presented in chapter 2.

The inseparability of computer science’s methods of inquiry is a theme that should pervade courses based on Algorithms and Data Structures: The Science of Computing. Students should finish such courses (and readers should finish the book) appreciating that even if they most enjoy one method (e.g., some enjoy crafting programs, others enjoy proving formal theorems), they will be more successful in that method if they can also understand and use the others.

Classroom Activities

The authors accompany this chapter with two classroom activities. One makes basic object oriented concepts tangible, and the other gives students a concrete example of abstraction and why it is so important in understanding complex systems.

Object Oriented Concepts

To give students tangible examples of many object oriented concepts, we use an abbreviated form of human chess. In other words, we have the class play a game we call “mini-chess,” in which student volunteers act as playing pieces on a “board” laid out on the floor, and other students direct them to move. To fit within the space and time of a typical class, mini-chess is played on a 4-by-4 board, using pawns, knights, queens, and kings (although instructors can certainly use different subsets of the standard chess pieces of they wish). The initial set-up of a mini-chess board is as shown here:

Note that each queen is opposite the opposing king; this is not the standard starting configuration for chess, but it avoids giving the first player to move a trivial win. The rules for moving pieces are exactly the same as in regular chess. A typical mini-chess game only lasts for a few moves.

To set up a mini-chess game, we prepare paper props that the human pieces will carry to identify themselves: crowns for kings and queens (we make identical crowns and recruit male students to be kings and females to be queens, but one could also use the common chess iconography of crowns with crosses for kings and crowns with spikes for queens), swords for knights, and simple squares for pawns. The color of the paper indicates the color of the piece. We then lay out the chess board on the floor of the classroom with painters tape (a paper tape with a weak adhesive, used for masking surfaces in painting, and available in hardware stores; it can be removed easily from things without leaving a residue). Squares on the board should be about three feet on a side to allow people to stand comfortably on them, although in classrooms where the furniture doesn’t move out of the way, smaller squares may be necessary. Finally, we recruit actors: a total of 16 students willing to play the parts of pieces, who wear or carry the appropriate paper prop and stand on the appropriate square of the board, and two students who will be “chess masters.” We then let the “chess masters” take turns telling pieces where to move, until someone wins or the game reaches a stalemate. Note that in small classes, one can play mini-chess with only a subset of the pieces, although such games may lead to stalemates or quick wins for whoever moves first. These things don’t matter pedagogically, but they make the game less fun for the students.

Before the mini-chess class, we ask students to read the first three sections of chapter 2, to become familiar with basic object oriented concepts and with pre- and postconditions. We also warn students that we will playing a form of chess in the next class, so that students can review the rules of the game if they wish. After playing the game in class, we ask students to identify concepts from the book that they observed in the game. Concepts that the game demonstrates include…

• Objects. The pieces are clear examples of objects. (Chess masters and the board may also be seen as objects, although they don’t embody the concept as clearly as pieces do.) Pieces have all the key characteristics of objects, namely…
  • Behavior, since pieces move in specific ways in response to the directions they receive from chess masters
  • State, for example position on the board, or in-play vs captured status
  • Distinct identities, made tangible by the fact that each piece is represented by a distinct person.
• Messages. The directions that the chess masters give to the pieces are messages. Most of these directions convey the basic command “move,” albeit with a much more flexible syntax than messages in programming languages, or even pseudocodes. The fact that the directions are delivered verbally allows students to perceive the act of sending a message, and provides an analogy for message delivery inside a program.
• Parameters. The “move” command that chess masters send to pieces is supplemented with information on which square a piece is to move to. Conveying supplemental information is exactly what parameters to messages do. As with the messages themselves, the format for “parameters” is far less rigid in mini-chess than in programs or pseudocode, but the fundamental concept is the same in both contexts.
• Classes and Subclasses. The set of all pieces is a class, characterized by handling the “move” message and by having state related to position or in-play/captured status. If students consider the chess masters or board to be objects, then these objects represent additional, very different, classes. In any case, since different kinds of piece respond to “move” messages differently, pawns, knights, kings, and queens each represent a different subclass of “piece.”
• Inheritance. Pawns, knights, kings, and queens inherit the state information that all pieces have. They also inherit the “move” message interface, although not its implementation.
• Preconditions. Chess has precise rules about when a move is legal. For example, you cannot make a move that exposes your own king to capture, most pieces cannot move through a square occupied by another piece, etc. These rules are preconditions for the “move” message.
• Postconditions. Each move has a number of consequences — at the very least, the moved piece’s position changes, and possibly an opposing piece gets captured, the opposing king is placed in check, etc. These consequences are postconditions of the “move” message. Some of these postconditions are conditional, i.e., they are only established some of the time. This can lead to discussion beyond what is in the book about how to specify such postconditions (is the condition part of the postcondition, as in “…and any opposing piece that was on the square this piece moved to is removed from play?” Is it clearer to use multiple precondition/postcondition pairs, as in “precondition 1: there are no pieces on the squares this piece moves over or stops on; postcondition 1: this piece is on the new square; precondition 2: there are no pieces on the squares this piece moves over but an opposing piece is on the square on which this piece stops; postcondition 2: this piece is on the new square and the opposing piece is removed from play?”) This is a discussion that probably won’t produce definite conclusions, but it does provide an opportunity to talk about which (if any) style the instructor prefers, when one style might be better than others, etc.
• Object oriented design. An interesting example of alternative class hierarchies sometimes arises while discussing mini-chess: should the immediate subclasses of “piece” be “pawn,” “knight,” “queen,” and “king,” or should they be “black piece” and “white piece,” with sub-subclasses “black pawn,” “white pawn,” “black knight,” etc? In the former case, should there be “black” and “white” sub-subclasses of “pawn,” “knight,” “queen,” and “king?” Such issues of class design are really beyond the scope of Algorithms and Data Structures: The Science of Computing, but if someone raises them they offer an opportunity to preview software engineering issues that more advanced courses may explore. (To offer an answer to the question, although probably not the only defensible one, the interfaces and behaviors of differently colored pieces are really identical, so it makes sense for color to be a publicly readable part of a piece’s state, but not to be reflected in classes.)

Abstraction

Abstraction is something that almost everyone practices, but that many people are not consciously aware of or able to define. By examining a specific example of this paradox, we can help students understand what abstraction is, and appreciate its importance. Our current favorite example is the cellular telephone: a cell phone is “really” a sophisticated computer on an elaborate wireless network. Users of cell phones don’t think of them this way, however; users think of cell phones as relatively simple variations on the familiar telephone. This is an act of abstraction, allowing users to ignore the details of analog-to-digital conversion, network connection, radio modulation, etc., in order to “simply” place a call.

To show this abstraction to students, the instructor can offer to trade cell phones with a student, with one of the parties then placing a call to the other. Since each person is using an unfamiliar phone, it’s reasonable for each person to explain to the other how to place or answer a call with their phone. The explanation will almost certainly be in terms such as “push such and such a button,” “dial the number,” etc.

After successfully placing the call, the instructor can say a little bit about how cell phones work, and explain placing and answering a call in terms of what “really” happens — to place a call, you make the computer in the calling phone tell the radio transmitter to modulate its signal in a way that encodes a packet of data that initiates the call…. The point that this process was previously described in very different, much simpler, terms, and that no-one who really wanted to use a cell phone would use the “real” description, can be made very quickly, without requiring the instructor to know much about cellular technology. Indeed, just reciting the above sentence “you make the computer in the calling phone tell the radio transmitter to modulate its signal in a way that encodes a packet of data that initiates the call…” can be enough to establish the basic point. For instructors who want to know more about cellular technology, textbooks on wireless networking provide an ample introduction. Once students have seen the difference between how they think of cell phones and what happens internally, the instructor can say a few words about the difference as an example of abstraction: the way people usually think of their phones hides details that ordinary users don’t need to know (i.e., it’s abstraction), and indeed hides details that would make cell phones unusable if users did have to know them (i.e., abstraction is essential to working with technological systems).

Copyright © 2005 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index