Автор статьи Дуглас Макилрой — американский математик, инженер и программист. Наиболее известен разработкой конвейера в операционной системе Unix, принципов компонентно-ориентированного программирования и нескольких оригинальных утилит: spell, diff, sort, join, speak, tr.

Иногда вам попадаются действительно замечательные программы. Покопавшись в памяти, я составил список настоящих жемчужин Unix за все годы. В основном, это довольно редкие и не такие уж необходимые программы. Но что их выделяет, так это оригинальность. Даже представить не могу, чтобы мне самому пришла идея какой-нибудь из них.

Поделитесь, какие программы вас тоже настолько поразили?

PDP-7 Unix

Для начала, сама система PDP-7 Unix. Её простота и мощь заставили меня перейти с мощного мейнфрейма на крошечную машину. Здесь квинтэссенция иерархической файловой системы, отдельная оболочка и управление процессами на уровне пользователя, что Multics на мейнфреймах не смогла реализовать после сотен человеко-лет разработки. Недостатки Unix (например, структура записей в файловой системе) были столь же поучительными и освобождающими, как и её новшества (например, перенаправление ввода-вывода в оболочке).

dc

Математическая библиотека для настольного калькулятора c переменной точностью Роберта Морриса использовала обратный анализ ошибок для определения точности, необходимой на каждом шаге для достижения заданной пользователем точности результата. На конференции НАТО по программной инженерии 1968 года в своём докладе о программных компонентах я предложил эталонные процедуры, которые могут дать результат любой желаемой точности, но я не знал, как их реализовать на практике. dc до сих пор остаётся единственной известной мне программой, способной на такое.

typo

Typo упорядочивает слова в тексте по их сходству с остальным текстом. Очепятки вроде 'hte' имеют тенденцию располагаться в конце списка. Роберт Моррис с гордостью говорил, что программа будет одинаково хорошо работать для любого языка. Хотя typo не помогает найти фонетические ошибки, она стала настоящей находкой для всех, кто набирает текст, и принесла много пользы до того, как появилась гораздо менее интересная, но более точная проверка орфографии по словарю.

Typo настолько же неожиданно устроена внутри, как и снаружи. Алгоритм измерения сходства основан на частоте появления триграмм, которые считаются в массиве 26?26?26. В крошечной памяти едва хватало места для однобайтовых счётчиков, поэтому была реализована схема сжатия больших чисел в маленькие счётчики. Чтобы избежать переполнения, счётчики обновлялись на вероятностной основе, поддерживая оценку логарифма значения счётчика.

eqn

С появлением фотонабора стало возможным, но ужасно утомительно выводить классическую математическую нотацию. Лоринда Черри решила разработать язык описания более высокого уровня, и вскоре к ней присоединился Брайан Керниган. Их блестящий ход состоял в том, чтобы выразить устную традицию в письменном виде, поэтому eqn оказался удивительно простым в изучении. Первый в своём роде препроцессор языка описания математических выражений, eqn с тех пор почти не улучшался.

struct

Бренда Бейкер затеяла разработку своего конвертера Fortan-to-Ratfor вопреки совету своего начальника — меня. Я подумал, что это может привести к специальному переупорядочиванию исходного текста. Он будет свободен от номеров операторов, но в остальном не более читаемый, чем грамотно структурированный код Fortran. Бренда доказала, что я ошибаюсь. Она обнаружила, что у каждой программы Fortran есть канонически структурированная форма. Программисты предпочитали каноническую форму, а не то, что сами изначально написали.

pascal

Диагностика синтаксиса в компиляторе, созданном группой Сью Грэхем в Беркли, была самой полезной из всех, что я когда-либо видел — и она проводилась автоматически. При синтаксической ошибке компилятор предлагает вставить лексему, чтобы продолжить синтаксический анализ. Никаких попыток объяснить, что не так. С этим компилятором я выучил Паскаль за один вечер, не имея под рукой никакого руководства.

parts

Спрятанный внутри пакета WWB (Writer's Workbench) модуль parts Лоринды Черри определяет части речи для слов в тексте на английском языке на базе только маленького словаря, правилах орфографии и грамматики. По этой аннотации программа WWB выводит стилометрические показатели текста, такие как преобладание прилагательных, придаточных предложений и сложных предложений. Когда Лоринда дала интервью в телепередаче Today на канале NBC и рассказала об инновационной проверке грамматики в текстах WWB, это было первое упоминание Unix на телевидении.

egrep

Аль Ахо рассчитывал, что его детерминированный распознаватель регулярных выражений обгонит классический недетерминированный распознаватель Кена. К сожалению, последний уже завершал проход по сложным регулярным выражениям, пока egrep строил свою детерминированную автоматику. Чтобы всё-таки победить в этой гонке, Аль Ахо обошёл проклятие экспоненциального роста таблицы состояний автомата, изобретя способ построения на лету только тех записей таблицы, которые действительно посещаются во время распознавания.

crabs

Очаровательная мета-программа Луки Карделли для оконной системы Blit выпускала виртуальных крабов, которые бродили по пустому пространству экрана, всё больше и больше откусывая края активных окон.

Некоторые общие мысли

Хотя это не видно извне, но теория и алгоритмы сыграли решающую роль в создании большинства этих программ: typo, dc, struct, pascal, egrep. На самом деле больше всего удивляет именно необычное применение теории.

Оригинальными авторами почти половины списка — pascal, struct, parts, eqn — были женщины, что значительно превосходит демографическую долю женщин в области компьютерных наук.

Дуглас Макилрой
Март, 2020