Was sind die Grenzen der gesamten funktionalen Programmierung?

19

Was sind die Einschränkungen der gesamten funktionalen Programmierung? Es ist nicht vollständig für Turing, unterstützt jedoch eine große Teilmenge der möglichen Programme. Gibt es wichtige Konstrukte, die Sie in einer Turing-vollständigen Sprache schreiben könnten, aber nicht in einer vollständigen funktionalen Sprache?

Und ist es richtig zu sagen, dass Programme, die in total funktionalen Sprachen geschrieben sind, vollständig statisch analysiert werden können, während die statische Analyse in Turing-complete-Sprachen durch Dinge wie das Halteproblem begrenzt ist? Damit meine ich nicht, dass in total funktionalen Sprachen alles statisch bestimmt werden kann, weil manche Dinge nur zur Laufzeit bekannt sind, sondern ich meine, dass theoretisch in einer idealen total funktionalen Programmiersprache geschriebene Programme analysiert werden können, damit alles das könnte theoretisch statisch bestimmt werden kann statisch bestimmt werden. Oder gibt es immer noch unentscheidbare Probleme in funktionalen Gesamtsprachen, die die statische Analyse unvollständig machen? Einige Probleme werden immer unentscheidbar sein, egal in welcher Sprache sie geschrieben sind, aber ich bin an solchen Problemen interessiert, die von der Sprache geerbt werden.

Matthijs Steen
quelle

Antworten:

16

Es kommt auf die gesamte Funktionssprache an .

Diese Antwort klingt wie eine Auskopplung, aber es kann nichts Konkretes gesagt werden. Überlegen Sie sich doch, an welchem ​​wichtigen entscheidbaren Programm Sie interessiert sind. Schreiben Sie ein Programm in Ihrer bevorzugten Turing-complete-Sprache, um es zu lösen. Da das Problem entschieden werden kann, stoppt Ihr Programm bei allen Eingaben.

(Ein nicht entscheidbares Problem könnte interessante Programme haben, die die Leute jedoch nicht verwenden können, da sie nie lange genug warten können, um die Antwort zu erfahren.)

Definieren Sie nun eine neue Sprache so, dass sie nur ein gültiges Eingabeprogramm hat: das Programm, das Sie gerade geschrieben haben, mit derselben Semantik wie zuvor. Es ist auf jeden Fall total, da alle Eingaben für alle darin geschriebenen Programme (von denen es nur eine gibt) immer enden.

Dieser billige Trick ist tatsächlich nützlich: Die Sprache Coq ist zum Beispiel eine voll funktionsfähige Sprache, bei der keine Programmtypprüfung durchgeführt wird, es sei denn, es gibt einen Beweis dafür, dass sie beendet wird. (Wenn Sie auf dieses Erfordernis verzichten, wäre es Turing-complete, sodass das einzige Hindernis darin besteht, einen Kündigungsnachweis zu finden.)

Ich bin mir nicht sicher, was Sie mit "alles, was theoretisch statisch bestimmt werden könnte, kann statisch bestimmt werden" meinen. es klingt tautologisch wahr. Dennoch ist die Analyse von Gesamtsprachen von Natur aus nicht einfach. Sie wissen, dass nichts divergiert, was eine nützliche Tatsache ist, aber das Verhältnis zwischen Input und Output ist immer noch komplex. (Insbesondere gibt es immer noch unendlich viele Eingabemöglichkeiten, sodass Sie auch theoretisch nicht alle ausführlich ausprobieren können.)

Paul Stansifer
quelle
Danke für deine Antwort. Totalität hilft also ein wenig, bleibt aber ein sehr schwieriges Problem. Was ich mit "alles, was theoretisch statisch bestimmt werden kann, kann statisch bestimmt werden" meinte, war, dass es möglich wäre, extrem schwierig oder nicht, alle Beziehungen zwischen Eingabe und Ausgabe zu analysieren, wenn Sie genug Ressourcen dafür hätten . Oder sind die fundamentalen Gründe, warum dies begrenzt ist? Wie Rices Theorm beweist auch Rice, dass dies für Teilfunktionen der Fall ist. Oder verstehe ich den Satz von Rice falsch?
Matthijs Steen
Ich denke, es hängt davon ab, was Sie unter "Beziehung" verstehen. Insbesondere wenn Sie nur "Eingabe A geht auf Ausgabe B" meinen, ist dies in einer gesamten funktionalen Sprache trivial bestimmbar; Führen Sie einfach das Programm aus. Aber Sie interessieren sich wahrscheinlich für Analysen, die etwas über eine unendliche Klasse von Eingaben aussagen.
Paul Stansifer
(hoppla; versehentlich die Eingabetaste drücken) ... aber das eröffnet einen anderen albernen Trick, denn ich kann unentscheidbare Fragen zur Identitätsfunktion stellen, wenn ich möchte: "Für manche Xist (identity X)eine Turing-Maschine ein Stillstand?" Sicher, das scheint nicht zu sein , etwa identity , aber wie „über“ Sie definieren?
Paul Stansifer
Ja, ich möchte wissen, ob es für alle möglichen Eingabewerte einer Definition gilt, nicht für einzelne Eingaben. Wenn ich Sie also richtig verstehe, bedeutet das, dass es immer einige unentscheidbare Fragen geben wird, egal welche Programmiersprache verwendet wird? Obwohl einige dieser unentscheidbaren Fragen möglicherweise umgangen werden, indem verhindert wird, dass das Problem überhaupt auftritt, wie z. B. vollständige Funktionssprachen für das Halteproblem? Denn wäre Ihre Frage nach der Identitätsfunktion in einer funktionalen Gesamtsprache nicht entscheidbar?
Matthijs Steen
Ja; Eine modifizierte Version des Problems, bei der "Turing Machine" durch "Panne nach Ablauf der Garantie Turing Machine" ersetzt wird, ist trivial lösbar. Für diese Zwecke ist es problematisch, dass das Stopp-Problem das beste Beispiel für ein unentscheidbares Problem ist, wenn die Prüfung von Programmen voller Unentscheidbarkeit ist.
Paul Stansifer
16

Was sind die Einschränkungen der gesamten funktionalen Programmierung? Es ist nicht vollständig für Turing, unterstützt jedoch eine große Teilmenge der möglichen Programme. Gibt es wichtige Konstrukte, die Sie in einer Turing-vollständigen Sprache schreiben könnten, aber nicht in einer vollständigen funktionalen Sprache?

LLL

  1. LLLList konsistent. Dies ist genau das, was Goedels Theorem ausschließt, vorausgesetzt, Sie können rechnen. Wir wissen also, dass wir keine Selbstdolmetscher in total funktionalen Sprachen schreiben können.

  2. Die Kehrseite davon ist jedoch, dass die Grenzen der Ausdruckskraft der Gesamtsprachen im Wesentlichen die Grenzen der Ausdruckskraft der Mathematik selbst sind . Zum Beispiel sind die in Coq (einem Proof-Assistenten) definierbaren Funktionen diejenigen, deren Berechenbarkeit mit ZFC nachgewiesen werden kann, mit zählbar vielen unzugänglichen Kardinälen. Im Grunde genommen ist jede Funktion, die Sie zur Zufriedenheit eines arbeitenden Mathematikers als total erweisen könnten, in Coq definierbar.

  3. Die Kehrseite der Kehrseite ist, dass Mathematik schwer ist! Es gibt also keinen einfachen Sinn, in dem Gesamtsprachen "vollständig analysierbar" sind - selbst wenn Sie wissen, dass eine Funktion beendet wird, müssen Sie möglicherweise noch viel kreative Arbeit leisten, um zu beweisen, dass sie eine gewünschte Eigenschaft hat. Wenn Sie zum Beispiel nur wissen, dass eine Funktion von Listen zu Listen total ist, können Sie nicht weit genug gehen, um zu beweisen, dass es sich um eine Sortierfunktion handelt.

Neel Krishnaswami
quelle
Danke für deine Antwort. Ich habe den Beitrag über dieses Problem im Lambda the Ultimate-Weblog gelesen , aber einige Leute in den Kommentaren geben an, dass es zwar nicht möglich ist, einen eigenen Evaluator als regulären, explizit konstruierbaren Begriff zu verwenden, es jedoch möglich wäre, einen funktionierenden Selbstbegriff zu erstellen. Bewerter mit einigen Tricks. Ich frage mich also, ob es Probleme gibt, die mit einigen Umwegtricks nicht in einer funktionalen Gesamtsprache gelöst (oder angenähert) werden können.
Matthijs Steen
Ich würde sagen, dass Selbsteinschätzung kein Problem darstellt, da sie je nach Sprache unterschiedlich ist. Das Problem "Evaluieren eines Programms in Sprache X" ist dasselbe Problem, unabhängig davon, ob Sie versuchen, es in Sprache X oder Y zu lösen. Insbesondere wenn Sprache X eine vollständige Funktionssprache ist, ist das Problem in einer bestimmten vollständigen Funktionssprache lösbar mit dem gleichen albernen Trick, den ich vorher benutzt habe.
Paul Stansifer
Neel, es scheint, als sollte es wesentlich einfacher sein, zu beweisen, dass eine Gesamtsprache ihren eigenen Interpreter nicht unterstützen kann. Verstehe ich dich falsch? Durch eine einfache Diagonalisierung kann jede Sprache mit einer Funktion ohne feste Punkte keinen eigenen Interpreter unterstützen (unabhängig davon, ob sie Arithmetik unterstützt oder nicht). Das Argument wird von Conor McBride hier ausgearbeitet: mail.haskell.org/pipermail/haskell-cafe/2003-May/004343.html
Tom Ellis
@TomEllis: Mein Argument ist im Wesentlichen dasselbe wie das von Conor. Tatsächlich macht sein Posten diese Beobachtung bereits (mit Conors charakteristischem Witz), wenn er sie "das Epimenides / Cantor / Russell / Quine / Godel / Turing-Argument" nennt.
Neel Krishnaswami