The article's author, Douglas McIlroy, is an American mathematician, engineer, and programmer. He is best known for developing the pipeline in the Unix operating system, principles of component-oriented programming, and several original utilities: spell, diff, sort, join, speak, tr.
Sometimes you come across truly remarkable programs. Digging through my memory, I've compiled a list of genuine Unix gems over the years. For the most part, these are quite rare and not particularly necessary programs. But what sets them apart is their originality. I can't even imagine having come up with any of them myself.
Share which programs have amazed you as well?
PDP-7 Unix
To begin with, the PDP-7 Unix system itself. Its simplicity and power made me switch from a powerful mainframe to a tiny machine. Here lies the quintessence of a hierarchical file system, a distinct shell, and user-level process management, which Multics on mainframes couldn't achieve even after hundreds of person-years of development. The shortcomings of Unix (like record structure in the file system) were as enlightening and liberating as its innovations (like input-output redirection in the shell).
dc
The mathematical library for the desktop calculator with variable precision by Robert Morris used reverse error analysis to determine the precision needed at each step to achieve the user-specified accuracy of the result. At the NATO Software Engineering Conference in 1968, in my talk about software components, I proposed standard procedures that could yield results of any desired accuracy, but I didn't know how to implement them in practice. dc remains the only program I know capable of such.
typo
Typo organizes words in text based on their similarity to the surrounding text. Mistakes like 'hte' tend to appear at the end of the list. Robert Morris proudly stated that the program would work just as well for any language. Although typo doesn't help find phonetic errors, it has been a true find for anyone who types text and has provided much utility before the far less interesting but more accurate dictionary spell check came along.
Typo is as unexpectedly organized on the inside as it is on the outside. The similarity measurement algorithm is based on the frequency of trigrams, which are considered within a 26×26×26 array. In the tiny memory, there was barely enough space for single-byte counters, so a scheme was implemented to compress large numbers into small counters. To avoid overflow, the counters were updated on a probabilistic basis, maintaining a logarithmic estimate of the counter's value.
eqn
With the advent of eqn, it became possible, though terribly tedious, to produce classical mathematical notation. Lorinda Cherry decided to develop a higher-level description language, and soon Brian Kernighan joined her. Their brilliant move was to express the oral tradition in written form, making eqn surprisingly easy to learn. The first of its kind preprocessor for a language to describe mathematical expressions, eqn has seen little improvement since.
struct
Brenda Baker undertook the development of her Fortran-to-Ratfor converter against the advice of her boss — me. I thought it might lead to special reordering of the source text. It would be free from operator numbers but otherwise no more readable than well-structured Fortran code. Brenda proved me wrong. She found that every Fortran program has a canonically structured form. Programmers preferred the canonical form over what they originally wrote.
pascal
The syntax diagnostics in the compiler created by Sue Graham's group at Berkeley were the most useful I've ever seen — and they were conducted automatically. In the case of a syntax error, the compiler suggests inserting a lexeme to continue syntax analysis. No attempts to explain what went wrong. With this compiler, I learned Pascal in one evening, without having any reference guide at hand.
parts
The module hidden inside the WWB (Writer’s Workbench) package parts Lorinda Cherry identifies parts of speech for words in English text based solely on a small dictionary, spelling and grammar rules. Based on this annotation, the WWB program generates stylometric indicators of the text, such as the prevalence of adjectives, subordinate clauses, and complex sentences. When Lorinda interviewed on the Today show on NBC and talked about the innovative grammar-checking in WWB texts, it was the first mention of Unix on television.
egrep
Alfred Aho hoped that his deterministic regular expression recognizer would outpace Ken's classic nondeterministic recognizer. Unfortunately, the latter was already finishing its pass over complex regular expressions while egrep building his deterministic automaton. To win this race, Aho circumvented the curse of exponential growth in the automaton's state table by inventing a way to construct only the entries in the table that are actually visited during recognition.
crabs
Lucia Cardelli's charming meta-program for the Blit window system spawned virtual crabs that roamed the empty space of the screen, increasingly nibbling at the edges of active windows.
Some general thoughts
Although it isn't visible from the outside, theory and algorithms played a crucial role in the creation of most of these programs: typo, dc, struct, pascal, egrep. What is truly surprising is the unusual application of theory.
Almost half of the original authors of the list — pascal, struct, parts, eqn — were women, which significantly exceeds the demographic share of women in the field of computer science.
Douglas McIlroy
March 2020
Source: habr.com
