Как я написал свой язык и онлайн 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, бинарные операторы (=, -, +, ||). Обычно токены разделены вайтспейсами.