• S-type programs — programs whose function is formally defined by and derivable from a specification.
• P-type programs — programs for which the problem may be precisely formulated, but for which the solution must inevitably reflect an approximation of the real world.
• E-type programs — programs that mechanize a human or societal activity and are embedded in the real world.

P-type and E-type programs differ from S-type programs in that they represent a computer application in the real world. They are together called A-type programs.

It is A-type programs that are most prone to change.

A longer summary of Lehman’s SPE-classification is given below, quoting heavily from the original article.

S-type programs

S-programs are programs whose function is formally defined by and derivable from a specification (hence the S).

Examples are the lowest common multiple of two integers, eight queens and dining philosophers.

Such problems may relate directly and primarily to the external world, but be completely defined.

Correct solution of the problem as stated, in terms of the programming language being used, becomes the programmer’s sole concern. At most, questions of elegance or efficiency may also creep in.

When this view can be legitimately taken the resultant program is conceptually static. One may change it to improve its clarity or its elegance, to decrease resource usage when the program is executed, even to increase confidence in its correctness. But any such changes must not effect the mapping between input and output that it achieves in execution.

In S-programs, judgments about the correctness, and therefore the value, of the programs relate by definition only to its specification.

P-type programs

P-programs are programs for which the problem may be precisely formulated, but for which the solution must inevitably reflect an approximation of the real world. (P for real world problem solution).

As an example, consider a program to play chess. The rules of the game of chess are completely specified; a procedure to make the best move at any given position can also be completely specified formally. Such a procedure is for example to, at any given position, create the tree of all games that may develop from it and adopt a minimax evaluation strategy to select the next move.

Because this search tree is very large, such an approach is not feasible in practice. Practical approaches to chess programs must therefore make some approximations.

The process of creating P-programs happens in the context of an intrinsic feedback loop.

Despite the fact that the problem to be solved can be precisely defined, the acceptability of a solution is determined by the environment in which it is embedded.

The solution obtained will be evaluated by comparison with the real environment.

In P-programs, the concern is not centered on the problem statement but on the value and validity of the solution obtained in its real-world context.

E-type programs

E-programs are those programs that mechanize a human or societal activity. The program has become a part of the world it models, it is embedded in it (hence the E).

They are are inherently even more change prone than P-programs in the following ways:

• It is not necessarily possible to precisely formulate the problem in the first place; the formulation of the specification must involve opinion and judgement. Once the program starts to be used, it creates feedback about this problem formulation, which leads to pressure for change.

• The program affects the world it is embedded in: the usage patterns, habits, capabilities and expectations of its users and others. By so affecting the world, further pressure for change is created.

• The world that’s being modeled may itself change, independently from the program. To stay relevant in the changing world, the program must change.

Examples of such programs are plentiful: Operating Systems, business administration software, inventory management, stock trading etc.