Beim Schreiben eines Interpreters, der sich an externe Programme / Funktionen anhängt (anhängen sollte), ist ein merkwürdiges Problem aufgetreten: Funktionen in 'C' und 'C ++' können keine unterschiedlichen Funktionen anhängen , z. B. kann ich keine Funktion erstellen , die 'printf' aufruft. mit genau den gleichen Argumenten, die es bekam, und muss stattdessen eine alternative Version aufrufen, die ein variadisches Objekt nimmt. Dies ist sehr problematisch, da ich ein Objekt erstellen möchte, das einen anonymen Hook enthält.

Daher fand ich das seltsam, da Forth , JavaScript und möglicherweise eine Vielzahl anderer Sprachen dies sehr leicht tun können, ohne auf Assemblersprache / Maschinencode zurückgreifen zu müssen. Bedeutet das, dass andere Sprachen dies so einfach können, dass die Klasse von Problemen, die jede Programmiersprache lösen kann, tatsächlich von Sprache zu Sprache unterschiedlich ist, obwohl alle diese Sprachen vollständig sind ?

$\mathbb{N}^k \rightarrow \mathbb{N}$

$\lambda$

Die Vollständigkeit der Daten sagt nichts über Typen, eingebaute Arrays / Ganzzahlen / Wörterbücher, Eingabe- / Ausgabefunktionen, Netzwerkzugriff, Multithreading, dynamische Zuweisung, ... aus.

Nur weil Java nicht über Feature X verfügt (z. B. Makros, übergeordnete Typen oder abhängige Typen), hört es nicht plötzlich auf, Turing zu beenden.

Vollständigkeit und Ausdruckskraft der Sprache sind zwei verschiedene Begriffe.

Vollständigkeit ist ein abstrakter Begriff der Berechenbarkeit. Wenn eine Sprache Turing vollständig ist, ist sie in der Lage, alle Berechnungen durchzuführen, die eine andere Sprache von Turing vollständig ausführen kann.

Dies sagt jedoch nicht, wie bequem es ist, dies zu tun. Einige Funktionen, die in einigen Sprachen einfach sind, können in anderen aufgrund der Auswahl des Designs sehr schwierig sein. Turing Vollständigkeit sagt nur , dass Sie kann die Berechnung tun. Als extremes Beispiel mag es schwierig sein, varadische Funktionen in C ++ einzuhängen, aber es ist möglich, einen JavaScript-Interpreter in C ++ zu schreiben, der variadische Funktionen einbinden kann.

Sprachdesign ist eine ziemlich interessante Kunst. Einer der wichtigsten Schritte ist die Ermittlung der Verhaltensweisen, die das Rückgrat Ihrer Sprache bilden sollen. Diese Verhaltensweisen sind Dinge, die in Ihrer Sprache einfach zu tun sind, weil sie im Erdgeschoss eingebaut sind. Wir treffen Entwurfsentscheidungen darüber, welche Funktionen in jeder Sprache enthalten sein sollen.

In Bezug auf Ihr spezielles Beispiel, als C entwickelt wurde, wurde es so konzipiert, dass es sehr nahe an den Assemblersprachen des Tages arbeitet. Variadic-Funktionen haben einfach Argumente mit sehr geringer Typensicherheit auf den Stapel geschoben. Die Implementierung dieser variablen Funktionen wurde dem Compiler überlassen, um maximale Portabilität zu gewährleisten. Dementsprechend wurden nur sehr wenige Annahmen über die Leistungsfähigkeit der Hardware getroffen. Als JavaScript auf den Markt kam, hatte sich die Szene geändert. Es wird bereits in einer virtuellen Maschine als interpretierte Sprache ausgeführt, sodass sich das Gleichgewicht in Richtung Bequemlichkeit verlagert. Das Zulassen des Einhängens verschiedener Funktionen wird sinnvoll. Selbst im Fall von JavaScript, das Just In Time Compiled ist, sind unsere Compiler bereit, weitaus mehr zusätzliche Informationen über die Argumente zu speichern, als die C-Compiler von früher zu speichern bereit waren.

Stellen Sie sich Programmiersprachen als verschiedene Landfahrzeuge vor: Fahrräder, Autos, Hovercars, Züge.

Turing Completeness sagt: "Dieses Fahrzeug kann überall hingehen, wo jedes andere Fahrzeug hingehen kann." Das heißt, Sie können dieselben Funktionen berechnen. Eingabe zu Ausgabe, Start zu Ende.

Diese Aussage sagt jedoch nichts darüber aus, wie Sie dorthin gelangen. Es könnte auf Schienen sein, es könnte auf Straßen sein, es könnte in der Luft sein. Ebenso sagt Turing Completeness nichts darüber aus, wie Sie eine Funktion berechnen. Sie können Rekursion oder Iteration oder einige seltsame zellulare Automaten verwenden. Sie können Typen verwenden oder nicht, Sie können dynamische oder statische Techniken verwenden. Wenn Sie jedoch nur Funktionen (oder Mengen / formale Sprachen) in Betracht ziehen, können Sie diese Funktionen berechnen, solange Sie Turing Complete ausführen.

Was Sie im Wesentlichen fragen, ist der Unterschied zwischen der Rechenkraft und der Ausdruckskraft (oder einfach Ausdruckskraft ) einer Sprache (oder eines Rechensystems).

Rechenleistung

Die Rechenleistung bezieht sich darauf, welche Arten von Problemen die Sprache berechnen kann. Die bekannteste Klasse von Rechenleistung ist diejenige, die einer Universal-Turing-Maschine entspricht . Es gibt viele andere Rechensysteme, wie z. B. Random Access Machines , λ-Kalkül , SK-Kombinator-Kalkül , µ-rekursive Funktionen , WHILEProgramme und viele andere. Und wie sich herausstellt, können sich alle gegenseitig simulieren, was bedeutet, dass sie alle die gleiche Rechenleistung haben.

Daraus entsteht die Church-Turing-These (benannt nach Alonzo Church , der die λ-Rechnung erstellt hat, und Alan Turing , der die Universal Turing Machine erstellt hat). Die Church-Turing-These ist eine Hypothese zur Berechenbarkeit mit zwei Aspekten:

1. alle allgemein berechenbaren Rechnersysteme sind gleich leistungsfähig und
2. Ein Mensch, der einem Algorithmus folgt, kann genau die Funktionen berechnen, die eine Turing-Maschine (und damit eines der anderen Systeme) berechnen kann.

Die zweite ist jedoch im Bereich der Philosophie des Geistes wichtiger als die Informatik.

Es gibt jedoch zwei Dinge, die die Church-Turing-These nicht sagt und die für Ihre Frage sehr relevant sind:

1. wie effizient die verschiedenen Simulationen sind und
2. wie bequem die Kodierung eines Problems ist.

Ein einfaches Beispiel für (1): Auf einem Computer mit wahlfreiem Zugriff dauert das Kopieren eines Arrays proportional zur Länge des Arrays. Bei einer Turing-Maschine dauert die Zeit jedoch proportional zum Quadrat der Länge des Arrays, da die Turing-Maschine keinen wahlfreien Speicherzugriff hat und sich nur zellenweise über das Band bewegen kann. Daher muss es sich n- mal über die n Elemente des Arrays bewegen, um sie zu kopieren. Daher können verschiedene Berechnungsmodelle auch im asymptotischen Fall, in dem versucht wird, von Implementierungsdetails abzuweichen, unterschiedliche Leistungsmerkmale aufweisen.

Beispiele für (2) gibt es zuhauf: Sowohl λ-Kalkül als auch Python sind Turing-vollständig. Aber möchten Sie lieber ein Programm in Python oder in λ-Kalkül schreiben?

Es gibt auch eine dritte Falte, die ich bis jetzt umgangen habe: Alle diese ursprünglichen Systeme wurden von Logikern, Philosophen oder Mathematikern entworfen, nicht von Informatikern… einfach, weil Computer und damit Informatik nicht existierten. Diese alle gehen zurück zu den frühen 1930er Jahren, noch vor Konrad Zuse ist sehr erste Experimente (die nicht programmierbar und / oder Turing-complete ohnehin waren). Sie sprechen nur von "berechenbaren Funktionen auf den natürlichen Zahlen".

Nun, wie sich herausstellt, gibt es eine Menge, die Sie als Funktionen auf natürlichen Zahlen ausdrücken können - schließlich kommen unsere modernen Computer sogar mit viel weniger aus (im Grunde 3-4 Funktionen auf den Zahlen 0 und 1, und das war's ), aber welche Funktion berechnet beispielsweise ein Betriebssystem?

Diese Vorstellung von I / O-Nebenwirkungen, die mit der Umgebung interagieren, wird von der Idee der "Funktionen über natürlichen Zahlen" nicht erfasst. Und doch ist es irgendwie wichtig, da, wie Simon Peyton Jones einmal legt es „All eine reine Funktion ohne Nebenwirkungen, ist Ihre CPU heiß machen“ , zu dem ein Zuschauer antwortete „tatsächlich, das ist eine Seite -Effekt auch! "

Edwin Brady , der Designer von Idris , verwendet scherzhaft (ich weiß nicht, ob er es erfunden hat) den Ausdruck "Tetris-vollständig", um diesen Unterschied zwischen "kann jede berechenbare Funktion auf natürlichen Zahlen berechnen" und "kann" auszudrücken verwendet werden, um nicht triviale Programme zu schreiben, die mit der Umgebung interagieren ". Ironischerweise demonstriert er dies durch die Implementierung eines Space Invaders-Klons in Idris , ist jedoch zuversichtlich, dass Tetris sich zu Space Invaders reduziert.

Eine andere Sache, die hervorgehoben werden muss, ist, dass nicht nur die Turing-Äquivalenz nicht unbedingt ausreicht, um über das tatsächliche Schreiben von "nützlichen" Programmen zu sprechen, sondern dass OTOH möglicherweise auch nicht einmal notwendig ist . Zum Beispiel ist SQL erst mit ANSI SQL: 1999 Turing-äquivalent geworden , aber vorher war es noch nützlich. In der Tat könnten einige argumentieren, dass die Herstellung eines Turing-Äquivalents überhaupt nicht zu seiner Nützlichkeit beigetragen hat. Es gibt viele domänenspezifische Sprachen, die nicht Turing-äquivalent sind. Datenbeschreibungssprache ist normalerweise nicht (und sollte es auch nicht sein). Total Languages ​​kann natürlich nicht Turing-äquivalent sein, Sie können jedoch Ereignisschleifen, Webserver oder Betriebssysteme darin schreiben. Es gibt auch Sprachen, die Turing-äquivalent sind, bei denen dies jedoch als Fehler angesehen wird.

Alles in allem ist die Turing-Äquivalenz also nicht besonders interessant, es sei denn, Sie möchten Programme statisch analysieren.

Ausdruckskraft

Unter der Annahme, dass unser Rechensystem leistungsfähig genug ist, um unser Problem überhaupt zu lösen, müssen wir als Nächstes unseren Algorithmus zum Lösen dieses Problems in einer Art formaler Notation für dieses System ausdrücken. Mit anderen Worten: Wir müssen ein Programm in einer Computersprache schreiben. Hier kommt der Begriff der Ausdruckskraft ins Spiel.

Es bezieht sich im Wesentlichen darauf, wie "einfach" oder "angenehm" es ist, unser Programm in unserer speziellen Programmiersprache zu schreiben. Wie Sie sehen können, ist der Begriff ziemlich vage, subjektiv und eher psychologisch als technisch.

Es gibt jedoch Versuche, die Definitionen zu präzisieren. Der bekannteste (und strengste, den ich kenne) stammt von Matthias Felleisen in seinem Aufsatz Über die Ausdruckskraft von Programmiersprachen (die ersten beiden Seiten enthalten eine sanfte Einführung, der Rest des Aufsatzes ist fleischiger).

Die Hauptintuition ist folgende: Wenn Sie ein Programm von einer Sprache in eine andere Sprache übersetzen, sind einige der Änderungen, die Sie vornehmen müssen, lokal enthalten (wie z. B. FORSchleifen in WHILESchleifen oder Schleifen in bedingte GOTOs umwandeln), und einige erfordern eine Änderung der globalen Struktur des Programms.

Wenn Sie ein Merkmal einer Sprache nur durch lokale Transformationen durch ein anderes Merkmal einer anderen Sprache ersetzen können, haben diese Merkmale keine Auswirkung auf die Ausdruckskraft. Dies nennt man syntaktischen Zucker .

Wenn es andererseits erforderlich ist, die globale Struktur des Programms zu ändern, kann die Sprache, in die Sie übersetzen, die Funktion nicht ausdrücken. Die Sprache, aus der Sie übersetzen, soll aussagekräftiger sein (in Bezug auf diese Funktion).

Beachten Sie, dass dies eine objektiv messbare Definition der Ausdruckskraft gibt. Beachten Sie auch, dass der Begriff kontextabhängig und vergleichend ist. Also, wenn jedes Programm in der Sprache A kann Sprache übersetzt wird B mit nur lokalen Veränderungen, und es gibt mindestens ein Programm in Sprache B , das kann nicht übersetzt wird A mit nur lokalen Änderungen, dann Sprache B ist streng ausdrucksvoller als Sprache EIN. Das wahrscheinlichere Szenario ist jedoch, dass viele Programme in beiden Sprachen hin und her übersetzt werden können, aber es gibt einige Programme in beiden Sprachen, die nicht in die andere übersetzt werden können. Dies bedeutet, dass keine Sprache strikt aussagekräftiger ist als die andere. Sie verfügen lediglich über unterschiedliche Funktionen, mit denen unterschiedliche Programme auf unterschiedliche Weise ausgedrückt werden können.

Dies gibt eine formale Definition dessen, was es bedeutet, "ausdrucksvoller" zu sein, erfasst aber immer noch nicht die psychologischen Vorstellungen, die hinter dem Phänomen stehen. Beispielsweise erhöht syntaktischer Zucker nach diesem Modell nicht die Ausdruckskraft einer Sprache, da er nur durch lokale Änderungen übersetzt werden kann. Aber wir wissen aus Erfahrung , dass mit FOR, WHILEund zur IFVerfügung, auch wenn sie nur syntaktischer Zucker für die bedingten sind GOTOMarken zum Ausdruck unserer Absicht leichter .

Tatsache ist, dass verschiedene Sprachen unterschiedliche Merkmale haben, die es leichter oder schwerer machen, unterschiedliche Denkweisen über ein Problem auszudrücken. Und manche Menschen finden vielleicht eine Möglichkeit, ihre Absicht leichter auszudrücken, und andere eine andere.

Ein Beispiel, das ich im Ruby-Tag auf StackOverflow gefunden habe: Viele Benutzer, die dem Ruby-Tag folgen, behaupten, dass Schleifen einfacher zu verstehen sind als Rekursion und Rekursion nur für fortgeschrittene funktionale Programmierer und Schleifen für Neueinsteiger intuitiver komplette Neulinge, die intuitiv Code wie folgt schreiben:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Was normalerweise dazu führt, dass mehrere Leute kommentieren, dass "das nicht funktioniert" und "sie es falsch machen" und der "richtige Weg" ist:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Offensichtlich gibt es einige Leute, für die die Schwanzrekursion eine natürlichere Art ist, das Konzept des "Schleifens" auszudrücken als Schleifenkonstrukte.

Zusammenfassung

Die Tatsache, dass zwei Sprachen Turing-äquivalent sind, sagt eins und genau eines aus: Sie können die gleichen Funktionen für natürliche Zahlen berechnen wie eine Turing-Maschine. Das ist es.

Es sagt nichts darüber aus, wie schnell sie diese Funktionen berechnen. Es sagt nichts darüber aus, wie einfach es ist, diese Funktionen auszudrücken. Und es sagt nichts darüber aus, was sie außer der Berechnung von Funktionen für natürliche Zahlen noch tun können (z. B. Verknüpfung mit C-Bibliotheken, Lesen von Benutzereingaben, Schreiben von Ausgaben auf den Bildschirm).

Bedeutet das, dass die Klasse von Problemen, die jede Programmiersprache tatsächlich lösen kann, von Sprache zu Sprache unterschiedlich ist, obwohl diese Sprachen alle vollständig sind?

Ja.

1. Es gibt Probleme, die nicht unter den Begriff "Turing-complete" fallen (der sich nur mit Rechenfunktionen für natürliche Zahlen befasst), beispielsweise das Drucken auf dem Bildschirm. Zwei Sprachen können Turing-vollständig sein, aber eine kann das Drucken auf dem Bildschirm ermöglichen und die andere nicht.
2. Selbst wenn beide Sprachen die gleichen Probleme lösen können, sagt das nichts darüber aus, wie komplex die Codierung ist und wie einfach es ist, diese Codierung auszudrücken. ZB kann C jedes Problem lösen, das Haskell kann, indem Sie einfach einen Haskell-Interpreter in C schreiben. Sie müssen jedoch zuerst den Haskell-Interpreter schreiben, um ein Problem auf diese Weise zu lösen!

Alle Programmiersprachen von Turing complete können die gleichen Algorithmen implementieren. Wenn Sie also feststellen, dass es sehr schwierig ist, einen Algorithmus in einer bestimmten Sprache zu implementieren, bedeutet dies nicht, dass dies unmöglich ist.

Denken Sie daran, dass eine Sprache aus Syntax und Semantik besteht. Manchmal ist die Menge der Wörter, die zu einer Sprache gehören, kein Minimum, um als vollständig angesehen zu werden. Es gibt Funktionen , die die Dinge einfacher machen (deshalb werden sie Funktionen genannt ). Wenn Sie diese Funktionen herausnehmen, ist die Sprache immer noch vollständig.

Einige davon könnten von Interesse sein:

• Source-to-Source-Compiler auf Wikipedia

• Über die Wichtigkeit der Vollständigkeit von Turing bei Lambda the Ultimate

Alle Turing-complete-Sprachen können die gleichen Dinge berechnen.

Wenn Sie versuchen, eine moderne Sprache zu implementieren, werden Sie feststellen, dass die meisten Funktionen keine Rechenfunktionen hinzufügen . Viele dieser Funktionen können auf einfachere Funktionen reduziert werden, die bereits in derselben Sprache vorhanden sind.

Hier sind einige Beispiele:

• Wenn Sie keine Aufzählungen haben, können Sie ganze Zahlen verwenden.
• Wenn Sie keine Puffer haben, deren Größe bekannt ist, können Sie einen Typ erstellen, der eine Größe und einen Puffer enthält, dessen Größe nicht bekannt ist.
• Wenn Sie keine Überprüfung der Puffergrenzen haben, können Sie den Index einfach jedes Mal überprüfen, wenn Sie sie verwenden.
• Wenn Sie keine variablen Funktionen haben, können Sie eine Funktion erstellen, die einen Puffer verwendet, dessen Größe bekannt ist, und aus diesem Puffer dieselben Informationen lesen, die Sie aus formalen Argumenten erhalten würden.
• Wenn Sie keine Operatoren haben, können Sie Funktionen verwenden.
• Wenn Sie keine Typen haben, die sich gegenseitig erben können, können Sie Typen erstellen, die sich gegenseitig enthalten, und über eine zusätzliche Indirektionsebene auf sie zugreifen, wobei die Untertypisierung einfach eine Umwandlung des Handles in den gesamten Typ in einen ist Handle-to-the-Contained-Typ.
• Wenn Sie keine Delegaten, aber Funktionszeiger haben, können Sie einen Typ erstellen, der das Referenzobjekt und einen Funktionszeiger enthält.
• Wenn Sie keine Delegaten, aber Schnittstellen haben, können Sie eine Schnittstelle deklarieren, die eine einzelne Methode mit der gewünschten Signatur enthält.
• Wenn Sie keine generischen Typen haben, können Sie nicht generische Typen verwenden, die nur die Ober- oder Untergrenzen annehmen, an denen Sie interessiert sind (und möglicherweise entsprechende Casts an den Verwendungspunkten durchführen, um den Compiler bei Laune zu halten).
• Wenn Sie kein lineares / affines Typsystem haben, können Sie einfach vermeiden, eine Variable mehr als einmal zu verwenden.
• ...und so weiter.

Das Mainstream-Sprachdesign konzentriert sich auf Funktionen, die es uns einfacher und bequemer machen, schneller zu rechnen, unsere Fehler früher zu erkennen, unbekannte Komponenten zu programmieren, die Parallelität sicherer zu machen und so weiter.

Das rein rechnerische Zeug wurde vor langer Zeit festgenagelt.

Die vorhandenen Antworten weisen zu Recht darauf hin, dass die Vollständigkeit von Turing kein guter Weg ist, um Sprachen zu vergleichen. Tatsächlich sind fast alle Sprachen vollständig. ("Wenn jeder etwas Besonderes ist, dann ist niemand etwas Besonderes", wie die Unglaublichen sagten.)

Es ist jedoch möglich, die Ausdruckskraft von Sprachen mit mathematischer Präzision zu vergleichen. Schauen Sie sich Felleisens Über die Ausdruckskraft von Programmiersprachen an . Die Idee ist ungefähr, die folgende Frage zu stellen: Kann ich jedes Programm in Sprache A in ein Programm in Sprache B konvertieren, indem ich nur lokale Änderungen vornehme? Mit anderen Worten, Felleisen gibt Ihrer Intuition eine mathematisch präzise Form.

Neben den Antworten aller anderen ist hier eine weitere Analogie.

Um Kleidung zu waschen, braucht man drei Dinge: ein Reservoir, das Wasser enthält, ein Reinigungsmittel und einen Rührmechanismus. Dies könnte auf viele Arten realisiert werden. Das Wasserreservoir ist alles, was genügend Wasser enthält (z. B. eine Wanne, ein See, ein Fluss). Der Bewegungsmechanismus kann eine mechanische Vorrichtung, ein Waschbrett oder sogar ein Stein sein, gegen den die Kleidung geschlagen wird. Und Waschmittel gibt es auch in verschiedenen Formen.

Was ist der Unterschied zwischen einer modernen Computer-Waschmaschine und einem Felsen neben einem Fluss?

Es läuft auf drei Dinge hinaus: Effizienz, Sicherheit und Komfort. Einige Waschmethoden verbrauchen weniger Energie, belasten die Umwelt weniger, verbrauchen weniger Wasser und so weiter. Einige Waschmethoden erfordern weniger wiederholte manuelle Tätigkeiten (die zu Verletzungen führen) oder sind bei schlechtem Wetter draußen. Für einige Waschmethoden ist kein Mensch erforderlich, um den Prozess zu überwachen.

Turing-complete-Programmiersprachen sind universell einsetzbar und werden daher für mehr als eine Aufgabe eingesetzt. Dennoch sind einige Programmiersprachen für eine bestimmte Aufgabe effizienter, bequemer und sicherer (in dem Sinne, dass weniger schief gehen kann, wenn das Programm tatsächlich verwendet wird) als andere.

Andere haben viele gute Antworten geliefert, erwähnen aber nicht ausdrücklich einen Vorbehalt, der mich einmal sehr verwirrt hat: Vollständigkeit bedeutet nicht, dass eine Sprache beliebige berechenbare Funktionen von ihren Eingaben bis zu ihren Ausgaben ausdrücken kann. Es ist schwächer: es muss einige Weise die Domäne darstellt , und den Bereich des Satzes von berechenbaren Funktionen als Ein- und Ausgänge , so daß jede dieser Funktionen abbildet auf ein Programm , das eine Darstellung der Eingänge an die entsprechenden Ausgänge erfolgt.

Nehmen wir zum Beispiel eine Sprache, die Turing-Maschinen ausdrückt. Jedes Programm in der Sprache ist eine Turingmaschine.

Betrachten Sie nun die Subsprache aller Turing-Maschinen, die nur die Zeichen a, b und blank lesen und schreiben. Es ist Turing complete, kann aber keine Programme ausdrücken, die zum Beispiel c für alle Eingaben erzeugen, da es kein cs schreiben kann. Es kann nur alle berechenbaren Funktionen an Ein- und Ausgängen ausdrücken, die als Zeichenfolgen von as und bs codiert sind.

Es ist also nicht wahr, dass alle Turing-vollständigen Sprachen die gleichen Dinge berechnen können, auch wenn wir diese Dinge auf die berechenbaren Funktionen von ihren potentiellen Eingaben bis zu ihren potentiellen Ausgaben beschränken. Für die Sprache müssen möglicherweise Ein- und Ausgänge auf bestimmte Weise codiert werden.