LFortran-Design

Allgemeine Übersicht

LFortran ist um zwei unabhängige Module herum aufgebaut, AST und ASR, die beide eigenständig sind (völlig unabhängig vom Rest von LFortran), und die Benutzer werden ermutigt, sie unabhängig für andere Anwendungen zu verwenden und darauf aufbauende Werkzeuge zu erstellen:

  • Abstrakter Syntaxbaum (abstract syntax tree, AST), Modul lfortran.ast: Stellt einen beliebigen Fortran-Quellcode dar, der ausschließlich auf der Syntax basiert und keine Semantik enthält. Das AST-Modul kann sich selbst in Fortran-Quellcode umwandeln.

  • Abstrakte semantische Repräsentation (abstract semantic representation, ASR), Modul lfortran.asr: Stellt einen gültigen Fortran-Quellcode dar, die gesamte Semantik ist enthalten. Ungültiger Fortran-Code ist nicht erlaubt (es wird ein Fehler ausgegeben). Das ASR-Modul kann sich selbst in einen AST umwandeln.

Der LFortran-Compiler setzt sich dann aus den folgenden unabhängigen Stufen zusammen:

  • Parsing: Konvertiert Fortran-Quellcode in einen AST

  • Semantisch: wandelt einen AST in eine ASR um

  • Optimierungen auf hoher Ebene: Optimierung der ASR zu einer möglicherweise schnelleren/einfacheren ASR (z. B. Inlining von Funktionen, Beseitigung redundanter Ausdrücke oder Anweisungen usw.)

  • LLVM IR-Code-Generierung und Optimierungen auf niedrigerer Ebene: wandelt eine ASR in eine LLVM IR um. In dieser Phase werden auch alle anderen Optimierungen durchgeführt, die keine ASR erzeugen, aber dennoch sinnvoll sind, bevor sie an LLVM IR übergeben werden.

  • Erzeugung von Maschinencode: LLVM führt dann alle Optimierungen durch und generiert Maschinencode (z. B. eine binäre ausführbare Datei, eine Bibliothek, eine Objektdatei, oder sie wird geladen und mit JIT als Teil der interaktiven LFortran-Sitzung oder in einem Jupyter-Kernel ausgeführt).

LFortran ist als Bibliothek strukturiert, und so kann man zum Beispiel den Parser verwenden, um einen AST zu erhalten und etwas damit zu tun, oder man kann dann den semantischen Analysator verwenden, um ASR zu erhalten und etwas damit zu tun. Man kann die ASR direkt generieren (z.B. aus SymPy) und dann entweder in AST und in einen Fortran-Quellcode konvertieren oder LFortran verwenden, um sie direkt in Maschinencode zu kompilieren. Mit anderen Worten, man kann LFortran verwenden, um einfach zwischen den drei äquivalenten Darstellungen zu konvertieren:

  • Fortran-Quellcode

  • Abstrakter Syntaxbaum (AST)

  • Abstrakte semantische Repräsentation (ASR)

Sie sind alle im folgenden Sinne gleichwertig:

  • Jeder ASR kann jederzeit in einen entsprechenden AST umgewandelt werden

  • Jeder AST kann jederzeit in einen entsprechenden Fortran-Quellcode konvertiert werden

  • Jeglicher Fortran-Quellcode kann immer entweder in einen äquivalenten AST konvertiert werden oder man bekommt einen Syntaxfehler

  • Jeder AST kann immer entweder in einen äquivalenten ASR umgewandelt werden oder man erhält einen semantischen Fehler

Wenn also eine Konvertierung möglich ist, sind sie gleichwertig, und die Konvertierung kann immer durchgeführt werden, es sei denn, der Code ist ungültig.

Details zum ASR-Design

Die ASR ist mit den folgenden Merkmalen ausgestattet:

  • ASR ist immer noch semantisch äquivalent zum ursprünglichen Fortran-Code (und hat keine semantischen Informationen verloren). ASR kann in AST und AST in Fortran-Quellcode konvertiert werden, welcher funktional dem Original entspricht.

  • Die ASR ist so einfach wie möglich: sie enthält keine Informationen, die nicht aus der ASR abgeleitet werden könnten.

  • Die ASR C++-Klassen (in Zukunft) sind ähnlich wie die SymEngine konzipiert: Sie werden einmal konstruiert und sind danach unveränderlich. Der Konstruktor prüft im Debug-Modus eher, ob alle Anforderungen erfüllt sind (z.B., dass alle Variablen in einer Funktion ein Dummy-Argument haben, dass explizite Arrays nicht zuweisbar sind und alle anderen Fortran-Anforderungen, um es zu einem gültigen Code zu machen), aber im Release-Modus konstruiert er die Klasse schnell und ohne Prüfungen. Dann gibt es Builder-Klassen, die die ASR-C++-Klassen so konstruieren, dass sie die Anforderungen erfüllen (die im Debug-Modus überprüft werden), und der Builder gibt eine Fehlermeldung aus, wenn ein Code kein gültiger Fortran-Code ist, und wenn er keine Fehlermeldung ausgibt, dann sind die ASR-C++-Klassen korrekt konstruiert. Somit enthalten die ASR-Klassen konstruktionsbedingt immer gültigen Fortran-Code und der Rest von LFortran kann davon abhängen.

Anmerkungen:

Informationen, die beim Parsen des Quelltextes in den AST verloren gehen: Leerzeichen, Unterscheidung zwischen mehrzeiligen und einzeiligen if-Anweisungen, Groß- und Kleinschreibung von Schlüsselwörtern.

Informationen, die beim Übergang von AST zu ASR verloren gehen: detaillierte Syntax, wie Variablen definiert wurden, und die Reihenfolge der Typattribute (ob die Arraydimension das Attribut dimension oder Klammern bei der Variablen verwendet; oder wie viele Variablen es pro Deklarationszeile gibt oder ihre Reihenfolge), da ASR nur die aggregierten Typinformationen in der Symboltabelle darstellt.

ASR ist der einfachste Weg, Fortran-Code zu erzeugen, da man sich nicht um die detaillierte Syntax (wie in AST) kümmern muss, wie und wo Dinge deklariert werden. Man spezifiziert die Symboltabelle für ein Modul, dann gibt man für jedes Symbol (Funktionen, globale Variablen, Typen, …) die lokalen Variablen an, und wenn es sich um ein Interface handelt, muss man angeben, wo man eine Implementierung finden kann, andernfalls wird ein Body mit Statements bereitgestellt, diese Knoten sind fast die gleichen wie in AST, außer dass jede Variable nur ein Verweis auf ein Symbol in der Symboltabelle ist (also kann man konstruktionsbedingt keine undefinierten Variablen haben). Die Symboltabelle für jeden Knoten, wie z. B. Funktion oder Modul, verweist auch auf seine Eltern (z. B. verweist eine Funktion auf ein Modul, ein Modul auf den globalen Bereich).

Der ASR kann direkt in einen AST umgewandelt werden, ohne dass weitere Informationen erfasst werden müssen. Und der AST direkt in Fortran-Quellcode.

Die ASR stellt immer einen semantisch gültigen Fortran-Code dar. Dies wird durch Überprüfungen in den ASR-C++-Konstruktoren (im Debug-Build) erzwungen. Wenn eine ASR eingesetzt wird, kann man davon ausgehen, dass sie gültig ist.

Fortran 2008

Fortran 2008 Standard Kapitel 2 „Fortran concepts“ left fest, dass Fortran Code eine Sammlung aus program units ist. (entweder alle in einer Datei oder in separaten Dateien), wobei jede program unit eine der folgenden ist:

  • Hauptprogramm (main program)

  • Modul oder Submodul

  • Funktion oder Subroutine

Beachte: Es kann auch eine block data-Programmeinheit sein, die verwendet wird, um Anfangswerte für Datenobjekte in benannten common blocks bereitzustellen, aber wir empfehlen die Verwendung von common blocks nicht (verwende stattdessen Module).

LFortran-Erweiterung

Wir erweitern die Fortran-Sprache, indem wir einen global scope, welcher nicht nur die Liste der program units (wie in F2008) ist, sondern auch include-Anweisungen, Deklarationen, use-Anweisungen und Ausdrücke enthalten kann.Wir definieren den global scope als eine Sammlung der folgenden Elemente:

  • Hauptprogramm (main program)

  • Modul oder Submodul

  • Funktion oder Subroutine

  • use Statement

  • Deklarationen (declaration)

  • Anweisung (statement)

  • Ausdruck (expression)

Zusätzlich wird, wenn eine Variable in einer Zuweisung (wie beispielsweise x = 5+3) nicht definiert ist, der Typ der Variablen aus der rechten Seite abgeleitet (z. B. wäre x in x = 5+3 vom Typ integer und y in y = 5._dp vom Typ real(dp)). Diese Regel gilt nur auf der obersten Ebene des global scope. Innerhalb von Hauptprogrammen, Modulen, Funktionen und Unterprogrammen müssen die Typen vollständig angegeben werden, genau wie in F2008.

Der global scope hat seine eigene Symboltabelle. Das Hauptprogramm und das Modul/Submodul sehen keine Symbole aus dieser Symboltabelle. Aber Funktionen, Unterprogramme, Anweisungen und Ausdrücke auf der obersten Ebene des global scope verwenden und operieren mit dieser Symboltabelle.

Für den global scope sind die folgenden Symbole in der Symboltabelle vordefiniert:

  • den üblichen Standardsatz von Fortran-Funktionen (wie size, sin, cos, …)

  • das Symbol dp für doppelte Genauigkeit, so dass man 5._dp für doppelte Genauigkeit verwenden kann.

Jedes Element im global scope wird wie folgt interpretiert: Das Hauptprogramm wird in eine ausführbare Datei mit demselben Namen kompiliert und ausgeführt; Module, Funktionen und Unterprogramme werden kompiliert und geladen; use-Anweisungen und Deklarationen fügen die Symbole mit dem richtigen Typ in die Symboltabelle des global scope ein, erzeugen aber keinen Code; Anweisungen werden in eine anonyme Unterroutine ohne Argumente übertragen, kompiliert, geladen und ausgeführt; Ausdrücke werden in eine anonyme Funktion, die den ursprünglichen Ausdruck zurückgibt, ohne Argumente übertragen kompiliert, geladen, ausgeführt und der Rückgabewert wird an den Benutzer zurückgegeben.

Der global scope wird immer Element für Element interpretiert, wie im vorherigen Absatz beschrieben. Er ist dazu gedacht, interaktive Nutzung, Experimente und das Schreiben einfacher Skripte zu ermöglichen. Code im global scope muss mit lfortran interpretiert werden. Für komplexeren (produktiven) Code wird empfohlen, ihn in Module und Programme umzuwandeln (indem man lose Anweisungen in Unterprogramme oder Funktionen umwandelt und Typdeklarationen hinzufügt) und ihn mit lfortran oder einem anderen Fortran-Compiler zu kompilieren.

Hier sind einige Beispiele für gültigen Code im global scope:

Beispiel 1

a = 5
print *, a

Beispiel 2

a = 5

subroutine p()
print *, a
end subroutine

call p()

Beispiel 3

module a
implicit none
integer :: i
end module

use a, only: i
i = 5

Beispiel 4

x = [1, 2, 3]
y = [1, 2, 1]
call plot(x, y, "o-")

Design Entscheidungen

Die LFortran-Erweiterung von Fortran wurde so gewählt, dass die Zahl der Änderungen möglichst gering ist. Insbesondere wurden nur auf der obersten Ebene des global scope einige der Fortran-Regeln gelockert (z.B. die optionale Angabe von Typen), um eine einfache und schnelle interaktive Nutzung zu ermöglichen.

Die Anzahl der Änderungen wurde so gering wie möglich gehalten, um die Umwandlung von global scope-Code in standardkonformen Fortran-Code mit Hilfe von Programmen und Modulen so einfach wie möglich zu gestalten, so dass er von jedem Fortran-Compiler kompiliert werden kann.