Gibt es heute gängige allgemeine Nicht-Turing-Allzwecksprachen?

11

Nicht-Turing-vollständige Sprachen bieten einen großen Vorteil gegenüber Turing-vollständigen Sprachen, da sie viel besser analysierbar sind und daher viel breitere Optimierungsmöglichkeiten bieten. Sie werden jedoch kaum verwendet und die Turing-Vollständigkeit wird tatsächlich als gutes Feature verkauft.

Gibt es heute gängige nicht-Turing-vollständige Sprachen, die für die allgemeine Programmierung entwickelt wurden?

MaiaVictor
quelle
8
Ich denke, die beiden Dinge, nach denen Sie suchen, sind nicht miteinander vereinbar. Wenn es nicht vollständig ist, kann es nicht für eine beliebige Verwendung verwendet werden.
Bobson
@Dokkat Ich habe die Frage erneut geöffnet und die Meta-Diskussion aus den Kommentaren entfernt. Bitte beachten Sie, dass Sie, wenn Sie mit einer der Richtlinien der Website nicht einverstanden sind, eine Meta-Diskussion veröffentlichen können. nicht nur ignorieren. Bei subjektiven Fragen liegt der Schlüssel zum Erfolg in der vorherigen Forschung und strengen Definition. Je mehr Sie recherchieren, desto spezifischer (und beantwortbarer) wird Ihre Frage und desto weiter entfernen Sie sich vom berüchtigten "nicht konstruktiven" Raum.
Yannis
Warum halten Sie "breitere Optimierungsmöglichkeiten" für einen "großen Vorteil"? Das heißt nicht, dass sich eine Optimierung nicht lohnt, aber ich würde die inhärente Optimierbarkeit einer Sprache angesichts der Leistungsfähigkeit moderner Computer sicherlich nicht als "großen Vorteil" bezeichnen.
Bobson
2
Coq kann in seiner Domäne als ziemlich "Mainstream" angesehen werden, wobei Konkurrenten (HOL, Agda, ACL und dergleichen) viel weniger sichtbar sind.
SK-Logik
Vielleicht verstehe ich nicht wirklich, was Turing-Vollständigkeit ist, aber wie kann eine Sprache universell und nicht-Turing vollständig sein? Ich dachte, die Bedeutung von Nicht-Turing-Vollständigkeit besteht darin, keine Rechenaufgabe ausführen zu können und somit auf einen bestimmten Zweck ausgerichtet zu sein.
Aviv Cohn

Antworten:

24

Es gibt heute keine gängigen Mehrzweck-Nicht-Turing-Vollsprachen. Es gibt jedoch mehrere nicht Turing-vollständige domänenspezifische Sprachen. ANSI SQL, reguläre Ausdrücke, Datensprachen (HTML, CSS, JSON usw.) und S-Ausdrücke sind einige bemerkenswerte Beispiele.

Es gibt keinen wirklichen Vorteil für Mehrzweck-Nicht-Turing-Vollsprachen. Der "viel besser analysierbare" Aspekt, von dem ich annehme, dass er eine Anspielung auf den Satz von Rice ist, trifft zu, ist jedoch für Sprachen, die auf mehrere verschiedene Anwendungsbereiche abzielen, nicht sehr sinnvoll. Andere Anforderungen haben Vorrang. Die Flexibilität der Vollständigkeit von Turing ist viel wichtiger als ihre Komplexität. Bei Programmiersprachen geht es wie bei jeder anderen Software um Kompromisse.

Bei domänenspezifischen Sprachen ist dies möglicherweise umgekehrt. Wenn Sie nicht "eine Sprache erstellen, um alle zu beherrschen", können Sie nur die Funktionen implementieren, die für den spezifischen Zweck Ihrer Sprache sinnvoll sind. Und meistens gehört die Vollständigkeit von Turing nicht dazu.

Yannis
quelle
CSS3 ist Turing-vollständig.
SK-Logik
5
@ SK-Logik CSS ist ohne HTML sinnvoll, kann auf jede Art von XML angewendet werden und nichts hindert Sie daran, es für ein anderes Format mit ungefähr kompatibler Form (Bäume mit benannten Knoten, Geschwisterreihenfolge usw.) zu implementieren. Ich habe persönlich CSS-Regeln für eine SVG-Datei geschrieben. Es ist nur viel häufiger für HTML, weil HTML weitaus häufiger ist als die anderen Formate.
2
@ Mike, das ist eine kaputte Analogie. Die CSS3-Semantik ist eng mit der Semantik der Präsentationssprache verbunden.
SK-Logik
2
Beachten Sie, dass SQL mit Windowing und CTEs (dh SQL: 2003) ebenfalls Turing-vollständig ist.
Jörg W Mittag
1
"Es gibt heute keine gängigen Mehrzweck-Nicht-Turing-Vollsprachen." - C ohne externen Speicher ist nicht Turing-vollständig, aber es ist sehr universell und Mainstream. (Nun, ich persönlich würde argumentieren, dass es eine domänenspezifische Sprache zum Schreiben von Unix-Kerneln ist und nicht einmal besonders gut darin ist, aber die Welt ist anderer Meinung.)
Jörg W Mittag
-3

Der Grund, warum unvollständige Sprachen nicht zum Mainstream gehören, ist, dass es einfach ist, eigene Sprachen zu implementieren, wann immer Sie sie benötigen und wie auch immer Sie sie benötigen. Ein interessantes Beispiel ist das Bitcoin-Skript: https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp

Adam Kurkiewicz
quelle
5
"Ja wirklich?" Möchten Sie Coq von Grund auf selbst implementieren, wenn es so einfach ist?
SK-Logik
Ist das nur deine Meinung oder kannst du es irgendwie unterstützen?
Mücke
Beispiele sind alle domänenspezifischen Sprachen, die keine Rekursion, unbegrenzte Iteration oder andere Turing-Tarpits benötigen. Ich bin mir auch sicher, dass die meisten von uns einfache Taschenrechner implementiert haben, die grundlegende Arithmetik verarbeiten.
MauganRa
1
Ich stimme jedoch zu, dass es nicht trivial ist, die Sprache Turing-unvollständig zu halten. Selbst ohne offensichtliche Turing-Tarpits könnte es immer einen Compiler-Fehler enthalten, der es ermöglicht, eine der zugrunde liegenden Plattformen zu verwenden.
MauganRa