Part 2 Searching, solving, inferring
In this part, we’ll look at algorithms I learned during my career building compilers, code analyzers, and other developer tools.
We typically think of searching as an algorithm that traverses an existing tree, list, table, or similar data structure for data that matches some criterion. But we can also characterize creating a new data structure that meets some criterion as a search problem: we’re searching a space of possibilities for an acceptable solution. In chapter 8, we’ll implement a backtracking search algorithm to solve a variety of seemingly unrelated problems which are—actually—the same: coloring a map, solving a Sudoku puzzle, and choosing how to enregister variables in a compiler.
Have you ever wondered how your favorite editor formats your source code so nicely? In chapter 9, we’ll look at an elegant greedy pretty-printing algorithm.
In chapter 10, we’ll look at two algorithms that solve opposite problems. The unification algorithm solves equations in first-order logic and can be used to implement type inference in a compiler. The anti-unification algorithm analyzes two unequal terms and discovers what they have in common; it’s useful for clone detection and other program-analysis problems.
Chapter 11 is our second abstract nonsense interlude, in which we’ll explore the monad pattern that underlies sequences, nullables, and other common generic types.