Металингвистический совратитель Си. Опус II: Рекуррентный экстаз09.11.2020 23:02

ij9p-nygxt17eoxodrwteoi07-m.jpeg

>> Осторожно, модерн! 2 — 0.2. Пропажа заначки

Год назад, в 15 лет, меня озадачила проблема compile-time имитации алгебраических типов данных в чистом Си. Для этого я создал poica — исследовательский язык на макросах. Серия этих опусов — логическое продолжение моего исследования.

Макросистема Си являет собой аналог перезаписи термов из одной известной Тьюринг-полной функциональной модели вычислений — лямбда-исчисления. Имея в арсенале эту невыносимо простую концепцию, можно, казалось бы, одними макросами описать совершенно любой алгоритм, поддающийся описанию в большинстве языков программирования!

Но есть одно «но»: блокировка рекурсии (macro blueprinting), зашитая прямо в стандартном препроцессоре — именно она препятствует манипулированию коллекциями произвольной длины, вычислению функции Аккермана и многим другим вещам; даже Y комбинатор не в силах помочь ввиду непервоклассной природы макросов.

Но это нас не остановит! Не можешь решить задачу целиком — реши её частично. Сей опус посвящён механизму обобщённой макрорекурсии в стиле передачи продолжений на отложенных макрораскрытиях.

Цель — сгенерировать Cons-список:

$ ((((((((((0), 1), 2), 3), 4), 5), 6), 7), 8), 9) $

Для этого нам предстоит протаранить скважину в продвинутое функциональное программирование…, но хватит уже лохматить бабушку, скорее под кат!


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


Для начала реализуем целочисленную арифметику. Недостающие макросы определены тут.


Инкрементация

#define INC(x) CAT(INC_, x)
#define INC_0  1
#define INC_1  2
#define INC_2  3
#define INC_3  4
#define INC_4  5
#define INC_5  6
#define INC_6  7
#define INC_7  8
#define INC_8  9

Пояснение для $3$:

$INC(3) \rightarrow \\ CAT(INC\_, 3) \rightarrow \\ INC\_3 \rightarrow \\ 4$


Сравнение

#define EQ(x, y) EQ_PICK_SECOND(CAT(EQ_, CAT(x, CAT(_, y))), 0, ~)

#define EQ_PICK_SECOND(...)            EQ_PICK_SECOND_AUX(__VA_ARGS__)
#define EQ_PICK_SECOND_AUX(_a, b, ...) b

#define EQ_0_0 ~, 1
#define EQ_1_1 ~, 1
#define EQ_2_2 ~, 1
#define EQ_3_3 ~, 1
#define EQ_4_4 ~, 1
#define EQ_5_5 ~, 1
#define EQ_6_6 ~, 1
#define EQ_7_7 ~, 1
#define EQ_8_8 ~, 1
#define EQ_9_9 ~, 1

Пояснение для $(3, 3)$:

$EQ(3, 3) \rightarrow \\ EQ\_PICK\_SECOND(CAT(EQ\_, CAT(3, CAT(\_, 3))), 0, \sim) \rightarrow \\ EQ\_PICK\_SECOND(EQ\_3\_3, 0, \sim) \rightarrow \\ EQ\_PICK\_SECOND(\sim, 1, 0, \sim) \rightarrow \\ EQ\_PICK\_SECOND\_AUX(\sim, 1, 0, \sim) \rightarrow \\ 1$

Пояснение для $(5, 9)$:

$EQ(5, 9) \rightarrow \\ EQ\_PICK\_SECOND(CAT(EQ\_, CAT(5, CAT(\_, 9))), 0, \sim) \rightarrow \\ EQ\_PICK\_SECOND(EQ\_5\_9, 0, \sim) \rightarrow \\ EQ\_PICK\_SECOND\_AUX(EQ\_5\_9, 0, \sim) \rightarrow \\ 0$

Смысл такой: если числа равны, CAT(EQ_, CAT(x, CAT(_, y))) раскрывается в ~, 1, иначе получится что-то вроде EQ_5_9, т.к. такого макроса не существует. Затем это хозяйство вместе с 0, ~ скармливается EQ_PICK_SECOND и EQ_PICK_SECOND_AUX. Но зачем EQ_PICK_SECOND просто перенаправляет свои аргументы в EQ_PICK_SECOND_AUX? Дело в том, что ~, 1 всё ещё считается за один аргумент несмотря на наличие запятой:


C11 6.10.3 Macro replacement
The sequence of preprocessing tokens bounded by the outside-most matching parentheses forms the list of arguments for the function-like macro. The individual arguments within the list are separated by comma preprocessing tokens, but comma preprocessing tokens between matching inner parentheses do not separate arguments.

Дополнительный уровень косвенности EQ_PICK_SECOND_AUX преобразует ~, 1 в два аргумента. Ключевой момент — это аргумент b в EQ_PICK_SECOND_AUX:

Далее EQ_PICK_SECOND_AUX раскрывается в ожидаемое двоичное значение b. Хорошо, с этим разобрались, но остался ещё один вопрос: зачем нужен последний аргумет ~ в EQ_PICK_SECOND(CAT(EQ_, CAT(x, CAT(_, y))), 0, ~)? Посмотрим что будет, если убрать его в вызове EQ_PICK_SECOND_AUX(EQ_5_9, 0, ~): 

warning: ISO C99 requires at least one argument for the "..." in a variadic macro
   17 | EQ_PICK_SECOND_AUX(EQ_5_9, 0)
      |                             ^

Релевантная выдержка из стандарта:


C11 6.10.3 Macro replacement
If there is a … in the identifier-list in the macro definition, then the trailing arguments, including any separating comma preprocessing tokens, are merged to form a single item: the variable arguments. The number of arguments so combined is such that, following merger, the number of arguments is one more than the number of parameters in the macro definition (excluding the …).


Ну теперь мы точно готовы! Возьмём яйца в кулак макросы-идиомы из предыдущего опуса и попытаемся сгенерировать эдакий Cons-список: 

#define GEN(acc, i) IF(EQ(i, 9), STOP, PROGRESS)(acc, i)

#define STOP(acc, i)     acc
#define PROGRESS(acc, i) GEN((acc, INC(i)), INC(i))

GEN((0), 0)
$ clang gen.c -std=c11 -Weverything -E
warning: disabled expansion of recursive macro [-Wdisabled-macro-expansion]
GEN((0), 0)
^
note: expanded from macro 'GEN'
#define GEN(acc, i) IF(EQ(i, 9), STOP, PROGRESS)(acc, i)
                                       ^

Выходит, что препроцессор не поддерживает рекурсию?


C11 6.10.3.4 Rescanning and further replacement
If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file«s preprocessing tokens), it is not replaced. Furthermore, if any nested replacements encounter the name of the macro being replaced, it is not replaced. These nonreplaced macro name preprocessing tokens are no longer available for further replacement even if they are later (re)examined in contexts in which that macro name preprocessing token would otherwise have been replaced.

Обидно!

jzlwcwfmtxb1fsjmh6u3wwk8hja.jpeg

Но должен же быть выход? После непродолжительных поисков натыкаемся на репозиторий map-macro, в котором реализован функтор для списков. Рекурсия достигается одной лазейкой в стандарте…, но для начала попытаемся понять саму идею. Определим следующие макросы: 

#define EMPTY()
#define DEFER(op) op EMPTY()

#define A(x) x DEFER(B)()(x)
#define B()  A

Посмотрим на раскрытие A(blah):

$ A(blah) \rightarrow \\ blah \ DEFER(B)(blah) \rightarrow \\ blah \ B \ EMPTY()(blah) \rightarrow \\ blah \ B \ ()(blah) $

Почему B ()(blah) не раскрывается в A(blah) и не происходит блокировка рекурсивного вызова? Очень просто: потому что препроцессор не воспринимает B () за вызов! — Препроцессор пересканирует токены последовательно: видим blah B EMPTY()(blah). blah — вызов? Нет. B — вызов? Нет. EMPTY() — вызов? Да, раскрываем. (blah) — вызов? Нет. Полученная последовательность лексем blah B ()(blah) и есть результат раскрытия. Выдержка из стандарта:


C11 6.10.3.4 Rescanning and further replacement
After all parameters in the replacement list have been substituted and # and ## processing has taken place, all placemarker preprocessing tokens are removed. The resulting preprocessing token sequence is then rescanned, along with all subsequent preprocessing tokens of the source file, for more macro names to replace.

Для раскрытия B () в выражении blah B ()(blah) необходимо ещё одно пересканирование. Посмотрим на неописуемой красоты отцентрованные TeX-формулы, которые я использовал исключительно для эстетического удовольствия вместо обычных серых-тусклых-невзрачных блоков кода работу механизма ещё чуточку:

$ blah \ B \ () (blah) \rightarrow \\ blah \ A (blah) \rightarrow \\ blah \ blah \ DEFER(B)(blah) \rightarrow \\ blah \ blah \ B \ EMPTY()(blah) \rightarrow \\ blah \ blah \ B \ ()(blah) $

$ blah \ blah \ B \ () (blah) \rightarrow \\ blah \ blah \ A (blah) \rightarrow \\ blah \ blah \ blah \ DEFER(B)(blah) \rightarrow \\ blah \ blah \ blah \ B \ EMPTY()(blah) \rightarrow \\ blah \ blah \ blah \ B \ ()(blah) $

… и так далее. Как мы можем автоматизировать пересканирования на столько раз, сколько нам нужно? Какая структура в языке побуждает сканирование последовательности лексем? Аргументы функциональных макросов. С применением многострадального макроса EXPAND, раскрывающегося в свои аргументы:

$ A(blah) \rightarrow blah \ B \ ()(blah) \\ EXPAND(A(blah)) \rightarrow blah \ blah \ B ()(blah) \\ EXPAND(EXPAND(A(blah))) \rightarrow blah \ blah \ blah \ B \ ()(blah) \\ EXPAND(EXPAND(EXPAND(A(blah)))) \rightarrow blah \ blah \ blah \ blah \ B \ ()(blah) \\ \ldots $

Наша задача сводится к генерации вызовов EXPAND и кодированию терминального условия — так мы заполучим вожделенную рекурсию. В map-macro не стали мыслить лукаво — пересканирование выполняется ровно 365 раз: 

#define EVAL(...)  EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL0(EVAL0(EVAL0(__VA_ARGS__)))
#define EVAL0(...) __VA_ARGS__

Для разового случая позволительно, но я поставил цель повыше — целиком и полностью забыть блокировку рекурсии как страшный сон. Созерцать абстракцию, обрабатывающую грязные препроцессорные дела за нас. В таком случае неприемлемо низкий предел 365 придётся повысить до, скажем, $2^{16}$, потому что один рекурсивный макрос может вызывать другой рекурсивный, а тот — третий, десятый и т.д. Всегда пересканировать $2^{16}$ раз — смерть для препроцессора, силой мысли аппроксимировать глубину рекурсии — смерть для программиста.


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

Как определить взаимодействие такого вида? Очень просто — задействуем сопоставление с образом — если рекурсивный макрос вернул CONTINUE — значит сделать ещё одно раскрытие, если STOP — значит терминальное условие выполнилось и нужно остановиться. Обратите внимание, что в первом случае возникает рекурсия в самом двигателе рекурсии! Чтобы устранить парадокс, мы бесстыдно сгенерируем достаточно ($2^{16}$) «раскрывателей», вызывая следующий в каждом предыдущем (похожее мы делали с макросом TESTS_FOR_EACH в предыдущем опусе).

Прототип:

[godbolt]

#define EMPTY()
#define DEFER(op) op EMPTY()

#define REC REC_0

#define REC_0(x)                    REC_0_OVERLOAD(x)
#define REC_0_CONTINUE(x)           REC_1(x)
#define REC_0_STOP(...)             __VA_ARGS__
#define REC_0_OVERLOAD(x)           REC_0_OVERLOAD_PRIMITIVE(x)
#define REC_0_OVERLOAD_PRIMITIVE(x) REC_0_##x

...

#define FOO(acc)   CONTINUE(DEFER(FOO_HOOK)()(acc blah))
#define FOO_HOOK() FOO

REC(FOO())

Посмотрим во что раскроется REC(FOO()): 

REC_3_LIMIT_REACHED(CONTINUE(CONTINUE(CONTINUE(CONTINUE(CONTINUE(CONTINUE(CONTINUE(FOO_HOOK ()(blah blah blah blah blah blah blah blah blah blah)))))))))

Почему столько много CONTINUE и blah? У нас ведь всего три уровня рекурсии…

Дело в том, что FOO(blah) раскрывается далеко не три раза. Внимательно проанализируем сколько произошло раскрытий:


  1. параметр REC_0,
  2. параметр REC_0_OVERLOAD,
  3. параметр REC_0_OVERLOAD_PRIMITIVE,
  4. параметр REC_1, …

Намного больше, чем три!

Аналогия: раскрытие аргументов — «двигатель» раскрытия, DEFER — «тормоз». Значит нужно притормозить столько раз, сколько сделали лишних раскрытий:

[godbolt]

#define REC REC_0

#define REC_0(...)                                                                                 \
    REC_0_OVERLOAD(REC_0_GET_CHOICE(__VA_ARGS__))                                                  \
    (REC_0_GET_REST(__VA_ARGS__))
#define REC_0_GET_CHOICE(choice, ...)    choice
#define REC_0_GET_REST(choice, ...)      __VA_ARGS__
#define REC_0_OVERLOAD(choice)           REC_0_OVERLOAD_PRIMITIVE(choice)
#define REC_0_OVERLOAD_PRIMITIVE(choice) REC_0_##choice
#define REC_0_CONTINUE                   REC_1
#define REC_0_STOP(...)                  __VA_ARGS__

...

#define REC_CONTINUE(hook, ...) CONTINUE, DEFER_2_TIMES(hook)()(__VA_ARGS__)
#define REC_STOP(...)           STOP, __VA_ARGS__

#define DEFER_2_TIMES(op) DEFER_0(DEFER_1)(op)
#define DEFER_0(op)       op EMPTY()
#define DEFER_1(op)       op EMPTY()
#define EMPTY()

#define FOO(acc)   REC_CONTINUE(FOO_HOOK, acc blah)
#define FOO_HOOK() FOO

REC(FOO())

-5vutzudluareilwxdmcg93aizg.jpeg

Вывод: 

REC_3_LIMIT_REACHED (CONTINUE, DEFER_1 (FOO_HOOK)()(blah blah blah blah))

Появился новый макрос REC_CONTINUE(hook, ...), «замораживающий» hook два раза. В противовес ему каждый блок REC_* раскрывает входные данные два раза:


  1. параметр REC_0,
  2. параметр REC_0_GET_REST,
  3. параметр REC_1, …

Но почему мы получили четыре blah вместо трёх? Последний blah — результат пересканирования тела REC_0. В этом можно убедиться, вызвав примитивную стрингификацию аргументов в REC_2_GET_REST (аргумент макроса в позиции #arg не раскрывается): 

#define REC_2_GET_REST(choice, ...)      PRIMITIVE_CAT(__VA_ARGS__)

...

#define PRIMITIVE_CAT(x) #x

Вывод: 

REC_3_LIMIT_REACHED ("FOO_HOOK ()(blah blah blah)")

Настало время посмотреть на раскрытие REC(FOO()):

$ REC(FOO()) \rightarrow \\ REC\_0(FOO()) \rightarrow \\ REC\_0\_CONTINUE(REC\_0\_GET\_REST(CONTINUE, \\ DEFER\_1(FOO\_HOOK)()(blah))) \rightarrow \\ REC\_0\_CONTINUE(FOO\_HOOK()(blah)) \rightarrow \\ REC\_1(FOO\_HOOK()(blah)) \rightarrow \\ REC\_1\_CONTINUE(REC\_1\_GET\_REST(CONTINUE, \\ DEFER\_1(FOO\_HOOK)()(blah \ blah))) \rightarrow \\ \ldots $

Кажется, всё в порядке.


Кто мы есть и зачем мы здесь? На первую часть вопроса можно ответить многогранно, а на вторую — чтобы сгенерировать такой Cons-список:

$ ((((((((((0), 1), 2), 3), 4), 5), 6), 7), 8), 9) $

Реализация достаточно проста:

[godbolt]

...

#define GEN(acc, i) IF(EQ(i, 9), STOP, PROGRESS)(acc, i)
#define GEN_HOOK()  GEN

#define STOP(acc, i)     REC_STOP(acc)
#define PROGRESS(acc, i) REC_CONTINUE(GEN_HOOK, (acc, INC(i)), INC(i))


С REC_STOP проблемка: рекурсивные макросы становятся непереиспользуемыми: допустим, что рекурсивный макрос A вызвал рекурсивный макрос B, тогда после выполнения B весь двигатель рекурсии остановится и A не сможет продолжить исполнение.

К счастью, деды решили эту задачу за нас целых 45 лет назад. Называется стиль передачи продолжений (CPS, continuation-passing style) — когда продолжение (материализованный поток исполнения; в нашем случае — функциональный макрос) явно передаётся в виде параметра в следующую функцию, вызывающую это продолжение с результатом вычислений, при том аргументами могут выступать только простые выражения (лямбда или переменная). Рассмотрим вычисление гипотенузы прямоугольного треугольника в прямом стиле и в CPS:


Прямой стиль

[godbolt]

#include 
#include 

#define let __auto_type

#define $(return_type, params, body) \
    ({return_type fn params { return body; } fn;})

int main(void) {
    let hypotenuse = $(double, (double x, double y), sqrt(x * x + y * y));

    printf("%f\n", hypotenuse(3, 4));
}


CPS

[godbolt]

#include 
#include 

#define let __auto_type

#define $(return_type, params, body) \
    ({return_type fn params { return body; } fn;})

int main(void) {
    let my_sqrt = $(double, (double x, double (*k)(double y)), k(sqrt(x)));
    let my_pow = $(double, (double x, double (*k)(double y)), k(x * x));
    let add = $(double, (double x, double y, double (*k)(double z)), k(x + y));

    let hypotenuse = $(double, (double a, double b, double (*k)(double n)),
        my_pow(a,
            $(double, (double a2),
                my_pow(b,
                    $(double, (double b2),
                        add(a2, b2,
                            $(double, (double a2b2), my_sqrt(a2b2, k))
                        )
                    )
                )
            )
        )
    );

    printf("%f\n", hypotenuse(3, 4, $(double, (double x), x)));
}

Так давайте же в каждый рекурсивный макрос принимать два дополнительных параметра: k (продолжение) и контекст k_cx (макросы не могут захватывать среду), а при достижении терминального условия вызывать этот k. Потребуется изменить определение REC_CONTINUE и превратить REC_STOP в особое продолжение: 

#define REC_CONTINUE(k, k_cx, ...) CONTINUE, DEFER_2_TIMES(k)()(UNPARENTHESISE(k_cx), __VA_ARGS__)

#define REC_STOP()               REC_STOP_AUX
#define REC_STOP_AUX(_k_cx, ...) STOP, __VA_ARGS__

Тогда генерация Cons-списка примет следующую форму:

[godbolt]

#define GEN(k, k_cx, acc, i) IF(EQ(i, 9), STOP, PROGRESS)(k, k_cx, acc, i)
#define GEN_HOOK()           GEN

#define STOP(k, k_cx, acc, i)     REC_CONTINUE(k, (k_cx), acc)
#define PROGRESS(k, k_cx, acc, i) REC_CONTINUE(GEN_HOOK, (k, k_cx), (acc, INC(i)), INC(i))

REC(GEN(REC_STOP, ~, (0), 0))

Внимание на REC(GEN(REC_STOP, ~, (0), 0)). REC_STOP превращён в продолжение, останавливающее двигатель рекурсии — макрос STOP при достижении терминального условия раскроется в REC_CONTINUE(REC_STOP, (k_cx), acc).

Рассмотрим один пример взаимодействия двух рекурсивных макросов: после Cons-списка генерируем второй список в форме (a)(b)(c)...:

[godbolt]

// (((a), b), c)

#define GEN(k, k_cx, acc, i) IF(EQ(i, 9), STOP, PROGRESS)(k, k_cx, acc, i)
#define GEN_HOOK()           GEN

#define STOP(k, k_cx, acc, i)     REC_CONTINUE(GEN_2_HOOK, (k, (k_cx, acc)), acc, 0)
#define PROGRESS(k, k_cx, acc, i) REC_CONTINUE(GEN_HOOK, (k, k_cx), (acc, INC(i)), INC(i))

// (a)(b)(c)

#define GEN_2(k, k_cx, acc, i) IF(EQ(i, 9), STOP_2, PROGRESS_2)(k, k_cx, acc, i)
#define GEN_2_HOOK()           GEN_2

#define STOP_2(k, k_cx, acc, i)     REC_CONTINUE(k, (k_cx), acc)
#define PROGRESS_2(k, k_cx, acc, i) REC_CONTINUE(GEN_2_HOOK, (k, k_cx), acc(INC(i)), INC(i))


Вывод 
((((((((((0), 1), 2), 3), 4), 5), 6), 7), 8), 9)(1)(2)(3)(4)(5)(6)(7)(8)(9)


Писать в стиле передачи продолжений — себя не любить. В идеале бы писать в обычном, прямом стиле, в то же время не озадачивая себя проблемами рекурсии… такая шайтан-машина уже реализована мною. Об этом — в следующем опусе.

© Habrahabr.ru