Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

Что именно делает всех бабочек «похожими» друг на друга? Отображение одной бабочки на другую не совпадает по клеткам; скорее, оно совпадает по функциональным органам, отчасти на макроскопическом и отчасти на микроскопическом масштабе. Вместо точных пропорций сохраняются функциональные отношения частей. Именно этот тип изоморфизма связывает между собой бабочек на гравюре Эшера «Бабочки» (рис. 37). То же верно и для более абстрактных бабочек Графика G, связанных между собой математическими отображениями одной функциональной части в другую. При этом полностью игнорируются пропорции линий, углы, и тому подобное.

Рис. 37. М. К. Эшер. «Бабочки» (гравюра на дереве, 1950).

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

Когда два предмета схожи между собой?

В этой книге мы вернемся к нему еще не раз и, рассмотрев его под всевозможными углами, увидим, насколько такой простой вопрос связан с природой разума. То, что этот вопрос возник в главе, посвященной рекурсии, не случайно, рекурсия — это область, в которой схожесть-внутри-различия играет центральную роль. Рекурсия основана на «одном и том же» событии, происходящем одновременно на нескольких различных уровнях. При этом события на разных уровнях не одинаковы — скорее мы находим в них какую-либо общую черту, как бы они не различались. Например, в «Маленьком гармоническом лабиринте» истории на разных уровнях весьма отличны друг от друга, и их схожесть заключается лишь в двух фактах: (1) все они — истории и (2) во всех историях действуют Ахилл и Черепаха. В остальном, эти истории радикально отличаются одна от другой.

Одна из основных способностей, необходимых в компьютерном программировании, — это умение заметить, когда два явления схожи в широком смысле, поскольку это ведет к модуляризации — разбиванию задачи на несколько естественных подзадач. Представьте, например, что вам надо исполнить одну за другой серию схожих операций. Вместо того, чтобы записывать каждую из них, мы можем написать петлю (или цикл ), которая говорит компьютеру, что, выполнив некое множество операций, он должен вернуться к началу и повторять тот же процесс снова и снова, пока не будет выполнено некое условие. Тело петли — определенные повторяющиеся команды — не должно быть жестко установленным; в нем допустимы предсказуемые вариации. Примером может служить несложная проверка того, является ли число N простым. Вначале вы делите число N на 2, потом на 3, 4, 5, и так далее, до N-1. Если N не делится ни на одно из этих чисел, то N — простое число.

Обратите внимание на то, что каждый шаг цикла здесь похож на другие, но не тождественен им. Заметьте также, что количество шагов варьируется в зависимости от N, поскольку петля постоянной длины не могла бы служить общей проверкой для простых чисел. Существуют два критерия для «прерывания» петли: (1) если N делится без остатка на какое-либо число, то петля прерывается и ответом будет «НЕТ»; (2) если мы достигли N-1 и N «выжило», не разделившись, то петля прерывается и ответом будет «ДА».

Основная идея петель такова: повторять серию родственных шагов до тех пор, пока не выполняется определенное условие. Иногда максимальное количество шагов в петле заранее известно, а иногда мы начинаем и ждем, пока петля прервется. Второй тип петель, который я называю свободными , опасен, поскольку условия для прерывания петли могут никогда не выполниться, в результате чего компьютер застрянет на так называемом «бесконечном цикле». Разница между свободными и ограниченными петлями , или циклами , является одним из важнейших понятий в теории вычислительной техники; этой теме будет посвящена глава «БлууП и ФлууП и ГлууП».

Петли могут быть также вложены одна в другую. Предположим, например, что мы хотим найти все простые числа от 1 до 5000. Для этого можно написать вторую петлю, повторяющую описанную проверку снова и снова, начиная с N=1 и кончая N=5000. Таким образом, у нашей программы будет структура «петли-в-петле». Хорошие программисты обычно составляют программы именно в этом «стиле». Подобные вложенные петли встречаются в инструкциях для сборки простых предметов, а также в таких видах деятельности, как вязание и вышивание, где маленькие петли повторяются несколько раз внутри больших петель, которые, в свою очередь, тоже повторяются несколько раз… Результатом петли на нижнем уровне может быть всего пара стежков, в то время как петля на высшем уровне производит большую часть изделия.

В музыке также часто встречаются вложенные одна в другую петли — например, когда гамма (маленькая петля) проигрывается несколько раз, возможно, сдвинутая при этом выше или ниже. Последние части Пятого концерта Прокофьева и Второй симфонии Рахманинова содержат длинные пассажи, в которых разные инструменты одновременно проигрывают гаммы-петли в быстром, среднем и медленном темпе — эффект получается потрясающий. Гаммы Прокофьева идут вверх, гаммы Рахманинова — вниз. Выбор за вами!

Более широким, чем понятие петли, является понятие подпрограммы или процедуры, которое мы уже затронули. Группа операций при этом рассматривается как одно целое, носящее определенное название — например, процедура УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ. Как мы видели в СРП, процедуры могут вызывать одна другую по имени — таким образом кратко описывается последовательность необходимых операций. Это — основа модульности в программировании. Разумеется, модульность существует также в качественных системах звуковоспроизведения, в мебели, в живых клетках и в человеческом обществе — везде, где есть иерархическая структура.

Чаще всего, нам нужна процедура, которая может варьироваться в зависимости от контекста. Такая процедура может согласовывать выбор действий с информацией, хранящейся в памяти, или же действовать согласно данному списку параметров . Иногда используются оба эти метода. В терминах СРП выбор последовательности действий называется выбором пути . СРП, улучшенная добавлением параметров и условий, контролирующих выбор путей внутри нее, называется Увеличенная Схема Переходов (УСП). Скорее всего, вы предпочтете УСП вместо СРП, если вам надо получить осмысленные русские предложения на основе набора слов; при этом базой служит грамматика, выраженная в УСП. Параметры и условия позволят вам ввести определенные семантические ограничения, запрещающие случайные соединения типа «неблагодарная закуска». Однако мы еще вернемся к этой теме в главе XVIII.