Are makefiles Turing complete?

问题:

Lately at work, I've been doing some translation from Makefiles to an alternative build system. I've seen some pretty hairy Make code in some places using functional map, filter, and foreach constructs. This surprised me since I think build scripts ought to be as declarative as possible.

Anyway, this got me thinking: is the Makefile language (say the latest GNU make to be specific) Turing complete?

回答1:

Yes, see this. Once you have lambda, it's all downhill from there.

Here is a plagiarized Fibonacci example

This should be enough to build a foundation for more generality (I've got to get back to work, or I'd play more.)

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,)

This prints out squares, fibonacci numbers and factorials. There appears to be a 16 bit limit on number sizes. Bummer.

回答2:

Now for a negative answer: GNU make actively blocks some mechanisms to create recursion:

1) Recursively expanded variables

aren't recursive in the "recursive function" sense: they can't be defined in terms of themselves:

Actually make detects the infinite loop and reports an error.

(I don't see how allowing them could be useful in practice, by the way.)

2) Rule chaining

can't be recursive, either:

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.

(I lost quite a lot of time over this while debugging my Makefiles - in addition to all the other things that make makefiles hard to maintain.)

P.S. for a recent project I wrote a patch to GNU make 3.82 which removes this limitation with a new -M option (see discussion). It works fine for me.