In the June CACM, Micah Beck writes an opinion piece Accept the Consequences where he is quite skeptical of the role of theory in real-world software development, concluding
It is important that we teach practical computer engineering as a field separate from formal computer science. The latter can help in the understanding and analysis of the former, but may never model it well enough to be predictive in the way the physical sciences are.
I certainly agree that theoretical results can't perfectly predict how algorithms work in practice, but neither does physics. The world is much more complex, both computationally and physically, to perfectly model. Physics gives us an approximation to reality that can help guide engineering decisions and theory can do the same for computation.
You need a basis to reason about computation, lest you are just flying blind. Theory gives you that basis.
Let's consider sorting. Beck complains that Quicksort runs in \(O(n^2)\) time in the worst case even though it is used commonly in practice, while the little-used Insertion sort runs in worst-case \(O(n\log n)\). Let's assume Beck meant an algorithm like heapsort that actually has \(O(n\log n)\) worst-case performance. But theorists do more than fixate on worst-case performance, Quicksort runs in \(O(n\log n)\) on average, and on worst-case if you use a random pivot, or a more complex deterministic pivoting algorithm. Introsort combines Quicksort efficiency and worst-case guarantees and is used in some standard libraries.
Beck worries about secondary storage and communication limitations but theorists have studied sorting in those regimes as well.
The other example he talks about is about a theoretical result that one cannot use an unreliable network to implement one that is completely reliable while textbooks consider TCP to be reliable. But in fact TCP was designed to allow failure because it took account of the theoretical result, not in spite of it.
Beck ends the article talking about Generative AI where theory hasn't kept up with practice at all. Beck calls for using classical AI tools based on formal logic as guardrails for generative AI. However, the lack of theoretical understanding suggests that such guardrails may significantly weaken generative AI's expressive power. Without adequate theory, we must instead rely more heavily on extensive testing, particularly for critical systems.
There are stronger examples Beck could have used, such as algorithms that solve many NP-complete problems efficiently in practice despite their theoretical intractability. Even here, understanding the theoretical limitations helps us focus on developing better heuristics and recognizing when problems might be computationally difficult.
I agree with Beck that relying solely on the theoretical models can cause some challenges but rather than have the students "unlearn" the theory, encourage them to use the theory appropriately to help guide the design of new systems.
Beck's call to separate software development from theory only underscores how important we need to keep them intertwined. Students should know the theoretical foundations, for they shape problem solving, but they should also understand the limitations of these models.
Wow, what an embarrassing and poorly researched / fact-checked article. Mis-stating basic facts (e.g., running time of insertion sort and the sorting lower bound). Citations to geeksforgeeks.org. And, sorting is a problem where the theory does an amazing job explaining the practice, even to the level of why dual-pivot quicksort implementations are faster than classic quicksort implementations (despite performing more compares and exchanges). If the author had "learned" the theory, he might be a bit less quick to tell students to "unlearn" it.
ReplyDeleteHe who loves practice without theory is like the sailor who boards a ship without a rudder and compass and never knows where he may cast.
ReplyDeleteNot my opinion only, Leonardo da Vinci wrote it.
While at it, let's also get rid of Math. It has no relation to real world after all.
ReplyDeleteThe real problem here is that many more applied computer scientists are closer to experimental physics, but the system they deal with are often much simpler than experimental physics. Experimental physics values theoretical physics, cause without it you cannot really do modern physics.
One other aspect is that a lot of computer science is human constructs, so it is more engineering than science what Beck does. E.g. a civil engineer who is designing a simple building doesn't need to know cutting edge theoretical physics. Once we get to civil engineer and theoretical physics, you might hear the civil engineer not being able to see the value of theoretical physics for his own work.
On the other hand, I think we can point to a lot of practical things that came out of theory. E.g. a lot of cryptography especially rely on theoretical computer science.
On the other side, we need to accept that a lot of people we train don't end up as scientists but as engineers, and maybe the weight that more practical topics a student should learn is lower than it should be while the amount of theory they should learn is more than it should be.