[Перевод] Решение Advent of Code на этапе компиляции с использованием макросов Rust25.12.2024 15:45

Писать качественный софт сложно. Написание тестов, обдумывание возникших сайдэффектов, муки выбора между оптимизацией скорости выполнения и использованием памяти. Идеальная программа — та, которая никогда не запускается. Никаких тебе мук выбора, багов и забот. Но что, если мы пойдем дальше, что если мы получим ответ на наш вопрос еще до того, как программа скомпилируется?

В этом году я хотел написать идеальную программу для решения челленджа Advent of Code. Если идеальная программа и может существовать, она должна быть написана на Rust. Давайте помучаем декларативные макросы Rust для получения ответа на задачу первого дня Advent of Code в виде ошибки компиляции.

$ cargo build
   Compiling advent-of-code-2024 v0.1.0 (/home/glados/Code/advent-of-code-2024)
error[E0080]: evaluation of constant value failed
   --> src/main.rs:142:5
    |
142 |     panic!("{}", format!("The answer is {answer}"));
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'The answer is 11', src/main.rs:142:5

Задача

Прочитайте условие задачи тут.

Грубо говоря, требуется следующее: получив две колонки чисел, отсортируйте обе, рассчитайте абсолютную разницу между соответствующими элементами и просуммируйте их.

Если ваша религия позволяет на такое смотреть, вот решение на python:

"""Warning: This code completes in a shocking O(n log n) time complexity
and allocates memory with reckless abandon."""
input = [
  3,   4,
  4,   3,
  2,   5,
  1,   3,
  3,   9,
  3,   3,
]
left = sorted(input[::2])
right = sorted(input[1::2])
print(sum(abs(l - r) for l, r in zip(left, right)))
# 11

Решение на python не только еле читаемое, так еще и невероятно медленное — O(n log n). Если мы не хотим, чтобы ИИ отобрал у нас работу, надо стремиться к более высокой планке. Скоро все медленнее O(1) станет неприемлемым.

Благородный порыв, но далеко не идеальная программа.

Совершенство

Если мы хотим поистине идеальную программу — ту, которая дает нам ответ ни разу не запускаясь, нам потребуется переместить процесс вычисления в сам компилятор. Современный Rust предлагает два способа выполнения вычислений на этапе компиляции: вычисление констант и декларативные макросы.

Технически, использование вычисления констант для расчета значения на этапе компиляции подходит больше всего. Вычисление констант в Rust сильно развилось за последнее время и стало крайне мощным инструментом. Но заголовок статьи говорит «с помощью макросов Rust», так что их мы и будем использовать.

Разделение списка

Первый шаг — разделить имеющиеся колонки на 2 списка.

let answer = day1! {
  3   4
  4   3
  2   5
  1   3
  3   9
  3   3
};

Вот так выглядит макрос:

macro_rules! day1 {
    // match two numbers at a time, storing them in left and right lists
    (@split [$($lcol:tt)*] [$($rcol:tt)*] $l:tt $r:tt $($tail:tt)*) => {
        day1!(@split [$($lcol)* $l] [$($rcol)* $r] $($tail)*)
    };
    // base case when no numbers remain
    (@split [$($lcol:tt)*] [$($rcol:tt)*]) => {
        todo!()
    };
    // entry
    ($($tail:tt)*) => { day1!(@split [] [] $($tail)*) };
}

Не залезая в дебри их работы, макросы, определяемые с помощью macro_rules! это набор шаблонов и раскрытий. О них можно думать как о наборе правил из двух частей:

macro_rules! some_macro {
  (pattern1) => { expansion1 };
  (pattern2) => { expansion2 };
  /* ... */
}

Каждое правило говорит: «Если видишь такой шаблон, заменяй его этим раскрытием». Макрос продолжает применять правила до тех пор, пока не останется частей для раскрытия. Синтаксис шаблонов может быть сложным, но мы остановимся на наиболее простых шаблонах в рамках данной статьи.

Начнем с простого шаблона ($a:tt) => { $a $a };. Для Rust он означает:

Обрабатывай один токен (tt) и называй его a.
Замени его, повторяя токен дважды

Так foo становится foo foo, а 1 становится 1 1.

Последовательность токенов также может быть сопоставлена с помощью ($($tail:tt)*). Символ *, как и в регулярных выражениях, означает ноль или больше повторений. К примеру, для входного значения 1 2 3:

По сути, все во внутренних скобках дублируется для каждого подходящего токена.

И наконец, шаблоны могут сопоставляться с токенами напрямую. Шаблон (abc $($tail:tt)*) будет срабатывать для любого входного значения, начинающегося с токена abc.

Этого введения должно быть достаточно, чтобы понять входное правило

    // entry
    ($($tail:tt)*) => { day1!(@split [] [] $($tail)*) };

Это этап подготовки. Тут мы

Сопоставляем 0 или более токенов (весь/любой ввод).
Оборачиваем в новый макрос, начинающийся со @split.
Добавляем два пустых списка, которые в итоге будут содержать правую и левую колонки чисел.
В конце оставляем наши входные значения нетронутыми.

@split позволяет нам управлять следующим совпадением, задав новое правило для шаблона, начинающегося с @split. Название @_name_ обусловлено конвенцией языка. Это может быть любая последовательность токенов, для которой требуется задать совпадение.

Таким образом, day1!( 1 2 3 4) раскрывается в day1!(@split [] [] 1 2 3 4).

Настоящая магия начинается дальше.

    // match two numbers at a time, storing them in left and right lists
    (@split [$($lcol:tt)*] [$($rcol:tt)*] $l:tt $r:tt $($tail:tt)*) => {
        day1!(@split [$($lcol)* $l] [$($rcol)* $r] $($tail)*)
    };

Это может выглядеть сложно, но достаточно легко понять на примере.

Начиная с раскрытия с предыдущего шага day1!(@split [] [] 1 2 3 4), под шаблон попадают:

Литерал токена @split
Пустые списки [] [] ([$($lcol:tt)*] [$($(rcol:tt)*])
Первое число 1 ($l)
Второе число 2 ($r)
И все остальные токены 3 4 ($($tail:tt)*)

Затем правило раскрывается в day1!(@split [1] [2] 3 4). Раскрытие в свою очередь создает новый макрос, который:

Добавляет 1 в конец первого списка ([$($lcol)* $l])
Добавляет 2 в конец второго списка ([$($(rcol)* $r])
Остальные токены остаются в конце 3 4 ($($tail)*)

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

Постепенное сопоставление токенов из хвоста и рекурсивная обработка остальных — паттерн, который называется tt munching. Сохранение результата для последующей обработки другими правилами называют push down accumulation.

Процесс продолжается, пока не остается необработанных токенов на входе.

day1!(@split [] [] 1 2 3 4)      // Match and split first pair (1,2)
-> day1!(@split [1] [2] 3 4)     // Match and split second pair (3,4)
-> day1!(@split [1 3] [2 4])     // No more pairs to match. move to base case

На данном этапе у нас не осталось токенов, которые можно подставить в $l $r и текущее правило становится неприменимо. Это приводит нас к последнему правилу, относящемуся к разделению списка.

    // base case when no numbers remain
    (@split [$($lcol:tt)*] [$($rcol:tt)*]) => {
        todo!()
    };

Теперь у нас есть два списка несортированных токенов и мы можем приступить к следующей фазе нашей идеальной программы.

Сортировка списка

Надеюсь, что прошлая часть была мягким введением в декларативные макросы в rust, потому что эта часть немного проклята.

Дальше нам нужно отсортировать последовательность 2 1 4 3 с прошлого шага до 1 2 3 4 на этапе компиляции. Проблема в том, что макросы не умеют работать с условиями, они лишь обрабатывают последовательности и раскрывают токены. Нет способа сказать «если a > b, раскрой в b a, в противном случае — в a b». По крайней мере не напрямую.

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

  (@sort 1 1) => { 1 1 };
  (@sort 1 2) => { 1 2 };
  (@sort 2 1) => { 1 2 };
  (@sort 1 3) => { 1 3 };
  (@sort 3 1) => { 1 3 };
  /* ... */

Но это было бы очень костыльно…

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

Полный макрос сортировки пузырьком

В основе лежит два типа правил.