Дональд Кнут, мастер алгоритмов, размышляет над 50 годами работы над своим главным творением, книгой «Искусство программирования», которую не прекращает дополнять

Дональд Кнут в своём доме в Стэнфорде, Калифорния. Жуткий перфекционист, назначил награду за нахождение ошибки в своих книгах.

Уже полвека стэнфордский специалист по информатике Дональд Кнут, немного напоминающий Йоду – хотя ростом он 193 см и носит очки – занимает доминирующее положение духовного учителя в области алгоритмов.

Он – автор «Искусства программирования», монографии, которую до сих пор продолжает писать, дойдя до 4 тома, и которая является трудом всей его жизни. Первый том вышел в 1968 году, а все тома вместе (продающиеся в наборе по $250 [или 12500 ? / прим. перев.]) в 2013 году попали в список книг, сформировавших прошедшее столетие науки, составленный журналом American Scientist. В него также входят специальное издание «Автобиографии Чарльза Дарвина», книга Тома Вулфа "Парни что надо!", книга Рейчел Карсон "Безмолвная весна", и монографии Альберта Эйнштейна, Джона фон Неймана и Ричарда Фейнмана.

«Искусство программирования», напечатанное тиражом более миллиона экземпляров, является библией в своей области. «Она похожа на настоящую Библию – она очень длинная и всеобъемлющая; других таких всеобъемлющих книг нет», — говорит Питер Норвиг, директор по исследованиям в Google. Спустя 652 страницы том закрывается цитатой на задней обложке книги, принадлежащей Биллу Гейтсу: «Если вы можете прочесть всю книгу, высылайте мне своё резюме».

Открывается том отрывком из «Сборника рецептов Маккола»:

Вот вам книга, опубликовать которую вы просили в тысячах ваших писем. У нас ушли годы на проверку и перепроверку бессчётного количества рецептов, с тем, чтобы предоставить вам только самое лучшее, интересное, идеальное.

В книжке перечислены алгоритмы, рецепты, питающие цифровую эпоху – хотя, как любит указывать доктор Кнут, алгоритмы можно найти и на вавилонских табличках возрастом 3800 лет. Он глубоко уважаемый алгоритмист; его именем названы некоторые из самых важных образчиков, например, алгоритм Кнута — Морриса — Пратта для поиска вхождения подстроки в строку. Он был придуман в 1970 и находит все вхождения заданной последовательности букв в тексте – к примеру, когда вы нажимаете Ctrl-F, чтобы поискать слово в документе.

Сейчас доктору Кнуту 80, и он обычно одевается так, как одевался, будучи молодым гиком, когда он только начинал эту одиссею: футболка с длинными рукавами поддета под футболку с короткими рукавами и джинсы – по крайней мере, в это время года. В те дни он писал программы в машинном коде, игрался с нулями и единицами.

«Кнут ясно дал понять, что систему можно понять по всей глубине, вплоть до уровня машинных кодов», — сказал доктор Норвиг. Сегодня, когда алгоритмы управляют (и вмешиваются) в нашу жизнь, у среднего программиста нет времени копаться с двоичной кашей, он работает с иерархиями абстракции, с наслоениями кода – и часто с цепочками кода, позаимствованного из библиотек. Но элита программистов иногда опускается на самые низкие уровни.

«В Google мы иногда просто собираем код из того, что есть», — сказал Норвиг во время встречи команды Google Trips в Маунтин-Вью. «А иногда, когда нужно обслужить миллиарды пользователей, это нужно сделать эффективно. 10% улучшение эффективности может обернуться миллиардами долларов, и чтобы достичь этого последнего уровня эффективности, надо понимать, что происходит до самого основания».


Доктор Кнут в Калифорнийском технологическом, где он получил докторскую степень в 1963 году.

Или, как объяснил Андрей Бродер, известный учёный, работающий в Google, и один из бывших учеников Кнута, во время встречи: «Нам нужен некий теоретический базис нашей работы. Нам не нужны несерьёзные, неуклюжие, второсортные алгоритмы. Мы не хотим, чтобы другие алгоритмисты сказали: „Да вы, ребята, идиоты“».

Приложение Google Trips, созданное в 2016, это алгоритм для туристов, размечающий развлечения для туристов на целый день. Команда работала над "максимизацией качества худшего из дней" – к примеру, алгоритм должен избегать того, чтобы отправлять пользователя несколько раз по одним и тем же местам для изучения разных достопримечательностей. Они вдохновлялись алгоритмом 300-летней давности, придуманным швейцарским [а также немецким и российским] математиком Леонардом Эйлером, который захотел нарисовать путь, проходящий через прусский город Кёнигсберг [ныне — Калининград], пересекавший все его семь мостов только по одному разу. Кнут обращается к классической проблеме Эйлера в первом томе своего трактата. Однажды он применил метод Эйлера для программирования швейной машины с компьютерным управлением.


Следование доктрине Кнута помогает избежать идиотизма. Он известен тем, что ввёл понятие «литературного программирования», подчёркивая важность написания кода, который могут читать не только компьютеры, но и люди – понятие, сегодня кажущееся чем-то старомодным. Кнут даже утверждал, что некоторые компьютерные программы можно считать литературными произведениями, наряду с поэмами Элизабет Бишоп и романом «Американская пастораль» Филипа Рота достойными пулитцеровской премии.

А ещё он печально известен своим перфекционизмом. Рэндал Манро, автор карикатур xkcd и «Объяснялки» [Thing Explainer], впервые узнал о Кнуте от программистов, упоминавших награду, которую тот обещал выплатить любому человеку, нашедшему ошибку в любой из его книг. Как вспоминает Монро, «люди говорили о получении такого чека, как будто это была нобелевка по информатике».

Требовательные стандарты Кнута, как литературные, так и остальные, могут объяснить, почему работа всей его жизни далека от завершения. Он поспорил с Сергеем Брином, сооснователем Google и бывшим его учеником, закончит ли Брин свою докторскую до того, как Кнут закончит свою монографию.

Рассвет алгоритма

В 19 лет Кнут опубликовал свою первую работу на техническую тему, "Потрецибная система мер и весов" в журнале Mad [Это был юмористический журнал, а потрециби – польское слово, использующееся в английском для обозначения несуразицы. К примеру, в своей работе Кнут ввёл новую меру длины в один потрециби, равную толщине 26-го номера журнала / прим. перев.]. Он стал специалистом по информатике ещё до появления информатики, изучая математику в учебном заведении, которая теперь называется Кейсовский университет Западного резервного района. Он изучал избранные программы, написанные для школьного мейнфрейма IBM 650, десятичного компьютера, и, встретив неточности, переписывал их и учебник, использовавшийся в классе. В качестве хобби он подсчитывал статистические показатели для баскетбольной команды, и написал программу, которая помогла им выиграть в своей лиге, благодаря чему известный тележурналист Уолтер Кронкайт даже снял о нём телевизионный сюжет под названием «Электронный тренер».


Во время летних каникул Кнут зарабатывал больше денег, чем его преподаватели за год, создавая компиляторы. Компилятор похож на транслятор, он превращает язык программирования высокого уровня (напоминающий алгебру) в язык низкого уровня (иногда это таинственный двоичный код), и, в идеале, улучшает программу в процессе. В информатике оптимизация представляет собой искусство, что отражается в ещё одной поговорке Кнута: «Преждевременная оптимизация – это корень всех зол».

В итоге Кнут сам стал компилятором, случайно обнаружив новую область, которую потом назвал «анализ алгоритмов». Издатель нанял его для написания книги о компиляторах, но проект вылился в книгу, собирающую всё, что он знал по поводу того, как писать программы для компьютеров – в книгу об алгоритмах.


Кнут в 1981 году, изучает номер журнала Mad от 1957 года, где напечатана его первая техническая статья.


«Искусство программирования», тома 1-4.

«К моменту наступления Ренессанса, по поводу возникновения этого слова уже имелись сомнения, — начинается книга. – Ранние лингвисты пытались понять его происхождение, создавая такие комбинации, как algiros [болезненный] + arithmos [число]». На самом деле, продолжает Кнут, это название появилось в честь персидского автора учебника IX века, Абу Абдуллах Мухаммад ибн Муса аль-Хорезми, имя которого в латинской записи стало звучать, как «Алгоритм». Кнут, который никогда не довольствовался полумерами, отправился в 1979 году в паломничество на родину аль-Хорезми, в Узбекистан [точнее, принял участие в конференции в г. Ургенч / прим. перев.].

С самого начала Кнут хотел написать одну книгу. Вскоре в информатике случился Большой взрыв, поэтому он переработал свой проект, разбив его на семь томов. Теперь он выпускает под-тома, или выпуски. Следующий «Том 4, выпуск 5», где, среди прочего, описываются такие вещи, как «бектрекинг» и «танцующие ссылки», должен был выйти ещё в 2018-м. Однако он задержался до апреля, поскольку автор постоянно находит всё новые и новые задачи, которые он обязательно хочет представить.

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

Обычно Кнут встречался со студентами по пятницам с утра, пока не начал проводить вечера в лаборатории Джона Маккарти, одного из пионеров разработки в области искусственного интеллекта, чтобы получить доступ к компьютерам, когда они были свободны. Испугавшись того, как дорогая его сердцу книга стала выглядеть после появления цифровых издательских систем, Кнут поставил себе целью разработать компьютерную систему типографского набора TeX, остающуюся золотым стандартом для всех форм научных коммуникаций и публикаций. Некоторые считают её величайшим вкладом Кнута, и величайшим вкладом в типографию со времён Гутенберга.

Эта десятилетняя отсрочка случилась в то время, когда компьютерами пользовались разные люди, и когда они работали быстрее ночью, когда большинство людей спят. Поэтому Кнут переключился на ночной образ жизни, сдвинул график на 12 часов, и поменял время встреч со студентами на период с 8 до 12 ночи в пятницу. Бродер вспоминает: «Когда я сказал своей девушке, что мы не сможем ничем заняться в пятницу вечером, потому что в 10 вечера у меня назначена встреча с моим научным руководителем, она подумала: „Это настолько глупо звучит, что, видимо, является правдой“».

Однако, когда Кнут решает поприсутствовать где-то лично, он всё своё внимание отдаёт этому мероприятию. «Быть рядом с ним – это удовольствие», — говорит Дженнифер Чейс, управляющий директор Microsoft Research. «Он как максимум в сообществе. Если бы у вас была функция оптимизации, представлявшая собой теплоту и глубину, то это был бы Дон».


Кнут обсуждает шрифты с Германом Цапфом, разработчиком шрифтов.

Воскресенье с алгоритмистом

Кнут живёт в Стэнфорде и встречается с людьми по воскресеньям. То, что он выделил для встречи целый день, было исключительным – обычно он недоступен во время дневного сна, представляющего собой священный ритуал, проходящий с 13 до 16 часов. Он начал свой день рано, в Первой лютеранской церкви Пало-Альто, где дал урок для воскресной школы перед толпой людей, собравшихся в комнате без стульев. По дороге домой он начинает философствовать о математике.

«Я никогда не буду знать всего, — сказал он. – Моя жизнь была бы куда хуже, если бы не было вопросов, на которые я бы знал ответы, и если бы не было вопросов, на которые я бы не знал ответы». Затем он предложил провести экскурсию по «современному калифорнийскому» дому, который они с женой построили в 1970. Его офис забит стопками флэшек и украшен поделками Джил, графического дизайнера, на тему дня святого Валентина. Наибольшее впечатление производит музыкальная комната, построенная вокруг изготовленного на заказ органа на 812 труб. Закончился день на вечеринке с пивом и загадками.

Загадки, игры, написание романа о сюрреальных числах, сочинение 90-минутной мультимедийной музыкальной композиции Fantasia Apocalyptica – такие вещи его заводят. Один из разделов его книги называется «Загадки против реального мира». Выдержку из книги он отправил команде, состоящей из отца и сына, Мартину Демейну, художнику, и Эрику Демейну, специалисту по информатике, работающим в MIT, поскольку Кнут включил в книгу их "алгоритмические шрифты-головоломки".

«Я был приятно удивлён, — сказал Эрик Демейн. — Попасть в эту книгу – это честь». Он упомянул ещё одну цитату Кнута, вдохновляющую проходящую два раза в год конференцию "Развлечения с алгоритмами": «Главной целью, вероятно, всегда было удовольствие».

А потом, сказал Демейн, эта область превратилась в практическую. Инженеры, учёные, художники – все они объединяются для решения реальных задач, типа свёртывания белка, робототехники, подушек безопасности, используя разработанные двумя Демейнами оригами, способы сложения бумаги и связывания её в различные формы.

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

Программисты всё ещё тренируют машины, и скармливают им данные. Данные – это новая область для появления ошибок и предвзятостей, причём тут их сложнее отловить и исправить. Однако, как сказал Кевин Славин, доцент из Лаборатории медиа MIT: «Теперь мы пишем алгоритмы, которые не способны прочесть. Это отмечает уникальный исторический момент, когда мы работаем с идеями, действиями и попытками, вызванными физикой, происходящей от людей, но не понимаемой людьми». Славин часто замечает: «У вас намечается прекрасное будущее, если вы алгоритм».


Кнут за своим столом дома, 1999.


Заметки

И оно будет тем более прекрасным, если вы алгоритм, хорошо разбирающийся в Кнуте. «Сегодня программисты используют то, что Кнут и другие использовали как компоненты своих алгоритмов, и комбинируют это со всякими другими необходимыми им вещами», — сказал доктор Норвиг из Google.

«С ИИ у нас получается то же самое. Просто этап комбинирования происходит автоматически, на основе данных, а не на основе работы программиста. Нам нужно, чтобы ИИ мог комбинировать компоненты с целью получения подходящего ответа на основе данных. Однако вы должны решать, что это за компоненты. Может случиться так, что каждый из компонентов будет страницей или главой из Кнута, поскольку это будет наилучший способ выполнения какой-либо задачи».

Значит, нам повезло, что Кнут продолжает этим заниматься. Он думает, что у него должно уйти ещё 25 лет на то, чтобы закончить «Искусство программирования», хотя эта оценка не менялась с 1980-х. Получат ли алгоритмы, пишущие другие алгоритмы, свою главу в книге, или страничку в эпилоге? «Определённо нет», — сказал Кнут.

«Меня беспокоит то влияние, которое алгоритмы оказывают на мир, — добавил он. – Начиналось всё с того, что специалисты по информатике беспокоились, потому что их никто не слушал. Теперь я беспокоюсь, что нас слушает слишком много народу».

?