Montag, 10. Dezember 2012

Syntax von Reni. Teil 2: Prioritäten

Ich hatte ja schon mal angedeutet, dass ich nicht so der große Anhänger von LEX und YACC bin. Das sind kranke Tools im Unix-Stil, die schon den 70ern veraltet waren.
Eine Bekannte hat mich kürzlich gefragt, ob ich so Bücher kenne wie "Compilers: Principles, Techniques, and Tools" (das so genannte Drachenbuch). Meine Meinung: Man kann nur hoffen, dass Compilerbauer dieses Buch höchstens als Schrankfußersatz verwenden.
Was hab ich damit für Probleme:
a) Es wird mit Kanonen auf Spatzen geschossen. (LEX)
b) Die Theorie der formalen Sprachen, die da immer zugrunde gelegt wird, ist für Compilerbau ungeeignet. Wozu brauche ich eine Fabrik die Autos herstellen kann, die für Fahrer mit einer variablen Anzahl von Gliedmaßen bestimmt sind?
c) Ich brauche nicht etwas, was mir zu einem Text sagt "Gehört zur Sprache L" oder "Gehört nicht zur Sprache L". Was bringt das? Was ich brauche, ist erstmal ein Syntaxbaum und dann etwas, mit dem ich denselben durchwandere, um den Code zu "stricken".
Klar geht das mit den o. g. Tools, aber es ist reingefummelt, viel zu kompliziert und viel zu eingeschränkt.

Deshalb geht Reni anders vor: Reni hat einen Prioritätsparser, der den Syntaxbaum erstellt und einen kontextabhängigen Visitor, der durch den Baum marschiert und dabei den Code erzeugt.
Der kontextabhängige Visitor wird später vorgestellt. Hier geht es zunächst um den Prioritätsparser.

Jeder kennt die Regel "Punktrechnung geht vor Strichrechnung". Nichts anderes ist das Prinzip des Prioritätsparsers (Eine entscheidende Kleinigkeit kommt noch dazu, doch davon gleich.).
Der Ausdruck 2 + 3 * 4 ergibt 14, weil erst 3*4 gerechnet werden muss und dann das Ergebnis zu 2 addiert wird. Das Beispiel ist sehr einfach, hier die Darstellung als Syntaxbaum:
2 3 4 * +
Die Prioritäten sind hier ganz einfach, oder? Höchste Priorität haben die einzelnen Zahlen, dann kommen die Punktrechnungen ("*" für Multiplikation und "/" für Division) und zum Schluß kommen die Strichrechnungen ("+" für Addition und "-" für Subtraktion).

P(Zahl) > P("*", "/") > P("+", "-")

Was ist aber jetzt mit einem Ausdruck wie 2 + 3 + 4? Sieht simpel und unproblematisch aus. Aber das gilt nur für einen menschlichen Betrachter. Der arme Compiler hat nämlich jetzt keine Ahnung, ob er erst 2 + 3 rechnen muss
2 3 + 4 +
oder erst 3 + 4
2 3 4 + +
(Er kann auch nicht erkennen, dass das in diesem Beispiel egal ist.). Wir müssen ihm irgendwie mitteilen, dass - sagen wir - erst 2 + 3 gerechnet werden soll. Dass nennt man Links-Assoziativität. Es gibt auch Rechts-Assoziativität und es gibt auch noch kompliziertere Dinge. Die obige Formel sagt aus, das es sich bei der Priorität um eine sogenannte Ordnungsrelation handelt. Tatsächlich werden Prioritäten manchmal als Zahlen angegeben. Aber schon ein Blick auf die Rechts- bzw. Linksassoziativität läßt die Schwächen dieses Konzepts erkennen: Je nachdem hat der betroffene Operator eine höhere (Linksassoziativität) oder niedrigere (Rechtsassoziativität) Priorität als er selber(!). Man könnte das noch hintricksen, indem man die Assoziativität als zusätzliche Eigenschaft dazu nimmt. Aber wenn dann noch andere Operatormuster ins Spiel kommen, wie zum Beispiel Klammerkonstrukte oder dreistellige Operatoren, wie then-else, muß man ins Grübeln kommen.
Was wäre, wenn man die Priorität nicht als Ordnungsrelation ansetzt, sondern einfach nur als Relation - mit einer schnöden Tabelle? Hier mal ein Beispiel für eine solche Tabelle (Erklärt wird sie im nächsten Eintrag):

(bot) ( (any) * / + - )
( <- <- <- <- <- <- <- ^^
(any) <- <- ^^ <- <- <- <- ^^
* <- <- ^^ ^^ ^^ <- <- ^^
/ <- <- ^^ ^^ ^^ <- <- ^^
+ <- <- ^^ ^^ ^^ ^^ ^^ ^^
- <- <- ^^ ^^ ^^ ^^ ^^ ^^
) <- = ^^ ^^ ^^ ^^ ^^ ^^
(eot) = ^^ ^^ ^^ ^^ ^^ ^^ ^^


Dienstag, 9. Oktober 2012

Syntax von Reni. Teil 1: Die Zerschnippelung in Tokens

Heute werde ich mal einige Grundlagen der Programmiersprache Reni vorstellen.
Was man braucht, um zu programmieren, ist ein Text, den man "Das Programm" nennt. Der Text muss bestimmten Regeln gehorchen, sonst meckert der Compiler. Oder aber er meckert nicht, aber wenn das Programm dann laufen soll, tut es nicht das, was es soll oder stürzt gar ab.
Die erste Sorte von Regeln nennt man, grob gesprochen, Syntaxregeln. Die zweite Sorte betrifft die sogenannte Semantik. Da komme ich später dazu.
Die simpelste, grundlegendste Regel: Ein Programm besteht aus eine Folge von Zeichen, die durch bestimmte Regeln in Tokens, das sind so etwas wie Worte, zergliedert werden. Das ist eigentlich keine grosse Sache, aber es ist gut, das wenigstens einmal hin zu schreiben.
Um diese Regeln zu erklären, müssen wir zunächst über Zeichentypen sprechen. Das sind:

  • Leerzeichen, Tabulator, Zeilenumbruch heissen Whitespaces
  • Alle Klammern, Komma, Semikolon und Ausrufezeichen heissen Syntaxzeichen
  • Buchstaben, Zahlen und der Unterstrich heissen alphanumerische Zeichen
  • Einfaches und doppeltes Hochkomma sind Stringbegrenzer (kommen wir noch dazu)
  • Das Doppelkreuz, auch Hashzeichen oder auch Gartenzaun ist das Kommentarzeichen (kommen wir auch noch dazu)
  • Alle anderen Zeichen (Hier mal eine Auswahl der wichtigsten: ^°§$%&/=?\+*@~<.->|) heissen Symbolzeichen

Jetzt können wir die Tokenbildungsregeln angeben:

  • Whitespaces trennen Token, sind aber selbst keine Token.
  • Syntaxzeichen trennen Token und sind auch selbst Token
  • Alphanumerische Zeichen bilden Token, wenn sie eine ununterbrochene Folge bilden
  • Auch Symbolzeichen bilden Token, wenn sie eine ununterbrochene Folge bilden
  • Ein Wechsel von alphanumerischen Zeichen zu Symbolzeichen oder umgekehrt trennt Token
Da kommt noch mehr, aber erstmal will ich diese Regeln durch ein paar Beispiele verdeutlichen:

Hello world123   123
dump_print
Die Token sind hier: "Hello", "world123", "123" und "dump_print". 


(Hello[world123,123;dump_print
Die Token sind hier: Runde Klammer auf, "Hello", eckige Klammer auf, "world123", Komma, "123", Semikolon und wieder "dump_print". 

Hello<<world123*123=:=dump_print
Die Token sind hier: "Hello", "<<", "world123", "*", "123", "=:=" und schließlich wieder "dump_print". 

Was jetzt noch fehlt, sich Strings und Kommentare. 
Beide trennen Tokens und Strings sind selbst auch Tokens. 
Strings sind fast beliebige Zeichenfolgen, die durch jeweils einen Stringbegrenzer vorne und hinten  begrenzt werden. Nomen est omen! Der Stringbegrenzer muß vorne und hinten der gleiche sein. Also gibt es somit zwei Arten von Strings: die die mit einfachem Hochkomma begrenzt werden und die mit einem doppelten. Aber keine Panik, das macht keinen Unterschied. 
Naja, fast keinen.   
"Fast beliebige Zeichenfolgen" bedeutet, dass natürlich der jeweils benutzte Stringbegrenzer nicht so einfach vorkommen kann. Aber er kann vorkommen - dann muss man ihn aber doppelt schreiben. Auch ist es verboten, einen Zeilenumbruch mitten im String vorkommen zu lassen. Wenn man das mal braucht, muss man sich anders helfen. Aber das kommt später (viel später). 
Ok, jetzt wieder ein paar Beispiele:

"Hello world"dump_print
Die Token sind hier: der String "Hello world" und schließlich wieder unser gutes altes "dump_print". 

'Hello world'dump_print
Dasselbe. Ist hier egal ob einfache oder doppelte Hochkommas. 

"it's cool man"dump_print
Die Token sind hier: der String "it's cool man" und wieder "dump_print".

'it''s cool man'dump_print
Dasselbe. Jedoch mussten wir hier das Hochkomma verdoppeln, weil der Begrenzer schon das einfache Hochkomma ist. Aber Achtung: es zählt trotzdem nur als eines.

Wenn man mal ein kompliziertes, schwer lesbares oder schwer verständliches Programm vorfinden sollte, kann man das durch sogenanntes Refactoring in ein weniger kompliziertes, besser lesbares oder leichter verständliches Programm verwandeln.
Oder man verwendet Kommentare, um das Spaghettimonster irgendwie zu beschreiben.
Ich empfehle die erste Methode, aber die geht nicht immer. Deshalb gibts auch in Reni Kommentare.
Kommentare beginnen mit einem Kommentarzeichen (#). Es gibt gleich zwei Sorten von Kommentaren: Zeilenkommentare reichen bis zum Ende der Zeile. Blockkommentare reichen bis zum Kommentarende-Zeichen. Die Blockkommentare erkennt man daran, dass nach dem Kommentarzeichen eine öffnende Klammer steht und dann noch ein Kommentarbezeicher folgt. Der wird verwendet, um das Ende des Kommentars zu finden. Das ist am einfachsten mit Beispielen zu illustrieren:
"Hello world" #(* Das ist ein Kommentar *)#dump_print  
Der  Kommentarbezeicher ist hier der Stern. Man kann jedes Symbol hier verwenden aber auch Namen, also Folgen von Buchstaben. Beispiel:
"Hello world" #(ignorieren Das ist ein Kommentar ignorieren)#dump_print  
Der  Kommentarbezeicher ist hier das Wort "ignorieren". 
Wozu man das braucht? Na Ihr werdet schon sehen...

Zum Schluß noch ein Beispiel für Zeilenkommentare, der Vollständigkeit halber:
"Hello world" # Das ist der auszugebende String
dump_print # ... und damit wird er ausgegeben   

Für den Compiler sind Kommentare nichts anderes als Leerzeichen. Er verwendet sie, wenn nötig als Trenner zweier Tokens, aber ansonsten werden sie ignoriert.

Den Einstieg haben wir jetzt. Das war vielleicht etwas "urschleimig". Und nix mit richtig programmieren. Aber es musste mal gesagt werden. 
Denn...
Ich hatte da mal so ein traumatisches Erlebnis. Es war Ende der Neunziger. Die "Programmiersprache" hieß "Base SAS". Und die hat großzügig auf solche schnöden Beschreibungen verzichtet. Das Ende vom Lied war, dass man in etwas kniffligeren Fällen (und die kommen bei echten Anwendungen garantiert) nie so richtig wusste, wie die Syntax genau definiert war. Ich habe mir damals geschworen, so etwas nie niemals zu tun.

Mittwoch, 29. August 2012

Am Strand

Blogleser wollen Podcasts! Das hab ich gelesen und finde das selbst auch. Deshalb hier der erste Reni-
Podcast.

Linkliste:
97 Things Every Programmer Should Know

Sonntag, 17. Juni 2012

Hallo Welt

Jede ordentliche Programmiersprache muß mit einen Hello-World-Programm beginnen. Ich will da auch nicht nachstehen. Hier ist es:

    "Hello world" dump_print


"Macht nicht viel her", wird jetzt so manche sagen. Aber das ist eigentlich mehr oder weniger immer so. Ein Hello-World-Programm dient der grundsätzlichen Klärung von Sachen: wie ist der allgemeine Rahmen des Programmtextes, wie findet die Kommunikation mit dem Benutzer des Programmes statt. Indem man dann versucht, dieses Programm zu Laufen zu bringen, werden eine weitere Grundsätze klar: wie man den Compiler oder Laufzeitumgebung besorgt und benutzt.
Also machen wir das mal:


Reni ist momentan eine experimentelle Programmiersprache. Deshalb gibt es nur eine eingeschränkte Infrastruktur. 


Level 1: Die niederschwelligste Variante ist eine Website, wo man oben das Programm eingibt und dann auf einen Kopf drückt. Ich habe mal eine solche Website erstellt. Meine "Mittel" als Webprogrammierer sind begrenzt, so dass diese Site definitiv ziemlich poplich daherkommt. Aber:
a) Sie tut es
b) Sie ist sie eine Mitmachprovokation
Hier ist also der Link

Level 2: Für die verschwindende Randgruppe der Windowsbenutzer gibt es noch eine weitere relativ einfache Möglichkeit. Man kann sich hier die Assemblies runterladen. Einfach irgendwohin auspacken und in einer Konsole "ReniExe <meinedatei>" eingeben. Dabei steht <meinedatei> für den Namen einer Textdatei, die das zu kompilierende Programm enthält. Möglicherweise muß man noch ".NET Framework 4" installieren. Außerdem möchte ich an dieser Stelle noch darauf hinweisen, dass alles was Ihr mit dieser Software tut, Ihr auf eigene Gefahr tut. Ich übernehme keinerlei Haftung für eventuelle Schäden.

Level 3: Das alles ist unter gpl3. Die Sourcen kann man auf github finden. Es wird VisualStudio und C# benötigt. Mitmachprovokation!

Level 3+: Vielleicht findet sich ja jemand, der das ganze mal unter Mono oder so ans Laufen kriegt. Das wäre für die Menschen, die sich mit Linux oder gar MacOS rumquälen müssen, hilfreich. Ich weiß nicht genau, aber möglicherweise eröffnet sich dann auch die Möglichkeit die Entwicklung mit etwas anderem als VisualStudio zu bestreiten (Nicht das ich das VisualStudio schlecht finde, aber eine größere Wahlfreiheit ist auf jeden Fall zu begrüßen). Da ich momentan keine großartigen Spezialfeatures benutze, sollte das nicht allzu schwer sein, aber schaun wir mal...

Hier mal noch ein etwas komplexeres Beispiel:


Viersich: 4;
EinsDazu: /\ arg + 1;
Konstrukt: /\
(
    Simpel: arg; 
    Pelsim: EinsDazu(arg); 
    Fun: /\ SimpelEinsDazu(arg)
);
lorum: Konstrukt(23);
ipsum: Konstrukt(8);
ipsum Pelsim := 15;
(Viersich, ipsum Simpel, ipsum Pelsim, ipsum Fun(7), lorum Simpel, lorum Fun(18)) dump_print


Man sieht hier Elementares zum Gebrauch von Variablen und Funktionen. Der Doppelpunkt definiert eine Variable mit Initialisierung. Das Zeichen "/\" soll ein Lambda symbolisieren. Es steht immer am Anfang der Funktionsdefinition und mit "arg" wird das Argument des Aufrufs bezeichnet. Wie man Strukturen definiert und dann auf die Elemente zugreift, kann man hier auch sehen (Funktion "Konstrukt", Variablen "lorum" und "ipsum"). Das Zeichen := ist die Wertänderung.

Update 14.9.2012: Lambda-Symbol ist jetzt ein Präfix.
Update 04.11.2012: Versionsnummer bei VisualStudio entfernt
Update 04.11.2012: Ein wenig mehr Erklärung beim komplexen Beispiel
Update 21.11.2012: Link zum Tester

Freitag, 30. Dezember 2011

Was bisher geschah

Die Anfänge
Am Anfang, das war so 1988, wollte ich mal etwas schaffen, mit dem man mithilfe von Programmablaufplänen programmieren konnte. Bald stellte sich mir die Frage, was soll in die Kästchen rein geschrieben werden? C? Pascal? Oder was Eigenes?
Ich war begeisterter TurboPascal Programmierer, was Anfang der Neunziger darin gipfelte, dass ich als meine Autonummer WI-TP60 wählte, nach der Objekt-orientierten Version Turbo Pascal 6.0. Aber im Laufe der Zeit nervte mich die Wirtsche Stringenz von Pascal mehr und mehr. Auch schien mir Borland immer mehr den roten Faden zu verlieren. Und den Sprung von DOS nach Windows, haben sie meiner Meinung nach völlig vermasselt (Keine Ahnung, ob etwa Delphi eine Renaissance ist, habs nie ernsthaft probiert).
Ich hatte zu der Zeit im Rahmen meines Jobs Zugriff auf richtig fette IBM-Rechner. Dort fand ich REXX (die IBM-Großrechner-Variante - nicht dieses lahme OS/2-Ding!). REXX hat sowas wie Strukturen ("Stems"), viele sehr clevere Stringverarbeitungsfunktionen und war - technikbedingt -schweinegrottenschnell. Es war als Commandosprache angelegt und bot so auch sehr schöne Möglichkeiten für Metaprogrammierung ("interpret"). Das wiederum brachte die nötige Flexibilität ins Spiel. Genervt hat lediglich die Fehlersuche manchmal, da REXX schwach getyped war.
Jedenfalls konnte ich damit Experimente machen, mit eigenen Vorstellungen von Objektorientierung. Das war schon mal sehr inspirierend.

Es hat einen Namen!
Dann - 1994 - lernte ich C++ kennen. Ich ließ Turbo Pascal und REXX hinter mir und fing an, "Reni", wie ich es schon damals nannte, in C++ zu bauen. Zuerst mit Borland C++ und später dann mit MS Visual C++.
Warum es "Reni" heißt? Vermutlich hat es mit einer nicht richtig bewältigten Frauengeschichte zu tun. Mehr sag ich dazu nur meiner Psychotherapeutin...
Mittlerweile hatte ich für mich die Frage beantwortet, was die Kästchen enthalten sollten: C (wie auch C++) hat eine mir zu kranke Syntax. Pascal war mir zu unpraktisch (Dito Modula). REXX war nicht getyped. Smalltalk war mir zu alt und zu komisch (LISP genauso). Und so weiter und so fort. An allen Sprachen hatte ich etwas rum zu mäkeln. Es ist mir natürlich bewußt, das ist alles sehr subjektiv.
Alles lief also darauf hinaus, meine eigene Programmiersprache zu entwickeln.
Kurz darauf kam für mich noch ein weiteres Argument dazu: Java. Für meine Vorstellung ist Java entstanden, indem man Smalltalk-Semantik mit C-Syntax versehen hat. Damals dachte ich, man sollte eigentlich genau umgekehrt vorgehen. "Richtige Speicherverwaltung", nicht Garbarge Collection - und - eine ordentliche Syntax. (Dabei hatte ich ein bisschen außer Acht gelassen, daß Syntax von Smalltalk auch nicht so richtig toll ist.) Auf jeden Fall gab das noch einen zusätzlichen Motivationsschub.
In den folgenden 10 Jahren nutzte ich meine sich entwickelnde Programmiersprache, um mein C++-Kung-Fu zu perfektionieren. Man muß das so sagen, denn scheinbar war mir "es schön zu machen" immer wichtiger, als fertig zu werden. Ich konzentrierte mich auch komplett auf den "linearen" Teil, also das, was in die Kästchen reinkommt. Die graphische Komponente hatte (und habe) ich ziemlich aus dem Fokus verloren.

Scharfe Konturen zeigen sich
Schließlich kam C# in die Welt - Die Microsoft-hat-die-Nase-voll-von-Java-Sprache. Java hat auch mich immer echt genervt. Das war für mich immer eine Sprache für Leute, die es auch mal mit Programmieren versuchen wollten. Aber C# dagegen hatte schon was. Es war nicht C++, aber immerhin. Als ich dann auch noch beruflich damit zu tun hatte, war ich hin und weg. Aber was mich ehrlich gesagt am meisten begeisterte waren die Sachen drumherum. Die IDE, die Dotnet-Bibliotheken und "the great and still growing" Resharper.
Nebenbei war ich mittlerweile auch von C++ etwas genervt, aber wiederum weniger von der Sprache selbst, als vielmehr vom Support innerhalb Visual Studio (Über die anderen IDEs will ich gar nicht reden, die spielen alle mindestens eine Liga tiefer). Z. B.: wer braucht ein IntelliSense, das nur funktioniert, wenn keine Fehler vorliegen?
Also schrieb ich dann den Compiler in C# um und machte damit weiter.
Und wieder ging es mehr ums Kung-Fu als ums fertig werden...
Mittlerweile bekam ich auch bei immer mehr Teilen des Compilers ein Gefühl von Ultimativität. Der Parser, der zentrale Syntaxbaum-Visitor und die Namensauflösungs-Strategie haben sich in einer Weise stabilisiert, dass ich es ziemlich genauso wieder designen würde, müsste ich wieder bei null anfangen.

In welchem Universum bin ich - zum Kuckuck?
Jedoch sind meine Lösungen ziemlich weit von dem entfernt, was ich mal als Compilerbau gelernt hatte. Wenn ich versuche, mir Hilfe aus Büchern zu holen, muß ich regelmässig feststellen, dass das alles nahezu nichts mit den Problemen zu tun hatte, die sich mir stellen. Zum Beispiel lex und yacc: die lösen derart unbedeutende Probleme, das man sich fragt, ob die mit ihnen einhergehende Verkomplizierung des Compilierprozesses wirklich das kleinere Übel ist. Mehrere Anläufe im Laufe der Jahre endeten immer mit dem Urteil: "Was fürn Scheiß". Und wie man einen Visitor baut, der kontextabhängig durch den Syntaxbaum marschiert, wenn die Ausdruckstypen nicht nur vom Syntaxelement sondern auch vom Kontext abhängen, hab ich auch nirgendwo gefunden. Wie machen die anderen das, wenn es Templates oder Generics oder wie auch immer die Dinger sonst heißen, gibt. Vermutlich ist das geheimes Druidenwissen.

Naja, mal sehen, was passiert, wenn ich es schaffe, dass eine größere Community da drauf guckt. Stellt sich dann raus, dass ich die ganze Zeit auf dem falschen Dampfer bin?
Ich hoffe nicht.
Ich hoffe, ich habe genial neue Methoden gefunden.
So genial und neu, dass ich damit in die Geschichte eingehen werde.

Samstag, 13. August 2011

bin auf github

Die C# - Sourcen für den Compiler stehen jetzt auf github zur Verfügung