15. Дональд Кнут

15. Дональд Кнут

Из всех героев этой книги Дональд Кнут, пожалуй, меньше всех нуждается в представлении. На протяжении последних 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 экономится только при п больше двух миллионных. Подобных исследований великое множество. Их авторы фантазируют о том, что, в принципе, если бы компьютеры были богоподобны, то у нас были бы более быстрые алгоритмы. Но даже алгоритмы вроде сбалансированного дерева или 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я³ шагов, а не п³ шагов. Если работа программы с действительным типом данных занимает определенное время t, то работа программы с комплексным типом данных занимает время 4?. Но если вы можете заглянуть внутрь ящика, то вам понадобится лишь 3 операции перемножения матриц с действительным типом данных, а не 4, поскольку у нас есть тождество, которое описывает результат перемножения двух комплексных матриц. Это лишь небольшой пример; их список можно продолжать до бесконечности.

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

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

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

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

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

Данный текст является ознакомительным фрагментом.