Seminar Summary of Classic ACM Papers: Part II

Here is another of my seminar summaries from Student Originated Software on one of the classic ACM papers we have been reading.

As with my last summary post, please don’t bother stealing this.  It’s immoral, unethical, and usually just plain rotten.  If you don’t understand the paper but you are required to turn a summary in, you need to read the paper carefully – this summary comes straight from the paper text, as with the summary posted in Part I.

PARNAS, ON THE CRITERIA TO BE USED IN DECOMPOSING SYSTEMS INTO MODULES

Parnas utilizes the example of a KWIC system to demonstrate how programs can be constructed by utilizing a series of different modules. By way of this example, he demonstrates how different modularizations yield different results in the level of information hiding available. He suggests criteria that might be used to properly construct these modules in order to ensure that modules may be developed independently of one another. He claims that the managerial and development time should be drastically reduced and that it should drastically increase the comprehensibility of the program for coders.

Parnas explicitly defines a module as a “responsibility assignment” rather than a subprogram, which may actually limit his argument. In larger programs, subprograms could in fact be fully modularized via responsibility assignments controlled by a master module called by the remainder of the program – the level of decomposition he discusses here can be more widely applied than is implied by the remainder of the paper. He creates two different modularizations for a KWIC index system: the first is based upon the stages the program steps through, the second is based upon discrete units of functionality. The first modularization utilizes five modules: input (reading in data), circular shift (finding the location of each circular shift), alphabetizing (alphabetizes the shifts), output (prints the shifts), and the master control module, which controls the operation of the program. This first module, Parnas argues, is the approach that would be used by most coders in creating a modularized system.

The second modularization utilizes six modules: line storage (responsible for the management of information regarding circular shifts), input (reads in from the input media), circular shifter (manages anything to do with shifts), alphabetizer (manages the alphabetical ordering of shifts), output (prints circular shifts), and master control (same function as the previous modularization). Parnas then begins to compare the benefits and drawbacks of each modularization. Both modularizations ease the ability to program each section individually, but only the second appropriately hides information so that the other modules do not need to rely on or replicate knowledge provided by other modules. After assembly, each module could be analytically identical, but the second module has more potential to be developed in an inefficient manner due to the information hiding available in this approach. Parnas also extensively discusses the changeability of each module and areas that could be modified and the impact that such changes may have on the programming of each module. Parnas is also concerned about the comprehensibility of code.

He proceeds to give an analysis of the impact of changing a particular portion of the design on both modules, isolating the circular shift algorithms. He gives examples of advisable decompositions for the system: creating data structures as a single module, pairing routines with their calling instructions is a single module, control structures are a single module, and information about the inputs are a single module.He also discusses the difference between hierarchical structures and modularization. He states that having a partial ordering of modules that allows different modules to use lower-level functionality and stand alone is beneficial; higher levels can be pruned to create a new program with the same base functionality.Thus, he concludes, a combination of modularization and hierarchical ordering can be greatly beneficial to a program.

In his conclusion, Parnas disdains directly correlating program modules with steps in a flowchart, instead urging the usage of a list of design decisions that could change and to press for information hiding whenever possible.

Agh, Technical Support!

I hate dealing with tech support people, over the phone or otherwise (though I have problems with the phone in general). At least part of this is because I am tech support, to a certain extent – my client work requires me to play that role (and, sort of offhand, so does my job in Evergreen’s Writing Center). So any example I can find that aptly illustrates just how stupid tech support people can be is just further proof to the whole situation.

Case in point. I’ve heard dumb stories from both the customer and the support technician’s perspective, but that one quite possibly takes the cake. My previous discussion regarding our experiences with Comcast not withstanding, this one’s pretty bad.

Seminar Summary of Classic ACM Papers: Part I

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.