Как я собственный язык на КуМире писал

Привет!

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

(картинка позаимствована с одного из официальных туториалов ^[1])

Предисловие

Как вообще мне в голову пришла эта идея? История достаточно проста: как-то раз у нас с товарищами зашел разговор о том, можно ли считать КуМир полным по Тьюрингу. В процессе этой беседы промелькнуло такое заявление: «Если на КуМире можно написать КуМир, то да, он тьюринг-полный». Разговор быстро закончился, но это утверждение почему-то мне врезалось в память, и мне захотелось попробовать написать хоть какой-то язык на нем.

О КуМире

Если вы вдруг не знаете, что такое КуМир или Русский Алгоритмический Язык (РАЯ), то вот коротенькая историческая справка.

В 1980-х годах, еще в СССР, академик Андрей Петрович Ершов ^[2] ввел в употребление, как его называет Википедия, «алголо-подобный алгоритмический язык с русским синтаксисом, использующий понятные школьнику слова на русском языке». Он впоследствии использовался в учебниках по информатике, где и закрепился. Затем для него был создан "Е-практикум" — редактор-компилятор РАЯ с комплектом исполнителей типа черепашки, робота и прочих подобных. Современная реализация РАЯ, которую мы будем рассматривать — КуМир. Он разработан (и поддерживается) НИИСИ РАН. Вот тут ^[3] можно скачать их IDE.

Как выглядит синтаксис? Вот один из примеров:

алг лит двоичнаяЗапись(арг цел a) нач
    цел b, d
    утв a > 0
    b := a
    знач := ""
    нц пока b > 0
        d := mod(b, 2)
        b := div(b, 2)
        выбор
            при d = 0: знач := "0" + знач
            при d = 1: знач := "1" + знач
        все
    кц
кон

(увы, на Хабре ожидаемо нет подсветки синтаксиса КуМира, придется пользоваться 1С подсветкой, чтобы хоть как-то было понятно)

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

Что мы собираемся делать?

Мы реализуем небольшой язык программирования, поддерживающий:

• присваивание и чтение переменных

• базовые арифметические операции и сравнения

• условный оператор if

• цикл while

• ввод и вывод через консоль

• 3 типа данных: boolean, number и string

При реализации я во многом руководствовался прекрасной книжкой от одного из разработчиков Dart — «Crafting Interpreters». Она абсолютно бесплатно доступна в веб версии на своем же сайте ^[4]. Крайне рекомендую ее всем, кто хочет реализовать свой интерпретатор и/или компилятор. Мы тут ограничимся только интерпретатором (хотя, кто знает, может быть мне захочется развить эту тему дальше).

Структура нашего интерпретатора максимально проста: сначала мы разбиваем текст на токены (токенизируем), затем парсим полученные токены в абстрактное синтаксическое дерево, а затем проходим по этому дереву и выполняем его узлы.

Разберем алгоритм на простейшем примере: a = 2 + 2 * 2

Токенизация

Сначала всю строку нужно преобразовать в поток токенов. Токен здесь можно воспринимать как «слово» нашего языка. В случае с нашим примером разбивка будет такой:

• имя a

• оператор =

• число 2

• оператор +

• число 2

• оператор *

• число 2

У каждого токена есть свой тип (имя, ключевое слово, число, оператор и т.д.) и лексема (собственно подстрока этому токену соответствующая).

Парсинг

Полученный поток токенов необходимо спарсить. Пользоваться я буду здесь обычным рекурсивным спуском ^[5]. Для работы алгоритма необходимо определить грамматику. Для парсинга нашего примера достаточно такой урезанной версии:

statement = expression
expression = assignment
assignment = term | VARIABLE "=" term
term = factor | factor "+" factor | factor "-" factor
factor = primary | primary "*" primary | primary "/" primary
primary = VARIABLE | NUMBER

Здесь в нижнем регистре описаны правила, в верхнем регистре типы токенов, в кавычках лексемы, а вертикальная черта — своеобразный оператор ИЛИ. Что тут происходит? Мы говорим, что утверждение = выражение. Выражение в свою очередь — присваивание. Присваивание — переменная = сумма или же просто сумма. Сумма — произведение + произведение или произведение - произведение или просто произведение. И таким образом расписывается и произведение, пока мы не доходим до "первичного" выражения, которое является либо названием переменной, либо числовым значением.

Вот этот страшный кусок кода, который я привел, называется РБНФ ^[6] — Расширенной Бэкус-Науровой Формой.

После применения этих правил, парсер построит нам абстрактное синтаксическое дерево, которое будет выглядеть как-то так:

Выполнение

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

run(node):
    if addition:
        a = run(node.left)
        b = run(node.right)
        return a + b
    ...

Вместо многоточия там дальше стоят if'ы на все случаи жизни: на вычитание, деление, присваивание, сравнение, на другие синтаксические конструкции.

Теперь мы знаем, что должно происходить внутри нашего интерпретатора, и можем начать его реализовывать. Или нет?...

Большие проблемы

Оказывается, в КуМире не существует динамических массивов. Вообще. Совсем. Есть только лишь «табличные значения», которые, по сути, являются си-шными массивами, да еще и длина у них жестко ограничена сверху. Указателей, само собой, там никаких тоже нет.

Казалось бы, все, ничего не выйдет, нам даже некуда складывать поток токенов... но! В КуМире есть строки, поддерживающие индексацию и срезы, а также конкатенацию. По факту они являются динамическими массивами символов, а значит мы можем ими воспользоваться. Каким образом? Да просто будем представлять списки как строки, в которых элементы разделены какими-то символами. Типа такого: [1, 2, 3] превращается в "1;2;3". В ASCII, кстати, даже специальные символы для разделения есть: File, Group, Record и Unit Separator (0x1C по 0x1F).

Вот реализация, к которой я пришел:

алг добавитьККонцуСписка(аргрез лит список, арг лит значение) нач
цел длина0 
  длина0 := длинаКоллекции(список)
  лит список1
  список1 := __кк__префикс + 'L' + цел_в_лит(длина0 + 1)
  цел i 
  i := __индексПовторенияНомер(список, __кк__разделитель, 1)
  если i < 1 то i := 4 все
  если i > длин(список) то 
    список1 := список1 + __кк__разделитель + значение
  иначе
    список1 := список1 + список[i:длин(список)] + __кк__разделитель + значение
  все
  список := список1
кон

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

^Lдлина^]элемент^]элемент

Пример:

^L3^]а^]б^]в

^ и ^] это как раз управляющие последовательности (0x1C и 0x1D).

Разумеется, в КуМире и подавно нету ни объектов, ни словарей, а для удобного представления узлов хотелось бы заиметь и их. Сделаем и словарь. Тут тоже звезд с неба хватать не будем, представим его просто как список ключей K и список значений V. Тогда если у нас есть пара ключ-значение a: b, то где-то на индексе i: K[i] == a; V[i] == b. Проще говоря, на одинаковых индексах в списке стоят части одной пары.

В завершение этой части еще хочу отметить, что КуМир не имеет ни исключений, ни даже какой-то функции вроде exit(), которая моментально завершает программу. Поэтому пришлось писать свою реализацию и сюда:

алг паника(арг лит причина) нач
  вывод "=== ПАНИКА ===", нс , причина, нс, "--- паника ---", нс
  утв нет
кон

Максимально прямолинейный способ решения проблемы: просто в рантайме вызываем assert false и программа завершается).

Наконец-то реализуем

Функция main, если ее можно так назвать, выглядит так:

алг
нач
  лит исхКод
  исхКод := считатьВесьФайл("test.lang")
  лит токены
  токены := токенизировать(исхКод)
  лит асд
  асд := спарсить(токены)
  лит результат, память
  память := новыйОбъект
  результат := выполнить(асд, память)
кон

Токенизатор выглядит тоже достаточно просто:

алг лит токенизировать(арг лит исхКод) нач 
  лит СТД_КЛЮЧ_СЛОВА
  СТД_КЛЮЧ_СЛОВА := __ток_стд_ключ_слова
  цел текущий = 1
  цел старт = 1
  сим текущийСим
  лит токены
  токены := новыйСписок
  нц пока текущий <= длин(исхКод)
    старт := текущий
    текущийСим := исхКод[текущий]
    текущий := текущий + 1
    выбор 
      при __ток_сим_пропускать(текущийСим):
      при текущийСим = '(': добавитьККонцуСписка(токены, "(")
      при текущийСим = ')': добавитьККонцуСписка(токены, ")")
      при текущийСим = '+': добавитьККонцуСписка(токены, "+")
      при текущийСим = '-': добавитьККонцуСписка(токены, "-")
      при текущийСим = '*': добавитьККонцуСписка(токены, "*")
      при текущийСим = '/': добавитьККонцуСписка(токены, "/")
      при текущийСим = ':': добавитьККонцуСписка(токены, ":")
      ...

Код приходится сокращать, в конце статьи есть ссылка на GitHub, там лежат все исходники.

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

алг лит __парситьСлагаемые(арг лит токены, аргрез цел текущий) нач 
  лит лев, прав, узел, токен
  лев := __парситьМножители(токены, текущий)
  знач := лев
  если __соотв(токены, текущий, "+") <> "" или __соотв(токены, текущий, "-") <> "" то
    токен := получитьИзСписка(токены, текущий - 1)
    прав := __парситьМножители(токены, текущий)
    узел := __новыйБинарныйУзел(токен, лев, прав)
    знач := узел
  все
кон

алг лит __парситьМножители(арг лит токены, аргрез цел текущий) нач 
  лит лев, прав, узел, токен
  лев := __парситьВторичное(токены, текущий)
  знач := лев
  если __соотв(токены, текущий, "*") <> "" или __соотв(токены, текущий, "/") <> "" то
    токен := получитьИзСписка(токены, текущий - 1)
    прав := __парситьВторичное(токены, текущий)
    узел := __новыйБинарныйУзел(токен, лев, прав)
    знач := узел
  все
кон

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

если типУзла = "=" то
  а := десериализовать(получитьПоКлючу(десериализовать(получитьПоКлючу(узел, "лев")), "арг"))
  б := выполнить(десериализовать(получитьПоКлючу(узел, "прав")), память)
  задатьПоКлючу(память, а, сериализовать(б))
  знач := б 
  выход
все

если типУзла = "!" то
  а := выполнить(десериализовать(получитьПоКлючу(узел, "арг")), память)
  если не __рт_являетсяЛог(а) то паника("ОШИБКА РАНТАЙМА: нельзя ! над не-лог") все
  знач := __рт_новыйЛогОбъект(не(получитьПоКлючу(а, "знач") = "true"))
  выход
все

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

Используем

Напишем простейшую программу на нашем детище: калькулятор с одним действием — делением:

numinput a
numinput b
if b == 0 {
    out "Cannot divide by 0"
} else { 
    out a / b 
}

Вводим с консоли два числа, проверяем на 0 и выполняем действие. Проверим:

Сколько заняло это по времени? Ответ неутешительный — на токенизацию, парсинг и выполнение ушло около 13.5 секунд. Blazingly fast тут даже и не пахнет.

Посмотрим на еще один алгоритм — подсчет факториала:

numinput a
b = 1
c = 1
while c <= a {
    b = b * c
    c = c + 1
}
out b

Подсчет факториала от 4 занял около 40 секунд.

Выводы

Что можно сказать, оглядываясь на этот опыт?

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

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

Виды аргументов

При декларации аргумента в КуМире нужно указать не только тип данных, но и «вид» аргумента:

• арг — обычный аргумент — нельзя модифицировать, можно читать.

• рез — результат выполнения — функция его модифицирует, но значение на момент начала выполнения функции у него не определено.

• аргрез — и аргумент, и результат одновременно.

Таким образом мы можем точно знать, какие из переданных аргументов изменятся после выполнения функции, а какие нет (этакий аналог &mut из Rust).

дано — валидация аргументов

В реальности помимо ограничения по типу, аргументы ограничиваются еще и по смыслу: нельзя в функцию mod передать в качестве второго аргумента 0. Такая валидация обычно сидит где-то в начале функции и выглядит из раза в раз одинаково: if (arg invalid) throw IllegalArgumentException или assert arg valid. При этом фактически условие valid/invalid приходится дублировать: один раз оно находится в коде, второй раз встречается в документации к этой функции.

КуМировское дано упрощает эту задачу. Являясь фактически частью сигнатуры функции (частью ее заголовка), оно представляет собой assert, который выполняется перед запуском функции. Таким образом, дано является и кодом валидации, и документацией. Сравните:

def set_element(arr: list, index: int, value) -> None:
    """
    Set element at index
    Args: 
        index: target index. Must be less than len(arr)
        value: target value
    """
    if index >= len(arr):
        raise ValueError
    arr[index] = value

алг задатьЭлемент(аргрез лит массив, арг цел индекс, арг лит значение)
дано индекс < длинаКоллекции(массив)
| Задать элемент по данному индексу
нач
    массив[индекс] = значение
кон

По-моему, гораздо лаконичнее.

Цикл «нц n раз»

Мелочь, а приятно. Далеко не все языки имеют цикл «сделать что-то n раз». А между тем иногда и он полезен.

КуМироспецифичная реализация оператора не

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

лог завтра пойдет дождь = нет
| Все следующие выражения синтаксически верны и означают одно и то же
вывод не завтра пойдет дождь
вывод завтра не пойдет дождь
вывод завтра пойдет не дождь

Так иногда хочется при проверке всяких флагов типа is_active иметь возможность писать не not is_active, а is_not_active. К сожалению, это лишь несбыточная мечта.

Заключение

Опыт, надо сказать, был крайне интересным, и, пожалуй что, даже уникальным. Можно ли сказать, что эти 6 часов были проведены с какой-то практической пользой? Пожалуй нет. Было ли это интересно? Определенно да. (хотя меня не покидает ощущение, что меня просто развели на 6 часов разработки на КуМире)

Исходный код этого творения лежит на GitHub ^[7] (открывать только через IDE КуМира от НИИСИ РАН, потому что без подсветки синтаксиса там не разобраться).

Буду рад услышать ваше мнение и прочитать ваши комментарии!