Wow. Such Rust. Much macro. © картинка - Твиттер аккаунт Servo

Язык Rust стремительно набирает обороты. Кто-то пророчит ему стать заменой C/C++, кому-то он просто нравится. Я скорее принадлежу ко второй группе. Разработчики стараются сделать его удобным и безопасным. В нем есть конструкции и принципы, которые еще не скоро появятся в "плюсах", ввиду инерции комитета и множества других причин. Поэтому, для всех личных проектов я предпочитаю использовать именно Rust.

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

Однажды, когда я в очередной раз застрял с синтаксическим анализатором (он же "парсер"), я подумал, что уж очень много я пишу однотипного кода. И этот однотипный код один в один ложится на грамматику в форме Бэкуса — Наура (БНФ).

Немного подумав, я решил, что мне надо написать генератор кода на основе грамматики. И для этой задачи как нельзя хорошо подходят макросы в Rust.

В статье описана реализация LL(*) парсера с использованием макросов. И реализован парсер простых математических выражений.

В итоге парсер для БНФ грамматики:

expr ::= sum
sum  ::= mul "+" sum | mul "-" sum | mul
mul  ::= atom "*" mul | atom "/" mul | atom
atom ::= "(" expr  ")" | number | neg;
neg  ::= "-" atom

Можно сгенерировать с помощью серии макросов:

rule!(expr, sum);
rule!(sum, or![
     and![(mul, token('+'), sum) => make_operator],
     and![(mul, token('-'), sum) => make_operator],
     mul
]);
rule!(mul, or![
     and![(atom, token('*'), mul) => make_operator],
     and![(atom, token('/'), mul) => make_operator],
     atom
]);
rule!(atom, or![
    and![(token('('), expr, token(')')) => |_lbrace, stat, _rbrace| Some(stat)],
    num,
    neg
]);
rule!(neg, and![(token('-'), atom) => |_, number| Some(Box::new(expression::Expression::Negate(number)))]);

Типичный любитель λ-исчисления.

Однажды, бороздя просторы интернета, я наткнулся на новость о лиспоподобном, встраиваемом языке программирования Shen. Раньше у них на главной странице висел пример кода на Лиспе. В примере авторы описывают абстрактную коллекцию и функции работы с ними.

Так уж совпало, что я являюсь тайным почитателем функционального программирования, а значит, в некоторой степени, лямбда-исчисления, которое состоит почти полностью из абстракций. Захотелось мне написать что-то максимально абстрактное и, что бы усложнить себе задачу, я решил, что встроенные типы данных это для слабых прикладников, а реализовать все нужно непременно в терминах кодирования Чёрча.

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

Если вас не пугает Lisp, много лямбд и y-combinator (не тот, который с новостями),