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

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

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

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

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

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

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

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

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

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

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

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

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