Letters

I was pleased with Ed Nisley's article "State of the Machine" (DDJ, December 2002). However, the state of the art in this area goes beyond the usage of flowcharts/UML/Statecharts. The benefits of the approach are even greater than eluded to in his article. There has been quite a bit of research devoted to the idea of stateboxes in software in the last decade. Formal methods in software engineering tend to focus heavily around the concept of software as a state machine.

One area in which I have personal experience is called "cleanroom software engineering." Structured Programming: Theory and Practice (Addison-Wesley, 1979), by R.C. Linger, H.D. Mills, and B.I. Witt, changed the industry in 1979. Today, structured programming is taught at the freshman level in college and is considered an essential skill to producing functional, maintainable code. Mills, Linger, and Alan R. Hevner further refined these ideas into approaching software development as statebox development in Principles of Information Systems Analysis and Design (Academic Press, 1997). This work did not enjoy such a large reception.

Over the last decade, these methods have been further expanded and developed by Drs. Poore and Trammell, and time after time, they demonstrated software development with previously unheard of lows in defect rate using a method that was coined as "cleanroom." Dr. Prowell further contributed a practical method to generate complete, concise, and verifiably correct code. Prowell, Trammell, Linger, and Poore published a wonderful guide to this method in Cleanroom Software Engineering: Technology and Process (Addison-Wesley, 1999). "Complete, concise, and verifiably correct" refers to the fact that the resulting statebox will be neither under or over specified, and can be directly audited for compliance with the requirements. The method (if perfectly followed— something I fear no human is capable of), will also generate a canonical statebox.

A quick exposition of the method is in order. The cleanroom method begins with a set of requirements. From this, stimuli and responses expected of the system are identified and traced to requirements. Stimuli are enumerated, methodically considering the response to every possible sequence of stimuli. A sequence may be illegal (and hence ignored) terminating any further expansion of that line of stimuli. It may also be equivalenced back to a previous set of stimuli. Each line is related back to the requirements. Once all expansions have terminated, the enumeration is completed. The design of a statebox that satisfies this enumeration follows easily from this information. This process uncovers many things that were left out of the requirements and identifies all the odd cases that one would not normally consider. So in the end, the requirements are greatly refined and a formal statebox matching them has been designed. Test case generation is also mathematically derived from a usage model based on the requirements. The nature of having a canonical statebox also leads to less code, which means less chance of bugs and less maintenance.

In practice, this method has led to project after project with near-zero defect rates. Why this hasn't caught on in the industry is a question I find myself asking time and time again. For one, it isn't laden with cool sounding buzzwords, like extreme (aside on XP: Gradient descent is not guaranteed to find the global minimum—think about it), aspect, agile, modality, synergy, and so on. Second, the method is tedious and nowhere near as fun as sitting down and hacking. Third, it gets little press. It is slowly gaining ground, especially in the medical device industry, telecommunications industry, and military. It isn't a silver bullet that solves all of a software development program's problems, things such as team communication would rank above this or any other method. Also cases where there are state space explosions, such as telecommunication routers, are impossible to be fully enumerated by hand. Research into extensions to cleanroom to handle such cases is underway today, using things such as categories of states. Composition of stateboxes handles most complex cases quite nicely, however, and is well understood.

In summary, Ed's column is a definite push in the direction of less buggy software and proper design. The evidence has been demonstrated many times by research and application of state-machine design. I'm already giving it a try and it's been a wonderful success for me.

Shawn Garbett
[email protected]

More On Little Languages

Dear DDJ,

The points in Joe Block's response ("Letters," DDJ, October 2002) to my letter ("Letters," DDJ, July 2002) are well-taken except for his statement: "On Windows, all compilers cost money." There are plenty of free languages; I still have the remnants of my CP/M Small-C, and it's my recollection that free compiler and script languages were available during the MS-DOS era and on into the days of Windows. But until very recently, none of them had an integrated IDE—which is crucial. When I want a utility to do something, I can write it in a batch or in any of a number of languages—or I can write and debug it in a unified IDE. There's just no comparison, then or now, in ease-of-use and productivity. Indeed, I've been wasting my time recently with Kylix (Linux Borland Delphi Pascal IDE) a bit, and it is still orders of magnitude more fun than gcc + gdb.

J.G. Owen
[email protected]

Incorrect Values

Dear DDJ,

In the article "Examining the VxWorks AE 1.1 RTOS," by Bart Van Beneden (DDJ, November 2002), there's a discrepancy between Table 1 (the interrupt results) and the reference to it: "Table 1 shows that when interrupts occur more frequently than every 255s,..." What are the correct values?

Georg Lohrer
[email protected]

DDJ responds: Thanks for pointing out the typesetting error Georg. Our apologies to the author and to readers. The table is correct, and the text reference (page 70) should be 25s.

DDJ