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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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