ansaurus

Question

Answer 1

+8 A:

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

Edit This is incorrect. See the note by Ranierpost. (I cannot delete this. Sorry)

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 2010-08-13 22:04:09

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 2010-08-13 22:18:21

That is awesome. And scary. Mostly scary.

Jörg W Mittag 2010-08-13 22:29:05

@Jorg Oleg is an awesome but scary guy. Mostly scary. Read the other stuff he has.

deinst 2010-08-13 22:33:04

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 2010-08-14 08:49:32

@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 2010-08-16 18:05:15

@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 2010-08-17 08:21:35

@deinst: That code is a perfect demonstration. Of course these same primitives can be used to implement decimal or hexadecimal number manipulation

reinierpost 2010-08-18 08:43:27

Answer 2

+1 A:

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 this 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.)

reinierpost 2010-08-17 08:44:33

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 2010-08-17 22:48:18

ansaurus

tags:

views:

answers:

Are makefiles Turing complete?

related questions