Ознакомительная версия.
Сейбел: Многие с вами согласятся, что, да, интереснее писать код самому. Но помимо увлекательности есть еще и...
Кнут: Дело не только в том, что это интересно. Работа математика заключается в том, чтобы писать доказательства, но практически никогда не бывает так, что в процессе решения математической задачи вы можете найти теорему, чьи гипотезы абсолютно идеально подходят для вашего случая. Практически всегда вы работаете с тем, что более или менее похоже на классическую теорему из учебника. Поэтому, что вы делаете? Читаете доказательство этой теоремы и думаете: «Ага, вот как мне нужно изменить это доказательство, чтобы доказать гипотезу, которой я занимаюсь». То есть в математических книгах полно теорем, но вы никогда не берете всю теорему от начала до конца — вам нужно увидеть ее доказательство, потому что лишь в одном случае из ста вы сможете найти теорему, которая идеально подходит для вашей задачи. Думаю, примерно так же дело обстоит и с ПО.
Сейбел: И тем не менее, не является ли ПО — по-моему, вы сами же об этом и говорили — самой сложной вещью, когда-либо созданной человеком?
Кнут: По-моему, Дейкстра сказал это первым, но, вообще, да, все верно. Все дело в том, что сложность соединения разных вещей далеко не однородна. В чистой математике стремятся к тому, чтобы выработать небольшое количество правил, которые можно было бы применять ко всем явлениям — 3-4 аксиомы для описания целой системы. В компьютерной же программе множество частей: шаг 1 не похож на шаг 2, а тот, в свою очередь, не похож на шаг 3. Вам нужно соединить все эти вещи и организовать весьма нетривиальным способом.
Сейбел: Таким образом, учитывая сложность, получается, что в какой-то момент нужно взять ряд черных ящиков и сказать: «Ага, мы знаем, как эта штука работает, и можем ею пользоваться». Если бы нам пришлось заглядывать внутрь каждого черного ящика, мы бы никогда не смогли ничего довести до конца.
Кнут: Я не говорю, что черные ящики бесполезны. Я говорю лишь о том, что если мне не разрешается их открывать и если мне нужно выполнить определенное задание, располагая лишь библиотекой из чего-то подобного, то я получу гораздо более низкие результаты — и все будет происходить намного медленнее.
Сейбел: Медленнее — вы имеете в виду работу программы или ее разработку?
Кнут: И то, и другое. Ну хорошо, я могу достаточно быстро сделать работающую программу, поэтому этого утверждать не могу. Просто у меня уйдет больше времени в силу того, что мне придется потратить время на изучение большего количества справочников и на поиск нужных элементов, то есть эта проблема скорее связана с поиском, а не с процессом создания.
Сейбел: Какое-то время назад программист, писавший стандартные библиотеки Java, написал статью о том, как в их реализации двоичного поиска на протяжении девяти лет была ошибка. То есть они взяли минимум и максимум, сложили их и разделили на два. Но, естественно, если операция сложения переполняется, то это ошибка. В общем, конечно, плохо то, что в стандартной библиотеке была ошибка, но в итоге они нашли ее и устранили. Если бы все сами писали двоичный поиск, то ошибочных двоичных поисков, наверное, было бы больше.
Кнут: Это так. И это лишь один пример из огромного множества. Двоичный поиск — это конкретный пример того, с чего мы начинали наши занятия по программированию в 1970-х. В первый день учебы все писали программы двоичного поиска и сдавали нам, после чего ассистенты их изучали. В результате работали меньше 10% программ. И находилось около 4-6 различных ошибок. Но ни одна из них не имела никакого отношения к переполнению, которое вы упомянули; это новая ошибка — на моих занятиях мы не считали сложение этих двух чисел проблемой.
Вернемся к идее черного ящика. Вы можете спросить, почему же она мне так ненавистна? Мы говорим об арифметических операциях, поэтому предположим, что у нас есть программа для перемножения матриц. У нас есть черный ящик для перемножения матриц, затем мы меняем тип данных — с действительного на комплексный; и теперь у нас есть черный ящик для перемножения комплексных матриц, работа которого занимает 4я3 шагов, а не п3 шагов. Если работа программы с действительным типом данных занимает определенное время t, то работа программы с комплексным типом данных занимает время 4t. Но если вы можете заглянуть внутрь ящика, то вам понадобится лишь 3 операции перемножения матриц с действительным типом данных, а не 4, поскольку у нас есть тождество, которое описывает результат перемножения двух комплексных матриц. Это лишь небольшой пример; их список можно продолжать до бесконечности.
У меня есть очередь с приоритетами или структура вроде кучи; что бы там ни было — двоичный поиск — у меня будет хороший источник для алгоритма, но он будет не до конца соответствовать моим целям, поэтому я каждый раз буду его адаптировать. И мне кажется, что так лучше для меня. Я знаю, что со мной не согласятся многие, кто считает, что их работа — писать программы, которые все будут использовать; поэтому если в них находятся ошибки, они их исправляют, и программы всех других людей также станут работать лучше. Хорошо. Мне не нравится такой подход к делу. И я хочу увидеть их программы.
В то время, когда я писал первый том «Искусства программирования», люди не понимали, что они могли использовать связные списки в своих программах, а также указатели для работы со структурами данных.
Столкнувшись с задачей, не связанной с массивами, вы обращались к имеющимся пакетам программ или к интерпретируемому языку, вроде IPL-V или Лиспа. Также были версии на Фортране, и вы могли взять эти подпрограммы, разобраться, как ими пользоваться, и создавать в нем собственную программу. Считалось совершенным абсурдом учить обыкновенного программиста использовать связные списки в собственных программах. Считалось, что все должно делаться с помощью этих наработанных процедур.
Но тогда в обычных пакетах должны были быть представлены все дополнительные инструменты, необходимые лишь для решения каких-то узких задач, встававших перед небольшим количеством пользователей. Поэтому моя книга в общем-то открыла людям глаза: «Боже, я могу это понять и адаптировать таким образом, что смогу разместить элементы в двух списках одновременно. Я могу менять структуру данных». Эта практика стала повсеместно доступной, а не закрытой для употребления лишь в рамках этих пакетов.
То же самое я вижу и сейчас, работая над структурами BDD. На данный момент есть 3-4 пакета подпрограмм, работающих с BDD, но я пишу сейчас в «Искусстве программирования» — если вкратце, — что вы тоже можете писать простые версии BDD для множества приложений, которые будут весьма эффективны. Вы можете использовать их для самых разных задач, в которых вам не нужны все эти прибамбасы других пакетов; и те вещи, которые вы теперь можете делать, легки для понимания и для использования в программах, которые вы пишете сами.
В этом году я закончил раздел, посвященный уловкам и приемам работы с побитовыми операциями, а эти вещи долго считались черной магией среди компьютерных специалистов. Я решил: пора сказать о том, что у этих приемов есть и теоретический аспект, благодаря которому можно понять эти идеи и то, как они используются. Вы можете абсолютно уверенно использовать их сами. Кроме того, вы можете создавать программы и делать удивительные вещи, о которых в прошлом году не имели особого представления. До нынешнего времени все это было в глубоком подполье, но этому мы также должны учить людей — это знание заслуживает того, чтобы быть доступным всем.
Я пишу много программ и не могу утверждать, что являюсь показательным примером, но точно знаю, что мне удается создавать много программ, успешно выполняющих различные задачи, и мне было бы намного труднее, если бы пришлось тратить время на изучение работы с программами и процедурами, написанными кем-то другим. Мне гораздо проще разобраться с рядом базовых понятий, после чего повторно использовать код путем редактирования текста кода, который раньше работал.
Ознакомительная версия.
