Как я написал свой язык и онлайн IDE

Здесь онлайн интерпретатор, здесь документация.

Зачем

В сентябре 2020 года я учился на 2 курсе. В том же месяце я впервые написал программу, которая мне понравилась. Она создаёт svg изображения растений, здесь её можно потрогать.

Чуть позже я выяснил, что такие программы называют процедурными генераторами. Я увлекся этим, сделал ещё парочку (1, 2).

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

Пришло в голову создать систему для создания генераторов, a.k.a. «генератор генераторов». В этом решении было две проблемы. Первая: уже оглядываясь назад, мне понятно, что дело было не в том, что языки неудобные, а в том, что я каждый раз менял инструменты. Из-за этого уходило время на их изучение. Вторая: я поставил очень широкую задачу, для которой невозможно создать DSL-язык. Нужно было остановиться на генераторах SVG-изображений, для начала.

Примеры генераторов, которые сделаны на моем языке

Также на языке сделана библиотека, чтобы классы преобразовывать в SVG-картинки (библиотека геометрии с ней плотно связана, получается tight coupling).

В чём суть языка?

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

class T {     a = b + 1     b = 3 } 

При создании получится экземпляр T, у которого a = 4, b = 3. Я думал, что такая система будет удобной для генераторов, потому что можно отдельно объявить какие-то компоненты как классы и связать их воедино сразу же внутри объявлений классов. Динамическое создание полей позволяет обращаться к ещё не созданным полям из родительских классов и менять их.

Более сложный пример:

class B {     nested = c.d.e     c = C() }  class C {     d = D()     d.e = E() }  class D {}  class E {}  fun main() {     b = B()     test(b.nested is E) } 

Получится такое дерево:

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

1. Вызываем bfs от корня и ищем поля, которые ещё не проинициализированы (bfs идет по полям типа класс¹),

2. Если полей не нашли, экземпляр класса создали.

3. Пока поля находим (пусть нашли поле a):

   1. Создаем стек инициализации, добавляем найденное поле a,

   2. Для всех полей в стеке:

      1. Смотрим, есть ли справа от = не проинициализированные поля.

      2. Если есть, ставим эти поля в стек. Если a = b + 1, а b ещё неизвестно, то ставим b в стек, стек будет [a, b].

      3. Если не созданных полей справа от = нет, убираем последний элемент из стека, инициализируем его.

Первоначальная задумка

Я не сразу решил делать язык. Хотелось сделать более простую систему, которой могли бы пользоваться не только программисты. Система должна быть атомарной (не должно быть лишнего) и полной (можно создать много генераторов, формально задать «любой генератор» я не могу). Вот к какой системе я пришел²:

Есть два типа объектов: геометрические и контейнерные. Геометрические — это графические SVG-элементы: прямоугольник, эллипс, круг, отрезок, path и т.д. Контейнерные объекты содержат в себе геометрические и контейнерные. Интересно, что все контейнеры можно реализовать в языке. Есть три типа контейнерных объектов:

1. Простой контейнер. Представляет из себя набор объектов. По сути просто массив, или <group> в SVG.

   class SimpleContainer {   // content - что лежит в контейнере   content = [SomeOtherContainer(), Circle(), Rect()] } 

2. Случайный контейнер. Выбирает случайный элемент внутри себя и всегда возвращает его. Это нужно для создания рандома.

   import std.utils as utils  class RandomContainer {   content = [SomeOtherContainer(), Circle(), Rect()]   random = -1   fun getContent() {       if(random == -1)         random = randInt(0, content.size - 1)       return content[random]   } } 

3. Рекурсивный контейнер. Он в каком-то смысле ключевой и повторяет идею языка. Нужно передать число numberOfElements в конструктор для создания такого числа вложенных рекурсивных контейнеров.

   class RecursiveContainer {   content = [...]   iter = if(parent == null) 0 else parent.iter + 1   child = if(iter < numberOfElements) RecursiveContainer(numberOfElements=numberOfElements) else null } 

В этой системе ещё можно менять параметры объектов, длину и ширину прямоугольника, радиус круга и т.д. Но хотелось добавить рандом и в эти параметры, чтобы они выглядели как формулы: rect.width = if(parent is Circle) randInt(10, 20) else 5. В этот момент я решил, что, пожалуй, нужно сразу делать язык, а не систему с контейнерами и формулами.

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

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

Стебель

Стебель цветка упрощённо — это последовательность отрезков, начало которого является концом другого. То есть можно задать стебель как:

// задаем вспомогательные геометрические классы - они уже есть в библиотеке std.geometry2D class Point {   x = 0   y = 0 }  class Segment {   p1 = Point()   p2 = Point() } // начинается значимый код class FlowerSegment : Segment {   iter = parent.iter + 1   // говорим, что начало next - конец текущего, а конец next повернут относительно его начала   next = if(iter < 5) FlowerSegment( \     p1=copy(p2), \     p2 = p2.plus(0, -20).rotate(rndInt(-45,45), p2))  \          else null } // класс нужен, чтобы при вызове parent.iter у FlowerSegment не напороться на NullPointerException class Root {   iter = 0   child = FlowerSegment() }

Этот код должен давать нам что-то такое:

Но вместо этого, он может сказать: p2 not found . Это потому, что анализ зависимостей работает не полностью, он не видит, что нужно проинициализировать p2 перед next. Я не стал его дорабатывать, потому что в нем есть фатальная проблема: в вызываемых функциях могут быть нужны поля, которые ещё не созданы (в данном случае функция plus предполагает, что мы уже знаем, чему равны x и y). А анализировать всю функцию непросто³: нельзя вызывать интерпретатор, потому что он может поменять какие-то значения. Чтобы это исправить, придется писать громоздкую конструкцию в next:

next = if(iter < 5 && p1 != null && p2.x != null && p2.y != null) ...

Цветок

Чтобы добавить цветок, нужно немного изменить код:

// класс из std.geometry2D class Circle {...}  class FlowerHead : Circle {   r = 5 }  class FlowerSegment : Segment {   iter = parent.iter + 1   next = if(iter < 5) FlowerSegment( \     p1=copy(p2), \     p2 = p2.plus(0, -20).rotate(rndInt(-45,45), p2)) \          else FlowerHead(center=p2) // вместо null теперь цветок, остальной код тот же }  ...

Разделение стебля

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

class DoubleFlowerSegment {     iter = parent.iter + 1     angle = rndInt(10, 45)     // тут уже код выглядит страшно.     // для s1.p2, параллельно переносим отрезок родитель,     // поворачиваем его     s1 = FlowerSegment(p1=copy(parent.p2), \             p2=copy(parent.p2) \             .translate(parent.p2.minus(parent.p1)) \             .rotate(angle, parent.p1))     s2 = FlowerSegment(p1=copy(parent.p2), \             p2=copy(parent.p2) \             .translate(parent.p2.minus(parent.p1)) \             .rotate(-angle, parent.p1)) }  class FlowerSegment : Segment {}  // остальной код не меняется

import std.utils as utils import std.geometry2D as geom import std.svg as svg  fun main() {      r = Root()   svgRes = svg.createSVG(r, 300, 400)     write(svgRes, "result.svg") }  class FlowerHead : Circle {   r = 5 }  class FlowerSegment : Segment {   iter = parent.iter + 1   next = if(iter < 5 && p1 != null && p2.x != null && p2.y != null) \   (if(rnd() > 0.7) DoubleFlowerSegment() else \   FlowerSegment( \     p1=copy(p2),  \     p2 = p2.plus(0, -20).rotate(rndInt(-45,45), p2))) \          else FlowerHead(center=p2) }  class DoubleFlowerSegment {     iter =parent.iter + 1     angle = rndInt(10, 45)     s1 = FlowerSegment(p1=copy(parent.p2), \         p2=copy(parent.p2)\             .translate(parent.p2.minus(parent.p1)) \            .rotate(this.angle, parent.p1))     s2 = FlowerSegment(p1=copy(parent.p2), \         p2=copy(parent.p2)\             .translate(parent.p2.minus(parent.p1))\            .rotate(-this.angle, parent.p1)) }  class Root {   width = 400   height = 300   iter = 0   child = FlowerSegment(p1=Point(x=width/2,y=height),\         p2=Point(x=width/2,y=height-10)) }

Остальные части

Чтобы цветы приобрели завершенный вид, нужно ещё сделать несколько шагов, которые я не вижу ценности разбирать:

1. Стеблю и цветку нужно добавить цвета.

2. Чтобы добавить тень, нужно каждый из отрезков продублировать и сместить копии влево на 1. Цвет этих сегментов нужно изменить на более темный.

3. Цветкам нужно добавить лепестки, стеблям — листья.

4. Чтобы не было ощущения, что все цветки «смотрят» на зрителя, их нужно изменить через svg transform.

Еще немного особенностей реализации

1. Для всех токенов⁴ объявлен метод evaluate(symbolTable: SymbolTable), который говорит, как токен должен интерпретироваться. Это очень удобно, но, наверное, никак иначе сделать нельзя 🙂

2. Можно интерпретировать параллельно несколько программ (дебажить нельзя).

Про IDE

Я использовал monaco editor, потому что у него есть удобный playground, в котором разобраны нужные кейсы.

Пожалуй, самое лучшее в IDE — это дебаггинг. Только это ненастоящий дебаг, потому что сперва вся программа прогоняется. «Дебаг» — это просто запись значений переменных. Зато с дебагом синхронизируется консольный вывод.

На втором месте подсвечивание ошибок.

Выводы

• Сделал ли я DSL специально для генераторов? Нет. В генераторе цветов на C# не сильно больше кода, чем на языке, который я сделал.

• Понравилось ли мне это разрабатывать? Конечно, да!

• Какие уроки я извлек из этого? Прежде чем создавать что-то, нужно проверить, как это примерно будет выглядеть в конечном итоге, и вообще стоит ли ради этого итога работать. Нужно было:

  • Набросать генератор цветов на моей языке,

  • Понять, что он не лучше, чем реализация на императивном языке,

  • Изменить подход / отказаться от реализации.

¹есть ещё поля Int, Double, List, Dictionary. Class — это то, что мы объявляем (как и в других языках).

²когда я делаю генераторы, я представляю их через эту систему. Она как бы «большими мазками» описывает как будут строиться картинки, а детали уже описываются в коде. Мне кажется, эта система удобна при создании генераторов независимо от языка, контейнеры можно воспринимать как паттерны.

³вообще можно создать аннотацию @Requires() для функций класса и в ней писать, какие поля должны быть проинициализированы перед вызовом.

⁴токен — это любой элемент в языке, например while, {, "abc", 123, бинарные операторы (=, -, +, ||). Обычно токены разделены вайтспейсами.