Jeffrey Ullman, a famous computer science professor, published an essay pushing back about the need to run experiments in computer science. Apparently, some conference reviewers gave him a hard time regarding a paper he submitted because it did not include experiments.
I am in general agreement with him: not every research paper should include experiments. That is obviously an excessive requirement. I also think that building theoretical models is very important. Experiments alone are unsatisfying. Indeed, science is not merely about running experiments. Imagine if we did not have Newton’s laws? Would we need to run experiments on every new object to see how it behaves when we push it? Experiments are often badly designed and misleading. I don’t tend to trust a paper that includes experiments more than another paper. In fact, a paper with a useful theoretical results can be much more powerful than any large set of experiments… since it is often easier to check the mathematics than to be sure that the experiments were carried on fairly. There is also a sense in which experiments can be pointless. For example, I was once asked to show experimentally that an algorithm based on external-memory sorting could scale up.
But, at some point, Ullman linked to my blog post A criticism of computer science: models or modÃ¨les? This brought mixed feelings. I think he misrepresented my opinions:
In this article, the author argues that one should never use a model that is not real running time on a real computer. For example, this author would not accept the O(n log n) lower bound on sorting, because it is based on counting comparisons rather than machine instructions executed.
I don’t think that my blog post says anything of the sort. I disagree with this statement even though Ullman is under the impression that it is what I believe. I think that our knowledge that sorting (in general) requires at least n log n operations is critical and fundamental. If you were to learn one thing from computer science, it would probably not be a bad choice. Of course, you can use Pigeonhole sort or Timsort to achieve sorting in even fewer operations but that requires extra assumptions.
Models are always simplifications. However, if your model is right by definition… that is, if no comparison with real world could lead you to conclude that your model is wrong, then it is not a scientific model. It might be a tremendously useful mathematical construction… but it is not science.
The fact that sorting runs in n log n-time is a scientific fact. It could be false: someone could come up with a generic sorting program that scales up linearly. Heck! This could happen on some future exotic computer architecture. Once it does, we will need to revise our textbooks.
It is also a scientific fact that the sorting algorithm used in Java, Timsort, is often preferable to the classical algorithms like merge sort or quick sort. We can run extensive experiments to check that fact. There is also a theoretical analysis that explains why Timsort can often be better.
Not everything needs to be science. For example, Codd’s work on relational algebra (the foundation for SQL) is fantastic. I am really happy we have SQL and everything that was built on it. But notice that it was built by people who didn’t merely come up with models… they implemented their ideas and had them face the real world.
The problem is that if we don’t require people to test out their ideas in the real world, we are going to get thousands of rambling researchers for every Codd. Sometimes, that is the impression that academic research in computer science gives.
Some researchers will eagerly point out that pure theory often proves useful in unexpected ways. But that is also true of art and philosophy. What sets our current civilization apart from the preceding ones is that we are founded on the scientific paradigm. The industrial revolution was possible because hackers built machines that worked, and irrespective of what the great minds of the time thought, they were adopted. In effect, results are what matters, not how smart you are or how prestigious your position is.
I do not believe we should do away with mathematics, art and philosophy, but we need to be watchful. Do you use a model because influential people are supporting it or because it fits the facts?
Continue reading with my post on Big-O notation and real-world performance.