C99预处理器图灵是否完整？

Question

在发现Boost预处理器的功能后,我发现自己在想:C99预处理器Turing是否完整？

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

Answer 1

好的宏不会直接递归扩展,但我们有办法解决这个问题.

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

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

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

Answer 2

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

从上述相关项目的描述:

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

Paul Fultz II的答案相当令人印象深刻,当然比我认为预处理器可以得到的更接近,但它并不是真正的图灵机器.即使你有无限的内存和时间,C预处理器也有一定的限制,可以阻止它像图灵机一样执行任意程序.C规范的 5.2.4.1节给出了C编译器的以下最小限制:

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

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

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

Answer 3

这是图灵在极限范围内完成(因为它们没有无限的RAM,所有计算机都是如此).查看使用Boost预处理器可以执行的操作.

编辑以回答问题编辑:

Boost的主要限制是最大的宏扩展深度,它是特定于编译器的.此外,实现递归的宏(FOR ...,ENUM ......等)并不是真正的递归,它们只是出现这种方式,这要归功于一堆几乎相同的宏.从大图来看,这种限制与实际递归语言中的最大堆栈大小没有什么不同.

有限图灵完全性(图灵兼容性？)真正需要的两件事是迭代/递归(等效构造)和条件分支.

Answer 4

为了使Turing完整，需要定义可能永远不会完成的递归-将其称为mu-recursive运算符。

为了定义这样的运算符，一个人需要定义的标识符的无限空间（在每个标识符被评估有限次的情况下），因为不能先验地知道找到结果的时间上限。在代码内部包含有限数量的运算符的情况下，人们需要能够检查无限数量的可能性。

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

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

C预处理器只能计算sigma递归运算符 。

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