C99预处理器图灵完成了吗？
在发现Boost preprocessor's capabilities之后，我发现自己在想: C99预处理器图灵是否完整？
如果不符合，那么不符合条件还缺少什么？
回答 2
Stack Overflow用户
发布于 2012-05-10 08:44:10
宏不会直接以递归方式展开，但我们有办法解决这个问题。
在预处理器中进行递归的最简单方法是使用延迟表达式。延迟表达式是需要更多扫描才能完全展开的表达式：
#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为什么这很重要？当一个宏被扫描和展开时，它会创建一个禁用的上下文。此禁用上下文将导致引用当前展开的宏的令牌被绘制为蓝色。因此，一旦它被涂成蓝色，宏将不再扩展。这就是为什么宏不会递归展开的原因。然而，禁用上下文只存在于一次扫描期间，因此通过延迟扩展，我们可以防止宏被涂成蓝色。我们只需要对表达式应用更多的扫描。我们可以使用这个EVAL宏来做到这一点：
#define EVAL(...) EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__)))
#define EVAL5(...) __VA_ARGS__现在，如果我们想要使用递归实现一个REPEAT宏，首先我们需要一些递增和递减操作符来处理状态：
#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__)
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__
#define INC(x) PRIMITIVE_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
#define INC_9 9
#define DEC(x) PRIMITIVE_CAT(DEC_, x)
#define DEC_0 0
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC_4 3
#define DEC_5 4
#define DEC_6 5
#define DEC_7 6
#define DEC_8 7
#define DEC_9 8接下来，我们需要更多的宏来执行逻辑：
#define CHECK_N(x, n, ...) n
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,)
#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x))
#define NOT_0 ~, 1,
#define COMPL(b) PRIMITIVE_CAT(COMPL_, b)
#define COMPL_0 1
#define COMPL_1 0
#define BOOL(x) COMPL(NOT(x))
#define IIF(c) PRIMITIVE_CAT(IIF_, c)
#define IIF_0(t, ...) __VA_ARGS__
#define IIF_1(t, ...) t
#define IF(c) IIF(BOOL(c))
#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)现在有了所有这些宏，我们就可以编写一个递归的REPEAT宏了。我们使用REPEAT_INDIRECT宏递归引用其自身。这将防止宏被涂成蓝色，因为它将在不同的扫描上展开(并使用不同的禁用上下文)。我们在这里使用OBSTRUCT，它会将扩展推迟两次。这是必要的，因为条件WHEN已经应用了一次扫描。
#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现在，由于计数器的限制，此示例限制为10次重复。就像计算机中的重复计数器会受到有限内存的限制一样。可以将多个重复计数器组合在一起来解决此限制，就像在计算机中一样。此外，我们可以定义一个FOREVER宏：
#define FOREVER() \
? \
DEFER(FOREVER_INDIRECT) () ()
#define FOREVER_INDIRECT() FOREVER
// Outputs question marks forever
EVAL(FOREVER())这将尝试永远输出?，但最终将停止，因为没有更多的扫描被应用。现在的问题是，如果我们给它无限的扫描次数，这个算法会完成吗？这就是所谓的停顿问题，图灵完备性是证明停顿问题的不可判断性所必需的。如你所见，预处理器可以作为一种图灵完整语言，但它并不局限于计算机的有限内存，而是受到所应用的有限扫描次数的限制。
Stack Overflow用户
发布于 2010-06-29 06:52:32
它是有限的图灵完成(所有的计算机都是如此，因为它们没有无限的RAM)。看看你可以用Boost Preprocessor做的事情。
针对问题编辑进行编辑：
Boost的主要限制是宏的最大扩展深度，这是特定于编译器的。此外，实现递归的宏(FOR...ENUM...等)并不是真正的递归，它们只是由于一堆几乎相同的宏而呈现出来的。总的来说，这种限制与在实际递归语言中设置最大堆栈大小没有什么不同。
对于有限的图灵完备性来说，真正需要做的只有两件事(图灵兼容性？)是迭代/递归(等价构造)和条件分支。
https://stackoverflow.com/questions/3136686
复制相似问题