Питер Сейбел - Кодеры за работой. Размышления о ремесле программиста

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

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

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

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

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

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

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

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

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

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

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