Unterschiede zwischen Stackmaschinen und Registermaschinen sind minimal

In der Forth community wird das Märchen verbreitet, dass Stackmachinen um einiges effizienter wären als Registermachinen. Angeblich wäre der GA144 Chipsatz um den Faktor 50 energieeffizienter als normale Microcontroller. Es ist für Außenstehende schwer die Fakten zu überprüfen, weil sehr viele Informationen zusammenfließen. Allein die Erklärung was genau eine Stackmaschine ist füllt ganze Bücher. Im folgende wird der Versuch unternommen Klarheit in die Sache zu bringen. Als Untersuchungsgegenstand wird eine selbst programmierte Virtuelle Maschine verwendet. Einmal als Stackmachine und einmal als Registermachine konzipiert. Der Sourcecode lautet:

loopmax = 1000000
verbose = 0

class Registermachine():
  def __init__(self):
    self.program = []
    self.r1,self.r2 = 0,0
    self.r3 = 0 # result
    self.initprogram()
    self.run()
  def showregister(self):
    if verbose != 0:
      print "register ", self.r1, self.r2, self.r3
  def run(self):
    for i in range(loopmax):
      self.runprogram()
  def runprogram(self):
    for i in range(len(self.program)):
      self.interpret(self.program[i])
      self.showregister()
  def initprogram(self):
    self.program = []
    self.program.append(("load1",10))
    self.program.append(("load2",11))
    self.program.append(("add",-1))
    self.program.append(("drop",-1))
  def interpret(self,instruction):
    if verbose != 0:
      print instruction[0],instruction[1]
    if instruction[0]=="load1":
      self.r1=instruction[1]
    if instruction[0]=="load2":
      self.r2=instruction[1]
    if instruction[0]=="add":
      self.r3 = self.r1+self.r2
    if instruction[0]=="drop":
      self.r3 = 0


class Stackmachine():
  def __init__(self):
    self.program = []
    self.stack = []
    self.verbose = 0 # 0=no output

    self.initprogram()
    self.run()
  def showstack(self):
    if verbose != 0:
      print "stack ", self.stack
  def initprogram(self):
    self.program = []
    self.program.append(("load",10))
    self.program.append(("load",11))
    self.program.append(("add",-1))
    self.program.append(("drop",-1))
  def interpret(self,instruction):
    if verbose != 0:
      print instruction[0],instruction[1]
    if instruction[0]=="load":
      self.stack.append(instruction[1])
    if instruction[0]=="add":
      # calculate
      result = self.stack[-1]+self.stack[-2]
      # delete last two element on stack
      del self.stack[-1]
      del self.stack[-1]
      # store result to stack
      self.stack.append(result)
    if instruction[0]=="drop":
      del self.stack[-1]

  def run(self):
    for i in range(loopmax):
      self.runprogram()
  def runprogram(self):
    for i in range(len(self.program)):
      self.interpret(self.program[i])
      self.showstack()

if __name__ == "__main__":
  #myVM = Stackmachine()
  myVM = Registermachine()

Die Virtuelle Maschine besteht aus einer Python Klasse welche die folgenden Befehle kennt: load, add und drop. Bei der Variante als Registermaschine enthält die VM drei einzeln ansprechbare Register r1,r2,r3. In diesen werden Werte hineingeschrieben und dort finden auch Berechnungen statt. Bei der Variante Stackmachine hingegen gibt es nur den Stack auf den von oben neue Werte hinaufgepoppt werden. Das Berechnungsmodell wurde dem Forth System nachempfunden. Wenn man die Virtuelle Maschine mit einem konkreten Programm ausführt und das mehrmals hintereinander benötigt die Registermaschine auf meinem PC 3,6 Sekunden, während die Stackmachine 4,3 Sekunden benötigt. Das heißt, nominell ist also die Registermaschine etwas schneller. Der Grund lautet, dass bei der Abarbeitung der Befehle andere Operationen in einer anderen Reihenfolge ausgeführt werden.

Wer sich näher den Sourcecode anschaut wird entdecken, dass der Vergleich höchst unfair ausfällt, weil man theoretisch auch die Stackmachine etwas tunen kann. Spart man nur einen Befehl ein, liegt die Geschwindigkeit ungefähr gleichauf. Worum es mir geht ist jedoch weniger das konkrete Ergebnis (4,3 Sekunden vs. 3,6 Sekunden) sondern die Tatsache, dass man eine virtuelle Maschine in Software programmiert, auf dieser ein Programm ausführt und davon die Ausführungszeit misst. Ich vermute mal, dass bei komplexeren Virtuellen Maschinen die noch dazu nicht in Python sondern in C programmiert werden, das Ergebnis ungefähr gleichauf liegt, vielleicht mit einem kleinen Vorteil für Registermaschinen. Aktuell gibt es Virtuelle Maschinen in beiden Ausprägungen. Die Java Virtual Maschine ist eine Stackmachine, während die Lua-virtual Maschine als Registermachine arbeitet.

Vielleicht ein kleiner Exkurs was überhaupt eine Virtuelle Maschine ist. Im Grunde nichts anderes als ein BASIC Interpreter. Die VM ließt eine Hochsprache ein und führt das auf der CPU aus. Ein Aufwendiger Compilerdurchlauf wird vermieden, demzufolge ist die Ausführungszeit schlechter als bei einem C-Compiler. Die interne Funktionsweise des Interpreters wird als Maschinenmodell sichergestellt. Ein Python Interpreter muss beispielsweise Nebenläufigkeit beherschen.

Worauf ich hinaus möchte ist, dass heutige Virtuelle Maschinen und CPUs die in Hardware realisiert wurde, nicht so ineffizient sind wie immer behaupten. Natürlich könnte man die Performance leicht erhöhen, dass man aber durch die Umstellung von Registermachinen auf Stackmachinen einen Geschwindigkeitsanstieg um den Faktor 50 erzielt ist reines Wunschdenken der Forth Community. Der Grund warum die meisten CPUs als Registermachine entwickelt werden hat damit zu tun, dass damit die Komplexität reduziert wird. Es ginge vielleicht auch als Stackmachine, der Vorteil wäre dabei nur minimal oder es wäre sogar langsamer. Soetwas wie verteckte Reservern die durch ein verändertes Programmiermodell freigeschaltet werden könnten gibt es nicht. Das zeigt der oben abgedruckte Python Sourcecode. Die Funktionsweise der kompletten Virtuellen Maschine ist dort als Sourcecode enthalten und man wird sehen, dass in beiden Fällen man nicht so viel optimieren kann. Man muss zwangsläufig zuerst eine Speicherzelle auslesen, dann die zweite Auslesen und das Ergebnis berechnen. Klar, auf echter Hardware kann man die Abläufe parallelisieren, aber im Python Programm ist es egal. Die Anzahl der Berechnungsschritte bleibt gleich.

Nach meiner Recherche ist der extrem niedrige Stromverbrauch des GA144 Prozessor auf andere Dinge zurückzuführen. Einmal die Tatsache dass dort kein externer RAM vorhanden ist. Der RAM benötigt in modernen Computer bereits 5 Watt und mehr an Strom, ist also eine elementare Größe. Und zweitens die Tatsache, dass ein Forth Prozessor nicht den vollständigen x86 Befehlssatz abbildet, er also kein vollwertiger Prozessor ist, sondern mehr Ähnlichkeit mit einem DSP Digital Signal Prozessor hat. Böse formuliert, ist der GA144 nicht turing-mächtig. Was natürlich eine Übertreibung ist, weil man natürlich sehr wohl ihn in Forth programmieren kann, nur wenn man echte Betriebssysteme wie Linux darauf ausführen will, braucht man vorher noch einen C to forth Aufsatz welcher die Geschwindigkeit massiv reduziert. Anders gesagt würde man einen fairen Vergleich durchführen bei dem der GA144 mit RAM ausgestattet ist und die selben Programme ausführt wie ein ARM Prozessor läuft der Stromverbrauch ungefähr auf das selbe hinaus. Der behauptete Vorteil von Stackprozesosren basiert auf einer Mischung aus Aberglauben und Wunschdenken. Genauer gesagt wird versucht Komplexität wegzudefinieren, indem man den Befehlssatz reduziert und behauptet man könnte auch ohne Betriebssystem einen Computer betreiben.

ZUKUNFT
Worum es wirklich geht ist nicht die reine Performance einer Stackmachine, sondern Optiemierungspotenzial sehe ich in der Synthese von Virtuellen Machinen. Im obigen Beispiel wurde sie manuell programmiert, vermutlich könnte man auch eine Meta-Ansatz wählen, bei dem man die virtuelle Machine für eine beliebige Sprache on-the-flx generiert. Also dass man sowohl für Python, Java und C# jeweils die selbe virtuelle Maschine nutzt. Das Konzept einer virtuellen Maschine, genauer gesagt eines Interpreter halte ich für zukufntsfähig, weil es hilft die Edit-Compile-Run-Zyklen in der Softwareentwicklung zu optimieren. Wenn man Prototypen entwickelt benötigt man nicht die maximale Performance eines C++ Compilers, selbst der Python Interpreter ist für die meisten Anwendungen viel zu schnell. Der Flaschenhals ist die Softwareerstellung, also wieviel Lines of Code ein Programmierer am Tag schreiben kann. Und wenn man nicht permanent auf Compile klicken muss sondern nur einen Knopf für Run hat, erhöht sich diese Maßzahl.

Nochmal zurück zur Forth Community und deren Vorstellung von Minimalismus. Laut der dort herschenden Ideologie bedeutet Minimalismus:
– kleine Codegröße des Forth Systems
– wenig Transistoren auf dem Stackcomputer
– geringer Stromverbrauch bei der Ausführung

Minimalismus wird als technisch definiert in dem Sinne, dass versucht wird die Ressourcen an verbautem Silizium und in Anspruch genommene Wattzahl zu minimieren mit der Vorstellung darüber ein effizientes System zu bekommen. Demgegenüber werden Ansätze abgelehnt, bei dem eine CPU 100 Watt schluckt und wo Programme im Umfang von 2 Gigabyte verwendet werden. Also das was heutzutage als Mainstream Computing bekannt ist. Meiner Ansicht nach ist der angestrebte Minimalismus der Forth Community eine Sackgasse, weil die Anzahl der verbauten Transistoren oder der Codeumfang nur eine Größe unter vielen ist und ökonomisch gesehen unwichtig ist. Das beste Beispiel dürfte wohl der Rasberry PI Computer sein, bei dem Gigabyteweise RAM Verbaut ist,gleichzeitig der Verkaufspreis jedoch sehr niedrig ist. Besser ist es, Minimalismus allein auf ökonomische Kenngrößen festzumachen, also was die Hardwarekosten sind und was die Softwarentwicklungskosten sind. Wenn wie beim Rasberry PI die Hardware fast umsonst verkauft wird, und man sich das fertige Betriebssystem komplett gratis aus dem Internet ziehen kann ist dieser Computer Minimalismus pur, selbst wenn der Hauptspeicher stolze 1 Gigabyte beträgt und die Zahl der verbauten Transistoren oberhalb von 100 Millionen liegt.

Advertisements

ForthOS ausprobiert

Das ForthOS Iso Image liegt auf http://www.forthos.org/install.html zum Download bereit. Um es zu starten muss man in CentOS vorher noch qemu plus kvm installieren. Dann noch schnell eine virtuelle Festplatte erzeugen und ForthOS hochfahren:

yum install qemu qemu-kvm
qemu-img create -f qcow2 hda.img 10G
qemu-system-x86_64 -hda hda.img -cdrom forthos.iso -boot d -m 1024 -enable-kvm -smp 2

Nach dem booten erhält man einen Forth Prompt auf dem man Forth Code eintippen kann, also „1 1 + .“ um eine Aufgabe zu rechnen. Leider geht im Hintergrund die CPU Belastung auf 100% hoch. Es ist unklar ob es sich dabei um einen Fehler handelt oder das ForthOS in Wirklichkeit ein böser Virus ist, der die CPU Zeit klauen will. Weitere Funktionen wie eine GUI habe ich in der Software nicht entdecken können.

OSKit
Nachdem das ForthOS nicht so funktioniert hat wie erhofft, bleibt Zeit noch etwas über das OSKit zu sagen. Zugegeben, ich habe das Projekt erst heute entdeckt, das Paper aus dem Jahr 2002 trägt den Titel „The oskit the flux operating system toolkit 0.97“ und wurde auf https://www.cs.utah.edu/flux/oskit/doc/oskit.ps.gz veröffentlicht. Wenn ich das Dokument richtig verstehe ist es ein Meta-Betriebssystem. Es basiert auf dem objektorientierten COM Modell aus dem Hardwaretreiber für Linux, FreeBSD und NetBSD abgeleitet werden. Ferner ist noch eine Virtual Memory Funktion und etwas Security mit dabei. Auch an eine X11 Grafikschnittstelle wurde gedacht. Zumindest nach dem Paper sieht es so aus, als könne man aus OSKit heraus Sourcecode erzeugen der dann für sehr unterschiedliche Betriebssysteme verwendet wird. Am besten sollte man gleichmal Linus Torvalds das Paper zuschicken, weil er sich dann viel Arbeit spart und nicht immer from scratch soviel selber Programmieren muss. Aber vielleicht gefällt ihm ja auch nicht der objektorientierte Ansatz über COM? COM ist ein Standard, der von Microsoft entwickelt wurde. Und dabei war Linux und Windows doch immer getrennt … Sehr merkwürdig das ganze.

Forth ist nicht fett

Manche Verschwörungstheoretiker behaupten, dass Forth eine verfettete Sprache wäre, die viel zu viel Möglichkeiten bereitstellt anstatt zwei drei wichtige Paradigmen anzubieten. Häufig wird das Bild einer vollgefressenen Tonne bemüht die alles in sich reinschaufelt was nicht bei drei auf dem Baum ist um so den Frust zu bekämpfen. Doch das ist nicht war. Forth ist eine extrem schlanke Sprache. Das dort Metaprogramming unterstützt wird ist kein Zeichen von zuviel, sondern sowas ist absolut nötig in der täglichen Programmierpraxis. Auch die Möglichkeit eigene Words anzulegen um den Sprachumfang beträchtlich zu erweitern ist Ausdruck eines minimalistischen Ansatzes. Das sich damit die Komplexität beträchtlich erhöht weil jeder seine eigene Word Datei erzeugt ist nur dummes Gerede. Wenn man „Create does“ richtig einsetzt ist es eine sinnvolle Erweiterung zu einem Forth System. Apropos System. Manche Leute sagen, dass man auch ohne Stack auskommt und sogar ohne lokale Variablen. Aber wie bitteschön will man denn ohne Stack sinnvolle Aufgaben ausführen. Nein, nein der Stack gehört zum absoluten Minimum, der muss einfach sein, sonst fehlt etwas. Ich meine, man kann ja den Stack, die umgekehrte polnische Notation und die fähigkeit als virtuelle Maschine nicht einfach streichen. Dann würde ja nicht mehr viel übrig bleiben, oder? Um halbwegs ansehnliche Programme zu schreiben braucht man einfach eine mächtige Hochsprache wie Forth die nicht nur compilerdirektiven, Präprozessoren und einen Interpreter mitbringt sondern ein eigenes Dateisystem, Plugins für selbstgeschriebene Erweiterungen sowie kleinere Spiele für zwischendurch. Das ist alles sehr schlank gehalten.

Forth ist eine kleine zierliche Sprache und keineswegs eine riesiger Truck der beide Fahrspuren benötigt und der über bestimmte Brücken schon gar nicht mehr drüberfahren darf weil er hoffnungslos überladen ist. Nein, Forth sieht sich dem Minimalismus verpflichtet es enthält daher keine überflüssigen Features wie sie in andernen Sprachen eingebaut sind. Bei C beispielsweise gibt es riesige Bibliotheken mit unmengen an Words, auf sowas kann Forth gut verzichten. Auch gibt es keine komplizierten Anleitungen wie bei Java sondern alles ist sehr spartanisch aufgebaut. Es gibt nur die eine Anleitung und wenn man die gelesen hat kann man sofort anfangen mit dem Programmieren. Es ist also keineswegs so, dass man erst beim Systemadminstrator einen Laufzettel ausfüllen muss nur weil man ein Hello World eintippen möchte. Nein, das geht alles sehr unbürokratisch, Forth ist ein sehr benutzerfreundliches System, insbesondere Bigforth steht im Ruf besonders leicht zu bedienen zu sein. Da ist alles auf einen schlanken Minimalismus hingetrimmt. Das Wort big ist nur eine Anspielung auf Small, was voll und ganz zutrifft.

Forth hat Übergewicht

Forth Anhänger behaupten, dass ihr System klein und schlank wäre. Das liegt daran, dass sie Forth noch nie auf eine Wage gestellt haben. In Wirklichkeit ist das System komplett überfettet. Das mag etwas paradox klingen angesichts von mageren 10 kb RAM die ein aktuelles eforth benötigt, während Micropython erst ab 2 MB RAM überhaupt bootet. Doch Minimalismus misst sich daran ob man auf etwas verzichten kann ohne das Projekt zu gefährden. Wenn man Forth nicht verwendet wie sehr ist dadurch der Erfolg im Robotik-Wettbewerb gefährdet? Richtig, es passiert überhaupt nichts. Man kann genausogut auch C oder Python auf seinem Microcontroller installieren, es gibt keine Nachteile. Ja mehr noch, will man in Forth ein Programm schreiben beispielsweise um auf dem Microcontroller einen Webserver online zu bringen, so sitzt man darüber Wochen ja Monate. In Python reicht ein simpler Befehl aus, und der Server ist online. Insofern ist Python klein und schlank auch wenn es viel mehr Speicher benötigt.

Wer sich mit Forth auskennt hat unzweifelhaft Expertenkenntnisse im Bereich Microcontrollerprogrammierung erlangt. Ist also jedem Python-Newbee der vor 1 Woche zum ersten Mal einen Microcontroller in Betrieb nahm haushoch überlegen. Aber hat er dadurch einen Vorteil? Kann er diese Expertenkenntnisse konkret ins Projekt einbringen oder ist es nicht eher überflüssiger Speck den er sich da angefressen hat und wo weniger mehr wäre? Das schön an Python ist, dass man da überhaupt nichts lernen braucht. Irgendwelche Kenntnisse muss man sich nicht anlesen und was man in einer Anleitung gelesen hat, darf man 2 Minuten danach schon wieder vergessen. Es stört sich keiner daran, Python Kenntnisse sind entbehrlich. Forth hingegen baut auf einer kontinuierlichen Lernerfahrung auf. Und wer nicht ein bestimmtes Tutorial gelesen hat, sieht kein Land mehr. Genau genommen zwingt Forth seine User dazu, sich permanent weiterzubilden, und alles bis ins Detail zu verstehen. Diese Lernspirale ist der reinste Luxus. Wer die Zeit und die Geduld hat sich auf Forth einzulassen — herzlichen Glückwünsch. ABer auch onne Forth findet die Micromouse den Weg durchs Labyrinth. So wichtig ist das System nicht, dass man es näher studieren müsste. Der Vorteil eines schlanken Systems lautet, dass man Platz frei hat um sich auf neues einzulassen. Bei Forth ist das leider nicht gegeben. Forth verlangt die gebündelte Aufmerksamkeit, selbst wenn man nur eine LED blinken lassen will. Und wenn sein Forth System noch kleiner machen will, muss man sich nochmehr anstrengen.

Othello in Forth

Im folgenden wird beschrieben wie man in der Programmiersprache Forth das Reversi / Othello Spiel programmiert. Anstatt den Forth Sourcecode selbst einzugeben, wird ein C-to-Forth Konverter verwendet, und zwar dieser hier:
https://github.com/dmedinag/C-to-Forth-compiler

Und anstatt das Othello Spiel selber zu programmieren, wird — richtig geraten — der folgende Code aus einem Github Projekt https://github.com/davidrobles/othello-c verwendet. Da sag nochmal einer, dass die „Plagiatsaffäre Guttenberg“ keine echte Wissenschaft gewesen wäre …

Jetzt wird die C-Datei nach Forth konvertiert:

cat Othello.c | ./c2 > Othello.fs

was natürlich mißlingt, was am C to Forth Konverter liegt weil der schlampig programiert wurde und nicht mit Pointern klarkommt. Das macht aber nichts, weil auch so klar ist wie das fertige Forth Programm aussehen wird. Und zwar besteht es aus folgenden 17 Subroutinen:

void init_othello()
bool is_game_over(Othello *othello)
cell_type *get_board(Othello *othello)
void set_current_board(Othello *othello, uint64_t bitboard)
void set_opponent_board(Othello *othello, uint64_t bitboard)
void print_bitboard(uint64_t board)
int *moves_array(Othello *othello)
void make_move(Othello *othello, int move)
int number_of_moves(Othello *othello)
void calculate_moves(Othello *othello)
unsigned int count_bits(uint64_t n)
uint64_t move_bitboard(Othello *othello, int move)
uint64_t get_current_board(Othello *othello)
uint64_t get_opponent_board(Othello *othello)
uint64_t empty_board(Othello *othello)
int current_player(Othello *othello)
void print_board(Othello *othello)

die in Forth kein void und bool als Anfang haben sondern mit einem Doppelpunkt eingeleitet werden, also so:

: init_othello
: is_game_over
: get_board
: set_current_board

usw.

Die Problematik ist, dass es keinen Unterschied macht ob der Code in Forth oder in C geschrieben steht er bleibt in beiden Fällen unübersichtlich. Und zwar deshalb, weil Othello ein anspruchsvolles Spiel ist, bei dem man viel berechnen muss wie das Spielfeld, erlaubte Züge, Eingaben des Users, eine rudimentäre GUI usw, und das eigentlich 17 Words in Forth dafür nicht ausreichend sind sondern man sehr viel mehr benötigen würde um die Sache richtig zu machen. Aktuell hat das von mir geforkte github Projekt 413 Zeilen Code und droht bereits arg unübersichtlich zu werden. Schuld daran ist jedoch nicht C oder Forth sondern die Problematik liegt in der prozeduralen Programmierung. Eigentlich müsste man das ganze objektorientiert aufziehen, also schön mit UML Diagrammen, Vererbung und Use-Case Diagrammen herumspielen und das alles in eine Dokumentation packen. Ich will damit andeuten, dass sich grundsätzlich Forth, C und jede andere Sprache ausgezeichnet eignen um damit leistungsfähige Programme zu erstellen, dass der Flaschenhals jedoch immer der Programmierer ist der im Zweifel das Problem nicht genau verstanden hat, sich keine Mühe gibt oder sich mit Smalltalk nicht gut auskennt.

Sind Stackbased Parser noch zeitgemäß?

Die gute alte Schule der Informatik ist auf eine Sache besonders stolz: den Stack. Damit ist jene Datenstruktur gemeint womit man rekursive Abstiege formuliert. Man kann mit einem Stack sowohl Graphen durchsuchen, Compiler entwickeln als auch High-Level Plannung durchführen. Komischerweise umgibt den Stack bis heute eine Aura des mystischen. Die großen Vordenker der heutigen Software wie Donald Knuth und Chuck Moore werden den Stack kennen und sie können auch seine Mächtigkeit beschreiben, aber es gibt etwas was sie nicht wissen: wo die Grenzen der Stackbasierten Programmierung liegen. Ein Stack ist eine Datenstruktur welche aus der Mathematik entlehnt ist und womit man abstrakte Probleme beschreiben kann. Sein Nachteil ist seine Einfachheit. Damit ist gemeint, um einen Stack in Software zu implementieren braucht man selten mehr als 100 Lines of Code. Wenn man zum Parsen der esoterischen Brainfuck Sprache einen Stack benötigt, sind es sogar noch weniger Zeilen. Und genau hier liegt sein Nachteil. Genauer gesagt nicht der Stack, sondern ein stackorientiertes Softwareengineering ist das Problem.

Leute welche den Stack bevorzugen, pflegen zugleich einen sehr knappen Programmierstil. Sie glauben dass man Programme die länger sind als 1000 Lines of Code reduzieren könne. Und sie betrachten Programmcode im Umfang von 1 Mio Lines of Code und mehr als Ausdruck von Dummheit. Das da also Programmierer das Problem nicht wirklich verstanden hätten und endlos viel Code schreiben. In Wahrheit ist es jedoch so dass große Probleme viel Code benötigen und das Programme die kurz sind auch nur sehr einfache Probleme lösen können. Anders formuliert, braucht man einen Parser für Brainfuck, mag ein 100 Zeilen Programm was einen rekursiven Stack verwendet ausreichend sein. Will man hingegen Pascal oder gar Java Parsen wird man es nicht schaffen in 100 Lines of Code und nur mit einem Stack das Problem zu lösen. sondern solche Dinge erfordern zwingend eine hohe Anzahl Lines of Code, und Stacks nehmen dabei nur einen sehr kleinen Teil möglicher Datenstrukturen ein.

Am einfachsten kann man die Schwächen eines Stacks im Bereich Compilerbau erläutern. Im einfachsten Fall besteht ein Compiler aus einem rekursiven Parser der eine Grammatik verwendet um Sourcecode in Maschinensprachen-Opcodes zu übersetzen. Nur, solche Aufgabenstellungen gibt es heute so nicht mehr. Im Regelfall will man Compiler haben, die Hochsprachen übersetzen können, und die auch noch Optimierungen vornehmen. Dafür reicht ein simpler rekursiver Parser nicht mehr aus. Man benötigt stattdessen eine komplette Compilerpipeline, also wo mehrere Module zusammengefügt werden. Um diese zu programmieren wird man im Regelfall auf Methoden des Softwareengineerings zurückgreifen also UML, objektorientierte Programmierung usw. Wenn man hingegen den Stack als einzig legitimes Ausdrucksmittel zulässt wird man vor den Herausforderungen der Gegenwart scheitert. Man kann damit zwar Probleme lösen, allerdings sind es selbstgeschaffene die sich so nicht stellen weil sie zu simpel sind.

Kommen wir nochmal zurück zu Brainfuck. Es handelt sich um eine sehr elegante Programmiersprache. Und es stellt einen gewissen akademischen Reiz da, sich damit näher zu beschäftigen. Ja, man kann über Brainfuck sogar komplette Dissertationen verfassen und sie erfüllen auch die Anforderungen der ehrwürdigen ACM Gesellschaft. Nur, die Informatik wird man damit nicht voranbringen. Brainfuck ist keine echte Programmiersprache, sondern es ist eine Modellsprache. Will man echte Software auf echten Computern programmieren wird man C++ oder Java verwenden. Das sind Sprache die im Real Life verwendet werden.

Von einem gewissen Standpunkt aus betrachtet macht auch C++ nichts anderes als Brainfuck. Beides sind turing-mächtige Sprachen. Der Unterschied ist jedoch, dass eine Problemlösung innerhalb der Brainfuck Welt keinen Wert besitzt. Meist ist die Lösung ohnehin bekannt. Es ist vergleichbar als wenn man ein Sudoko Rätsel löst. Es ist zwar ein netter Zweitvertreib aber es handelt sich um ein künstliches Rätsel, was so im echten Leben nicht existiert. Es ist zu einfach, der Anspruch an sich selber ist zu niedrig. Ich will damit sagen, dass Leute die sich mit Stackmachinen näher beschäftigen, ernsthafte Informatik aufgegeben haben und sich mit Scheinproblemen beschäftigen. Sie tun dies, weil sie mit richtigem Software-engineering überfordert sind, weil sie die dort vorhandene Komplexität nicht handeln können. Das ist ungefähr vergleichbar als wenn Gamer nicht gegen richtige Gegner kämpfen sondern sich ein Spaßlevel bauen, wo sie gegen extrem leicht zu besiegende Bots kämpfen um wenigstens ein kleines Erfolgserlebnis zu bekommen.

Es gibt in der Informatik-Literatur dazu sehr viele Paper. Meist geht es darin, wie man Towers of Hanoi mit einer Stackmachine spielt oder wie man einen Übersetzer für eine fiktive Kusntsprache programmiert. Die Gemeinsamkeit ist dass zwar oberflächlich Informatik betrieben wird, das ganze aber sehr akademisch und trocken daherkommt. Es ist in sich alles richtig, aber das ganze bleibt ohne Wert. Es handelt sich um selbst geschaffene Probleme mit dem Ziel vorher bekannte Problemlösungstechniken erneut anzuwenden um sich und der Welt zu zeigen, wie es gemacht wird. Manche sagen dazu, dass die Probleme billig sind.

Zugegeben, ein sehr hartes Urteil. Aber die Informatik basiert nicht so sehr auf bestimmten Lösungsstrategien, sondern worum es in der Informatik geht ist die Größe Lines of Code. Aus welchem Grund auch immer gibt es einen direkten Zusammenhang zwischen der Komplexität einer Aufgabe und der benötigten Menge Codezeilen. Damit ist gemeint, dass Sourcecode der lang und umfangreich ist, einen höheren Wert besitzt als Code der klein und übersichtlich ist. Was in diesem Code drinsteht, welche Algorithmen und Datenstrukturen verwendet werden, ist zweitrangig. Will man die Mächtigkeit von Computern und Software ausweiten muss man den Umfang des Sourcecodes erhöhen.

Diese Erkenntnis ist nicht theoretisch fundiert, sondern es handelt sich um eine Erkenntnis, wenn man reale Softwareprojekte beobachtet. Man kann beispielsweise sehen, dass der Umfang von MS-windows im Verlauf der Jahre angestiegen ist. Und das objektiv betrachtet die Software heute leistungsfähiger ist als jemals zuvor. Diesen Zusammenhang zu leugnen macht keinen Sinn. Es scheint eine Art von Naturgesetz zu sein. Das erstaunliche aus Sicht der akademischen Informatik ist, dass der Windows Sourcecode keineswegs aus rekursiven Minimalautomaten besteht, die sich gegenseitig in einem Bootstrapping Prozess aufrufen, sondern dass das ganze eine ökonomisch motivierte Fleißarbeit ist, vergleichbar mit dem was Aschenputtel in dem gleichnahmigen Märchen macht. Also nicht so sehr mit Genie an die Aufgabe herangehen, sondern mit stetiger Wiederholung.

Und das dürfte wohl der wichtigste Unterschied sein, zwischen der alten Garde der Informatiker wie Donald E. Knuth welche zweifelsohne geniale Denker waren und heutigen Programmierern, die sich damit brüsten wieviel Codezeilen sie schon bei github hochgeladen haben. Heutige Programmierer sehen sich eher als fleißige Arbeiter die industriell Software für die Masse herstellen. Wo es egal ist, wenn der Code nicht perfekt ist, weil er ohnehin in 2 Monaten durch besseren Code ersetzt wird. Und das im Extremfall noch nichtmal von ihnen selber, sondern von jemand anderes, der noch dazu eine komplett andere Programmiersprache verwendet.

FORTH
Nachdem ich den Trend in Sachen Software-Entwicklung beschrieben habe, mag man vielleicht denken dass in dieser Welt kein Platz wäre für eine Minimal-Sprache wie Forth. Komischerweise aber gerade doch. Natürlich weiß jeder, dass echte Softwareprojekte aus vielen Codezeilen bestehen und selten in Forth geschrieben werden, aber umso interessanter ist es, dazu einen Ausgleich zu finden und sich dann eben doch wieder mit dem genauen Gegenteil zu beschäftigen. Also darüber nachzugrübeln wie man einen Primzahl-algorithmus mit möglichst wenig Forth-Statements formuliert. Als Denksportaufgabe sozusagen um eben doch ein wenig das eigene Genie zu fördern. Es gibt also einerseits riesige Programmprojekte mit Millionen lines of Code und auf der anderen Seite die Minimalsprachen wo man sich selber beschränkt um in theoretische Dimensionen vorzudringen. Forth lässt sich am ehesten als minimalistische Programmiersprache vergleichen die anders als Brainfuck zusätzlich noch Hardware und Terminal-Fenster beinhaltet. Was die Forth Community mit Vorliebe tut ist hocheffiziente CPU-Cores zu entwerfen und darüber zu diskutieren wie man auf diesen sehr kompakten Programmcode ausführt. Also einen Race to the bottom durchführt.

Aus Sicht der Anwendungsorientierten Informatik wo Standard x86 CPUs und Standard-Programmiersprachen eingesetzt werden mag das befremdlich wirken, aber im Grunde ergänzt sich Forth und die Mainstream-Inforamtiik sehr gut. Jede Seite macht das was sie gut kann und man entwickelt sich immer weiter auseinander. Das heißt, nicht integration sondern Spaltung ist das Ziel. Bis man sich nichts mehr zu sagen hat …

In https://bernd-paysan.de/b16-presentation.pdf erläutert Bernd Paysan die Motivation hinter dem b16 Prozessor. Auf Seite 10 der Folie wird deutlich, warum es bei Forth sogenannte Words gibt und nicht Befehle wie in einer Hochsprache: weil das die minimalistische Variante ist. Ein Word kann man sich als Sprunglabel vorstellen. Wenn man plant eine möglichst kompakte Sprache zu verwenden, ist das die beste Lösung. Auch die anderen Eigenheiten von Forth wie die Zeichen „. ; @ !“ sind keineswegs zufällig entstanden, sondern sind Ergebnis eines Minimalistischen Ansatzes. Auf Seite 12 der gleichen Powerpoint Präsentation findet sich dann ein Schaubild des kompletten b16 Prozessors. Im Grunde ist das eine Art von Turing-Maschine in Hardware. Also ein Modellcomputer anhand derer man theoretische Informatik erläutern kann.

Der Forth Metacompiler

Nachdem in einem früheren Blogpost bereits auf ein github Projekt verlinkt wurde bei dem mittels Bison ein C-to-forth Compiler erzeugt wurde, stellt sich die Frage ob man das ganze nicht noch effizienter machen kann. Bison ist ein Unix-Programm was aus einer „.y“ Datei eine „.c“ Datei erzeugt. In der „.y“ Datei befindet sich die Language Grammar und in der „.c“ dann der fertige Parser. Etwas ähnliches gibt es auch in Forth. In dem Paper

„T.A. Invanco: User definable language interface for Forth“, http://soton.mpeforth.com/flag/jfar/vol6/no1/article2.pdf

Wird ein Forth-Metacompiler beschrieben. Er entspricht vom Funktionsumfang ungefähr Bison/Yacc. Die Idee lautet aus einer Sprachdefinition eine Abstract Maschine zu erzeugen. Will man Pascal Code parsen benötigt man eine andere Sprachdefinition als wenn man Java oder C Code parsen möchte. Generell dürften solche Metacompiler der Schlüssel zur Mächtigkeit von Forth sein. Weil man damit nicht länger in Forth selber programmieren muss (also eigene Words definiert, kryptische IF Statement eintippt, sondern man stattdessen Hochsprachen wie Java, C++ oder was auch immer verwendet. Voraussetzung ist lediglich, dass man die Grammar dafür hat. Was also für die Java Datei den Abstract Syntax Tree erzeugt und diesen dann nach Forth übersetzt.

Zugegeben, das ganze ist etwas gewagt. Weil es bedeutet, dass man es sich mit der UNIX Community verscherzt. So nach dem Motto: wir wollen nicht länger mit Bison/Yacc herumspielen sondern wir haben etwas besseres, was sehr viel mehr kann. Bison/Yacc sind noch eine Stufe oberhalb der GNU C Compiler angesiedelt. Mit GNU C wurde UNIX programmiert, aber mit Yacc wurde der erste Compiler erzeugt, der C Code in Assembly übersetzen konnte.

Anders formuliert, der schönste C-Sourcecode ist witzlos wenn man ihn nicht nach Machinencode übersetzen kann. Man braucht dazwischen immer einen Compiler. Üblicherweise ist die Unix/LInux Commuhity von Bison/Yacc hochgradig abhängig. Es ist gewissermaßen der zentrale Knoten der immer benötigt wird. Wenn es gelingt, dazu einen Bypass zu legen, hätte man einerseits C-Compiler die jedoch unabhängig von UNIX funktionieren. Und mehr noch, mit einem Forth Metacompiler kann man nicht nur C übersetzen sondern auch Pascal, Java, Python und was auch immer. Diese Sprache sind es, auf die es ankommt, weil man in diesen Hochsprachen sehr gut Algorithmen formulieren kann, also Hello World Programme, Betriebssysteme oder was auch immer.

Nochmal zurück zu dem oben verlinkten Paper, die gute Nachricht lautet, dass der darin vorgestellte „META-79“ im Anhang als Forth-Listing abgedruckt ist. Man kann das ganze als Gegenmodell zu Bison bezeichnen. Die schlechte Nachricht lautet, dass außer in diesem Paper das ganze nirgendwo sonst thematisiert wurde. Und Beispiel-Grammar-Files für Python, C und Java gibt es auch keine.

WARUM?
Angesichts von soviel Fachbegriffen wie Meta, Grammar und Parsergenerator stellt sich die Frage, wozu man das alles braucht. Die Antwort lautet, dass man Hochsprachen wie C auf einer phyischen Stackmachine ausführen möchte. Stackmachinen wiederum lassen sich sehr effizient in Silizium bauen und man kann sie parallelisieren. Dadurch erhält man extrem leistungsfähige Gaming-PCs. Also Systeme die nicht nur müde 15 fps anzeigen sondern 120 fps in 4K Auflösung darstellen, ohne dass der Lüfter auch nur hochdreht.

Mit den heute verfübaren C++ Compilern und Intel CPUs ist das nicht machbar. Deshalb ist es Zeit für etwas neues. Etwas, das wirklich Druck macht, was richtig fett ist. Also nicht irgendwelche klein klein Optimierungen, wo die neue Intel CPU um 7,23% schneller ist als die alte CPU sondern wo man in den Sessel hineingedrückt wird weil das System so wahnsinnig schnell ist.

LITERATUR
In der Literatur wird der Begriff „Forth Metacompiler“ in einem anderen Kontext verwendet. Stattdessen ist der korrekte Begriff „Parser Generator in Forth“, „Is Forth code compact? A case study“ http://www.complang.tuwien.ac.at/anton/euroforth/ef99/ertl99.pdf vergleicht mehrere davon und erwähnt bereits in der Einleitung dass der kompakteste aus 14 Zeilen Code besteht, geschrieben in welcher Programmiersprache? Richtig, diejenige Sprache die wirklich böse ist. Etwas sachlicher muss man jedoch festhalten, dass Parsergeneratoren das Herzstück sind wenn man programmiert, sie sind noch wichtiger als Betriebssysteme. Ein Parsergenerator plus die passende Sprachdatei führt dazu, dass man eine Hochsprache wie C in Maschinensprache übersetzen kann. Letztlich dürfte es das sein, worum es geht. Die Forth Syntax der umgekehrten polnischen Notation mag ganz nett sein für kurze Programme, doch was wirklich angesagt sind dass sind Interpreter die Java und Python auswerten können. Das ausgerechnet das minimalistische Forth wovon es sogar eine Version für den Lieblingscomputer C-64 gibt, dazu eine Plattform bereitstellt überrascht ein wenig. Es bedeutet vereinfacht ausgedrückt, dass man auf dem C-64 nicht nur in C++ programmiert, sondern auch den ersten C++ auf dem C-64 programmiert. Also nix mit Crosscompilation, sondern man schreibt sich seinen Compiler selber um damit dann größere Projekte zu starten.