Coupled Code is Cool

Happy new year, nothing too deep this week because I am traveling. If you read NULL BITMAP this year you have my gratitude. Peace and love.

One of the transformational moments for me in "coding" specifically was when reviewing the code of one of the more effective programmers I know. We had a DAG, or something. Quick background, a DAG, or Directed Acyclic Graph, is a directed graph that contains no cycles. A graph is a DAG if and only if it has a topological sort: a total ordering of the vertices such that none of the edges "go backwards." You might think of it as extending the partial order that the DAG gives you to a total order that never contradicts the partial order.

// generate a DAG
vertices := 10
graph := make(map[int][]int)
for i := 0; i < vertices; i++ {
  for j := i + 1; j < vertices; j++ {
    if rand.Intn(2) == 0 {
      graph[i] = append(graph[i], j)
    }
  }
}

And we had some cause to topological sort this thing. At the time, I might have either found some library, or wrote a little package with which to do a topological sort. A common algorithm for doing a topological sort is to do a depth-first search outwards from each root,

What this person did was something much better:

... some other code ...

seen := make(map[int]struct{})
var visit func(int)
visit = func(x int) {
  if _, ok := seen[x]; ok {
    return
  }
  seen[x] = struct{}{}
  for _, v := range graph[x] {
    visit(v)
  }
  fmt.Println(x)
}

for i := 0; i < vertices; i++ {
  visit(i)
}

... some other code ...

The remarkable thing to me here was that they just inlined the implementation. There was no effort at all to encapsulate the algorithm, to hide the implementation, to decouple the approach from the intent. Not to mention, no way to test the code in isolation! It goes against a lot of traditional practices for non-trivial algorithms.

Maybe the key insight here is that topological sort is a trivial algorithm, that isn't worthy of a library, a package, or even a separate function. Can you, via practice, elevate the level of what you deem as trivial to the point where it can actually be effective to inline things like this, and trust that readers of the code will recognize a topological sort when they see it?

It's a fairly standard teaching strategy for newer programmers, who tend to couple programs too much, to tell them to just extract and decouple things until they are physically unable to do it any more. I think this is a good thing to tell people because doing it to the extreme is a good way to build intuition for when it gets to be too much, and can help you develop a sense of taste for when to ease off the gas pedal.

Seeing this hunk of code go past showed me that there are places to ease off even more. I kind of hate LeetCode culture, where people talk about "grinding" algorithms and stuff. But I think it's true that there are some algorithms, like topological sort, that are simple enough, short enough, and ubiquitous enough that you should just memorize how to implement them.

Sometimes I think about how the rise of LLM-assisted coding will impact this sort of thing. On one hand it would certainly make it easier to inline this kind of implementation, but on the other hand, it makes it harder to assess and use good taste when it comes to whether it's a good idea to do so or not (since you didn't have to fit the whole algorithm in your brain to write it out).