Student Originated Software, my yearlong software development program at Evergreen, requires us to write a weekly summary of the reading assignment for that week. I thought I might share some of these summaries, as well as links to the papers themselves.

I shouldn’t have to say this, but in this day and age, better safe than sorry – plagarism is a very bad thing. As a writing tutor, I condemn it, and if you steal my summary and pass it off as your own, then you are likely in violation of some sort of ethics code (more than likely academic, but possibly professional). Save yourself the trouble – don’t do it. If you need to steal a summary instead of reading the paper, perhaps you’re in the wrong place in life.

WIRTH, PROGRAM DEVELOPMENT BY STEPWISE REFINEMENT

Programming, according to Wirth, is too often taught in the abstract; rather than providing specific, concrete examples for students to follow and build on, students are crammed with abstract facts and information about a language, rather than focusing exclusively on methods of design and construction in the context of those languages. Thus, Wirth puts forth a problem by which to construct an ongoing example of how to design a program. The Eight Queens problem states that eight queens must be placed on an 8×8 chessboard in such a way that no one queen endangers the others. Wirth puts forth that the best way to develop a solution to this problem is, first, to develop an appropriately abstract notation in which to discuss the program’s development and evolution. He first posits an approach that is essentially “brute force”; try every possible combination until generating an acceptable result by examining every possibility in the problem domain. The issue with this solution is that it takes seven hours to come up with a single solution, much less multiple possible board layouts!

Wirth’s second solution is to generate two subset predicates from the overall result. Thus, the join of those two subsets yields the full domain of problem results. Through preselection, he reduces the problem to only a 100-second execution time. However, this second result isn’t beneficial either; rather than taking 2^32 tries to find solutions, this algorithm takes 2^24, an improvement of 0.003% – negligible! Wirth then proceeds with a third, far more elegant solution: treat each column on the board individually. As a queen is placed, she invalidates certain positions on the board: no queen may be placed on the same column, the same /-diagonal, or the same -diagonal. Since queens are being placed sequentially left to right on the board, you are only ever dealing with N queens in the Nth step. Therefore, place a single queen on the board; as that queen is placed, track in three arrays the diagonals and columns where other queens may no longer be placed according to a set of coordinates. If necessary, be able to backtrack from a particular solution so that all possible solutions within the problem domain are tested. Under this algorithm, the full solution set is found within 15 minutes.

Wirth then steps through the development of the code behind each of the possible solutions, showing how each step in generating the code is merely a refinement of the previous possible solution; he does so by developing a series of primitive operations and refining their definition step-by-step. By defining these instructions in the abstract and waiting until the last possible second to assert data representation, Wirth is able to create a solution that utilizes the same functionality in slightly different ways.

Wirth concludes that the best way for programs to be designed is through stepwise refinement which waits until the last possible step to determine data representation and to commit to a particular structure. This is the only way to do careful programming that yields a clean and efficient result.