Действительно ли возможно иметь «полезный» язык программирования, который не является полным по Тьюрингу?

37

Там, где принято считать, что язык должен быть полным по Тьюрингу, чтобы быть хорошим, действительно ли возможно иметь «полезный» язык программирования, который не является полным по Тьюрингу?

Я должен пояснить, что речь идет о языках «программирования» в традиционном смысле, а не о языках разметки или запросов.

PhonicUK
источник
3
@PhonicUK SQL сначала не был завершен
Ryathal
4
@Ryathal SQL - это не язык программирования, а язык запросов.
Яннис
2
@PhonicUK Ваш вопрос в комментарии действительно стоит того, замените опубликованный вопрос на этот, иначе он будет закрыт как неконструктивный. На самом деле есть полезные нетуринговые полные языки, и мне было бы интересно узнать подробности о них.
Джимми Хоффа
5
регулярное выражение еще не завершено, но оно широко используется
трещотка урод
3
@DavidHammen Фактические реализации ограничены, да, из-за ограничений нашей физической вселенной (может только построить ограниченную память, может только запустить машину в течение ограниченного времени, прежде чем она выйдет из строя). Но это не значит, что языки ограничены. IOW полная спецификация языка не требует от реализации наложения таких ограничений на программу, в то время как язык не-TC требует, например, доказательства завершения.

Ответы:

48

Coq , Agda , HOL и ACL2 - очень полезные и чрезвычайно мощные языки, хотя они не являются полными по Тьюрингу.

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

SK-логика
источник
2
Для тех, кто не знаком с этими языками, не могли бы вы подробнее рассказать о том, что им не хватает, что делает их неполными по Тьюрингу, и о некоторых примерах вещей, построенных на этих языках?
PhonicUK
8
@PhonicUK: компилятор Си не является реализация C . Это инструмент, который преобразует код на одном языке (C) в другой (обычно машинный код). Это не означает, что сам компилятор C эквивалентен любой случайной программе на C.
Йоахим Зауэр
9
@PhonicUK, вы не можете внедрить интерпретатор для языка, полного по Тьюрингу, в язык, не полный по Тьюрингу. Но вы, конечно, можете реализовать компилятор (поскольку процессор с полной Тьюрингом выполнит реальную оценку).
SK-logic
11
@ SK-логика: "Конечно?" Это возможно только для C, потому что это довольно простой язык. Это невозможно для C ++, потому что компилятор должен интерпретировать код шаблона (который завершается по Тьюрингу во время компиляции).
MSalters
11
@MSalters Да, если компиляция языка завершена по Тьюрингу, компилятор для него должен быть написан на языке полного тьюринга. Что также довольно очевидно (не говоря уже о тавтологии). Однако обратите внимание, что стандарт C ++ допускает ограничения на входные программы, такие как максимальная глубина оценки для экземпляров шаблона (и существующие реализации допускают это). Если я не ошибаюсь, это означает, что возможен нетюрирующий полный компилятор C ++ (конечно, за исключением несвязанных проблем).
12

Я бы подумал, что термин «мини-язык» Йегге относится к тому факту, что часто полезно использовать язык для конкретных задач, когда для выполнения задачи язык не требует полноты тьюринга, и в этом суть -Turing полных языков может быть полезным. https://sites.google.com/site/steveyegge2/language-grubbing

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

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Нетурингово-полные языки

Существует много вычислительных языков, которые не являются полными по Тьюрингу. Одним из таких примеров является набор регулярных языков, чаще всего регулярных выражений, которые генерируются конечными автоматами. Более мощным, но все еще не полным по Тьюрингу расширением конечных автоматов является категория автоматов с понижением и бесконтекстных грамматик, которые обычно используются для генерации деревьев разбора на начальном этапе компиляции программы. Дополнительные примеры включают в себя некоторые из ранних версий языков пиксельных шейдеров, встроенных в расширения Direct3D и OpenGL, или ряд математических формул в электронной таблице без циклов. [Цитата необходима] В целом функциональных языках программирования все функции являются полными и должны прекратить, такие как благотворительность и эпиграмма. Благотворительность использует систему типов и управляющие конструкции, основанные на теории категорий,

Языки данных

Понятие полноты по Тьюрингу не применяется к таким языкам, как XML, JSON, YAML и S-выражения, поскольку они обычно используются для представления структурированных данных, а не для описания вычислений. Их иногда называют языками разметки или, точнее, «языками описания данных».

В нем также упоминается, что представления структуры данных не являются языками, но я думаю, что XSLT следует считать представлением вычислений, возможно, XPath не основывается на том, что Яннис сказал выше о том, что SQL является языком запросов, а не языком вычислений. Возможно, T-SQL или PL / SQL считаются языками вычислений, хотя, поскольку вы можете выполнять множество вычислений, используя их агрегаты, где обобщенная форма SQL, возможно, не определяет агрегаты.

Джимми Хоффа
источник
8

Я понимаю, что SQL довольно популярен среди бизнес-типов

Мартин Беккет
источник
3
SQL - это язык запросов, а не язык программирования.
PhonicUK
4
@PhonicUK: а в чем разница между языком запросов и языком программирования?
Йоахим Зауэр
8
@PhonicUK - Tex - это язык текстовой разметки, и он завершен по Тьюрингу
Martin Beckett
3
современные реализации sql, насколько я знаю, завершены.
Шабун
6
@shabunc IIRC только с хранимыми процедурами. Аргументация становится немного круглой, если она не завершена по Тьюрингу, то это не язык программирования - поэтому все языки "программирования" - TC
Мартин Беккет
5

Полнота Тьюринга необходима для того, чтобы язык был пригоден для использования в качестве языка общего назначения. Но этого недостаточно , т. Е. Только потому, что он завершен по Тьюрингу, он не подходит для каждой проблемной области:

  • Доказано, что пробелы являются завершенными по Тьюрингу, но, очевидно, не подходят для любой проблемной области вне развлечений для программистов.
  • Шаблоны C ++ доказали свою полную готовность по Тьюрингу, но на самом деле вы никогда не будете писать целые программы с ними.

И наоборот, DSL подходит для проблемной области, для которой он был разработан (при условии, что он был действительно прилично спроектирован), даже без полноты по Тьюрингу:

  • HTML * предоставляет краткий способ описания дерева DOM. Хотя JavaScript завершен по Тьюрингу и может использоваться для того же, он гораздо более шумный и неясный
  • XPath и другие языки запросов, PCRE без встроенного кода и тому подобное - все это мощные инструменты для той единственной работы, для которой они были разработаны

* IIRC было доказано, что HTML с CSS-анимациями является завершением Тьюринга, используя их для реализации игры жизни Конвея на множестве флажков. Но полезность HTML сохраняется даже в браузерах, которые не поддерживают CSS-анимацию.

back2dos
источник
2
У вас есть ссылка на жизнь Конвея, реализованная в CSS?
RBerteig
Я не знаю о реализации CGOL в CSS, но я знаю, что Правило 110 было реализовано. Кажется, не могу найти его, кажется, он был перемещен.
Кристиан Манн
-1 Очень интересно, но не
отвечает
2
@mattnz: Неверно. Я привожу конкретные примеры языков, не являющихся полными по Тьюрингу, которые полезны, и я думаю, что это правильный ответ на вопрос: «Действительно ли возможно иметь« полезный »язык программирования, который не является полным по Тьюрингу?», В отличие от другого ответа здесь
back2dos
3

На самом деле существуют языки программирования, где вы можете писать только «эффективные» программы. Эффективность в этом смысле означает, что каждая программа, написанная на таком языке, представляет язык в P. Беллантони, Ниггл и Швичтенберг описывают такой язык здесь .

SpaceTrucker
источник
1

Препроцессор C не является полным по Тьюрингу (по замыслу), однако он все же может реализовать интерпретатор для языка, который является полным по Тьюрингу (Order-the-language, как описано в документации, по сути, является просто прогоном мельница чисто функциональная вещь типа ML / Scheme, и она была бы относительно непримечательной - вероятно, довольно удобной в использовании - если бы не необычная реализация).

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

  1. обеспечить неоправданно большой динамический ряд (2 ^ 64 или так по умолчанию), достаточно большой для решения наиболее реалистичных задач с использованием экспоненциального расширения процесса ( бормотание бормотать жизни Вселенной бормотания ).

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

Не спорьте, что Order обязательно «полезен» сам по себе, или что любой механизм, реализованный на CPP, был бы, но это интересное подтверждение концепции. Он также предположительно динамически печатается , что необычно для этой области.

Leushenko
источник
Upvote за бормотание в середине лекции.
jpaugh
-1

Да, действительно возможно иметь полезный язык, который не является полным по Тьюрингу. Смотрите здесь: http://tkatchev.bitbucket.org/tab/examples.html

Другим примером полезного неполного языка Тьюринга является SQL. (И еще одна - это электронные таблицы, такие как Gnumeric или Excel, хотя на самом деле они не являются языками программирования.)

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

Проще говоря, полнота Тьюринга означает способность к рекурсии. Наличие рекурсии означает наличие потенциально неограниченных структур в памяти. Поскольку в реальном мире память не бесконечна, для полноты по Тьюрингу требуется управление памятью и / или сборка мусора.

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

Нота бене! Быть неполным по Тьюрингу не обязательно означает, что любая программа обязательно прекратит работу. Неполный язык Тьюринга может позволить оценить бесконечный ленивый список.

Ткачев
источник
-1

Один интересный «язык программирования субтьюринга» до сих пор не упоминался, поэтому я добавлю его.

Это называется "Crema" . Он описывает себя как:

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

Это довольно минималистичный и довольно низкий уровень.

Это должно выглядеть знакомо разработчикам на Си.

Первоначально он финансировался Агентством перспективных исследовательских проектов в области обороны (DARPA), но на момент написания статьи выглядит совершенно незатронутым. Но, возможно, кто-то все же заинтересован.

Матеуш Ковалевски
источник