Шаблон метапрограммирования: примитив рекурсивный?

Question

В этой статье автор утверждает:

... программа действительно показала, что механизм создания шаблона является примитивно-рекурсивным языком, который может выполнять нетривиальные вычисления при компиляциивремя.

Мне это показалось довольно интересным, так как я помогаю преподавать класс по теории вычислений, который углубляется в теорию примитивных рекурсивных функций.Однако у меня сложилось впечатление, что шаблонное метапрограммирование было завершено по Тьюрингу, что является более строгим утверждением, чем утверждение, что оно является примитивно-рекурсивным ... В конце концов, не очень сложно создать шаблонную метапрограмму, которая не останавливается.

Я что-то упустил?Является ли шаблон метапрограммирования строго примитивным рекурсивным языком, или я прав, полагая, что он охватывает более широкий спектр программ?

Answer 1

Полагаю, вы просто слишком много читаете в тексте, и «примитив» не подразумевается как «примитивно-рекурсивный», а скорее «рекурсивный язык» (звучит странно, я бы назвал этофункциональный язык, но неважно), который является примитивным.

Если вы посмотрите на TMP как на функциональный язык, он не очень сложный;таким образом, это примитивный.

Но вы правы, TMP определенно завершен по Тьюрингу.

Я сомневаюсь, что многие люди слышали о примитивных рекурсивных языках, и поэтому это просто неудачновыбор слов.

Answer 2

Программа Унруха демонстрировала только примитивную рекурсию, то есть зацикливание (я действительно присутствовал, когда это произошло!).Однако сразу было признано, что полная рекурсия была поддержана (потому что в действительности реализация не выполняла оптимизацию хвостовой записи).