Из всех героев этой книги Дональд Кнут, пожалуй, меньше всех нуждается в представлении. На протяжении последних 40 лет он пишет свой многотомный шедевр «Искусство программирования» — библию фундаментальных алгоритмов и структур данных. Журнал «American Scientist» включил эту работу в список 12 самых важных естественнонаучных исследований века наряду с произведениями Рассела, Уайтхеда, Эйнштейна, Дирака, Фейнмана и фон Неймана. Кнут популяризировал применение асимптотической нотации («О» большое) при анализе алгоритмов, изобрел LR-анализатор и защищал операторы перехода GOTO от критики Эдсгера Дейкстры.

Но он не просто теоретик. Закончив третий том «Искусства программирования» в 1976 году, Кнут взял перерыв на год, как он тогда думал, собираясь написать системы компьютерной верстки ТеХ и METAFONT, для того чтобы его книги были напечатаны так, как он хотел. Через десять лет он закончил этот проект, попутно изобрел новый стиль программирования — «литературное программирование» — и алгоритм для разбиения абзацев текста на строки, который и по сей день применяется в программах компьютерной верстки.

Среди его многочисленных наград — первая премия имени Грейс Мюррей Хоппер от Ассоциации вычислительной техники (1971), премия Тьюринга (1974) и Национальная научная медаль США (1979). В 1990 году он перестал пользоваться электронной почтой, объясняя это тем, что его работа заключается не в том, чтобы быть «на самом верху», а в том, чтобы быть «в самом низу», — именно там можно глубже понимать и затем объяснять в книгах многие области компьютерных наук.

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

Сейбел: Когда вы научились программировать?

Кнут: Во время учебы на первом курсе в Технологическом институте Кейса. Осенью 1956 года — в течение четверти или семестра — в институте появился компьютер.

Сейбел: IBM 650?

Кнут: Да, это была модель 650. Первая модель, которую IBM выпустила партией больше 100 штук. Наверное, количество проданных компьютеров тогда исчислялось тысячами, вряд ли десятками тысяч. Так или иначе, это был первый компьютер массового производства — и он появился даже в институте Кейса.

Я работал тогда в лаборатории статистики и занимался там сортировкой карт. Я сводил статистические данные в таблицы, зарабатывая этим хоть какую-то прибавку к стипендии. В окне первого этажа был виден стоящий в кабинете компьютер с мигающими лампочками. Зрелище завораживало.

Как-то раз один сотрудник лаборатории, встав к доске, объяснил мне и еще паре моих друзей-первокурсников, как работает эта машина. Я нашел руководство пользователя для этого компьютера — в нем были примеры программ строк по десять. Мне они показались глуповатыми — видимо, даже эти небольшие программки можно было улучшить.

Позже выяснилось, что ночью можно пойти и поработать на компьютере. Это было необычно. Думаю, только в университете Дартмута и Кейсовском институте первокурсникам позволялось дотрагиваться до компьютеров. В других университетах были профессиональные операторы, которым приносишь пачку перфокарт и на утро получаешь у них ответ. Но в Кейсе нас подпускали к компьютерам. Только предупреждали: «Смотри, осторожнее вот с этим; не нужно делать вот этого — в компьютере от этого произойдет сбой». В общем, нам выпал прекрасный шанс поработать с этим компьютером.

Так или иначе, я проверил, сработает ли одна из моих небольших поправок к одной из программ — и она сработала. Я подумал: «Боже мой, это поразительно. Я всего лишь первокурсник, а у меня уже получается лучше, чем написано в этой книге, — наверное, у меня к этому талант». В итоге оказалось, что у меня действительно к этому были способности, но не в том смысле, в каком я думал, ведь ту конкретную программу практически кто угодно мог написать лучше, чем в том конкретном руководстве.

Это была десятичная машина, поэтому работать было проще, ведь мне не пришлось учить двоичную арифметику, хотя в старших классах я в принципе немного занимался ею. Тем не менее из-за того что машина была десятичной, работать на ней было немного проще, удобнее. До сих пор помню тот машинный язык, например sixty-five is reset-add-lower (сейчас он помогает мне придумывать пароли и прочее).

Сейбел: Ого, кажется, вы только что выдали свой секрет.

Кнут: Да, точно. Затем я решил написать небольшую программу для разложения числа на простые множители. В программе было около 100 строк. Я приходил по ночам, когда машина была не занята, и занимался отладкой. В моей 100-строчной программе я нашел больше 100 ошибок. Но две недели спустя у меня была готова программа, с помощью которой можно было вычислить простые множители любого десятизначного числа, набранного с помощью переключателей консоли.

Так я и учился программировать — брал собственную программу и сидел за компьютером неделями, пытаясь сделать ее чуточку лучше.

Моя вторая программа переводила двоичный код в десятичный. А третьей была программа для игры в крестики-нолики — именно после нее я стал настоящим программистом.

Тогда мне пришлось использовать структуры данных. Я сделал три версии игры в крестики-нолики, одна из которых была основана на самообучении программы: она начинала играть, ничего не зная об игре, и затем запоминала после каждого проигрыша свои ходы как сомнительные, а ходы соперника как удачные, а после этого соответственно повышала рейтинг одних позиций и уменьшала рейтинг других. После 400 игр она была уже достаточно приемлемым игроком в крестики-нолики.

Сейбел: Похоже, многие из тех, с кем я беседовал, имели непосредственный доступ к компьютерам в самом начале своей карьеры. Тем не менее у Дейкстры есть работа — уверен, вы с ней знакомы, — в которой он прямо говорит, что студентов компьютерных специальностей первые несколько лет обучения не следует допускать к работе за компьютером — все это время они должны учиться работать с символами.

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

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

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

Кнут: Иногда я сам не уверен, что понимаю их. Я пытаюсь изложить множество умных мыслей по поводу темы того или иного раздела — я нахожу их в различных источниках, где они высказаны частично, и объединяю в некое целое, которое уже может быть использовано в дальнейшем, в котором история передана верно, где исправлены ошибки и двусмысленности, присутствовавшие в оригинале.

Взять, к примеру, главы, которые я пишу сейчас: работа начинается с обработки материала, взятого из математических журналов и написанного на собственном жаргоне, который большинство программистов, как мне кажется, даже и не подумают учить. Поэтому я пытаюсь адаптировать эти тексты до такой степени, чтобы хотя бы самому их понимать. Я пытаюсь излагать ключевые идеи так просто, как могу, но в итоге получается, что за каждыми пятью страницами моей книги — чья-то карьера.

Другими словами, любой вопрос, раскрытый в моей книге на пяти страницах, этими пятью страницами далеко не исчерпывается — его изучению можно посвятить всю жизнь, потому что компьютерные науки — действительно очень богатая область. Компьютерные науки вовсе не сводятся к ряду простых вещей. Если бы компьютерные науки действительно были очень просты и все свелось бы лишь к тому, чтобы сформулировать 50 правильных вещей и выучить их, тогда, да, тогда бы я сказал: «Да, каждый человек в мире должен знать эти 50 вещей — и должен знать их хорошенько».

Но это не так. В моих книгах — тысячи страниц и тысячи примеров, которые я записываю и включаю в книги, для того чтобы не держать их все в голове. Мне приходится постоянно возвращаться к ним и изучать их заново. В моих книгах есть ответы ко всем заданиям, так как я знаю, что десять лет спустя я не буду помнить ничего о том, как делать ту или иную вещь, и мне придется потратить много времени на то, чтобы восстановить утраченные знания. Поэтому я оставляю для себя хотя бы минимальные подсказки на будущее.

Я постоянно разрываюсь между мыслью «Ну, это слишком сложно — не стоит об этом говорить совсем» и ощущением, что те, кто прочтет книгу, скажут: «Все, о чем вы пишете, очевидно. От ваших книг никакой пользы». В любой отдельно взятый момент меня можно застать за спором с самим собой — выкинуть ли мне все или набрать еще материала, поскольку имеющегося недостаточно.

В итоге же все сводится к тому, что все по-настоящему интересное, что можно изложить на половине страницы моей книги, должно занимать полстраницы. Также должны быть включены все вещи, которые слишком хороши, чтобы их не включить. Я тут выяснил, что в раздел о двоичных диаграммах решений, который я только что написал, включено больше 260 заданий — по ходу дела у меня набиралось все больше и больше материала не для широкой аудитории. Не все из этих 260 заданий будут интересны абсолютно всем. Тем не менее я уверен, что многие оценят по достоинству каждое из этих заданий в отдельности.

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

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

Я не включаю в свои книги исследования, где, например, фигурирует структура данных, в которой множитель log log n экономится только при n больше двух миллионных. Подобных исследований великое множество. Их авторы фантазируют о том, что, в принципе, если бы компьютеры были богоподобны, то у нас были бы более быстрые алгоритмы. Но даже алгоритмы вроде сбалансированного дерева или AVL-дерева я не использую в своих программах, не будучи твердо уверен в том, что это будет действительно большое дерево.

Сейбел: А что вы используете?

Кнут: Обыкновенное дерево двоичного поиска, которое с недавнего времени стал особым образом рандомизировать.

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

Кнут: Когда в 1977-1978 годах я написал первую версию ТеХ, у меня, разумеется, еще не было литературного программирования, но уже было структурное программирование. Я писал в большом блокноте, без сокращений, карандашом.

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

Это была система первого поколения, поэтому можно было использовать разные архитектуры, которые следовало отбросить, пока я не пожил с ней достаточно долго и не понял что к чему. Это была своего рода вечная проблема — нельзя было набирать текст без шрифтов, но нельзя было создать шрифты, не имея возможности набирать текст.

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

Сейбел: И на экономию времени вы рассчитывали, поскольку вам не пришлось бы писать вспомогательный код и модули для тестирования, чтобы протестировать незаконченный код?

Кнут: Именно.

Сейбел: Помимо того что ваши книги так хорошо набраны, как по-вашему, они бы сильно изменились, если бы вы не потратили десять лет на создание ТеХ?

Кнут: Хороший вопрос. Использование структурного программирования не в чисто академических целях — другими словами, я думаю об инвариантах не только в пробных, но и в реальных программах, — возможно, повлияло на то, как я сейчас описываю алгоритмы в своих новых книгах. А если не повлияло, то должно было.

Я бы ничего не узнал о кэшировании и о тенденциях изменений в компьютерной индустрии, и о других подобных вещах, если бы просто шел по накатанной дорожке — черпая знания для своих книг из уже написанных трудов. Пока я писал первые три тома, я не создавал программ, подобных ТеХ, написание которых более характерно для активной программистской деятельности. Я же писал пробные программы. Таким образом, я получал некое представление о числах и величинах.

На самом деле, это потрясающе — осознавать во время процесса написания книги те вещи, которые заставляют тебя использовать то или иное слово. Это поистине тайна — как это все происходит. Это наиболее важное влияние, которое оказал на меня опыт создания ТеХ, — я по-другому стал относиться к вещам, и я стал писать по-иному, по-иному составлять предложения — они стали менее громоздкими. У всей книги появилась какая-то новая интонация — уверенности или еще чего-то.

Сейбел: То есть к моменту завершения ТеХ вы были уже значительно лучшим программистом, чем когда начинали его создавать?

Кнут: Да, потому что я стал применять методы литературного программирования.

Сейбел: Понятно, у вас появились более качественные инструменты, но улучшились ли непосредственно ваши навыки?

Кнут: Я узнал очень много нового, пока работал над этим проектом. В частности узнал, как много ресурсов вашего мозга съедает разработка ПО. Это оказалось намного более сложным заданием, чем я ожидал. Я не мог одновременно преподавать на полную ставку и полноценно заниматься разработкой ПО. Но я мог преподавать на полную ставку и полноценно заниматься написанием книг; ПО же требовало невероятного внимания к мельчайшим деталям. Мой мозг был забит только программным обеспечением, так что я не мог думать ни о чем другом. Поэтому я стал с особым уважением относиться к тем, кто работает в крупных проектах по разработке ПО; я бы никогда не узнал, как они работают, если бы сам не занимался схожей работой.

Сейбел: То есть, по-вашему, программировать сложнее, чем писать книги; где-то я читал ваше мнение, согласно которому невозможно сказать, сколько времени займет написание той или иной книги. Значит ли это, что сказать, сколько времени займет написание одной программы, еще сложнее?

Кнут: Да, это так. Это очень верный вывод.

В этом году я написал три крупные программы с помощью методов литературного программирования, код каждой из которых занимает больше 100 страниц формата А4. Две из них взаимосвязаны, так что это скорее две с половиной программы. И еще около 150 небольших программ. Пожалуй, за предыдущий год мне удалось сделать меньше. То есть я очень плотно занимался в этом году созданием небольших программ, но некоторые из них я писал по месяцу или дольше.

Сейбел: И вы с самого начала могли сказать, что будете писать их месяц?

Кнут: Что касается одной из них — да, я ожидал, что на ее создание уйдет месяц. Я знал, что это будет непростое задание, но не мог предположить, насколько у нее богатый потенциал, — я даже добавил несколько дополнительных свойств по ходу ее использования. Я считаю, что это абсолютная истина, которую должен усвоить каждый руководитель отдела разработки: сроки написания программы нельзя спрогнозировать.

Сейбел: Помимо того что вы написали «Искусство программирования» и ТеХ, вы изобрели и всячески продвигали литературное программирование — способ программирования, при котором код гораздо легче прочитать неспециалисту. Вы написали WEB и CWEB, инструменты реализации языков литературного программирования на базе Паскаля и Си.

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

Сейбел: Так, может, объясните, почему вы так любите литературное программирование и чем оно отличается от нелитературного программирования?

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

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

Или можно сказать: «Допустим, что а, равное тому-то и тому-то, — это множество главных элементов». Таким образом, разговорный термин множество главных элементов дополняется математическим описанием того, как мы создали множество а.

То есть в основе литературного программирования лежит идея, что лучший способ передачи сообщения — совмещение формального и неформального способов. Такой подход обеспечивает естественную основу для переключения между естественным языком — английским — и формальным языком — Си, Лиспом или любым другим языком программирования — и их совмещения. Как мне кажется, такой метод облегчает работу с документацией.

И еще: когда я пишу программу, мне не нужно предоставлять ее в той форме, в какой ее хочет видеть компилятор. Я предоставляю ее в форме, по моему мнению, наиболее доступной для читателя.

Кто-то пишет код снизу вверх, создавая подпрограммы, дающие все более крупные и крупные объекты, и становясь все более уверенным в себе, поскольку теперь может сделать гораздо больше. Другие пишут сверху вниз; они начинают писать и думают: «Так, у меня есть задача, которую нужно решить, — сначала я сделаю вот это, а потом — вот это».

Если я пишу литературную программу, то могу выбирать между этими способами. И практически всегда в итоге моя программа создается в том порядке, в каком я ее сам продумал. То есть, начиная работу, я думаю: «Ага, у меня есть задача, которую нужно решить, то есть сначала мне нужно решить вот это, а потом я решу вон то».

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

И я начинаю заниматься тем, что в данный момент волнует меня больше всего, но и тем, что я готов решить в данный момент. Не откладывая этого дела в долгий ящик — если я готов выполнить его прямо сейчас, то прямо сейчас его и делаю. Но это уже совсем другой порядок — ни снизу вверх, ни сверху вниз. Это психологический момент: «Мне нужна задача, выполнение которой принесло бы мне сейчас наибольшее удовольствие и к выполнению которой я сейчас готов». В этом уравнении не так уж много неизвестных. Таким образом, мне очень важно то, что я без всяких проблем могу создавать программу в подобном человечески понятном порядке.

Так почему же эта идея не получила широкого распространения по всему миру? Почему все не делают так? Я сейчас точно не вспомню, кто абсолютно верно сформулировал объяснение — кажется, это был Джон Бентли. В упрощенной форме мысль звучит примерно так: лишь два процента населения земного шара рождены, чтобы стать гениальными программистами. И лишь два процента населения земного шара рождены, чтобы стать гениальными писателями. А Кнут хочет, чтобы абсолютно все были и теми, и другими.

Мне не кажется, что нам удастся увеличить общее количество программистов в мире — оно не будет превышать двух процентов. Я имею в виду программистов, которые действительно понимают машину, которые были рождены для этого занятия, для кого это дело всей жизни. С другой стороны, сейчас, с появлением блогов, мне совершенно очевидно повышение общей способности выражать свои мысли. Таким образом, вторая часть мысли Бентли сейчас не так уж верна.

Я лишь немного занимался этим в Стэнфордском университете с группой студентов. Они писали программы в качестве летнего проекта, и я познакомил их с идеей литературного программирования. В то лето у меня была группа лишь из семи человек. Шестерым из них эта идея настолько понравилась, что они применяют ее до сих пор. Седьмой ее ненавидел. Его представление о литературной программе было следующим: он брал обычную программу, сверху создавал надстройку и говорил: «Это модуль номер один», — и так далее. Конечно, в Стэнфорд принимают тех, кто умеет хорошо писать, то есть это не вполне репрезентативный пример.

Сейбел: Вам когда-нибудь приходилось писать литературную программу, которую вы коренным образом перестраивали, чтобы объяснить ее? Просто мне трудно представить, что поток сознания всегда является наилучшим принципом организации материала.

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

Сейбел: Пишете ли вы литературный код для программ, которые никто кроме вас никогда не увидит?

Кнут: Конечно. Именно этим литературное программирование и хорошо — я могу разговаривать с самим собой. Я могу прочитать программу год спустя и точно понять, о чем я тогда думал.

Сейбел: Всегда ли этот метод работает?

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

Я недавно распечатал небольшой комплект больших коллекций подпрограмм, написанных на Си, которые в общем-то отражают текущее состояние дел в работе с булевыми схемами решений (BDD). Это полная противоположность CWEB; практически все во всем мире разрабатывают пакеты программ именно так. Делается это с помощью достаточно упорядоченных соглашений по комментированию, которые понимаются широким сообществом. И код не так уж труден для понимания, поскольку он логически разделен, в нем есть заголовочные файлы, и вы можете видеть структуры данных, и к каждой части структуры данных даны комментарии, поясняющие тот или иной момент. Это еще один вполне эффективный стиль программирования.

Тем не менее я уверен в том, что этот метод далеко не столь эффективен, как литературное программирование, в силу множества неосязаемых вещей, которые я не могу доказать. Наиболее убедительным аргументом для меня является моя уверенность в том, что некоторые из написанных мною программ я никогда бы не смог написать без методов литературного программирования. Например, создание эмулятора MMIX стало бы для меня такой чудовищной головоломкой, что если бы мне пришлось работать над ним с помощью обычного метода, то не думаю, что мне удалось бы его завершить. Обычного разделения его на подпрограммы было недостаточно для того, чтобы упростить его, сделав удобным для восприятия и работы с ним.

Этот эмулятор учитывает наиболее общим образом спецификацию компьютера: какими функциональными блоками он обладает, сколько инструкций может выполнять одновременно, каковы его стратегии кэширования, как работает шина и устройство вывода, каким образом производится прогнозирование ветвления и как работает конвейер.

Вы можете придумать компьютер с шестью блоками деления и конвейером, состоящим из определенного количества стадий, и сэмулировать его. Будете ли вы быстрее вычислять простые числа с таким компьютером? Вам не нужно создавать такой компьютер.

Я не утверждаю, что невозможно взять эту программу и разбить ее на подпрограммы, но я бы никогда не смог ее выполнить подобным образом. Кроме того, код занимает всего 170 страниц, и он понятен — я не единственный в мире человек, который его понимает.

Сейбел: Я читал повторную реализацию игры Adventure, осуществленную вами с помощью методов литературного программирования; она мне показалась слегка монолитной. Это было похоже на стиль литературного программирования, поскольку тут вы можете интерполировать объекты и совсем не думать о том, чтобы разбить ее на подпрограммы.

Кнут: Верно. Вместо того чтобы вызывать подпрограмму, мы как будто имеем встроенные подпрограммы на протяжении всей программы. Идея подпрограммы по-прежнему используется, но в итоговом варианте вашей программы подпрограмм нет. Это больше походит на макросы. Но суть в том, что на уровне понятий механизм вызова подпрограмм не нужен, если у вас есть иной способ реализации этой функции на языке, который вы используете.

Что касается Adventure, то не думаю, что я на самом деле убрал подпрограммы из программы Дона Вудса, написанной на Фортране, — я взял его программу на Фортране и переписал ее на английском и на Си. Но абсолютно верно то, что если вы взглянете на мой код ТеХ, то увидите, что подпрограмм в стеке около 4-5, тогда как в программе, написанной кем-либо другим — без применения методов литературного программирования, — их может быть и 50, и 100.

Я пытаюсь работать с блоками, которые соотносятся с моим мыслительным процессом, а не подчиняюсь каким-то логическим принципам работы с формальной системой. Я хочу, чтобы мои программы соответствовали моему интуитивному процессу их создания, а не чьей-либо жестко закрепленной схеме.

Естественно, в конечном счете она должна быть перенесена на компьютер, у которого есть жесткие рамки, четкие правила понимания. Но в моем представлении хорошая и правильная программа должна наиболее точно передавать образ моих мыслей, а не принцип работы компьютера. Мне нужно найти способ перехода из одного состояния в другое, но я стремлюсь сохранять исходные тексты ближе к своей голове, чем к компьютеру.

Кроме того, я убежден, что литературное программирование — это очень эффективный способ ведения документации, обеспечивающий связь между группами людей. Многие люди понимали код ТеХ настолько хорошо, что могли создавать сценарии, при которых в программе происходил сбой. Мне кажется, что еще больше людей в какой-то из моментов своей жизни понимали именно эту программу, а не любую другую программу схожего размера.

Сейбел: И тем не менее сталкивались ли вы когда-нибудь с такими ситуациями, в которых люди читали ваш код и все равно задавали вам вопросы, заставлявшие вас думать: «Неужели они действительно тут что-то не поняли?»

Кнут: Конечно. Такое происходит постоянно, но лишь из-за недостаточно высокого качества моих объяснений. Позвольте привести простой пример. В «Искусстве программирования» я пишу о первых применениях побитовых операций, и у меня есть такое предложение: «Компьютер Manchester Mark 1, созданный примерно в то же время, что и EDSAC, использовал не только побитовые операторы И, но также ИЛИ и исключающее ИЛИ. В его первом руководстве программиста, написанном в 1950 году, Алан Тьюринг отмечал, что побитовый оператор НЕ может быть получен с помощью исключающего ИЛИ или в сочетании с несколькими подобными операторами».

То есть во фразе «В его первом руководстве программиста Алан Тьюринг...» речь идет о первом руководстве программиста для компьютера Manchester Mark 1. Но четверо или пятеро человек, прочитавших это предложение, независимо друг от друга заявили, что поняли фразу в том смысле, что в 1950 году Алан Тьюринг написал свое первое руководство программиста.

На самом деле у него были и другие руководства по программированию, поэтому я написал все правильно, но фраза была неправильно истолкована людьми. Поэтому я исправил ее следующим образом: «В первом руководстве по программированию для компьютера Mark I, написанном в 1950 году, Алан Тьюринг отмечал...»

То же касается и чисто математических моментов — ко мне обращаются люди, которые их не понимают. Поэтому я скажу так: как правило, я все пишу верно, но знаю, что мне тем не менее нужно эти моменты исправлять и улучшать.

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

Кнут: Нет. Хорошая литературная программа всегда покажет свою историю. Хорошая литературная программа всегда скажет: «Вот очевидный способ выполнения данной задачи — почему бы нам им не воспользоваться?»

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

Я использую запрещенные приемы по двум причинам. Во-первых, если это действительно повысит производительность моей программы и если это повышение производительности действительно необходимо. Или иногда я думаю: «Это решение кажется не совсем чистым. Не могу сегодня ничего с собой поделать — хочется использовать этот запрещенный прием, потому что это так клево». То есть чисто для своего удовольствия. В любом случае я все это документирую, а не просто использую в программе и все.

Сейбел: То есть это чаще встречается не в коде, а в тексте?

Кнут: Да, речь о текстовой части. Я не показываю код, который исключил из программы. Хотя мог бы.

Сейбел: Есть ли в CWEB возможность включать код, не являющийся частью приложения? Тогда можно не документировать этот момент, а просто делать комментарий: «Это действительно очень простая версия данной функции».

Кнут: У вас просто есть код, который не используется. Он упоминается в документации с пометкой, что этот код нигде не используется.

Сейбел: То есть на этот фрагмент вы просто нигде не ссылаетесь?

Кнут: Да. Кроме того, у меня есть код, который я могу вызвать из отладчика. Я могу сказать: «Нужно вызвать то-то и то-то с такими-то и такими-то параметрами». Подпрограмма никогда не вызывается непосредственно из самой программы, но она всегда есть в документации. Поэтому я могу остановить выполнение программы посередине, вызвать эту подпрограмму — она осмотрится, как идут дела, как все обстоит на более масштабном уровне.

Сейбел: И точно таким же образом вы можете написать: «Раздел первый — это простейшая реализация данного алгоритма; раздел второй — слегка модифицированная версия первого раздела; раздел третий — вот его мы действительно используем, но вы его никогда не поймете, если не прочтете первые два раздела».

Кнут: Именно. У меня есть несколько программ в Интернете, которые решают головоломку «15». И я использую 3 разные версии. Я говорю: «Прочитайте версию номер один, иначе вы никогда не поймете версию номера два. И прочитайте версию номер два, иначе вы никогда не поймете версию номер три».

Мне приходилось писать самые разные программы. Иногда я работаю над программой, для которой производительность — последнее дело; важно лишь получить ответ. В таком случае я применяю метод грубой силы — тогда мне совсем не нужно думать, поскольку не требуется придумывать никаких тонких решений, и я точно не перемудрю. При таких обстоятельствах ни о какой преждевременной оптимизации не может быть и речи.

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

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

Комбинаторные алгоритмы — это потрясающая вещь, поскольку одна хорошая идея может в десятки раз сократить время работы программы. Но я вовсе без всякого высокомерия отношусь к идеям, с помощью которых можно сэкономить и 20%, если программа выполняется триллион раз. Потому что, сэкономив сотню наносекунд в цикле, который исполняется триллион раз, думаю, вы экономите целый день. Если код будет использоваться действительно часто, то будет совсем не лишним придумывать различные тонкие ходы, которые не так-то легко сразу понять.

Около года назад я прочитал обзор в журнале «Computing Reviews» — рецензент писал о книге под названием «Programming Tricks» (Уловки в программировании) или что-то вроде того. Суть рецензии сводилась к следующему: «Если бы я узнал, что кто-то из программистов, работающих на меня, применяет эти штучки, я бы их уволил». Естественно, я начал искать эту книгу, подумав: «Именно такая книга мне и нужна — в ней я могу узнать для себя много нового». К сожалению, уловки не были такими уж хорошими.

Сейбел: Они что, действительно причиняли вред?

Кнут: Вообще-то, это были очень слабые и неэффективные уловки. Они не были систематизированы и все такое, но самое главное — они были достаточно очевидны. Это была совершенно иная культура. Что же касается рецензента, который собирался увольнять своих сотрудников, — он хочет, чтобы в программировании все делалось неэффективно, но вписывалось бы в его идею аккуратности. Его абсолютно не интересует, хороша программа или нет — если брать в расчет скорость исполнения и производительность; он думает лишь о том, чтобы она соответствовала другим критериям, — например, чтобы ее поддержку мог осуществлять абсолютно любой человек. Что ж, у многих вообще очень странные взгляды на действительность.

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

Проблема в том, что программирование становится совсем не интересным и не привлекательным занятием, если можешь лишь вызывать что-то из библиотеки, но не можешь написать библиотеку сам. Если бы работа программиста заключалась в том, чтобы находить правильное сочетание параметров для выполнения достаточно очевидных вещей, то кто бы захотел выбрать себе такую профессию?

Существует некое излишнее возвеличивание ПО многократного использования, когда вовсе не нужно открывать ящик и смотреть, что же находится внутри. Всегда приятно иметь черные ящики, но — практически всегда — если можешь заглянуть внутрь ящика, то можешь улучшить его работу, как только узнаешь, что же находится внутри.

Люди же, наоборот, все засовывают в упаковку, которую не открыть, и преподносят эту закрытую упаковку программистам, и всем программистам во всем мире не разрешается вскрывать эту упаковку. Они только и могут что соединять одно с другим. И поэтому приходится помнить, что, вызывая вот эту подпрограмму, нужно ввести х0, у0, х1, у1, а при вызове другой подпрограммы нужно ввести х0, х1, у0, у1. Все выполняется строго по инструкции — и это ваша работа.

Сейбел: Многие с вами согласятся, что, да, интереснее писать код самому. Но помимо увлекательности есть еще и...

Кнут: Дело не только в том, что это интересно. Работа математика заключается в том, чтобы писать доказательства, но практически никогда не бывает так, что в процессе решения математической задачи вы можете найти теорему, чьи гипотезы абсолютно идеально подходят для вашего случая. Практически всегда вы работаете с тем, что более или менее похоже на классическую теорему из учебника. Поэтому, что вы делаете? Читаете доказательство этой теоремы и думаете: «Ага, вот как мне нужно изменить это доказательство, чтобы доказать гипотезу, которой я занимаюсь». То есть в математических книгах полно теорем, но вы никогда не берете всю теорему от начала до конца — вам нужно увидеть ее доказательство, потому что лишь в одном случае из ста вы сможете найти теорему, которая идеально подходит для вашей задачи. Думаю, примерно так же дело обстоит и с ПО.

Сейбел: И тем не менее, не является ли ПО — по-моему, вы сами же об этом и говорили — самой сложной вещью, когда-либо созданной человеком?

Кнут: По-моему, Дейкстра сказал это первым, но, вообще, да, все верно. Все дело в том, что сложность соединения разных вещей далеко не однородна. В чистой математике стремятся к тому, чтобы выработать небольшое количество правил, которые можно было бы применять ко всем явлениям — 3-4 аксиомы для описания целой системы. В компьютерной же программе множество частей: шаг 1 не похож на шаг 2, а тот, в свою очередь, не похож на шаг 3. Вам нужно соединить все эти вещи и организовать весьма нетривиальным способом.

Сейбел: Таким образом, учитывая сложность, получается, что в какой-то момент нужно взять ряд черных ящиков и сказать: «Ага, мы знаем, как эта штука работает, и можем ею пользоваться». Если бы нам пришлось заглядывать внутрь каждого черного ящика, мы бы никогда не смогли ничего довести до конца.

Кнут: Я не говорю, что черные ящики бесполезны. Я говорю лишь о том, что если мне не разрешается их открывать и если мне нужно выполнить определенное задание, располагая лишь библиотекой из чего-то подобного, то я получу гораздо более низкие результаты — и все будет происходить намного медленнее.

Сейбел: Медленнее — вы имеете в виду работу программы или ее разработку?

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

Сейбел: Какое-то время назад программист, писавший стандартные библиотеки Java, написал статью о том, как в их реализации двоичного поиска на протяжении девяти лет была ошибка. То есть они взяли минимум и максимум, сложили их и разделили на два. Но, естественно, если операция сложения переполняется, то это ошибка. В общем, конечно, плохо то, что в стандартной библиотеке была ошибка, но в итоге они нашли ее и устранили. Если бы все сами писали двоичный поиск, то ошибочных двоичных поисков, наверное, было бы больше.

Кнут: Это так. И это лишь один пример из огромного множества. Двоичный поиск — это конкретный пример того, с чего мы начинали наши занятия по программированию в 1970-х. В первый день учебы все писали программы двоичного поиска и сдавали нам, после чего ассистенты их изучали. В результате работали меньше 10% программ. И находилось около 4-6 различных ошибок. Но ни одна из них не имела никакого отношения к переполнению, которое вы упомянули; это новая ошибка — на моих занятиях мы не считали сложение этих двух чисел проблемой.

Вернемся к идее черного ящика. Вы можете спросить, почему же она мне так ненавистна? Мы говорим об арифметических операциях, поэтому предположим, что у нас есть программа для перемножения матриц. У нас есть черный ящик для перемножения матриц, затем мы меняем тип данных — с действительного на комплексный; и теперь у нас есть черный ящик для перемножения комплексных матриц, работа которого занимает 4я3 шагов, а не п3 шагов. Если работа программы с действительным типом данных занимает определенное время t, то работа программы с комплексным типом данных занимает время 4t. Но если вы можете заглянуть внутрь ящика, то вам понадобится лишь 3 операции перемножения матриц с действительным типом данных, а не 4, поскольку у нас есть тождество, которое описывает результат перемножения двух комплексных матриц. Это лишь небольшой пример; их список можно продолжать до бесконечности.

У меня есть очередь с приоритетами или структура вроде кучи; что бы там ни было — двоичный поиск — у меня будет хороший источник для алгоритма, но он будет не до конца соответствовать моим целям, поэтому я каждый раз буду его адаптировать. И мне кажется, что так лучше для меня. Я знаю, что со мной не согласятся многие, кто считает, что их работа — писать программы, которые все будут использовать; поэтому если в них находятся ошибки, они их исправляют, и программы всех других людей также станут работать лучше. Хорошо. Мне не нравится такой подход к делу. И я хочу увидеть их программы.

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

Столкнувшись с задачей, не связанной с массивами, вы обращались к имеющимся пакетам программ или к интерпретируемому языку, вроде IPL-V или Лиспа. Также были версии на Фортране, и вы могли взять эти подпрограммы, разобраться, как ими пользоваться, и создавать в нем собственную программу. Считалось совершенным абсурдом учить обыкновенного программиста использовать связные списки в собственных программах. Считалось, что все должно делаться с помощью этих наработанных процедур.

Но тогда в обычных пакетах должны были быть представлены все дополнительные инструменты, необходимые лишь для решения каких-то узких задач, встававших перед небольшим количеством пользователей. Поэтому моя книга в общем-то открыла людям глаза: «Боже, я могу это понять и адаптировать таким образом, что смогу разместить элементы в двух списках одновременно. Я могу менять структуру данных». Эта практика стала повсеместно доступной, а не закрытой для употребления лишь в рамках этих пакетов.

То же самое я вижу и сейчас, работая над структурами BDD. На данный момент есть 3-4 пакета подпрограмм, работающих с BDD, но я пишу сейчас в «Искусстве программирования» — если вкратце, — что вы тоже можете писать простые версии BDD для множества приложений, которые будут весьма эффективны. Вы можете использовать их для самых разных задач, в которых вам не нужны все эти прибамбасы других пакетов; и те вещи, которые вы теперь можете делать, легки для понимания и для использования в программах, которые вы пишете сами.

В этом году я закончил раздел, посвященный уловкам и приемам работы с побитовыми операциями, а эти вещи долго считались черной магией среди компьютерных специалистов. Я решил: пора сказать о том, что у этих приемов есть и теоретический аспект, благодаря которому можно понять эти идеи и то, как они используются. Вы можете абсолютно уверенно использовать их сами. Кроме того, вы можете создавать программы и делать удивительные вещи, о которых в прошлом году не имели особого представления. До нынешнего времени все это было в глубоком подполье, но этому мы также должны учить людей — это знание заслуживает того, чтобы быть доступным всем.

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

Сейбел: Как изменились ваши взгляды на программирование с того времени, когда вы только начинали им заниматься?

Кнут: Мы уже обсудили с вами литературное программирование; это само по себе коренное изменение в понимании своей функции: не просто расстановка в нужном порядке инструкций, а объяснение того, что происходит. Дейкстра прошел ту же эволюцию. В конце концов, его программы были даже более литературными, чем мои, — в том смысле, что они даже не добрались до компьютера. Они были просто литературными.

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

Это очень важный момент — необходимость осознания абстрактных понятий, позволяющих нам работать с крупными системами, не теряя уверенности в том, что у нас все под контролем, что мы знаем, что делаем, несмотря на то, что эти понятия чертовски сложны.

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

Для меня одной из самых главных революций в языках программирования стало использование указателей в языке Си. Если у вас есть необычные структуры данных, то нередко появляется необходимость в том, чтобы одна часть структуры указывала на другую часть, и люди пробовали по-разному реализовать эту функцию в языках более высокого уровня. Например, Тони Хоар разработал ясную четкую систему, но язык Си привнес следующее (что сначала показалось мне большой ошибкой, но в конце концов я это полюбил): если х — это указатель, и вы пишете х+1, это означает не следующий байт после х, а следующий узел после х в зависимости от того, на что указывает х: если он указывает на большой узел, то х+1 пройдет большой путь; если х указывает на что-то маленькое, то и х+1 продвинется немного. Для меня это одно из самых потрясающих усовершенствований нотации.

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

Кнут: Указатели уже настолько вышли из моды, что мне приходится вступать по этому поводу в споры. Если говорить о моем 64-разрядном компьютере, то, если действительно заботиться о производительности моего компьютера, мне приходится признать, что лучше отказаться от использования указателей, поскольку на моей машине 64-битные регистры, но всего 2 гигабайта оперативной памяти. Поэтому у указателя никогда не бывает больше 32 значащих битов. Но каждый раз, когда я использую указатель, это стоит мне 64 бита, и это удваивает размер моей структуры данных. Более того, это еще идет и в кэш-память, и половины кэш-памяти как не бывало, а за это приходится платить — кэшпамять дорогая.

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

Сейбел: Есть ли в вашем программистском арсенале другие важные инструменты?

Кнут: Файлы изменений — их я придумал после того, как уже стал использовать методы литературного программирования, и я не знаю их аналогов в инструментариях других программистов, поэтому позвольте объяснить их вам.

Когда я написал ТеХ и METAFONT, люди стали просить их у меня. У всех этих людей было 200-300 различных комбинаций языков программирования, операционных систем и компьютеров, поэтому я хотел сделать так, чтобы мой код с легкостью можно было адаптировать к любой системе. И мы разработали такое решение: я пишу главную программу, которая работает в Стэнфордском университете, после чего создается дополнение — файл изменений (change file), который может адаптировать эту главную программу для работы на чьем угодно компьютере.

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

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

Эту систему можно написать за час, и она достаточно хорошо справляется со своей задачей. После чего все инструменты, которые есть в нашем распоряжении для литературного программирования — программы «сплетания» и «спутывания», — будут работать с главным файлом и файлом изменений.

Поэтому мне время от времени приходится выпускать новую главную программу. У сотен людей по всему миру есть свои файлы изменений — возможно, их шесть строк, которые должны совпасть с моими, уже не совпадают, поэтому им нужно внести ряд изменений. Но им не приходится делать слишком много. Каждый раз, когда я исправляю ошибку, программа практически сразу заработает — исправление ошибки также отражается и на работе их программ. То есть проблема была решена очень просто, и все сработало. Любой может это понять и сделать.

Примером крайности в этой области может служить случай, имевший место, когда ТеХ адаптировался для работы с Unicode. У них был файл изменений раз в десять больше главной программы. Другими словами, из 8-битной программы они сделали 16-битную, но вместо того чтобы пройтись и переделать мою главную программу, они были настолько увлечены файлами изменений, что просто написали свои файлы изменений и назвали это Omega, — миллион строк файлов изменений для 20 000 строк кода ТеХ. Это крайность.

Но сейчас я постоянно использую файлы изменений, потому что пишу для себя программы, которые использую в своей книге, — есть множество задач, в которых я бы хотел разобраться, и мне бы хотелось поэкспериментировать с различными версиями. Например, вчера я захотел выяснить, насколько большой является булева схема для перемножения n-битных чисел. То есть у меня есть программа, которая берет любую булевскую функцию и вычисляет ее BDD.

В моей исходной программе нужно ввести таблицу истинности функции в процессе работы; она говорит: «Введите таблицу истинности», — и я ввожу шестнадцатеричное число, потому что у меня есть множество небольших функций, которые я использую в качестве примеров. Но это работает только для небольших функций, которые я хочу ввести в таблицу истинности.

Есть и крупная функция, например «Перемножить все пары 8-битных чисел». Эта функция от 16 переменных — 8 бит в л: и 8 бит в у. Поэтому я пишу небольшой файл изменений, который убирает этот интерактивный диалог и заменяет его программой, составляющей таблицу истинности для умножения.

Затем я заменил это фразами вроде «Прочтем биты справа налево, а не слева направо — получится другая BDD» или «Попробуем все булевы функции от шести переменных, просмотрим их все и выясним, у которой из них наибольшая BDD». Но это все лишь вариации моей исходной программы.

У меня наберется около 15 вариантов этой программы, и все они абсолютно доступны. Это было неожиданным ответвлением от литературного программирования, возникшим из-за того, что нам надо было посылать главные файлы множеству людей, которые изменяли их для своих систем. Сейчас я использую его совершенно по-другому.

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

Кнут: Да, я пишу книгу.

Сейбел: Как по-вашему, этот механизм может получить более широкое применение?

Кнут: Не знаю. Не предполагаю, как бы все это происходило, работай я в команде из 50 человек. Но надеюсь, что программист-одиночка, пишущий программы, чтобы чему-то научиться, не вымирающий вид.

Сейбел: В начале карьеры вы занимались машинным кодом, затем перешли на структурное программирование, которое предоставило — логичным образом — структуру для ваших программ. Затем вы изобрели литературное программирование, с помощью которого стали структурировать программы по-новому. Появилось ли с момента изобретения литературного программирования еще что-то, столь же кардинально изменившее ваши взгляды на программирование?

Кнут: У меня теперь есть более эффективные инструменты для отладки в рамках литературного программирования — вот, по большому счету, и все.

Сейбел: Хорошо, давайте поговорим об отладке. Что это за более эффективные инструменты, которые вы сейчас используете?

Кнут: Как оказалось, изобретатели отладчика GNU поняли, что препроцессоры можно использовать для написания программ. То есть можно устанавливать соотношение между низкоуровневыми объектами и высокоуровневыми источниками в совершенно разных языках. Другими словами, я могу писать на CWEB, но никогда не смотреть на низкоуровневые вещи, потому что они отобразятся в моем CWEB-источнике по мере моего продвижения по программе.

Сейбел: То есть речь идет о средстве, встроенном в GDB, которое используется CWEB?

Кнут: И оно было встроено в GDB, потому что оно было встроено в Си, для того чтобы заполучить директивы__LINE__. Нам пришлось поработать, для того чтобы использовать директивы__LINE__, но теперь все работает превосходно. У компьютера есть только двоичная инструкция, но GDB знает, что это было получено из моего исходного WEB-файла, несмотря на то что WEB появился через 10 или 20 лет после Си. Следовательно, с их стороны было очень хорошим, дальновидным решением выполнить эту работу.

Сейбел: То есть вы используете GDB. Какие еще инструменты отладки вы применяете?

Кнут: Я добавляю много кода, проверяющего качество исполнения моих структур данных, со всеми их повторами. Эта проверка достоверности, когда она включена, может замедлить выполнение программы на два порядка.

Например, у меня была сложная структура данных, в которой использовался подсчет ссылок. Я пишу довольно сложные программы, и процесс подсчета ссылок усложняется. Время от времени мне приходится то увеличивать, то уменьшать счетчик ссылок. Но когда указатель находится в регистре или является параметром подпрограммы, считается это ссылкой в структуре данных или нет? Поэтому я пишу проверку, которая проходит через миллион счетчиков, проверяя, сколько ссылок действительно было сделано и все ли сходится. Затем я делаю небольшие вычисления и проверяю все целиком. Таким образом, ошибки будут обнаружены за миллиард шагов до того, как они проявят себя и все рухнет.

Была одна программа, которая выполняла умножение с помощью нового способа, и я усиленно ее тестировал. Я составил ряд из 256 чисел и перемножил каждое с каждым, а после каждого шага делал проверку. Умножаю 2 на 3 — сбой! Исправляю. Потом еще что-нибудь. В конце концов я добрался до того момента, когда все 256 правильно умножались друг на друга.

Это очень важная техника отладки для меня. Наверное, около 10% кода посвящено тому, что мне нужно только во время отладки. Кроме того, код проверки также документирует структуру данных.

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

Сейбел: Говоря об инвариантах и различных видах операторов утверждений, люди вроде Дейкстры говорят, что мы должны устанавливать очень формальные операторы утверждения на каждом этапе своих программ, чтобы в дальнейшем суметь доказать корректность этих программ. Я читал ваши рассуждения о том, что корректность программы нужно доказывать «неформально». Как вы думаете, стоит ли идти дальше и формально доказывать корректность программы?

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

Самая первая работа Тони Хоара про формальное доказательство называлась «Proof of a Program: FIND (Доказательство программы: FIND). Это было прекрасное научное исследование, которое весьма продвинуло общее положение дел в этой области. Но в этом доказательстве было 2-3 ошибки. Тогда людям не приходило в голову проверять, находится ли список индексов внутри границ или еще что-нибудь в этом духе. Всегда есть опасность появления пробелов. Тем не менее он осуществил гораздо более качественную и тщательную проверку, чем кто-либо до него.

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

Или взять, к примеру, ТеХ — с формальной точки зрения там полный бардак. Задумывалось, что эту программу будут использовать люди, а не компьютеры. Было бы абсолютно невозможно сформулировать, что значит корректность для ТеХ. Некоторые методы формальной семантики настолько сложны, что никто не может внятно определить понятие корректности.

Сейбел: Работая над ТеХ, вы написали совершенно зубодробительный тест для программы.

Кнут: Верно.

Сейбел: Каким образом вам удается так относиться к своим программам? Программисты зачастую хотят защитить свое дитя, поэтому они, как правило, стараются не очень усердно тестировать свои программы.

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

Например, одно из моих лучших профессиональных достижений во время работы в Burroughs Corporation было связано с деятельностью по обнаружению ошибок в устройстве их аппаратного обеспечения. Их инженеры показывали мне спецификации для своих компьютеров, а мне нужно было сконструировать примеры, при которых они бы ошибались на единицу или что-то вроде того. Я нашел свыше 200 ошибок в их компьютерах серии В-5000, прежде чем они поступили в производство, хотя перед этим они прошли тест на эмуляторах.

Сейбел: То есть, по сути, вы изобретали программы, которые были верны с точки зрения семантики языка, но машина исполняла их некорректно?

Кнут: Да. Конечно же, если у них плавающая запятая неправильно вычисляла произведение двух чисел, я пытался найти примеры чисел, когда плавающая запятая не работала. Кроме того, иногда они реализовывали стек аппаратно, и у них были ситуации, когда регистры были пусты или не на верху стека, и я пытался придумать сценарии, в которых их логика не работала.

Сейбел: Вы делали это по какой-то системе? Как вы находили все эти вещи?

Кнут: Может быть, я просто излишне придирчив? Не знаю. Но если я пытаюсь что-то доказать, например теорему, если речь о математике, а не доказать правоту чего-либо, то мне, как правило, проще сказать: «Давайте найдем контрпример». Я могу просто завестись, отыскивая дырку во всем этом или пытаясь объяснить, почему это не работает. Если же не могу найти никаких дырок, то вижу доказательство.

Думаю, все дело во мне — я люблю придираться и отыскивать ошибки. Мне гораздо интереснее, когда я выступаю против чего-либо, а не просто сижу и приговариваю: «Ага, да, это работает. Интересно, почему?»

Сейбел: Любопытно, что именно это движет вас вперед, хотя всю свою жизнь вы посвятили объяснению проблем. Не думаете ли вы, что такой подход подпитывает ваше стремление все объяснять?

Кнут: Единственное, что можно утверждать по поводу моих объяснений, — я пытаюсь совместить в естественном мыслительном процессе наблюдения за явлениями одновременно два разных способа, чтобы понять что-либо лучше. Думаю, чрезвычайно важно видеть вещи объемно, а не в одном измерении. Не знаю, как это связано с моей придирчивостью.

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

Сейбел: Еще один вывод, который вы вынесли из работы над ТеХ — вы об этом писали в «The Errors of ТеХ» (Ошибки ТеХ), — нужно фиксировать каждую ошибку, обнаруженную в программе. Ребята вроде сотрудников Института разработки ПО считают, что процесс разработки ПО можно назвать взвешенным и зрелым, если вы отслеживаете все ваши ошибки и пытаетесь понять, как предотвратить подобные ошибки в будущем. Но вы говорили о том, что ведение журнала ошибок никоим образом не помогает вам предотвращать появление ошибок в будущем.

Кнут: Верно. Хотя и не сказать, что без этого журнала ничего бы не изменилось в худшую сторону.

Сейбел: Но разве вы не думали: «Ага, теперь, когда я увидел эту ошибку, я ее больше не повторю»?

Кнут: Мне просто нужно узнать и признать свои грехи. Если использовать богословскую терминологию, то можно сказать, что все люди нуждаются в отпущении грехов.

Сейбел: То есть вы замечали ошибки в своих программах и думали про себя: «Ох, я снова сделал ту же самую ошибку».

Кнут: Да.

Сейбел: Почему же так? Может быть, дело в какой-то особой природе ошибок, что особенно затрудняет усвоение урока и недопущение подобных ошибок в будущем?

Кнут: Думаю, скорее всего, дело в том, что я пытаюсь заниматься все более сложными вещами. Я всегда пробую то, что требует от меня максимум усилий. Если бы мне нужно было сейчас вернуться и написать эти программы еще раз — те, которые полегче, — я бы не допустил так много ошибок. Но теперь, зная немного больше, я пытаюсь писать более сложные программы. То есть я совершаю ошибки, потому что всегда работаю на пределе своих способностей. Работать, никогда не покидая зоны комфорта, — это же скучно.

Сейбел: То есть теоретически вы могли бы продолжать писать системы для верстки текста до конца своей жизни?

Кнут: Да, они бы у меня выходили весьма неплохо. Но мы постоянно поднимаем для себя планку и неизбежно задеваем ее. Мы работаем с тем, как уже говорилось, что находится на пределе человеческих возможностей, и то, что мы делаем сейчас, еще сложнее того, с чем нам приходилось сталкиваться раньше.

Если же мы ограничиваем себя лишь тем, что действительно очень просто, то нам этого недостаточно, потому что наши аппетиты постоянно растут, мы всегда стремимся расширить границы своих возможностей, чтобы двигаться вперед, пока не доходим до того, что удается нам с величайшим трудом. А добравшись до этого момента, мы снова хотим расширить границы своих возможностей и так далее.

Таким образом, нам никуда не деться от ошибок, разве что мы откажемся писать программы, расширяющие наши способности. Так как же нам делать это лучше? Каждые три года появляется новое модное словечко для обозначения новой панацеи — той, что решит все проблемы и с чем все будет работать без сбоев.

Последние два-три года новой панацеей считалось экстремальное программирование. До этого было еще что-то. Потом еще кто-нибудь придумает очередное решение всех проблем, и многие вспрыгнут на подножку этого поезда, но потом им придется задуматься: «Черт, а ведь по-прежнему не все так уж легко».

Сейбел: Изменился ли со временем тип человека, который может стать хорошим программистом?

Кнут: Судя по моему многолетнему опыту, практически всегда, когда я встречаю 100 человек из той или иной группы населения (не считая студентов специальности «компьютерные науки»), двое из них — программисты, в том смысле что действительно находят общий язык с машиной. В городе Василла (Аляска) проживает 10 000 человек, соответственно там должно быть 200 программистов.

Сейбел: Так изменилось ли программирование за это время настолько, что изменился тип людей, попадающих в эти два процента? Или тут все по-прежнему?

Кнут: Не знаю, ведь понятие «программирование» можно трактовать по-разному. Мы всегда пытаемся создавать инструменты, благодаря которым компьютерные процессы как можно больше походили бы на то, что происходит в мозгу человека. Я скорее говорю о таком способе работы машины, когда она пытается раздвинуть горизонты, а не просто решить задачу.

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

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

Сейбел: Но вам ведь все еще интересно программировать самому?

Кнут: Разумеется, да. Мне просто необходимо программировать. Я просыпаюсь утром, и у меня уже готово несколько предложений литературной программы. Перед завтраком — уверен, поэтам это знакомо — я должен сесть за компьютер и записать этот абзац, и только потом могу идти есть, и я счастлив. Без этого я не могу, должен это признать.

Ладно, давайте я расскажу о программе, которую написал вчера. Я умножаю большие целые числа, которые значительно больше Вселенной; это особые целые числа — для работы их можно ужать, поэтому я могу с ними работать, несмотря на то, что не могу выразить их с помощью обычной нотации. Я умножал эти невероятно огромные целые числа, возводил их в квадрат и выяснял, как они выглядят после возведения в квадрат. Я пока мало понимаю, что там происходит, но мне это очень интересно.

Сейбел: Вы занимаетесь наукой, кроме того, участвовали в создании крупных систем и работали в промышленности. Какой вы видите связь между научными исследованиями в области компьютерных наук и их практическим применением в промышленности?

Кнут: Ситуация похожа на качели. В 1960-х наука сильно опережала промышленность, и программы, создаваемые в промышленных компаниях — кроме разве что системы заказа авиабилетов, — были абсолютно смехотворны для людей из университетов.

К 1980 году ситуация кардинальным образом изменилась: программы, написанные учеными, вызывали смех в промышленных компаниях, потому что наука ушла в теологию, и было запрещено использование операторов перехода GOTO. Я, конечно, утрирую — чтобы не усложнять, — но, по большому счету, в университетских программах были табу, которые связывали по рукам и ногам, а у тех, кто был занят в промышленности, ограничений не было.

Но затем люди в университетах придумали более эффективные идеи сетевых технологий и работы с крупными фрагментами данных и прочим — и вырвались вперед. То есть ситуация постоянно меняется. Но в области разработки алгоритмов и структур данных за последние годы наметилась тенденция, которая меня совсем не радует: создается множество структур данных, просто... вычурных - другого слова не могу подобрать. Они чрезвычайно сложны, умны и восхищают интеллектуальным размахом, но мне они кажутся бесплодными. Они не имеют никакого отношения к жизни, они работают в каком-то своем мире. Это нормальный мир, у него есть своя структура; это милые и дружелюбные люди, но их программы лично мне не нравятся, и они совершенно несовместимы с практикой.

Не знаю, почему мне так важно — совместимо что-либо с практикой или нет. Есть математики, которые вообще никогда не думают о чем-либо конечном и практически никогда не работают со счетно бесконечными множествами; они публикуют потрясающие работы, в которых говорят о безумных видах бесконечности, про которые они все понимают, и это доставляет им удовольствие. То же самое можно обнаружить и в области изучения алгоритмов. Что касается меня, то мне намного больше нравится работать с идеями, которые я могу использовать на своем компьютере.

Сейбел: В 1974 году вы писали о том, что к 1984 году у нас будет «Утопия 84» — идеальный язык программирования, который вытеснит Кобол и Фортран; кроме того, вы говорили о явных признаках того, что такой язык постепенно обретает реальные очертания. С 1984 года прошло уже два десятилетия — похоже, ваши прогнозы не сбылись.

Кнут: Нет, ничего такого не было.

Сейбел: Это в вас тогда говорил ваш юношеский оптимизм?

Кнут: Видимо, когда я писал об этом, то думал о Симуле и тенденциях в объектно-ориентированном программировании. Думаю, на самом деле с появлением каждого нового языка приводятся в порядок знания о старых языках и добавляется что-то новое, экспериментальное и так далее; но никогда не было так, что создается новый язык и все — дальше идти некуда, можно останавливаться на уже достигнутом. Всегда появляется желание развиваться дальше.

Может быть, когда-нибудь кто-то скажет: «Хватит, я не собираюсь быть новатором; я просто хочу быть внятным и понятным — этих принципов и буду придерживаться». Паскаль начинал с подобной философии, но не продолжил ее. Может, мы и доживем до того времени, когда кто-нибудь скажет: «Давайте-ка сузим наш угол зрения и постараемся сделать что-то стабильное». Возможно, это окажется неплохой идеей.

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

Кнут: Да, верно. Каким-то образом языки должны быть расширяемыми. Java не стала расширяемой в хорошем смысле этого слова.

Сейбел: Вы и сами создали несколько языков, пожалуй, самый популярный из них — ТеХ.

Кнут: Ну да, ТеХ — это язык программирования, но все эти дополнительные свойства я добавил после долгих споров и препираний. Гаю Стилу, Терри Винограду, Лесли Лэмпорту и другим были нужны определенные вещи, когда они использовали ТеХ в качестве внешнего интерфейса при работе над своим материалом. Кажется, Терри Виноград писал книгу о синтаксисе естественных языков, поэтому ему были нужны по-настоящему мощные макросы, чтобы сделать диаграммы для своей книги. Именно это подтолкнуло ТеХ по направлению к тому, чтобы превратиться в язык программирования уже в начале своего существования.

Сейбел: Вам когда-нибудь хотелось плотнее заняться разработкой языка как такового?

Кнут: Не знаю. Наверное, да. Мне по-своему очень не нравится, что считается, будто каждый язык должен быть универсальным, потому что они будут универсальными — но по-разному. Как в UNIX есть 30 определений регулярных выражений в одном флаконе — в зависимости от того, какую часть UNIX вы используете, вам предлагается немного отличное представление о регулярных выражениях. Если внутри каждого вашего инструмента находится машина Тьюринга — разве это нормально? Я на самом деле думал про ТеХ, что чем больше в нем языка программирования, тем меньше в нем того, что непосредственно связано с версткой.

Вводя расчет простых чисел в руководство по использованию ТеХ, я не считал это должным использованием ТеХ. Я представлял себе это так: «Да, кстати, глядите-ка: собаки могут стоять на задних лапах, а ТеХ может вычислять простые числа».

Сейбел: Но люди пользуются тем, что это тьюринг-полный язык программирования для вычислений, связанных с версткой. Если бы он не обладал полнотой по Тьюрингу, им бы не удалось делать все это.

Кнут: Да, это так. В 1960-х годах я написал язык программирования для эмуляции, на завершение которого потратил много сил, поскольку у него было множество пользователей, но когда появилась Симула, она понравилась мне больше, и я просил людей забыть о моем языке SOL. Вообще-то, мне не кажется, что у меня какой-то особенный талант к разработке языков.

Во время работы над ТеХ я обращался к сотням лет истории человечества, не желая отказываться от всего того, до чего дизайнеры книг дошли за многие века, и начинать заново, сказав: «В общем, забудьте тех ребят; знаете, мы будем рассуждать логически». В этом случае суть дела сводилась, в основном, к тому, чтобы выбрать чудовищно сложную задачу и найти сравнительно небольшой набор базисных элементов для ее поддержки. Вместо 1000 элементов у меня 100 базисных элементов или около того. Но пойти дальше, сведя все к 50 или 10 элементам — что нужно было бы сделать для математической ясности, — мне кажется, такой путь просто не сработает. Задача изготовления книг очень сильно взаимосвязана со сложностью реального мира, который просто противится любым упрощениям.

Сейбел: Я не проводил никаких специальных исследований, но у меня складывается такое ощущение, что подавляющее большинство математических и научных работ в наши дни сверстаны в ТеХ. Наверняка вы не раз видели какие-то исследования, сверстанные в ТеХ, и думали: «Ого, моя программа играет здесь определенную роль».

Кнут: Доказательство великой теоремы Ферма — один из таких случаев. Это одна из самых известных математических работ. И все равно постоянно встречаются книги, которые, я знаю, не были бы написаны, если бы их авторы шли по проторенным дорожкам. Опять же это своего рода проблема черных ящиков.

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

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

Поэтому мне всегда очень приятно осознавать тот факт, что люди смогли пробиться через все это и что плоды их творчества поступают напрямую к их читателям.

Сейбел: Как по-вашему, программисты и ученые в области компьютерных наук хорошо знают историю нашей области знания? Ведь она, в общем-то, не столь продолжительна.

Кнут: Не так уж и много сейчас ученых. Даже когда я начинал писать книги — в 1963 году, — мне не казалось, что люди знали тогда, что происходило в 1959 году. На прошлой неделе я прочел в «American Scientist», что был заново открыт алгоритм, который Бойер и Мур открыли в 1980 году. Я на каждом шагу сталкиваюсь с тем, что люди не осознают все великолепие нашей истории. Многим молодым программистам кажется странной мысль о том, что в 1970-х люди тоже что-то знали, понимали и умели.

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

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

Например, я долго изучал вавилонские рукописи, чтобы узнать, как 4000 лет назад описывались алгоритмы и что они обо всем этом думали, были ли у них циклы и прочее и как их описывали. Для меня эта работа, безусловно, была не напрасной, поскольку я обогатил свое понимание работы человеческого мозга и понял, как тогда делались открытия.

Несколько лет назад я нашел старинную рукопись на санскрите, датированную XIII веком, которая была посвящена проблемам комбинаторной математики. Практически никто из тех, кого знал автор, не смог бы даже приблизительно понять, о чем он говорил. Но я нашел перевод этой рукописи — и она оказалось мне очень близка. Я думал сходным образом, когда только начал программировать. Чтение первоисточников очень сильно обогащает меня в личном плане и в том, что касается моего творческого потенциала.

Мне не удалось передать ничего этого своим студентам. В современной компьютерной науке есть те, кому это удается (их не так много). Но я могу пересчитать по пальцам одной руки тех, кто разделяет мою любовь к чтению первоисточников.

У меня большая коллекция исходных кодов. Есть компиляторы, компиляторы Digitek 1960-x, созданные в очень интересной манере. В них использован собственный язык, идентификаторы длиной 30 символов, но они были очень описательными; эти компиляторы заметно превосходили своих тогдашних конкурентов — эта компания производила мейнстримовые компиляторы в 1963 или 1964 году.

У меня есть исходный код Дейкстры операционной системы THE. Я его не читал, лишь пока проглядел, но я нашел его, потому что уверен, что мне интересно будет почитать его в свободное время. Однажды я сломал руку, катаясь на велосипеде, и практически ничего не мог делать целый месяц, поэтому читал исходный код, в котором, как я слышал, применялись некоторые интересные недокументированные идеи. Думаю, этот опыт был очень важен для меня.

Сейбел: Как вы читаете исходный код? Ведь непросто читать даже то, что написано на известном вам языке программирования.

Кнут: Но это действительно того стоит, если говорить о том, что выстраивается в вашей голове. Как я читаю код? Когда-то была машина под названием Bunker Ramo 300, и кто-то мне однажды сказал, что компилятор Фортрана для этой машины работает чрезвычайно быстро, но никто не понимает почему. Я заполучил копию его исходного кода. У меня не было руководства по этому компьютеру, поэтому я даже не был уверен, какой это был машинный язык.

Но я взялся за это, посчитав интересной задачей. Я нашел BEGIN и начал разбираться. В кодах операций есть ряд двухбуквенных мнемоник, поэтому я мог начать анализировать: «Возможно, это инструкция загрузки, а это, возможно, инструкция перехода». Кроме того, я знал, что это компилятор Фортрана, и иногда он обращался к седьмой колонке перфокарты — там он мог определить, комментарий это или нет.

Спустя три часа я кое-что понял об этом компьютере. Затем обнаружил огромные таблицы ветвлений. То есть это была своего рода головоломка, и я продолжал рисовать небольшие схемы, как разведчик, пытающийся разгадать секретный шифр. Но я знал, что программа работает, и знал, что это компилятор Фортрана — это не был шифр, в том смысле что программа не была написана с сознательной целью запутать. Все дело было в коде, поскольку у меня не было руководства по компьютеру.

В конце концов мне удалось выяснить, почему компилятор работал так быстро. К сожалению, дело было не в гениальных алгоритмах — просто там применялись методы неструктурированного программирования и код был максимально оптимизирован вручную.

По большому счету, именно так и должна решаться головоломка: составляются таблицы, схемы, информация извлекается по крупицам, выдвигается гипотеза. В общем, когда я читаю техническую работу, это такая же сложная задача. Я пытаюсь влезть в голову автора, понять, в чем состоял его замысел. Чем больше вы учитесь читать вещи, написанные другими, тем более способны изобретать что-то свое — так мне кажется.

Мы должны публиковать код. Доступны комментарии Джона Лайонса к 6-й версии UNIX, с исходным кодом. И программы Билла Аткинсона теперь находятся в открытом доступе благодаря Apple, и уже скоро мы сможем их прочитать. Это очень хорошо документированный код со множеством новаторских графических алгоритмов.

Сейбел: Конечно, благодаря политике открытого исходного кода у нас сейчас гораздо больше кода для чтения, чем раньше.

Кнут: Да, это так. И по-прежнему каждый может применять разные виды нотации — не стоит читать только тех программистов, которые пишут так же, как и вы.