C99预处理器图灵是否完整？
在发现Boost预处理器的function后，我发现自己在想：C99预处理器Turing是否完成？
如果不是，那么缺less什么资格？
这里是滥用预处理器来实现一个图灵机的例子。 请注意，需要一个外部构build脚本来将预处理器的输出反馈到其input中，因此预处理器本身并不是图灵完整的。 不过，这是一个有趣的项目。
从上述项目的描述来看：
预处理器不是图灵完成的，至less在程序只进行一次预处理的情况下是不行的 。 即使允许程序自身包含，情况也是如此。 （原因在于，对于一个给定的程序，预处理器只有有限的状态数量，加上由文件包含的地方组成的堆栈，这只是一个下推自动机。
Paul Fultz II的答案相当令人印象深刻，它的确比我认为的预处理器所能获得的更接近，但它不是一个真正的图灵机器。 C预处理器有一定的限制，即使你拥有无限的内存和时间，也可以阻止它像一个图灵机一样执行一个任意的程序。 C规范的第5.2.4.1节给出了C编译器的以下最小限制：
- 在一个完整expression式中嵌套expression式的嵌套expression式
- 内部标识符或macros名称中的63个重要的初始字符
- 在一个预处理翻译单元中同时定义了4095个macros标识符
- 逻辑源代码行中有4095个字符
下面的计数器机制需要每个值的macros定义，所以macros定义的限制会限制你可以循环的次数（ EVAL(REPEAT(4100, M, ~))会产生未定义的行为）。 这实质上是对你可以执行的程序的复杂性进行限制。 多层次扩张的嵌套和复杂性也可能触及其他限制之一。
这与“无限记忆”的局限性根本不同。 在这种情况下，规范特别指出，只要符合标准的C编译器即使具有无限的时间，内存等，也只需符合这些限制即可。任何超出这些限制的input文件都可能以不可预知或未定义的方式处理（或直接拒绝）。 有些实现可能有更高的限制，或者根本没有限制，但是这被认为是“特定实现”而不是标准的一部分。 有可能使用Paul Fultz II的方法在一些没有限制的特定编译器实现上实现类似于图灵机的东西，但是一般意义上说“这可以在任何符合标准的C99预处理器“， 答案是不。 由于这里的限制是build立在语言本身之上的，而不仅仅是我们无法构build一台无限的计算机的一个副作用，所以我认为图灵是完整的。
macrosmacros不会直接recursion地扩展，但是有办法可以解决这个问题。
在预处理器中进行recursion最简单的方法是使用延迟expression式。 延迟expression式是需要更多扫描才能完全展开的expression式：
#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
为什么这很重要？ 那么当一个macros被扫描和扩展，它创build一个禁用上下文。 这种禁用的上下文将导致引用当前扩展macros的令牌被绘成蓝色。 因此，一旦被涂成蓝色，macros观将不再扩大。 这就是为什么macros不能recursion地扩展。 但是，在一次扫描中只存在禁用的上下文，所以通过推迟扩展，我们可以防止我们的macros变成蓝色。 我们只需要对expression式应用更多的扫描。 我们可以使用这个EVALmacros来做到这一点：
#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__
现在，如果我们要使用recursion实现REPEATmacros，首先我们需要一些增量和减量运算符来处理状态：
#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
接下来我们需要更多的macros来做逻辑：
#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)
现在用所有这些macros，我们可以写一个recursion的REPEATmacros。 我们使用REPEAT_INDIRECTmacros来recursion地引用自身。 这可以防止macros被绘成蓝色，因为它将在不同的扫描上展开（并使用不同的禁用上下文）。 我们在这里使用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次重复。 就像在计算机中的重复计数器将受限于有限的内存。 可以将多个重复计数器组合在一起来解决这个限制，就像在电脑中一样。 此外，我们可以定义一个FOREVERmacros：
#define FOREVER() \ ? \ DEFER(FOREVER_INDIRECT) () () #define FOREVER_INDIRECT() FOREVER // Outputs question marks forever EVAL(FOREVER())
这将尝试输出? 永远，但最终会停止，因为没有更多的扫描应用。 现在的问题是，如果我们给它无限次的扫描，这个algorithm会完成吗？ 这被称为暂停问题，图灵完备性是certificate暂停问题的不确定性所必需的。 正如你所看到的那样，预处理器可以作为一个图灵完备的语言，但并不局限于计算机的有限存储器，而是受限于应用的有限数量的扫描。
这是图灵在限制内完成的（因为所有的计算机都没有无限的RAM）。 看看你能用Boost预处理器做的事情。
编辑回应问题编辑：
Boost的主要限制是编译器特定的最大macros扩展深度。 另外，实现recursion（FOR …，ENUM …等）的macros并不是真正的recursion，它们只是由于一堆近乎相同的macros而出现。 总的来说，这个限制与实际recursion语言中的最大堆栈大小没有什么不同。
对于有限的图灵完备性（图灵兼容性）来说，唯一真正必需的两件事是迭代/recursion（等价构造）和条件分支。
要完成图灵，需要定义可能永远不会完成的recursion（一个称为murecursion运算符 – https://en.wikipedia.org/wiki/%CE%9C-recursive_function ）。
为了定义这样的操作符，需要无限的标识符空间（在每个标识符被评估有限次数的情况下），因为人们不能先验地知道发现结果的时间的上限。 在代码中有限数量的操作员需要能够检查无限数量的可能性。
所以这个类的函数不能由C预处理器来计算。
C预处理器只能计算sigmarecursion运算符 – https://en.wikipedia.org/wiki/Primitive_recursive_function 。
有关详细信息，请参阅Marvin L. Minsky（1967）的计算过程 – 计算：有限与无限机器，Prentice-Hall，Inc. Englewood Cliffs，NJ等。
