Блог компании технологический центр дойче банка

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

Введение

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

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

Язык "Вектор"

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

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

// для комментариев будем использовать обозначение как в C10; -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 -> inta[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 41 2 3 */map 2 3 4 -> 2 6 121 {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 yx 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)                  // квадрат 3x3a[0 1 2;0 1 2] ~ a didx b          // подматрица 3x3 в ac = til count[a]-2                 // допустимые индексы, til n ~ 0 .. n-1c {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 2a where a=1        // она используется в основном для фильтрации массивовa filter a=1       // в APL/J используется ее бинарный аналог, который сразу фильтрует аргумент

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

total = +/fold ,/fold: price * v=0 min volume + 0 max order -\fold/map volumesold = +/fold/map vvolume = 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 // каким-то образом нам заданы индексы ordertotal = +/fold ,/fold: price[iorder] * v=0 min vo + 0 max order -\fold/map vo=volume iordersold = +/fold/map vvolume[iorder] = vo app/map ii= where 0 < vo= vo - vprice app\[iorder]set ii // для разнообразия используем didx

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

total:(+/) (,/) price[iorder]*v:0|vo + 0&order -\' vo:volume iordersold: (+/') vvolume[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 возвращает значение не равное 0f/[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", используется в JprocessSomeA/[{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 // в случае исключения вернуть valuef/[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-1N 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 на части по индексам n1nk

Некоторые примеры:

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} // сама функция сортировки легко определяется через iasc

iasc намного полезнее просто 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}

Это третья часть рассказа про опционы, где мы поговорим про биномиальную модель, риск-нейтральную меру и разберёмся, как рассчитать цену опциона.

Если вы пропустили наш подробный рассказ про опционы, вот ссылки на предыдущие части:
Что такое опционы и кому это нужно. Ликбез для гика, ч. 6
Опционы: пут-колл парити, броуновское движение. Ликбез для гика, ч. 7

Данный пост основан на расшифровке моих видеолекций Одношаговая биномиальная модель и Расчет опциона, созданных в рамках курса Finmath for Fintech.

Одношаговая биномиальная модель. Можно ли считать цену опциона как математическое ожидание дисконтируемой выплаты? Что может пойти не так?

Следующее понятие, которое необходимо обсудить, риск-нейтральная мера. Это понятие в общем виде требует не-школьной математики, поэтому, как и ранее, мы не будем что-то доказывать в общем виде. Вместо этого начнем с очень простого примера (даже может показаться, что он слишком простой и вообще не имеет никакого отношения к реальным моделям для нашей темы). На этом примере мы увидим, как работают термины, а все результаты, которые мы получим, будут верны и в более общем случае.

Мы рассматриваем биномиальную модель с дискретным временем. У нас есть два момента времени, в которых наблюдается рынок: t₀ и t₁, есть некий рисковый актив, т.е. он содержит в себе риск. Его цена в момент t₀ равна 50. И есть два варианта развития события в будущем (поэтому модель и называется биномиальной): цена может увеличиться до 100 или упасть до 25. Это наш рисковый актив, в котором есть некоторая неопределенность. Также нам в нашей модели нужен некоторый безрисковый актив, аналог банковского счета в надёжном банке. Предположим, у нас риск-нейтральная ставка 20% и, значит, деньги, положенные в момент времени t₀ на депозит в количестве 50 в момент времени t₁ дадут выплату 60.

В нашей модели есть некоторые вероятности. Обозначим их: p вероятность того, что актив увеличится в цене, и вероятность того, что актив в цене уменьшится: 1-p.

Если бы мы работали с активом, в котором нет никакой неопределенности, то цена такого актива в момент времени t₀ была бы просто дисконтированной выплатой в момент t₁, как это есть для безрискового актива. Но у нас есть два варианта с некоторой неопределенностью. Логично выглядит предположение о том, что, используя эти вероятности, мы бы могли просчитать математическое ожидание от дисконтированной выплаты какого-то производного продукта. Если мы рассмотрим колл-опцион на такой риск базовый актив, то его цена, наверное, будет равна математическому ожиданию дисконтированной выплаты в момент времени t₁:

Это наше предположение.

Тут D₁ коэффициент дисконтирования из момента t₁ в момент t₀. Посчитаем, чему будет равно записанное выше выражение. Для определенности давайте скажем, что страйк этого опциона K равен 70. Тогда у нас есть все данные, чтобы посчитать мат. ожидание.

Проверим, работает ли наше предположение. Мы сделаем так: составим некоторый портфель из опциона, базового актива в момент t₀ и рассмотрим его выплату в момент t₁. Составим портфель следующим образом. Мы продаем 15 колл-опционов и покупаем 6 штук базового актива. Берем в долг 125 единиц денег. Такие вот магические цифры, чуть попозже мы увидим, откуда они берутся, как их можно посчитать, но пока это просто выбранные константы. В момент времени t₀ изменение нашего баланса будет выглядеть следующим образом:

Мы получаем прибыль за 15 опционов: +15С₀; платим за шесть единиц базового актива по цене 50: -6*50; получаем: +125 денег.

Далее следует момент времени t₁ и два возможных варианта: когда цена актива (S₁) стала 25 и когда цена актива стала 100. В первом случае, когда цена стала 25 при страйке 70, опцион ничего не стоит. Когда цена стала 100, и мы продали 15 опционов, нам нужно заплатить премию -15*(100-70). Приобретенные шесть единиц базового актива у нас на балансе, мы можем их продать и получить деньги по текущему курсу 6*25 или 6*100 соответственно тому, какая цена реализовалась. Наш долг увеличивается согласно процентной ставке, и мы получаем выплату, в обоих случаях одинаковую, которая не зависит от цены актива: -150. Теперь сложим все числа, которые у нас получились на момент времени t_1. Как видим, в обеих колонках получаем ноль. Это связано с тем, что изначально цифры были специально подобраны.

В момент времени t₁ независимо от того, какой сценарий реализуется, портфель, составленный таким образом, стоит ноль. Следовательно, в момент времени t₀ он тоже должен стоить столько же ноль. Мы опять используем условие отсутствие арбитража на рынке.

Приравняв эту сумму к нулю, мы получаем цену опциона:

Мы видим, что результат 11,6 не совпадает с тем, что получили ранее: 12,5. Этот, казалось бы, интуитивно верный результат не сработал. Составив специальный портфель, мы увидели, что, если бы цена на колл-опцион была 12,5, это бы как раз и означало наличие арбитража на рынке. То есть при такой цене на колл-опцион можно было бы зарабатывать деньги без риска. Давайте разберемся, почему же так получилось.

Одношаговая биномиальная модель. Расчет опциона. Риск-нейтральные вероятности

Чтобы проанализировать полученный результат, давайте немного обобщим модель и будем работать уже не с фиксированными числами, а с какими-то параметрами. Обозначим текущий курс рискового актива как S, введем параметр d и параметр u. У нас к моменту времени цена t₁ рискового актива может пойти либо вниз в d раз, либо вверх в u относительно текущего уровня. Цена безрискового актива по-прежнему определяется некоторым дискаунт-фактором.

Заметим, что по построению параметры модели заданы так, что d<D₁^-1<u (см. рис. 4).

По поводу составления портфеля следует заметить, что мы сразу можем поделить весь портфель на номинал нашей позиции в опционах. Это, возможно, даст нам дробные номиналы в каких-то других позициях, но мы разрешаем себе с этим работать в рамках нашего математического анализа. Мы будем работать с любыми действительными числами как с положительными, так и с отрицательными. В рамках практики рынка отрицательные позиции соответствуют short selling, и могут быть определенные ограничения на такие позиции, но мы этим в нашем тоже анализе пренебрегаем.

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

Купим какое-то количество x базового актива S и возьмем в долг какое-то количество денег, такое, чтобы получить выплату ровно y. Мы его дисконтируем на момент t₀ и получаем D₁y. Мы берем в долг D₁y, а выплатить в момент t₁ нам нужно будет y. Т.е. для баланса это будет сумма -y.

В случае с базовым активом мы покупаем на сумму xS. У нас возможны два случая: когда цена пошла вниз S₁=d*S и когда цена пошла вверх S₁=u*S. Соответственно, наша позиция будет стоить x*d*S или x*u*S. И мы продаем один колл-опцион, в начальный момент времени мы за него получаем премию C₀. В момент времени t₁ мы обязаны сделать выплату по этому опциону, так как взяли на себя это обязательство: -C_d и -C_u соответственно.

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

Эта система из двух уравнений с двумя неизвестными имеет решение. Вычтем одно уравнение из другого, чтобы сразу получить значение x.

Подставляя значение x, можно найти y.

По построению этих уравнений такие значения x и y дают нам в обоих возможных вариантах цену портфеля, равной нулю. Рассуждая точно так же, как и в прошлый раз, портфель на expiry в момент времени t₁ стоит ровно ноль, независимо от того, какая цена базового актива реализуется на рынке. Следовательно, этот портфель должен стоить ноль и в момент t₀, по условию отсутствия арбитража. Таким образом, мы получаем уравнение для цены колл-опциона в начальный момент времени. Запишем выражение для цены колл-опциона C₀ в момент времени t_0, используя наше решение.

Где q новый параметр, который выражается через известные нам коэффициенты:

По построению, так как мы задали параметры u, d и дискаунт-фактор D₁^-1 так, как показано на рис. 4, то значение q лежит в диапазоне от нуля до единицы. То есть в диапазонах, доступных для значений вероятности.

В слагаемом с C_u мы используем q, а для выплаты C_d при движении вниз мы используем (1-q). То есть формулу можно переписать как вычисление математического ожидания, но используя уже не вероятность p, которая соответствует реальной вероятности того, что произойдет на рынке, а некоторую синтетическую вероятность, которая определяется формулой для q. Иначе говоря, мы получили математическое ожидание дисконтированной выплаты, но используя уже некоторые другие вероятности. Это и является вычислением математического ожидания в риск-нейтральной мере.

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

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

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

Многошаговая биномиальная модель

Подход, описанный здесь для рассуждения про риск-нейтральные вероятности, стал популярен благодаря статье Cox, J. C.; Ross, S. A.; Rubinstein, M. (1979). Option pricing: A simplified approach. Такой подход помогает решить сразу несколько важных проблем.

Во-первых, после публикаций статей Блэка, Шоульца и Мертона в 1973 году появилось успешная, быстро и широко принятая теория прайсинга опционов. Эту теорию нужно было преподавать в университетах. В том числе MBA-студентам и студентам экономических факультетов. Но разделы математики, которые используются для рассуждений, в общем виде в стандартную программу не входят. Даже сегодня и даже для студентов технических специальностей. А преподавать как-то нужно. Ведь MBA-программа это не только красивый диплом для студентов, но и дополнительный заработок для преподавателей математики.

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

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

Далее можно математически проанализировать предельный случай при N . Что и было сделано авторами статьи. Если правильно выбрать параметры u и d, тов пределе решётка будет приближаться к логнормальному распределению. Т.е. в пределе получаем модель Блэка-Шоульца.

Математический анализ такого предельного случая рассматривать не будем, просто приведём некоторую визуализацию. На рис. 7 и 8 нарисованы решетки при больших значениях N. В отличии от рис. 6 нарисованы только точки, показывающие возможные значения, линий между ними нет, чтобы можно было разглядеть детали.

Все статьи этой серии:

Стоимость денег, типы процентов, дисконтирование и форвардные ставки. Ликбез для гика, ч. 1
Облигации: купонные и бескупонные, расчет доходности. Ликбез для гика, ч. 2
Облигации: оценка рисков и примеры использования. Ликбез для гика, ч. 3
Как банки берут друг у друга в долг. Плавающие ставки, процентные свопы. Ликбез для гика, ч. 4
Построение кривой дисконтирования. Ликбез для гика, ч. 5
Что такое опционы и кому это нужно. Ликбез для гика, ч. 6
Опционы: пут-колл парити, броуновское движение. Ликбез для гика, ч. 7

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

В основу этой статьи легли четыре мои видеолекции из курса Finmath for Fintech, которые можно найти на YouTube: Основное уравнение теории ценообразования, Стохастический коэффициент дисконтирования, Связь цен и корреляции рисков и Избыточная доходность. Риски.

Основное уравнение теории ценообразования

Для начала рассмотрим некоторую игрушечную задачу. Начнем с воображаемого инвестора, который думает, сколько ему потратить сегодня, сколько ему вложить, чтобы получить какую-то прибыль завтра. У него есть горизонт планирования, состоящий из двух дней: сегодня t и завтра t+1. Предположим, поначалу наш инвестор был ленив и потреблял все, что он получал. Назовем это ситуацией потребителя П. Потребитель получает какую-то зарплату e_t (какой-то доход earnings) и всю ее потребляет с_t (consumption). Аналогично выглядит ситуация завтра:

c_t+1 = e_t + 1

Теперь, предположим, наш потребитель задумался о том, чтобы вложить часть своей зарплаты в какой-то актив (A), одна единица которого стоит p_t и который завтра принесет инвестору выручку в размере x_t+1. Нужно объяснить, почему мы обозначили цену сегодня и выручку завтра разными буквами. Дело в том, что цена сегодня это фиксированное число, она известна. В то время как x_t+1 (та выручка, которую принесет актив завтра) это случайная величина, не гарантированная: может быть больше, может меньше. Это рисковый инструмент. Предположим, что наш инвестор решил стать настоящим инвестором (И) и купить N штук этого актива. Тогда его потребление сегодня уменьшается:

с_t = e_t - Np_t

Но завтра его потребление увеличится, потому что он получит

с_t + 1 = e_t + 1 + Nx_t+1

Возникает естественный вопрос: лучше ли поведение инвестора (И), чем поведение простого потребителя (П)? Уточним вопрос. Какое значение N наиболее оптимально?

Чтобы ответить на это, нужно понять, что именно означает оптимально. То есть мы должны выяснить, какую функцию мы здесь оптимизируем. Мы можем смоделировать поведение инвестора, введя некоторую функцию полезности. Функция полезности или функция удовольствия зависит от уровня потребления. Запишем это. Если сегодня уровень потребления с_t, то сегодняшнее значение уровня полезности u(с_t). Соответственно, для завтрашнего уровня потребления u(с_t+1).

В нашей временной модели, состоящей из двух временных периодов сегодня и завтра, мы бы хотели, чтобы ответ на вопрос какое N является оптимальным? зависел от этих двух величин (u(с_t) и u(с_t+1)). Поэтому мы сейчас их объединим в одну общую функцию полезности. Наша общая функция полезности будет иметь следующий вид: потребление сегодня плюс бета, помноженная на математическое ожидание потребления завтра.

U = u(с_t) + E[u(с_t+1)]

Сегодняшнее потребление нам известно, потому что про сегодня у нас есть полная информация. Завтрашнее потребление зависит от того, какова будет величина с_t+1. А она включает в себя выручку от того же актива, в который мы вложились. В нашу общую функцию полезности входит ожидаемое удовольствие от потребления завтра. Случайная величина с_t+1 включает в себя доход от нашего актива, в который мы вложились, именно поэтому здесь стоит знак математического ожидания. Более того, мы дисконтируем это ожидаемое удовольствие на некоторый коэффициент , который можно назвать коэффициентом нетерпения (нам всегда хочется здесь и сейчас, чем в какой-то абстрактный момент времени завтра).

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

График функции U может выглядеть следующим образом:

Типичным вариантом будет функция такого вида:

Итак, наш инвестор хочет максимизировать общую функцию полезности, найти оптимальный уровень вложений N:

Umax

Условием первого порядка для решения этой оптимизационной задачи является условие равенства нулю производной.

Распишем выражение:

Давайте теперь посмотрим на это уравнение, на условие первого порядка, и решим его относительно цены актива сегодня p_t. Величины u'(c_t) и не являются случайными, они определены. Поэтому мы их можем внести под знак математического ожидания. Получим следующую формулу:

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

Из условий максимизации общей функции полезности мы получили уравнение установления цен в качестве условия первого порядка. Эти условия первого порядка представляют собой баланс между предельными издержками потребителя сегодня, оттого что он уменьшил свое потребление, и перед тем предельным удовольствием, которое он получит завтра за счет выручки от данного рискового актива x.

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

Стохастический коэффициент дисконтирования

Итак, у нас есть выражение:

Обозначим весь коэффициент перед иксом как m_t+1 и назовем его стохастический коэффициент дисконтирования. После этого наше уравнение установления цен примет более компактный вид:

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

Где R_f базовая процентная ставка (предполагаем, что базовая процентная ставка положительная, поэтому коэффициент дисконтирования 1/R_f меньше единицы и наша цена сегодня, естественно, чуть меньше, чем выручка, которую мы получим завтра).

Если убрать зависимость от индекса t, то можно записать уравнение установления цен в максимально компактном виде:

Если есть какие-то рисковые инструменты, тогда стоимость будет следующей:

Если рисковый инструмент имеет такую же ожидаемую доходность, что и безрисковый инструмент, разумно предположить, что, поскольку вложения в него связаны с некоторой неопределенностью, с определенным риском, его стоимость сегодня будет меньше. Полученное нами выше общее уравнение ценообразования можно рассматривать как обобщение этих ситуаций. Оно говорит, что все дополнительные поправки, связанные с риском, имеют своим источником один стохастический коэффициент дисконтирования, который является одним и тем же для всех рисковых и безрисковых инструментов. Для объекта m есть несколько разных названий: стохастический коэффициент дисконтирования, ядро ценообразования. Если математическое ожидание представить себе в виде интеграла, то тогда функция m выступает там в качестве ядра интегрирования. Все теории ценообразования так или иначе занимаются тем, что пытаются связать этот m с данными. То есть, если у вас есть какие-то данные, вы строите модель, как из них получить этот коэффициент m.

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

Простейший случай это вклад. У вас есть 1 рубль сегодня, и вы ожидаете какую-то доходность завтра R_t+1. Это может быть какая-то акция, у которой есть сегодняшняя цена p_t. Завтрашняя цена может быть какая-то иная, случайная величина p_t+1, плюс дополнительно владельцу этой акции могут быть выплачены какие-то дивиденды d_t+1 (цена и дивиденды, конечно, связаны). Это может быть какой-то бонд, у которого, наоборот, купон фиксированный 1, и тогда речь идет о том, какая у него цена сегодня p_t. Это может быть опцион, например колл-опцион. Вы покупаете его за некоторую сумму сегодня C_t, и он дает вам выручку, которая связана со страйк-ценой, с ценой актива по какой-то такой формуле из теории опционов: max(S_t - K, O). Во всех этих и многих других ситуациях (наш список можно продолжить) уравнение установления цен, полученное нами, применимо. С практической точки зрения вопрос заключается только в том, чтобы объяснить или предложить модель построения этого стохастического коэффициента дисконтирования m.

Связь цен и корреляции рисков

В нашей формуле установления цен присутствуют две случайные величины выручка нашего актива x и стохастический коэффициент дисконтирования m. Связь между этими двумя величинами можно померить, посчитав их ковариацию. Согласно известной формуле:

cov(m,x) = E[mx] - E[m]E[x]

Выражение E[mx] и присутствует в уравнении установления цен. Перепишем наше уравнение установления цен, выразив этот компонент через два остальных члена этого равенства:

p_t = E[m]E[x] + cov(m,x)

Само математическое ожидание стохастического коэффициента дисконтирования E[m] можно представить себе следующим образом. Если у нас есть безрисковый вклад, то есть мы вложили единицу, то тогда мы должны получить:

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

Теперь заменим математическое ожидание стохастического коэффициента дисконтирования E[m] на величину, обратную базовой процентной ставке:

Итак, что же у нас получилось? Сегодняшняя цена актива имеет две составляющие. Первая составляющая зависит только от самого актива (это, можно сказать, приведенное, с помощью базовой процентной ставки, к сегодняшнему дню математическое ожидание выручки нашего актива). Вторая составляющая, которая добавляется, связывает наш актив и коэффициент дисконтирования. Назовем вторую часть формулы cov(m,x)платой за риск. Она является поправкой к приведенной текущей стоимости, к первой части формулы. Давайте подумаем, какой может быть поправка. Она может быть как отрицательной, так и положительной. Это зависит от того, как наш актив скоррелирован со стохастическим коэффициентом дисконтирования. Давайте вспомним формулу для m и напишем это выражение чуть более подробно:

Величина u'_t(c_t) не является случайной.

Чем больше потребление, тем меньше становится производная функции u, то есть с увеличением потребления u'_t+1уменьшается. Если же наш актив ведет себя следующим образом: когда потребление увеличивается, наш актив тоже увеличивается (то есть это актив, который хорошо работает в ситуации, когда экономика и благосостояние растут), то тогда такой актив имеет отрицательную ковариацию cov(m,x). Наш актив становится дешевле. Когда наш актив является чем-то вроде страховки и, наоборот, хорошо работает, когда потребление падает, в тех ситуациях он приносит нам доход. А когда употребление растет, он не так хорош, его поведение, поведение этой случайной величины и поведение производной функции u' одинаковы эта величина положительная, и мы платим дополнительную величину.

Функция u вогнутая, чем больше растет потребление (consumption), тем производная этой функции меньше. Если величина x с ростом потребления увеличивается, то есть ведет себя как актив, который приносит хорошую прибыль, когда экономика растет, он скоррелирован отрицательно с величиной u', и тогда добавка, плата за риск, отрицательна. Какой в этом смысл? Если вы дополнительно инвестируете в такой актив,то ваш уровень потребления как пользователя становится более волатильным и для вас это приемлемо только в том случае, если цена этого актива будет с каким-то дисконтом (cov(m,x) будет снижать цену по сравнению с базовой стоимостью). И наоборот, когда актив это что-то вроде страховки (когда потребление падает) и ведет себя хорошо, то тогда он положительно скоррелирован с производной функцией u, и тогда у вас появляется дополнительная премия, которую вы платите, чтобы инвестировать в этот актив.

Избыточная доходность. Системный и идиосинкратический риск

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

Если мы умножим обе части этой формулы на базовую процентную ставку и перенесем ковариацию в левую часть, а единицу в правую часть, тогда получим следующую формулу:

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

Посмотрим, что нам еще дает уравнение установления цен, записанное в таком виде:

Рисковый актив x обладает некоторой волатильностью. Заметим, что в наше уравнение установления цен входит именно ковариация m и x, а не вариация случайной величины x. Например, если x и m скоррелированы слабо, значение ковариации практически равно нулю, то, несмотря на то что x может иметь очень большую или очень маленькую волатильность, цена p, согласно этому уравнению, будет той же самой и определяться компонентой формулы E[x]/R_f, фактически от E[x]. Из этого можно сделать вывод: важна волатильность случайной величины x сама по себе, а именно ее проекция на m. Можно записать, что x является суммой двух величин проекции величины x на m и всего остального:

Для проекции можно записать явную формулу:

Эта формула похожа на формулу, которая пишется для проекции одного вектора на другой в векторном пространстве. Что же касается ортогональной части , то ее ковариация с m равна нулю:

Случайная величина x, ожидаемая доходность актива, может иметь некоторую волатильность, то есть некоторый риск. При этом часть этого риска влияет на цену (является систематическим риском та часть, которая является проекцией на m). Другая же часть, хоть и является случайной, никак не влияет на цену и называется идиосинкратической. Риск какого-то инструмента, какого-то актива, всегда распадается на систематическую и идиосинкратическую части.

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

Основная сложность в применении этого уравнения в явном виде заключается в том, что очень сложно измерить этот коэффициент m_t+1. Для каждого конкретного инвестора это возможно было бы сделать, если б устроить ему большой опрос, но померить температуру в среднем по больнице достаточно сложно. Поэтому любая дальнейшая деятельность заключается в том, чтобы уточнять это уравнение.

Одной из первых попыток построить работающую модель была попытка под названием CAPM (Capital Asset Pricing Model), которая утверждает, что наш стохастический коэффициент дисконтирования есть просто линейная комбинация, в которую входит R_w доходность портфеля благосостояния.

Доходность этого портфеля благосостояния можно померить, если в качестве ориентира взять какой-нибудь большой индекс, например Standard & Poor's 500, и посмотреть доходность этого индекса. Эту модель называют моделью с одним фактором. Более сложные модели, такие как APT (Arbitrage pricing theory), говорят, что m представляет собой линейную комбинацию нескольких факторов.

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

Все статьи этой серии

• Стоимость денег, типы процентов, дисконтирование и форвардные ставки. Ликбез для гика, ч. 1

• Облигации: купонные и бескупонные, расчет доходности. Ликбез для гика, ч. 2

• Облигации: оценка рисков и примеры использования. Ликбез для гика, ч. 3

• Как банки берут друг у друга в долг. Плавающие ставки, процентные свопы. Ликбез для гика, ч. 4

• Построение кривой дисконтирования. Ликбез для гика, ч. 5

• Что такое опционы и кому это нужно. Ликбез для гика, ч. 6

• Опционы: пут-колл парити, броуновское движение. Ликбез для гика, ч. 7

• Опционы: расчет одношаговой биномиальной модели. Ликбез для гика, ч. 8

В предыдущей статье я описал векторные языки и их ключевые отличия от обычных языков. На коротких примерах я постарался показать, как эти особенности позволяют реализовывать алгоритмы необычным образом, кратко и с высоким уровнем абстракции. В силу своей векторной природы такие языки идеально присоблены для обработки больших данных, и в качестве доказательства в этой статье я полностью реализую на векторном языке простой SQL интерпретатор. А чтобы продемонстрировать, что векторный подход можно использовать на любом языке, я реализую тот же самый интерпретатор на Rust. Преимущества векторного подхода столь велики, что даже интерпретатор в интерпретаторе сможет обработать select с группировкой из таблицы в 100 миллионов строк за 20 с небольшим секунд.

Общий план.

Конечная цель - реализовать интепретатор, способный выполнять выражения типа:

select * from (select sym,size,count(*),avg(price) into r  from bt where price>10.0 and sym='fb'  group by sym,size)  as t1 join ref on t1.sym=ref.sym, t1.size = ref.size

Т.е. он должен поддерживать основные функции типа сложения и сравнения, позволять where и group by выражения, а также - inner join по нескольким колонкам.

В качестве векторного языка я возьму Q, так как его специализация - базы данных.

Интерпретатор будет состоять из лексера, парсера и собственно интерпретатора. Для экономии места я буду приводить только ключевые места, а весь код можно найти здесь. Так же для краткости я реализую лишь часть функциональности, но так, чтобы все важное было на месте: join, where, group by, 3 типа данных, агрегирующие функции и т.п.

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

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

Наконец, сам интерпретатор. На Q он имеет весьма скромные размеры - строк 25. На Rust, конечно, гораздо больше, но написать его проще, чем может показаться. Нужно просто по шагам повторять все операции Q, адаптируя их к специфике Rust.

Это моя первая программа на Rust и сразу хочу сказать, что слухи о его сложности сильно преувеличены. Если писать в функциональном стиле (read only), то проблем нет никаких. После того, как Rust несколько раз забраковал мои идеи, я понял, чего он хочет и уже не сталкивался с необходимостью все переделывать из-за контроллера ссылок, а явные времена жизни понадобились только один раз и по делу. Зато взамен мы получаем программу, которую можно распараллелить по щелчку пальцев. Что мы и сделаем, чтобы добиться просто феноменальной производительности для столь примитивной программы.

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

Лексер

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

fsa[state;char] -> state

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

Т.е. есть следующие этапы:

• Кодирование. Входные символы отображаются в группы (my.var -> aa.aaa, 12.01 -> 00.00, "str 1" -> "sss 1" и т.д.).

• Трансформация. Закодированные символы пропускаются через fsa (aa.aaa -> aAAAAA, 00.00 -> 0IFFF, "sss 1" -> "SSSSSR).

• Разбиваем начальную строку на части по начальным состояниям (a, 0, " и т.д.). Для удобства все не начальные состояния обозначены большими буквами.

Все три этапа - это векторные операции, поэтому на Q эта идея реализуется одной строкой (все состояния закодированы так, что начальные меньше limit):

(where fsa\[start;input]<limit)cut input

Это в сущности весь лексер. Правда еще необходимо определить fsa. В подавляющем большинстве случаев в качестве fsa можно взять матрицу - таблицу переходов конечного автомата. Простой автомат можно задать и руками, но можно реализовать небольшой DSL. Отображение в группы можно организовать через небольшой массив (ограничимся ASCII символами для простоты):

cgrp: ("\t \r\n";"0..9";"a..zA..Z"),"\\\"=<>.'";c2grp: 128#0; // массив [0;128]// Q позволяет присваивать значения по индексу любой формы.// В данном случае массиву массивов. В Rust необходимы два явных цикла:// cgrp.iter().enumerate().for_each(|(i,&s)| s.iter()//   .for_each(|&s| c2grp[s as usize] = i + 1));c2grp[`int$cgrp]: 1+til count cgrp;

Для краткости я не привожу все цифры и буквы. Нас интересуют пробельные символы, цифры, буквы, а также несколько специальных символов. Мы закодируем эти группы числами 1, 2 и т.д., все остальные символы поместим в группу 0. Чтобы закодировать входную строку, достаточно взять индекс в массиве c2grp:

c2grp `int$string

Автомат задается правилами (текущее состояние(я);группа(ы) символов) -> новое состояние. Для обозначения групп и начальных состояний токенов удобно использовать первые символы соответствующих групп (для группы 0..9 - 0, например). Для обозначения промежуточных состояний - большие буквы. Например, правило для имен можно записать так:

aA А a0.

т.е. если автомат находится в состояниях "a" (начало имени) или "A" (внутри имени), и на вход поступают символы из групп [a,0,.], то автомат остается в состоянии "A". В начальное состояние "a" автомат попадет автоматически, когда встретит букву (это правило действует по умолчанию). После этого, если дальше он встретит букву, цифру или точку, то перейдет во внутреннее состояние "A" и будет там оставаться до тех пор, пока не встретит какой-то другой символ. Я запишу все правила без лишних комментариев (Rust):

let rules: [&[u8];21] =  [b"aA A a0.",                         // имена   b"0I I 0",b"0I F .",b"F F 0",        // int/float   b"= E =",b"> E =",b"< E =",b"< E >", // <>, >= и т.п.   b"\" S *",b"S S *",b"\"S R \"",      // "str"   b"' U *",b"U U *",b"'U V '",         // 'str'   b"\tW W \t"];                        // пробельные символы

Числа и строки заданы в упрощенном формате. "*" в качестве входного символа имеет специальное значение - все возможные символы. Большие буквы - это состояния внутри токенов. Такая договоренность дает нам возможность легко определить начало токена - это все состояния, которые не большие буквы.

Матрица fsa из этих правил генерируется элементарно. Схематично это выглядит так:

fsa[*;y] = y (по умолчанию для всех состояний)"aA A a0." -> "aA","A","a0."; fsa[enc["aA"];enc["a0."]] = enc["A"]...

Необходимо закодировать символы с помощью вектора states:

states: distinct " ",(first each cgrp),raze fsa[;1];limit: 2+count cgrp;enc:states?; // в Q encode - это поиск индекса элемента в векторе

Вперед поместим все начальные состояния (пробел для учета группы 0), чтобы можно было легко определить limit.

Код генерации fsa я опускаю - он следует схеме выше.

Матрица переходов у нас есть, осталось определить саму функцию lex. В парсере нам понадобится знать тип токена, поэтому вычислим и его тоже. На Rust лексер выглядит так:

let s2n = move |v| ["ID","NUM","STR","STR","WS","OTHER"][find1(&stn,&v)];move |s| {    if s.len()==0 {return Vec::<Token>::new()};    let mut sti = 0usize;    let st: Vec<usize> = s.as_bytes().iter().map(|b| { // st:fsa\[0;c2grp x]        sti = fsa[sti][c2grp[std::cmp::min(*b as usize,127)]];        sti}).collect();    let mut ix: Vec<usize> = st.iter().enumerate() // ix:where st<sta        .filter_map(|(i,v)| if *v<sta {Some(i)} else {None}).collect();    ix.push(st.len());    (0..ix.len()-1).into_iter()        .filter_map(|i|            match s2n(st[ix[i]]) {                 "WS" => None,                  kind => Some(Token{ str:&s[ix[i]..ix[i+1]], kind})             }).collect()

На Q получится значительно более кратко:

s2n:(states?"a0\"'\t")!("ID";"NUM";"STR";"STR";"WS");lex:{  i:where (st:fsa\[0;c2grp x])<limit;  {x[;where not "WS"~/: x 0]} (s2n st i;i cut x)};

Если мы запустим лексер, то получим:

lex "10 + a0" -> (("NUM";"";"ID");("10";"+";"a0"))

Интерпретатор

Интерпретатор можно разделить на две части - выполнение выражений и выполнение select. Первая часть тривиальна на Q, но требует большого количества кода на Rust. Я приведу основные структуры данных, чтобы было понятно, как в целом работает интерпретатор. В основе лежит enum Val:

type RVal=Arc<Val>;enum Val {       I(i64),    D(f64),    II(Vec<i64>),    DD(Vec<f64>),    S(Arc<String>),    SS(Vec<Arc<String>>),    TBL(Dict<RVal>),    ERR(String),}

Есть три типа данных - строки, целые и нецелые, две формы их представления - атомарная и вектор. Также есть таблицы и ошибки. Dict - это пара Vec<String> и Vec<T> одинаковой длины. В случае таблицы T = Vec<RVal>, где каждый Val - это II, DD или SS. Rust позволяет в легкую распаралелливать программу, но нужно, чтобы типы данных позволяли передавать свои значения между потоками. Для этого я обернул все разделяемые значения в асинхронный счетчик ссылок Arc. Считается, что атомарные операции более медленные, однако в программе, которая работает с большими данными, это не имеет большого значения.

Интерпретатор работает с выражениями:

enum Expr {    Empty,    F1(fn (RVal) -> RRVal, Box<Expr>), // f(x)    F2(fn (RVal,RVal) -> RRVal, Box<Expr>, Box<Expr>), // f(x,y)    ELst(Vec<Expr>),    ID(String),  // variable/column    Val(Val),    // simple value - 10, "str"    Set(String,Box<Expr>), // 'set var expr' - assignment    Sel(Sel), // select    Tbl(Vec<String>,Vec<Expr>), // [c1 expr1, c2 expr2] - create table }

ELst и Empty используются только парсером. Expr (ссылки на себя) необходимо хранить в куче (Box). Выполняются выражения функцией eval в некотором контексте, где заданы переменные (Set), а также могут быть определены колонки таблицы:

struct ECtx {    ctx: HashMap<String,Arc<Val>>,   // variables}struct SCtx {    tbl: Arc<Table>,                // within select    idx: Option<Vec<usize>>,        // idx into tbl    grp: Arc<Vec<String>>,          // group by cols}

eval сравнительно проста (self = ECtx):

type RRVal=Result<Arc<Val>,String>;fn top_eval(&mut self, e: Expr) -> RRVal {    match e {        Expr::Set(id,e) => {            let v = self.eval(*e, None)?;            self.ctx.insert(id,v.clone()); Ok(v)},        Expr::Sel(s) => self.do_sel(s),        _ => self.eval(e, None)    }}fn eval(&self, e: Expr, sctx:Option<&SCtx>) -> RRVal {    match e {        Expr::ID(id) => self.resolve_name(sctx,&id),        Expr::Val(v) => Ok(v.into()),        Expr::F1(f,e) => Ok(f(self.eval(*e,sctx)?)?),        Expr::F2(f,e1,e2) => Ok(f(self.eval(*e1,sctx)?,self.eval(*e2,sctx)?)?),        Expr::Tbl(n,e) => { self.eval_table(None,n,e) }        e => Err(format!("unexpected expr {:?}",e))    }}

Set и Sel нужен модифицируемый контекст, а его нельзя будет передать просто так в другой поток. Поэтому eval разбит на две части. Задача resolve_name - найти переменную или колонку и при необходимости применить where индекс. eval_table - собрать таблицу из частей и проверить, что с ней все в порядке (колонки одной длины и т.п.). Функции F1 (max, count ...) и F2 (+, >=, ...) сводятся к огромным match блокам, где для каждого типа прописывается нужная операция. Макросы позволяют уменьшить количество кода. Например, для арифметических операций часть match выглядит так:

(Val::D(i1),Val::I(i2)) => Ok(Val::D($op(*i1,*i2 as f64)).into()),(Val::D(i1),Val::D(i2)) => Ok(Val::D($op(*i1,*i2)).into()),(Val::I(i1),Val::II(i2)) => Ok(Val::II(i2.par_iter()    .map(|v| $op(*i1,*v)).collect()).into()),

Это может показаться неоптимальным, но когда вы обрабатываете таблицу на 100 миллионов строк, это не имеет ни малейшего значения. Видите слово par_iter выше? Это все, что нужно сделать в Rust, чтобы операция стала параллельной.

Выполнение select гораздо интереснее и сложнее. Разберем его на Q, потому что код на Rust многословно повторяет код на Q, который и сам по себе непростой.

Select состоит из подвыражений (join, where, group, select, distinct, into), каждое из которых выполняется отдельно. Самое сложное из них - join. В его основе лежит функция rename, задача которой присвоить колонкам уникальные имена, чтобы не возникло конфликта при join:

// если x это name -> найти, select -> выполнитьsget:{[x] $[10=type x;get x;sel1 x]};// в грамматике таблица определяется как '(ID|sel) ("as" ID)?'// так что x это список из 2 элементов: (ID из as или имя таблицы;ID/select)// y - уникальный префиксrename:{[x;y]  t:sget x 1; // получить таблицу: names!vals  k:(k!v),(n,/:k)!v:(y,n:x[0],"."),/:k:key t; // k - оригинальные имена,        // v - уникальные, n - с префиксом (table.name)  (k;v!value t)};

Все эти манипуляции сводятся к построению двух словарей - отображения из настоящих имен колонок и расширенных (table.name) в уникальные и из уникальных имен в сами колонки таблицы. Уникальные имена позволяют иметь в одной join таблице колонки с одинаковыми именами из разных таблиц и обращаться к ним в выражениях через нотацию с точкой.

В основе join следующая функция:

// x - текущая таблица в формате rename// y - следующая таблица в этом формате// z - join выражение, список (колонка в x;и в y)// условие join: x[z[i;0]]==y[z[i;1]] для всех ijoin_core:{[x;y;z]  // m - отображение имен в уникальные для новой таблицы x+y  // имена из x имеют приоритет  // c - переименовываем join колонки в уникальные имена  c:(m:y[0],x 0)z;  // после join z[;0] и z[;1] колонки будут одинаковыми  // поэтому колонки из y перенаправим на x  m[z[;1]]:c[;0];  // x[1]c[;0] - просто join колонки из таблицы x (подтаблица)  // y[1]c[;1] - симметрично из y  // sij[xval;yval] -> (idx1;idx2) найти индексы join в обеих таблицах  // sidx[(i1;i2);x;y без join колонок] -  //  собрать новую таблицу из x и y и индексов  (m;sidx[sij[x[1]c[;0];y[1]c[;1]];x 1;c[;1]_ y 1])}// sidx просто применяет индексы ко всем колонкам и объединяет y и z// y z - это словари, но поскольку традиционно векторные функции имеют// максимально широкую область определения, не нужно обращаться явно к value sidx:{(y@\:x 0),z@\:x 1};

Вся работа выполняется в функции sij, все остальное - это манипуляции именами, колонками и индексами. Если бы мы захотели добавить другой тип индекса, достаточно было бы написать еще одну sij. Конечно, функция выглядит непросто, но учитывая, что она покрывает 80% select, ей можно это простить.

Функция sij сводится к поиску строк таблицы x в таблице y. В Rust для этих целей можно использовать HashMap с быстрой hash функцией FNV - поместить в Map одну таблицу и потом искать в ней строки второй. В Q, судя по времени выполнения, скорее всего используется что-то подобное. В целом в Q у нас есть два варианта - использовать векторные примитивы или воспользоваться встроенными возможностями связанными с таблицами. В первом варианте все по-честному:

// x и y - списки колонокsij:{j:where count[y 0]>i:$[1=count x;y[0]?x 0;flip[y]?flip x]; (j;i j)};// или на псевдокоде// i=find_idx[tblY;tblX]; j=i where not null i; return (j,i[j])

используем функцию поиска значения в векторе (?) и транспозиции матрицы (flip). Этот вариант не такой медленный как может показаться - всего в 2.5 раза медленнее, чем оптимизированный поиск сразу по таблице (который выглядит ровно также - x?y, только x и y - таблицы, а не списки векторов). Это показывает в очередной раз силу векторных примитивов.

Наконец сам join - это просто цикл свертки по всем таблицам (fold):

// "/" это fold, rename' это map(rename)sjoin:{[v] join_core/[rename[v 0;"@"];rename'[v 1;string til count v 1];v 2]};

Остальные части select гораздо проще. where:

swhere:{[t;w] i:til count value[t 1]0;  // все строки по умолчанию  $[count w;where 0<>seval[t;i;();w];i]}; // выбрать те, которые не 0// seval такой же как eval в Rust, т.е. его сигнатура:// seval[table,index;group by cols;expr], ECtx - это сам Q

Основная функция select:

sel2:{[p] // p ~ словарь с элементами select (`j, `s, `g  и т.п.)  i:swhere[tbl:sjoin p`j;p`w]; // сходу делаем join и where  if[0=count p`s; // в случае select * надо найти подходящие имена колонкам    rmap:v[vi]!key[tbl 0] vi:v?distinct v:value tbl 0;    p[`s]:{nfix[x]!x} rmap key tbl 1];  if[count p`g; // group by    // из group колонок нужен только первый элемент, нужно знать их имена    gn:nfix {$[10=type x;x;""]} each p`g;    // sgrp вернет список индексов (idx1;idx2;..) для каждой группы    // затем нужно выполнить seval[tbl;idxN;gn;exprM] для всех idx+expr    // т.е. двойной цикл, который в Q скрыт за двумя "each"    g:sgrp[tbl;i;p`g]];    :key[p`s]!flip {x[z] each y}[seval[tbl;;gn];value p`s] each g;  // если group нет, то все элементарно - просто seval для всех select выражений  (),/:seval[tbl;i;()] each p`s };

Функция sgrp в основе group by - это просто векторный примитив group, возвращающий словарь, где ключи - уникальные значения, а значения - их индексы во входном значении:

sgrp:{[t;i;g] i value group flip seval[t;i;()] each g};

Я опускаю distinct и into части, поскольку они малоинтересны. В целом - это весь select на Q. В краткой записи он занимает всего 25 строк. Можно ли ждать хоть какой-то производительности от столь скромной программы? Да, потому что она написана на векторном языке!

Производительность

Напомню, что этот игрушечный интерпретатор может выполнять выражения типа

select * from (select sym,size,count(*),avg(price) into r  from bt where price>10.0 and sym='fb'  group by sym,size)  as t1 join ref on t1.sym=ref.sym, t1.size = ref.size

и при этом справляться с таблицами в сотни миллионов строк. В частности таблица bt в выражении выше сгенерирована выражением:

// в интерпретаторе на Rust// s = ("apple";"msft";"ibm";"bp";"gazp";"google";"fb";"abc")// i/f - i64/f64 интервалы [0-100)set bt [sym rand('s',100000000), size rand('i', 100000000),    price rand('f', 100000000)]

Т.е. содержит 100 миллионов строк. Поначалу базовый select с group by (получается 800 групп по ~125000 элементов)

select sym,size,count(*),avg(price) into r from bt group by sym,size

работал 44 секунды в программе на Rust, что совсем неплохо и само по себе. Однако после некоторых оптимизаций, а главное распаралелливания ключевых операций, мне удалось добиться скорости порядка 6 секунд. На мой взгляд весьма хороший результат для подобной таблицы.

Самое главное, программа на Rust, несмотря на свой внушительный вид, - это почти 1 в 1 программа на Q. Поэтому больших интеллектуальных усилий и даже отладки она не потребовала. Также благодаря векторности изначального языка ее ускорение путем распараллеливания не потребовало почти никаких усилий - если все операции изначально над массивами, то все что нужно - это вставить там и тут par_iter вместо iter.

Интерпретатор на Q не столь быстр, но вышеуказанный select всего на 50% медленнее аналогичного запроса на самом Q. Это значит, что по сути Q работает на больших данных почти также быстро, как и программа на компилируемом языке.

Хочу также отметить то, насколько великолепным языком проявил себя Rust. За все время разработки и отладки я не получил ни одного segfault и даже panic увидел всего несколько раз, и почти все это были простые ошибки выхода за пределы массива. Также поражает, насколько легко и безопасно в нем можно распараллелить задачу.

Парсер

Я отложил парсер на конец, поскольку он довольно объемен и не имеет прямого отношения к теме статьи. Тем не менее, может вам будет интересно ознакомиться с тем, как легко можно написать весьма серьезный парсер в функциональном стиле на Rust.

Это рекурсивный нисходящий парсер без заглядывания вперед. Из-за этого он не может предсказать следующий шаг и вынужден обходить все варианты. Такой парсер, конечно, медленный и не годится для серьезных задач, но для SQL выражений больше и не надо. Какая разница, парсится выражение 1 микросекунду или 10, если сам запрос займет минимум сотни микросекунд.

Такие парсеры часто пишут руками, и выглядят они примерно так:

parse_expr1(..) {   if(success(parse_expr2(..)) {    if (success(parse_str("+") || success(parse_str("-")) {      if(success(parse_expr1(..)) {         return <expr operation expr>      }      return Fail    }    return <expr>  }  return Fail;}

Главная идея предлагаемого парсера в том, что нет смысла писать это все руками, можно написать генератор подобных парсеров из BNF-подобной формы. Для всех сущностей BNF пишем по функции, затем генерируем из описания грамматики в виде строк набор парсящих функций, и все готово. В Rust, как строго типизированном языке, есть нюансы. В первую очередь определим типы для парсящих и post process функций:

type ParseFn = Box<dyn Fn(&PCtx,&[Token],usize) -> Option<(Expr,usize)>>;type PPFn = fn(Vec<Expr>) -> Expr;

ParseFn будет захватывать правила грамматики, поэтому она должна быть замыканием (closure) и лежать в куче. PCtx содержит другие ParseFn для рекурсивных вызовов и PPFn для постобработки дерева. Если парсинг не удался, она возвращает None, иначе Some с выражением и новым индексом в массив токенов. PPFn обрабатывает узел дерева, поэтому принимает безликий список выражений и превращает его в нужное выражение.

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

("expr", "expr1 ('or' expr {lst})? {f2}"),("expr1","'not' expr1 {f1} | expr2 ('and' expr1 {lst})? {f2}"),("expr2","expr3 (('='|'<>'|'<='|'>='|'>'|'<') expr2 {lst})? {f2}"),("expr3","expr4 (('+'|'-') expr3 {lst})? {f2}"),("expr4","vexpr (('*'|'/') expr4 {lst})? {f2}"),("vexpr","'(' expr ')' {2} | '-' expr {f1} | call | ID | STR | NUM |  '[' (telst (',' telst)* {conc}) ']' {tblv}"),("call", "('sum'|'avg'|'count'|'min'|'max') '(' expr ')' {call} |  'count' '(' '*' ')' {cnt} | 'rand' '(' STR ',' NUM ')' {rand}"),

Тут видны ключевые части - имя правила, само правило и PP функции в фигурных скобках. Каждая продукция правила должна заканчиваться на PP функцию, поскольку правило возвращает Expr, а не Vec<Expr>. PP функция по умолчанию возвращает последний элемент вектора, поэтому кое-где PP функций нет. ID, NUM и т.п. должны обрабатываться ParseFn функцией с соответствующим именем.

Генерируется наш парсер с помощью следующей функции:

let parse = |str| {    let t = l(str);  // add ({}) depth map    let mut lvl = 0;    pp_or(&t.into_iter().map(|v| {      match v.str.as_bytes()[0] {        b'(' | b'{' => lvl+=1,        b')' | b'}' => lvl-=1,        _ => ()};      (v,std::cmp::max(0,lvl))}).collect::<Vec<(Token,i32)>>()    , 0)};

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

Далее наше правило поступает в парсер BNF. Нужно реализовать следующие компоненты:

• or правило - A | B

• and правило - A B C

• const правило - "(", "select".

• token правило - NUM, STR.

• subrule правило - expr1, call.

• optional правило - A?

• 0+ правило - A*

• 1+ правило - A+

• PP правило - {ppfn}

Это работа, требующая тщательности, но проделать ее нужно один раз. Например, or правило:

fn pp_or(t: &[(Token,i32)], lvl:i32) -> ParseFn {    if t.len() == 0 {return Box::new(|_,_,i| Some((Expr::Empty,i)))};    let mut r: Vec<ParseFn> = t      .split(|(v,i)| *i == lvl && v.str.as_bytes()[0] == b'|' )      .map(|v| pp_and(v,lvl)).collect();    if 1 == r.len() {        r.pop().unwrap()    } else {        Box::new(move |ctx,toks,idx|          r.iter().find_map(|f| f(ctx,toks,idx)))    }}

Функция должна вернуть ParseFn замыкание. В общем случае, когда pp_and вернула несколько ParseFn, нужно организовать цикл и выполнять подфункции, пока одна из них не вернет Some.

pp_and работает аналогично, только все ее подфункции должны вернуть Some. Также в случае успеха она должна вызвать нужную PPFn для обработки результата.

fn pp_and(t: &[(Token,i32)], lvl:i32) -> ParseFn {    if t.len() == 0 {return Box::new(|_,_,i| Some((Expr::Empty,i)))};    let (rules,usr) = pp_val(Vec::<ParseFn>::new(),t,lvl);    Box::new(move |ctx,toks,i| {        let mut j = i;        let mut v = Vec::<Expr>::with_capacity(rules.len());        for r0 in &rules {        if let Some((v0,j0)) = r0(ctx,toks,j) {            j = j0; v.push(v0)            } else {return None} };        Some((ctx.ppfns[&usr](v),j))    })}

pp_val рекурсивно обрабатывает круглые скобки и все базовые выражения. Вот некоторые примеры из нее:

// Token - if ok call rules[Token]move |ctx,tok,i| if i<tok.len() && tok[i].kind == s   {ctx.rules[&s](ctx,tok,i)} else {None}// Subrulemove |ctx,tok,i| ctx.rules[&s](ctx,tok,i))}// rule?move |ctx,tok,i| Some(rule(ctx,tok,i).unwrap_or((Expr::Empty,i)))// rule+move |ctx,tok,i| {    let (e,i) = plst(&rule,ctx,tok,i);    if 0<e.len() {Some((Expr::ELst(e),i))} else {None}}// где plstlet mut j = i; let mut v:Vec<Expr> = Vec::new();while let Some((e,i)) = rule(ctx,tok,j) {j=i; v.push(e)};(v,j)

Это весь код, необходимый для создания парсера. Чтобы его сгенерировать, нужно вызвать parse и положить правило в map:

let mut map = HashMap::new();map.insert("expr".to_string(), parse("expr1 ('or' expr {lst})? {f2}"));...  

Также необходимо определить PP функции. В большинстве случаев они сравнительно просты:

let mut pfn: HashMap<String,PPFn> = HashMap::new();// default rulepfn.insert("default".to_string(),|mut e| e.pop().unwrap());// set name expr выражениеpfn.insert("set".to_string(),|mut e| Expr::Set(e.swap_remove(1).as_id(),  e.pop().unwrap().into()) );

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

Наконец, положим правила в специальную структуру и определим для нее функцию parse:

PCtx { rules:map, ppfns:pfn}...impl PCtx {    fn parse(&self, t:&[Token]) -> Expr {        if let Some((e,i)) = self.rules["top"](&self,t,0) {            if i == t.len() {e}              else {Val::ERR("parse error".into()).into()}        } else {Val::ERR("parse error".into()).into()}    }}

Все, парсер готов. Он не быстр, но зато очень прост. Плюс он полностью динамический - можно менять правила во время выполнения программы, например, отключить какие-то возможности.