Was ist die mathematische Grundlage für Werte der ersten, zweiten und dritten Klasse in Programmiersprachen?

19

Hinzugefügt

Ich habe gerade zwei verwandte Fragen gefunden

/math//q/1759680/1281

/programming//a/2582804/156458


In Programmiersprachen aus der Programmiersprache Pragmatik von Michael Scott

Im Allgemeinen wird ein Wert in einer Programmiersprache als erstklassig bezeichnet , wenn er als Parameter übergeben, von einem Unterprogramm zurückgegeben oder einer Variablen zugewiesen werden kann. Einfache Typen wie Ganzzahlen und Zeichen sind in den meisten Programmiersprachen erstklassige Werte. Im Gegensatz dazu kann ein Wert der zweiten Klasse als Parameter übergeben, aber nicht von einem Unterprogramm zurückgegeben oder einer Variablen zugewiesen werden, und ein Wert der dritten Klasse kann nicht einmal als Parameter übergeben werden.

Bezeichnungen sind in den meisten Programmiersprachen Werte der dritten Klasse, in Algol jedoch Werte der zweiten Klasse. Unterprogramme zeigen die meisten Variationen an. Sie sind erstklassige Werte in allen funktionalen Programmiersprachen und den meisten Skriptsprachen. Sie sind auch erstklassige Werte in C # und mit einigen Einschränkungen in mehreren anderen imperativen Sprachen, einschließlich Fortran, Modula-2 und -3, Ada 95, C und C ++. 11 Sie sind Werte zweiter Klasse in den meisten anderen imperativen Sprachen und Werte dritter Klasse in Ada 83.

  1. Was ist die mathematische Grundlage für Werte der ersten, zweiten und dritten Klasse in Programmiersprachen?

    Die Terminologie erinnert mich an die Logik erster / zweiter Ordnung, aber hängen sie zusammen?

  2. Es scheint mir, dass der Unterschied zwischen ihnen darin besteht, in welchem ​​speziellen Fall ein Wert verwendet werden kann

    • als Parameter übergeben,
    • von einem Unterprogramm zurückgegeben oder
    • in eine Variable zugewiesen.

    Warum sind die spezifischen Fälle wichtig, während andere Fälle nicht erwähnt werden?

Vielen Dank.

Tim
quelle
23
Das Klassifizieren von Werten in die erste / zweite Klasse ist ebenso fruchtlos wie das Klassifizieren von Sprachen in Paradigmen. Alles, was Sie am Ende haben werden, sind vage Verallgemeinerungen, die das Bild durcheinander bringen. Dies ist nicht der richtige Ansatz zum Verständnis von Programmiersprachen. Was wichtig ist, ist das Verstehen der Syntax, der Statik und der Dynamik der Sprache, aber das ist viel zu groß, um in einem Kommentar darauf
einzugehen
3
Nebenbei: PL / I wäre ein Beispiel für Labels als erstklassig. In PL / I können Sie zu beschriftende Variablen deklarieren, ihnen Codestellen zuweisen und sie aufrufen. Sie können sie auch als Parameter übergeben und sogar Arrays daraus erstellen.
Theraot
@Theraot: Vielleicht datiere ich mich selbst, aber bin ich der einzige, der jemals mit zugewiesenen und berechneten GOTOs in FORTRAN zu tun hatte? Und nein, ich habe das @ $% nicht geschrieben! Code, ich steckte es Reengineering.
Jamesqf
@jamesqf Ich bin mir bewusst, dass ich Labels in FORTRAN und COBOL zuweisen kann. Nein, das habe ich nicht verwendet. Ich bin mir nicht sicher, wie ich die Labels dort einordnen soll. Aber für das, was ich lese (ich habe die Handbücher), geht PL / I darüber hinaus und ich bin überzeugt, dass Labels dort erstklassig sind.
Theraot

Antworten:

45

Es gibt keine und es ist ziemlich willkürlich.

Die einzige nützliche Unterscheidung ist zwischen erstklassig und allen anderen. Jeder Fall, der sich in der "anderen" Klammer befindet, hat in jedem Fall einen eigenen Satz von Regeln, und sie alle zusammen zu fassen, ist einfach nicht sehr hilfreich. "Erste Klasse" bedeutet im Wesentlichen "Sie müssen die Regeln nicht nachschlagen" und "andere" bedeutet "Sie müssen die Regeln lernen".

Beispielsweise sind in C ++ einzelne Funktionen erstklassige Werte, solange sie zustandslos sind. Überlastsätze sind nicht aber Lambdas sind. In C # sind Funktionen im Allgemeinen erstklassige Werte, aber es gibt einige unangenehme Fälle, die beim Umgang mit Typinferenz auftreten, die verhindern, dass sie in allen Fällen auftreten.

DeadMG
quelle
10
+1, obwohl ich im Kontext eines Buches wie Programmiersprache Pragmatik , das eine große Anzahl von Konstrukten in einer großen Anzahl von Sprachen vergleicht und die Ähnlichkeiten und Unterschiede sowie die Auswirkungen auf die Tiefe analysiert, denke, dass diese Art von Kurzschrift nützlich sein kann. (Gehen Sie einfach nicht herum und erwarten Sie von anderen, dass sie "gebraucht" und "gebraucht" so verstehen, dass sie bestimmte Dinge bedeuten.)
ruakh
(Äh, wo mit "gebraucht" und "dritter Hand" ich natürlich "zweiter Klasse" und "dritter Klasse" meine. :-P)
ruakh
3
Wenn Sie mit gebrauchten Funktionen handeln möchten, sollten Sie dies in einer Sprache tun, in der Funktionen erstklassige Bürger sind. ^^
5gon12eder
@ 5gon12eder: "gebrauchte Funktionen" sind diejenigen, die Sie aus Bibliotheken von Drittanbietern aufrufen, nicht wahr?
Jamesqf
11

Ich bin mit DeadMG einverstanden, der wichtige Unterschied ist zwischen erstklassig und "alles andere". Es gibt jedoch eine bekanntere Methode, um den Unterschied zu klassifizieren.

Erstklassige Werte sind Daten, die anderen sind Code. (Grob gesagt: Ich bin sicher, dass es Ausnahmen gibt. Aber dies ist eine wirklich gute Annäherung, die für reale Sprachen gilt.)

In einigen Sprachen können Sie Code als Daten behandeln. Dafür sind funktionale Sprachen bekannt: Mit einigen von ihnen können Sie den Code des laufenden Programms ändern (die Grundlage der genetischen Programmierung ).

Sprachen wie C und C ++ ermöglichen es Ihnen, die Adresse von Funktionen zu übernehmen: Während Sie diese nicht ändern können, können Sie Funktionen als Parameter an andere Funktionen übergeben. C ++ hat auch den syntaktischen Zucker von Funktoren . Die Idee dabei ist, ein ganzes Objekt zu erstellen, das sich auf der Oberfläche wie eine Funktion zu verhalten scheint und so herumgereicht werden kann, als ob es Daten wären. Was sonst eine niedrigere Wertklasse ist, kann als erstklassiger Wert behandelt werden.

Mathematisch denke ich, ist der beste Weg, an die AST eines Programms zu denken . Normalerweise hat jedes Token einen bestimmten Typ, der mit anderen Typen kompatibel sein kann oder nicht. Denken Sie an L-Wert, R-Wert und das andere Durcheinander von Werttypen in C ++ . Fügen Sie dann die Schlüsselwörter, Symbole, die Funktionen usw. sind, hinzu. Einige davon können je nach Sprache Werte der ersten, zweiten oder dritten Klasse sein.

Ich bin mir nicht sicher, ob es wirklich wichtig ist, die "Klasse" von Werten zu kennen, außer vielleicht in einem akademischen Umfeld. In der realen Welt ist es wichtig zu wissen, wie Sie Code weitergeben und wie Daten behandeln können: Funktoren, Lambdas / Closures, Funktionszeiger usw.


quelle
2
Ein Beispiel für einen Nicht-Code-Nicht-First-Class-Wert: Lua verfügt über eine spezielle ..."Variable", die zur Bezeichnung von Vararg-Funktionsparametern verwendet wird. Sie können es in vielen Ausdrücken verwenden, als wäre es eine Werteliste (wie z. B. print(...)oder local args = {...}), aber es gibt einige Dinge, die Sie nicht damit tun können, wie z. B. in einem Closure ( function(...) return function() return ... end end) darauf zu verweisen .
Colonel Zweiunddreißig
8

Die Denotational Semantics bietet eine mathematische Grundlage für die Beschreibung der Funktionsweise von Werten und Variablen in einer Programmiersprache. Es wurde in meinem Computer Sci Degree so gut erklärt, dass ich eine Bestnote in der Prüfung Denotational Semantics erhielt, dann das meiste vergaß und es in einem 20-jährigen Leben als Programmierer nie gebraucht habe.

Sie können sich für eine gut definierte mathematische Grundlage entscheiden oder eine informelle Terminologie wie „Status erster Klasse“ verwenden. Ich hätte viel mehr gelernt, wenn der Kurs auf Scotts Programmiersprache Pragmatik basiert hätte, aber die formale Mathematik wird für jemanden benötigt, der einen Doktortitel in Programmiersprachendesign machen wird.

Wenn Sie die Spezifikation für die meisten Programmiersprachen lesen, werden Sie feststellen, dass es Dissidenten an Denotational Semantics mangelt. In den meisten gut entwickelten Sprachen befand sich jedoch jemand im Team, der Experte für Programmiersprachendesign ist, weshalb Denotational Semantics gut verstanden wird.

Deshalb verwendet Michearl Scott eine informelle Terminologie, die in gewissem Zusammenhang mit der formalen Mathematik steht, während er das Thema so präsentiert, wie es die meisten Programmierer nutzen können. Seine Terminologie wird von anderen nicht verwendet, ist also für die Kommunikation nicht nützlich, bietet Ihnen jedoch eine gute Grundlage für die Fragen, die Sie stellen sollten, wenn Sie zum ersten Mal eine neue Programmiersprache sehen.

Beachten Sie, dass Michael L. Scott ein führender Forscher auf dem Gebiet der Informatik ist und daher die formale Mathematik verstehen und sehr gerne anwenden wird. Wie die besten Forscher ist er jedoch in der Lage, die Anwendung der Forschung auf den Rest von uns zu erklären.

Ian
quelle
Vielen Dank. Welche Bücher wurden in Ihrer Klasse verwendet? Welche Bücher empfehlen Sie jetzt? Ich lerne selbst
Tim
@ Tim, ich habe meine Klasse vor über 20 Jahren gemacht! Ich gehe davon aus, dass Michearl Scotts Buch eines der besten ist und mehr behandelt, als Sie brauchen, es sei denn, Sie werden auf PHD-Ebene recherchieren.
Ian
3

Nein, das Wort "first" in "first class" und in "first order" bedeutet verschiedene Dinge.

Aber ja, die Begriffe "erstklassig" und "erster Ordnung" hängen zusammen. In beiden geht es darum, zu klassifizieren, über welche Konzepte, die eine Sprache beschreiben kann, die Sprache auch abstrahieren kann.

Ein Konzept ist erstklassig, wenn die üblichen Abstraktionsmechanismen einer Sprache über dieses Konzept abstrahieren können.

Beispielsweise kann die Programmiersprache Java Ganzzahlen beschreiben, und alle üblichen Mechanismen zum Abstrahieren über Ganzzahlen (Akzeptieren als Methodenparameter, Zurückgeben als Funktionsergebnisse, Speichern in Datenstrukturen usw.) funktionieren für Ganzzahlen.

Ein Konzept ist erster Ordnung, wenn es nicht verwendet werden kann, um über sich selbst zu abstrahieren.

Zum Beispiel können wir in Java Methoden verwenden, um bestimmte Dinge zu abstrahieren. Methoden können jedoch nicht zum Abstrahieren von Methoden verwendet werden, da ein Methodenname nicht als Methodenparameter übergeben werden kann. Dies ist in JavaScript anders, wo Sie mithilfe der Klammernotation über den Namen eines Objekts auf eine Eigenschaft als Zeichenfolge zugreifen und über Zeichenfolgen abstrahieren können.

Ein Konzept ist zweiter Ordnung, wenn es verwendet werden kann, um Verwendungen erster Ordnung von sich selbst zu abstrahieren, nicht jedoch Verwendungen zweiter Ordnung.

In Java können Sie beispielsweise Generics verwenden, um über Typen zu abstrahieren (wie in class Foo<T> { public List<T> content; }). Sie können jedoch keine Generika verwenden, um über Generika (wie in class Bar<T> { public T<Int> content; }) zu abstrahieren . Dies ist in Scala anders.

Ein Konzept ist dritter Ordnung, wenn es verwendet werden kann, um Verwendungen erster und zweiter Ordnung von sich selbst zu abstrahieren, nicht jedoch Verwendungen zweiter Ordnung.

Und so weiter.

Schließlich ist ein Konzept höherer Ordnung, wenn es verwendet werden kann, um willkürliche Verwendungen von sich selbst zu abstrahieren.

Zusammenfassung: Wenn ein Abstraktionsmerkmal erstklassig ist, ist es auch übergeordnet. Und wenn ein Abstraktionsmerkmal erster Ordnung ist, kann es nicht erstklassig sein.

Toxaris
quelle
1
Sie können dies jedoch List<List>in Java tun . Vielleicht kannst du klarstellen, was du mit diesem Teil meinst?
Polygnome
1
Guter Punkt. Ich meine: class Foo<A> { A<Int> ... }. Das heißt, ich meine, einen generischen Typparameter als generische Klasse zu verwenden. Dann Foo<List>würde das A<Int>zu instanziieren List<Int>. In Java ist das nicht möglich. Ich werde versuchen, dies später in der Antwort zu ändern.
Toxaris
Das ist in der Tat nicht möglich.
Polygnome
Ich habe jetzt das irreführende List<List>Beispiel ersetzt. Vielen Dank für den Hinweis auf das Problem, @Polygnome.
Toxaris
@Toxaris Ich denke, das ist nur eine eigenwillige Terminologie, die Sie sich ausgedacht haben. Ein "Konzept" ist nicht erster oder zweiter Ordnung, sondern ein logischer Quantor.
Miles Rout
2

Was ist die mathematische Grundlage für Werte der ersten, zweiten und dritten Klasse in Programmiersprachen?

Keine, die mir bekannt sind.

Die Terminologie erinnert mich an die Logik erster / zweiter Ordnung, aber hängen sie zusammen?

Nicht wirklich.

Die "Klasse" eines Programmiersprachenelements ist nur eine Kurzform der Frage, welche Dinge der Benutzer meiner Sprache programmgesteuert manipulieren möchte . Beispielsweise bietet C # eine Reihe von Operationen zum Bearbeiten von Werten , eine Reihe von weniger Möglichkeiten zum Bearbeiten von Typen und keine Operationen zum Bearbeiten von Beschriftungen .

Ihre Vorstellung, dass es hier einen Zusammenhang gibt, ist jedoch nicht ganz falsch. Es gibt eine Analogie von der Logik erster Ordnung zur prozeduralen Programmierung und von der Logik höherer Ordnung zur funktionalen Programmierung. Bei der Logik erster Ordnung geht es um die logische Manipulation von Werten. In der prozeduralen Programmierung geht es um die programmatische Manipulation von Werten. Bei der Logik höherer Ordnung geht es um die logische Manipulation von Logikaussagen , bei der funktionalen Programmierung um die programmatische Manipulation von Funktionen .

Warum sind die spezifischen Fälle wichtig, während andere Fälle nicht erwähnt werden?

Sie müssten den Autor um eine endgültige Antwort bitten.

Ich würde mich nicht zu sehr auf diesen Begriff "Klasse" einlassen. Es ist keine formal definierte Sache. Es ist eine Abkürzung, mit der Sprachdesigner darüber sprechen, welche Art von Dingen programmgesteuert manipuliert werden können.

Eric Lippert
quelle
2

„Erstklassiger Wert“ ist in diesem Zusammenhang eine Standardterminologie in der Programmiersprachtheorie. Ein erstklassiger Wert kann als normaler Wert in der Sprache bearbeitet und zur Laufzeit berechnet werden. Das ist natürlich eine tautologische Definition, bis Sie eine Semantik für die Sprache definiert haben, und dann ist ein Wert das, was die Semantik als Wert definiert. Ziel des Konzepts ist es, zu identifizieren, was direkt manipuliert werden kann, anstatt nur indirekt darauf zuzugreifen.

Beispielsweise sind in fast jeder Programmiersprache Maschinen-Ganzzahlen mit einer begrenzten Größe (z. B. 8-Bit-Ganzzahlen oder 32-Bit-Ganzzahlen oder 64-Bit-Ganzzahlen usw.) erstklassige Werte. Sie können sie in Variablen speichern, übergeben und an Funktionen zurückgeben usw. In den meisten Sprachen, jedoch nicht in einfachen Sprachen wie Assembler und C, sind Zeichenfolgen erstklassige Werte - in C jedoch nicht Zeiger auf Strings bekommen. In C sind Strings und Arrays keine erstklassigen Werte: Beispielsweise können Sie einer Funktion kein Array übergeben, einer Array-Variablen kein Array zuweisen usw. In C sind Funktionen keine erstklassigen Werte entweder: Sie können keine Funktion in einer Variablen speichern, sondern nur einen Zeiger auf eine Funktion. Im Gegensatz dazu sind Zeichenfolgen und Funktionen in den meisten höheren Programmiersprachen erstklassige Werte: Sie können sie in einer Zeichenfolge usw. speichern.

Ein Beispiel für ein Konzept, das in vielen zu kompilierenden Programmiersprachen nicht erstklassig ist, sind Typen. In einer Sprache wie C oder Java leben Typen zur Kompilierungszeit, Sie können sie nicht mit Sprachkonstrukten bearbeiten. (Java hat auch ein dynamisches Typsystem, das auf Klassen basiert. Klassen sind durch Reflektion erstklassige Werte.) Im Gegensatz dazu hat eine Sprache wie Python eine typeFunktion, die einen Wert zurückgibt, der den Typ ihres Arguments darstellt.

Die Negation von „erstklassigem Wert“ in der Standardterminologie ist „kein erstklassiger Wert“. Der Begriff "Wert zweiter Klasse" wird nicht allgemein verwendet, und "Wert dritter Klasse" noch weniger. Erwarten Sie nicht, sie außerhalb dieses Buches zu sehen. Es gibt absolut keine Grundlage für die Definition von "second" als "kann als Parameter übergeben werden" und "third" als "kann nicht als Parameter übergeben werden". Es gibt keine Skala von Dingen, die sinnvoll nummeriert werden könnten. Nur sehr wenige Sprachen unterscheiden zwischen Werten, die als Parameter an Funktionen übergeben werden können, und Werten, die Variablen zugewiesen werden können. Daher ist es nicht sinnvoll, einen Namen für dieses Konzept zu definieren.

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