80

在发现Boost 预处理器的功能后，我发现自己想知道：C99 预处理器 Turing 是否完整？

如果没有，不符合资格缺少什么？

4

4 回答 4

155

好吧，宏不会直接递归扩展，但是我们可以通过一些方法来解决这个问题。

在预处理器中进行递归的最简单方法是使用延迟表达式。延迟表达式是需要更多扫描才能完全展开的表达式：

#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())

这将尝试?永远输出，但最终会因为不再应用扫描而停止。现在的问题是，如果我们给它无限次扫描，这个算法会完成吗？这被称为停机问题，图灵完备性对于证明停机问题的不可判定性是必要的。如您所见，预处理器可以充当图灵完备的语言，但不受限于计算机的有限内存，而是受到有限扫描次数的限制。

于 2012-05-10T00:44:10.433 回答
41

这是一个滥用预处理器来实现图灵机的例子。请注意，需要一个外部构建脚本来将预处理器的输出反馈到其输入中，因此预处理器本身并不是图灵完备的。不过，这是一个有趣的项目。

从上述链接项目的描述中：

预处理器不是图灵完备的，至少在程序只预处理一次的情况下是这样。即使允许程序包含自身也是如此。（原因是对于给定的程序，预处理器只有有限数量的状态，加上一个由包含文件的位置组成的堆栈。这只是一个下推自动机。）

Paul Fultz II 的回答令人印象深刻，而且肯定比我想象的预处理器所能得到的更接近，但它不是真正的图灵机。C 预处理器有一定的限制，即使你有无限的内存和时间，它也无法像图灵机一样执行任意程序。C 规范的第 5.2.4.1 节给出了 C 编译器的以下最低限制：

  • 完整表达式中的 63 个括号表达式嵌套级别
  • 内部标识符或宏名称中的 63 个有效初始字符
  • 在一个预处理翻译单元中同时定义 4095 个宏标识符
  • 逻辑源代码行中有 4095 个字符

下面的计数器机制要求每个值都有一个宏定义，因此宏定义限制将限制您可以循环的次数（EVAL(REPEAT(4100, M, ~))会产生未定义的行为）。这实质上限制了您可以执行的程序的复杂性。多级扩展的嵌套和复杂性也可能达到其他限制之一。

这与“无限内存”限制根本不同。在这种情况下，规范明确规定符合标准的 C 编译器只需要符合这些限制，即使它有无限的时间、内存等。任何超过这些限制的输入文件都可以以不可预测或未定义的方式处理（或直接拒绝）。一些实现可能有更高的限制，或者根本没有限制，但这被认为是“特定于实现的”而不是标准的一部分。可以使用 Paul Fultz II 的方法在某些特定的编译器实现上实现类似图灵机的东西这没有有限的限制，但在一般意义上“这可以在任何任意的、符合标准的 C99 预处理器上完成”，答案是否定的。由于这里的限制是语言本身内置的，而不仅仅是我们无法构建无限计算机的副作用，我说这破坏了图灵的完整性。

于 2010-06-28T23:10:43.833 回答
10

为了图灵完备，需要定义可能永远不会完成的递归——称之为mu-recursive operator。

要定义这样的运算符，需要定义标识符的无限空间（以防每个标识符被评估有限次），因为我们无法先验地知道找到结果的时间上限。由于代码中的运算符数量有限，因此需要能够检查无限数量的可能性。

因此，此类函数不能由 C 预处理器计算，因为在 C 预处理器中定义的宏数量有限，并且每个宏仅扩展一次。

C 预处理器使用Dave Prosser 的算法（由 Dave Prosser 于 1984 年为 WG14 团队编写）。在该算法中，宏在第一次展开时被涂成蓝色；递归调用（或相互递归调用）不会扩展它，因为在第一次扩展开始时它已经被涂成蓝色。因此，对于有限数量的预处理行，不可能无限调用函数（宏），这是 mu 递归运算符的特征。

C 预处理器只能计算sigma-recursive 运算符 。

有关详细信息，请参阅Marvin L. Minsky (1967) 的计算过程——计算：有限和无限机器，Prentice-Hall, Inc. Englewood Cliffs, NJ 等。

于 2016-05-26T14:11:38.257 回答
4

它在限制内是图灵完备的（所有计算机都是如此，因为它们没有无限的 RAM）。看看你可以用Boost Preprocessor做什么。

针对问题编辑进行编辑：

Boost 的主要限制是编译器特定的最大宏扩展深度。此外，实现递归的宏（FOR ...、ENUM ... 等）并不是真正的递归，它们只是由于一堆几乎相同的宏而出现。总的来说，这个限制与实际递归语言中的最大堆栈大小没有什么不同。

对于有限的图灵完备性（图灵兼容性？）真正需要的唯一两件事是迭代/递归（等效结构）和条件分支。

于 2010-06-28T22:52:32.453 回答