Part II: Data Abstraction

In the previous part, we looked at how procedures describe computational processes. In this part, we will turn our attention to the data that is manipulated by those processes and how it can be structured. There are many qualitatively dissimilar ways of structuring data. For example, the list of stops for a bus route bears little resemblance to someone's family tree. In this part, we'll focus on a few representative data structures and the collection of operations that is appropriate to each one.

In Chapter 6, we'll work through the fundamentals of using and representing compound data in the relatively simple context of data types with a fixed number of components. Our focus is on the collection of operations that forms the interface between the uses of the data type and its representation. In Chapter 7, we'll show how two-component data structures can actually be used to represent lists of any length, by treating each nonempty list as having a first element and a list of the remaining elements. We'll extend this recursive approach to structuring data to hierarchical, tree-like structures in Chapter 8. Next we'll examine how a diverse collection of different data representations can present a single, uniform collection of interface operations. Finally, we'll look at programs as themselves being hierarchically composed data (expressions made of subexpressions) and see how to provide a uniform ``evaluate'' operation across the diversity of different expression types. By doing so, we'll show that implementing a programming language is really a specific application of the techniques introduced in this part of the book.

Chapter 6: Compound Data and Data Abstraction

We use the game of Nim to introduce data abstraction as a method for dealing with compound data. We specify abstract data type operators for ``game states'' in Nim by imagining what commands would need to be issued to a ``gamekeeper,'' and write a working version of Nim using these as-yet-unimplemented operators. Next, we give four different implementations of these operators, including versions based on procedural representations and cons-pairs. The application section incorporates an additional level of abstraction by using higher-order programming to add strategies to Nim, with the moves selected by the strategies encoded in another data type. An additional topic in this chapter is the use of basic input/output procedures in Scheme to write interactive programs.

Chapter 7: Lists

We explain Scheme lists through the two-part list viewpoint, and illustrate them using box-and-pointer diagrams. We construct simple lists, both explicitly and procedurally, and explain and reinforce basic list processing idioms (cdring down a list, consing up a list, map, filter, iteration, and tree recursion) through numerous examples and exercises. The long application section guides the students through the development of a movie database query system, using a table of query patterns with corresponding action procedures to implement a natural language interface.

Chapter 8: Trees

We introduce binary search trees as a data structure enabling efficient binary search (which we motivate through the movie query system of chapter 7), and illustrate these trees using two diagramming schemes. By analyzing the efficiency issues that arise with binary search trees, we naturally draw in such concepts as depth, height, and balance. We study expression trees in the third section, writing a procedure that evaluates infix expressions. (This topic is revisited and greatly expanded in chapter 10.) The application section develops an automated phone book using the data retrieval radix trees know as tries.

Chapter 9: Generic Operations

We motivate generic operations two ways: first, by integrating various list representations (which is done through message-passing); and second, using the problem of integrating diverse databases (movies, books, and compact disks), which we do two ways, using type tags and operation tables. The application section illustrates generic operations by having the reader implement a computer graphics system.

Chapter 10: Implementing Programming Languages

We complete a full circle by writing two different Scheme evaluators (Micro-Scheme and Mini-Scheme) in Scheme using the pattern/action system from chapter 7, trees from chapter 8, and generic operators from chapter 9. This also provides an opportunity to introduce the use of EBNF grammars for syntax specification, and to preview some basic results from the theory of formal languages and automata. The application section adds explanatory output to Mini-Scheme, paralleling the substitution model given in the first chapters.
This is a portion of the annotated table of contents for the textbook Concrete Abstractions: An Introduction to Computer Science Using Scheme, by Max Hailperin, Barbara Kaiser, and Karl Knight. Free access to the full text in PDF form and supporting materials are also available.