Verwenden Programmiersprachen allgemeine rekursive Funktionen als Grundlage?

23

Dies ist eine naive und daher möglicherweise falsch formulierte Frage, also entschuldigen Sie sich im Voraus!

Meiner Ansicht nach kann eine Turing-Maschine als Berechnungsgrundlage für prozedurale / imperative Programmiersprachen angesehen werden. Ebenso ist der Lambda-Kalkül die Grundlage für funktionale Programmiersprachen.

Ich habe kürzlich erfahren, dass die Church-Turing-These auch die wechselseitige Gleichwertigkeit mit einem dritten Rechenmodell zeigt: den allgemeinen rekursiven Funktionen . Gibt es Programmiersprachen, die dies als Berechnungsmodell verwenden? Wenn nicht, gibt es einen technischen Grund dafür; dh neben "noch keiner ausprobiert"?

Xophmeister
quelle
1
Ich würde sagen, dass Turing-Maschinen oder Universalregister-Maschinen eine Basis für Prozessor-PLs (Assembly-PLs) sind. Sie haben keine Funktionen. -rekursive Funktionen sind eine Basis für zwingende PLs. Sie haben keine Funktionen höherer Ordnung. μ
beroal
1
Ich würde auch empfehlen, sich mit Logik erster Ordnung und Prolog zu befassen.
beroal
1
Vor C ++ 11 constexprkonnten (/ mussten) Sie 'Vorlagen' verwenden, um Berechnungen zur Kompilierungszeit vom Compiler durchführen zu lassen. Die Einschränkungen für Vorlagen lassen keine Schleifen zu, Sie können jedoch die Rekursion verwenden, um eine beliebige Schleife zu emulieren, sodass Sie eine Turing- Complete-Funktion (Metaprogrammierung
JimmyB

Antworten:

45

Direkte Antwort auf die Frage: Ja, es gibt es esoterische und höchst unpraktische PLs, die auf rekursiven Funktionen basieren (think Whitespace), aber aus triftigen Gründen basiert keine praktische Programmiersprache auf rekursiven Funktionen.μμμ

Allgemeine rekursive (dh mgr; -rekursive) Funktionen sind signifikant weniger aussagekräftig als Lambda-Kalküle. Somit bilden sie eine schlechte Grundlage für Programmiersprachen. Sie haben auch nicht Recht, dass das TM die Grundlage für zwingende PLs ist: In Wirklichkeit sind gute zwingende Programmiersprachen viel näher an -calculus als an Turing-Maschinen.λμλ

In Bezug auf die Rechenfähigkeit sind -rekursive Funktionen, Turing-Maschine und der untypisierte Kalkül alle gleichwertig. Der untypisierte LC hat jedoch gute Eigenschaften, die keiner der beiden anderen besitzt. Es ist sehr einfach (nur 3 syntaktische Formen und 2 Rechenregeln), sehr kompositorisch und kann Programmierkonstrukte relativ leicht ausdrücken. Ausgestattet mit einem einfachen Typsystem (z. B. System erweitert mit ) kann der -calculus äußerst aussagekräftig sein, da er viele komplexe Programmierkonstrukte einfach, korrekt und kompositorisch ausdrücken kann. Sie können auch das& lgr; F ω f i x & lgr; & lgr;μλFωfixλλ-Kalkül leicht Konstrukte einzuschließen, die keine Lambdas sind. Keines der anderen oben genannten Rechenmodelle bietet Ihnen diese schönen Eigenschaften.

Die Turing-Maschine ist weder kompositorisch noch universell (Sie müssen für jedes Problem ein TM haben). Es gibt keine Konzepte für "Funktionen", "Variablen" oder "Komposition". Es ist auch nicht genau richtig, dass TMs die Grundlage für zwingende PLs sind - FWIW, zwingende PLs sind Lambda-Kalkülen mit Steueroperatoren viel näher als Turing-Maschinen. Eine ausführliche Erklärung finden Sie in Peter J. Landins "Eine Entsprechung zwischen ALGOL 60 und der Lambda-Notation der Kirche" . Wenn Sie in Brainf ** k programmiert haben (was tatsächlich eine ziemlich einfache Turing-Maschine implementiert), werden Sie wissen, dass Turing-Maschinen keine gute Idee für die Programmierung sind.

μ μ Nμ -rekursive Funktionen ähneln in dieser Hinsicht TMs. Sie sind kompositorisch, aber nicht annähernd so kompositorisch wie die LC. Sie können auch keine nützlichen Programmierkonstrukte in -rekursive Funktionen kodieren . Darüber hinaus berechnen die rekursiven Funktionen nur über , und um über alles andere zu berechnen, müssen Sie Ihre Daten mit einer Art Gödel-Nummerierung in natürliche Zahlen codieren, was schmerzhaft ist.μμN

Es ist also kein Zufall, dass die meisten Programmiersprachen irgendwie auf dem Kalkül basieren! Der Kalkül hat gute Eigenschaften: Ausdruckskraft, Komposition und Erweiterbarkeit, die anderen Systemen fehlen. Allerdings sind Turing - Maschinen gut für die Rechenkomplexität zu studieren und rekursive Funktionen sind gut für den logischen Begriff der Berechenbarkeit zu studieren. Sie haben beide hervorragende Eigenschaften, die dem -calculus fehlen, aber auf dem Gebiet der Programmierung gewinnt -calculus eindeutig.λ μ λ λλλμλλ

Tatsächlich gibt es viele, viele weitere Turing-Komplettsysteme, denen jedoch jegliche herausragende Eigenschaft fehlt. Conways Spiel des Lebens, LaTeX-Makros und sogar (einige behaupten) DNA sind vollständig, aber niemand programmiert (dh programmiert ernsthaft) mit Conway oder studiert die Komplexität der Berechnungen mit LaTeX-Makros. Ihnen fehlen einfach gute Eigenschaften. Turing komplett per se ist fast bedeutungslos , wenn es um Programmierung geht.

Außerdem sind viele nicht-Turing-fähige vollständige Rechensysteme sehr nützlich, wenn es um die Programmierung geht. Reguläre Ausdrücke und yacc sind nicht vollständig, aber sie sind äußerst leistungsfähig bei der Lösung einer bestimmten Klasse von Problemen. Coq ist auch nicht vollständig in Turing, aber es ist unglaublich leistungsfähig (es wird tatsächlich als viel ausdrucksvoller angesehen als sein Cousin in Turing, OCaml). Wenn es um die Programmierung geht, ist die Vollständigkeit von Turing nicht der Schlüssel, da viele (fast) nutzlose Systeme uninteressanterweise Turing complete sind. Sie werden nicht behaupten, dass Brainf ** k oder Whitespace mächtigere Programmiersprachen sind als Coq, oder? Eine ausdrucksstarke Grundlage ist der Schlüssel zu leistungsfähigen Programmiersprachen. Deshalb basieren moderne Programmiersprachen fast immer auf demλ-Infinitesimalrechnung.

xuq01
quelle
7
"Niemand programmiert mit Conway" ... einige machen ein funktionierendes Spiel von Tetris in Conways Spiel des Lebens ... auch in der Tat ist es so praktisch wie Leerzeichen :)
Alexei Levenkov
Ein Weg, dies zu sehen, ist, dass eine -calculus-Funktion, die Turing-Maschinen simuliert, wahrscheinlich viel kürzer wäre als eine Turing-Maschine, die den -calculus simuliert (was ich auch nicht gesehen habe). λλλ
Rechtschreibung ohne Kontext
@ AlexeiLevenkov Das ist absolut falsch. Whitespace ist im Wesentlichen eine (einfache) imperative Sprache, wenn auch mit einer merkwürdigen Syntax. Es verfügt über Einrichtungen für Arithmetik, Grundsteuerfluss, Stack und Heap Manipulation und I / O . Das QFT-Projekt erforderte andererseits den Entwurf eines Compilers von einer sehr einfachen Sprache bis hin zu einer RISC-Baugruppe, die für eine CPU erstellt wurde, die in einem mit OTCA-Metapixeln emulierten Wireworld-ähnlichen Zellularautomaten eingebaut ist .
Rechtschreibung ohne Kontext
@AlexeiLevenkov Der ultimative Cogol → CGoL-Compiler erforderte die Arbeit vieler Menschen über vier Jahre, während es ein Projekt namens HaPyLi gibt , das eine weitaus komplexere Sprache für Whitespace kompiliert und von einer Person in ihrer Freizeit geschrieben wurde.
Rechtschreibung ohne Kontext
4

Das Eingeben µ-recursive function programming languagevon Google hat mich zu diesem GitHub-Repo geführt . Die Antwort auf Ihre Frage lautet:

Ja, und es heißt Myopie

Es ist übrigens in Haskell geschrieben.

Kapol
quelle
μ
2
Na sicher. Ich bin einfach davon ausgegangen, dass OP eine solche Sprache finden möchte, um die Theorie oder etwas
anderes