Питер Сейбел - Кодеры за работой. Размышления о ремесле программиста
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 игр она была уже достаточно приемлемым игроком в крестики-нолики.
Сейбел: Похоже, многие из тех, с кем я беседовал, имели непосредственный доступ к компьютерам в самом начале своей карьеры. Тем не менее у Дейкстры есть работа - уверен, вы с ней знакомы, - в которой он прямо говорит, что студентов компьютерных специальностей первые несколько лет обучения не следует допускать к работе за компьютером - все это время они должны учиться работать с символами.
Кнут: Но он и сам так не учился. Он высказывал очень много правильных и прекрасных мыслей, но не всегда был прав. Как и я. Моя позиция по этому поводу такова. Допустим, есть некий ученый - в любой области науки. Становясь старше, этот ученый думает: “Да, что-то из того, что я делал, оказалось действительно полезно, а что-то я уже не использую. Моим студентам не стоит тратить время на какие-то неглобальные вещи. Я вообще не буду с ними обсуждать никакие частные и низкоуровневые задачи. Теоретические понятия - вот что действительно важно и необходимо. Да, и забудем о том, как я до всего этого дошел сам”.
