Geometrische Gruppentheorie XX

Die Symmetriegruppe {S_{4}} des Tetraeders, die Tetraedergruppe, hat die Ordnung 24. Mehr kann es nicht geben, denn es gibt nur 24=4{*}3{*}2{*}1 Permutationen der Zahlen 1, 2, 3, 4. Alle Permutationen von 4 Zahlen bilden eine Gruppe, die symmetrische Gruppe {S_{4}} und sie ist isomorph zur Tetraedergruppe.

Die Tetraedergruppe wird erzeugt von den Elementen S=\{(2,4), (1,2), (1,3), (1,4), (2,3), (3,4)\}.

Die reellen Zahlen mit der gewöhnlichen Addition bilden eine nicht endlich erzeugte Gruppe.

Die Isometriegruppe {\mathcal{E}} der euklidischen Ebene wird von allen Spiegelungen erzeugt.

{\mathcal{E}} ist natürlich nicht endlich erzeugt. Sogar die Symmetriegruppe des Kreises ist nicht endlich erzeugt und die Symmetriegruppe der euklidischen Ebene enthält Spiegelungen eines Kreises.

.

[1] Rosebrock Stephan: Geometrische Gruppentheorie

Advertisements

Kapitel 13 von Crenshaw’s „Let’s build a compiler!“ Teil 5

Was ist falsch?

An diesem Punkt könnte man glauben: Es muss hier mehr zu tun geben, als nur ein paar CPU Befehle einzubauen, um Parameter übergeben zu können.

Richtig! Der Code den wir hier erzeugen lässt viele Dinge offen.

Das Wichtigste, er ist falsch! Sehen wir uns den Code für einen Prozeduraufruf genauer an. Der Aufrufer legt die Parameter auf dem Stapel ab und ruft die Prozedur auf. Die Prozedur VERWENDET die Information, lässt aber den Stapelzeiger unverändert. Das heißt die Parameter liegen auch nach der Rückkehr zum Aufrufer auf dem Stapel. Das heißt, JEMAND muss den Stapel bereinigen oder wir bekommen sehr rasch Probleme!

Glücklicherweise kann das sehr leicht erledigt werden. Wir müssen nur, wen alles erledigt ist, den Stapelzeiger ändern.

Soll das im aufrufenden oder im aufgerufenen Programm passieren? Manche Programmierer lassen das vom aufgerufenen Programm erledigen, da hier für den Aufruf weniger Code erzeugt werden muss und die Prozedur weiß wieviele Parameter an sie übergeben wurden. Aber dann muss man etwas mit der Rücksprungadresse machen sonst geht sie verloren.

Wir überlassen dem aufrufenden Programm die Arbeit und die aufgerufene Prozedur führt nur ein Return aus. Das aufrufende Programm MUSS sich jetzt merken wieviele Parameter es übergeben hat. Wir werden einfach die Prozedur ParamList in eine Funktion umwandeln und die Anzahl der auf den Stapel gelegten Bytes zurückgeben.

{ Verarbeite die Parameterliste für einen Prozeduraufruf }

function ParamList: integer;
var N: integer;
begin
  N := 0;
  Match('(');
  if Look <> ')' then
  begin
    Param;
    inc(N);
    while Look = ',' do
    begin
      Match(',');
      Param;
      inc(N);
    end;
  end;
  Match(')');
  ParamList := 2*N;
end;

Die Prozedur CallProc verwendet das, um den Stapel zu bereinigen:

{ Verarbeite einen Prozeduraufruf }

procedure CallProc(Name: char);
var N: integer;
begin
  N := ParamList;
  Call(Name);
  CleanStack(N);
end;

Wir benötigen eine weitere Codeerzeugungsprozedur:

{ Passe den Stapelzeiger an }

procedure CleanStack(N: integer);
begin
  if N > 0 then
  begin
    Emit('ADD #');
    WriteLn(N,',SP');
  end;
end;

Der Stapel wird nun richtig behandelt.

Das nächste Problem hat mit unserer relativen Adressierung des Stapelzeigers zu tun. Sie funktioniert in unserem einfachen Beispiel sehr gut, weil hier sonst niemand mit dem Stapel arbeitet. Sehen wir uns ein anderes, einfaches Beispiel an:

PROCEDURE FOO(A,B)
BEGIN
  A = A + B
END

Der erzeugte Code des einfachen Parsers sieht so aus:

FOO:
  MOVE 6(SP),D0   ; Hole A
  MOVE D0,-(SP)   ; Lade es
  MOVE 4(SP),D0   ; Hole B
  ADD (SP)+,D0    ; Addiere A
  MOVE D0,6(SP)   ; Speichere A
  RTS

Das ist falsch. Wenn wir den ersten Parameter auf den Stapel laden ist der Offset für die zwei formalen Parameter nicht mehr 4 und 6 sondern 6 und 8. Das zweite Hole wird daher wieder A und nicht B laden.

Das ist nicht das Ende der Welt. Wir müssen nur bei jedem Laden den Offset mitführen, tatsächlich machen wir auch das, wenn die CPU nicht andere Methoden unterstützt.

Glücklicherweise bietet der 68000 eine solche Unterstützung. Die CPU wird von vielen Compilern benutzt und Motorola hat dem 68000 eine Unterstützung spendiert.

Das Problem ist, dass der Stapelzeiger während der Prgrammausführung rauf und runter wandert und damit seine Verwendung als Referenz auf die Parameter zu einer unschönen Sache wird. Als Lösung wird ein ANDERES Register verwendet. Dieses Register wird üblicherweise gleich dem Originalen Stapelzeiger gesetzt und Rahmenzeiger (frame pointer) genannt.

Mit der 68000 Instruktion LINK wird der Rahmenzeiger deklariert und gleich dem Stapelzeiger in einem Schritt gesetzt. Es wird dabei sogar noch mehr gemacht. Dieses Register könnte ja in der aufrufenden Prozedur eine andere Verwendung haben. LINK lädt auch den aktuellen Wert des Registers auf den Stapel. Es kann auch einen Wert zum Stapelzeiger addieren um Platz für die lokalen Variablen zu machen.

Das Gegenstück zu LINK ist UNLK, welches einfach den Stapelzeiger wieder herstellt und in das Register den alten Wert verschiebt.

Mit diesen zwei Befehlen wird aus unserem obigen Beispiel:

FOO:
  LINK A6,#0
  MOVE 10(A6),D0  ; Hole A
  MOVE D0,-(SP)   ; Lade A
  MOVE 8(A6),D0   ; Hole B
  ADD (SP)+,D0    ; Addiere A
  MOVE D0,10(A6)  ; Speichere A
  UNLK A6
  RTS

Unseren Compiler auszubessern ist viel einfacher als es zu erklären. Wir müssen nur die Codeerzeugung in DoProc verändern. Wir erstellen dazu eine neue Prozedur, die ähnlich den Prolog und Epilog Prozeduren ist , die in DoMain aufgerufen werden:

{ Schreibe den Prolog für eine Prozedur }

procedure ProcProlog(N: char);
begin
  PostLabel(N);
  EmitLn('LINK A6,#0');
end;

{ Schreibe den Epilog für eine Prozedur }

procedure ProcEpilog;
begin
  EmitLn('UNLK A6');
  EmitLn('RTS');
end;

Die Prozedur DoProc ruft diese beiden Routinen auf:

{ Parse und übersetze eine Prozedurdeklaration }

procedure DoProc;
var N: char;
begin
  Match('p');
  N := GetName;
  FormalList;
  Fin;
  if InTable(N) then
    Duplicate(N);
  ST[N] := 'p';
  ProcProlog(N);
  BeginBlock;
  ProcEpilog;
  ClearParams;
end;

Zum Schluss müssen wir noch die Referenz zum Stapelzeiger in den Prozeduren LoadParam und StoreParam anpassen:

{ Lade einen Parameter in das Hauptregister }

procedure LoadParam(N: integer);
var Offset: integer;
begin
  Offset := 8 + 2 * (NumParams - N);
  Emit('MOVE ');
  WriteLn(Offset,'(A6),D0');
end;

{ Speichere einen Parameter vom Hauptregister }

procedure StoreParam(N: integer);
var Offset: integer;
begin
  Offset := 8 + 2 * (NumParams - N);
  Emit('MOVE D0,');
  WriteLn(Offset,'(A6)');
end;

(Die Offsetberechnung hat sich geändert um das Laden von A6 zu erlauben).

Das war’s. Testen wir es.

Wir erzeugen hier gefälligen Code für Prozeduren und Prozeduraufrufe. Wir haben (jetzt) keine lokalen Variablen und die Schachtelung von Prozeduren ist nicht erlaubt.

Es bleibt da noch ein kleines Problem:

WIR KÖNNEN KEINE RESULTATE AN DEN AUFRUFER ZURÜCKGEBEN!

Das ist natürlich keine Beschränkung die sich aus unserem erzeugten Code ergibt. Es hat mit der Wertübergabe der Parameter zu tun. Wir können formale Parameter innerhalb der Prozedur beliebig verwenden. Wir können sie mit Werten belegen oder als Schleifenzähler verwenden usw. Also, unser Code erfüllt genau unsere Erwartungen. Um dieses Problem zu lösen müssen wir einen alternativen Ansatz für die Parameterübergabe verwenden.

Referenzübergabe

Das ist nun einfach, da wir den Mechanismus schon entwickelt haben. Es sind nur wenige Änderungen in der Codeerzeugung notwendig. Statt den Wert auf den Stapel zu laden, laden wir die Adresse. Der 68000 hat einen Befehl PEA, der das für uns erledigt.

Wir erstellen eine neue Version unseres Testprogrammes. Bevor wir beginnen,
>\textcompwordmark{}>\textcompwordmark{}>\textcompwordmark{}>\textcompwordmark{}> MACHEN WIR EINE KOPIE <\textcompwordmark{}<\textcompwordmark{}<\textcompwordmark{}<\textcompwordmark{}<
von unserem momentanen Programm, da wir es später wieder benötigen.

Wie soll der erzeugte Code für diesen Fall aussehen? Bei demselben Beispiel wie zuvor müssen wir den Aufruf

FOO(X,Y)

so übersetzen:

PEA X(PC)  ; Lade die Adresse von X
PEA Y(PC)  ; Lade die Adresse von Y
BSR FOO    ; Aufruf von FOO

Eine kleine Änderung von Param:

{ Verarbeite einen aktuellen Parameter }

procedure Param;
begin
  EmitLn('PEA '+GetName+'(PC)');
end;

(Bei der Referenzübergabe können keine Ausdrücke vorkommen, daher liest Param den Namen direkt).

Auf der anderen Seite ist die Referenzübergabe indirekt:

FOO:
  LINK A6,#0
  MOVE.L 12(A6),A0  ; Hole Adresse von A
  MOVE (A0),D0      ; Hole A
  MOVE D0,-(SP)     ; Lade es
  MOVE.L 8(A6),A0   ; Hole Adresse von B
  MOVE (A0),D0      ; Hole B
  ADD (SP)+,D0      ; Addiere A
  MOVE.L 12(A6),A0  ; Hole Addresse von A
  MOVE D0,(A0)      ; Speichere A
  UNLK A6
  RTS

Wir können als das durch eine Änderung von LoadParam und StoreParam erledigen:

{ Lade einen Parameter in das Hauptregister }

procedure LoadParam(N: integer);
var Offset: integer;
begin
  Offset := 8+4*(NumParams-N);
  Emit('MOVE.L ');
  WriteLn(Offset,'(A6),A0');
  EmitLn('MOVE (A0),D0');
end;

{ Speichere einen Parameter von Hauptregister }

procedure StoreParam(N: integer);
var Offset: integer;
begin
  Offset := 8+4*(NumParams-N);
  Emit('MOVE.L ');
  WriteLn(Offset,'(A6),A0');
  EmitLn('MOVE D0,(A0)');
end;

Um richtig zu zählen müssen wir eine Zeile in ParamList ändern:

ParamList := 4 * N;

Das war’s. Der erzeugte Code ist nicht optimal, weil wir das Adressregister immer wenn ein Parameter gebraucht wird aktualisieren. Aber es ist konsistent mit unserem KISS Ansatz: Wir erzeugen Code der funktioniert.

Wir merken an, dass hier eine weitere Stelle zur Oprimierung des Codes ist und machen weiter.

Wir haben nun die Wertübergabe und die Referenzübergabe gelernt. Wir wollen natürlich mit BEIDEN Möglichkeiten gleichzeitig arbeiten können. Momentan geht das noch nicht, weil wir über Typen noch nicht gesprochen haben.

Müssen wir uns auf eine Möglichkeit beschränken so wählen wir, wie im guten alten FORTRAN, die Referenzübergabe, da wir nur hier Rückgabewerte verwalten können.

Das ist der Unterschied zwischen TINY und KISS. In der nächsten Version von TINY verwenden wir nur die Referenzübergabe. In KISS stehen uns dann beide Möglichkeiten zur Verfügung.

Geometrische Gruppentheorie XIX

Die Ordnung eines Elements

Die Ordnung oder Periode eines Elements {g} in einer Gruppe ist die kleinste Zahl {n\in\mathbb{N},} so dass {g^{n}=e} gilt. Man schreibt auch {\vert g\vert=n.}

Jede Spiegelung hat die Ordnung 2. Elemente der Ordnung 2 heißen Involutionen.

Die Identität der Gruppe ist das einzige Element mit der Ordnung 1.

In {\mathbb{Z}} haben alle Elemente, außer dem neutralen, die Ordnung unendlich. Die Ordnung einer Drehung um 360/n ist {n.}

Eine Translation hat immer die Ordnung unendlich. Führt man eine Verschiebung der Ebene mehrfach hintereinander aus, so kann dabei nie die Identität entstehen.

Sind zwei Gruppen isomorph, so haben sie dieselbe Anzahl Elemente. Die Gruppen {(\mathbb{Z}_{4},+_{4})} und {(D_{2},\circ)} haben jede 4 Elemente. Sind sie isomorph? In {\mathbb{Z}_{4}}hat die 1 die Ordnung 4. In der Gruppe {D_{2}}gibt es jedoch kein Element der Ordnung 4. {D_{2}} und {\mathbb{Z}_{4}} sind nicht isomorph.

Die Gruppe {D_{2}=\{id,d,s_{a},s_{b}\}} heißt Kleinsche Vierergruppe.

Ist die Ordnung eines Elements {g\in G} endlich und gleich der Ordnung der Gruppe {G,} so ist G zyklisch und wird von {g} erzeugt.

.

[1] Rosebrock Stephan: Geometrische Gruppentheorie

Kapitel 13 von Crenshaw’s „Let’s build a compiler!“ Teil 4

Die Semantik der Parameter

Wir haben die SYNTAX der Parameterübergabe betrachtet und einen Parsermechanismus programmiert der die Übergabe abarbeiten kann. Nun müssen wir uns die SEMANTIK ansehen, d.h. welche Aktionen müssen durchgeführt werden wenn Parameter erkannt werden.

Es gibt mehr als einen Weg um die Parameter zu übergeben. Die Art der Übergabe hat einen entscheidenden Einfluss auf den Charakter der Programmiersprache. Es ist wichtig sich die Alternativen etwas anzusehen um dann die Entscheidung zu treffen.

Die Hauptarten der Parameterübergabe sind:

  • Wertübergabe
  • Referenzübergabe (Adresse)

Die Unterschiede sieht man am besten im Lichte der Vergangenheit.

Die alten FORTAN Compiler übergaben Referenzen. Mit anderen Worten, es wurde die Adresse des Parameters übergeben. Das Unterprogramm konnte die Parameter lesen und schreiben genauso wie eine globale Variable. Das ist sehr effizient und ziemlich einfach da derselbe Mechanismus, mit einer Ausnahme (die wir später diskutieren), in allen Fällen zur Anwendung kommt.

Es gibt damit aber auch Probleme. Viele Programmierer meinen, dass damit die Verbindung des aufgerufenen Programmes mit dem aufrufenden Programm zu eng ist. Übergeben wir zum Beispiel einen Zähler und verwenden ihn im Unterprogramm weiter so ist Vorsicht geboten. Um den Zähler nicht im aufrufenden Programm zu verändern, müssen wir in dem Unterprogramm eine Kopie des Zählers erstellen und nur mit dieser arbeiten. Einige FORTRAN Programmierer haben immer von ALLEN, mit Ausnahme der Rückgabewerte, Parameter eine Kopie gemacht. Dieses Kopieren vermindert natürlich stark die Effizienz dieses Ansatzes.

Es gibt da noch ein Problem, das zwar nicht wirklich ein Fehler der “Referenzübergabe“ ist, aber negative Auswirkungen auf viele Implementationsentscheidungen hat.

Angenommen wir haben das Unterprogramm:

SUBROUTINE FOO(X,Y,N)

wobei N eine Eingabezähler oder ein Statusanzeiger ist. Oft wollen wir in der Lage sein ein Literal oder einen Ausdruck statt der Variable übergeben zu können. So wie:

CALL FOO(A,B,J+1)

Der dritte Parameter ist hier keine Variable und hat daher auch keine Adresse. Die ersten FORTRAN Compiler haben daher solche Ausdrücke nicht erlaubt und man musste daher:

K = J + 1
CALL FOO(A,B,K)

schreiben.

Wieder ist hier eine Kopie notwendig und die muss der Programmierer machen. Nicht gut!

Spätere FORTRAN Implementationen haben dann Ausdrücke als Parameter erlaubt. Sie haben einer compilergenerierten Variablen den Wert des Ausdruckes zugewiesen und die Adresse der Variablen als Parameter übergeben.

So weit so gut. Wird im Unterprogramm der Variablen ein neuer Wert zugewiesen, kein Problem. Beim nächsten Aufruf wird sie sowieso neu berechnet.

Das Problem entsteht wenn jemand die Dinge effizienter machen will. Der allgemeinste “Ausdruck“ scheint ein einziger Integerwert zu sein, wie in:

CALL FOO(A,B,4)

Statt den Ausdruck immer wieder zu berechnen und in einer temporären Variablen zu speichern, wird hier gleich der Wert als Integer übergeben. Da wir immer nur Adressen übergeben scheint es sinnvoll zu sein die Adresse des Literals, 4 in unserem Beispiel, zu übergeben.

Die meisten Compiler erkennen alle Literale und speichern sie in einem eigenen “Literal-Pool“. Daher können wir nur einen Wert für jedes Literal speichern. Diese Kombination der Designentscheidungen: Übergabe von Ausdrücken, Optimierung der Literale als speziellen Fall und die Benutzung eines Literal-Pools führt zu einem Desaster.

Um das zu erkennen rufen wir das Unterprogramm FOO wie in unserem obigen Beispiel auf. Wir übergeben also das Literal 4. Tatsächlich wir die Adresse des Literals, welches im Literal-Pool gespeichert ist, übergeben. Diese Adresse korrespondiert mit dem formalen Parameter K in dem Unterprogramm.

Angenommen in dem Unterprogramm FOO wird, ohne dass es dem Programmierer bewußt ist, K auf -7 GEÄNDERT. Plötzlich hat das Literal 4 den Wert -7 und in jedem Unterprogramm wird statt 4 eine Adresse übergeben die auf den Wert -7 zeigt. Das kann zu Fehlern führen die nur sehr schwer zu finden sind. Das gibt dem Konzept der Referenzübergabe einen schlechten Beigeschmack, obwohl eigentlich eine Kombination von Designentscheidungen zu diesen Problemen führt.

Trotzdem hat der FORTRAN Ansatz Vorteile. Wir müssen nicht mehrere Übergabemechanismen programmieren. Dasselbe Schema, Übergabe der Adresse, funktioniert in ALLEN Fällen, auch mit Feldern. Die Größe des Compilers wird kleiner.

In den modernen Programmiersprachen wie C, Pascal, Ada oder Modula2 werden Skalare allgemein als Wert übergeben.

D. h. der Wert des Skalars wird in einen anderen Wert, der nur für diesen Aufruf benutzt wird, kopiert und übergeben. Da dieser Wert eine Kopie ist kann hier nichts passieren. Der Wert im aufrufenden Programm wird nicht geändert.

Das sieht auf den ersten Blick etwas ineffizient aus. Aber es muss auf jeden Fall der Wert oder die Adresse zum Übergeben gesucht werden. In dem Unterprogramm ist der Gebrauch von der “Wertübergabe“ definitiv effizienter, weil hier eine Abstraktionsebene wegfällt. Wir haben gesehen, dass in FORTRAN auch öfters Kopien notwendig sind. Insgesamt ist die Wertübergabe besser.

Es gibt da eine kleine Ausnahme: werden alle Parameter mit ihrem Wert übergeben, kann das Unterprogramm keine Rückgabewerte abliefern. Der Parameter wird im aufrufenden Programm NICHT geändert. Natürlich erfüllt das nicht seinen Zweck.

Es gibt zwei Antworten zu dieser Frage und sie sind äquivalent. In Pascal hat Wirth den VAR Parameter vorgesehen. Bei diesen Parameter geschieht eine Refernzübergabe, wie im guten alten Fortran. Das Problem mit den Literalen umgeht Wirth in dem er für VAR Parameter nur Variablen zulässt.

In C wird dasselbe explizit gemacht. In C werden ALLE Parameter als Werte übergeben. Eine Art von Parameter die C unterstützt ist der Zeiger. Der Wert eines Zeigers, der übergeben wird, ist die Adresse einer Variablen. Man kann zwar den Wert der Variable ändern aber nicht den Zeiger selbst. Um einen Zeiger zu ändern muss ein Zeiger auf einen Zeiger übergeben werden.

Wir werden mit beiden Ansätzen, Wertübergabe und Referenzübergabe, experimentieren.

Wertübergabe

Zuerst versuchen wir ganz einfache Dinge. Wir beginnen mit dem Ansatz der Wertübergabe. Betrachten wir den Prozeduraufruf:

FOO(X,Y)

Es gibt eigentlich nur eine Art die Werte zu übergeben, nämlich mit dem CPU-Stapel. Der generierte Code könnte folgendermaßen aussehen:

MOVE X(PC),-(SP)  ; Lade X
MOVE Y(PC),-(SP)  ; Lade Y
BSR FOO           ; Rufe FOO

Das scheint nicht zu schwierig zu sein!

Wird BSR ausgeführt lädt die CPU die Rücksprungadresse auf den Stapel und springt zu FOO. An diesem Punkt wird der Stapel so aussehen:

    .
    .
    Wert von X (2 Bytes)
    Wert von Y (2 Bytes)
SP->Rücksprungadresse (4 Bytes)

Die Parameterwerte befinden sich also, bezüglich zum Stapelzeiger, an genau definierten Orten. In diesem Beispiel sind die Adressen:

X: 6(SP)
Y: 4(SP)

Die aufgerufene Prozedur könnte so aussehen:

PROCEDURE FOO(A,B)
BEGIN
  A = B
END

(Die Namen der formalen Parameter sind willkürlich … nur ihre Position zählt.)

Der erzeugte Code könnte so aussehen:

FOO: MOVE 4(SP),D0
     MOVE D0,6(SP)
     RTS

Da nur die Reihenfolge der formalen Parameter zählt, müssen wir ihre Position in der Parameterliste kennen. Daher müssen wir in der Symboltabelle Änderungen vornehmen. Tatsächlich ist es, in unserem Einzeichen-Fall, das Beste eine neue Symboltabelle für die formalen Parameter zu schaffen.

Deklarieren wir eine neue Tabelle:

var Params: Array['A'..'Z'] of integer;

Wir müssen auch abspeichern wieviele Parameter eine gegebene Prozedur hat.

var NumParams: integer;

Wir müssen sie auch initialisieren. Da die formalen Parameter für jede Prozedur unterschiedlich sein können, müssen sie wir für jede Prozedur neu initialisieren:

{ Initialisiere die Parametertabelle mit Null }

procedure ClearParams;
var i: char;
begin
  for i := 'A' to 'Z' do
    Params[i] := 0;
  NumParams := 0;
end;

Wir geben alle Aufrufe dieser Prozedur in das Init und DoProc:

{ Initialisierung }

procedure Init;
var i: char;
begin
  GetChar;
  SkipWhite;
  for i := 'A' to 'Z' do
    ST[i] := ' ';
  ClearParams;
end;

{ Parse und übersetze eine Prozedurdeklaration }

procedure DoProc;
var N: char;
begin
  Match('p');
  N := GetName;
  FormalList;
  Fin;
  if InTable(N) then
    Duplicate(N);
  ST[N := 'p';
  PostLabel(N);
  BeginBlock;
  Return;
  ClearParams;
end;

Der Aufruf innerhalb von DoProc setzt voraus, dass die Tabelle innerhalb des Hauptprogrammes bereinigt ist.

Wir benötigen noch einige Prozeduren um mit der Tabelle arbeiten zu können. Die nächsten Funktionen sind im Wesentlichen Kopien von InTable, TypeOf, usw.:

{ Finde die Parameternummer }

function ParamNumber(N: char): integer;
begin
  ParamNumber := Params[N];
end;

{ Ist der Bezeichner ein Parameter ? }

function IsParam(N: char): boolean;
begin
  IsParam := Params[N] <> 0;
end,

{ Füge einen neuen Parameter in die Tabelle ein }

procedure AddParam(Name: char);
begin
  if IsParam(Name) then
    Duplicate(Name);
  Inc(NumParams);
  Params[Name] := NumParams;
end;

Zum Schluss brauchen wir noch Codeerzeugungsprozeduren:

{ Lade einen Parameter ins Hauptregister }

procedure LoadParam(N: integer);
var Offset: integer;
begin
  Offset := 4 + 2 * (NumParams - N);
  Emit('MOVE D0,);
  WriteLn(Offset,'(SP)');
end;

{ Lade das Hauptregister auf den Stack }

procedure Push;
begin
  EmitLn('MOVE D0,-(SP)');
end;

(Die letzte Routine haben wir schon früher einmal programmiert, aber sie war nicht in unserer Basisversion für dieses Programm)

Mit diesen Vorbereitungen können wir die Semantik des Aufrufes von Prozeduren mit Parameterlisten abarbeiten (den Code für Prozeduren ohne Parameterliste haben wir schon erstellt).

Nun verarbeiten wir einen formalen Parameter. Dazu müssen wir nur jeden Parameter in die Parametersymbolliste aufnehmen:

{ Verarbeite einen formalen Parameter }

procedure FormalParam;
begin
  AddParam(GetName);
end;

Was machen wir wenn ein formaler Parameter im Programm der Prozedur auftaucht? Damit haben wir etwas Arbeit. Zuerst müssen wir feststellen, dass es sich um einen formalen Parameter handelt. Dazu benötigen wir eine modifizierte Version von TypeOf:

{ Hole den Typ des Symbols }

function TypeOf(n: char): char;
begin
  if IsParam(n) then
    TypeOf := 'f'
  else
    TypeOf := ST[n];
end;

(Da TypeOf jetzt IsParam aufruft, könnte es sein, dass wir es in unserem Quelltext verschieben müssen.)

Wir modifizieren auch AssignOrProc um mit dem neuen Typ arbeiten zu können:

{ Entscheide ob eine Anweisung eine Zuweisung oder ein Prozeduraufruf ist }

procedure AssignOrProc;
var Name: char;
begin
  Name := GetName;
  case TypeOf(Name) of
    ' ' : Undefined(Name);
    'v', 'f' : Assignment(Name);
    'p' : CallProc(Name);
  else
    Abort('Identifier '+Name+' Cannot be used here');
  end;
end;

Zum Schluss muss noch das Programm für die Verarbeitung einer Zuweisung und eines Ausdrucks erweitert werden:

{ Parse und übersetze einen Ausdruck }
{ Rudimentäre Version }

procedure Expression;
var Name: char;
begin
  Name := GetName;
  if IsParam(Name) then
    LoadParam(ParamNumber(Name))
  else
    LoadVar(Name);
end;

{ Parse und übersetze eine Zuweisung }

procedure Assignment(Name: char);
begin
  Match('=');
  Expression;
  if IsParam(Name) then
    StoreParam(ParamNumber(Name))
  else
    StoreVar(Name);
end;

Diese Prozedur verarbeitet jeden Variablennamen der entweder ein formaler Parameter oder eine globale Variable ist, abhängig ob der Name in der Parametersymbolliste enthalten ist oder nicht. Wir verwenden dabei nur eine rudimentäre Form von Expression. Im fertigen Programm müssen wir die, hier aufgezeigten, Änderungen auch in Factor und nicht in Expression vornehmen.

Der Rest ist einfach. Wir fügen nur die Semantik zum aktuellen Prozeduraufruf hinzu. Das können wir durch eine neue Programmzeile erledigen:

{ Verarbeite einen aktuellen Parameter }

procedure Param;
begin
  Expression;
  Push;
end;

Das ist es. Versuchen wir unser neues Programm mit Prozeduren mit formalen Parameterlisten. Dann versuchen wir Zuweisungen, die Kombinationen von globalen und formalen Parametern enthalten. Wir können innerhalb einer Prozedur eine weitere Prozedur aufrufen, aber wir können Prozeduren nicht GESCHACHTELT deklarieren. Wir können auch formale Parameter von einer Prozedur an die nächste weitergeben. Wenn wir die volle Syntax der Sprache programmiert haben können wir formale Parameter auch lesen und schreiben und sie in komplexen Ausdrücken verwenden.

Geometrische Gruppentheorie XVIII

Eigenschaften von Gruppen

Sei {(G,\cdot)} eine beliebige Gruppe und {u,v,w\in G.} Dann gilt:

  1. {v\cdot g\cdot g^{-1}\cdot w=v\cdot w}
  2. {g^{0}=id}
  3. {(g^{-1})^{-1}=g}
  4. {g^{-n}=(g^{-1})^{n}}

Sei {(G,\cdot)} eine beliebige Gruppe. Dann gilt:

  1. In G gibt es nur ein neutrales Element.
  2. Zu jedem Gruppenelement gibt es nur genau ein Inverses.
  3. Aus {g\cdot v=g\cdot w} oder {v\cdot g=w\cdot g} folgt {v=w} für Gruppenelemente {g,v,w.}
  4. Sind {g_{1},g_{2},..,g_{n}\in G,} so gilt:

    \displaystyle  (g_{1}\cdot g_{2}\cdot..\cdot g_{n})^{-1}=g_{n}^{-1}\cdot g_{n-1}^{-1}\cdot..\cdot g_{1}^{-1}

Sind {a,b,c,d} Elemente einer Gruppe {G,} so haben die Gleichungen {xa=c} und {by=d} jeweils genau eine Lösung.

Aufgabe:

Seien {a,b,c,d} Elemente einer Gruppe {G.} In der Gruppe gelte die Gleichung {ab^{-1}dca^{-1}=1} (1 ist hier das neutrale Element). Lösen sie diese Gleichung nach {d} auf.

  • {ab^{-1}dca^{-1}=1}
  • {b^{-1}dca^{-1}=a^{-1}}
  • {dca^{-1}=ba^{-1}}
  • {dc=ba^{-1}a=b}
  • {d=bc^{-1}}

Aufgabe:

Lösen sie die Gleichung {(1,3)\circ x=(1,2)(3,4).}

Das Inverse von (1,3) ist (3,1), damit gilt {x=(3,1)\circ(1,2)(2,3).} D.h. 1 wird zu 2, 2 wird zu 1 und 1 wird zu 3, usw. Man erhält {x=(1,2,3,4)}

.

[1] Rosebrock Stephan: Geometrische Gruppentheorie

Kapitel 13 von Crenshaw’s „Let’s build a compiler!“ Teil 3

Prozeduraufruf

Wir sehen uns nun den zweiten Teil der Arbeit an … den Aufruf.

Die BNF für den Prozeduraufruf:

<proc_call> ::= <identifier>

für die Zuweisung gilt andererseits

<assignment> ::=
  <identifier> '=' <expression>

Hier haben wir anscheinend ein Problem. Beide BNF Anweisungen beginnen auf der rechten Seite mit einem Bezeichner (). Haben wir jetzt einen Prozeduraufruf oder eine Zuweisung? Es sieht so aus als ob unser Parser auf der Grundlage des aktuellen Symbols nicht entscheiden kann wie er weitermachen soll. Genau das ist der Fall. Die Lösung ist ganz einfach, wir müssen nur in der Symboltabelle nachsehen welchen Typ der aktuelle Bezeichner hat.

Hier die Lösung:

{ Parse und übersetze eine Zuweisung }

procedure Assignment(Name: char);
begin
  Match('=');
  Expression;
  StoreVar(Name);
end;

{ Entscheide auf Zuweisung oder Prozeduraufruf }

procedure AssignOrProc;
var Name: char;
begin
  Name := GetName;
  case TypeOf(Name) of
    ' ': Undefined(Name);
    'v': Assignment(Name);
    'p': CallProc(Name);
  else
    Abort('Identifier ' + Name +
      ' Cannot be used here');
  end;
end;

{ Parse und übersetze einen Anweisungsblock }

procedure DoBlock;
begin
  while not(Look in ['e']) do
  begin
    AssignOrProc;
    Fin;
  end;
end;

In der Prozedur DoBlock wird nun, anstatt Assignment, AssignOrProc aufgerufen. AssignOrProc liest einfach den Bezeichner, bestimmt seinen Typ und rüft dann die zugehörige Prozedur auf. Da der Name schon gelesen wurde müssen wir ihn als Parameter weitergeben. Die Prozedur CallProc ist eine einfache Codeerzeugungsroutine:

{ Rufe eine Prozedur auf }

procedure CallProc(N: char);
begin
  EmitLn('BSR ' + N);
end;

Damit haben wir einen Compiler der mit Prozeduren arbeiten kann. Prozeduren können Prozeduren in jeder Tiefe aufrufen. Obwohl wir geschachtelte Prozedurdeklaration nicht erlaubt haben, hindert uns nichts an geschachtelten Aufrufen, wie wir es von anderen Sprachen gewöhnt sind. Wir haben es geschafft und es war nicht zu schwer.

Natürlich können wir momentan nur Prozeduren ohne Parameter behandeln. Die Prozeduren dürfen ausserdem nur mit globalen Variablen arbeiten. An diesem Punkt haben wir ein Äquivalent zum GOSUB von BASIC. Nicht schlecht … viele Programmierer verwenden GOSUB’s, aber wir können es besser. Das ist der nächste Schritt.

Parameterübergabe

Wir kennen die Basisprinzipien für die Übegabe von Parametern, aber wir wiederholen sie hier um sicherzugehen.

Im Allgemeinen hat die Prozedur eine Parameterliste, z. B.:

PROCEDURE FOO(X, Y, Z)

In der Prozedurdeklaration werden die Parameter formale Parameter genannt. Innerhalb der Prozedur kann auf sie über diese Namen zugegriffen werden. Die Namen, die für die formalen Parameter benutzt werden, sind völlig willkürlich. Letztendlich zählt nur ihre Position in der Parameterliste. Im obigen Beispiel bedutet ‚X‘ einfach “der erste Parameter“ wann immer er benutzt wird.

Wird eine Prozedur aufgerufen, werden die “aktuellen Parameter“ übergeben und mit den formalen Parametern eins zu eins verknüpft.

Die BNF für diese Syntax sieht in etwa so aus:

<procedure> ::=
  PROCEDURE <ident> '(' <param-list> ')'
  <begin-block>

<param-list> ::= <parameter>
  ( ',' <parameter> )* | null

Ähnlich sieht der Prozeduraufruf aus:

<proc-call> ::=
  <ident> '(' <param-list ')'

Wir haben hier wieder eine Entscheidung für unsere Syntax getroffen. In einige Sprachen, wie Pascal oder Ada, ist die Übergabe von Parameterlisten optional. Gibt es keine Parameter so werden die Klammern einfach weggelassen. In anderen Sprachen, wie C oder Modula2, sind die Klammern, sogar wenn die Liste leer ist, notwendig. Klar, wir haben vorher nach der ersten Syntaxregel gearbeitet. Wir werden aber den zweiten Ansatz bevorzugen. Gibt es nur Prozeduren ist der “listenfreie“ Ansatz etwas praktischer. Die Anweisung

Initialize;

kann dann nur ein Prozeduraufruf sein. In den Parsern, die wir geschrieben haben, haben wir viele Prozeduren ohne Parameter verwendet und es wäre umständlich hier immer leere Klammern schreiben zu müssen.

Aber später haben wir auch Funktionen verwendet. Da Funktionen an der selben Stelle wie einfache Bezeichner auftauchen können, gibt es keine Möglichkeit sie zu unterscheiden. Es muss in der Deklaration nachgesehen werden um hier die Entscheidung zu treffen. Manche meinen das ist ein Vorteil. Ihr Argument ist, dass ein Bezeichner durch einen Wert ersetzt wird und macht es einen Unterschied ob es eine Substitution oder eine Funktion ist? Aber wir müssen etwas aufpassen, weil eine Funktion sehr zeitaufwändig sein kann. Schreiben wir einen einfachen Bezeichner in einen Ausdruck kann das zur Laufzeit viel Zeit verbrauchen. Wir meinen, dass wir diesen Ansatz nicht verwenden sollen.

Egal, Niklaus Wirth hat Pascal und Modula2 entworfen. Er wird aus guten Grund die Regeln für den zweiten Entwurf geändert haben!

Die Realisierung ist für beide Ansätze einfach und daher erfolgt hier die Entscheidung aus rein persönlichen Vorlieben.

Bevor wir weitermachen ändern wir den Übersetzer um (möglicherweise leere) Parameterlisten verarbeiten zu können. Momentan erzeugen wir keinen zusätzlichen Code … wir parsen nur die Syntax. Der Code zur Verarbeitung der Deklaration sieht der, zum Behandeln der VAR-Listen, sehr ähnlich:

{ Verarbeite eine formale Parameterliste einer Prozedur }

procedure FormalList;
begin
  Match('(');
  if Look <> ')' then
  begin
    FormalParam;
    while Look = ',' do
    begin
      Match(',');
      FormalParam;
    end;
  end;
  Match(')');
end;

Die Prozedur DoProc benötigt eine zusätzliche Zeile um FormalList aufzurufen:

{ Parse und übersetze eine Prozedurdeklaration }

procedure DoProc;
var N: char;
begin
  Match('p');
  N := GetName;
  FormalList;
  Fin;
  if InTable(N) then
    Duplicate(N);
  ST[N] := 'p';
  PostLabel(N);
  BeginBlock;
  Return;
end;

Momentan ist der Code für FormalParam ein Platzhalter und überspringt einfach die Parameterliste:

{ Verarbeite einen formalen Parameter }

procedure FormalParam;
var Name: char;
begin
  Name := GetName;
end;

Den aktuellen Prozeduraufruf muss ein ähnlcher Code abarbeiten:

{ Verarbeite einen aktuellen Parameter }

procedure Param;
var Name: char;
begin
  Name := GetName;
end;

{ Verarbeite eine Parameterliste eines Prozeduraufrufs }

procedure ParamList;
begin
  Match('(');
  if Look <> ')' then
  begin
    Param;
    while Look = ',' do
    begin
      Match(',');
      Param;
    end;
  end;
  Match(')');
end;

{ Verarbeite einen Prozeduraufruf }

procedure CallProc(Name: char);
begin
  ParamList;
  Call(Name);
end;

Hier ist CallProc nicht mehr eine einfache Codeerzeugungsroutine. Sie beinhaltet jetzt einige Strukturen. Um das zu handhaben nennen wir die Codeerzeugungsroutine in Call um und rufen sie in CallProc auf.

Damit können wir die Syntax richtig parsen.

Wir prüfen aber NICHT ob die Anzahl der formalen und aktuellen Parameter (und später, die Typen) übereinstimmt. In einem echten Compiler müssen wir die Prüfung natürlich durchführen. Momentan ignorieren wir diese Forderung, einfach weil in unserer Symboltabelle noch kein Platz zum Speichern der Information vorhanden ist. Später werden wir auch das erledigen.

Geometrische Gruppentheorie XVII

Aufgabe:

Bildet {\mathbb{Z}_{n}} mit der Multiplikation modulo {n} eine Gruppe?

Das neutrale Element ist die 1. Für die 0 gibt es aber dann kein Inverses. Es bildet also keine Gruppe.

Aufgabe:

Bildet {\mathbb{J}_{n}=\{1,2,3,4,5,..,n-1\}} mit der Multiplikation modulo {n} eine Gruppe?

Ist {n} keine Primzahl, so lässt sie sich in ein Produkt von Primfaktoren {\prod p_{i}^{\nu_{i}}} zerlegen. Dann gibt es in der Menge {\mathbb{J}_{n}} eine Element das dieselbe Zerlegung geteilt durch eine Primzahl hat. Für diese Zahl kann es kein Inverses geben.

{\mathbb{J}_{n}} ist nur für {n} ist eine Primzahl eine Gruppe.

Aufgabe:

Welche Elemente der zyklischen Gruppe {(\mathbb{Z}_{12},+_{12})} erzeugen einzeln genommen die Gruppe {\mathbb{Z}_{12}?}

Alle Elemente die teilerfremd zu 12 sind (1,5,7,11) erzeugen die Gruppe.

.

[1] Rosebrock Stephan: Geometrische Gruppentheorie