Один раввин узнает или открывает секрет имени Бога и произносит его над глиняной человеческой фигурой, оживляя ее и нарекает свое создание големом. По одной из версий легенды, раввин пишет на лбу голема слово ЭМЕТ, означающее истину. Голем начинает расти. Наступает момент, когда господин не может дотянуться до него. Он просит голема завязать ему башмаки. Голем наклоняется, и раввину удается стереть первую букву слова ЭМЕТ. Остается МЕТ – мёртв. Голем обращается в пыль. Борхес, "Вечер Шестой. Каббала"
Сегодня мы повторим эксеримент, подобный проведённому Йехудой Бен Бецалелем в Праге, однако наше заклинание, вдыхающее жизнь (а лучше сказать "Жизнь") в кусок железа (в нашем случае) будет подлиннее слова ЭМЕТ, как говорит Борхес, или ТЕТРАГРАММАТОНА, как утверждают другие источники. И всё-таки вся программа будет записана ровно в одну строчку! (и даже символы мы будем писать справа налево, как это делал раввин). В этой главе мы шаг за шагом разберём работу программы на APL, реализующую игру Жизнь, с которой познакомились в четвёртой главе.
Однако прежде, чем начать подробный разбор (правильней было бы сказать – «расшифровку») программы, давайте попробуем разработать стратегию ее написания.
«Жизнь» по самой своей сути – игра циклическая. Тем более, алгоритм управляющий ходом игры, подразумевает использование циклов. Так, например, основной цикл программы – это смена поколений. Чтобы вычислить умершие и рожденные клетки, необходимо «просканировать» матрицу, то есть последовательно просмотреть одну за другой, как пустые, так и заполненные клетки. И, наконец, самый глубокий цикл должен вычислять количество соседей каждой из клеток
Казалось бы – все пропало; у нас нет возможности использовать ни одного цикла внутри строчки, не говоря уже о трех вложенных циклах! Но APL не был бы APL'ом, если бы не позволял выбраться из, казалось бы, безвыходной ситуации.
Начнем с того, что цикл, который «сканирует» матрицу, то есть проходит по всем ее клеткам, нам просто не нужен. Ведь в APL мы можем легко обрабатывать целые матрицы с помощью одной функции. Что же касается главного цикла – того, который руководит сменой поколений, то его не будет вообще!
Обозначим число поколений, которые необходимо распечатать как N. А теперь просто запишем все N циклов в одну очень длинную цепочку вычислений, то есть в одну строчку и выполним ее.
Так не пойдет, - возмутится читатель, - а если нам нужно распечатать 100 поколений ? Что же, выписывать в строчку 100 циклов, которые делают одно и то же ? Вот здесь-то и зарыта пресловутая собака. Все циклы (каким бы большим не было их число) выполняют одни и те же действия. Поэтому мы просто напишем одну строчку с действиями, происходящими внутри единственного цикла, а потом размножим ее (с помощью r) N раз. И здесь на помощь нам приходит удивительный оператор APL, который называется ⍎ (Execute). Этот оператор выполняет строку (настоящую строку, то есть текст, заключенный в кавычки, а не строку программы), переданную ему как аргумент[1]. Этот-то оператор и будет отвечать за выполнение длинной цепочки вычислений, которую мы ему дадим.
Наконец, нам необходимо посчитать всех соседей каждой из клеток без использования циклов. Это и будет основным трюком нашей программы.
Будем представлять заполненные клетки матрицы единицей, а пустые нулем.
Для примера, возьмем матрицу размером 5х5 и зададим в самой середине простейший «организм» - осциллятор, который называется «семафор»:
Семафор ведёт себя так:
Итак, что нужно сделать, чтобы найти сумму всех соседей какой-либо из клеток ?
Соседей этих 8 и, если мы сдвинем нашу матрицу 8 раз в каждом из возможных направлений и сложим все единицы, полученные в каждой из клеток, то сумма даст в точности число единиц (то есть соседей), окружающих данную клетку.
На следующем рисунке представлены восемь матриц, полученных в результате такого сдвига:
Теперь сложим все полученные матрицы (кроме исходной):
Мы получили матрицу, в каждой клетке которой записано число соседей этой клетки. Но ведь это в точности то, что нам нужно! Теперь, согласно правилам «Жизни», заполненные клетки, у которых 2 или 3 соседа останутся жить; клетки, у которых один сосед – отомрут, а в пустых клетках, у которых ровно три соседа, родятся новые заполненные клетки.
Произведя простые логические операции с полученной матрицей, мы получим следующее поколение «семафора»:
Имея на руках план действий, мы готовы приступить к разбору программы. Однако сначала, руководствуясь принципами настоящего фокусника (а язык APL и есть настоящий фокусник),поделим наше представление на три части так, как поведал нам фильм "Престиж" [2]. Итак
Часть первая - "Наживка"
Перед вами программа, распечатывающая N поколений «организма», заданного начальной матрицей M [3]:
В этом месте автор не может удержаться и не упомянуть, что эта самая программа когда-то попала в редакторскую колонку журнала Dr.Dobbs, посвященную APL:
При разборе будем двигаться строго справа налево, так, как это делает интерпретатор APL. Для удобства (исключительно для удобства, а не потому, что это как-то диктуется APL!) поделим нашу программу на логические блоки так, как это показано на рисунке. Так будет удобнее следить за развитием событий.
Часть вторая - "Превращение"
В апострофы заключена строка, которая и является «телом» нашей программы (Block 1). Она выглядит так:
Первым делом над исходной матрицей производится операция Enclose: ⊂M. Эта операция превращает матрицу в скаляр (то есть размерность ее становится 1х1, сохраняя при этом внутреннее содержание - очередной магический трюк APL!). Это довольно трудно осознать, поэтому здесь нам поможет картинка с примером такой операции:
Зачем это нужно, скоро станет понятно. Следующая функция называется Rotate: Ө . Она вращает матрицу на заданное число позиций относительно горизонтальной оси (что выражается во внешнем виде значка). Чтобы понять назначение этой функции и объяснить присутствие значка ¨ (Each) справа от нее, посмотрим сначала на левый аргумент Rotate, а именно на выражение (V,V←1 -1) Здесь происходят сразу два действия: присваивание переменной V значения вектора 1 –1 (что представляется как V←1 -1) и немедленное использование этой переменной (переменная-вектор V будет использована еще много раз в нашей строке). Тут же мы знакомимся с функцией , (запятая), которая называется Catenate и служит для «склеивания» двух элементов в единый вектор. Таким образом, выражение V,V←1 -1 означает просто вектор из четырех элементов: 1 –1 1 –1. Как уже было сказано, побочным эффектом этого выражения является инициализация переменной V.
Итак, перед нами следующее выражение (Block 2):
(1 –1 1 –1) Ө¨⊂M
Оператор[4] ¨ , который называется Each действует на функцию Rotate таким образом, что каждому элементу левого аргумента Rotate ставится в соответствие элемент правого аргумента Rotate и действие вращения матрицы происходит попарно: один элемент левого аргумента соответствует одному элементу правого аргумента. (Оператор Each может, конечно, использоваться и с любой другой функцией). Если же одним из аргументов является скаляр (как в нашем случае – вспомните, что матрица была превращена в скаляр с помощью Enclose!), то он превращается в вектор с числом элементов, соответствующих аргументу-вектору. Таким образом, наше выражение может быть представлено как
(1 –1 1 –1) Ө¨(⊂M ⊂M ⊂M ⊂M)
Теперь уже легко понять, что здесь происходит. Наша матрица вращается четыре раза вокруг горизонтальной оси: вверх на один ряд, вниз на один ряд, еще раз вверх, и еще раз вниз. Результат этих действий выглядит так:
Но это только промежуточный результат. На самом деле нам нужно сдвинуть каждую из этих матриц влево и вправо на одну колонку, чтобы в итоге получить четыре сдвига по диагоналям. Имея в запасе необходимые знания, сделать это легко с помощью такого выражения: (1 –1 –1 1) Φ¨ Block 2
Здесь тоже используется функция Rotate, но уже вокруг вертикальной оси: Φ. Знакомый нам оператор Each повернет все четыре матрицы в соответствии с левым аргументом: влево, вправо, вправо, влево. Однако, чтобы переменная V не стояла без дела, вместо вектора 1 –1 –1 1, запишем (V,ΦV). Здесь еще раз используется оператор Rotate, который в данном случае применяется к самой переменной V. Быть может, такая запись и не добавляет ясности к происходящему, но зато она очень в духе APL!
Теперь мы знаем, как выглядит результат выражения (V,ΦV)Φ¨(V,V←1 -1)Ө¨⊂M,, которое мы назовем Block 3:
После того, как матрица M сдвинута по всем четырем диагоналям, нам осталось только сдвинуть ее вверх, вниз, вправо и влево. Так, результатом выражения VӨ¨⊂M (Block 4) будет:
А результатом выражения VΦ¨⊂M (Block 5):
Матрица сдвинута во всех восьми возможных направлениях! Чтобы найти число всех соседей каждой из клеток, нам нужно составить все наши так называемые блоки в вектор, состоящий из матриц, и произвести над ним операцию сложения.
В APL это делается так (для простоты чтения воспользуемся нашими обозначениями):
+/ (Block 5) , (Block 4) , (Block 3)
Здесь мы знакомимся еще с одним оператором /, который называется Reduction. Он вставляет функцию, с которой работает (в нашем случае – функцию сложения), между всеми элементами вектора-аргумента (заметьте также, что запятая, то есть функция Catenate составила все блоки в единый вектор):
матрица1 блока 5 + матрица2 блока 5 + матрица1 блока 4 + матрица2 блока 4 + матрица1 блока 3 + матрица2 блока 3 + матрица3 блока 3 + матрица4 блока 3.
Матрица всех соседей готова! Она и есть результат выражения, обозначенного нами Block 6.
(В скобках нужно добавить, что над матрицей соседей производится еще одно действие – ⊃ (Disclose) - которое превращает скаляр, содержащий матрицу, в матрицу изначальной размерности).
Следующим шагом, как и было сказано, будет нахождение всех клеток, число соседей которых равно 2 или 3, с тем, чтобы они продолжали жить в следующем поколении, а пустые клетки, у которых ровно три соседа, должны будут «ожить».
Операция сравнения матрицы соседей с матрицей, заполненной двойками (Block 7), даст в итоге матрицу, состоящую из нулей и единиц таким образом, что единицы будут соответствовать клеткам, у которых есть ровно два соседа:
2=T← Матрица всех соседей
Здесь снова производятся сразу два параллельных действия – присваивание переменной T матрицы всех соседей и немедленное сравнение её с матрицей двоек (заметьте, что скаляр 2 «размножается» до размерности матрицы T).
Вот как это сравнение выглядит на самом деле:
Результат получившегося сравнения выражения таков:
Произведя логическую операцию AND (∧) над этой и оригинальной матрицей M (Block 8) - то есть оставляя единицы только на тех местах, где они встречаются в обеих матрицах - мы получим матрицу, в которой «живыми» остались только клетки, имеющие ровно двух соседей:
Действительно, в исходной матрице M только средняя клетка имеет ровно двух соседей.
Теперь, подобным образом, найдем все клетки, у которых ровно 3 соседа (неважно, являются ли сами клетки «живыми» или нет – в наших интересах оставить в «живых» в живых, и «оживить» пустые клетки).
Результатом выражения (3=T) (Block 9) станет (еще раз взгляните на матрицу всех соседей):
Именно эти клетки должны «родиться» в следующем поколении.
Наконец, осталось только логически сложить (с помощью операции OR (∨)) обе полученные матрицы (представленные на двух последних рисунках), и мы вычислили новое поколение «Жизни» для M!
Все вместе:
Block 10 ← Матрица всех соседей,
то есть
(3=T)∨M∧2=T← Матрица всех соседей
дает результат:
что и требовалось доказать.
Теперь распечатаем на экране полученную матрицу с помощью функции Quad (⎕), путем «присваивания» ей полученного значения:
Но на этом приключения не заканчиваются.
Вспомните, что до сих пор мы рассмотрели только действия, приводящие к вычислению и распечатке следующего поколения. Кроме того, все эти действия пока «закрыты» от выполнения внутри строки, заключенной в апострофы. Что же происходит с этой строкой?
Взгляните на Bock 11:
Переменная S получает значение строки, которую мы обозначили Block 1 (обратите внимание - значение именно строки как набора символов, а не результата её вычисления!). Таким образом мы как бы задерживаем выполнение Block 1 до того момента, когда всё будет готово к вычислению N поколений (вспомним, что Block 1 вычисляет только одно поколение "Жизни").
Ещё раз вернёмся к фокусу с превращением вектора в скаляр - на этот раз превратим в него вектор символов S с помощью Enclose: ⊂S. Двигаясь влево, мы видим функцию ⍴ (Reshape), левый аргумент которой N есть число поколений, которые необходимо вычислить. Reshape превратит скаляр(!) S в вектор, состоящий из N одинаковых элементов, каждый из которых представляет собой Block 1, то есть нашу процедуру для вычисления одного поколения. Таким образом, мы получили вектор скаляров, состоящих из векторов символов.
Последняя метаморфоза - функция Enlist (∈) превращает массив, состоящий из любого количества вложенных элементов в простой вектор, как бы распрямляет его. Наш сложный вектор из N вложенных "скаляров-векторов" превратится в один очень длинный, но простой вектор символов. Чтобы подчеркнуть важность этого последнего вектора, давайте назовём его как-нибудь вычурно, "по-математически", например 𝕹. И здесь начинается третья, главная часть нашего представления -
Часть третья - "Престиж" Вот на что нужно обратить внимание: каждая подстрока вектора 𝕹 (то есть, каждый Block 1) начинается с символа M (заданной матрицы 1-го поколения), а заканчивается операцией присвоения ← (как обычно, читаем строку справа налево):
То есть, самый правый символ вектора 𝕹 - начальная матрица M, а весь вектор 𝕹 выглядит таким образом:
Теперь уже становится понятно, что именно здесь происходит: когда 𝕹 начинает выполняться справа налево, каждый раз заново вычисленное значение матрицы M (то есть, каждое следующее поколение "Жизни") присваивается той же самой переменной М как её "входная" матрица, чтобы уже на её основе вычислить новое поколение! А число всех вычисленных поколений равно N.
Единственная оставшаяся проблема - что делать с самой левой, висящей в воздухе, стрелкой (операцией присвоения) вектора 𝕹. Взгляните на самый левый символ Block'а 11:
Наша последняя "висящая" стрелка Block'а 1 слева упирается в символ ⎕ (Quod), который склеивается с вектором 𝕹 запятой (Catenate). Но это же и есть в точности то, что нам нужно - распечатать последнее поколение!
Наше грандиозное представление заканчивается встречей с функцией Execute ⍎. Эта функция - ни что иное, как встроенный в язык интерпретатор самого APL - она выполняет данную ей в качестве аргумента строку (конечно же, эта строка должна содержать синтаксически верное выражение языка). Ну и каким же будет результат выполнения нашего vector par excellence 𝕹 ?
Правильно: N напечатанных на экране матриц, представляющих N поколений "Жизни", начиная с заданной матрицы M.
Пошёл собирать реквизит.
[1] Execute подобен функции eval Лиспа.
[2] В оригинале The Pledge, The Turn, and The Prestige.
[3] Справедливости ради нужно заметить, что автор потратил целый день, на то, чтобы разобраться в своей собственной программе, написанной несколько лет назад. Эта ситуация вполне обычна, когда речь идет об APL.
[4] Оператор отличается от функции тем, что его аргументом является некая функция, а не числовое или символическое значение. Будучи примененным к функции оператор некоторым образом изменяет ее действие.