Was ist eine Art in der Semantik der Programmiersprache?

9

In Kapitel 1 der praktischen Grundlagen für Programmiersprachen erwähnt der Autor, dass abstrakte Syntaxbäume mit Sortierungen verknüpft sind .

Intuitiv sind Sortierungen wie Typen, aber ich würde gerne wissen, ob sie eine genaue Definition haben. Ich würde mich freuen, wenn auch einige Referenzen zur Verfügung gestellt werden.

rslima
quelle

Antworten:

4

Es hängt davon ab, welche Semantik wir für Typen und Sortierungen verwenden würden. - Wie kurz - wenig informell - Definitionen auch sein mögen - Sortierungen sind Klassen von ASTs und Typen sind Klassen von Werten .

Nummer47
quelle
4

Es gibt tatsächlich eine große Ähnlichkeit zwischen Sortierungen für die Abstact-Syntax und Typen, wie sie normalerweise verstanden werden. Aber Sortierungen sind ein formales syntaktisches Konzept , und AS-Bäume sind auch Syntax, während Typen ein semantisches Konzept sind .

Die Terminologie stammt aus dem Begriff Algebren (auch freie Algebren genannt ) und der universellen Algebra . Dies sind im Wesentlichen syntaktische Theorien algebraischer Strukturen, die unabhängig von Interpretationen analysiert werden. Sie wurden in der ersten Hälfte des 20. Jahrhunderts entwickelt.

Ein Begriff kann als Baum angesehen werden, bei dem die Knoten von einer endlichen Menge von Operatoren beschriftet werden, wobei jeder Operator eine feste Arität hat, die die Anzahl der Töchter im Baum angibt. Arity 0 ist für Blätter. In mehrfach sortierten Algebren wird dies mit Sortierungen verfeinert, sodass jeder Operator zu einer Sortierung gehört, und Aritäten werden durch eine geordnete Liste von Sortierungen ersetzt, die für jede Tochter die Sortierung ihres Hauptoperators festlegt. Die Art eines Operators wird zusammen mit der Liste der Sorten seiner Tochter als Signatur des Operators bezeichnet.

In universellen Algebren wird dies weiter verfeinert, indem gleich definierte Äquivalenzbeziehungen zwischen Begriffen eingeführt werden.

Obwohl es ein wenig verblasst zu sein scheint, waren diese Konzepte im späten 20. Jahrhundert sehr populär und wurden in der Informatik vielfach studiert, da abstrakte Algebren dann als Grundlage für abstrakte Datentypen angesehen wurden, die teilweise Vorläufer dessen sind, was ist nos Klassen in der objektorientierten Programmierung.

Universelle Algebren beziehen sich auf die Entwicklung der Kategorietheorie, die auch in der gegenwärtigen Vision von Typen und Programmiersprachen von grundlegender Bedeutung ist.

Algebren sind syntaktische Objekte und sollen mit einer Interpretation in einigen semantischen Domänen verwendet werden, die Typen entsprechen. Eine Interpretation ist ein Homomorphismus, der Sortierungen in Wertebereiche (Typen) und Operatoren in Funktionen zwischen diesen Bereichen abbildet , so dass Signaturen und Gleichungen auch im Fall einer Gleichungsalgebra respektiert werden. Auf diese Weise können Sie die Ergebnisse der Gruppentheorie auf jede Domäne mit einer Operation anwenden, die die Definition einer Gruppe berücksichtigt.

Diese Organisation wurde von frühen Forschern in Programmiersprachen als sehr praktisch angesehen, insbesondere von Forschern, die sich mit der Formalisierung von Programmiersprachen befassen. Es hatte den Vorteil, Syntax und Semantik zu isolieren und mathematisch gut verstanden zu werden.

Ein weiterer Grund für die Übernahme war die Entwicklung eines Tools zur Manipulation von Programmen, entweder in Entwicklungsumgebungen oder in formalen Systemen, um die Eigenschaften von Programmen zu beweisen (was sich als immer mehr Doppelprobleme herausstellte).

Dies führte zur Entstehung des Konzepts des abstrakten Syntaxbaums (AST) für Programmiersprachen, bei denen es sich im Wesentlichen um Begriffe einer mehrsortierten Algebra handelt (die manchmal in einigen Systemen durch die Verwendung der Sortiervereinigung verfeinert wird). Der AST ist die Referenzsyntax für eine Sprache, aus der die Semantik durch Homomorphismus wie in der Denotationssemantik definiert werden kann.

Dies ist nicht nur praktisch, um die Semantik von Sprachen zu studieren, sondern Bäume sind auch besser strukturiert als Zeichenfolgen und somit eine bessere Grundlage für die Entwicklung von Programmierwerkzeugen und Programmierumgebungen.

Es ermöglicht das Isolieren von Parsing, was traditionell ein chaotischer Teil war, da die Einschränkungen der Parsing-Technologie die Verwendung verzerrter Grammatiken erzwangen. Präsentationsprobleme werden ebenfalls berücksichtigt.

Es ermöglicht mehrere konkrete (Zeichenfolgen- oder Grafik-) Darstellungen von Programmen, was manchmal praktisch sein kann (es gibt keinen Grund, warum die Verwendung von Interpunktion anstelle von Tabulatoren oder umgekehrt in der Programmsyntax den Personen aufgezwungen werden sollte).

Es macht es einfach, viele Interpretationen von Programmen und Arten zu definieren , um Programmeigenschaften mit abstrakten Interpretationen zu analysieren.

Es ist praktisch, um (halb-) automatisierte Programmmanipulationswerkzeuge zu schreiben, beispielsweise für automatische Programmtransformationen oder Übersetzungen zwischen Sprachen.

In der Praxis können die Dinge manchmal etwas komplizierter sein, da einige Formen der abstrakten Syntax es einigen Operatoren ermöglichen, Bäume (Ausdrücke) zu erstellen, die zu mehreren Sorten gehören (eine informelle Sichtweise). Beispielsweise könnte es eine Sortierung für syntaktische Konstrukte geben, die Variablen (zuweisbare Entitäten) darstellen, und eine andere für Ausdrücke. Aber jede Variable kann als Ausdruck verwendet werden, wobei das Gegenteil falsch ist.

Frühe Veröffentlichungen zu Programmiersprachen stammen aus der Mitte der siebziger Jahre. Die damalige Konzeptualisierung war für die Produktion syntaxbewusster Programmierumgebungen gedacht (das Wort "gerichtet" wurde dann verwendet)). Suchen Sie nach Mentor und Centaur in Europa und nach Cornell Program Synthesizer in den USA. Sie waren die ersten beiden Systeme, die solche Konzepte tatsächlich auf praktische Weise verwendeten. Viele andere wurden später entwickelt.

Die abstrakte Syntax geht jedoch diesen Systemen voraus. Die Lisp-Sprache (1958) hatte eine abstrakte Syntax, was nicht verwunderlich ist, da sie von einem Logiker entwickelt wurde und zum Zwecke der Erstellung von Programmen, die Programme manipulieren (siehe auch ML und LCF ... die später kamen). Aber Lisp war nicht sortiert: Alles war syntaktisch eine Liste und eine verfeinerte Struktur war im Wesentlichen semantikabhängig. Dies führte einige Leute zu der falschen Annahme, dass Lisp keine Syntax hatte.

babou
quelle
Würden Sie sagen, dass es zwei verschiedene Hierarchien gibt, eine im Syntaxland und eine im Semantikland? In der Syntax haben wir wie Sie ASTs und Sortierungen und Klassen von Sortierungen. In der Semantik haben wir Werte, Typen, Arten ... usw. Gibt es keine Sprachen, die beide in einer Entwicklungsumgebung wie Twelf oder Coq vereinen?
CMCDragonkai
@CMCDragonkai Ich würde (abgesehen von möglichen Fehlern) genau das sagen, was ich gesagt habe. Ich würde diese Hierarchien nicht nennen, sondern Bereiche des (Meta-) Diskurses. Die Syntax-Semantik-Trennung unterscheidet, worüber wir sprechen und wie wir es tun, was eine Repräsentation erfordert. Sie sollten nicht Syntax und Semantik derselben Sprache mischen wollen, aber die Syntax einer Sprache kann Gegenstand eines Diskurses sein und gehört daher zur Semantik einer anderen Sprache. In diesem Sinne könnten Sie eine Vereinigung sehen, die mit Vorsicht behandelt werden muss. Die Syntax wird immer endlich generiert, während die Semantik keine solche Einschränkung aufweist.
Babou
2

In Kapitel 4 wird angezeigt, dass Sortierungen für die Syntax und Typen für die Semantik gelten.

Das Beispielsyntaxdiagramm auf Seite 40 behandelt die Sortierungen in der Sprache L {num str}. Anscheinend sind Sortierungen Kategorien in der Syntax der Sprache.

Insbesondere hat "plus" eine Sortierung, die die syntaktische Kategorie seines Ergebnisses ist. Die Art des Operators "plus" heißt "Exp". Dies stellt die Tatsache dar, dass syntaktisch ein Aufruf des Operators "plus" ein Ausdruck ist. Ein Aufruf des Operators "plus" kann eine Position in einem abstrakten Syntaxbaum füllen, an der ein Ausdruck zulässig ist. Das ist, was für eine Konstruktion ein "Plus" ist. So passt es in die Struktur eines Textes, der ein Programm darstellt.

Das Typsystem auf Seite 41 behandelt die Typen in der Sprache L {num str}. Der Typ des Operators "plus" ist "num", vorausgesetzt, seine Operanden haben den Typ "num". Dieses Urteil ist eine teilweise Beschreibung der Semantik des Operators "plus". Das heißt, ein Teil der Bedeutung des Operators "plus" ist das Kombinieren von zwei Zahlen, um eine Zahl zu erzeugen. Diese Bedeutung unterscheidet "Plus" von anderen Ausdrücken.

Darüber hinaus gibt es eine Sortierung mit dem Namen "Typ", die die beiden Typen "num" und "str" ​​enthält.

Minopret
quelle
1
Nun, er verwendet es in diesem Konzept, aber er definiert es nicht klar. Ich fand den Begriff "Vielsortierte Logik", der mir scheint, dass Sortierungen und Typen wirklich geschlossene verwandte Konzepte sind. Ich wollte nur eine klare Definition für beide wissen.
Rslima
Es hat etwas mit "reinen Typsystemen" zu tun. Ich vermute, wir könnten die Darstellung in " Lambda Calculi with Types " als konventionell betrachten. Aber es ist nicht prägnant. Ich habe noch keine Referenz gefunden, die klare, präzise Definitionen von Begriff, Typ, Art und Sortierung enthält.
Minopret
Was ist mit Produktionsköpfen in einem Parser? Oftmals klassifizieren Sie Grammatiken unter ähnlichen Namen wie Ausdruck oder Typ.
CMCDragonkai
1

Zu Beginn von Kapitel 1 gibt Harper einen Hinweis darauf, was er mit dem Wort sort meint :

Die Syntax einer Sprache gibt an, wie verschiedene Arten von Phrasen (Ausdrücke, Befehle, Deklarationen usw.) zu Programmen kombiniert werden können.

Er definiert die Wortphrase als einen abstrakten Syntaxbaum, den er dann diskutiert.

jcora
quelle
Es scheint mir, als ob "sort" hier mit seiner üblichen englischen Bedeutung verwendet wurde, synonym zu "Arten".
Raphael
@ Raphael Ja, aber es scheint, dass diese Bedeutung mit der letztgenannten formalen Verwendung übereinstimmt, würden Sie nicht zustimmen?
JCora
Nicht ganz. Der Ausdruck "diese Art von X" kann häufig im Buch vorkommen; Dieser Satz signalisiert in keiner Weise, dass etwas definiert wird. (Auch diese Passage entspricht nicht meinem Verständnis des Begriffs "sortieren").
Raphael
@Raphael OK, bitte erklären Sie, wie inkonsistent diese bestimmte Verwendung ist, es würde mich sicherlich informieren, denn so verstehe ich es derzeit.
JCora
Der Begriff "Sortierung", den ich kenne, ist mit einzelnen Knoten des AST verbunden, nicht mit einem ganzen Baum (was Sie in Ihrer Quelle als "Phrase" bezeichnen).
Raphael