Какова общая сложность построения канонического языкового представления?

Question

Часто удобно иметь каноническое представление языка (в моем случае это обычно языки, специфичные для предметной области); однако я считаю, что существуют строгие ограничения на выразительность участвующих языков, которые определяют, можно ли определить и / или создать каноническую форму для произвольной программы на этом языке. К сожалению, мне не удалось найти ссылки, о которых я (смутно) вспоминаю, читая об этом.

С одной стороны, кажется разумным, что создание канонического представления языка имеет сопоставимую сложность со многими сложными задачами о графах (например, изоморфизм графов), но с другой стороны, iirc, компиляторы, такие как gcc, yhc и ghc используйте промежуточные представления для генерации выходных данных в различных форматах (сборка, javascript и т. д.), так что, по крайней мере, в некоторых формах это решаемая проблема.

Когда можно определить / сгенерировать каноническую форму для данного языка? (Насколько выразительным может быть этот язык и как языковая выразительность влияет на полезность канонических форм?) Пожалуйста, предоставьте ссылки или доказательства, если это вообще возможно.

Редактировать: Например, Regular Language (например, «чистая» форма регулярных выражений) не может выразить многие из тех вещей, которые Turing- полный язык может. Другими словами, вы не можете написать веб-сервер на обычном языке, но вы можете сделать это с помощью лямбда-исчисления). Мой вопрос о теоретических возможностях и имеет конкретный ответ, касающийся теории сложности. Если у меня есть DSL, который необходимо передать в другую систему, часто будет полезно сгенерировать каноническую форму этого кода перед его передачей, поскольку это будет разъединять независимые представления, используемые двумя разными системами. Однако , если это P-Space complete или NP-Complete для перевода полного по Тьюрингу языка в каноническую форму, то вам не следует тратить время на создание канонической формы - либо найдите другую способ сделать это или уменьшить сложность языка до того, что можно канонизировать за полиномиальное время.

Answer 1

Под «каноническим представлением» я предполагаю, что вы имеете в виду следующее: Вызовите программы P и Q эквивалент , если они «делают одно и то же» на одном и том же входы. «Делать одно и то же» означает, что программы имеют одинаковый выходной сигнал, и обе программы останавливаются через конечное время или обе входят в бесконечный цикл. Это отношение эквивалентности определяет классы эквивалентности в наборе всех программ. «Каноническое представление» программы P - это программа P ', принадлежащая одному и тому же классу эквивалентности, и вам требуется, чтобы все члены одного и того же класса эквивалентности имели одинаковое каноническое представление.

Для языков, полных по Тьюрингу, вычислимое по Тьюрингу каноническое представление позволило бы вам решить проблему остановки следующим образом: сначала напишите программу, состоящую из бесконечного цикла, и найдите ее каноническое представление Q . Затем для любой входной программы P сначала механически преобразуйте ее в программу P ₀ , которая делает то же самое, за исключением того, что она не производит вывод, а затем найдите каноническое представление P ₀ 'этой программы. Если результат равен Q , вы знаете, что P ₀ не останавливается и, следовательно, P . В противном случае P ₀ останавливается, как и P .

Для еще большего удовольствия, прочитайте некоторые из работ Грегори Чейтина над тем, что он называет "элегантными" программами.

Answer 2

Мне кажется, что компиляция на ассемблере может быть отнесена к категории как перевод в каноническую форму на практике.