What the Four Color Theorem Can Teach Us About Writing Software
alexkudlick.com
alexkudlick.com
I actually thought this was going to go in another direction. When the proof for the four color theorem was published there was a good deal of controversy about it. It had not been fully verified by a person, the bulk of it was generated by computers. The method of generating the elements of the proof was vetted, but not the final output. This has some relation to the issues we have now with machine learning and systems being built based on the generated models that we don't fully understand. It also relates to more complex chain of compilation systems we use these days where each layer of translation introduces the potential for subtle errors or malicious action.
But if the interface leaks: e.g. if it alters some state, if some edge cases aren't covered or some of its internal dependencies have to be visible on the outside then the mess ramifies through you whole system and is a burden on any code you write, change or read.
Mathematical code often fits this model well. Implementations are frequently very hairy because of the calculations involved plus mathematically inelegant bells and whistles required by the real world. But since these things tend to be calculations, their interfaces are often no more than "call this function, get or result or an error, with no side-effcts". Very clean.
But it's also unstable: a circle with an odd number of nodes (e.g. a triangle) requires three colours, while a circle with an even number of nodes needs only two, even though both models seem similarly complex.
Nonetheless, focusing on reducing complexity and simplifying dependency graphs is good, mmkay.
If the 'bus' is simple enough to need few colors, then great.
Same goes for the sibling comment regarding a ball of mud. It makes the analysis more complex but you should consider every global variable as connected to every other global in constructing the graph. Balls of mud, in my thinking, then need nearly as many colors as they have globals since every component theoretically interacts with every other. And when I mixed all the water colors as a kid, I was always disappointed to get a muddy color.
Simplifying your depgraph by writing on big ball of mud means pushing the complexity down. Instead of a complex module graph, you have a complex dependency graph between variables/functions/whatever in your mudball. Oversimplify your individual modules and you complexify your module graph, or even your production infrastructure (one-line microservices anyone?).
Forced to choose, I would prefer a mudball to dependency hell. But really I would like the complexity to be intelligently and somewhat evenly distributed to each level.
But can we even reason beyond 4 levels? This point made a lot of sense to me. My intuition is that this comes down to our fundamental inability to generally solve quintics. There are also topological proofs to this which fit the author's point perfectly [0]. 4th degree is the limit of formal proof.
That's only true if your dependency graph is planar. That said, the sentiment is spot on: you can get away with arbitrarily complicated code as long as you avoid embedding K_3,3 and K_5 in your dependency graph.
This is touched on in the article. The triangle is a complete graph, each vertice is connected to each other. A 2 colored circular graph would not be a complete graph. It would have a ring or fan-out shape.
You could have graph with 3 vertices that is 2 colored, you just can't have each vertice be connected to each other one.
I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar.
Or to bring it back to software, I think it's true that a small system where each piece can directly talk to each other piece is more complex than a large system where pieces only communicate with their neighbors.
A square can, (you put one node in the middle), but 5 and up can't be both complete and planar.
Clever!
+---+
/ \
+ +
\ /
+---+
The four colour limit is only for planar graphs. Dependency graphs need not be planar.
Also there is a very well understood connection between software complexity and graph colourings: register allocation. If you model variables as vertices, and place edges between variables that are required at the same time, then assigning locations to variables is a graph colouring.
I think this might generalise: the number of graph colours tells you something about the maximum number of things you need to keep track of simultaneously in order to deal with one locality in the graph.
That being said, I doubt chromatic number is the right measure for software dependency graphs. Especially when there are hundreds of graph complexity metrics (tree-width, centrality measures, measures based on cuts and flows, etc.). Even just now for the first time I saw this thing called cyclomatic complexity: https://en.wikipedia.org/wiki/Cyclomatic_complexity
I'd be interested to hear from someone who has experience applying graph metrics to static code analysis in practice. What's useful and informative?
This reminds me a bit of domain driven contexts (something just added to Elixir/Phoenix 1.3) - reducing the surface area of sub nodes from each other by exposing that single point interface.
The Kempe-chain proof of the 5-colouring of any planar graph is easy and beautiful.
https://math.stackexchange.com/questions/23409/did-the-appel...
"Four Colors Suffice: How the Map Problem Was Solved" by Robin Wilson.
https://www.goodreads.com/book/show/450635.Four_Colors_Suffi...
https://www.selenic.com/blog/?p=626
In rust, there's cargo-graph to do this for your packages:
https://github.com/kbknapp/cargo-graph
I used that on Servo once see PNG at https://dirkjan.ochtman.nl/files/servo-graph.png or SVG at https://dirkjan.ochtman.nl/files/servo-graph.svg.
From these explorations, I think the four color theorem-type planarity or connectedness is actually less important than a lack of cycles for the perceived complexity, or the difficulty encountered due to that complexity.
http://pycallgraph.slowchop.com/en/master/
But like I said, it was ages ago, so I don't know how good/bad it is now.
I think once you put in direction, you will see that cycles are much more important than overlaps in edges in determining complexity. If you can keep the graph acyclic, life is pretty easy. I think big cycles are worse than small cycles, cycles that opverlap each other make things much more complex.
http://www.literateprogramming.com/mccabe.pdf
That is, we use a strategy for substituting away subgraphs; we can classify programs by what results from that process. It may turn out that there are particular problematic subgraphs to avoid.
Also, that you can use the finite set of minimal graph minors for a surface of genus X to do case analysis instead of having an infinite amount of cases to test with.
When I was told about this many years ago, it was described as the 'n factorial problem'. This problem assumes that directionality of the communication is important. If you have two nodes, they are 2! ways to communicate. If you have three things, there are 3! or 6 ways to communicate between the nodes. The suggested solution was similar, group components together behind a black box facade so that 30 components can be reduced to 3! main communication paths or less.
I really like the visualization. It's a happy medium between something like UML and something that's actually useful, and creates useful constraints around communication channels between classes.
I'm sure there's some design pattern that breaks the rule, but overall trying to force a "4 color" programming pattern seems like it can't do anything but help.
"If any part of a system depends on the internals of another part, then complexity increases as the square of the size of the system."
A link to a slide from him showing n2 dependencies - http://bit.ly/2t0xukK
If you really want your interviewees to hate you, ask them to solve it using D colours!
Also, K3, K2 and K1 are planar with maximum degree 2, 1, respectively 0, but require 3, 2, 1 colors.
So, in general, D colors isn’t sufficient.
Also, what's the name for the process for transforming a "map" into a connected network, just like he did at the beginning?
To use the same node graph analogy, when you focus too much on reducing the number of colors, you end up needing to create tons of nodes between the nodes that actually DO SOMETHING. Your software ends up more complex and difficult to manage.
If the problem you're trying to solve focuses on the fundamentals of the abstraction, you're most certainly gaining clarity (possibly at the expense of performance).
If you find the abstraction's making you lose clarity, it might very well be that you're really working on incidental complexity, but there's also a distinct chance you just chose the wrong abstraction.