Programmiersprache, in der jeder Ausdruck Sinn macht

23

Per Empfehlung reposte ich dies von Stack Overflow .

Kürzlich habe ich über folgendes Thema nachgedacht.

Betrachten Sie den Code für eine Standard "Hallo Welt!" Programm:

main()
{
    printf("Hello World");

}

Nahezu jede Änderung an diesem Code macht ihn nun völlig unbrauchbar. Tatsächlich verhindert fast jede Änderung, dass der Code kompiliert wird. Beispielsweise:

main(5
{
    printf("Hello World");

}

Nun zur eigentlichen Frage. Gibt es eine Programmiersprache, in der jede mögliche Kombination von Symbolen - also jeder Ausdruck - Sinn macht? Ich versuchte, über eine Lösung nachzudenken, und fand zwei:

  1. Postfix mit einer begrenzten Anzahl von Variablen. Im Wesentlichen sind alle Variablen bereits definiert, bevor Sie Code schreiben, und Sie müssen nur damit arbeiten. Theoretisch können Sie eine beliebige Anzahl von Operationen ausführen, indem Sie eine Kette von vielen einfachen Programmen bilden, von denen jedes die Ergebnisse an andere weitergibt. Code kann als eine Reihe von Zeichen in Postfix-Notation geschrieben werden.

  2. "Postfix" mit einem Stapel von Variablen. Variablen werden auf einem Stapel gespeichert. Jede Operation nimmt zwei Variablen von oben und setzt das Ergebnis an ihre Stelle. Das Programm endet, wenn es die letzte Operation oder Variable erreicht hat.

Ich persönlich hasse beide. Sie sind nicht nur begrenzt, sie sind auch unelegant. Es handelt sich nicht einmal um echte Lösungen, sondern vielmehr um Problemumgehungen, die im Wesentlichen einige Arbeiten an einen externen Prozess "verlagern".

Hat jemand eine andere Idee, wie man dieses Problem löst?

user1561358
quelle
48
Bei einem Compiler , erstellen Sie einen neuen Compiler C ' , die wie folgt funktioniert: gegebene Quelle s , übergibt es an C . Wenn C damit einverstanden ist und eine ausführbare Datei erzeugt, ist dies der Fall. Wenn sich C jedoch beschwert, wird eine ausführbare Datei ausgegeben, die ausgedruckt wird. Der Compiler C ' akzeptiert jeden String als gültiges Programm. CCsCCCYou are a bimbo.C
Andrej Bauer
1
BF benötigt passende [ ]Befehle (laut Wiki-Seite). Mein Gedanke war, die CPU-Opcodes zu betrachten. Aber selbst dann können einige Muster zu Problemen führen (z. B. wenn ein Opcode 3 Bits umfasst, Ihr Programm jedoch nur 2 Bits). Abgesehen von diesem Problem, bei dem möglicherweise mit zusätzlichen 0 Bits aufgefüllt wird, kann man an jede CPU mit einem denken vollständiger Opcode-Satz, der den Anspruch "Jeder String ist ein gültiges Programm" erfüllt. Vielleicht bedeutungslos, aber immer noch gültig.
Ran G.
1
Lassen Sie Ihre Hardware eine Z-80-CPU mit 64 KB RAM sein. Schreiben Sie einen Compiler, der einfach den ASCII-codierten Quellcode in den 64-KB-Speicher kopiert (ggf. Abschneiden oder Auffüllen mit Nullen). Dieser Compiler gibt niemals einen Syntaxfehler aus.
Ben Crowell
1
@RanG. Ein 'Compiler', der jeden Bitstream verarbeitet und ihn als gültiges Bit des Objektcodes für den gegebenen Prozessor repariert, würde meines Erachtens die Anforderungen des OPs erfüllen. Selbst für Systeme mit komplexen Befehlssätzen wie x86 wäre dies wahrscheinlich nicht besonders schwierig. Ich habe vor Jahren einen Artikel über die Gültigkeit von zufälligen Bytes als x86-Programme gelesen und festgestellt, dass x86 tatsächlich weitaus robuster ist als von den Autoren ursprünglich erwartet.
Otakucode
2
Ohne weitere Bedingungen ist diese Frage langweilig: Andrejs Kommentar und Davids Antwort geben "triviale" Antworten. Sie müssen genauer bestimmen, was Sie wollen.
Raphael

Antworten:

31

Redcode, die Assemblersprache hinter Codewars, wurde ausdrücklich so geschrieben, dass sie nur sehr wenige Stoppanweisungen enthält, da der Code häufig verstümmelt wird, bevor er endgültig veröffentlicht wird. Je mehr Möglichkeiten er zum Stoppen hat, desto weniger interessant ist das Spiel.

In der Praxis gibt es nur sehr wenige solcher Sprachen, weil wir nicht nur wollen, dass ein Programm ausgeführt wird, sondern dass es so läuft, wie wir es erwarten. Wenn Sie einen Tippfehler machen und die Art und Weise ändern können, wie das Programm ausgeführt wurde, muss es annehmbar nahe am ursprünglich erwarteten Verhalten liegen, oder die Programmierer sind frustriert.

Es gibt einen gewissen Vorrang für solche Dinge, wenn natürliche Sprachen anstelle von formalen Sprachen verwendet werden, aber ich würde es nicht als großes Feld bezeichnen, wenn man es mit der Verwendung formaler Sprachen vergleicht. Wenn Sie sich für solche Programmiersprachen interessieren, ist die Community für die Verarbeitung natürlicher Sprachen genau das Richtige für Sie.

Ein weiteres Gebiet, das Sie sich ansehen könnten, ist die Genetik. Es gibt bemerkenswert wenige genetische Sequenzen, die einfach ungültig sind. Viele von ihnen sind bei Reproduktionen nicht sehr effektiv, aber nur sehr wenige sind ungültig.

Cort Ammon - Setzen Sie Monica wieder ein
quelle
1
Genetik scheint kein gutes Beispiel zu sein. Sprechen Sie in Bezug auf Gültigkeit oder Ungültigkeit nur von Replikation? Weil natürlich jeder String ein gültiges Programm für eine Sprache ist, in der die einzig mögliche Anweisung ist replicate this string. Es ist jedoch keine wirklich aussagekräftige Programmiersprache, da es bei weitem nicht in der Nähe von Turing Complete liegt.
Tel.
2
@tel: Cort spricht wahrscheinlich eher von der Proteinsynthese über mRNA als von der Replikation. Nahezu jede genetische Sequenz kann transkribiert und dann in die Proteinsynthesemaschinerie eingegeben werden: Ist das herauskommende Protein ausreichend stabil, dass es zum Zeitpunkt seines Baus noch nicht abgebaut ist, und wenn ja, ob es irgendetwas Nützliches bewirkt? Der Organismus ist eine andere Sache ...
Steve Jessop
3
Der genetische Code ist kein Code, um sich selbst zu reproduzieren. Es ist (im Allgemeinen) ein Code für ein Protein. Ob das Protein nützlich ist, ist oft eine andere Frage. Natürlich wird es interessanter. Einige Teile des "Codes" in einer genetischen Sequenz sind eher eine Anweisung im Sinne von "Dieser Code ist ein paar Zeilen weiter unten - manchmal sollten Sie ihn einfach ignorieren." Es gibt alle möglichen coolen "Programme", in denen sich Zellen und Viren gegenseitig bekämpfen.
Joel
TECO ist ein weiteres Beispiel aus der Praxis .
cjm
1
@ CJM wow. "Eine API ist nicht fertig, wenn Sie alles hinzugefügt haben, sondern wenn Sie alles entfernt haben." Wenn Sie nicht TECO sind, sind Sie fertig, wenn Sie keine Zeichen mehr haben, denen Sie eine Bedeutung zuweisen können.
Cort Ammon - Reinstate Monica
16

Die Idee einer universellen Turingmaschine verwendet genau eine solche "Programmiersprache": eine Codierung von Turingmaschinen als natürliche Zahlen, beispielsweise binär dargestellt, so dass jede natürliche Zahl eine Turingmaschine, dh ein Programm bezeichnet. In dieser Sprache ist jede Folge von Nullen und Einsen ein Programm.

nn te Zeichenfolge in der Liste, die ein gültiges Java-Programm ist. In der neuen Programmiersprache sind Programme nur natürliche Zahlen und jede natürliche Zahl ist ein gültiges Programm.

Ich bin mir sicher, dass es auch esoterische Programmiersprachen gibt, in denen jeder String ein Programm ist. Wenn Sie jedoch nur nach einer Liste dieser Fragen fragen, ist Ihre Frage hier meines Erachtens nicht zum Thema.

David Richerby
quelle
13

Eine Programmiersprache so zu erweitern, dass jeder Ausdruck Sinn ergibt, ist immer möglich, aber nicht interessant. Sie können beispielsweise jedem Ausdruck, den die Originalsprache ablehnt, einfach die Bedeutung „Nichts tun“ zuweisen.

Das Entwerfen einer Programmiersprache, in der jeder Ausdruck so sinnvoll ist, dass Sie ihn ausführen können, ist nicht besonders nützlich. Eine gute Programmiersprache ist nicht nur eine, in der ein Affe auf einer Tastatur tippen und ein gültiges Programm schreiben kann, sondern eine, in der ein Programmierer leicht das Programm schreiben kann, das er schreiben möchte. Das Schreiben gültiger Programme ist nicht der schwierige Teil des Programmierens: Der schwierige Teil ist das Schreiben eines Programms, das das ausführt, was von ihm erwartet wurde. Das Ablehnen offensichtlich falscher Programme ist in dieser Hinsicht sehr hilfreich.

Eine andere Möglichkeit, dies zu beheben, besteht darin, die Semantik aller möglichen Eingaben vollständig zu definieren, einschließlich der Angabe, welche Kompilierungs-, Lade- oder Laufzeitfehler für jede Eingabe generiert werden sollen, falls vorhanden. Das heißt, "Programm nach dem Drucken Syntax error at line 42auf dem Standardfehlerstrom abbrechen " ist Teil der definierten Semantik der Sprache. Jeder Ausdruck "macht Sinn", indem er eine definierte Bedeutung hat. Ist das eine nützliche Bedeutung? Vielleicht - schließlich ist es nützlich, wenn das Programm offensichtlich falsch ist, es abzulehnen.

Gilles 'SO - hör auf böse zu sein'
quelle
12

Schauen Sie sich Jot an , eine auf kombinatorischer Logik basierende Sprache, in der jede Folge von 0en und 1en (einschließlich einer leeren Folge) ein gültiges Programm ist.

Petr Pudlák
quelle
2
Dies ist keine Informatik - Antwort.
Raphael
2
@Abdulrhman Es ist ganz einfach, eine Bijektion zwischen binären Zeichenfolgen und natürlichen Zahlen zu definieren. Sie können also jedes Programm als natürliche Zahl codieren, wenn Sie möchten.
CodesInChaos
7
@Raphael Bitte erläutern Sie die Antwort oder schlagen Sie eine Verbesserung vor. Gerne verbessere ich sie, wenn Sie Gründe für Ihre Kritik angeben.
Petr Pudlák
+1, ich wollte eine ähnliche Antwort für eine fiktive Programmiersprache geben, die auf natürlichen Zahlen basiert, aber das ist ähnlich. AFAIK: Es gibt keine Programmierung (in der Praxis) mit dieser Funktion, aber man kann eine mit nur Zahlen konstruieren, wobei jede Kombination eine Bedeutung hat (sowohl als Operatoren als auch als Operanden). Dies ist der Schlüssel
Nikos M.
8

Ein gutes Beispiel ist Whitespace . In der eigentlichen Sprache ist jede Kombination von Operatoren gültig. Die Operatoren sind Leerzeichen, Tabulator und Zeilenvorschub (insbesondere "\ n"). Alle anderen Zeichen gelten als Kommentare .

Diese Antwort und in der Tat Ihre Frage (sowie die gesamte Webseite) sind Beispiele für gültige Whitespace-Programme (obwohl sie möglicherweise nichts besonders Interessantes bewirken).

Slebetman
quelle
Ich habe gerade darüber nachgedacht, nachdem ich meine Brainfuck-Antwort gepostet habe (deine ist besser, da sie korrekt ist), aber ich frage mich - ist ein leeres Programm immer noch ein Programm? (dh wenn diese drei Zeichen im gesamten Dateistream fehlen). - Wenn in meinem Auto all die Dinge fehlen würden, die es zu einem Auto gemacht haben, wäre es dann immer noch ein Auto?
BrainSlugs83
Dies ist keine Informatik - Antwort. (Auch "jede Whitespace-Zeichenfolge"! = "Jede Zeichenfolge".)
Raphael
2
@Raphael: Aber jede mögliche Zeichenfolge (einschließlich solcher , die keine Leerzeichen enthalten) gelten Leerzeichen Programme - zur Kenntnis , dass alle Zeichen , die keine Leerzeichen ist einfach Kommentare im Leer Programmiersprache sind
slebetman
2
@slebetman Du hast meinen Kommentar in Klammern zu wörtlich interpretiert. Ich habe über ungepaarte Loop-Token gesprochen. Einige ähnliche Probleme in Leerzeichen könnten sein: Funktioniert die Rückkehr ohne vorherigen Anruf? (kodiert als [LF][Tab][LF]) Was passiert, wenn Sie einen leeren Stapel platzieren? Was passiert, wenn Sie zu einem undefinierten Label springen? Was passiert, wenn Sie doppelte Bezeichnungen definieren?
CodesInChaos
7

Ich möchte auf die Idee eingehen, die viele Plakate gegeben haben, dass eine solche Sprache "nutzlos" wäre. Vielleicht wäre es für Menschen nutzlos, manuell zu schreiben, um eine bestimmte Aufgabe zu lösen. Dies ist jedoch sicherlich nicht der einzige Anwendungsfall, obwohl er in der Mehrzahl der Fälle für Programmiersprachen verwendet wird. Einige Anwendungsfälle kommen in den Sinn, wenn eine solche Sprache nützlich ist, und wir können diese Felder nach Beispielen für solche Sprachen durchsuchen.

Erstens ist Cort Ammons Anspielung auf die Genetik genau richtig : Die Programmtransformation in der Frage (als Ersatz )für 5) kann als Mutation angesehen werden . Diese Art der Manipulation ist auf dem Gebiet der Evolutionsberechnung üblich ; insbesondere genetische Algorithmen führen solche Transformationen auf Saiten , während die genetische Programmierung Transformationen Programme . In beiden Fällen möchten wir normalerweise jeder Möglichkeit eine Bedeutung zuweisen, da dies den kompaktesten Suchraum ergibt.

Genetische Algorithmen basieren auf einer Art Bewertungsfunktion für Zeichenfolgen. Wenn wir einen Programmiersprachen-Interpreter als Auswertungsfunktion verwenden, haben wir ein Szenario, in dem eine Programmiersprache nützlich ist, die allen möglichen Zeichenfolgen eine Bedeutung zuweist. In der genetischen Programmierung wird angenommen, dass unsere Bewertungsfunktion ein Programmierspracheninterpreter ist, wir können jedoch verschiedene Darstellungen für unsere Programme auswählen . Beispielsweise arbeiten viele Systeme mit abstrakten Syntaxbäumen. Wenn wir Zeichenfolgen als Repräsentation auswählen, stellen wir dasselbe Szenario wieder her wie bei genetischen Algorithmen.

Eine andere Situation, in der jeder String ein gültiges Programm sein soll, ist die Aufzählung von Programmen. Dies hängt mit der von CodesInChaos erwähnten Bijektion zusammen, aber wir ziehen es aus mehreren Gründen möglicherweise vor, Zeichenfolgen anstelle von natürlichen Zahlen zu verarbeiten:

  • Wenn die Sprache eine gewisse Struktur aufweist, z. Unterstrings können Bedeutungen zugewiesen werden, die bei der Übersetzung in Natural-Zahlen verloren gehen können. In diesem Fall bevorzugen wir möglicherweise die Verwendung von Zeichenfolgen, um Teilzeichenfolgen lokal zu analysieren und zu transformieren, anstatt das gesamte Programm als Zahl darzustellen. Dies ist analog zu der Vorgehensweise, bei der wir bitweise Operationen für ein Int anstelle von arithmetischen Ausdrücken bevorzugen, wenn jedes Bit eine individuelle Bedeutung hat. Dies ist im Grunde eine Verallgemeinerung des Evolutionsszenarios.
  • Möglicherweise möchten wir die Programme nach Bedarf generieren. Beispielsweise könnten wir mit der Ausführung eines Programms beginnen, das völlig unbestimmt ist, und die einzelnen Anweisungen (z. B. Zeichen) nur dann (z. B. zufällig) generieren, wenn der Anweisungszeiger sie erreicht. Dies ist in der algorithmischen Informationstheorie üblich, wo das Programm ein Turing-Maschinenband ist, und das Ziel ist, das Verhalten von zufällig erzeugten Programmen zu charakterisieren. Beispielsweise können wir den Solomonoff-Wert vor beliebigen Zeichenfolgen als die Wahrscheinlichkeit formulieren, dass eine universelle Turing-Maschine mit einem zufälligen Band diese Zeichenfolge ausgibt.

In Bezug auf Beispielsprachen basieren viele evolutionäre Rechensysteme auf Stack-Sprachen wie der Push- Familie. Diese neigen dazu, beliebige Ströme von Token zuzulassen (die wir als einzelne Zeichen darstellen könnten). Manchmal (wie im BrainSlugs83-Beispiel für Brainfuck) gibt es Einschränkungen beim Ausgleichen von Klammern. jedoch können wir dies in Beziehung zu sich selbst begrenzenden Programme , dass ein String wie [kein gültiges sein Programm , aber es ist ein gültiges Programm Präfix . Wenn wir uns einen Compiler / Interpreter vorstellen, der den Quellcode von stdin liest, dann lehnt er einen String nicht ab[ , sondern wartet einfach auf weitere Eingaben, bevor er fortfährt.

Sprachen wie Binary Combinatory Logic und Binary Lambda Calculus sind direkt aus der Arbeit an algorithmischer Informationstheorie entstanden, z. von http://tromp.github.io/cl/cl.html

Dieses Design eines minimalistischen Universalcomputers wurde von meinem Wunsch motiviert, eine konkrete Definition der Kolmogorov-Komplexität zu entwickeln, die die Zufälligkeit einzelner Objekte untersucht.

Warbo
quelle
2

Echte Programmiersprachen sollen dem Menschen Sinn vermitteln , nicht dem Computer. Da viele lustige Texte mit fast zufällig gemischten Buchstaben in der Show herumschwirren, können die Leute Kauderwelsch lesen und daraus einen Sinn ziehen, auch ohne das Zerfleischen zu bemerken. Denken Sie nur zurück, wie schwierig es ist, Tippfehler und andere solche Fehler in Texten zu finden.

Eine Programmiersprache wie die, nach der Sie fragen, würde den Leuten verständlich machen, was sie lesen möchten, und nicht, was aufgeschrieben ist. Das Debuggen in Sprachen, in denen es eine begrenzte Anzahl von gesetzlichen Bestimmungen gibt, bei denen nicht viel Unklarheit möglich ist, ist bereits schwierig genug. Gute Sprachen reduzieren mögliche Interpretationen zB durch transponierte Symbole oder Tippfehler. Natürliche Sprachen sind aus dem gleichen Grund auch für ihre Redundanz berüchtigt.

vonbrand
quelle
0

In der Programmiersprache Brainfuck kann fast jeder mögliche binäre Ausdruck als Programm interpretiert werden. - Das heißt, Sie könnten ein völlig gutes Programm nehmen, eine Menge Müll hinein tippen und es wäre immer noch ohne Probleme kompilierbar / interpretierbar.

( Bearbeiten: Es stellt sich heraus, dass Sie öffnende und schließende eckige Klammern abgleichen müssen, aber ansonsten gilt das Obige.)

Dies wird durch diese zwei einfachen Methoden erreicht:

  1. Alle Befehle, die es versteht, sind ein einzelnes Byte (in BF sind sie alle einzelne ASCII-Zeichen, zum Beispiel *).

  2. Alle Zeichen, die es nicht versteht, werden als Kommentare verworfen.

Die Programmiersprache ist Turing complete (das heißt, sie kann alles, was jede andere Sprache kann).

*: Es stellt sich heraus, dass nicht alle BF-Befehle ein einzelnes ASCII-Byte sind - dh Klammern MÜSSEN übereinstimmen -, so dass diese Sprache dort nicht die ersten Kriterien erfüllt. - Aber jede Sprache, die beide Kriterien erfüllt, würde das erfüllen, was das OP verlangt.

BrainSlugs83
quelle
2
Nicht nur , dass sich die Frage nicht beantworten, es ist kein Computer ist Wissenschaft Antwort.
Raphael
1
Sie könnten die Sprache neu definieren, um mit diesen auf eine vernünftige Weise umzugehen. ZB indem Sie zu Beginn des Programms genügend Klammern einfügen und am Ende des Programms Klammern schließen, um einen Ausgleich zu erzielen. Es ist einfach, einen Interpreter zu schreiben, der Programme so behandelt, als ob diese Klammern existierten, ohne das Programm tatsächlich neu zu schreiben. Natürlich ist das Starten eines Brainfuck-Programms mit einer öffnenden Klammer ziemlich nutzlos, da es alles bis auf die passende schließende Klammer ignoriert.
CodesInChaos
1
@Raphael Die Frage des OP lautete: "Gibt es eine Programmiersprache, in der jede mögliche Kombination von Symbolen - das heißt jeder Ausdruck - Sinn ergibt?" - Meine Antwort lautet: "Ja, hier ist ein Beispiel für eine, die nahe kommt, und hier ist die Theorie dahinter." - Abgesehen von der Festlegung genauer Regeln für eine Sprachklasse, die den Anforderungen des OP entsprechen würde, bin ich mir nicht sicher, wie viel mehr Raum für Wissenschaft hier ist. Können Sie ein Beispiel oder einen Link zu einer Ressource geben, die genau das enthält, was Sie hier sehen möchten? -- Vielen Dank.
BrainSlugs83
2
David und Gilles geben Antworten auf Fragen der Informatik. Sie erforschen Prinzipien und sagen nicht nur "Sprache X macht das (fast)". Wenn Sie ihre Antworten lesen, werden Sie feststellen, dass Antworten der letzteren Form auch ziemlich langweilig sind. Das ist nicht deine Schuld, aber die OPs - die Frage (als Informatikfrage) ist langweilig; Es gibt ein falsches Gefühl von Komplexität.
Raphael
Man könnte BF leicht "reparieren", so dass jede Zeichenfolge akzeptiert wird: Sie tun einfach so, als ob ]am Ende der Quelle genügend Zeichen vorhanden sind , um allen nicht übereinstimmenden [s zu entsprechen, und [am Anfang genug , um allen nicht übereinstimmenden zu entsprechen ]. Die Semantik von [und ]kann leicht geändert werden, um sie dementsprechend zu machen. (zB wenn kein passender gibt es ]dann [stoppt nur die Ausführung , wenn das Byte an dem Datenzeiger Null ist. ]springt nur zu Beginn des Programms in einer ähnlichen Situation.) Die resultierende Sprache würde komplett sein Turing und eine beliebige Zeichenfolge akzeptieren würde.
Nathaniel