Понимание макросов DEFER и OBSTRUCT

Я создал небольшую библиотеку метапрограммирования , которая реализует основные полезные конструкции, такие как REPEAT(times, x), IF(value, true, false), кортежи и т.д.

Большинство моих реализаций работают, перегружая макросы на основе их количества переменных аргументов или через счетчик:

// Example:
#define REPEAT_0(x) 
#define REPEAT_1(x) x REPEAT_0(x) 
#define REPEAT_2(x) x REPEAT_1(x)
#define REPEAT_3(x) x REPEAT_2(x)
// ...
// (these defines are generated using an external script)
// ...

#define REPEAT(count, x) CAT(REPEAT_, count)(x)

Это отлично работает, но я недавно встретил чрезвычайно интересную реализацию макрорекурсии Пола Фульца.

До раздела отложенное выражение я не мог понять его статью.

Однако у меня много проблем с пониманием использования DEFER и OBSTRUCT.

Paul реализует очень изящную версию REPEAT, которая не требует script -generated, как это:

#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)

#define REPEAT(count, macro, ...) \
    WHEN(count) \
    ( \
        OBSTRUCT(REPEAT_INDIRECT) () \
        ( \
            DEC(count), macro, __VA_ARGS__ \
        ) \
        OBSTRUCT(macro) \
        ( \
            DEC(count), __VA_ARGS__ \
        ) \
    )
#define REPEAT_INDIRECT() REPEAT

//An example of using this macro
#define M(i, _) i
EVAL(REPEAT(8, M, ~)) // 0 1 2 3 4 5 6 7

DEFER, OBSTRUCT и другие утилиты реализованы как таковые:

#define EMPTY()
#define DEFER(id) id EMPTY()
#define OBSTRUCT(...) __VA_ARGS__ DEFER(EMPTY)()
#define EXPAND(...) __VA_ARGS__

#define A() 123
A() // Expands to 123
DEFER(A)() // Expands to A () because it requires one more scan to fully expand
EXPAND(DEFER(A)()) // Expands to 123, because the EXPAND macro forces another scan

  • Когда препроцессор расширяет макрос, результат "окрашивается" до следующего сканирования - он не будет рекурсивно расширяться, если не произойдет дополнительное сканирование. Правильно ли это?

  • Увеличивает ли макрос EXPAND(...) дополнительное сканирование? Если это так, разрешает ли это сканирование макросы рекурсивно? Какая разница между EXPAND(...) и DEFER(id)?

    • Увеличивает ли DEFER два дополнительных сканирования?

  • Как насчет макроса OBSTRUCT(...)? Усиливает ли два дополнительных сканирования?

  • Теперь - почему OBSTRUCT требуется в рекурсивной реализации REPEAT? Почему бы DEFER или EXPAND работать здесь?

Ответы

Ответ 1

Использование макросов типа DEFER и сложной макрологии C в целом зависит от понимания того, как препроцессор C фактически расширяет макрокоманды. Он не просто пытается уменьшить все деревья выражений так, как это делает обычный язык программирования, а скорее работает на потоке линейных токенов и имеет неявный "курсор" в том месте, где он в настоящее время исследует поток для возможных замещений. В любом заданном "стеке" процесса расширения курсор никогда не перемещается назад, и как только токен передан в потоке, он не проверяется снова.

Просматривая первый пример операции DEFER:

 DEFER(A)()  // cursor starts at the head of the sequence
^            // identifies call to DEFER - push current position

 DEFER( A )()  // attempt to expand the argument (nothing to do)
       ^
 // replace occurrences of id in DEFER with A,
 // then replace the call to it with the substituted body

 A EMPTY() ()  // pop cursor position (start of pasted subsequence)
^              // doesn't find an expansion for A, move on
 A EMPTY() ()  // move to next token
  ^            // EMPTY() is a valid expansion
 A  ()         // replace EMPTY() with its body in the same way
   ^           // continuing...
 A ()          // `(` is not a macro, move on
  ^
 A ( )         // `)` is not a macro, move on
    ^
 A ()          // end of sequence, no more expansions
     ^

Курсор перемещался после A во время "повторного сканирования" тела DEFER после замены аргументов, что является второй и последней попыткой расширить этот набор токенов. Как только курсор переместился через A, он не возвращается к нему во время этой последовательности расширения, а так как "повторное сканирование" находится на верхнем уровне, следующая последовательность расширений отсутствует.

Теперь рассмотрим одно и то же выражение, но завернутый в вызов EXPAND:

 EXPAND(DEFER(A)())    // cursor starts at the head etc.
^                      // identifies call to EXPAND

 EXPAND( DEFER(A)() )  // attempt to expand the argument
        ^              // this does the same as the first
                       // example, in a NESTED CONTEXT

 // replace occurrences of __VA_ARGS__ in EXPAND with A ()
 // then replace the call with the substituted body

 A ()          // pop cursor position (start of pasted subsequence)
^              // identifies A, and can expand it this time

Поскольку списки аргументов расширяются в сложном контексте, а позиция курсора восстанавливается в позиции перед исходным вызовом для повторного сканирования, помещая вызов макроса в любой список аргументов макроса - даже тот, который на самом деле ничего не делает, как EXPAND - дает ему "свободный" дополнительный пробег курсором расширения, путем сброса позиции курсора в потоке дополнительное время для дополнительного повторного сканирования и, следовательно, предоставление каждого свежеприведенного выражения вызова (то есть, имя макроса и список аргументов в скобках) дополнительный шанс на распознавание расширителем. Таким образом, все EVAL это дает вам 363 (3 ^ 5 + 3 ^ 4 + 3 ^ 3 + 3 ^ 2 + 3, кто-то проверяет мою математику), бесплатный повторный поиск проходит.

Итак, обращаясь к вопросам в свете этого:

  • "painting blue" не работает совсем так (объяснение в вики немного ошибочно сформулировано, хотя это не так). Имя макроса, если оно сгенерировано внутри этого макроса, будет окрашено в синий цвет постоянно (C11 6.10.3.4 "[blue] токены больше не доступны для дальнейшей замены, даже если они позже (повторно) рассмотрены" ). Точка DEFER скорее состоит в том, чтобы гарантировать, что рекурсивный вызов не будет сгенерирован на проходе расширения макроса, но вместо этого... отложен... до внешнего этапа сканирования, после чего он не будет окрашен синий, потому что мы больше не внутри этого имени. Вот почему REPEAT_INDIRECT функционально; так что это может быть предотвращено от расширения во что-либо, упоминающее имя REPEAT, если мы все еще находимся в теле REPEAT. Он требует, по меньшей мере, одного дополнительного свободного прохода после того, как исходный REPEAT завершает, чтобы развернуть маркеры EMPTY.
  • да, EXPAND заставляет дополнительный проход расширения. Любой вызов макроса предоставляет один дополнительный проход расширения к любому выражению, переданному в списке аргументов.
    • Идея DEFER заключается в том, что вы не передаете ей целое выражение, а только часть "функции"; он вставляет разделитель между функцией и ее списком аргументов, который стоит один проход расширения для удаления.
    • поэтому разница между EXPAND и DEFER заключается в том, что DEFER налагает потребность в дополнительном проходе до того, как функция, которую вы передаете, расширится; и EXPAND предоставляет дополнительный проход. Таким образом, они друг друга обратны (и применяются вместе, как и в первом примере, эквивалентны вызову, который не используется).
  • да, OBSTRUCT стоит два прохода расширения до того, как функция, которую вы передаете, будет расширена. Это делает DEFER расширение спейсера EMPTY() одним (EMPTY EMPTY() ()), сжигая первый курсор reset при избавлении от вложенного EMPTY.
  • OBSTRUCT требуется вокруг REPEAT_INDIRECT, потому что WHEN расширяет (по истине) на вызов EXPAND, который сгорит один слой косвенности, пока мы все еще находимся в пределах вызова REPEAT. Если бы существовал только один слой (a DEFER), вложенный REPEAT был бы сгенерирован, пока мы все еще находимся в REPEAT контексте, в результате чего он будет окрашен в синий цвет и будет убивать рекурсию прямо там. Использование двух уровней с OBSTRUCT означает, что вложенный REPEAT не будет создан до тех пор, пока мы не достигнем повторного сканирования любого макрокоманда вне REPEAT, после чего мы сможем безопасно сгенерировать имя снова, потому что он выскочил из стека без расширения.

Таким образом, этот метод рекурсии работает с использованием внешнего источника большого количества повторов сканирования (EVAL) и откладывает расширение имени макроса внутри себя по меньшей мере одним проходом повторного сканирования, поэтому он происходит дальше стек вызовов. Первое расширение тела REPEAT происходит во время повторного сканирования EVAL[363], рекурсивный вызов откладывается до повторного сканирования EVAL[362], отложенного вложенного расширения... и так далее. Это не истинная рекурсия, поскольку она не может образовать бесконечный цикл, но вместо этого полагается на внешний источник кадров стека для записи.