4 ms·
Theory-curious but mostly workaday programmer here. Does this have any application to detecting spaghetti code in conventional codebases, or is it specific to t
by neilk 5y ago
Theory-curious but mostly workaday programmer here. Does this have any application to detecting spaghetti code in conventional codebases, or is it specific to the Busy Beaver problem?
“Cyclomatic complexity” is as old as the hills, but attempts to count the paths through the code from a begin state to and end state. According to Wikipedia it’s similar to “circuit rank” which is the minimum number of edges to remove in order to break cycles. That smells like it’s related to this graph reduction thing but I lack intuition into this problem.
- ravi-delia 5y agoI highly doubt it does, it's largely a fun puzzle with potential ramifications for limits of computability.
- hackerfromthefu 5y agoLow Cyclomatic Complexity is absolutely the result of careful management of interfaces in the system. The inverse is also true that high CC is a sign of poorly structure code, which tends towards spaghetti. Thus I agree it's related to the premise of detecting spaghetti code. There's nice CC visualizers that can show you at a glance areas that have higher complexity. Sometimes that complexity is related to the problem domain, but sometimes it comes from overhead of poor system architecture.
- atq2119 5y agoPeople are perfectly capable of writing spaghetti code in structured programming languages (without goto) and such programs are always reducible in the sense of this article. Actually, I have a hunch that every program that is reducible in the standard compiler sense is also reducible in the sense of the article, but the converse does not hold. 1 -> 2 -> 3 -> 4, 1 -> 3 -> 2 is irreducible in the compiler sense (there is a loop with two entries) but reducible in the sense of the article (first merge 2 and 3, then delete self loop, an acyclic graph remains which is trivially reducible).