Дональд Кнут, мастер алгоритмов, размышляет над 50 годами работы над своим главным творением, книгой «Искусство программирования», которую не прекращает дополнять
Дональд Кнут в своём доме в Стэнфорде, Калифорния. Жуткий перфекционист, назначил награду за нахождение ошибки в своих книгах.
Первый том вышел в 1968 году, а все тома вместе (продающиеся в наборе по $250 [или 12500 ₽ / прим. Уже полвека стэндфордский специалист по информатике Дональд Кнут, немного напоминающий Йоду – хотя ростом он 193 см и носит очки – занимает доминирующее положение духовного учителя в области алгоритмов.
Он – автор «Искусства программирования», монографии, которую до сих пор продолжает писать, дойдя до 4 тома, и которая является трудом всей его жизни. В него также входят специальное издание «Автобиографии Чарльза Дарвина», книга Тома Вулфа "Парни что надо!", книга Рейчел Карсон "Безмолвная весна", и монографии Альберта Эйнштейна, Джона фон Неймана и Ричарда Фейнмана. перев.]) в 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 [число]». «К моменту наступления Ренессанса, по поводу возникновения этого слова уже имелись сомнения, — начинается книга. Кнут, который никогда не довольствовался полумерами, отправился в 1979 году в паломничество на родину аль-Хорезми, в Узбекистан. На самом деле, продолжает Кнут, это название появилось в честь персидского автора учебника IX века, Абу Абдуллах Мухаммад ибн Муса аль-Хорезми, имя которого в латинской записи стало звучать, как «Алгоритм».
Вскоре в информатике случился Большой взрыв, поэтому он переработал свой проект, разбив его на семь томов. С самого начала Кнут хотел написать одну книгу. Следующий «Том 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-х. Значит, нам повезло, что Кнут продолжает этим заниматься. «Определённо нет», — сказал Кнут. Получат ли алгоритмы, пишущие другие алгоритмы, свою главу в книге, или страничку в эпилоге?
– Начиналось всё с того, что специалисты по информатике беспокоились, потому что их никто не слушал. «Меня беспокоит то влияние, которое алгоритмы оказывают на мир, — добавил он. Теперь я беспокоюсь, что нас слушает слишком много народу».
☃
