Welche Art von theoretischem Objekt entspricht einem C ++ - Konzept?

Mir fehlt ein Hintergrund in der theoretischen Informatik, aber ich hätte gerne verstanden, welchen theoretischen Objekten C ++ - Konzepte entsprechen. Grundsätzlich ermöglichen C ++ - Konzepte das Definieren einer Reihe von Typen, die eine Liste von Einschränkungen erfüllen. Also, aus theoretischer Sicht, welchen C ++ - Konzepten entsprechen oder entsprechen sie grob (und in diesem Fall, was sind die Unterschiede)?

pl.programming-languages type-theory algebra ct.category-theory Vincent
quelle

C ++ - Programme sind wie Turing-Maschinen. Funktionen sind wie Orakel, sie brauchen einfach mehr Zeit. C ++ ist wie viele Programmiersprachen wie der Lambda-Kalkül. Die Laufzeiterstellung von Funktionen ist ab C ++ 11 offenbar neu.

Philip White

@PhilipWhite Ich denke, Sie verpassen den Punkt der Frage. Das OP fordert keine theoretische Erklärung verschiedener Konzepte von C ++, sondern eine theoretische Erklärung einer Konstruktion von C ++, die als Konzept bezeichnet wird. Ich kenne mich in PL nicht gut genug aus, um die Frage zu beantworten, aber nach meinem Verständnis sind Konzepte eine Art Mechanismus, um den Polymorphismus einzuschränken. Ich weiß nicht, ob solche Mechanismen bereits formal untersucht wurden, aber es scheint ein vernünftiger Mechanismus zu sein, um ein Typsystem zu ergänzen.

Holf

Mein Fehler ... Ich bin dem Link gefolgt, habe ihn aber nicht zu genau gelesen. (Ich hatte nie die Notwendigkeit gefunden, Konzepte in C ++ selbst zu lernen / zu verwenden.)

Philip White

Antworten:

Aus Sicht der Programmiersprachtheorie entsprechen C ++ - Vorlagen in Kombination mit Konzepten im Gegensatz zur Perspektive der Berechenbarkeit, die andere Antworten und Kommentare angeboten haben, einem begrenzten Polymorphismus oder einer eingeschränkten Generizität . Konzepte selbst entsprechen den Einschränkungen oder Grenzen eines Typs.

Eine Vorlage ist eine Funktion auf Typebene, die nach Typ parametrisiert ist und durch ein Konzept zur Implementierung einer bestimmten Schnittstelle eingeschränkt wird. Wenn die Vorlage auf einen Typ angewendet wird, der diesem Konzept entspricht, wird ein neuer Typ erstellt.

Vorlagen + Konzepte sind analog zu Generika in Java, Scala oder Eiffel. Sie unterscheiden sich von Vorlagen in früheren C ++, weil sie das Angeben und Überprüfen von Einschränkungen für die Typparameter ermöglichen, während C ++ - Vorlagen dies nicht zuließen. Der Vorteil ist eine bessere statische Überprüfung, ob das Programm nach dem Anwenden der Vorlage gut typisiert ist.

Eine gute Referenz ist Pierce, Benjamin C. (2002). Typen und Programmiersprachen . MIT Press, Kapitel 26: Begrenzte Quantifizierung.

Dave Clarke
quelle

In C ++ - Vorlagen sind Typbeschränkungen integriert, die eine Form der strukturellen Typisierung erstellen, da ein Typ nur einige definierte Operationen enthalten muss (die in der Vorlagendefinition enthalten sind), um die Typprüfung zu erfüllen. Konzepte scheinen fast dasselbe zu tun, ermöglichen jedoch die Zuordnung von Namen zu diesen Verhaltensweisen (eine Form der nominalen Typisierung) und bieten somit eine Möglichkeit, frühere und bessere Fehlermeldungen zu erzeugen. Ich denke auch nicht, dass Konzepte Typ-zu-Typ-Funktionen sind. Die verknüpfte Beschreibung beschreibt sie als Typprädikate - oder als Typ für boolesche Funktionen.

oconnor0

@ oconnor0: Du hast recht. Konzepte + Vorlagen ergeben einen begrenzten Polymorphismus. Ich werde meine Antwort aktualisieren.

Dave Clarke

Ich bin mir nicht sicher, ob ich damit einverstanden bin. Selbst ohne Konzepte, C ++ - Vorlagen und parametrischen Polymorphismus scheinen ich nur sehr vage verwandt zu sein. Ein polytypisierter Begriff wird typgeprüft, um sicherzustellen, dass er auf allen möglichen Instanzen funktioniert. Java-Generika haben das (trotz Java bricht die Parametrizität). C ++ - Vorlagen verwenden stattdessen "SFINAE", wobei Typen erst nach der Instanziierung überprüft werden, was sie für mich weit von universellen Typen entfernt.

Chi

-3

C ++ - Konzepte werden rekursiv aufzählbaren Sprachen zugeordnet. Da das C ++ - Typsystem Turing vollständig ist, kann jede Eigenschaft von Typen, die während der Vorlageninstanziierung abgefragt werden kann (Größe, Parameter usw.), über ein beliebiges Programm ausgeführt werden, das im Typsystem simuliert wird.

Geoffrey Irving
quelle

Ich habe etwas mehr über Konzepte gelesen. (Anscheinend sind Konzepte in C ++ neu.) Natürlich akzeptiert jede C ++ - Funktion eine rekursiv aufzählbare Sprache. das ist trivial. Behaupten Sie, dass die Zuordnung von Konzepten zu neuen Sprachen eine Bijektion ist? Dies scheint offensichtlich falsch zu sein; Wenn Sie sich den Abschnitt "Konzepte" ansehen, heißt es, dass Funktionskonzepte "nur aus einer return-Anweisung bestehen dürfen, deren Argument ein Einschränkungsausdruck sein muss", während bei Variablenkonzepten "der Initialisierer ein Einschränkungsausdruck sein muss". Diese Konzepte klingen für mich also nicht vollständig.

Philip White

Konstante Ausdrücke sind Turing vollständig, also ja: Es ist eine Bijektion. Formalisierung, bei der die Kodierung von Typen explizit angegeben werden muss; Eine Aussage, die dies nicht tut, ist, dass die Menge von Konzepten, die Teilmengen der Typen void, C <void>, C <C <void>>, ... darstellen, die die ganzen Zahlen in unary darstellen, genau die RE-Sprachen sind.

Geoffrey Irving

Natürlich haben praktische Compiler Berechnungsgrenzen bei der Bewertung konstanter Ausdrücke, aber wenn diese Überlegungen berücksichtigt werden, lautet die Antwort, dass es eine endliche Menge von Konzepten gibt. Vermutlich ist das nicht die angeforderte Antwort.

Geoffrey Irving

Sie meinen Einschränkungsausdrücke. Je nach Ressource gibt es 9 Arten von Einschränkungsausdrücken, und jedes Konzept verwendet möglicherweise nur einen Einschränkungsausdruck. Die Darstellung der Ganzzahlen in Unary ist auch keine sinnvolle Bijektion zwischen Re-Sprachen und C ++ - Konzepten. Insbesondere bleibt die semantische Äquivalenz nicht erhalten.

Philip White

Nein, ich meinte konstante Ausdrücke. Gemäß dem Link in der Frage ist dies Eintrag 4 in der Liste der 9 Arten von Einschränkungen. Die meisten anderen 9 sind jedoch ebenfalls Turing vollständig: z. B. ist es Turing vollständig, um zu entscheiden, ob ein Typ in C ++ in einen anderen konvertierbar ist.

Geoffrey Irving