Ist es tatsächlich möglich, eine "nützliche" Programmiersprache zu haben, die nicht vollständig ist?

37

Wo es akzeptiert wird, dass eine Sprache vollständig sein muss, um etwas Gutes zu sein, ist es tatsächlich möglich, eine 'nützliche' Programmiersprache zu haben, die nicht vollständig ist?

Ich sollte klarstellen, dass es sich hier ganz speziell um Programmiersprachen im herkömmlichen Sinne handelt und nicht um Auszeichnungs- oder Abfragesprachen.

PhonicUK
quelle
3
@PhonicUK SQL war am Anfang nicht vollständig
Ryathal
4
@Ryathal SQL ist keine Programmiersprache, sondern eine Abfragesprache.
Yannis
2
@PhonicUK Ihre Frage im Kommentar lohnt sich tatsächlich, ändern Sie die gepostete Frage in die, oder es wird als nicht konstruktiv geschlossen. Es gibt tatsächlich nützliche, aber nicht vollständige Sprachen, und ich wäre interessiert, Einzelheiten darüber zu erfahren.
Jimmy Hoffa
5
Regex ist noch nicht vollständig, aber es ist weit verbreitet
Ratschenfreak
3
@DavidHammen Die tatsächlichen Implementierungen sind begrenzt, ja, aufgrund der Grenzen unseres physikalischen Universums (kann nur endlichen Speicher aufbauen, kann die Maschine nur für eine begrenzte Zeit laufen lassen, bevor es zu Fehlfunktionen kommt). Das heißt aber nicht, dass die Sprachen begrenzt sind. Die Spezifikation einer vollständigen Sprache erfordert keine Implementierung, um einem Programm solche Grenzen aufzuerlegen, wohingegen eine Sprache, die keine TC-Sprache ist, zum Beispiel einen Kündigungsnachweis erfordert.

Antworten:

48

Coq , Agda , HOL und ACL2 sind sehr nützliche und äußerst leistungsfähige Sprachen, obwohl sie nicht vollständig sind.

Ein gemeinsames Merkmal, das sie unvollständig macht, ist die Tatsache, dass es immer möglich ist, eine Kündigung nachzuweisen. Eine sehr einfache Einschränkung reicht aus: Rekursive Aufrufe sind nur zu nachweislich strukturell kleineren Konditionen erlaubt. Obwohl es nicht möglich ist, einen Interpreter für eine Turing-vollständige Sprache oder sogar für die Sprache selbst zu implementieren, sind dennoch viele andere nützliche Dinge möglich, wie beispielsweise ein zertifizierter C-Compiler .

SK-Logik
quelle
2
Könnten Sie denjenigen, die mit diesen Sprachen nicht vertraut sind, etwas näher erläutern, was sie vermissen, wodurch sie nicht vollständig werden, und einige Beispiele für Dinge, die mit diesen Sprachen erstellt wurden?
PhonicUK
8
@PhonicUK: Ein C-Compiler ist keine C-Implementierung . Es ist ein Tool, das Code in einer Sprache (C) in einen anderen (normalerweise Maschinencode) umwandelt. Dies bedeutet nicht , dass der C-Compiler selbst einem zufälligen C-Programm entspricht.
Joachim Sauer
9
@PhonicUK, Sie können keinen Interpreter für eine Turing-vollständige Sprache in einer nicht Turing-vollständigen Sprache implementieren. Sie können aber natürlich einen Compiler implementieren (da eine Turing-vollständige CPU eine tatsächliche Auswertung durchführt).
SK-logic
11
@ SK-Logik: "Natürlich?" Es ist nur für C möglich, weil das eine ziemlich einfache Sprache ist. Für C ++ ist dies nicht möglich, da ein Compiler Vorlagencode interpretieren muss (der zur Kompilierungszeit Turing-complete ist).
MSalters
11
@MSalters Ja, wenn die Kompilierung der Sprache vollständig ist, muss ein Compiler dafür in einer vollständigen Sprache geschrieben sein. Das ist auch ein bisschen offensichtlich (nicht tautologisch zu sagen). Beachten Sie jedoch, dass der C ++ - Standard Einschränkungen für die Eingabeprogramme zulässt, z. B. eine maximale Auswertetiefe für Vorlageninstanziierungen (und vorhandene Implementierungen erlauben dies). Wenn ich mich nicht irre, kann dies bedeuten, dass ein nicht wirklich vollständiger C ++ - Compiler möglich ist (außer natürlich bei Problemen, die nichts damit zu tun haben).
12

Ich würde denken, Yegges Begriff "Mini-Sprache" bezieht sich auf die Tatsache, dass es oft nützlich ist, eine Sprache für bestimmte Probleme zu verwenden, bei denen die Sprache keine Vollständigkeit erfordert, um die Aufgabe zu erfüllen -für vollständige Sprachen kann nützlich sein. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia antwortet sehr gut, genau in Übereinstimmung mit dem, was ich gesagt habe. Zuerst dachte ich an reine Mathematik, dann erinnerte ich mich an reguläre Ausdrücke, und Wikipedia listet Epigramm auf, von dem ich glaube, dass es in der "reinen Mathematik" -Vene liegt.

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Nicht Turing-vollständige Sprachen

Es gibt viele Computersprachen, die nicht vollständig sind. Ein solches Beispiel ist die Menge der regulären Sprachen, am häufigsten reguläre Ausdrücke, die von endlichen Automaten generiert werden. Eine leistungsstärkere, aber immer noch nicht Turing-vollständige Erweiterung endlicher Automaten ist die Kategorie der Pushdown-Automaten und der kontextfreien Grammatiken, die üblicherweise zum Generieren von Analysebäumen in einer ersten Phase der Programmkompilierung verwendet werden. Weitere Beispiele sind einige der frühen Versionen der in Direct3D- und OpenGL-Erweiterungen eingebetteten Pixel-Shader-Sprachen oder eine Reihe mathematischer Formeln in einer Tabelle ohne Zyklen. In funktionalen Programmiersprachen sind alle Funktionen vollständig und müssen kündigen, wie Charity und Epigram. Charity verwendet ein Typensystem und Kontrollkonstrukte basierend auf Kategorietheorie.

Datensprachen

Der Begriff der Turing-Vollständigkeit gilt nicht für Sprachen wie XML, JSON, YAML und S-Ausdrücke, da sie normalerweise zur Darstellung strukturierter Daten verwendet werden und nicht zur Beschreibung von Berechnungen. Diese werden manchmal als Auszeichnungssprachen oder besser als "Datenbeschreibungssprachen" bezeichnet.

Es wird auch erwähnt, dass Datenstrukturrepräsentationen keine Sprachen sind, aber ich denke, XSLT sollte als Repräsentation der Berechnung gelten. XPath basiert möglicherweise nicht auf dem, was Yannis oben über SQL als Abfragesprache und nicht als Berechnungssprache sagte. Möglicherweise zählen T-SQL oder PL / SQL als Berechnungssprachen, da Sie viele Berechnungen mit ihren Aggregaten durchführen können, bei denen die verallgemeinerte Form von SQL möglicherweise keine Aggregate angibt.

Jimmy Hoffa
quelle
8

Ich verstehe, dass SQL bei Geschäftstypen sehr beliebt ist

Martin Beckett
quelle
3
SQL ist eine Abfragesprache, keine Programmiersprache.
PhonicUK
4
@PhonicUK: und was genau ist der Unterschied zwischen einer Abfragesprache und einer Programmiersprache?
Joachim Sauer
8
@PhonicUK - Tex ist eine Textauszeichnungssprache und es ist Turing komplett
Martin Beckett
3
Soweit ich weiß, sind die modernen SQL-Implementierungen vollständig.
Shabunc
6
@shabunc IIRC nur mit gespeicherten Prozeduren. Das Argument wird ein bisschen rund, wenn es nicht vollständig ist, dann ist es keine Programmiersprache - daher sind alle "Programmiersprachen" TC
Martin Beckett
5

Die Vollständigkeit ist erforderlich, damit eine Sprache für den allgemeinen Gebrauch geeignet ist. Aber es ist nicht ausreichend , dh nur weil es vollständig ist, ist es nicht für jede Problemdomäne geeignet:

  • Whitespace hat sich als vollständig erwiesen, eignet sich jedoch offensichtlich nicht für Problembereiche außerhalb der Programmiererunterhaltung.
  • C ++ - Vorlagen haben sich als vollständig erwiesen, trotzdem würden Sie nie ganze Programme damit schreiben.

Umgekehrt ist ein DSL für die Problemdomäne geeignet, für die es entworfen wurde (vorausgesetzt, es wurde tatsächlich anständig entworfen), auch ohne Turing-Vollständigkeit:

  • HTML * bietet eine übersichtliche Möglichkeit, einen DOM-Baum zu beschreiben. Während JavaScript vollständig ist und dazu verwendet werden kann, ist es viel lauter und unklarer
  • XPath und andere Abfragesprachen, PCRE ohne eingebetteten Code usw. sind leistungsstarke Tools für den einzelnen Auftrag, für den sie entwickelt wurden

* IIRC hat bewiesen, dass HTML mit CSS-Animationen Turing vollständig ist, indem sie Conways Game of Life für eine Reihe von Kontrollkästchen implementieren. Die Nützlichkeit von HTML bleibt jedoch auch in Browsern erhalten, die CSS-Animationen nicht unterstützen.

back2dos
quelle
2
Haben Sie einen Link zu Conways Leben in CSS implementiert?
RBerteig
Ich kenne keine CGOL-Implementierung in CSS, aber ich weiß, dass Regel 110 implementiert wurde. Es scheint aber nicht zu finden, es scheint verschoben worden zu sein.
Christian Mann
-1 Sehr interessant, geht aber nicht auf die gestellte Frage ein
mattnz
2
@ Mattnz: Falsch. Ich gebe konkrete Beispiele für nicht Turing-vollständige Sprachen, die nützlich sind, und die meiner Meinung nach eine angemessene Antwort auf die Frage "Ist es tatsächlich möglich, eine 'nützliche' Programmiersprache zu haben, die nicht Turing-vollständig ist?", Ähnlich einer anderen Antwort hier
back2dos
3

Es gibt tatsächlich Programmiersprachen, in denen man nur "effiziente" Programme schreiben kann. Effizient in diesem Sinne bedeutet, dass jedes in einer solchen Sprache geschriebene Programm eine Sprache in P. Bellantoni, Niggl und Schwichtenberg beschreiben hier eine solche Sprache .

SpaceTrucker
quelle
1

Der C - Präprozessor ist nicht Turing-complete (mit Absicht), aber es kann immer noch einen Dolmetscher implementieren für eine Sprache , die ist Turing vollständig (Order-the-Sprache, wie in der Dokumentation beschrieben, ist im Grunde nur eine run-of-the Mühle rein funktionale ML / Scheme-Typ Sache, und wäre relativ unauffällig - wahrscheinlich ganz nett zu bedienen - wenn es nicht für die ungewöhnliche Umsetzung wäre).

Der Trick dahinter ähnelt den obigen Argumenten zur Implementierung einer Turing-Maschine in einem endlichen physikalischen Universum: Der C-Präprozessor kann der Sprache nicht unendlich viele Schritte oder Datenzellen bereitstellen , aber er kann:

  1. Geben Sie eine unangemessen große dynamische Zahl an (standardmäßig 2 ^ 64), die groß genug ist, um die realistischsten Probleme mithilfe eines exponentiellen Expansionsprozesses zu lösen ( Murmeln, Murmeln, Lebensdauer des Universums, Murmeln ).

  2. Verwenden Sie eine beliebige statische Begrenzung für die obige Zahl, dh während die Anzahl der Schritte eine endliche Zahl sein muss, können Sie die spezifische Begrenzung zum Zeitpunkt des "Kompilierens" ändern, indem Sie die statischen Einstellungen der Interpreter-Engine ändern. Da es keine (theoretische) Begrenzung für den tatsächlichen Wert dieser Obergrenze gibt, kann sie (theoretisch) erweitert werden, um dem Platzbedarf für ein Abschlussprogramm zu entsprechen.

Um nicht zu argumentieren, dass Order an sich notwendigerweise "nützlich" ist oder dass jede CPP-implementierte Engine dies wäre, aber es ist ein interessanter Proof of Concept. Es ist angeblich auch dynamisch getippt , was für diesen Bereich ungewöhnlich ist.

Leushenko
quelle
Gegenstimme für das Murmeln mitten in der Vorlesung.
Jpaugh
-1

Ja, in der Tat ist es möglich, eine nützliche Sprache zu haben, die nicht vollständig ist. Siehe hier: http://tkatchev.bitbucket.org/tab/examples.html

Ein weiteres Beispiel für eine nützliche unvollständige Turing-Sprache ist SQL. (Und noch eine andere ist Tabellenkalkulation wie Gnumeric oder Excel, obwohl sie nicht wirklich Programmiersprachen sind.)

Welche Gründe sprechen für eine Sprache, die nicht vollständig ist? Auf diese Weise können Sie einige starke Garantien für das Laufzeitverhalten abgeben.

Vollständigkeit zu gewährleisten, bedeutet, rekursionsfähig zu sein. Rekursion bedeutet, potenziell unbegrenzte Strukturen im Gedächtnis zu haben. Da in der realen Welt das Gedächtnis nicht unendlich ist, erfordert die Vollständigkeit des Turing eine Speicherverwaltung und / oder eine Speicherbereinigung.

Das Verbot der Rekursion ist eine großartige Möglichkeit, um das wirklich, wirklich schwierige Problem der Ressourcenverwaltung zu vermeiden.

Nota bene! Turing unvollständig zu sein, bedeutet nicht unbedingt, dass ein Programm unbedingt beendet wird. Eine unvollständige Turing-Sprache könnte die Auswertung einer unendlichen Lazy-Liste ermöglichen.

tkatchev
quelle
-1

Eine interessante "Sub-Turing-Programmiersprache" wurde bisher nicht erwähnt, also werde ich sie hinzufügen.

Es heißt "Crema" . Es beschreibt sich als:

Crema ist ein LLVM-Front-End, das speziell für die Ausführung im Sub-Turing-Complete-Bereich konzipiert ist. Crema wurde so konzipiert, dass es einfach zu erlernen und für die meisten Programmieraufgaben praktisch ist und die Komplexität des Programms auf das zur Verbesserung der Sicherheit erforderliche Minimum beschränkt.

Es ist ziemlich minimalistisch und ziemlich niedrig.

C-Entwicklern dürfte das bekannt vorkommen.

Es wurde ursprünglich von der Defense Advanced Research Projects Agency (DARPA) finanziert, sieht aber zum Zeitpunkt des Schreibens noch recht ungepflegt aus. Aber vielleicht interessiert sich doch jemand.

Mateusz Kowalewski
quelle