Векторные языки мало известны широкому кругу программистов и занимают узкую нишу обработки данных в финансах, статистике и прикладной математике. Хотя сам векторный подход (или, точнее, программирование с помощью массивов) распространен гораздо шире, чем может показаться. Он реализован в известных библиотеках (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 кита векторных языков
Все векторные языки основаны на нескольких базовых принципах, которые сильно выделяют их из общей массы языков:
Порядок выполнения операций.
Особые модификаторы функций.
Опора на индексирование и структурно-полиморфные базовые функции.
Я не включаю в этот список специальные знаки для обозначения базовых операций, хотя именно они являются первым, что бросается в глаза при знакомстве с векторным языком. Дело в том, что только в 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 -> 2APL и 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 -> 6fold легко расширяется на произвольное число аргументов. Любой аргумент, как и в случае 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 -> 106left, 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 <val> -> 0 -10 -30 -52
// теперь положительные числа - это то, что попало в заказ
volume + <val> -> 30 15 -10 -30
// убираем отрицательный мусор и получаем количество реально проданного для каждого предложения
v=0 min <val> -> 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<count a]for a // аналог "if condition then f[a] else a", используется в J
processSomeA/[{count x}]while a // processSomeA обрабатывает a пока там что-то естьЕще один более экзотический суффикс - это over:
// 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Поскольку все итерационные суффиксы производят промежуточные результаты, то с ними можно использовать модификатор "\" (вернуть промежуточные результаты).
Крайне полезен также суффикс prior:
// вызвать 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Аналог этого суффикса есть в J. Нужно, чтобы в языке была возможность определить функцию обратную к f. sqrt vs x^2; sin vs arcsin; zip vs unzip и т.п.
Поменять аргументы местами:
x f/swp y ~ y f x; f/swp x ~ x f xЭтот суффикс тоже из J, крайне полезен для устранения лишних скобок.
Суффикс memo:
f/[size]memo // запоминать результаты для ускорения вычислений в кеше определенного размераСуффикс trap:
f/[value]trap // в случае исключения вернуть value
f/[fn]trap // или вызвать exception handlerАсинхронность:
f/async // аналог async f(..) для вызова асинхронных функцийТакже можно пофантазировать о пользе метасуффиксов, т.е. суффиксов, модифицирующих поведение других суффиксов. Пара таких уже имеется - "\" и "/". Полезны были бы в том числе метасуффиксы, изменяющие направление вычислений - reverse и flip. Они были бы полезны в паре с fold - делать все тоже самое, но с конца аргументов в начало, и делать все тоже самое, но поперек массива т.е. вдоль колонок, а не строк.
Еще один метасуффикс – parallel. Его можно было бы применять в паре с map/right/left и т.п., чтобы распараллелить вычисления. В Q версии 4.0+ многие базовые операции снабжены этим суффиксом в неявном виде, что позволяет существенно ускорить обработку больших массивов.
Структурно полиморфные функции
Это функции, которые некоторым образом трансформируют структуру данных. В отличие от обычных языков, в векторных такие функции являются центральными, потому что операции, как правило, производятся с массивами, матрицами и другими сложными структурами данных. Выше мы уже применяли некоторые такие функции на практике (where), а индексирование само по себе является такой операцией. Дальше я опишу некоторые типичные функции подобного плана.
Функции til/take/drop/cut
Это центральные функции для любого векторного языка, они необходимы для создания и изменения формы массивов.
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<count/map txt) cut txt) div 2Т.е. найти места, где пустая строка меняется на непустую и наоборот, разрезать текст на части и выкинуть каждый второй кусок.
Выделить из текста даты в формате DDDDXDDXDD, где X – это одно из “-/.”, привести X к стандартной форме “/”:
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<deltas idx” вычисляет места, где индекс не возрастает на 1 - места разрыва
// -2 в prior, чтобы первая разность была больше 1, а следовательно индекс 0 попал в результат
// словарь (m dict "---",10 take "0") по сути является функцией, которая отобразит числа в 0, разделители в -, а остальные символы в символ по умолчанию (в Q это пробел)
extract "On 2010.10.10 and 2020-12-13 at 10:00:00.0" -> ("2010/10/10";"2020/12/13")Заметьте, как часто используется индексирование в том числе с помощью словаря. Этот прием уникален для векторных языков и позволяет реализовывать алгоритмы необычным образом.
Функции split/join
Эти функции, обычно, есть во всех языках. В векторных они сильно перегружены по первому аргументу и выполняют все возможные операции по слиянию и разбиению массивов. Некоторые из них:
“\n” split str; “\n” join str // самый очевидный способ использования
10 split num; 10 join 1 2 3 4 // разобрать/собрать число в 10-ной системе счисления (или любой другой)
24 60 60 1000 split 36938567 // для каждого разряда можно указать свой модуль (в данном случае разбираем на части время)Перепишем разбиение на абзацы с помощью split (пусть текст нам задан одной строкой):
v where 0<count/map v=“\n\n” split txtСортировка
В векторном языке предпочтение отдается функции, которая не сортирует массив, а возвращает индексы для его сортировки – iasc:
sort={x iasc x} // сама функция сортировки легко определяется через iasciasc намного полезнее просто sort. Например, с ее помощью можно легко реализовать сортировку по нескольким колонкам:
// сортируем 0..n-1 по каждой колонке с конца
msort={x app\left til[count x 0] {x iasc y}/fold reverse x} Отсортировать, согласно какой-нибудь функции:
x iasc x mod 10 // например, по последней цифреВыражение “iasc iasc x” вернет нам для каждого элемента x его место в отсортированном массиве. Cоответственно, если мы применим этот индекс к уже отсортированному другому массиву y, то перемешаем его точно таким же образом, как x:
// фактически обратная функция к sort, если y=sort a, то a~a unsort y
unsort={y iasc iasc x} Или более обще – мы можем перемешать любой массив y согласно массиву x. Например, если мы хотим сделать что-то с подгруппами массива, но не менять при этом порядок элементов (т.е. аналог update … group by …):
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 возвращает словарь, где ключи – уникальные элементы массива, а значения - их индексы в нем. Схематично ее можно определить через наши примитивы так:
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)С помощью group выражение выше можно записать более просто:
// все 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 Функция group почти эквивалентна group by в SQL, но она очень удобна и сама по себе. Например, пусть есть очередь задач (q) от разных пользователей (u). Мы хотим упорядочить ее так, чтобы все пользователи были равны:
q (,/fold g) iasc ,/fold til/map count/map g=group uСгруппируем по имени пользователя, каждой задаче назначим приоритет в виде числа (til + count), отсортируем все задачи по приоритету и индексами применим этот порядок к q.
Практические примеры
В завершение я разберу несколько программ на настоящих векторных языках. Вы убедитесь, что, несмотря на их жуткий вид, их можно практически один в один переписать на нашем игрушечном языке.
Сортировка на J
Часто приводится следующий пример сортировки на J, выглядящий как бессмысленный набор знаков:
qsort=: (($:@(<#[), (=#[), $:@(>#[)) ({~ ?@#)) ^: (1<#)На самом деле точно такой же алгоритм часто приводят для демонстрации возможностей других языков (Haskell, например). Если переписать его буквально на наш язык, то получим:
qsort={{(x y filter y<x),(y filter y=v),x y filter y>v:y rand count y}[self]/[1<count x]for x}Или более по-человечески:
qsort={if 1<c:count x then (self y filter y<v),(y filter y=v),self y filter y>v:y rand count c else x end}Нельзя даже сказать, что он как-то сильно подчеркивает достоинства J, потому что на Haskell он выглядит практически также. На K эта функция выглядит так:
qsort:{$[1<#x;(f x<e),(x@&:x=e),(f:.z.s x@&:)x>e:*1?x;x]}Как видите, тяга J к знакам и функциям без переменных не сильно помогает уменьшить длину выражений.
Игра Жизнь на APL
В примерах для APL приводится следующая программа для вычисления одного шага в игре жизнь:
life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}Кратко напомню правила. Есть прямоугольное поле из живых и мертвых клеток (1 vs 0). На каждом шаге: a) в пустой клетке, у которой ровно 3 соседа, зарождается жизнь б) живые клетки, у которых меньше двух или больше 3 соседей, погибают от одиночества или перенаселенности. Соседи - это 8 клеток вокруг заданной клетки, плюс сама клетка.
Обратите внимание, что знаки APL хоть и необычны, но выглядят гораздо лучше ASCI мешанины в J. Увы, но изящность нотации APL нельзя повторить с помощью стандартного набора символов.
В данной программе несколько раз используется так называемое внешнее и внутреннее произведение (точка), которое является обобщением умножения матриц, векторов и т.д. Для векторов это просто:
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}Программа, почти один в один эквивалентна APL программе - поворачиваем матрицу 3 раза по строкам, затем 3 раза каждую из этих трех по столбцам, выравниваем массив, т.е. получаем список из 9 матриц, суммируем их, получая число соседей, включая статус самих клеток и потом проверяем правила.
Для сравнения тот же алгоритм на Q:
{(x&a=4)|3=a:sum raze -1 0 1 rotate\:/:-1 0 1 rotate/:\: x}