Makefile是图灵完备的吗？

Question

最近在工作中，我一直在将Makefile翻译成另一种构建系统。我发现有些地方的Make代码使用了函数式map、filter和foreach结构，这让我很惊讶，因为我认为构建脚本应该尽可能声明式。

无论如何，这让我想到一个问题：Makefile语言（以最新的GNU make为例）是否是图灵完备的？

- Jay Conrod

---

没有您的描述，我会问您是否在解决一个赌注 :) - Merlyn Morgan-Graham

它在Unix中，语法复杂，但功能强大。像这样的大多数东西都是图灵完备的。当有人向我展示vi宏图灵机时，二十年前我并不感到惊讶。 - David Thornley

在构建字符串时，你可以调用任何你喜欢的东西，包括图灵机。从技术上讲，在这一点上，你已经失败了。（我们的 Makefile 中有 Perl 调用。叹气） - Ira Baxter

Answer 1

是的，参见这里。一旦你有lambda，其余部分就水到渠成了。

下面是一个剽窃的斐波那契数列的例子。

这已足以为更普遍的内容打下基础（我必须回去工作了，否则我会玩得更多）。

dec = $(patsubst .%,%,$1)

not = $(if $1,,.)

lteq = $(if $1,$(if $(findstring $1,$2),.,),.)
gteq = $(if $2,$(if $(findstring $2,$1),.,),.)
eq = $(and $(call lteq,$1,$2),$(call gteq,$1,$2))
lt = $(and $(call lteq,$1,$2),$(call not,$(call gteq,$1,$2)))

add = $1$2
sub = $(if $(call not,$2),$1,$(call sub,$(call dec,$1),$(call dec,$2)))
mul = $(if $(call not,$2),$2,$(call add,$1,$(call mul,$1,$(call dec,$2))))
fibo = $(if $(call lt,$1,..),$1,$(call add,$(call fibo,$(call dec,$1)),$(call fibo,$(call sub,$1,..))))
fact = $(if $(call lt,$1,..),.,$(call mul,$1,$(call fact,$(call dec,$1))))

numeral = $(words $(subst .,. ,$1))

go = $(or $(info $(call numeral,$(call mul,$1,$1)) $(call numeral,$(call fibo,$1)) $(call numeral,$(call fact,$1)) ),$(call go,.$1))

_ := $(call go,)

这个程序输出平方数、斐波那契数和阶乘。似乎有一个16位的数字大小限制。遗憾。

- deinst

---

一旦你有了lambda，那么我猜你就可以创建一个Y组合子来实现递归。正如你所说的，从那里开始一切都变得轻而易举。 - Jay Conrod

太棒了，同时也很可怕，大部分是可怕的。 - Jörg W Mittag

@Jorg Oleg是一个厉害但有点可怕的人。大多数时候是可怕的。看看他还有什么其他东西。 - deinst

我刚刚意识到那是谁的网站。我同意。Oleg Kiselyov很棒。他用60行代码实现的纯函数式面向对象系统是纯粹的天才。 - Jörg W Mittag

@deinst：答案并不那么简单。Kiselyov使用的结构（字符串连接，*=和$（call）；$（foreach）不是必要的）并没有提供图灵完备性：它们确实为您提供了递归（但仅因为这些“函数”可能包含对自身的$（call）），但没有停止它的方法（没有条件执行）；但是，$（if）和$（subst）*提供了这一点，在理论上达到了图灵完备性。然而，我无法使用这些原语实际编写例如斐波那契数列的递归定义。 - reinierpost

Answer 2

现在给出一个否定的答案： GNU make积极地阻止一些创建递归的机制：

1) 递归展开变量

并不是以“递归函数”的意义递归的：它们不能用自己来定义：

Actually make detects the infinite loop and reports an error.

（顺便说一句，我不认为在实践中允许它们有什么用处。）

2）规则链接

也不能递归：

No single implicit rule can appear more than once in a chain. (...)
This constraint has the added benefit of preventing any infinite loop
in the search for an implicit rule chain.

我在调试Makefile时花费了很多时间，除了其他使Makefile难以维护的因素外。

附注：最近我写了一个GNU make 3.82的补丁，通过新的-M选项去除了这个限制（请参见discussion）。对我来说它运行得很好。

- reinierpost

---

有趣，但如果make在存在$(eval)之类的东西时始终能够检测到递归宏，我会非常惊讶。 - Jay Conrod