54

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?

Jay Conrod
  • 28,943
  • 19
  • 98
  • 110
  • 1
    Without your description, I'd ask if you were resolving a bet :) – Merlyn Morgan-Graham Aug 13 '10 at 22:10
  • 2
    It's in Unix, it's got hairy syntax, and it's surprisingly powerful. Most things like that are Turing-complete. I wasn't surprised twenty years ago when somebody showed me a vi macro Turing machine. – David Thornley Aug 16 '10 at 19:45
  • 3
    You can shell out to anything you like, including a Turing machine, during the construction of strings. Technically you've lost at this point. (We have Perl calls in our Makefiles. Sigh). – Ira Baxter Oct 30 '11 at 03:37

2 Answers2

58

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.

deinst
  • 18,402
  • 3
  • 47
  • 45
  • 4
    Once you have lambda, then I guess you can create a Y-combinator which gives you recursion. As you say, all downhill from there. – Jay Conrod Aug 13 '10 at 22:18
  • 16
    That is awesome. And scary. Mostly scary. – Jörg W Mittag Aug 13 '10 at 22:29
  • 1
    @Jorg Oleg is an awesome but scary guy. Mostly scary. Read the other stuff he has. – deinst Aug 13 '10 at 22:33
  • 2
    I just now realized whose site that is. I agree. Oleg Kiselyov is awesome. His purely functional OO system in 60 lines of code is pure genius. – Jörg W Mittag Aug 14 '10 at 08:49
  • 1
    @deinst: The answer isn't quite so easy. The constructs Kiselyov uses (string concatenation, *=* and *$(call)*; *$(foreach)* is not essential) do not provide Turing completeness: they do give you recursion (but only because these "functions" may contain *$(call)*s to themselves) but no way of stopping it (there is no conditional execution); however, *$(if)* and *$(subst) provide that, and with that, Turing completeness is reached in theory. However I'm unable to actually write, for instance, a recursive definition of the Fibonacci numbers with there primitives. – reinierpost Aug 16 '10 at 18:05
  • @deinst: nice! Initially I thought (and wrote) that your answer was wrong, but I didn't realize that $(call) can be used recursively. Some other mechanisms in GNU make cannot. – reinierpost Aug 17 '10 at 08:21
  • @deinst: That code is a perfect demonstration. Of course these same primitives can be used to implement decimal or hexadecimal number manipulation – reinierpost Aug 18 '10 at 08:43
10

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.

reinierpost
  • 8,425
  • 1
  • 38
  • 70
  • 4
    This is interesting, but I'd be very surprised if make could always detect recursive macros in the presence of something like $(eval). – Jay Conrod Aug 17 '10 at 22:48