Say your app stores each user's name as one string, in a field called name, and forty files across the code read that field directly. Then a request comes in: greet people by their first name, and sort them by their last name. So name becomes first_name and last_name, and your pull request touches forty files. Nothing about the product got harder. One small decision, how a name is stored, had leaked into forty places.
Why did one decision reach forty files, and how could you have drawn the lines so it touched just one? In 1972, David Parnas answered that with a tiny program, cut into modules two different ways. Both versions work. But when he lists the changes the program is likely to need, two of them spread through every module of one version, while in the other version every change stays inside a single module. The idea that separates them is information hiding.
This paper is hosted by its original publisher.
Read on dl.acm.orgThe Problem in 1972
D. L. Parnas, at Carnegie-Mellon University, published the paper in Communications of the ACM in December 1972 (volume 15, number 12, pages 1053 to 1058; received August 1971, revised November 1971). By then modular programming already had a textbook statement: the paper opens by quoting a 1970 textbook on the design of system programs, and notes that assemblers already let one module be written "with little knowledge of the code in another module" and be reassembled "without reassembly of the whole system."
He lists what modules were supposed to give you:
| Promise | In his words (p. 1054) |
|---|---|
| teams work apart | "development time should be shortened because separate groups would work on each module with little need for communication" |
| change one module | "it should be possible to make drastic changes to one module without a need to change others" |
| read one module | "it should be possible to study the system one module at a time" |
Then he points at the gap: "Usually nothing is said about the criteria to be used in dividing the system into modules" (p. 1053). Programmers were trained, he says later, to "begin with a rough flowchart" (p. 1056), so the obvious move is to make each step of the flowchart a module. The paper sets out to show that this quietly breaks the second promise.
The KWIC Index
His example is a KWIC index (key word in context, an index for technical literature described by H. P. Luhn in a 1960 paper). Parnas defines it in three sentences: it "accepts an ordered set of lines, each line is an ordered set of words, and each word is an ordered set of characters." Any line may be "circularly shifted" by "repeatedly removing the first word and appending it at the end of the line." The system "outputs a listing of all circular shifts of all lines in alphabetical order" (p. 1054).
Take two lines, the titles of two other papers in this library: no silver bullet and out of the tar pit.
| # | Shift | Sorted output |
|---|---|---|
| 1 | no silver bullet | bullet no silver |
| 2 | silver bullet no | no silver bullet |
| 3 | bullet no silver | of the tar pit out |
| 4 | out of the tar pit | out of the tar pit |
| 5 | of the tar pit out | pit out of the tar |
| 6 | the tar pit out of | silver bullet no |
| 7 | tar pit out of the | tar pit out of the |
| 8 | pit out of the tar | the tar pit out of |
Every word gets a turn at the front, so you can find a title by any word in it. Parnas admits this is small: "such a system could be produced by a good programmer within a week or two." So he asks the reader to treat it "as if it were a large project" (p. 1054).
Modularization 1: Cut by the Steps
The first decomposition follows the flowchart, one module per step (p. 1054):
- Input reads the lines and stores them in core. "The characters are packed four to a word, and an otherwise unused character is used to indicate the end of a word. An index is kept to show the starting address of each line."
- Circular shift runs after input and builds an index of every shift as pairs of (original line number, starting address).
- Alphabetizing reads the arrays of modules 1 and 2 and writes the same kind of pairs, in alphabetical order.
- Output uses the arrays of modules 3 and 1 to print the listing.
- Master control sequences the other four.
Before work could begin, the defining documents had to include "a number of pictures showing core formats, pointer conventions, calling conventions, etc." Every module reads those formats. Parnas notes that "experiments on a small scale indicate that this is approximately the decomposition which would be proposed by most programmers for the task specified."
Four characters to a word means each memory word holds four characters. In our own example, line 1 packed four characters to a word is no◆s ilve r◆bu llet ◆ (◆ is the end-of-word character), with lines starting at addresses 0 and 17 and shift pairs (1,0), (1,3), (1,10), (2,17) and so on. Those addresses are our illustration; the paper gives none.
Five Likely Changes
Then the move that makes the paper. "There are a number of design decisions which are questionable and likely to change under many circumstances. This is a partial list" (p. 1055):
| # | Decision likely to change | Why it might change |
|---|---|---|
| 1 | the input format | |
| 2 | keeping all lines in core (the computer's main memory) | for large jobs they may not all fit at once |
| 3 | packing the characters four to a word | for small data, a character per word saves time; or pack differently |
| 4 | an index of the circular shifts instead of storing them | for a small index or a large core, writing them out may be better; or compute them on demand |
| 5 | alphabetizing the list once | search for each item when needed, or sort partially |
None of these is a feature. Each is a choice made early that might be remade when the data or the machine changes. The name field was exactly this kind of decision.
The Ripple
Run the five changes against modularization 1 (p. 1055):
| Change | Modules it reaches, cut by the steps |
|---|---|
| 1. input format | 1 (input) |
| 2. lines no longer all in core | every module |
| 3. a new packing | every module |
| 4. write the shifts out | circular shift, and alphabetizing and output "will also know of the change" |
| 5. sort on demand | difficult: "The output module will expect the index to have been completed before it began." |
The reason is one sentence: "In the first decomposition the format of the line storage in core must be used by all of the programs."
Modularization 2: Cut by the Secrets
The second decomposition cuts the same program differently (pp. 1054 to 1055):
- Line storage owns the memory layout and offers functions:
CHAR(r,w,c)is the c-th character of the w-th word of line r (soCHAR(1, 2, 3)is thelinsilver),SETCHAR(r,w,c,d)stores a character,WORDS(r)counts the words in a line, andDELINEandDELWRDdelete. - Input reads the lines and calls line storage to store them.
- Circular shifter offers analogs of those functions (
CSCHAR(l,w,c), withCSSETUPcalled first) and "creates the impression that we have created a line holder containing not all of the lines but all of the circular shifts of the lines." - Alphabetizer offers
ALPHandITH:ITH(i)"will give the index of the circular shift which comes ith in the alphabetical ordering." With our lines,ITH(1)is 3:bullet no silver. - Output prints; master control sequences as before.
The Same Changes Again
| Change | Cut by the steps | Cut by the secrets |
|---|---|---|
| 1. input format | 1 | 1 (input) |
| 2. lines no longer all in core | every module | 1 (line storage) |
| 3. a new packing | every module | 1 (line storage) |
| 4. write the shifts out | 3 | 1 (circular shifter) |
| 5. sort on demand | difficult | 1 (alphabetizer) |
In Parnas's words:
By looking at these changes we can see the differences between the two modularizations. The first change is confined to one module in both decompositions. For the first decomposition the second change would result in changes in every module! The same is true of the third change. …
In the second decomposition the story is entirely different. Knowledge of the exact way that the lines are stored is entirely hidden from all but module 1. Any change in the manner of storage can be confined to that module!
(p. 1055)
The alphabetizer "was designed so that a user could not detect when the alphabetization was actually done." And in some versions a symbol table module (the kind of table a compiler uses to keep track of names) was used inside line storage: "This fact was completely invisible to the rest of the system." Two exclamation marks carry the argument.
Two Criteria
What decided where the cuts went? In modularization 1 each module is a step in time. In modularization 2 each module is a secret: line storage hides how lines are stored, input hides the input format, the shifter hides whether shifts are stored or computed, the alphabetizer hides when the sorting happens. "The modules no longer correspond to steps in the processing. The line storage module, for example, is used in almost every action by the system."
In the first decomposition the criterion used was to make each major step in the processing a module. One might say that to get the first decomposition one makes a flowchart. …
The second decomposition was made using "information hiding" [4] as a criterion. …
Every module in the second decomposition is characterized by its knowledge of a design decision which it hides from all others. Its interface or definition was chosen to reveal as little as possible about its inner workings.
(p. 1056)
Reference [4] is his own 1971 Carnegie-Mellon report, "Information distribution aspects of design methodology." He is fair to the flowchart: it "was a useful abstraction for systems with on the order of 5,000-10,000 instructions, but as we move beyond that it does not appear to be sufficient; something additional is needed."
What the Cut Buys
The other two promises follow the same line (p. 1056):
- Teams. In modularization 1, the interfaces "are the fairly complex formats and table organizations," and designing them "must be a joint effort among the several development groups." In modularization 2, they "consist primarily in the function names and the numbers and types of the parameters," so "the independent development of modules should begin much earlier."
- Understanding. "To understand the output module in the first modularization, it will be necessary to understand something of the alphabetizer, the circular shifter, and the input module." In the second, in his "subjective judgment," this is not true.
The subtle part: the two systems "may share all data representations and access methods," and one built either way "could conceivably be identical after assembly" (p. 1055). The difference is "the way that they are divided into the work assignments, and the interfaces between modules." That is why, for Parnas, a module is "a responsibility assignment rather than a subprogram" (p. 1054). The second design "has been used successfully in a class project."
Hiding Too Little
Parnas then turns the criterion on his own design (p. 1056). The circular shifter hid how shifts are stored, but its definition promised an order: line i's shifts before line j's, the original first, then one-word rotations. Programs only needed three things: every shift is there, none appears twice, and a function that gives the original line of a shift. By promising the order, the design ruled out a perfectly good system "in which the circular shifts were produced in alphabetical order, ALPH is empty, and ITH simply returns its argument as a value." He classifies that failure as "a design error."
He then lists other decisions worth hiding (pp. 1056 to 1057):
- a data structure, with its internal linkings and its accessing and modifying procedures, in a single module;
- the sequence of instructions that calls a routine, together with the routine;
- the formats of control blocks, the records for items waiting in an operating system's queues, hidden in a "control block module";
- character codes, alphabetic orderings and similar data;
- the sequence in which items are processed.
Levels
Modularization 2 also has a hierarchy, and Parnas keeps it separate (pp. 1057 to 1058). The relation is "uses": input and the circular shifter use line storage; output and the alphabetizer use the circular shifter; a symbol table, if present, sits on level 1 and line storage on level 2. Because nothing lower uses anything higher, the relation is a partial ordering, and that gives two benefits: lower levels simplify the upper ones, and "we are able to cut off the upper levels and still have a usable and useful product." The symbol table "can be used in other applications; the line holder could be the basis of a question answering system."
But a system cut like modularization 1 could keep a hierarchy too, so "hierarchical structure and 'clean' decomposition are two desirable but independent properties of a system structure."
He saw the same pattern in a translator for a Markov algorithm language that he and his colleagues built: because modules such as "register representation, search algorithm, rule interpretation" hid decisions rather than following steps, the decomposition "was valid for a pure compiler and several varieties of interpretors."
The Price of Hiding
Parnas did not pretend the second design was free:
If we are not careful the second decomposition will prove to be much less efficient than the first. …
… To successfully and efficiently make use of the second type of decomposition will require a tool by means of which programs may be written as if the functions were subroutines, but assembled by whatever implementation is appropriate. …
(p. 1057)
With every function a procedure call, printing one shift means asking for it a character at a time through the shifter into line storage (in our own sketch, 28 calls for the 14 letters of bullet no silver, one CSCHAR and one CHAR each), while modularization 1 transfers control between modules only now and then. His fix was to insert routines "into the code by an assembler." Today compilers do exactly that. The GCC manual: "One way GCC can achieve this is to integrate that function's code into the code for its callers. This makes execution faster by eliminating the function-call overhead." It is called inlining. His conclusion puts the same point as a rule: "To achieve an efficient implementation we must abandon the assumption that a module is one or more subroutines, and instead allow subroutines and programs to be assembled collections of code from various modules" (p. 1058).
Where It Lives Today
Java's String class hides how it stores its characters; your code calls length() and charAt(i). For years the array inside used two bytes per character. JEP 254 reports that "most String objects contain only Latin-1 characters. Such characters require only one byte of storage, hence half of the space in the internal char arrays of such String objects is going unused." So Java 9 (General Availability on 21 September 2017) changed the packing:
We propose to change the internal representation of the String class from a UTF-16 char array to a byte array plus an encoding-flag field. …
This is purely an implementation change, with no changes to existing public interfaces.
That is Parnas's change 3, "we may pack, but in different formats," made inside one module. Code that only used String's public methods did not need to change.
What Aged
The cost of a call. His efficiency warning is the most dated part of the paper. The "tool" he asked for is a normal compiler optimization now.
Hiding became a language feature. In 1972 a module was a work assignment kept by discipline. Languages now enforce the boundary: in Go, a name is visible outside its package only if "the first character of the identifier's name is a Unicode uppercase letter."
Leaks nobody promised. Parnas's error was an order he promised. Hyrum's Law describes the modern version: "With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody." Go's maps are a clear case. The old Go specification "did not define the order of iteration for maps, and in practice it differed across hardware platforms," so "a test might always pass on one machine but break on another." Go 1 (released 2012-03-28) defined the order "to be unpredictable, even if the same loop is run multiple times with the same map," so that "code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem." The current specification still says the order "is not specified and is not guaranteed to be the same from one iteration to the next." Hiding a decision now sometimes means making it impossible to observe.
The flowchart scale. His "5,000-10,000 instructions" is a 1972 number. The advice outlived it.
A small erratum: the paper spells the textbook authors "Gouthier and Pont" in the text and "Gauthier" in the references.
The Takeaway
Back to the forty files. Had the name lived inside one user module, with every other file asking it for a display name or a sort key, splitting the field would be a change to one file, and the forty files that call it would never notice. That is the method of the paper's conclusion:
We have tried to demonstrate by these examples that it is almost always incorrect to begin the decomposition of a system into modules on the basis of a flowchart. We propose instead that one begins with a list of difficult design decisions or design decisions which are likely to change. Each module is then designed to hide such a decision from the others. …
(p. 1058)
Draw your module boundaries around the decisions most likely to change, not around the steps the program takes.
Less than two years later, an operating system paper described every disk, tape drive and communication line as a file, read and written through the same small interface. Which raises the question that Ritchie and Thompson's Unix paper answers: what can you build when everything looks like a file?
References
- D. L. Parnas, "On the Criteria To Be Used in Decomposing Systems into Modules," Communications of the ACM 15(12), December 1972, pp. 1053 to 1058. ACM Digital Library.
- H. P. Luhn, "Key word-in-context index for technical literature (kwic index)," American Documentation 11(4), October 1960. doi.org/10.1002/asi.5090110403.
- GCC manual, "An Inline Function is As Fast As a Macro." gcc.gnu.org.
- JEP 254, "Compact Strings." openjdk.org/jeps/254. JDK 9 project page: openjdk.org/projects/jdk9.
- Java SE 21 API,
java.lang.String. docs.oracle.com. - Hyrum's Law. hyrumslaw.com.
- Go 1 release notes, "Iterating in maps." go.dev/doc/go1. Go release history: go.dev/doc/devel/release. The Go Programming Language Specification: go.dev/ref/spec.
- Dennis M. Ritchie and Ken Thompson, "The UNIX Time-Sharing System," Communications of the ACM 17(7), July 1974, section 3.3 "Special Files."
