Ken Thompson Had grep Ready by the Next Morning. The Search Code Was Already Inside the ed Editor.

One afternoon at Bell Labs, by his own account, Doug McIlroy asked Ken Thompson whether he could lift the regular-expression recognizer out of the ed text editor and turn it into a program that read a file in one pass. “The next morning I found a note in my mail announcing a program named grep,” McIlroy later recalled. The first Unix manual page for grep is dated March 3, 1973.

Told quickly, the story sounds like a feat of overnight programming. The more useful part is what Thompson did not have to write. The search code already existed inside ed; grep was that code, set free from an editor that could not hold a large file.

A dictionary too big for ed

McIlroy’s request came out of his work on a program that read text aloud through a voice synthesizer. As he invented rules for pronouncing English spelling, he checked Webster’s dictionary for words where a rule might fail. The letter pair “ui,” for example, sounds different in “fruit,” “guile,” “guilty” and “anguish.”

The obstacle was ed itself. McIlroy had to break the dictionary into pieces that fit in ed’s limited buffer, then use ed’s global command to pull out lists of words and narrow them with repeated scans. In ed, the command g/re/p means: for every line that matches the regular expression re, print the line. Each time, ed copied a piece of the dictionary into a temporary file, scanned it twice and threw it away. McIlroy called the process tedious and “terribly wasteful.”

What Thompson did by the next morning

Thompson’s answer was to take the one ed command McIlroy kept running and make it a program of its own. McIlroy recalled that Thompson, when asked what the odd name grep meant, said it was obvious: the name stood for the editor command the program simulated, g/re/p, short for “global regular expression print.” The Fourth Edition Unix manual, the first to include grep, sums it up in a single line: “search a file for a pattern.”

Because grep makes one pass through its input instead of loading it into an editor’s buffer, the dictionary no longer had to be cut into pieces. If no file is named, grep reads standard input, so the output of another program can flow straight into it.

The matcher itself was not new. Thompson had already brought regular expressions into his version of the QED editor and described a matching method in a 1968 paper in Communications of the ACM, a journal of the Association for Computing Machinery. McIlroy’s 1987 history of Research Unix describes what Thompson did: “Thompson promptly liberated his regular expression recognizer and christened it after the ed command g/re/p.” In McIlroy’s telling, the job was to free existing code, not to invent new code.

There is a technical twist. According to the programmer Russ Cox, Thompson chose not to use his 1968 algorithm when he implemented ed, and ed and its descendant grep used recursive backtracking instead. A backtracking matcher tries one possible match and, if that match fails, backs up to try another. In Cox’s account, the first Unix tool to offer the full regular-expression syntax was Al Aho’s egrep, which appeared in the Seventh Edition in 1979 and matched with a precomputed automaton: a state machine built from the pattern before the search starts.

Two accounts of who asked for grep

Not every version of the story features McIlroy. In a 2018 interview with the YouTube channel Computerphile, Brian Kernighan, Thompson’s Bell Labs colleague, credited the request to Lee McMahon, who wanted to find every occurrence of a word in the Federalist Papers. At about a megabyte, the text was too big for ed. In Kernighan’s telling, McMahon asked Thompson, went home, and came back the next day to find that Thompson had written the program.

In McIlroy’s first-person account, published in the 1997 book Netizens, he puts himself and the dictionary at the center. His own 1987 history does not say who asked: it says grep was born when Thompson “was asked how to search for patterns in a file that was too big for the editor.” The sources do not settle who asked. Both versions agree on the essentials: a file too big for ed, and a working program by the next day.

How one ed command became a family of Unix tools

McIlroy’s 1987 history notes that grep is “generally cited as the prototypical software tool”: a small program that does one job on whatever text it is given. Al Aho, who wrote egrep, also added fgrep to the Seventh Edition; fgrep searches for fixed strings rather than regular expressions. The name grep spread beyond Unix too. In 2016, McIlroy described grep as “a euphonious coinage so useful that it made its way into the OED [Oxford English Dictionary] as both noun and verb.”

Why freeing the code mattered more than writing it fast

The design choice that lasted was not a clever algorithm. It was the decision to stop treating search as something an editor does to a file it holds, and to make search a single pass over a stream of lines. The same recognizer that was cramped inside ed became more useful outside it.

When a feature is trapped inside a larger program, the fix can be to take it out rather than to write it again. More than 50 years later, every developer who types grep is spelling out, minus the slashes, the ed command McIlroy once ran on a dictionary cut into pieces: g/re/p.

Explore

Stay connected