Building abstractions and recognizing common patterns

Concrete problems are often messy. They have many components and are generally provided with more information than one needs to actually solve the problem. This extraneous data is often distracting and gets in the way of solving the problem. To get around this, one needs to extract only the essential information, discarding the irrelevant excess, and identify only the general concepts of data and processes. This process is called abstraction.

An abstraction is a generalized view of a concept or data that keeps only the essential information and properties of the concept. A well-designed abstraction allows one to devise simple and elegant solutions to problems that are otherwise complex and opaque. They take time to build, but the payoff can be dramatic. A good abstraction will apply to a large class of problems and will become a useful tool for the future. They can help you realize your problem as a more general class of problem, or invent a new general class of solution that can be used elsewhere.

Aside

The author is a mathematician by training. The process there is exactly the same, although they are known for taking the abstraction step a little further than is perhaps warranted.

Abstraction is not just a tool for reducing problems to something simpler but more general. As a programmer, you use abstractions all the time, such as functions, classes, system memory, and file systems. Abstractions are very important in programming because they allow you to build reusable code that functions in many scenarios, rather than being specific to each problem. The C/C++ runtime libraries provide functions for allocating and freeing memory that can be used for many different things in many different circumstances.

There are several places where abstraction really matters. The first, and probably most immediately useful, is for the initial ingestion and preprocessing of data. When writing software, you will need to decide how your program will obtain the data it needs to solve a problem. Will it be a Unix command-line tool that reads directly from the terminal (stdin) or a file on the disk? Will it be a GUI application where the user types the data in directly? Will it be part of a library that exposes an interface that other developers can use? Each of these appears different, but with a well-designed abstraction, you could be flexible enough to answer any of these design objectives.

Another reason to abstract your input data is to make sure it conforms to your requirements. As described above, units of measurement are not standardized around the world, and assuming that all measurements use the same units is dangerous. Using an abstraction on the interface of your application would allow you to work with the data, placed in the correct units, regardless of the input type (assuming that the unit information was provided). We will come back to this idea later too.

Abstractions are also useful when designing algorithms, as we shall see later. For instance, if your data belongs to, or can be easily embedded in, a mathematical structure such as a vector space, then the operations and methodology of that structure can be used to devise an algorithm. This is advantageous for several reasons. Mathematical structures are well studied – perhaps too much so – so these can be used to make strong guarantees about the algorithm. Second, mathematical operations, particularly those concerning vector spaces, are well studied, and there are many optimized implementations of them.

Identifying commonalities in data

Data is an obvious place to look to build abstractions. As described previously, forming abstractions around the source and nature of the data provided can ease the acquisition, validation, and processing of data. However, before we can do this, we need to filter out the information that is not relevant to the problem. Of course, this is a classic “chicken and egg” problem since one sometimes cannot tell what information is relevant before actually solving the problem.

Finding these generalizations starts with asking some basic questions about your data. Is the data numerical in nature? If so, what kind of numbers? Numerical data is likely to fit into some kind of mathematical structure. It has natural orderings, which may or may not be relevant to your problem, and more specifically, there will be “equals comparable” to one another (the operation == is defined for numerical values). It also has arithmetic (+, -, *, /), which has well-defined interactions with the ordering and equality comparisons. Each of these is an abstract property that numbers happen to possess. Any given problem might require that your data be ordered and comparable (such as searching and sorting), or that it has some or all arithmetic operations, but not actually rely on the actual form of the underlying data.

Text data is a great example of an abstract class of data. Text is a sequence of characters taken from a particular “alphabet,” such as the ASCII code table or the UTF-8 code table. The actual nature of these characters might well be important. For instance, ASCII characters are represented by a single byte, whereas UTF-8 has multi-byte characters as well as single-byte characters. It is not necessarily important to know what alphabet is used for a particular set of text data, but it is important that you know how to identify individual characters, compare them, or otherwise operate upon them.

Broadly speaking, many problems can be generalized by considering what traits parts of the data must satisfy (having ordered, equality comparable, iterable, etc.). Sometimes it is easy to identify which traits are required up front (searching generally requires iterable and comparable), but other times this isn’t possible. Sometimes you need to solve the problem with concrete data to realize that it can be generalized. Sometimes it cannot be generalized at all.

Identifying structure in the problem

Sometimes it’s not just the data that can be abstracted. Sometimes the problem itself has a general structure that can be identified and exploited. A typical example of this might be to identify one part of a problem as an instance of a theoretical framework. For instance, if one step of a problem is to find particular patterns within data, which for text is usually accomplished with regular expressions (this is pattern recognition). The abstraction comes by understanding that the computational theory of regular expressions is deterministic finite automata (DFA), which are the abstraction that we seek. These kinds of abstractions can be difficult to spot but generally lead to high-quality results.

Finding abstractions such as this can give you a theoretical framework in which the solution to the main problem can be found. Finite automata (and finite state machines) are a very powerful pattern that can be used in a great many situations. Once you know that part of the problem involves such a construction, you can start to look for other parts of the problem that also fit this model. This might not be successful, but it does at least give options for where to look and how to proceed.

Having a good understanding of some of these fundamental theories obviously makes identifying these kinds of abstractions and understanding what capabilities they have easier. Topics such as regular expressions are very well understood, even if they are sometimes difficult to use in practice. There are several other similar patterns that you should endeavor to understand; sorting and searching algorithms are another great example. Numerical methods for solving linear systems, constrained optimization, and graph algorithms, such as shortest path, are great examples. Numerical algorithms have a habit of turning up in unexpected places.

A digression into Sudoku

Many common puzzles and games ultimately require the solver or player to recognize patterns within the context of the game. This is especially obvious in Sudoku puzzles. Here, the objective is to place the digits 1-9 in a 9-by-9 grid so that each digit appears once in each row, column, and 3-by-3 box. Simple Sudoku puzzles only require basic techniques such as identifying pairs of digits or other kinds of mutual exclusion within a given row or column. However, harder puzzles require the solver to identify more complex patterns within the grid.

For instance, more difficult Sudoku puzzles require the solver to identify intermediate patterns such as “X-wings.” Here, the solver identifies a pair of rows (or columns) and a digit where the only valid position for the digit in each of the rows appears in a pair of columns. Since both rows must contain the digit, and it cannot appear in the same column in both rows, we can deduce that the only valid position for the digit in the two identified columns is within the two given rows, allowing us to eliminate this digit from other positions within the columns. (The same logic applies symmetrically if one started with a pair of columns.) There are many patterns in Sudoku, and being a good solver requires one to be able to identify and exploit the deductions provided by these patterns.

Note

Chess is another example of a game where the ability to recognize patterns of play is crucial for being a good player. This allows the player to quickly identify paths to victory and counterstrategies that can be employed to win the game. Part of learning how to play these games is to learn some of the common patterns that appear and how to use or counter them. Solving problems is no different. Being an effective programmer requires you to learn some of the common patterns, their uses, and how to incorporate them into solutions to problems.

Common functional patterns

There are many functional patterns that you should be familiar with. We’ve already mentioned a few. Sorting patterns involve placing elements in order according to a sorting predicate. A search is a related problem that uses a condition or predicate to find a specific element or range within a set of data. Other patterns include filtering (and the related random sampling), shuffling, and permutations of a range of data. These are useful patterns that appear frequently in programming, sometimes in their standard form, but often in a less obvious form.

Many problems eventually reduce to solving a numerical problem, such as solving a system of equations, constrained optimizations, or graph algorithms. These tend to require some work to find the correct mathematical formulation of the problem. Again, this is obvious in some cases and not in others. More important patterns come from statistics and probability. Generating high-quality random numbers is a complicated topic. Problems that have a statistical component are usually obvious; any time there is uncertainty in measurements or methodology, statistics will probably be needed.

Combinatorics is the branch of mathematics that deals with the various ways that a (finite) set can be combined – how the elements can be permuted, or paired up, and so on. This branch includes graph theory, which appears frequently in programming problems. Problems that make explicit use of graph theory include dependency resolution (dependencies of a project are usually expressed as a directed graph), scheduling (turns out to be a graph coloring problem), and route planning is either a shortest path or traversal problem depending on the objectives.

Common structural patterns

Recognizing functional patterns is usually an early step in the problem-solving process. Structural patterns usually appear in the final stages, when designing algorithms or finally implementing your solution. Structural patterns include the design patterns and idioms for a particular language that allow you to design interfaces and make your code efficient. (The classic books on design patterns includes “structural patterns” as one of the topics; our usage of the term includes everything described in this book and not just what they describe as structural patterns.) We will use many structural patterns.

For example, the strategy (or policy) pattern is a means of encapsulating a family of different, but interchangeable, methodologies that can be used to obtain a result in different circumstances. For instance, one might define various algorithms for reading data from a file as strategies, and change the strategy based on the file type. We will make use of this pattern several times later in this book.

Other patterns worth mentioning are adapters, facades, flyweights, and proxies. These are all examples of patterns that adapt the interface of a given object or class to allow it to be used in some other context. Another useful pattern is a decorator, where the capabilities of an object are extended by means of a wrapping class.

Note

One pattern that is used heavily in C++ is the “template method” pattern, where the skeleton of an algorithm is described in terms of some generic (placeholder) operations that can be customized by the specific implementation. The C++ standard template library is full of examples of these kinds of patterns, especially in the algorithm header. This pattern excels when producing general-purpose and flexible implementations of algorithms that can appear in many different contexts.