Какова общая сложность построения канонического языкового представления?
Часто бывает удобно иметь каноническое представление языка (в моем случае это обычно языки, специфичные для предметной области); однако я считаю, что существуют строгие ограничения на выразительность участвующих языков, которые определяют, можно ли определить и / или создать каноническую форму для произвольной программы на этом языке. К сожалению, мне не удалось найти ссылки, о которых я (смутно) вспоминаю, читая об этом.
С одной стороны, кажется разумным, что создание канонического представления языка имеет сравнимую сложность со многими сложными задачами о графах (например, изоморфизмом графов), но с другой стороны, iirc, компиляторы, такие как gcc, yhc и ghc, используют промежуточные представления генерировать выходные данные в различных форматах (сборка, javascript и т. д.), так что это по крайней мере в некоторых формах решенная проблема.
Когда можно определить / сгенерировать каноническую форму для данного языка? (Насколько выразительным может быть этот язык, и как выразительность языка влияет на полезность канонических форм?) Пожалуйста, предоставьте ссылки или доказательства, если это вообще возможно.
Редактировать: Например, Регулярный язык (например, "чистая" форма регулярных выражений) не может выразить многие из тех же вещей, что и язык, полный по Тьюрингу. Другими словами, вы не можете написать веб-сервер на обычном языке, но вы можете сделать это с помощью лямбда-исчисления). Мой вопрос о теоретических возможностях и имеет конкретный ответ, касающийся теории сложности. Если у меня есть DSL, который необходимо передать в другую систему, часто будет полезно сгенерировать каноническую форму этого кода перед его передачей, так как это отделит независимые представления, используемые двумя разными системами. Однако, если для перевода языка, полного по Тьюрингу, в каноническую форму используется P-Space или NP-Complete, вам не следует тратить время на создание канонической формы - либо найдите другой способ сделать это, либо уменьшить сложность языка до того, что можно канонизировать за полиномиальное время.
2 ответа
Под "каноническим представлением" я предполагаю, что вы имеете в виду следующее: назовите программы P и Q эквивалентными, если они "делают одно и то же" на одних и тех же входах. "Делать одно и то же" означает, что программы имеют одинаковый выходной сигнал, и либо обе программы останавливаются через конечное время, либо обе входят в бесконечный цикл. Это отношение эквивалентности определяет классы эквивалентности в наборе всех программ. "Каноническое представление" программы P - это программа P, принадлежащая одному и тому же классу эквивалентности, и вам требуется, чтобы все члены одного и того же класса эквивалентности имели одинаковое каноническое представление.
Для языков, полных по Тьюрингу, вычислимое по Тьюрингу каноническое представление позволит вам решить проблему остановки следующим образом: сначала напишите программу, состоящую из бесконечного цикла, и найдите ее каноническое представление Q. Затем для любой входной программы P сначала механически преобразуйте ее в программу P0, которая делает то же самое, за исключением того, что она не производит выходных данных, а затем найдите каноническое представление P0'этой программы. Если результатом является Q, вы знаете, что P0 не останавливается, и, следовательно, P не останавливается. В противном случае P0 останавливается, как и P.
Для еще большего удовольствия прочитайте некоторые работы Грегори Чейтина о том, что он называет "элегантными" программами.
Мне кажется, что компиляция на ассемблере может быть отнесена к категории как перевод в каноническую форму на практике.