This article draws on ideas originally discussed at InfoQ, grounded in Meir Lehman’s 1980 paper “Programs, Lifecycles, and Laws of Software Evolution.”
The Core Tension: Correctness vs. Change
When you start programming, the appeal is the puzzle: make the machine produce the right answer. But as software grows larger and more complex, a harder problem emerges — how do you even define what “right” means? Static typing, automated testing, property testing, and proof assistants all assume you can specify correctness up front. Most of the time in production software, you can’t.
The practical reality of software requirements is that they conflict, evolve, and are often only partially understood. Trying to resolve every corner case before writing a line of code is a path to paralysis. The better approach is to recognize that not all software is the same — and to choose your optimization target accordingly.
Sometimes correctness is possible, and it matters. The rest of the time, optimize for change, so that we can incrementally discover and approach “right.”
When Is Correctness Even Possible?
Consider how different these software contexts are: firmware baked into hardware, scientific data-reduction pipelines, financial settlement systems, internal activity dashboards, and a landing page for a 30-day ad campaign. These are not the same engineering problem. Treating them identically — insisting on full formal specification for each — is a category error.
Meir Lehman’s 1980 paper “Programs, Lifecycles, and Laws of Software Evolution” made a crucial observation: many arguments about correctness “become reconcilable or irrelevant under an adequate program classification scheme.” His classification divides programs into three types — S, P, and E — based on how well the solution is understood at the time of development.
Lehman’s S/P/E Classification
- S-programs — A solution is formally specified and derivable from that specification.
- P-programs — A problem is specified, but an optimal solution is computationally intractable; we can only seek “better.”
- E-programs — The software is entwined in the problem space it is trying to improve; requirements shift as the software is used.
S-Programs: A Solution Is Specified
An S-program is one whose function is formally defined and derivable from a specification. Given a complete, non-contradictory spec, there is a provably correct implementation. Classic examples include sorting algorithms, checksum functions, cryptographic primitives, and well-defined data-format parsers.
Writing the specification is the genuinely hard part. Committees that produce standards like CSS or the JPA specification are doing the difficult work of resolving conflicts and edge cases so that implementors can aim at a fixed target. When a discrepancy surfaces between a program and its specification, the bug is often in the spec itself.
Once an S-program correctly implements its specification, it is effectively done. You might tune it for performance, but the specification hasn’t changed. If the requirements change, you have a different S-program — possibly one that borrows code from the original, but conceptually separate. S-programs are the puzzles we can fully solve, and solving them is deeply satisfying.
P-Programs: A Problem Is Specified
Some problems can be precisely stated but not optimally solved in tractable time. The classic example is the travelling salesman problem: we can define the objective function exactly, but finding a globally optimal route over large graphs is computationally prohibitive. We can find better and better approximations, but not a provably perfect answer.
Statistical simulations such as Monte Carlo methods also belong here. They cannot be exhaustively tested because they are not deterministic by design. Mathematical reasoning and formal proofs carry more weight than test suites in this domain.
Lehman notes that P-programs evolve as we learn more about the problem — new constraints surface once an algorithm is in use — which is why he groups them with E-programs for lifecycle purposes.
E-Programs: Software Entwined in the Problem Space
Everything else — and this is the vast majority of custom software — falls into the E category. These are systems built with incomplete requirements, deployed into environments that change, used by humans whose needs and behaviours shift in response to the software itself.
Lehman called these programs “embedded” (meaning embedded in a sociotechnical system, not embedded in hardware — a terminology choice that causes confusion). A better word is entwined. The program becomes a part of the world it models. Deploying new software changes the human system around it, which generates new demands on the software. As Lehman wrote: “The need for continuing change is intrinsic to the nature of computer usage.”
E-programs are never truly “done.” If your goal is to close tickets and ship finished things, this can feel unsatisfying. If your goal is to help real people with real problems, E-programs are where the most meaningful work happens.
Compose Applications from S-Programs Wherever Possible
Lehman’s insight that applications should be built from well-defined, correct S-program components is sound. His mistake was in the sequencing: he believed you should fully decompose the application into S-programs before writing it. In practice the order is reversed. You build the fuzzy, evolving E-program first, and S-program components emerge from that process over time as understanding solidifies.
Lehman also assumed each S-program component would be implemented by the development team. The modern reality is different: you search for existing, already-verified implementations — open-source libraries, frameworks, SaaS components — and adapt the application design to use them. Custom software development today is far more about integration than original construction.
S-Programs Are Reusable: Optimize for Correctness
Because S-programs are well-specified, they are reusable across projects. This property — and the intellectual satisfaction of solving a clean puzzle — is what drives the enormous ecosystem of open-source libraries, language standard libraries, and software-as-a-service primitives.
A practical signal that you have found an S-problem inside a larger E-program: the sub-problem feels abstract and general, and a nagging sense surfaces that someone has already solved it. That is usually correct. Search before implementing.
When you are creating a reusable S-program, correctness is the right optimization target. Use property-based testing, type systems, and formal reasoning where practical. This investment pays back every time the component is reused.
Problems Migrate from E to S as Understanding Matures
The boundary between E and S is not fixed. Components that start out as bespoke, imprecisely-understood parts of an application can later be extracted, generalized, and turned into well-specified, reusable S-programs — but only after the problem has been solved enough times in enough contexts to be fully understood.
Object-relational mapping is a good historical example. Development teams wrote custom ORM code inside their own applications for years. Once the problem was widespread and well-understood, frameworks like Hibernate could solve it broadly. After that, a standards committee could write the JPA specification — a formal S-program target. Similarly, CRUD application patterns became clear enough through repetition that a framework like Ruby on Rails could encode them as reusable conventions.
Good standards emerge from many implementations; correct implementations then follow from good standards.
E-Programs Are Most Custom Software: Optimize for Change
If you are building software for humans to use inside a business context, you are almost certainly building an E-program. It is fit for a specific purpose, part of specific operations, and not designed for reuse outside that context. The job is not to make it permanently correct — it is to make it correct enough now and keep making it better. The optimization target is change, not correctness.
What does optimizing for change mean in practice?
Don’t Write Code — Change Code
Lehman analysed the traditional software lifecycle — Requirements → Design → Detailed Design → Programming → Test → Rollout → Maintenance — and noticed that problems clustered at the handoffs between phases. He also noticed that every earlier phase appears, in miniature, inside Maintenance. His recommended fix was to strengthen the separations between phases. The better answer, now visible with hindsight, is to collapse them: start somewhere and iterate. Make every change small and safe. When changes are small enough, the phases blur together and the handoff problems disappear.
Practically, this means:
- Establish a walking skeleton of the application early, before it does anything useful.
- Wire in continuous integration and automated testing from day one, not as an afterthought.
- Automate deployment so that shipping a small change has a low and predictable cost.
- Treat security scanning and quality gates as part of the delivery pipeline, not a separate phase.
These are not optional polish. They are the table stakes for playing the “change software safely” game.
Reduce the Fear of Changing Code
The biggest obstacle to continuous change is not the effort involved — it is fear. Fear that a change will break something, that a refactoring will introduce a regression, that a deployment will cause an outage. Modern engineering practices directly address this:
- Refactoring with automated tests lets you reshape code with confidence that behaviour is preserved.
- Microservices and module boundaries limit the blast radius of any single change.
- Infrastructure as code and deployment automation make the operational side of change repeatable and auditable.
- Feature flags decouple deployment from release, so you can ship code without exposing it to all users at once.
Lehman even anticipated service-oriented decomposition in 1980, noting that each module could run on its own processor in a distributed system — while acknowledging that many problems with such architectures remained unsolved. Many of those problems now have established solutions.
Change How You Change Code
The most important architectural question for an E-program is not “what should it do?” but “how will we change it?” Good architecture defines both a target state and a practical path from here to there.
Your delivery pipeline is itself an E-program. The software you need to deliver changes. The infrastructure you deploy to evolves. The quality checks your organisation requires shift over time. Treat your CI/CD configuration with the same care you give production code: version it, test it, and refactor it. A rigid pipeline becomes a bottleneck as fast as rigid application code.
When You Can’t Know “Correct,” Aim for “Better”
Lehman wrote: “Absolute correctness of the program as a whole is not the real issue. It is the usability of the program and the relevance of its output in a changing world that must be the main concern.”
Usability and relevance are not easy to unit test. But they can be measured. Instrument your features to detect whether users actually engage with them. Observe the effect of a change on the system the software is entwined in. Use that signal to decide whether the next change should reinforce, revise, or reverse what you just shipped. A feature that nobody uses is not correct in any meaningful sense, regardless of how many tests it passes.
Summary: Choosing Your Optimization Target
| Program type | Definition known? | Optimize for | Typical examples |
|---|---|---|---|
| S-program | Fully specified | Correctness | Sorting algorithms, cryptographic functions, data format parsers |
| P-program | Problem specified, optimal solution intractable | Better approximations | Route optimization, statistical simulations |
| E-program | Incomplete; shifts with use | Changeability | Most business applications, SaaS products, internal tools |
Recognize which type of software you are building. Reach for existing, correct S-program components wherever the problem is well-understood. Build the entwined, human-facing parts of your system to change safely and often. Measure outcomes in the real world, not just in test suites. That is how you make software that is genuinely useful — not just technically correct.