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

Привет, Хабр!

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

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

Предисловие

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

О КуМире

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

Андрей Петрович Ершов. Фото взято со статьи на Хабре.

В 1980-х годах, еще в СССР, академик Андрей Петрович Ершов ввел в употребление, как его называет Википедия, «алголо-подобный алгоритмический язык с русским синтаксисом, использующий понятные школьнику слова на русском языке». Он впоследствии использовался в учебниках по информатике (А. Г. Кушниренко), где и закрепился. Затем для него был создан "Е-практикум" — редактор-компилятор РАЯ с комплектом исполнителей типа черепашки, робота и прочих подобных. Современная реализация РАЯ, которую мы будем рассматривать — КуМир. Сначала разрабатывался в МГУ, а на сегодняшний день в НИИСИ РАН. Вот тут можно скачать их 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». Она абсолютно бесплатно доступна в веб версии на своем же сайте. Крайне рекомендую ее всем, кто хочет реализовать свой интерпретатор и/или компилятор. Мы тут ограничимся только интерпретатором (хотя, кто знает, может быть мне захочется развить эту тему дальше).

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

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

Токенизация

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

• имя a

• оператор =

• число 2

• оператор +

• число 2

• оператор *

• число 2

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

Парсинг

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

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

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

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

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

Выполнение

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

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 (открывать только через IDE КуМира от НИИСИ РАН, потому что без подсветки синтаксиса там не разобраться).

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