Являются ли make-файлы Turing завершенными? - PullRequest
Новая
       6

Являются ли make-файлы Turing завершенными?

46 голосов
/ 14 августа 2010

В последнее время на работе я делаю перевод из Makefiles в альтернативную систему сборки.Я видел довольно симпатичный код Make в некоторых местах с использованием функциональных карт, фильтров и конструкций foreach.Это удивило меня, так как я думаю, что сценарии сборки должны быть как можно более декларативными.

В любом случае, это заставило меня задуматься: является ли язык Makefile (скажем, последняя версия GNU, чтобы быть конкретным) завершенным по Тьюрингу?

Ответы [ 2 ]

44 голосов
/ 14 августа 2010

Да, см. , это .Если у вас есть лямбда, оттуда все идет под гору.

Вот плагиат Пример Фибоначчи

Этого должно быть достаточно, чтобы заложить фундамент для большей общности (я должен вернуться к работеиграть больше.) 

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-битное ограничение на размеры номера.Облом.

9 голосов
/ 17 августа 2010

Теперь за отрицательный ответ: 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 - в дополнение ко всем другим вещам, которые затрудняют поддержку make-файлов.)

P.S. для недавнего проекта я написал патч для GNU make 3.82 , который снимает это ограничение с новой опцией -M (см. обсуждение ). У меня работает нормально.

...