part two

Part 2: Searching, solving, inferring

In this part we’ll look at algorithms I learned during my career in building compilers, code analyzers and other developer tools.

We typically think of “searching” as an algorithm that traverses an existing tree, list, table or other similar data structure looking for data that matches some criterion. But we can also characterize creating a whole 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: coloring a map, solving a sudoku puzzle and choosing how to enregister variables in a compiler are all the same problem.
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 Chapters 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, where we’ll explore the “monad” pattern that underlies sequences, nullables and other common generic types.