Используют ли какие-либо языки программирования общие рекурсивные функции в качестве основы?

23

Это наивный и, следовательно, возможно, некорректный вопрос, поэтому заранее извиняюсь!

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

Недавно я узнал, что тезис Черча-Тьюринга также показывает взаимную эквивалентность с третьей моделью вычислений: общими рекурсивными функциями . Есть ли языки программирования, которые используют это в качестве модели вычислений? Если нет, то есть ли техническая причина; то есть кроме "Никто еще не пробовал"?

Xophmeister
источник
1
Я бы сказал, что машины Тьюринга или машины с универсальным регистром являются основой процессорных ПЛ (сборочных ПЛ). У них нет функций. -рекурсивные функции являются основой императивных PL. У них нет функций высшего порядка. μ
Beroal
1
Я также рекомендовал бы изучить логику первого порядка и Пролог.
Beroal
1
До C ++ 11 constexprвы могли (/ должны были) использовать «шаблоны», чтобы вычисления выполнялись компилятором во время компиляции. Ограничения на шаблоны не допускают циклы, но вы можете использовать рекурсию для эмуляции любого цикла, так что в итоге вы получите средство Turing-complete (мета-программирование) как часть стандарта языка C ++, см., Например, stackoverflow.com/questions / 189172 / c-templates-turing-complete
JimmyB

Ответы:

45

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

Общие рекурсивные (т. Е. Mu -рекурсивные) функции значительно менее выразительны, чем лямбда-исчисления. Таким образом, они создают плохую основу для языков программирования. Вы также не правы в том, что ТМ является основой императивных PL: в действительности хорошие императивные языки программирования гораздо ближе к -calculus, чем к машинам Тьюринга.μλ

С точки зрения вычислимости -рекурсивные функции, машина Тьюринга и нетипизированный -calculus все эквивалентны. Однако нетипизированный LC обладает хорошими свойствами, которых нет ни у одного из двух других. Он очень прост (всего 3 синтаксических формы и 2 вычислительных правила), очень сложен и может относительно легко выражать программные конструкции. Более того, оснащенный простой системой типов (например, System расширенной с помощью ), -calculus может быть чрезвычайно выразительным в том смысле, что он может выразить многие сложные программные конструкции легко, правильно и композиционно. Вы также можете расширитьμλFωеяИксλλ-калькулум легко включать конструкции, которые не являются лямбдами. Ни одна из других вычислительных моделей, упомянутых выше, не обладает такими хорошими свойствами.

Машина Тьюринга не является ни композиционной, ни универсальной (вам нужно иметь ТМ для каждой задачи). Нет понятий «функции», «переменные» или «состав». Также не совсем верно, что ТМ являются основой императивных PL - FWIW, императивные PL намного, намного ближе к лямбда-исчислениям с управляющими операторами, чем к машинам Тьюринга. См. Подробное объяснение «Переписка между Алголом 60 и лямбда-нотацией» Питера Дж. Ландина . Если вы запрограммировали в Brainf ** k (который на самом деле реализует довольно простую машину Тьюринга), вы будете знать, что машины Тьюринга не являются хорошей идеей для программирования.

μ -рекурсивные функции аналогичны ТМ в этом отношении. Они композиционные, но не такие композиционные, как LC. Вы также просто не можете кодировать полезные программные конструкции в -рекурсивные функции. Более того, рекурсивные функции вычисляются только по , и для вычисления по чему-либо еще вам нужно кодировать ваши данные в натуральные числа, используя какую-то нумерацию Гёделя, что является болезненным.μμN

Таким образом, не случайно, что большинство языков программирования так или иначе основаны на -calculus! -исчисления обладает хорошими свойствами: выразительность, композиционность и расширяемость, что другие системы не хватает. Однако машины Тьюринга хороши для изучения вычислительной сложности, а -рекурсивные функции хороши для изучения логического понятия вычислимости. Они оба обладают выдающимися свойствами, которых нет у -calculus, но в области программирования -calculus явно выигрывает.λλμλλ

На самом деле существует множество систем Turing, но им не хватает каких-либо выдающихся свойств. Игра жизни Конвея, макросы LaTeX и даже (некоторые утверждают) ДНК полностью завершены по Тьюрингу, но никто не программирует (то есть занимается серьезным программированием) с Конвеем и не изучает вычислительную сложность с использованием макросов LaTeX. Им просто не хватает хороших свойств. Тьюринг сам по себе является почти бессмысленным , когда речь идет о программировании.

Кроме того, многие нетуринговы полные вычислительные системы очень полезны, когда дело доходит до программирования. Регулярные выражения и yacc не являются полными по Тьюрингу, но они чрезвычайно эффективны для решения определенного класса задач. Coq также не является полным по Тьюрингу, но невероятно мощным (на самом деле он считается гораздо более выразительным, чем его двоюродный брат по Тьюрингу, OCaml). Когда дело доходит до программирования, полнота по Тьюрингу не является ключевой, так как многие (близкие) бесполезные системы неинтересны по завершению по Тьюрингу. Вы не собираетесь утверждать, что Brainf ** k или Whitespace являются более мощными языками программирования, чем Coq, не так ли? Выразительная основой является ключом к мощным языкам программирования, и именно поэтому современные языки программирования почти всегда основаны наλ-исчисление.

xuq01
источник
7
«Никто не программирует с Конвеем» ... некоторые делают Строящую рабочую игру «Тетрис» в «Конвеевской игре жизни» ... и на самом деле она так же практична, как и пробел :)
Алексей Левенков
λλ
@AlexeiLevenkov Это совершенно не соответствует действительности. Пробел по сути является (простым) императивным языком, хотя и со странным синтаксисом. Он имеет средства для арифметики, базового потока управления, манипулирования стеком и кучей и ввода-вывода . Проект QFT, с другой стороны, требовал разработки компилятора от очень простого языка до сборки RISC, созданной для ЦП, построенного в сотовом автомате, подобном Wireworld, эмулированному с помощью OTCA Metapixels .
неконтекстовое правописание
@AlexeiLevenkov Лучший компилятор Cogol → CGoL требовал работы многих людей в течение четырех лет, в то время как существует проект под названием HaPyLi , компилирующий гораздо более сложный язык в Whitespace, который был написан одним человеком в свободное время.
неконтекстовое правописание
4

Печатание µ-recursive function programming languageв Google привело меня к этому репозиторию GitHub , поэтому ответ на ваш вопрос:

Да, и это называется близорукостью

Кстати, на Хаскеле написано.

Kapol
источник
μ
2
Конечно. Я просто предположил, что ОП хочет найти такой язык для изучения теории или чего-то еще, а не для того, чтобы на самом деле завоевать мир этим ;-)
Kapol