Март 23

DOU Проектор: Как мы написали SubScript — расширение для многопоточности в Scala

От редакции:
В рубрике DOU Проектор все желающие могут презентовать свой продукт (как стартап, так и ламповый pet-проект). Если вам есть о чем рассказать — приглашаем поучаствовать. Если нет — возможно, серия вдохновит на создание собственного made in Ukraine продукта. Вопросы и заявки на участие присылайте на Данный адрес e-mail защищен от спам-ботов, Вам необходимо включить Javascript для его просмотра. .

Идея

Добрый день, меня зовут Анатолий Кметюк, и в этой статье я бы хотел рассказать об open-source проекте, в котором я участвую. Наш проект называется SubScript и является расширением языка Scala, которое добавляет синтаксис Algebra of Communicating Processes (ACP) в Scala.

Проект был основан Andre van Delft, независимым исследователем из Нидерландов, в 2012 году, на тот момент у него уже был многолетний опыт реализации подобного решения для Java. В 2014 году к Андре присоединился я, в 2015 третьим членом команды стал Andrew Lawrence из Великобритании.

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

Для решения этой проблемы были созданы высокоуровневые фреймворки, такие как Lightbend (Typesafe) Akka и Rx Scala. Они существенно облегчили задачу написания параллельных программ, но мы считаем, что задачу можно облегчить еще больше, если решать ее на языке, предназначенном для этой задачи. Как я уже сказал, мы реализуем решение для параллельного программирования на базе ACP — одной из алгебр процессов, которая была создана в 1982 году.

ACP определяет язык для описания процессов и задает аксиомы, на которых и строится эта алгебра. Процессы описываются переменными и операторами ACP. Например, «+» является оператором выбора и «a + b» значит «a или b», в зависимости от того, что из них началось раньше.

Идея SubScript состоит в том, чтоб добавить язык ACP в Scala. Таким образом, программисты получают новый язык, адаптированный для написания многопоточных программ, которым они могут пользоваться непосредственно из языка Scala.

Реализация

SubScript добавляет в Scala специальные конструкции для описания параллельных задач — так называемые скрипты. Вот пример скрипта:

script live(x: Int) = a b println(x)

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

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

Еще один пример, на этот раз с параллелизмом:

script live = a && b && c

Тут && — оператор strong-AND-параллелизма. «Параллелизм» значит, что a, b, и c выполняются одновременно; «AND» значит, что скрипт live успешно завершит свое выполнение, если все операнды && успешно завершатся; «strong» значит, что неудача хотя бы одного из операндов (например, произошло исключение) ведет к неудаче всего оператора и немедленной отмены выполнения остальных операндов.

Для сравнения, доступен также & — простой AND-параллелизм, когда неудача в одном из операндов тоже ведет к неудаче всего оператора, но не ведет к немедленной отмене всех остальных операндов. Также есть || и | - strong-OR-параллелизм и normal-OR-параллелизм соответственно, где успешное завершение хотя бы одного оператора ведет к успешному завершению всего операнда.

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

Скрипты могут определяться везде, где могут определятся обычные методы. Запускаются скрипты путем вызова на них Scala метода runScript:

def main(args: Array[String]) {runScript(live)}
script live = println(“Hello World!”)

Этот код запустит скрипт live из метода main.

Препроцессор

Очевидно, что синтаксис определения скрипта невозможно реализовать чисто средствами Scala, как и синтаксис некоторых операторов. Поэтому на ранних стадиях SubScript существовал в форме форка компилятора Scala, и весь новый синтаксис задавался путем модификации компилятора.

Новый синтаксис генерировал стандартные Abstract Syntax Trees (AST) Scala. Например, «script foo» переписывался в AST, эквивалентные «def foo» (скрипт соответствует методу). Операнды под оператором последовательности в теле скрипта, «a b с», — в вызов методов библиотеки, которая реализует SubScript — что-то малочитабельное вроде “_seq(_script_call(a), _script_call(b), _script_call(c))”.

Этот подход был очень неудобным как минимум по двум причинам. Во-первых, начать работать с SubScript было сложно. Нужно было клонировать наш проект с GitHub, компилировать компилятор из исходников и использовать его для компиляции всех проектов с SubScript. Во-вторых, модифицировать синтаксис из компилятора Scala — сложно, неинтуитивно и часто ведет к ошибкам, которые трудно выявлять.

Поэтому в 2015 году мы переработали наш подход и избавились от всех модификаций к стандартному компилятору. Вместо этого мы задали синтаксис нашего языка путем модификации парсера языка Scala, написанного Li Haoyi на Parboiled2 — генераторе парсеров для Scala. Этот новый парсер по-прежнему переписывал синтаксис SubScript в стандартный синтаксис Scala, вызывая методы библиотеки, которая реализует SubScript.

Далее, мы написали плагин для SBT (build tool для Scala), который применял этот парсер ко всем исходникам проекта, помеченным импортом «import subscript.language», генерировал синтетические исходники, где код SubScript был переписан в код Scala, и лишь тогда вызывал компилятор.

Вкратце, мы заставляем SBT переписывать код SubScript в код Scala и компилируем переписанные исходники.

Например, следующий код:

script live = a b c

переписывается в это:

def live = subscript.DSL._script[Any](None, Symbol("live")){(_node: subscript.vm.ScriptTrait[Any]) =>
  implicit val script = _node
subscript.DSL._seq(subscript.DSL._maybeCall("", (here: subscript.vm.model.callgraph.CallGraphTreeNode) => subscript.DSL._maybeVarCall("a")), subscript.DSL._maybeCall("", (here: subscript.vm.model.callgraph.CallGraphTreeNode) => subscript.DSL._maybeVarCall("b")), subscript.DSL._maybeCall("", (here: subscript.vm.model.callgraph.CallGraphTreeNode) => subscript.DSL._maybeVarCall("c")))}

Данный подход решил две основные проблемы с модификацией компилятора: изменять синтаксис стало намного проще, а начать пользоваться SubScript теперь можно просто добавив 3 строки кода в build.sbt и одно строку в project/build.sbt.

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

Core Library

Весь функционал SubScript реализован в форме библиотеки, так называемой SubScript Virtual Machine (VM, не имеет ничего общего с JVM, это обычная библиотека Scala). Скрипты представляются в форме деревьев — template trees. Нечитабельный код выше выполняет очень простую задачу — строит дерево, описывающее скрипт «a b c», и возвращает его из метода «live», в который переписался скрипт «live».

Template trees выполняются специальными обьектами — ScriptExecutor. Когда вы вызываете runScript(live), вы передаете template tree, сгенерированное live, в метод runScript. Сам runScript создает ScriptExecutor, который и выполняет это дерево.

По ходу выполнения ScriptExecutor постепенно конвертирует template tree в граф. Если temlate tree — статичная структура данных, задающая весь скрипт за раз и никогда не меняющаяся, то граф выполнения скрипта — динамичный. Каждый узел template tree имеет свой lifecycle, который управляется ScriptExecuter’ом. Когда приходит время, ScriptExecuter создает новый узел графа из узла template tree, где хранится все динамическое состояние этого узла, но когда в узле графа отпадает необходимость, узел удаляется из графа.

Результаты

Для облегчения начала работы с SubScript мы детально описали процесс написания первой программы Hello World в нашем GitHub репозитории. Для начала работы вам нужно иметь всего лишь SBT 0.13 и Java 8. В разработке программ на SubScript вам поможет встроенный графический дебаггер, с помощью которого можно отслеживать, как выполняются скрипты, шаг за шагом.

Кроме этого, мы создали проект SubScript Koans, написанный в духе Scala Koans и Ruby Koans. С его помощью вы сможете освоить SubScript интерактивно, выполняя небольшие задания. Освоив язык, вы сможете посмотреть примеры его применения в нашем репозитории примеров.

Пример работы — Twitter Search

Язык имеет достаточно много функций и синтаксиса, который сложно запомнить, поэтому мы также создали cheat-sheet, где кратко перечислен основной синтаксис языка. Мы стараемся активно продвигать проект в научной сфере — теоретические аспекты проекта и статьи, которые мы презентуем на конференциях, можно найти на нашем сайте subscript-lang.org.

Мы активно исследуем направления применения SubScript и совершенствуем язык новым функционалом. На данный момент мы рассматриваем следующие направления развития, в числе прочих:

Интеграция с Scala JS, возможность написания JS-приложений на SubScript;
Интеграция с Dotty — новым компилятором Scala. Проблема с текущей реализацией SubScript — неинформативность ошибок, которые выдает компилятор при компиляции синтетических исходников. Мы надеемся, что интегрировав SubScript в Dotty и используя плагины для компилятора, мы сможем избавиться от этой проблемы;
Моделирование встроенных систем — как оказалось, порой сложнее описать процесс взаимодействия компьютера с человеком, чем процесс выполнения параллельной программы. Пример модели духовки можно посмотреть тут (в разработке);
Дизайн процессов, паттерны программирования процессов на SubScript;
Интеграция с IntelliJ IDEA;
Симуляция дискретных систем.

Мы более чем рады новым разработчикам, которые могли бы работать вместе с нами! Как видите, есть много перспективных направлений развития, поэтому если у вас есть время и вам интересна Scala, приглашаем к участию в проекте.