Worauf bezieht sich die Ausdruckskraft konkret?

Ausdruckskraft wird von Wikipedia definiert als:

.. die Breite der Ideen, die in dieser Sprache dargestellt und kommuniziert werden können.

Beziehen sich "Ideen" auf die Dinge (Operationen, Strukturen, Algorithmen usw.), die wir mit der Maschine kommunizieren können ? Oder bezieht es sich auf die "menschlichen" Konzepte, die erfasst und mit der Sprache an andere Menschen kommuniziert werden können?

Wie wird die Ausdruckskraft bewertet und gemessen?

Wenn wir zum Beispiel eine Sprache wie JavaScript verwenden und den Variablennamen eine seltsame Einschränkung auferlegen, zum Beispiel, dass die Variable eine 8-stellige Zahl sein muss, der ein Unterstrich vorangestellt wird/^_[0-9]{8}$/ , verlieren wir die Ausdruckskraft?

Oder wäre das nur absurd und nervig?

Zu klären:

Wird die Ausdruckskraft an den allgemeinen Begriffen gemessen, die der Sprache inhärent sind?

• ganze Zahlen und Zeichenketten
• Schleifen
• Bedingungen

Oder die Anzahl spezifischer , einzigartiger Ideen, die die Sprache darstellen kann:

• die ganzen Zahlen 1, 2 ... 2 ^ 32
• Zeichenfolgen mit "Was sagt der Fuchs?" und "wha pah pah pah pah pah pow"
• für jeden Frosch in meiner Sammlung von Fröschen
• wenn Frosch ist grün oder etwas dann etwas tun ,

Das wegweisende Papier zur Ausdruckskraft ist Über die Ausdruckskraft von Programmiersprachen von Matthias Felleisen (1991) . Es enthält eine mathematisch strenge Definition der Ausdruckskraft von Sprachen.

Intuitiv, wenn jedes Programm, das in Sprache A geschrieben werden kann, auch in Sprache B mit nur lokalen Transformationen geschrieben werden kann, aber es gibt einige Programme, die in Sprache B geschrieben werden, die nicht in Sprache A geschrieben werden können, ohne ihre globale Struktur zu ändern (dh nicht mit nur rein lokale Transformationen), dann wird die Sprache B ist ausdrucksvoller als Sprache A .

Eine nette Eigenschaft dieser Definition ist, dass sie die Möglichkeit zulässt, dass es Sprachpaare gibt, in denen es Programme in X gibt, die nicht in Y ausgedrückt werden können, und Programme in Y, die nicht in X ausgedrückt werden können , und daher sind die Sprachen verschieden, aber auch nicht sprache ist ausdrucksvoller als die andere. Dies passt gut zu unserer realen Erfahrung, dass es einige Sprachen gibt, die in einigen Dingen gut sind und einige, die in anderen Dingen gut sind, und keine ist im Allgemeinen "besser" als die andere.

Ausdruckskraft wird von Wikipedia definiert als:

Lassen Sie uns diese Seite noch einmal lesen. Eines der ersten Dinge, die zu beachten sind, ist, dass dort "Sprache" und nicht "Programmiersprache" steht und die meisten Beispiele keine Programmiersprachen sind. Das erste Beispiel ist ein Vergleich von OWL2 EL und OWL2 RL, die beide Ontologie sind Sprachen.

Man kann das Konzept auf Programmiersprachen anwenden, aber auch auf Pattern-Matching-Sprachen, Markup-Sprachen, Abfragesprachen, visuelle Stylesheet-Sprachen, reguläre Ausdrücke (und alle regulären Sprachen, auf die sie sich beziehen) und so weiter. Man kann sogar auf die Ausdruckskraft natürlicher Sprachen wie Englisch verweisen, was oft sehr informell, aber mit größerem Ernst bei der Betrachtung der Probleme im Zusammenhang mit der Verarbeitung natürlicher Sprachen geschieht.

Beziehen sich "Ideen" auf die Dinge (Operationen, Strukturen, Algorithmen usw.), die wir mit der Maschine kommunizieren können? Oder bezieht es sich auf die "menschlichen" Konzepte, die erfasst und mit der Sprache an andere Menschen kommuniziert werden können?

Es bezieht sich auf das, was in dieser Sprache ausgedrückt werden kann und als eine Sache für sich betrachtet wird.

Beispiel: (In meinen Beispielen verwende ich JavaScript, da Ihre Frage darauf hinweist, dass es eine der Sprachen ist, die Sie kennen.) Beachten Sie die Javascript-Anweisung:

var x = 3 + 4;

Dies bedeutet, dass die Wertsumme von 3 und 4 berechnet wird und der Wert einer Beschriftung xin einem bestimmten Namespace-Bereich zugeordnet wird.

Wenn wir alle Computer der Welt zerstören und diesen Code auf ein Stück Papier schreiben würden, würde es bleiben, dass es in Javascript immer noch dieselbe Bedeutung hat. Wir wären nicht in der Lage, solchen Code für irgendetwas auszuführen, aber die abstrakte Definition der Sprache ist immer noch etwas, worüber wir sprechen könnten.

Das mag pedantisch erscheinen, aber es ist eigentlich ziemlich wichtig, dass Sprachen Dinge sind, über die abstrakt argumentiert werden kann, ohne die realen Computer zu berücksichtigen. Zum einen sind die Leute, die über theoretische Aspekte von Computersprachen nachdenken, die in der Praxis noch nicht realisierbar waren, einer der Faktoren, die uns dahin gebracht haben, wo wir heute sind. Computer brauchen Informatik, aber Informatik braucht keine Computer, nur die Idee einer Berechnung.

Natürlich benutzen wir Computer in der realen Welt, und heutzutage verwenden viele Leute sie in der Praxis, anstatt einige Spezialisten, die sie theoretisch diskutieren. Auf der Seite, auf die Sie verlinkt haben, heißt es:

Der Ausdruck Ausdruckskraft kann mit einer Reihe von Bedeutungen verwendet werden. Es kann ein Maß für die Ideen bedeuten, die in dieser Sprache ausgedrückt werden können:

• ungeachtet der Leichtigkeit (theoretische Ausdruckskraft)

• prägnant und leicht verständlich

Der erste Sinn dominiert in Bereichen der Mathematik und Logik, die sich mit der formalen Beschreibung von Sprachen und ihrer Bedeutung befassen, wie der formalen Sprachtheorie, der mathematischen Logik und der Prozessalgebra.

In informellen Diskussionen bezieht sich der Begriff oft auf den zweiten Sinn oder auf beides. Dies ist häufig bei der Diskussion von Programmiersprachen der Fall. Es wurden Anstrengungen unternommen, um diese informellen Verwendungen des Begriffs zu formalisieren

Von diesen beiden Verwendungszwecken bezieht sich der praktische Einfluss des ersten Begriffs ausschließlich auf das, was an den Computer übermittelt werden kann.

Die zweite bezieht sich mehr auf das menschliche Verständnis sowohl beim Lesen als auch beim Schreiben, obwohl der Grad, in dem es dies tut, zwischen den Verwendungen sehr unterschiedlich ist, da sie informell sind und als solche nicht genau definiert sind.

Wenn wir zum Beispiel eine Sprache wie JavaScript verwenden und den Variablennamen eine seltsame Einschränkung auferlegen, zum Beispiel, dass Variable eine 8-stellige Zahl sein muss, der ein Unterstrich vorangestellt wird /^_[0-9]{8}$/, verlieren wir die Ausdruckskraft?

Durch die formale Definition haben wir keine Ausdruckskraft verloren: Wir sind auf 100.000.000 Variablen beschränkt, aber wenn es wirklich nötig wäre, könnten wir dies umgehen, indem wir Objekte erstellen, die mehr Variablen im neu erstellten Namespace enthalten. Als solches könnte jedes Programm, das heute in Javascript geschrieben ist, in dieser neuen Form umgeschrieben werden, so dass sie gleichermaßen aussagekräftig sind.

Nach der informellen Definition haben wir einiges verloren, aber wie viel davon abhängt, wie informell wir sind, was sich ändern wird, da man wiederum nicht sagen kann, was "die Regel" für eine informelle Verwendung ist. Wir könnten sagen, wir haben ein kleines Stück verloren, weil Programme mit mehr als 100.000.000 Variablen im selben Namespace über eine einfache Substitution hinaus neu geschrieben werden müssen. Eine noch informellere Verwendung würde sich wiederum auf die mentale Auswirkung derartiger unbeholfen variabler Namen auf die Gesamtheit der Menschen beziehen.

Es ist auch erwähnenswert, dass die Leute informell Dinge betrachten, die überhaupt nicht Teil der Sprache sind. Betrachten Sie die Änderungen in Javascript von der Erstellung bis heute.

Die formalste Definition besagt, dass die Ausdruckskraft ziemlich unverändert geblieben ist. Immerhin war Turing am Anfang komplett.

Durch eine informellere Definition ist es in bestimmten Dingen wie der Array-Manipulation, der Ausnahmebehandlung und (vielleicht am allermeisten) der Einbeziehung regulärer Ausdrücke erheblich ausdrucksvoller geworden. Diese führen nichts aus, was zuvor mit Javascript nicht möglich war, obwohl sie oft in wenigen Zeilen und einer Ausführungszeit von weniger als einer Sekunde ausgeführt werden können, die kilobyte Code zum Schreiben in Javascript1.0 und eine lange Zeit zum Ausführen benötigt.

Durch eine viel informellere Definition wieder die Änderung von Javascript's erstem Gebrauch in Browsern (in der Lage, die Werte von Formulareingaben zu ändern, document.writewährend die Seite zuerst analysiert wird und an einen neuen Ort verschoben wird oder in der Geschichte vorwärts oder rückwärts geht, aber hübsch Vieles andere) dazu ist heute (in der Lage, fast alles auf der Seite zu ändern, einschließlich der Daten von Serveraufrufen) absolut immens, obwohl sich das meiste nicht auf Javascript bezieht, sondern auf die erstellten Objektmodelle und APIs verfügbar, anstatt die Sprache (z. B. VBScript im IE profitiert von diesen Änderungen gleichermaßen).

Meiner Meinung nach ist diese letzte Verwendung so informell, dass sie nicht wirklich korrekt ist, aber das ist das Problem bei informellen Definitionen.

Durch die formale Definition ist es wirklich überhaupt nicht ausdrucksvoller geworden.

Ich glaube nicht, dass Regeln für die Benennung von Variablen wirklich erfassen, was unter "Ausdruckskraft" zu verstehen ist. Ich denke, dass sich "Ausdruckskraft" auf grundlegendere Dinge bezieht. Betrachten Sie beispielsweise C # mit Linq im Vergleich zu C # vor Linq. Nach dem Hinzufügen von Linq wurde es möglich, SQL-ähnliche Abfragen direkt in C # zu schreiben. Dies ist viel eleganter als die vorherigen Alternativen, z. B. SQL in Zeichenfolgenliterale zu setzen und diese dann an den Server zu übergeben oder eine Auflistung mit "for" zu durchlaufen.

Ein weiteres gutes Beispiel sind Sprachen mit prototypbasierter Vererbung. In diesen Sprachen ist es möglich, einer Instanz oder sogar einer Klasse (unter welchem ​​Namen auch immer eine "Klasse" in einer bestimmten Sprache vorkommt ...) zur Laufzeit einfach neue Methoden hinzuzufügen. Das kann man in C ++ oder C # nicht wirklich machen. Ihnen fehlt dieser Ausdrucksgrad im Vergleich zu prototypbasierten Sprachen. (C # hat das Konzept der Erweiterungsmethoden, und man kann durchaus sagen, dass diese die Ausdruckskraft erhöhen.)

Wie im Wikipedia-Artikel erwähnt, bezieht sich Ausdruckskraft auf die Menge von Programmen, die in der Sprache ausgedrückt werden können. Alles, was Sie als "Programmiersprache" betrachten (JavaScript, LISP, C #, Perl usw.), ist im Wesentlichen vollständig und kann alles ausdrücken, was als "berechenbar" bezeichnet wird.

Es sollte jedoch klar sein, dass reguläre Ausdrücke nicht so aussagekräftig sind wie reguläre Programmiersprachen. Außerdem sind Shell-Platzhalter etwas weniger aussagekräftig als reguläre Ausdrücke.

Eine SQL-Version mit allgemeinen Tabellenausdrücken ist aussagekräftiger als eine Version ohne, da Sie mit CTEs rekursive Abfragen darstellen können, die in SQL sonst nicht ausgedrückt werden könnten.

Es gibt einen einfacheren und direkteren Weg, die Ausdruckskraft zu verstehen, aber zuerst müssen wir herausfinden, was wir unter Sprachen verstehen. Es gibt zwei Disziplinen, die Sprachen studieren: Linguistik und Automaten. Beide stimmen darin überein, dass Sprache Sätze von Wörtern (endliche Folgen) sind, die aus einem endlichen Alphabet unter Verwendung von Verkettung aufgebaut sind. Typischerweise haben interessante Sprachen (mit interessant meine ich solche Sprachen, die wir auf nützliche Weise interpretieren können) auch eine Reihe von Regeln, die regeln, welche Wörter in der Sprache sind und welche nicht. Beachten Sie, dass Ausdruckskraft nur dann vorhanden sein kann, wenn eine Interpretation vorliegt.

Mit Interpretation meine ich die Existenz einer Funktion, bei der ein Wort in einer Sprache ein Objekt aus einer Reihe von Objekten auswählt (dies ist offensichtlich für natürliche Sprachen umstritten).

Lassen Sie sich jedoch nicht durch die Verwendung von "Wort" in die Irre führen. Ein Java-Programm ist ein Wort in der Java-Sprache (obwohl es mehrere Dateien umfassen kann, die mehrere durch Leerzeichen getrennte Zeichenfolgen enthalten).

Es wäre kontraproduktiv, so komplizierte Sprachen wie moderne Programmiersprachen zu verwenden, um mit diesem relativ einfachen Konzept fertig zu werden. Deshalb würde ich lieber mathematische Formeln verwenden.

• Definieren wir Sprache A als alle Formeln, die eine Ganzzahladdition beinhalten.

• Definieren wir Sprache B als die Sprache aller Formeln mit ganzzahliger Multiplikation.

In beiden Fällen verbieten wir die Verwendung des Identitätselements. Somit enthält Sprache A die Wörter "1 + 1", "1 + 2", "1 + 3", "2 + 3" und so weiter. Die Sprache B enthält Wörter "2 * 2", "2 * 3", "2 * 4", "3 * 4" und so weiter. Wir weisen den jeweiligen Symbolen auch die üblichen Interpretationen "*" und "+" (Ganzzahladdition und Ganzzahlmultiplikation) zu. Die Interpretation von "1 + 1" ist also 2 und die Interpretation von "2 * 2" ist 4.

Beachten Sie nun, dass die Sprache A strikt aussagekräftiger ist als die Sprache B, da in ganzen Zahlen die Multiplikation zwar als wiederholte Addition gewertet werden kann, es jedoch keine Möglichkeit gibt, die Addition als Multiplikation im Allgemeinen darzustellen.

Zusammenfassend lässt sich sagen, dass Sprache A ausdrucksvoller ist als Sprache B, wenn ihre Interpretationsfunktionen eine gemeinsame Domäne haben. Das Bild der Interpretationsfunktion von B ist jedoch eine geeignete Teilmenge des Bildes der Interpretationsfunktion von A.

TLDR: Wenn ein Feature fehlt, aber auf andere Weise ausgedrückt werden kann, ist dies kein Mangel an Ausdruckskraft. Wenn Sie sich einen Algorithmus vorstellen oder ihn sogar in einer Sprache implementieren können, eine andere Sprache jedoch so strukturiert ist, dass die Implementierung des Algorithmus nicht möglich ist, handelt es sich um ein Ausdrucksproblem *.

Einschränkungen bei der Benennung von Variablen beeinträchtigen die Ausdrucksfähigkeit nicht (es sei denn, es gibt so wenige Namen, dass man nicht mehr alle Algorithmen ausdrücken und keine Variablen mit so etwas wie Arrays + Indizes fälschen kann).

Ein einfaches Beispiel für einen Mangel an Ausdruckskraft ist: Sie müssen do_homeworkund bring_down_trash. Dies ist leicht in Code zu schreiben:

do_homework();
bring_down_trash();

Diese Lösung sieht ziemlich einfach aus, aber tatsächlich do_homeworkund bring_down_trashungeordnet, könnte man auch schreiben:

bring_down_trash();
do_homework();

Das ist ebenso ungenau, weil es nicht ausdrückt, dass wir nicht beabsichtigt haben, einen Befehl durchzusetzen. Wir wollen auch keine Threads verwenden. Wir wollen so etwas sagen:

compiler_or_interpreter_pick_one(
    {
        do_homework();
        bring_down_trash();
    },
    {
        bring_down_trash();
        do_homework();
    }
);

Soweit ich weiß, ist es sehr schwierig bis unmöglich, dies in einer Programmiersprache auszudrücken.

Ein Beispiel, das mich sehr stört, ist, dass es in Java unmöglich ist, ein Array von Objekten zu haben. Sie können ein Array von Zeigern auf Objekte erstellen, die jedoch nicht dasselbe Speicherlayout aufweisen (Effizienz beim Sprechen).

Ein Beispiel aus einer anderen Antwort : C ++ unterstützt nicht das Hinzufügen von Methoden zu einer Klasse oder Instanz . Dies ist wahr, schränkt jedoch die Ausdruckskraft von C ++ nicht ein.

struct Extensible{
    std::vector<std::function<void(Extensible *)>> instanceExtensions;
    static std::vector<std::function<void(Extensible *)>> classExtensions;
};

Dies ist eine Klasse, zu der Sie eine beliebige Anzahl von Memberfunktionen für Instanzen und die Klasse hinzufügen, entfernen und aufrufen können. Technisch gesehen ist C ++ in dieser Hinsicht wahrscheinlich aussagekräftiger als Programmiersprachen, die diese Funktion tatsächlich unterstützen, da Sie in C ++ auswählen können, wie die Funktionen gespeichert werden sollen (Vektor vs. Array vs. forward_list).

* Einige Sprachen haben einen Mangel an Ausdruckskraft. Normalerweise machen sie es unmöglich, Endlosschleifen zu schreiben. Dies kann das Halteproblem lösbar machen und automatische Korrektheitsnachweise ermöglichen.