Там, где принято считать, что язык должен быть полным по Тьюрингу, чтобы быть хорошим, действительно ли возможно иметь «полезный» язык программирования, который не является полным по Тьюрингу?
Я должен пояснить, что речь идет о языках «программирования» в традиционном смысле, а не о языках разметки или запросов.
Ответы:
Coq , Agda , HOL и ACL2 - очень полезные и чрезвычайно мощные языки, хотя они не являются полными по Тьюрингу.
Общей чертой, которая делает их не полными по Тьюрингу, является тот факт, что всегда можно доказать завершение. Достаточно простого ограничения: рекурсивные вызовы допускаются только на предположительно структурно меньших терминах. Поэтому, хотя невозможно реализовать интерпретатор для языка, полного по Тьюрингу, или даже для самого языка, многие другие полезные вещи все еще возможны, например, сертифицированный компилятор Си .
источник
Я бы подумал, что термин «мини-язык» Йегге относится к тому факту, что часто полезно использовать язык для конкретных задач, когда для выполнения задачи язык не требует полноты тьюринга, и в этом суть -Turing полных языков может быть полезным. https://sites.google.com/site/steveyegge2/language-grubbing
Википедия отвечает на это очень хорошо, прямо в соответствии с тем, что сказал мой инстинкт. Сначала я думал о чистой математике, а потом вспомнил регулярное выражение, и в Википедии перечислены эпиграммы, которые, я думаю, будут в духе «чистой математики».
http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages
В нем также упоминается, что представления структуры данных не являются языками, но я думаю, что XSLT следует считать представлением вычислений, возможно, XPath не основывается на том, что Яннис сказал выше о том, что SQL является языком запросов, а не языком вычислений. Возможно, T-SQL или PL / SQL считаются языками вычислений, хотя, поскольку вы можете выполнять множество вычислений, используя их агрегаты, где обобщенная форма SQL, возможно, не определяет агрегаты.
источник
Я понимаю, что SQL довольно популярен среди бизнес-типов
источник
Полнота Тьюринга необходима для того, чтобы язык был пригоден для использования в качестве языка общего назначения. Но этого недостаточно , т. Е. Только потому, что он завершен по Тьюрингу, он не подходит для каждой проблемной области:
И наоборот, DSL подходит для проблемной области, для которой он был разработан (при условии, что он был действительно прилично спроектирован), даже без полноты по Тьюрингу:
* IIRC было доказано, что HTML с CSS-анимациями является завершением Тьюринга, используя их для реализации игры жизни Конвея на множестве флажков. Но полезность HTML сохраняется даже в браузерах, которые не поддерживают CSS-анимацию.
источник
На самом деле существуют языки программирования, где вы можете писать только «эффективные» программы. Эффективность в этом смысле означает, что каждая программа, написанная на таком языке, представляет язык в
P
. Беллантони, Ниггл и Швичтенберг описывают такой язык здесь .источник
Препроцессор C не является полным по Тьюрингу (по замыслу), однако он все же может реализовать интерпретатор для языка, который является полным по Тьюрингу (Order-the-language, как описано в документации, по сути, является просто прогоном мельница чисто функциональная вещь типа ML / Scheme, и она была бы относительно непримечательной - вероятно, довольно удобной в использовании - если бы не необычная реализация).
Уловка позади этого аналогична рассмотренным выше аргументам о реализации любой машины Тьюринга в конечной физической вселенной: препроцессор C не может предоставить языку бесконечное количество шагов или ячеек данных, но он может:
обеспечить неоправданно большой динамический ряд (2 ^ 64 или так по умолчанию), достаточно большой для решения наиболее реалистичных задач с использованием экспоненциального расширения процесса ( бормотание бормотать жизни Вселенной бормотания ).
используйте произвольное статическое ограничение для указанного выше числа, т. е. хотя число шагов должно быть некоторым конечным числом, вы можете изменить значение определенного ограничения во время «компиляции», изменив статические настройки механизма интерпретатора. Поскольку нет (теоретического) ограничения на действительное значение этого ограничения, его (теоретически) можно расширить, чтобы соответствовать требованию к месту для любой завершающей программы.
Не спорьте, что Order обязательно «полезен» сам по себе, или что любой механизм, реализованный на CPP, был бы, но это интересное подтверждение концепции. Он также предположительно динамически печатается , что необычно для этой области.
источник
Да, действительно возможно иметь полезный язык, который не является полным по Тьюрингу. Смотрите здесь: http://tkatchev.bitbucket.org/tab/examples.html
Другим примером полезного неполного языка Тьюринга является SQL. (И еще одна - это электронные таблицы, такие как Gnumeric или Excel, хотя на самом деле они не являются языками программирования.)
Относительно того, почему вы хотели бы, чтобы язык не был завершен по Тьюрингу: потому что это позволяет вам дать некоторые строгие гарантии поведения во время выполнения.
Проще говоря, полнота Тьюринга означает способность к рекурсии. Наличие рекурсии означает наличие потенциально неограниченных структур в памяти. Поскольку в реальном мире память не бесконечна, для полноты по Тьюрингу требуется управление памятью и / или сборка мусора.
Запрет рекурсии - отличный способ избежать действительно сложной проблемы управления ресурсами.
Нота бене! Быть неполным по Тьюрингу не обязательно означает, что любая программа обязательно прекратит работу. Неполный язык Тьюринга может позволить оценить бесконечный ленивый список.
источник
Один интересный «язык программирования субтьюринга» до сих пор не упоминался, поэтому я добавлю его.
Это называется "Crema" . Он описывает себя как:
Это довольно минималистичный и довольно низкий уровень.
Это должно выглядеть знакомо разработчикам на Си.
Первоначально он финансировался Агентством перспективных исследовательских проектов в области обороны (DARPA), но на момент написания статьи выглядит совершенно незатронутым. Но, возможно, кто-то все же заинтересован.
источник