Векторные языки — параллельный мир01.12.2020 16:33

Векторные языки мало известны широкому кругу программистов и занимают узкую нишу обработки данных в финансах, статистике и прикладной математике. Хотя сам векторный подход (или, точнее, программирование с помощью массивов) распространен гораздо шире, чем может показаться. Он реализован в известных библиотеках (NumPy), популярном языке статистиков R, математических пакетах (MATLAB), даже в современных языках программирования (Julia). Однако возможность умножить матрицу на вектор простым выражением (A*v) — это всего лишь вершина айсберга возможностей, которыми обладают полноценные векторные языки. При том, что эти языки не так сильно отличаются от обычных, как может показаться на первый взгляд, они заставляют программиста мыслить совершенно в других категориях и реализовывать алгоритмы способами, которые никогда не придут в голову человеку, привыкшему к Java или даже Haskell. Их характерной чертой, например, является выворачивание наизнанку циклов — вместо того, чтобы спускаться по вложенным циклам вниз к простым значениям и там использовать их в функциях, вы оперируете сложными объектами целиком, давая указания языку, какие именно части этих объектов и как именно вы хотите использовать и так много раз в одном выражении. В этой статье я хочу познакомить вас с этим оригинальным подходом к реализации алгоритмов.

Введение

Для начала определим место векторных языков в мире языков программирования. Исторически первый такой язык (APL) был создан Кеннетом Иверсоном, вдохновленным математической записью. До сих пор эта «математичность» видна невооруженным взглядом и определяет область использования векторных языков — финансы, статистика, математические вычисления. Векторные языки обычно выделяют в отдельную ветвь развития, что создает впечатление об их исключительности. Однако по своей сути это типичные функциональные языки, идеологически очень близкие к Lisp. Как Lisp они обладают минимальным синтаксисом, опираются на один основной тип данных — массив (он же список). Программы пишутся в основном в функциональном стиле, но, в отличие от более «чистых» языков типа ML, в них нет никаких препятствий для использования элементов императивного программирования типа деструктивного присваивания. Без присваивания было бы не обойтись в любом случае, поскольку само слово «векторный» означает, что меняются большие массивы данных, которые было бы накладно копировать при каждом изменении.

У языков программирования есть, как правило, излюбленные области, где особенно ярко проявляются их сильные стороны. На С, например, легко работать с железом. На ML легко писать компиляторы. Lisp известен тем, что на нем легко написать интерпретатор Lisp. Аналогично на векторном языке сравнительно легко можно написать интерпретатор векторного языка. Но главная сила векторных языков, разумеется, в их векторности. Соответственно на них легко написать математическую библиотеку, что и было проделано много раз. Также вектор значений — это фактически колонка в таблице в базе данных, т.е. на векторном языке должно быть легко написать базу данных, и это действительно так. В этой статье я опишу векторные языки в целом, а в следующей я планирую показать, как в пару десятков строк кода можно реализовать простой SQL интерпретатор, начиная с лексера и заканчивая джойнами.

Язык «Вектор»

Для демонстрации возможностей векторных языков мне понадобятся примеры. Можно было бы приводить их на одном из существующих языков, но они довольно сложны для понимания, поэтому я решил, что будет проще создать по ходу дела игрушечный векторный язык, который минимально отличался бы от обычных языков и при этом обладал всеми возможностями настоящего векторного языка. Заодно вы убедитесь, что все эти языки основаны на одних и тех же понятиях, и что за их загадочными обозначениями скрываются обычные (и не совсем обычные) функции.

Назовем этот язык «Вектор». Для начала определим простые (атомарные) типы данных в этом языке:

// для комментариев будем использовать обозначение как в C
10; -20      // integer, ";” разделяет выражения
1.2; -1.3e10 // float
"c"          // char

Я не буду заводить отдельный булев тип. Будем считать, что true — это обычное число 1, а false — 0.

Главный составной тип — это массив, он же список. В векторных языках для определения массивов можно использовать краткую запись:

1 -2 3              // это массив из трех элементов, достаточно перечислить элементы через пробел
1.2 10 -3           // чтобы создать массив float, достаточно записать только одно число как float
"string"            // для строк (массив символов) используется традиционная запись
(1;"a";1.2 1.3 1.4) // смешанный массив, явная запись с помощью (;;;)

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

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

a=1 2 3 dict 3 2 1 // int -> int
a[1]               // доступ через ключ - аналогично индексированию
key a; value a     // доступ к составным частям словаря

Выше я использовал оператор присваивания »=». Главная особенность присваивания — оно действует как обычный оператор и возвращает присваиваемое значение, т.е. можно написать:

b=1+a=3*2 // b равно 7

В векторных языках традиционно уделяется особое внимание функциям от одной (нуля) или двух переменных — монадам и диадам. J доходит до того, что там абсолютно все функции имеют два и меньше аргументов. Мы не будем себя ограничивать, в «Векторе» для функций мы определим следующие правила:

{x}; {x;y}; {x;y;z} // функции от 1/2/3 переменных, определенных неявно как x,y,z
{[a;b;c;d] }        // явное определение аргументов
f[x;y;z]            // вызов функции с помощью скобок
f x                 // монадный вызов
y f x               // диадный вызов, т.е. f[x;y]
{self[]}            // ссылка на саму функцию для рекурсивного вызова

Нам не понадобится присваивать значения глобальным переменным в функциях, поэтому все присваивания внутри функций локальные.

Определим несколько базовых функций:

+ - * /         // арифметические функции
== < > <= >= <> // функции сравнения
~               // функция эквивалентности. Если 1 == x~y, то x и y неотличимы.
list            // создать массив(список) из аргументов: list[1;2]
,               // конкатенация списков и атомов (чисел и символов)

Функция »,» — центральная во всех векторных языках, она соединяет два объекта в один. Если ее аргументы — словари, то результатом будет словарь (значения с одинаковыми ключами будут взяты из правого аргумента), в остальных случаях результатом будет список:

1,2 -> (1;2)
1,2 3 -> (1;2;3)
"ab",1 2 -> ("a";"b";1;2)

Этих сведений нам пока достаточно, остальные функции определим по ходу дела.

3 кита векторных языков

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

1. Порядок выполнения операций.

2. Особые модификаторы функций.

3. Опора на индексирование и структурно-полиморфные базовые функции.

Я не включаю в этот список специальные знаки для обозначения базовых операций, хотя именно они являются первым, что бросается в глаза при знакомстве с векторным языком. Дело в том, что только в APL они действительно к месту, в остальные языки они перекочевали по наследству и вместо ясности, наоборот, добавляют тумана и затрудняют чтение программы. Как вы убедитесь, можно все (почти) особые обозначения заменить на обычные слова и ничего не потерять. Даже длина выражений возрастет всего раза в два.

Первые два пункта и индексирование подробно объясняются в следующих трех разделах. Под структурно-полиморфными функциями я понимаю функции, которым безразличен не только тип аргумента, но и его конкретный вид. Например, функция first возвращает первый элемент чего бы то ни было — атома (простого типа данных), массива, словаря. Точно также »,» соединяет два любых объекта, которые можно соединить. Некоторые из этих функций я определю по ходу дела, а часть подробнее рассмотрю в специальном разделе ниже.

Порядок выполнения

В векторных языках вычисления традиционно производятся справа налево, а все встроенные функции и операторы имеют одинаковый приоритет. Т.е. выражение типа

2*3+1

следует читать как

2*(3+1)

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

На самом деле, вопрос стоило бы поставить иначе — зачем вообще нужен приоритет операций. Пользы от него почти никакой, зато он порождает двусмысленности и необходимость запоминать лишнюю информацию. Например, в С++ существует 17 уровней приоритета операций, некоторые из которых право ассоциативные, а некоторые лево ассоциативные. Порядок вычислений не определен, но при этом есть больше двух десятков правил, определяющих этот порядок в частных случаях. Есть даже особый класс задач для собеседований, нужный чтобы подловить кандидатов на незнании этих правил. В векторных языках, напротив, основное правило одно — вычисления производятся справа налево, логичным исключением из этого правила являются скобки и управляющие конструкции типа if-then-else.

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

Модификаторы функций

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

В нашем языке я буду называть эти модификаторы суффиксами, поскольку они будут добавляться в конец к названию функции. Общий их вид следующий:

модификатор действия + опциональные аргументы + название + опциональный индикатор монадности

Где модификатор действия это »/» или »\» (об этом ниже), а индикатор монадности — »:». Индикатор монадности нужен для тех случаев, когда мы хотим вызвать функцию с одним аргументом, но из контекста это неясно. Т.е. в общем случае функция с суффиксом выглядит так:

fn/[args]suffix:

map

Рассмотрим самые важные суффиксы, и тогда их смысл станет понятнее. Например, суффикс map:

f/map[a1;..;an]; x f/map y; f/map x

Это классическая функция, которая в наше время есть во всех языках. Смысл ее в том, чтобы вызвать f последовательно для всех элементов списков одинаковой длины a1,…, an с одинаковыми индексами. Однако суффикс map имеет важное отличие — любой аргумент может быть атомом. Если все аргументы атомы, то f/map эквивалентно просто f. Примеры:

1 +/map 1 2 3 -> 2 3 4
1 2 3 */map 2 3 4 -> 2 6 12
1 {x+y}/map 1 -> 2

APL и J допускают для map дополнительный аргумент — rank (дальнейшее является переносом этой идеи в наш язык, а не буквальным описанием). Просто map имеет бесконечный ранг, что значит, что функция применяется непосредственно к элементам списка. 0-й ранг значит, что функцию необходимо применить к атомарным значениям, 1-й — к векторам, 2-й к матрицам и т.д. Можно допустить и отрицательные значения, чтобы указывать ранг с другой стороны, т.е. количество map в сложном суффиксе »/map/map/…/map». Это бывает удобно, когда мы хотим применить функцию к элементам сложной структуры. Например:

// хотим применить f к элементам матрицы
f/[0]map matrix ~ f/map/map matrix ~ f/[-2]map matrix

Также понятие ранга полезно для понимания действия базовых операторов и функций в векторном языке. Многие из них по умолчанию имеют суффикс »/[0]map». Например,»+» на самом деле »+/[0]map», т.е. он принимает в качестве аргументов любые структуры, которые можно сложить. Действие map определяется в таком случае рекурсивно — к атомам применяется сама функция, в остальных случаях применяется рекурсивно f/[0]map. Например:

(1;1 2;1 1) + (10 20;10;1 1) -> (11 21;11 12;2 2)  // аргументы конформны, т.е. имеют совместимую форму
1 2 + 1 2 3 -> exception                          // а так нельзя, длина спиcков должна быть одинакова

fold

Следующий суффикс — это, конечно, reduce, он же fold или свертка:

f/fold[a1;..;an] или f\fold[a1;..;an]

Для одного аргумента вызов fold эквивалентен подставлению f между элементами массива:

a[n-1] f ... f a[1] f a[0]

Классический пример — это суммирование элементов списка:

+/fold 1 2 3 -> 6

fold легко расширяется на произвольное число аргументов. Любой аргумент, как и в случае map, может быть атомом. Есть два варианта fold: /fold и \fold. Разница в том, что мы хотим получить в конце — только финальный результат или также все промежуточные. Сравните, например:

+/fold 1 2 3 4 -> 10
+\fold 1 2 3 4 -> 1 3 6 10

Иногда бывает полезно передать в fold начальное значение, используем для этого параметр суффикса:

+/[100]fold 1 2 3 -> 106

left, right

Также очень полезны суффиксы left и right. Это разновидности map для двух аргументов:

x f/right y ~ f[x]/map y
x f/left y ~ f[;y]/map x // запись f[;y] означает, что один аргумент пропущен.

Эти суффиксы нужны в ситуациях типа:

// строка – это массив, поэтому просто map использовать нельзя
"Mr. " ,/right ("John";"Bill") ~ ("Mr. John";"Mr. Bill")  

Поскольку left и right — это разновидности map, то логично добавить в них поддержку рангов. В первую очередь потому, что некоторые базовые функции неявно определяются с рангом 0. Например, функция поиска в массиве:

a ? b ~ a ?/[0]right b // возвращает индекс в "a" для каждого атома в "b"
1 2 3?(1 2;2 3) ~ (0 1;1 2)

Обобщенное индексирование и присваивание

Определив базовые суффиксы, мы можем более ясно и точно описать другие важные особенности векторных языков, например, индексирование.

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

// обычное индексирование, i - число
a i ~ a idx i ~ a[i]                                       
// обобщенное индексирование, один уровень, ii - вектор или атом чисел
a ii ~ a[ii] ~ a idx/right ii
// индексирование вглубь, рекурсивное определение. i1,i2,.. - атомы или вектора чисел
a[i1;i2;...] ~ a didx (i1;i2;...) ~ a[i1] didx/left (i2;..)

Отметим разницу между idx и didx. Первый — это поверхностный (shallow) индекс, второй — индекс вглубь. На idx логично навесить неявный суффикс »/[0]right», чтобы можно было индексировать с помощью любых структур.

Например, если «a» — это изображение, то вычислить все конволюции (свертки, основная операция в сверточных нейронных сетях — CNN) с помощью функции «f» можно таким выражением:

b = (0 1 2;0 1 2)                  // квадрат 3x3
a[0 1 2;0 1 2] ~ a didx b          // подматрица 3x3 в a
c = til count[a]-2                 // допустимые индексы, til n ~ 0 .. n-1
c {f a didx b+(x;y)}/right/left c  // конструкция /right/left – это декартово произведение, результат которого – матрица всех пар из c

Для такой полезной функции как didx неплохо бы иметь свой собственный суффикс. Назовем его set:

// f\[i1;..;in]set[a;b;..] определим как
v=a; v[i1;..;in] = f/[neg n]map[a[i1;...;in];b;..]; v

Выражение выглядит запутанно, но суть его проста. Мы выбираем подмножество «a» с помощью глубокого индекса i1…in, после чего вызываем функцию f спустившись на глубину индекса, т.е. f вызывается отдельно для каждого элемента, который мы индексируем, а остальные аргументы разлагаются на части согласно правилам map (т.е. они должны быть конформны форме индекса). set возвращает копию «a», где проиндексированные элементы заменены результатом функции. set является обобщением присваивания, поскольку позволяет менять не только переменные, но и любые значения:

// присвоить центральному квадрату матрицы значение 1
(0 0 0 0;0 0 0 0;0 0 0 0;0 0 0 0) =\[1 2;1 2]set 1

Часто при присваивании мы хотим также вызвать какую-нибудь функцию:

a[1 3] += 10 // прибавить 10 к элементам с индексами 1 и 3

Такой синтаксис позволяет вызывать некоторые встроенные функции, но не произвольные. set решает эту проблему, если мы сделаем одно допущение:

a +\[1 3]set 10 // присваивание
a +/[1 3]set 10 // просто выражение
neg/[1 3]set a  // унарный вариант присваивания, изменить знак элементов 1 3

Т.е. добавим правило, что если слэш указывает на переменную, то изменение происходит в самой переменной (in place), если нет, то в функцию передается ее копия. С помощью такого set можно коротким выражением описать программу, которая займет не один десяток строк кода на обычном языке.

Например, пусть у нас есть массив чисел «a», и есть список апдейтов. Каждый апдейт это функция + индексы в «a», к которым ее нужно применить, + значения. Разделим апдейты на три части — массив функций «fn», массив соответствующих им индексов «ii» и массив значений «v». С помощью set все апдейты можно применить одной строкой:

{a x\[y]set z}/fold[fn;ii;v]

Практический пример

Того, что мы уже знаем о векторных языках достаточно, чтобы решить вполне практическую задачу. Представим, что у нас есть котировки неких товаров (например, акций) — price — и объем предложения для каждой цены — volume. Нам поступает заявка от клиента — order — купить столько-то товара по самой выгодной цене:

price = (100 102 103;200 201;300 310 320 330)
volume = (10 9 12;5 6;30 25 20 22)
order = (8;20;45)

Необходимо посчитать: а) сколько реально каждого товара будет продано б) сколько придется заплатить с) убрать проданное из цен и объема. Остановитесь и подумайте минуту, как бы вы реализовали этот алгоритм на своем любимом языке. Так вы четче почувствуете контраст с векторным подходом.

Нам понадобится функция where, которая вычисляет индексы ненулевых элементов:

where 0 1 1 -> 1 2
a where a=1        // она используется в основном для фильтрации массивов
a filter a=1       // в APL/J используется ее бинарный аналог, который сразу фильтрует аргумент

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

total = +/fold ,/fold: price * v=0 min volume + 0 max order -\fold/map volume
sold = +/fold/map v
volume = volume app/map ii= where 0 < volume= volume - v // x app y ~ x[y]
price = price app/map ii

Самая сложная часть, пожалуй, это вычисление переменной v, поэтому я покажу, что происходит для одного заказа по шагам:

// выполняем заказ, когда числа становятся отрицательными, он выполнен
45 -\fold 30 23 20 22 -> 15 -10 -30 -52
// убираем те предложения, которые полностью исчерпаны
0 max  -> 0 -10 -30 -52
// теперь положительные числа - это то, что попало в заказ
volume +  -> 30 15 -10 -30
// убираем отрицательный мусор и получаем количество реально проданного для каждого предложения
v=0 min  -> 30 15 0 0
// теперь, чтобы определить сколько было продано товара типа 2, достаточно сложить полученные числа
+/fold v -> 45
// чтобы получить сумму, нужно умножить на цены и сложить
+/fold price[2] * v -> 13650

Наконец, чтобы обновить volume и price, нужно просто вычесть выполненный заказ и отфильтровать нулевые значения. Заметим, что трудоемкую фильтрацию можно выполнять не для каждого заказа. Нашему алгоритму безразличны нулевые предложения, и на сложность вычислений они почти не влияют.

Для простоты я взял order той же длины, что и price/volume. На практике order будет значительно короче, как же поменяется программа:

iorder=0 2; order=8 45 // каким-то образом нам заданы индексы order
total = +/fold ,/fold: price[iorder] * v=0 min vo + 0 max order -\fold/map vo=volume iorder
sold = +/fold/map v
volume[iorder] = vo app/map ii= where 0 < vo= vo - v
price app\[iorder]set ii // для разнообразия используем didx

Как видите, изменений почти нет. Для полноты я приведу реальную программу на Q:

total:(+/) (,/) price[iorder]*v:0|vo + 0&order -\' vo:volume iorder
sold: (+/') v
volume[iorder]: vo @' ii:where each 0 < vo:vo - v
@[`price;iorder;@;ii]

Другие суффиксы

map/fold/set и их вариации являются самыми важными и часто используемыми суффиксами, однако есть и другие, без которых не может обойтись ни один векторный язык. В первую очередь это итерационные суффиксы, аналоги циклов while/for:

// вызвать f[a1;..;an] N раз, если аргументов больше одного, то f должна возвращать список
f/[N]for[a1;..;an]
// predicate - функция с тем же количеством аргументов, что и f. Вызывать f до тех пор пока predicate возвращает значение не равное 0
f/[predicate]while[a1;..;an]

Простые примеры использования:

last {(y;x+y)}/[10]for[0;1]      // вычислить 12-е число Фибоначчи
f/[0

// f вызывается до тех пор, пока не вернет либо первоначальные аргументы, либо значение с предыдущего шага
f/over[a1;..;an]

rotate[1]\over 0 0 0 0 1       // получить матрицу с единицами на второй главной диагонали
sqrt={{0.5*y+x/y}[x]/over x/2} // вычисление квадратного корня sqrt(a) ~ x=0.5*x+a/x

// вызвать f для всех пар значений в векторе v -> (f[v 0;val];f[v 1;v 0];f[v 2;v 1];...)
f/[val]prior v 

differ = {not ~/prior x}  // вернуть для x массив, где 1 помечает элементы отличающиеся от предыдущего
deltas = -/prior          // вернуть дельты соседних значений

f/inv // вызвать функцию "обратную" к f

x f/swp y ~ y f x; f/swp x ~ x f x

f/[size]memo // запоминать результаты для ускорения вычислений в кеше определенного размера

f/[value]trap // в случае исключения вернуть value
f/[fn]trap    // или вызвать exception handler

f/async // аналог async f(..) для вызова асинхронных функций

til N               // til 5 -> 0 1 2 3 4, создать последовательность чисел от 0 до N-1
N take M            // 10 take 1; 10 take 0 1 2; -2 take til 5 – создать массив из N элементов, элементы брать последовательно из источника M (при отрицательном N с конца)
(n1;…;nk) take M    // создать k-мерную матрицу (логичное обобщение)
N drop M            // 2 drop 1 2 3; -2 drop 1 2 3 – убрать N элементов из начала/конца M
(n1;n2;..;nk) cut M // разрезать M на части по индексам n1…nk

5 5 take 1 0 0 0 0 0            // матрица 5x5 с 1 на главной диагонали
1 drop/map (where a==”@”) cut a // разрезать a на части, начинающиеся на @, убрать @

txt 2*til (count txt=(where 0 =/prior 0

extract={{x =/set[;4 7] "/”} x where "0000-00-00"~/right (m dict "---",10 take "0") x=x (where 1<-2 -/prior w) cut w=where x in m="-/.0123456789"}
// -/prior вычисляет дельты соседних элементов, т.е. "1 ("2010/10/10";"2020/12/13")

"\n” split str; "\n” join str // самый очевидный способ использования
10 split num; 10 join 1 2 3 4 // разобрать/собрать число в 10-ной системе счисления (или любой другой)
24 60 60 1000 split 36938567  // для каждого разряда можно указать свой модуль (в данном случае разбираем на части время)

v where 0sort={x iasc x} // сама функция сортировки легко определяется через iasc

// сортируем 0..n-1 по каждой колонке с конца
msort={x app\left til[count x 0] {x iasc y}/fold reverse x} 

x iasc x mod 10 // например, по последней цифре

// фактически обратная функция к sort, если y=sort a, то a~a unsort y    
unsort={y iasc iasc x} 

a=11 2 6 15 6 18 19
// разделим на две группы (a>10), посчитаем +\fold для каждой
g=+\fold/map (where differ g i) cut a i=iasc g=a>10 
// теперь, чтобы восстановить первоначальный порядок, достаточно второй раз применить iasc
(,/fold g)iasc i -> 11 2 8 26 14 44 63

group={u dict where x ==/right u=distinct x}
group 0 1 2 1 0 1 -> 0 1 2 dict (0 4;1 3 5;list 2)

// все fold map и т.д. при аргументе словаре работают со списком его значений
// f/fold d ~ f/fold value d; f/map d ~ (key d) dict f/map value d
(,/fold +\fold/map a g) iasc ,/fold g= group a>10 

q (,/fold g) iasc ,/fold til/map count/map g=group u

qsort=: (($:@(<#[), (=#[), $:@(>#[)) ({~ ?@#)) ^: (1<#)

qsort={{(x y filter yv:y rand count y}[self]/[1

qsort={if 1v:y rand count c else x end}

qsort:{$[1<#x;(f xe:*1?x;x]}

life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

a (f . g) b ~ f/fold a g/map b

a (f . g) b ~ a {f/fold x g/map y}/right/left flip b

life = {(x min a==4) max 3==a=+/fold ,/fold: -1 0 1 rotate/left/right -1 0 1 rotate/right/left x}

{(x&a=4)|3=a:sum raze -1 0 1 rotate\:/:-1 0 1 rotate/:\: x}