Wie ist die allgemeine Komplexität eine kanonische Sprache Darstellung des Gebäudes?

Question

Es ist oft praktisch, eine kanonische Darstellung einer Sprache zu haben (in meinem Fall sind sie in der Regel domänenspezifische Sprachen); aber ich glaube, es gibt strenge Grenzen für die Ausdruckskraft der beteiligten Sprachen, die bestimmen, ob eine kanonische Form bestimmt werden kann und / oder für ein beliebiges Programm in dieser Sprache erstellt. Leider habe ich es nicht gelungen, die Verweise zu finden, die ich (vage) Lesen erinnern darüber in.

Auf der einen Seite scheint es sinnvoll, dass eine kanonische Darstellung einer Sprache zu schaffen ist von vergleichbarer Komplexität zu viele harte Graphenprobleme (zB: Graphisomorphie), aber auf der anderen Seite, iirc, Compiler wie gcc, YHC und ghc Zwischendarstellungen verwenden Ausgänge in verschiedenen Formaten (Montage, JavaScript, etc.) zu erzeugen, so ist dies zumindest in einigen Formen, ein gelöstes Problem.

Wann ist es möglich, eine kanonische Form für eine bestimmte Sprache zu bestimmen / generieren? (Wie ausdruck kann die Sprache sein, und wie Sprache Ausdruck die Nützlichkeit der kanonischen Formen auswirken?) Bitte geben Sie Hinweise oder Beweise, wenn überhaupt möglich.

Edit: Zum Beispiel, ein Reguläre Sprache (zB : die ‚reine‘ Form von regulären ausdrücken) kann viele der gleichen Dinge nicht ausdrücken, dass eine Turing-complete Sprache können. Mit anderen Worten, können Sie nicht einen Web-Server in einer regulären Sprache schreiben, aber man kann mit Lambda-Kalkül). Meine Frage ist, über die theoretischen Möglichkeiten, und hat eine spezifische Antwort auf die Komplexitätstheorie bezieht. Wenn ich einen DSL haben, die auf ein anderes System übertragen werden muss, wird es oft von Vorteil sein, eine kanonische Form dieses Codes zu erzeugen, bevor es zu übertragen, da diese die unabhängigen Darstellungen durch die beiden unterschiedlichen Systemen entkoppeln wird. Jedoch , wenn es P-Raum abgeschlossen ist, oder NP-Complete eine Turing-complete Sprache in eine kanonische Form zu übersetzen, dann sollten Sie nicht eine kanonische Form zu bauen verschwenden Zeit versucht - entweder finden eine andere Art und Weise, es zu tun, oder die Sprache Komplexität zu etwas reduzieren, dass können in Polynomzeit authorisiert werden.

Answer 1

Mit dem "kanonische Darstellung" Ich nehme an, Sie haben folgende Bedeutung: Rufen Sie Programme P und Q Äquivalent , wenn sie "das gleiche tun" auf den gleichen Eingaben. „Doing die gleiche Sache“ bedeutet, dass die Programme die gleiche Leistung haben, und entweder beide Programme halt nach einer endlichen Zeit oder beides geben Sie eine Endlosschleife. Diese Äquivalenzrelation definiert Äquivalenzklassen in der Menge aller Programme. Die „kanonische Darstellung“ ein Programm P ist ein Programm P zu der gleichen Äquivalenzklasse gehört, und Sie verlangen, dass alle Mitglieder der gleichen Äquivalenzklasse haben die gleiche kanonische Darstellung.

Für Turing-complete Sprachen, eine Turing-berechenbare kanonische Darstellung würden Sie ermöglicht das Halting Problem zu lösen wie folgt: zuerst ein Programm schreiben, das aus einer Endlos-Schleife und findet die kanonische Darstellung Q . Dann gilt für jede Eingabeprogramm P , zuerst verwandeln sie mechanisch in ein Programm P ₀ , die das gleiche tut, außer dass es keine Ausgabe erzeugt, und dann die kanonische Darstellung finden P ₀ ‘dieses Programms. Wenn das Ergebnis Q , wissen Sie, dass P ₀ nicht halt, und daher auch nicht P . Andernfalls P ₀ hält, und so auch P .

Für noch mehr Spaß, lesen Sie einige Gregory Chaitins Arbeit auf, was er „elegant "Programme.

Answer 2

Es scheint mir, dass in eine Assemblersprache kompiliert als Übersetzung in eine kanonische Form in einer praktischen Art und Weise kategorisiert werden können.