History Of Iterative

History of Iterative and Incremental Development.

For the June 2003 IEEE Computer issue dedicated to agile processes (edited by A. Cockburn and L. Williams), Vic Basili and CraigLarman wrote history of iterative/incremental/agile lifecycle processes. You can get the PDF of the whole article from http://www.craiglarman.com

This is an excerpt from the beginning of the paper, from the 1950s-1980.

Iterative and Incremental Development:A Brief History

Craig Larman Chief Scientist, Valtech USA craig@craiglarman.com

Dr. Victor R. Basili Professor, Dept. of Computer Science, University of Maryland basili@cs.umd.edu

A central practice of agile methods is iterative, evolutionary, and incremental software development. This is a spotlight history of its long and widespread practice, promotion by software engineering thoughtleaders, and recommendation by standards groups. Large projects ranging from Project Mercury in the late 1950s to an air traffic control system in the 1990s are noted. A detailed analysis of the different methods is beyond the scope of this history; the emphasis is chronology rather than comparison.

Although evolutionary, iterative and incremental development (IID) in software is in the ascendance as the "modern" or "agile" approach to replace ad hoc or waterfall (sequential lifecycle) development, its practiced and published roots go back surprisingly far. At least as far back as the mid 1950s, as a contemporary alternative to the nascent waterfall model, first described as the "stagewise model" for the USA air defense SAGE project by H.D. Benington in "Production of Large Computer Programs," Proceedings of the ONR Symposium on Advanced Program Methods for Digital Computers, June 1956. Winston Royce also opined on the waterfall model -- within the constraints of government contracting at that time -- in "Managing the Development of Large Software Systems," Proceedings of IEEE Westcon, 1970. We are mindful that the idea of IID comes independently from many, countless unnamed projects and the contribution of thousands. This short history spotlighting a few projects and individuals is not meant to diminish the unsung importance of others.

Agile methods which apply IID as a cornerstone practice have received criticism from waterfall and requirements engineering proponents for insufficient early requirements and design. But, the history shows evolutionary requirements, design, and development rather than large up-front specification efforts has been common, successful, and recommended by experts. Of course, software engineering experts (e.g., readers of IEEE journals) are well aware of this, but it is still surprisingly unknown in many commercial and government organizations.

There are variations in the IID approaches described here, and it is beyond the scope of this article -- chronology rather than comparison -- to provide deep contrasting analysis.

Yet, some varying and common traits are noted, such as differences in the lifecycle details. For example, the length of iterations, and whether or not they were timeboxed. Another difference is the degree of up-front work on specifications. Some early projects attempted significant up-front work combined with incremental timeboxed development. Others -- the majority -- were more classically evolutionary and feedback-driven.

Yet in each, there was a common theme to avoid a single-pass sequential, document-driven, gated-step approach.

On terminology: in modern usage in popular IID methods such as the Unified Process, Extreme Programming, Scrum, and DSDM, iterative development implies not just revisiting work, but also -- and more commonly -- evolutionary advancement. And as the history will show, this usage extends as far back as the 1960s. Begging forgiveness from the more literal-minded, the article follows popular convention.

The majority of discussion and examples are devoted to the 1970s and 80s -- the most active early history that is least known. The 1990s and beyond section is briefer.

On with the story

Pre-1970

Early roots for IID are found in the work of Walter Shewhart, the quality expert at Bell Labs who proposed, in the 1930s, a series of short "Plan-Do-Study-Act (PDSA)" cycles for quality improvement. PDSA was then vigorously promoted by quality guru W. Edwards Deming, starting in the 1940s, and described in his Out of the Crisis in 1986. The application of PDSA to software was explored in Tom Gilb's early IID method Evo (more on this later), and by Zultner in The Deming Approach to Quality Software Engineering, Quality Progress, 21(11) 1988.

A milestone 1950s project applying IID was the X-15 hypersonic jet (see W.H. Dana, The X 15 Lessons Learned, NASA Dryden Research Facility, 1993):

A major contributor to the X-15 s success over the long run was its emphasis on incremental development.

Although not a software project, we mention the X-15 because some personnel (and hence, IID experience) seeded NASA's early 1960s Project Mercury, which did apply IID in software -- and some of the latter project's personnel seeded the IBM Federal Systems Division (FSD), another early IID proponent.

Project Mercury was run with very short, but structured, n-day timeboxed iterations. There was a technical review of all changes, and interestingly, the Extreme Programming practice of test-first development was applied: tests were planned and written in advance of each micro-increment. Top-down development with stubs was also practiced.

Recollections of Gerald M. Weinberg, who worked on the project, provide a window onto some practices during this period (personal communication):

We were doing incremental development as early as 1957, in Los Angeles, under the direction of Bernie Dimsdale [at IBM's Service Bureau Corporation]. He was a colleague of John von Neumann, so perhaps he learned it there, or assumed it as totally natural. I do remember Herb Jacobs (primarily, though we all participated) developing a large simulation for Motorola, where the technique used was, as far as I can tell, indistinguishable from XP.

When much of the same team was reassembled in Washington, DC in 1958 to develop Project Mercury, we had our own machine and the new Share Operating System, whose symbolic modification and assembly allowed us to build the system incrementally, which we did, with great success. Project Mercury was the seed bed out of which grew the IBM Federal Systems Division. Thus, that division started with a history and tradition of incremental development.

All of us, as far as I can remember, thought waterfalling of a huge project was rather stupid, or at least ignorant of the realities. I think what the waterfall description did for us was make us realize that we were doing something else, something unnamed except for software development.

The earliest reference we found specifically focused on describing and recommending iterative development came in 1968 from Randell and Zurcher at the IBM T.J. Watson Research Center, "Iterative Multi-level Modeling -- a Methodology for Computer System Design," Proceedings of the IFIP Congress, 1968.

This was cited, and the promotion of iterative development repeated, in M.M. Lehman's Sept 1969 internal report to IBM management on development recommendations, in "The Programming Process" (reprinted in Program Evolution -- Processes of Software Change, 1985). To quote Lehman summarizing their work:

The basic approach recognizes the futility of separating design, evaluation and documentation processes in software-system design. The design process is structured by an expanding model seeded by a formal definition of the system, which provides a first, executable, functional model. It is tested and further expanded through a sequence of models, that develop an increasing amount of function and an increasing amount of detail as to how that function is to be executed. Ultimately, the model becomes the system.

[See also LehmansLaws]

Another 1960s reference we found came from the still active Robert Glass (columnist in IEEE Software and CACM): "Elementary level Discussion of Compiler/Interpreter Writing," ACM Computing Surveys, Mar 1969. Glass writes:

It is the opinion of the author that incremental development is worthwhile, [it] leads to a more thorough system shakedown, avoids implementer and management discouragement.

The 1970s

In the aforementioned 1970 article by Royce -- often (incorrectly) cited as the paragon of single-pass waterfall -- he actually recommends an approach somewhat different than what has devolved into the notion of waterfall today, with its strict sequence of requirements analysis, design, and development phases. He recommends to "do it twice." To quote:

If the computer program in question is being developed for the first time, arrange matters so that the version finally delivered to the customer for operational deployment is actually the second version insofar as critical design/operations areas are concerned.

He goes on to suggest that a 30-month project might have a 10-month throw-away "pilot model" and justifies its necessity where there are novel elements and unknown factors (hardly a unique case). Thus, we see hints of iterative development, feedback and adaptation. This iterative feedback-based step in a classic "waterfall paper" has been lost in most descriptions of this model, although it was clearly not classic IID.

What did Royce think about the waterfall vs. IID, as he came to learn of the latter approach? His son, Walker Royce, a contributor to popular IID methods in the 1990s, said of his father and this paper (personal communication):

He was always a proponent of iterative, incremental, evolutionary development. His paper described the waterfall as the simplest description, but that it would not work for all but the most straightforward projects. The rest of his paper describes [iterative practices] within the context of the 60s/70s government contracting models (a serious set of constraints).

An ironic insight, given the influence this paper had as part of the bulwark promoting a strict sequential lifecycle for large, complex projects.

The next earliest reference in 1970 comes from Harlan Mills, a 70s software engineering thoughtleader who worked at the IBM FSD. In his well-known "Top-down Programming in Large Systems" he promotes iterative development. This was published in Debugging Techniques in Large Systems (and reprinted in Mills collected papers: Software Productivity, 1988).

In addition to the paper's main advice to develop starting from top-level control structures downwards, perhaps less appreciated was the related lifecycle advice of building the system via "iterated expansions."

it is possible to generate a sequence of intermediate systems of code and functional subspecifications so that at every step, each [intermediate] system can be verified to be correct,

Clearly, Mills suggests iterative refinement for the development phase, but there is no mention of avoidance of a large up-front specification step, length of iterations, or an emphasis on feedback and adaptation-driven development from each iteration. However, these are points that he raises later in the decade. Given his employment at the IBM FSD, we suspect his exposure to more "classic" IID projects run there in the early 1970s influenced his thought, but could not confirm this with colleagues.

Early practice of more modern IID (feedback-driven refinement with customer involvement, clearly delineated iterations) come from the leadership of Mike Dyer, Bob McHenry?, and Don O'Neill (and many others) during their tenure at the IBM FSD. What is fascinating about the FSD story is the extent and success of IID use on large, life-critical USA Department of Defense (DoD), space, and avionic systems during the 70s.

The first major FSD documented application of IID (that we know of) was in 1972. This was no toy application, but a major, high-visibility life-critical system of over 1 million lines of code: the command and control system for the first USA Trident submarine. The project included Dyer, McHenry?, and O'Neill as project manager. O'Neil conceived and planned the use of IID (later called "integration engineering" at FSD) on this project; it was a key success factor, and he was awarded an IBM Outstanding Contribution Award for it. Note the visible approval by IBM leadership for IID methods.

The project could not be late: the system had to be delivered by a certain date, otherwise FSD faced a $100,000 per day late penalty. The project was organized in 4 timeboxed iterations of about 6 months each. There was still a significant up-front specifications effort, and the iteration length was longer than normally recommended today. Although there was some feedback-driven evolution in the requirements, the IID approach was seen also as a way to manage the complexity and risks of large-scale development. See O'Neill, "Integration Engineering Perspective," The Journal of Systems and Software, 3, 1983.

Also in 1972, and outside of the IBM FSD, another major project that applied IID comes from an FSD competitor: TRW.

They applied incremental development on the $100 million TRW/Army Site Defense software project for ballistic missile defense. The project began in February 1972 and developed the system in 5 iterations. Iteration 1 did tracking of a single object, and by iteration 5, a couple of years later, the system was complete. The iterations were not strictly timeboxed, and there was significant up-front specifications work, but they were also refined in response to each iteration's feedback. See Williams, "Managing the Development of Reliable Software," Proceedings, International Conference on Reliable Software, ACM/IEEE, April 1975.

As with IBM FSD, TRW (where Royce worked) was an early adopter of IID practices. Indeed, Barry Boehm, the originator of the IID "spiral model" in the mid 80s, served at TRW as Chief Scientist.

Another early (mid 1970s), successful, and extremely large application of IID at FSD was the USA Navy helicopter-ship system LAMPS. A 4-year 200 person-year effort involving millions of line of code, it was incrementally delivered in 45 timeboxed iterations (1 month per iteration). This is the earliest project example we found where the length of iteration was in the range commonly recommended by today's popular IID methods (most advise in the 1-6 week range). The project was quite successful: To quote, "Every one of those deliveries was on time and under budget." See Mills, "Principles of Software Engineering," IBM Systems Journal, Vol 19, No 4, 1980.

In 1975 another early and widely cited paper devoted to IID was published. The approach was called "iterative enhancement" and comes from Vic Basili and Joe Turner. See "Iterative Enhancement: A Practical Technique for Software Development," IEEE Transactions on Software Engineering, Dec 1975. The description plainly describes classic IID:

The basic idea behind iterative enhancement is to develop a software system incrementally, allowing the developer to take advantage of what was being learned during the development of earlier, incremental, deliverable versions of the system. Learning comes from both the development and use of the system, where possible. Key steps in the process were to start with a simple implementation of a subset of the software requirements and iteratively enhance the evolving sequence of versions until the full system is implemented. At each iteration, design modifications are made along with adding new functional capabilities.

Basili and Turner describe the successful application of IID to the development of an extendable family of compilers for a family of application specific programming languages on a variety of hardware architectures. The base system was developed in 17 iterations over 20 months. Each iteration was analyzed from the both the user's and developer's point of view and the feedback influenced both the language requirements and design changes for future iterations. Measures, such as coupling and cohesion, were tracked over the multiple iterations.

1976 saw the arrival of a long-standing and passionate voice for evolutionary and iterative development. Tom Gilb published Software Metrics (coining the term), in which he included discussion of his IID practice named evolutionary project management, and introduced the terms "evolution" and "evolutionary" to the process lexicon. This is the earliest book we could find containing a clear discussion and promotion of IID, and especially, evolutionary delivery. For example:

"Evolution" is a technique for producing the appearance of stability. A complex system will be most successful if it is implemented in small steps and if each step has a clear measure of successful achievement as well as a "retreat" possibility to a previous successful step upon failure.

You have the opportunity of receiving some feedback from the real world before throwing in all resources intended for a system, and you can correct possible design errors.

Gilb is one of the earliest and most active IID practitioners and promoters, having started the practice in the early 1960s, and as we will see, responsible for a few IID milestones. His material was probably the first with a clear agile, light, quick results-oriented, and adaptive iterative flavor similar to newer IID methods.

By 1976, Harlan Mills had strengthened his IID message. In "Software Development," IEEE Transactions on Software Engineering, Dec 1976, he writes:

Software development should be done incrementally, in stages with continuous user participation and replanning, and with design-to-cost programming within each stage.

In the context of a 3-year inventory control system, he goes on to challenge the idea and value of up-front requirements or design specifications. He says:

there are dangers, too, particularly in the conduct of these [waterfall] stages in sequence, and not in iteration -- i.e., that development is done in an open loop, rather than a closed loop with user feedback between iterations. The danger in the sequence [waterfall approach] is that the project moves from being grand to being grandiose, and exceeds our human intellectual capabilities for management and control.

And perhaps reflecting several years of seeing IID in action at FSD, Mills asks:

why do enterprises tolerate the frustrations and difficulties of such [waterfall] development?

In 1977, the Trident IID approach that included integrating all software components at the end of each iteration (named "Integration Engineering" by McHenry?) was incorporated into the FSD Software Engineering Practices, to which the Trident team and Mills were key advisors. See O'Neill, "The Management of Software Engineering," IBM Systems Journal, vol 19, No 4, 1980. Integration Engineering was spread to the 2,500 FSD software engineers, and the idea of IID as an alternative to the waterfall stimulated substantial interest within IBM's commercial divisions, senior customer ranks, and among competitors.

Although unknown to most software professionals, another early and striking example of a major IID success is the very heart of the NASA Space Shuttle software itself: the Primary Avionics Software System. This was built by FSD from 1977 to 1980, applying IID in a series of 17 iterations over 31 months, averaging around 8 weeks per iteration (see Madden and Rone, "Design, Development, Integration: Space Shuttle Flight Software System," Communications of the ACM, Sept 1984). Their motivation? The waterfall lifecycle was not suitable because "The requirements on the Shuttle program evolved during the software development process." Ironically (in hindsight), the authors sound almost apologetic in having to forego the "ideal" waterfall for an IID approach:

Due to the size, complexity, and evolutionary [changing requirements] nature of the program, it was recognized early that the ideal software development lifecycle [the waterfall model] could not be strictly applied. However, an implementation approach (based on small incremental releases) was devised for STS-1 which met the objectives by applying the ideal cycle to small elements of the overall software package on an iterative basis.

This Shuttle project also exhibited classic IID practices: timeboxed iterations in the 8 week range, feedback-driven refinement of specifications, and so forth.

1978 saw the first discussion of IID in the popular press that we could find. Tom Gilb started publishing a column in Computer Weekly (UK) that regularly promoted IID, evolutionary project management and delivery. For example (April 6, 1978):

''Management does not require firm estimates of completion, time, and money for the entire project. Each [small iterative] step must meet one of the following criteria (priority order): either (a) give planned return on investment payback, or, if impossible, then (b) give breakeven (no loss); or, at least, (c) some positive user benefit measurably; or, at least (d) some user environment feedback and learning.''

An early paper sometimes cited on the subject of incremental development is "A Successful Software Development," by Wong, in IEEE Transactions on Software Engineering, no. 3, 1984. It describes a successful air defense system project that ran from 1977 to 1980 that combined significant up-front specifications -- but with incremental development and builds. The project was ostensibly meant to fit within DoD single-pass waterfall standards, with testing and integration in the last phase. However, Wong comments on the unrealism of this approach, and their need and advantages using incremental development:

The [waterfall] model was adopted because software development was guided by DoD standards. In reality, software development is a complex, continuous, iterative, and repetitive process. The [waterfall model] does not reflect this complexity.