Semantik von Programmiersprachen

Semantik von Programmiersprachen

In der Theoretischen Informatik ist die formale Semantik (Programmiersprachen) das Studium der Bedeutung von Computerprogrammen, die als mathematische Objekte betrachtet werden.

Verbindung mit Linguistik

Wie in der Linguistik bezeichnet hier die Semantik die Verbindung zwischen einem Signifikanten, dem Programm und einem bezeichneten mathematischen Objekt, das von den Eigenschaften abhängt, die man über das Programm wissen möchte.

Die Verknüpfung zwischen der Signifikanzsprache (der Programmiersprache) und der Signifikanz (Hoare-Logik, Automaten oder andere) wird auch als semantisch bezeichnet.

Gemeinsame Semantik einer Programmiersprache

Die am häufigsten verwendete Semantik, um eine Programmiersprache zu verstehen, ist die operative Semantik, die Denotationssemantik und die axiomatische Semantik.

Operative Semantik

In der Operativen Semantik 1 ist die Bedeutung eines Programms die Reihenfolge der Zustände der Maschine, auf der das Programm läuft. Mit anderen Worten, ein Programm wird als Beschreibung eines Zustandsübergangssystems betrachtet. In dieser Semantik sind die Programme:

a = 1; b = 0

und

a = 1; 
b = 0

sind gleichwertig (haben die gleiche Bedeutung), aber das Programm:

b = 0; a = 1

ist ihnen nicht gleichwertig (selbst wenn am Ende das Ergebnis gleich ist, finden die Aktionen nicht in der gleichen Reihenfolge statt).

Wir können diese Semantik abstrahieren, indem wir nur einen Teil des Gedächtnisses der Maschine beobachten oder zum Beispiel nur die Interaktionen des Programms mit der Außenwelt (die Spur des Programms) beobachten.

Denotationssemantik

Hauptartikel: Denotational Semantik.

Initiiert von Christopher Strachey und Dana Scott ist die denotationale Semantik 2 ein Ansatz, bei dem eine mathematische Funktion namens Denotation jedem Programm zugeordnet ist und in gewisser Weise seine Wirkung, seine Bedeutung darstellt. Diese Funktion nimmt beispielsweise den Zustand des Speichers vor der Ausführung an und führt nach der Ausführung zum Zustand.

In dieser Semantik sind alle obigen Beispiele für die operationale Semantik gleichwertig, aber das Programm:

a = 1; 
b = 1;

ist ihnen nicht gleichwertig.

Es gibt verschiedene Varianten der Denotationssemantik, von denen die Denotational Continuation-Semantik eine der bekanntesten ist, die statt einer Funktion mit einem Programm, das den Speicher transformiert, eine Funktion assoziiert, die die Fortsetzung (die Zukunft) der Maschine transformiert nach der Ausführung des Programms in der Fortsetzung vor der Ausführung des Programms. Mit anderen Worten, die Denotationssemantik durch Fortführung läuft dem Programm entgegen, sie berücksichtigt, was nach einer Instruktion passiert, um daraus abzuleiten, was vor dieser Instruktion 3 geschehen muss.

Einer der wichtigen Aspekte der Denotationssemantik ist die Eigenschaft der Kompositionalität: Die Denotation eines Programms wird durch die Kombination der Denotationen seiner Bestandteile erreicht.

Axiomatische Semantik

Hauptartikel: Axiomatische Semantik.

In der axiomatischen Semantik 4 ist das Programm nicht mehr als ein Transformator von logischen Eigenschaften auf den Speicherzustand: Wenn wir vor der Ausführung p wahr haben, dann haben wir q wahr nach. Wir sind nicht länger an dem genauen Zustand der Erinnerung interessiert, solange wir wissen, ob das Eigentum hält.

Wenn die Eigenschaft, an der wir interessiert sind, ist, ob a und b nach der Ausführung des Programms positiv sind, dann sind alle vorherigen Beispiele in dem Sinne äquivalent, dass unabhängig vom Zustand der Maschine vor der Programmausführung die Eigenschaft in exit gilt. Was wir in Hoares Logik bemerken:

{\ displaystyle \ {{\ text {true}} \}} a = 1; b = 0 {\ displaystyle \ {geq 0 \ land b \ geq 0 \}}

Beziehung zwischen verschiedenen Semantiken

Diese drei Semantiken sind, wie die Beispiele nahelegen, nicht völlig unabhängig voneinander:

  • zwei syntaktisch äquivalente Programme sind operativ so;
  • zwei operativ äquivalente Programme sind denotational;
  • und zwei denotational äquivalente Programme sind axiomatisch.

Aber die Kehrwerte sind falsch.

So kann man die Semantik hierarchisieren, indem man sagt, dass eine Semantik die Abstraktion eines anderen ist, wenn und nur dann, wenn zwei äquivalente Programme in der letzten auch in der ersten sind. Diese Beziehungen wurden durch die Theorie der abstrakten Interpretation formalisiert.

Wir können diese Hierarchie (Teilaufordnung) auf die semantischen Äquivalenzen vervollständigen, indem wir die Identität oben (zwei Programme sind identisch, wenn sie die gleiche Folge von Zeichen sind) und unten die Abstraktion am gröbsten platzieren Chaos, wo jedes Programm zu jedem anderen Programm gleichwertig ist.

Leave a Comment