Игра «Жизнь» Конвея В Одной APL Строке

http://catpad.net/michael/APLLife.gif

Разъяснение

Если вам не известны игра «Жизнь» Конвея или язык программирования APL, я рекомендую ознакомиться сочень кратким описанием APL и описанием игры Конвея «Жизнь» . Кроме того, на этой странице вы найдете толкование и несколько рецензий для IBM APL2.

Представленное детальное объяснение программы APL, которое рассматривает поколение N изначальной конфигурации М игры «Жизнь», также послужит кратким и достаточно неформальным курсом об APL.

Прежде, чем мы начнем расшифровку (похоже, здесь это слово наиболее подходящее) программы «Жизнь», давайте поработаем над стратегией написания этой программы в одну строку, и не важно насколько нереально это звучит.
«Жизнь» – это циклическая по своей природе игра, и , конечно же, алгоритм реализации этой игры очевидно должен состоять из нескольких циклов. Поэтому, главный цикл данной игры – это движение поколений. Другой цикл – сканирует матрицу и ведет подсчет мертвых, живых или новорожденных клеток. Еще один цикл подсчитывает количество клеток-соседей для каждой существующей клетки. Теперь, вы думаете, вот и все: в одной строке мы не можем использовать даже один цикл, не говоря о том, чтобы вместить все три цикла!
Но подождите минутку – APL дает нам возможность решить практически любую, даже самую отчаянную ситуацию.

Для начала, чтобы сканировать матрицу, нам не требуется цикл, поскольку зачастую APL позволяет нам работать со всей матрицей, используя всего лишь одну функцию. То же относиться и к подсчитыванию количества соседей. Что же касается главного цикла, который регулирует изменение поколений – там он совершенно не понадобиться!

Пусть N будет количеством поколений, которые мы хотим посчитать. Мы можем написать все циклы (подпрограммы, которые образуют тело цикла) как одну очень длинную строку. Теперь, все что нам нужно сделать – оформить эту строку.
Это не хорошо – говорят читатели. – А что если нам понадобиться 1000 поколений? Нам нужно будет написать 1000 циклов, которые будут выполнять одно и то же? Абсолютно нет! Как говорилось ранее, все эти циклы выполняют одну и ту же задачу, поэтому мы напишем всего один цикл, после чего с помощью APL мы их размножим N-е количество раз, используя функцию ρ (ro), которая создает массивы любой длинны. После завершения этой задачи, мы будем использовать прекрасную функцию APL под названием Выполнить – http://catpad.net/michael/apl/Execute.gif. Эта функция выстраивает цепочку последовательных действий в виде работающей строки APL программы (наиболее подходящая операция в Lisp называется eval). Эта функция будет отвечать за построение «очень длинной строки» последовательно связанных циклов тел.

Под конец, нам необходимо будет подсчитать всех соседей каждой клетки в нашей матрице. Это будет главным трюком нашей программы.
Давайте считать живую клетку «Жизни» за единицу, а пустую клетку за ноль. К примеру, мы возьмем матрицу 5х5 и поместим в ее середину очень маленький, но интересный организм под названием семафор:

http://catpad.net/michael/apl/table1.gif
Вот как ведет себя семафор:

и т.д., и т.д.
Поэтому в следующем поколении мы будем ожидать следующую матрицу:
http://catpad.net/michael/apl/table13.gif

Что нам необходимо сделать, чтобы найти сумму всех соседей для каждой клетки в данной матрице? Количество соседей эквивалентно 8, поэтому, если мы перевернем нашу матрицу 8 раз во всех возможных направления, а затем объединим все первые получившиеся клетки – сумма будет равна количеству первых (т.е. соседних) клеток, окружающих данную клетку.
На следующем рисунке вы можете увидеть все 8 матриц, после подобного вращения:

http://catpad.net/michael/apl/table2.gif

Теперь, давайте суммируем все эти матрицы, кроме исходной:

http://catpad.net/michael/apl/table3.gif

Вот более детальное рассмотрение некоторых клеток в исходной матрице, которые указывают на своих соседей:

Таким образом, мы получили матрицу, где каждая клетка содержит такое же количество соседей-живых клеток, как и в исходной матрице!
Теперь, согласно правилам «Жизни», клетки, имеющие 2 или 3 соседей, будут жить в следующем поколении, пока все остальные не погибнут. Пустые клетки, которые имеют именно 3 соседа, будут рождены в новом поколении.
Проведя несколько простых логических операций над матрицей соседей, мы получим новое поколение нашего семафора.

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

http://catpad.net/michael/apl/program.gif

Чтобы расшифровать программу мы переместимся справа на лево, поскольку толкователь APL движется в таком направлении. Для удобства (и только для удобства, поскольку в APL нет ничего подобного) мы разобьём нашу программу на несколько логических блоков, как показано на следующем рисунке:

В таком виде будет легче следовать за развитием событий.

Между апострофами существует связь, которая является основой «тела» нашего главного цикла (Блок 1):

http://catpad.net/michael/apl/block1.gif

Первое, что произойдет на данном этапе – проведение операции Закрыть над исходной матрицей М: ⊂M. Функция Закрыть превращает массивы любой длинны в скалярную величину (вот и все, масив теряет все свои направления, тогда как его исходный контент остается нетронутым). Эта ситуация скороее является исключением, поэтому может быть полезно изобразить ее на рисунке:

Следующая функция называется Вращениеhttp://catpad.net/michael/apl/Rotate_horiz.gif. Она поворачивает матрицу заданное количество раз относительно ее горизонтальной оси (как это отображено в визуализации функции). Чтобы понять значение этой функции и верно истолковать символ «, давайте сперва посмотрим на левую часть доказательстваВращения, а именно выражение: (V,V←1 -1).

Здесь происходит два действия: переменная V закрепляется за вектором 1-1 (представлено как V←1 -1) и сразу же используется (эта переменная будет использоваться в данной программе много раз). Здесь мы встретили новую функцию – , (запятая), которая называется Соединяющей и предназначена для соединения двух элементов в общий вектор. Стало быть, выражение V,V←1 -1 вычисляет вектор, состоящий из четырех элементов: 1 -1 1 -1. Как уже было сказано, побочным эффектом этого выражения является инициализация переменной V.

Итак, мы получаем следующее (Блок 2):
http://catpad.net/michael/apl/Block2.gif

Операция « (которая называется Каждый) влияет на функцию Вращения таким образом, что каждый элемент левой части доказательства Вращения получает копию, представляющую собой элемент правой части доказательства Вращения, поэтому вращение матрицы М будет происходить попарно.
(Заметка об операциях: операции имеют влияние непосредственно на функции, вне зависимости, действуют ли функции на массивы или скалярные величины. Т.е. если доказательство функции всегда будет массивом или скалярной величиной, то доказательство операции всегда будет функцией).
Конечно же операция Каждый может использоваться с любой другой функцией APL.
Запомните: в случае, если одно из доказательств функции скалярно (и вы помните, что исходная матрица М была преобразована в скаляр посредством функции Закрыть), этот скаляр преобразуется в вектор с равным количеством элементов, аналогичным количеству элементов вектора, что является другим доказательством функции. Это означает, что наше выражение будет выглядеть следующим образом: http://catpad.net/michael/apl/Rotate_with_Each.gif

Теперь легче понять, что же происходит. Матрица М вращается вокруг своей горизонтальной оси: один оборот вверх, один оборот вниз, и снова один оборот вверх и один вниз. Результат выглядит так:

http://catpad.net/michael/apl/table5.gif

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

http://catpad.net/michael/apl/rotate_block2.gif

Мы нова используем функцию Вращения, но в этот раз она будет вращать матрицы вокруг вертикальной оси (как изображено на символе). Операция Каждый будет действовать на все 4 матрицы, в соответствии с левым доказательством Вращения: влево, вправо, вправо, влево. Кроме того, чтобы получить максимальную пользу от переменной V, мы также будем ее здесь использовать, а вместо вектора 1 -1 -1 1 впишем (V,http://catpad.net/michael/apl/Rotate_vert.gifV). Здесь снова используется Вращение, которое само по себе относиться к V.
Возможно это выражение не помогает в разъяснении сути, но оно очень подходит для APL!

Теперь мы знаем, как выглядит результат выражения http://catpad.net/michael/apl/expr.gif

Мы назовем его Блок 3:

http://catpad.net/michael/apl/table6.gif

После того, как матрица М была перемещена во всех диагональных направлениях, все что находиться слева перемещается вверх, вниз, влево и вправо. Таким образом, результатом выражения http://catpad.net/michael/apl/Block4.gif
будет:

http://catpad.net/michael/apl/table7.gif

А результатом выражения http://catpad.net/michael/apl/Block5.gif
будет:

http://catpad.net/michael/apl/table8.gif

Наконец-то, матрица была перемещена во всех 8 направлениях. Чтобы найти количество соседей каждой клетки, нам необходимо создать вектор, состоящий из недавно полученных матриц, и суммировать все элементы вектора. В APL мы этом можем легко сделать следующим образом:

+/ (Блок 5) , (Блок 4) , (Блок 3)

Здесь представлена еще одна операция, которая называется Понижение и изображается в виде косой черты: / Операция Понижение вносит свой аргумент функции (в данном случае дополнительную функцию) между всеми элементами данного вектора. Обратите также внимание на Соединяющую функцию, которая создает вектор всех блоков. Вот что мы получаем:
(матрица 1 блока 5) + (матрица 2 блока 5) +
(матрица 1 блока 4) + (матрица 2 блока 4) +
(матрица 1 блока 3) + (матрица 2 блока 3) + (матрица 3 блока 3) + (матрица 4 блока 3).

Теперь у нас есть матрица всех соседей. Она являет собой результат выражения Блока 6.
(Здесь стоит добавить, что существует еще одна функция, которая действует на полученную матрицу –Раскрыть: ⊃. Она прямо противоположна функции Закрыть и преобразовывает матрицу, содержащую скаляр, в матрицу с исходным направлением).

Следующим шагом, как говорилось, будет поиск всех клеток с количеством соседей, эквивалентным 2 или 3, чтобы они могли продолжать жизненный цикл в следующем поколении, а также поиск пустых клеток с тремя соседями, для рождения новых клеток.
Для начала сравним матрицу соседей с матрицей заполненной 2s (Блок 7), в результате мы получим матрицу нулей и единиц, где единицы относятся к клеткам, которые имеют именно по два соседа:
2=T← Матрица всех соседей (Блок 6).
Здесь снова параллельно проявляется два действия: переменная Т приобретает значение матрицы соседей и в то же время сравнивается с матрицей 2s (скаляр «2» распространяется на матрицу 2s, расширение которой эквивалентно матрице, которая сравнивалась с принципом работы APL).
Вот как выглядит сравнение в реальности:

http://catpad.net/michael/apl/table9.gif

И результатом этого является:

http://catpad.net/michael/apl/table10.gif

Как вы видите, получившаяся в результате матрица содержит в каждой клетке результат сравнения всех соответствующих клеток матриц доказательства. 1 означает, что клетки идентичны, 0 – наоборот.

Если для этой и исходной матрицы М (Блок 8), где 1s будут слева только там, где обе матрицы имеют 1s, мы воспользуемся логической операцией И (∧), тогда мы получим матрицу, где по два соседа будут иметь именно только живые клетки:

http://catpad.net/michael/apl/table11.gif

Более того, в исходной матрице М только центральные клетки имеют по два соседа.
Таким же способом мы можем найти клетки, которые имеют только по три соседа. Обратите внимание на трюк: не важно, является ли исходная клетка пустой или живой – нам нужно дать возможность живим клетками жить и заполнить пусты клетки новорожденными 1s.
Итог выражения 3=T (Блок 9), где Т, как вы помните, является матрицей соседей:

http://catpad.net/michael/apl/table12.gif

Эти клетки должны быть рождены в следующем поколении.

Теперь мы должны логически добавить (используя операцию ИЛИ (∨) ) обе матрицы из последних двух выражений и – вуаля! – мы высчитали следующее поколение «Жизни» для матрицы М!

Теперь все вместе
Блок 10 ← Матрица всех соседей, которая
(3=T)∨M∧2=T ← Матрица всех соседей
даст в результате:

http://catpad.net/michael/apl/table13.gif

что несомненно является следующим поколением семафора.

Теперь нам необходимо продемонстрировать итоговую матрицу и мы это сделаем используя функцию вывода APL под названием Квадрат: http://catpad.net/michael/apl/Quad.gif (достаточно просто «присвоить» матрице эту функцию).

Но, мы еще не закончили.
Запомните, что до этого момента мы только лишь делали расчет для одного поколения. К тому же, все действия все еще «заморожены» между апострофами. Так что же произойдет с этой цепочкой?

Посмотрите на Блок 11. Переменная S присвоена цепочке, обозначающей Блок 1. Снова заметьте: S неэквивалентна значению (или размеру) цепочки, S эквивалента самой цепочке, т.е. последовательности значений между апострофами. Таким образом мы отсрочили выполнение Блока 1, до момента, когда все будет подготовлено для расчета N поколения «Жизни». (Запомните, Блок 1 рассчитывает только одно поколение).

Чтобы преобразовать S из вектора в скалярную величину мы используем уже известную нам функциюЗакрыть. Перемещаясь влево мы обнаружим новую функцию – Перепрофилировать (ρ), которая содержит левое N доказательство, представляющее количество поколений, которое мы хотим посчитать. Эта функция изменит ныне скалярную S на вектор с N-эквивалентными элементами, каждый из которых содержится в Блоке 1, являющимся «подпрограммой» для подсчета одного поколения. В общем, мы получили вектор скаляров, состоящий из цифровых векторов.

Последняя метаморфоза – еще одна функция Привлечь (∈), которая используется для создания простого вектора вне массива, состоящего из любого количества вмещающихся элементов. Поэтому, наш «сложный» вектор вмещающихся N элементов станет одним очень длинным, но прямолинейным цифровым вектором. Назовем его как-то по-особенному чтобы подчеркнуть важность этого вектора, например, обозначим как зачастую делают математики.

Стоит обратить внимание на следующее: каждая из подцепочек (т.е. каждый Блок 1) вектора   начинается с символа М (исходная матрица) и заканчивается с привязанной операции ← (как обычно, начало справа, а окончание слева). Таким образом, крайняя правая цифра   – это исходная матрица М, а сам по себе вектор выглядит следующим образом (внутреннее содержание упущено):

http://catpad.net/michael/apl/aacute_vector.gif

И вот оно! Теперь понятно, что происходит: когда цепочка  выполняется справа налево, чтобы рассчитать новое поколение, каждый новый расчет матрицы М (т.е. каждое новое поколение «Жизни») будет присвоен к такой же переменной М, как и новая исходная матрица! Количество поколений будет эквивалентно N.

Теперь осталась только одна проблема – что делать с крайней левой, висящей в воздухе операцией ←. Посмотрим еще раз на всю программу – в самом конце стрелка направляется прямо к символу http://catpad.net/michael/apl/Quad.gifКвадарткоторый последовательно связан запятой с вектором Значит ли это, что необходимо вывести все? Именно, это то, что нам нужно!

И наконец-то, в конце этого грандиозного действа мы встречаем знакомую нам функцию http://catpad.net/michael/apl/Execute.gif (Выполнить). Эта функция показывает символическую цепочку, которая является доказательством данной функции. Конечно, цепочка должна содержать искусственно исправленное APL выражение. Так что значит эта функция? Это, собственно, толкователь APL, скрываемый под видом бесхитростной функции.

Итак, как будет в итоге выглядеть настоящее выражение нашего вектора Справа – выведенные на экран N матрицы, которые представляют N поколение «Жизни», начиная с исходной матрицы М.

English original version

Advertisements