Lehman on Software, Models and Change

The modeled and evolving quality of software comes to the surface when thinking about software maintenance. A classic paper on this is Lehman’s 1980 paper Programs, life cycles, and laws of software evolution, which lays out the territory with great clarity, then confidently strides off in the completely wrong direction.


Lehman introduces a distinction between 

  • S-programs, that implement a formal mathematical (s)pecification, such as the travelling salesman problem
  • P-programs, that solve some messy (p)roblem arising in the world, such as actually scheduling real salespeople and their ambiguities and partly-known preferences, and 
  • E-programs, those (e)mbedded in and changing the world they directly model, such as in air-traffic control.

For P-programs and E-programs, “the acceptability of a solution is determined by the environment in which it is embedded.” The distinction is in the programs relationship with its origin story: between top-down and bottom-up; transcendence and immanence.

Lehman goes on to note P-programs are also in a feedback loop arising from their use in the world. Their execution is observed, even lived, by their users, and this results in demand for change. 

This is a cybernetic view, though Lehman doesn’t use the terminology. The paper sketches some more complicated loops, particularly where a specification intermediates between the P-program and the world. It is that intermediation, rather than feedback, that is foregrounded in the difficult and famous statement on code:world relations:

Any program is a model of a model within a theory of a model of an abstraction of some portion of the world or of some universe of discourse.

Lehman drops this on page two, before defining S-, P- or E-programs, and never gets around to defining theory or model, or otherwise directly elaborating, disconnected sagelike pronouncements being an expected feature of software engineering papers of the time. Cook (and a team including Lehman) later link this to the social process of Kuhn’s paradigm shifts – renaming P-programs to (p)aradigm-programs and E-programs to (e)volving-programs.

Weisberg’s work on the crucial role of models in science could also help. For Weisberg, a theory maps a model to the world through (mostly explicit) construals. This plays a similar role to “abstraction” in Lehman’s definition. (Bit more on Weisberg here.)

It’s also worth throwing Naur’s “Programming as Theory Building” into the mix, though his paper does not make much distinction between model-as-code and theory-as-code.

Lehman also introduces “laws” of software evolution, which did have some empirical basis, but appear hard to reproduce. They might be compared to more recent work on meaningful descriptive code metrics, or properties of software as a material.

The Rivers and The Lakes That You’re Used To

After accelerating through insight after insight into the fluid and evolving nature of software, Lehman closes off the theory section by casually inventing microservices (in 1980), then taking a screaming left turn at the Process Street T-Junction, crashing through a railing and tumbling over a cliff. For over that cliff flows a process waterfall, and in the structured programming era, there’s nothing more attractive.

Like the rest of the structured programming crowd, he has factory envy: “An assembly line manufacturing process is possible when a system can be partitioned into subsystems that are simply coupled and without invisible links … Unfortunately, present day programming is not like this.” Lehman goes on to emphasize the care and structure needed when writing separate elaborate requirement and technical specifications. You get the idea. The remaining process recommendations I’m just going to skip.

It is easy to be wise after the fact in 2019. Agile practices and literal miniature software assembly lines (continuous build infra) now exist, and have made us much more sensitive to the damage done by scope size and delivery delay in large software systems. Trying to solve complex problems with more upfront planning was a high modernist worldview going out of fashion, but still very much in the intellectual water in 1980: Lehman gave a lecture in 1974 referencing both city planning and the Club of Rome report Limits to Growth. Perhaps it would be fairer to point out that thinkers who advocated short simple changes as a response to complex systems – like Jane Jacobs, or John Boyd and his OODA loop – were always tacking into the intellectual wind.


Cook, S., Harrison, R., Lehman, M.M. and Wernick, P.: ‘Evolution in software systems: foundations of the SPE classification scheme’, Software Maintenance and Evolution Research and Practice, 2006, 18, (1), pp. 1-35  
Lehman, M.M. , “Programs, cities, students – Limits to growth?” Inaugural Lecture, May 14,  1974, ICST Inaugral Lecture Series, Ed., VOI. 2, pp. 147-163, 1979. vol. 9, pp. 211-229,  1970-1974; and in Programming Methodology D. Gries, Ed. New York: Springer-Verlag, 1979,  pp. 42-69.
Lehman, M. M. (1980). Programs, life cycles, and laws of software evolution. Proceedings of the IEEE, 68(9), 1060-1076.
Naur, P. (1985). Programming as theory building. Microprocessing and microprogramming, 15(5), 253-261.
Weisberg – Simulation and Similarity.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.