Our project this quarter involves implementing and evaluating a prototype Perfectly Accurate Calculator (PAC) to perform exact calculations on real numbers. It's widely known in CS that this is impossible, which is why we live with the roundoff errors in floating point calculations. Like so many widely known facts, that one is false. A real number can be represented with perfect accuracy by a function that produces rational numbers approaching that value in the limit. Of course, there's no completely general way of printing out those values in a nice readable finite form. But, once you have such an exact real number cum function, you can decide how much accuracy to print out, change your mind as many times as you like, and view the approximate results with confidence that you know exactly how far off they might be.
The PAC will have a Graphical User Interface (GUI) that allows you to enter numbers, describe calculations on them, and view the results. The TAs and I will write most or all of the GUI code (often an annoyingly gooey task), which will provide a structure in which you may fiddle with the interesting calculations inside.
We will approach the PAC by a process I call "sideways programming." When I was a boy, the great pooh-bahs of CS debated violently whether one should program
In retrospect, it seems pretty obvious that one should do both of these: building libraries (bottom-up) with the right tools to solve a particular problem (as well as a number of other problems that might come up next week), and using the tools in those libraries to craft a solution (top-down) to a particular problem.
But even bottom-up and top-down programming together are not enough. The product of programming is not just a program, it's a program in relationship to a specification of the function of that program. There are two reasons why it doesn't really work to start with the specification and just cook up the program, whether bottom-up or top-down:
I'm rather proud of coining the "sideways programming" label, although nobody else seems to use it. There is a fair amount of literature on "rapid prototyping", a method for producing software by sideways programming. The phrase "rapid programming" denotes a particular application of sideways programming when reason #1 above dominates the structure of the work. There are some spectacular failures in the history of software, such as the software to control the Hubble space telescope, that arose from a misguided attempt to freeze a specification before working on the program.
The history of software is also littered with very bad analogies to other branches of engineering. Perhaps the worst offender is the analogy to building bridges, accompanied by the complaint that software doesn't seem to be as reliable as bridges, and therefore we need to write software more like we build bridges. Well, the reliability of software is not determined in any way vaguely like the reliability of bridges, so this idea only produces wistful articles in journals.
On the other hand, now that most software designers and programmers do a certain amount of sideways programming, whether consciously or un, some analogies to other aspects of material construction pop out. In the bad old days (which aren't really over), programmers (and their bosses, which is a bigger problem) tended to think of programming as an accumulation of lines of program code, with productivity measured in lines of (debugged, if we're being smarter) code per unit time. Code written and thrown away seemed to be wasted. But almost no material structure is built without some sort of scaffolding---another structure that's built to help with the primary one, and then dismantled. Perhaps we should be even more willing to throw away immaterial lines of program code than material scaffolding.
The real progress in programming is not the accumulation of lines of program code, but the accumulation of detailed understanding of the relationship between the program and its specification. In order to understand one part of a program, we often write additional program code that is not part of a final product. My second futile grab for fame in the theory of software engineering is to coin the phrase "scaffolding code" for stuff you write that serves a useful transitional purpose, but is deliberately thrown away.
Actually, programming goes way beyond most forms of material engineering in the use of valuable stuff that gets thrown away. Many good software designers and programmers make a point of throwing away one whole prototype before writing anything deliverable. (I'm pretty confident that people make a point of doing this. I'm not so confident that they actually do it very often. But it's a good idea.)
Working back to our particular project: I have already implemented a crappy calculator, that only does addition, with a lame GUI. For the project, we will gradually replace pieces of this crappy calculator with more interesting pieces. Eventually, we will have a prototype Perfectly Accurate Calculator. We'll probably compare several versions of exact real computing, and see which one seems to run fastest.