C99 预处理器图灵完整吗？

StackOverflow https://stackoverflow.com/questions/3136686

题

发现后 增强预处理器的能力 我发现自己在想：C99 预处理器图灵完整吗？

如果没有的话，缺少什么才没有资格呢？

有帮助吗？

解决方案

这里 是滥用预处理器实现图灵机的一个示例。请注意，需要外部构建脚本来将预处理器的输出返回其输入中，因此预处理程序本身并不完整。尽管如此，这还是一个有趣的项目。

从上述项目的描述中：

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

保罗·富尔茨二世（Paul Fultz II）的答案令人印象深刻，肯定比我认为预处理器所能获得的要近，但这不是真正的图灵机器。 C预处理器具有某些限制，即使您有无限的内存和时间，也可以阻止其像图灵计算机那样执行任意程序。第5.2.4.1节 C规格 给出以下C编译器的最小限制：

  • 63个完整表达式中括号表达式的嵌套水平
  • 63个内部标识符或宏名称中的重要初始字符
  • 4095个宏标识符同时在一个预处理翻译单元中定义
  • 逻辑源线中的4095个字符

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

这与“无限记忆”限制根本不同。在这种情况下，规格专门说，即使具有无限的时间，内存等，也只需要符合这些限制的标准c编译器。 （或完全被拒绝）。某些实现可能具有较高的限制，或根本没有限制，但这被认为是“特定于实施的”，而不是标准的一部分。可以使用Paul Fultz II的方法来实现图灵机上的东西 一些特定的编译器实施 这没有有限的限制，但是从一般的意义上说：“这可以在任何任意的，标准的C99预处理器上做到这一点”，答案是否定的。由于这里的限制是内置在语言本身中的，而不仅仅是我们无法构建无限计算机的副作用，我说这会破坏图丁的完整性。

其他提示

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

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

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

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

要完成图灵，需要定义可能永远无法完成的递归 - 一个人打电话给它们 MU恢复操作员.

要定义这样的操作员，需要一个无限的标识符空间（如果对每个标识符进行了有限次数的评估），因为人们无法知道 先验 找到结果的上限。在代码中有限数量的运算符，因此需要能够检查无限数量的可能性。

所以 这类功能无法由C预处理器计算 因为在C预处理器中，定义的宏数量有限，并且每个宏仅扩展一次。

C预处理器使用 戴夫·普罗瑟（Dave Prosser）的算法 （由Dave Prosser撰写为WG14团队于1984年撰写）。在这种算法中，在第一次扩展的那一刻，宏被粉刷成蓝色。递归调用（或相互递归调用）不会扩展它，因为它在首次扩展开始的那一刻已经被涂成蓝色。因此，使用有限数量的预处理线路，不可能做出无限的功能调用（宏），这表征了MU回收操作员。

C预处理器只能计算 Sigma恢复运营商 .

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

它在限制范围内是图灵完备的（所有计算机都是如此，因为它们没有无限的 RAM）。查看您可以做的事情种类 升压预处理器.

编辑响应问题编辑：

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top