Problem/Solution Space
Posted by Daniel Lyons Sat, 15 Dec 2007 11:09:00 GMT
Programming is different because you give people a problem and a solution at the same time.
Somehow, when someone comes to you with a programming task, you distill from that what exactly their problem is. Then you decide what the solution to the problem will be. Finally, you deliver to the customer two things: your conception of the problem they brought you and your concrete solution to that problem. (There’s usually a third product of this, which is either money or laughter depending on how badly you screw it up.)
There’s really two problems here. The customer is actually bringing you a universe with some flaws. They want a universe without these flaws. There are actually many universes without these flaws, so your first job as a programmer is to understand the customer’s reality.
Because programming begins and ends in concrete terms it’s easy to fall under the impression that it is concrete the whole time. Nothing could be further from the truth.
The set of perfect universes for this customer is quite large. Each one consists of a problem definition and a solution implementation. For example, someone may come to you with the problem that they have no money. They want to live in a universe in which they have money. One perfect universe is the one in which they panhandle for an hour and earn $3. Presto, they are no longer broke.
This definition of problem considers being broke to be a one-time state of being. There are other solutions to this problem with different attributes. For example, you could also go pick up aluminum cans for two weeks and take them to the recycling center to earn $50. $50 is more than $3, but two weeks is a lot longer than 1 hour. On the other hand, panhandling is degrading and picking up cans is just boring.
The solution isn’t the only thing that can vary. There are other ways of defining the problem. With a little common sense it’s easy to see that being broke is probably not a one-time event. Better solutions are probably found by designing the problem to account for this insight, but coming up with this insight isn’t something anyone has an algorithm for. The result of this insight, however, is a formal problem and a formal solution.
Additionally, the solution you hand over to the customer comes with another problem built-in. The customer imagines a world in which they have money, not a world in which they pick up aluminum cans or panhandle. However, the customer can’t come to you and just have wealth appear. They have to do some work to create new wealth.
As we imagine perfected universes, we are in the act of formalizing a problem and conceiving of a formal solution to that problem. This means dividing the problem into a metaphor, a formalized problem and selecting and then implementing a formalized solution.
The Incompleteness Theorem comes into it at the stage where you divide the solution into the part you solve for the user and the part the user solves for themselves. Another way of looking at this is, the amount of work the user has to do to utilize the perfection. You can balance this equation such that the user has to do no work; this is the complete solution with no expressiveness. I think this balance is probably a continuum on the incomplete side and a point on the complete side.
Elegance is that the problem and the solution are both as small as possible without becoming complete in the incompleteness theorem sense. Only the minimum of what is needed to define the problem and solve it to perfect this universe are included. Nothing extraneous.
The uncharted territory is problem definition itself. This is what computing science has taken for granted, because sorting and searching are intrinsic and easily defined problems that require interesting solutions that vary only by how. This is also why “real world” programming is such a hassle—most of your time is spent defining the problem/solution space rather than working on the solution.
Let’s work an example. The customer wants data management, so this is the problem/solution space. They bring you disks as the imperfect world. You define two concepts, “files” and “directories” and conceive of how they will work and build FAT. The two concepts consist of the problem you formalize and FAT is the formal solution. You’ve also given the customer the work of using files and directories in an appropriate fashion. That’s their problem; you’re done.
Same example again. The customer wants data management. I look to set theory, and then to relational theory. I conceive of “relations,” “tuples,” “tables,” “columns,” and “queries” from relational theory. I define a formal language, SQL. I implement a database, PostgreSQL. I’ve now increased the complexity on virtually every front, but I’ve also increased the expressiveness on the client’s side. He also has to do more up-front work, in that he must learn how to interact with the system via SQL. If we were being fair, he would weigh the time to learn SQL against the time to learn filesystems and the time he would spend implementing against a filesystem that he wouldn’t spend by having access to SQL and understanding it, but this seldom is the case.
Inappropriate abstractions are simply problem conceptions which increase the amount of work the customer has to do in the supposedly perfected universe with the formally defined problem and selected solution. It is more effort to deploy a program using CORBA in the backend than to deploy a program using a custom-written protocol, so the abstraction isn’t really an abstraction, it buys you nothing.
Powerful abstractions reduce the expressiveness by some factor but make the system more coherent. Drupal may consider arbitrary chunks of content uniquely addressable from anywhere, but this makes the management problem so bad the front-end doesn’t even bother. Voltaire is a better abstraction because removing sibling-to-sibling transclusions aren’t common enough to warrant a design that accommodates them. Voltaire simplifies the problem and the solution, and both are elegant and quite powerful.
Carter’s juxtapositional thinking/focussed attention dichotomy is just pointing out that programming begins with the act of creating a good problem formalism and that is an artistic act. It’s process to him. Fred Brooks is describing the design itself when he talks about conceptual coherence. If you have islands of meaningful features that don’t have a common substrate, you’re just pushing complexity from the flawed universe into the formal problem rather than the formal solution.
Dijkstra is arguing that both the problem and the solution need to be simple and elegant or neither will be comprehensible. And I tend to agree.
I need new nouns for these things.
