Автор статьи Дуглас Макилрой — американский математик, инженер и программист. Наиболее известен разработкой конвейера в операционной системе Unix, принципов компонентно-ориентированного программирования и нескольких оригинальных утилит: spell, diff, sort, join, speak, tr.
Иногда вам попадаются действительно замечательные программы. Покопавшись в памяти, я составил список настоящих жемчужин Unix за все годы. В основном, это довольно редкие и не такие уж необходимые программы. Но что их выделяет, так это оригинальность. Даже представить не могу, чтобы мне самому пришла идея какой-нибудь из них.
Поделитесь, какие программы вас тоже настолько поразили?
Для начала, сама система PDP-7 Unix. Её простота и мощь заставили меня перейти с мощного мейнфрейма на крошечную машину. Здесь квинтэссенция иерархической файловой системы, отдельная оболочка и управление процессами на уровне пользователя, что Multics на мейнфреймах не смогла реализовать после сотен человеко-лет разработки. Недостатки Unix (например, структура записей в файловой системе) были столь же поучительными и освобождающими, как и её новшества (например, перенаправление ввода-вывода в оболочке).
Математическая библиотека для настольного калькулятора c переменной точностью Роберта Морриса использовала обратный анализ ошибок для определения точности, необходимой на каждом шаге для достижения заданной пользователем точности результата. На конференции НАТО по программной инженерии 1968 года в своём докладе о программных компонентах я предложил эталонные процедуры, которые могут дать результат любой желаемой точности, но я не знал, как их реализовать на практике. dc до сих пор остаётся единственной известной мне программой, способной на такое.
Typo упорядочивает слова в тексте по их сходству с остальным текстом. Очепятки вроде 'hte' имеют тенденцию располагаться в конце списка. Роберт Моррис с гордостью говорил, что программа будет одинаково хорошо работать для любого языка. Хотя typo не помогает найти фонетические ошибки, она стала настоящей находкой для всех, кто набирает текст, и принесла много пользы до того, как появилась гораздо менее интересная, но более точная проверка орфографии по словарю.
Typo настолько же неожиданно устроена внутри, как и снаружи. Алгоритм измерения сходства основан на частоте появления триграмм, которые считаются в массиве 26×26×26. В крошечной памяти едва хватало места для однобайтовых счётчиков, поэтому была реализована схема сжатия больших чисел в маленькие счётчики. Чтобы избежать переполнения, счётчики обновлялись на вероятностной основе, поддерживая оценку логарифма значения счётчика.
С появлением фотонабора стало возможным, но ужасно утомительно выводить классическую математическую нотацию. Лоринда Черри решила разработать язык описания более высокого уровня, и вскоре к ней присоединился Брайан Керниган. Их блестящий ход состоял в том, чтобы выразить устную традицию в письменном виде, поэтому eqn оказался удивительно простым в изучении. Первый в своём роде препроцессор языка описания математических выражений, eqn с тех пор почти не улучшался.
Бренда Бейкер затеяла разработку своего конвертера Fortan-to-Ratfor вопреки совету своего начальника — меня. Я подумал, что это может привести к специальному переупорядочиванию исходного текста. Он будет свободен от номеров операторов, но в остальном не более читаемый, чем грамотно структурированный код Fortran. Бренда доказала, что я ошибаюсь. Она обнаружила, что у каждой программы Fortran есть канонически структурированная форма. Программисты предпочитали каноническую форму, а не то, что сами изначально написали.
Диагностика синтаксиса в компиляторе, созданном группой Сью Грэхем в Беркли, была самой полезной из всех, что я когда-либо видел — и она проводилась автоматически. При синтаксической ошибке компилятор предлагает вставить лексему, чтобы продолжить синтаксический анализ. Никаких попыток объяснить, что не так. С этим компилятором я выучил Паскаль за один вечер, не имея под рукой никакого руководства.
Спрятанный внутри пакета WWB (Writer's Workbench) модуль
Аль Ахо рассчитывал, что его детерминированный распознаватель регулярных выражений обгонит классический недетерминированный распознаватель Кена. К сожалению, последний уже завершал проход по сложным регулярным выражениям, пока
Очаровательная мета-программа Луки Карделли для оконной системы Blit выпускала виртуальных крабов, которые бродили по пустому пространству экрана, всё больше и больше откусывая края активных окон.
Хотя это не видно извне, но теория и алгоритмы сыграли решающую роль в создании большинства этих программ: typo, dc, struct, pascal, egrep. На самом деле больше всего удивляет именно необычное применение теории.
Оригинальными авторами почти половины списка — pascal, struct, parts, eqn — были женщины, что значительно превосходит демографическую долю женщин в области компьютерных наук.
Дуглас Макилрой
Март, 2020
Иногда вам попадаются действительно замечательные программы. Покопавшись в памяти, я составил список настоящих жемчужин 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
