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.

Advertisements

24 thoughts on “Der Forth Metacompiler

  1. Noch besser ist ein in die Sprache eingebetteter Parsergenerator. Das gibt es schon lange bei verschiedenen Lisp Dialekten. Auf die einsame semantische Spitze getrieben wurde es bei Dylan. Leider haben sich diese Sprachen in der C / Java Welt nicht durchsetzen können.

    Like

  2. Texte selbst auf deutschen Web-Seiten nur noch in Englisch, Google 2017, Facebook, Windows 10 und Apple’s Developer Program.
    Kein Schwein haette seinerzeit einen verhaeltnismaessig teuren Sharp Pocket-Computer gekauft, haette man sich bei Sharp anmelden und blechen muessen um ihn programmieren zu koennen (Assembler ging nebenbei auch, nicht nur Basic).
    Ueberwachung und Steuerung der Rechner und Smartphones durch irgend welche anonymen Hansels, die meinen sie koennen machen was sie wollen.
    Naja, koennen sie ja auch – die Leute finden es ja geil.
    Ein neuer C64 sollte der Raspberry sein. Aber was tun die “neuen Programmierer”? Sie installieren ihre “PC-Software” drauf und nach ein paar Stunden Fun fliegt das Ding inne Ecke oder dient bestenfalls als Medienspieler.
    Mich wundert das nicht.
    So geht das nicht Leute!
    Ich wusste es immer: Ich bin locker mal 20 Jahre zu spaet geboren …und mit zu wenig Zaster… naja ueberhaupt und insgesamt in den falschen Umstaenden.
    Soll bloss kein Petrus an der Himmelspforte fragen, was ich in meinem Leben geleistet haette. Dem hau ich sowas von …aufe 12…
    Manchmal ist weniger einfach mehr.
    Und deshalb… und so komme ich bedingt zum Thema… gehe ich nun back to the Roots.
    Ich steige aus!
    FORTH als eigenstaendiges Betriebssystem OHNE Ramsch-internet und OHNE buntes dafuer um so ueberladeneres Gedoens… einsam in meinem Keller!
    DAS IST MEIN LEBENSZIEL!
    Und dabei bedauere ich es noch ausserordentlich, dass ich mir keinen Prozessor bauen kann – aus Waescheklammern! Sehr sehr schade!
    Keinen Bock mehr auf den ganzen UEBERLADENEN Ramsch UND AUF DAS SICH-ABHAENGIG-MACHEN VON DEN LAUNEN IRGENDWELCHER AKTIENBONZEN UND PUSCHEL-DESIGNERN!
    Mich nervt die Zeit einfach nur noch ab!
    Ach ja, eine Orgel! Ich kauf mir eine Orgel! Eine alte Farfisa oder sowas… im Buchenholzgehaeuse und mit 20 Klaengen statt 500 oder 1000, dafuer aber robust und mit einem Schalter/Regler fuer jede Funktion statt dieser elenden Menues und Touch-Screens und im Lautsprecher hoert man dann das Piepsen von der Hintergrundbeleuchtung – was ein Krampf!
    …durchatme…
    Tut mir leid… Ich hatte wieder eine nervige Google-Suche hinter mir – gar nicht gut fuer meinen Blutdruck oder den Kommentarbereich eines zufaellig gefundenen Blogs… wieso muss dieser hier auch ausgerechnet TrollHeaven heissen… WIE SOLL MAN SICH DA BEHERRSCHEN?! :-)
    Aber wirklich – genau SO fuehle ich mich:

    (naja die Kinder koennen ja nix dafuer.)
    Und auf YouTube steht jetzt:
    “Wir haben fleißig am neuen YouTube gearbeitet, um es besser als je zuvor zu machen. Jetzt ausprobieren.”
    BLOSS NICHT! KEIN INTERESSE! Eh nur wieder irgend ein Zeuch!
    …bevor ich mich wieder von vorn aufrege:

    Parsergeneratoren werden auch gerne mal ueberbewertet… um noch etwas zum Thema zu schreiben. :-)

    Like

  3. Vorweg: Die ersten Teile der Orgel sind da – einmanualig tut’s das schon mal. Ich mach ernst und steig aus dem Ramschkrampf aus.

    Bedingt durch gelangweiltes Warten und bezueglich Gramatik…

    Vielleicht ein nettes Sonntagsspielzeug, auch wenn heute nur ein oller Mittwoch ist.

    Eine Beschreibungssprache fuer Zeit-/Datums-/Preis-/sonstige Zahlenansagen in allen(?) Sprachen dieser Welt, die ausschliesslich mit Hex-Ziffern auskommt (ganz unten allerdings eine lesbarere Darstellung – dort wird es dann auch nochmal besonders witzisch).
    Die Anzahl der Regeln und Regellisten (siehe unten) ist allerdings etwas eingeschraenkt; man muss bei komplexeren Gramatiken ggf. mehrere Regelwerke nacheinander anwenden.
    Jedenfalls sollte das auch mit sehr einfachen Mikrocontrollern mit sehr wenig Speicher einsetzbar sein (na gut, 256 Byte wird nicht ganz reichen, 64 KB braucht man aber auch nicht; denke mit 8 KB ziemlich sicher und mit 4 KB und zusaetzlichen Hardware-Oszillatoren koennte man eine sprechende Uhr bauen – vielleicht schafft es einer auch nur mit 2 KB, wohl etwas knapp, keine Ahnung).

    1 Ein Regelwerk besteht aus einer oder mehr Regellisten und einer abschliessenden Hexadezimalziffer Fhex sowie, falls erforderlich, einer weiteren Ziffer Fhex um das letzte Byte auszufuellen. Die einzelnen Regellisten (ausser der ersten) muessen NICHT an einer Bytegrenze beginnen.
    1.1 Eine Regelliste besteht aus einer oder mehr Einzelregeln oder kurz Regeln.
    1.1.1 eine Einzelregel enthaelt links ein Muster und rechts eine Ersatzsequenz (kurz Sequenz), die die Ausgabe beschreibt wenn das Muster zur Eingabe passt. Abgeschlossen wird eine solche Liste mit der Hex-Ziffer Fhex anstelle eines Musters.
    1.1.1.1 Ein Muster besteht aus den Hex-Ziffern 0hex bis 9hex und Ahex bis Ehex und wird mit Fhex abgeschlossen. Die laenge des Musters muss mit der Laenge der Eingabe uebereinstimmen.
    1.1.1.1.1 Die Ziffern 0hex bis 9hex muessen mit der Eingabe an den betreffenden Stellen uebereinstimmen.
    1.1.1.1.2 Die Ziffern Ahex bis Ehex dienen zur Angabe von Gruppierungskonstrukten; die zugehoerigen Eingabeziffern werden in den Erfassungsvariablen A bis E lokal gespeichert.
    1.1.1.2 Eine Ersetzungssequenz besteht aus einer Folge von 0 oder mehr Wortnummern im Bereich 00hex bis 7Fhex und/oder aus einem Paar Erfassungsvariable:Subregellistennummer, erstere im Bereich von Ahex bis Ehex, letztere im Bereich 0hex (Startregelliste) bis Fhex (ein solches “Paar-Byte” liegt also im Bereich von A0hex bis EFhex). Abgeschlossen wird die Ersetzungssequenz durch Fhex. Die noch zur Verfuegung stehenden Bytes 80hex bis 9Fhex sind reserviert/nicht definiert.
    1.1.1.2.1 Bei einem passenden Muster werden Wortnummern einfach in die Ausgabe kopiert.
    1.1.1.2.2 Eingetragene Regelelistennummern in der Ersetzungssequenz werden angewendet mit dem jeweiligen Inhalt der angegebenen Erfassungsvariablen als Eingabe und das Teilergebnis durch die Anwendung der Subregelliste selbst in die Ausgabe geschrieben.

    regelwerk ::= regelliste {regelliste} F [F]. // evtl. zweites F um letztes Byte zu Fuellen
    regelliste ::= regel {regel} F.
    regel ::= muster sequenz.
    muster = /[0-9A-E]+F/. // Musterlaenge == Eingabelaenge
    sequenz ::= {wort | paar} F.
    wort ::= /[0-7][0-9A-F]/. // 80hex bis 9Fhex reserviert
    paar ::= erfassungsvariable subregellistennummer.
    erfassungsvariable ::= /[A-E]/.
    subregellistennummer ::= /[0-9A-F]/.

    Beispiel fuer eine sprechende Uhr.

    Es empfiehlt sich die Nibble-Starrtpositionen der einzelnen Regellisten in einer entsprechenden Verzeichnisliste zu halten, wobei der erste Eintrag im Verzeichnis die Position der Startregel (nicht zwingend, aber empfohlenerweise = 0) ist.
    Die Ausgabe muesste hier noch von einem TTS-System ins Phonetische uebersetzt werden; man koennte auch direkt die Phoneme samt Betonung in den Wortnummern codieren (wuerde hier aber zu unuebersichtlich).
    Weiter unten findet sich noch eine abstraktere (lesbarere/schoenere) Quelltextdarstellung.

    // Woerter

    // .enum null eins zwei drei vier fuenf sechs sieben acht neun // 00hex bis 09hex
    // .enum zehn elf zwoelf ein zig ssig sech sieb zwan _und_ // 0Ahex bis 13hex
    // .enum _uhr_ // 14hex

    // Regel #0 (uhrzeit = Startregel)
    aabbf a1 14 b2 f // a@stunde _uhr_ b@minute
    f

    // Regel #1 (stunde)
    01f 0d f // ein
    aaf a3 f // a@zahl
    f

    // Regel #2 (minute)
    00f f // keine Ausgabe
    aaf a3 f // a@zahl
    f

    // Regel #3 (zahl)
    0af a5 f // a@ziffer
    10f 0a f // zehn
    11f 0b f // elf
    12f 0c f // zwoelf
    16f 10 0a f / sech zehn
    17f 11 0a f // sieb zehn
    1af a5 0a f // a@ziffer zehn
    2af a4 18 0e f // a@spezial zwan zig
    3af a4 03 0f f // a@spezial drei ssig
    abf b4 a5 0e f // b@spezial a@ziffer zig
    f

    // Regel #4 (spezial)
    0f f // keine Ausgabe
    1f 0d 13 f // ein _und_
    af a5 13 f // a@ziffer _und_
    f

    // Regel #5 (ziffer)
    0f 00 f // null
    1f 01 f // eins
    2f 02 f // zwei
    3f 03 f // drei
    4f 04 f // vier
    5f 05 f // fuenf
    6f 06 f // sechs
    7f 07 f // sieben
    8f 08 f // acht
    9f 09 f // neun
    f
    f // Fuell-Nibble 185 + 1 = 186 Nibbles ( 93 Bytes)

    Ein lesbarerer Quelltext koennte dann so aussehen (hier — fuer Kommentare):

    = 0 — Enum-Start
    + null eins zwei drei vier fuenf sechs sieben acht neun
    + zehn elf zwoelf ein zig ssig sech sieb zwan _und_
    + _uhr_

    / uhrzeit — Startregel

    : uhrrzeit
    aabb a@stunde _uhr_ b@minute

    : stunde
    01 ein
    aa a@zahl

    : minute
    00 — keine Ausgabe
    aa a@zahl

    : zahl
    0a a@ziffer
    10 zehn
    11 elf
    12 zwoelf
    16 sech zehn
    17 sieb zehn
    1a a@ziffer zehn
    2a a@spezial zwan zig
    3a a@spezial drei ssig
    ab b@spezial a@ziffer zig

    : spezial
    0 — keine Ausgabe
    1 ein _und_
    a a@ziffer _und_

    : ziffer
    0 null
    1 eins
    2 zwei
    3 drei
    4 vier
    5 fuenf
    6 sechs
    7 sieben
    8 acht
    9 neun

    Ein Uebersetzer und Interpreter ist noch zu schreiben und hoffe keine Fehler gemacht zu haben – denn ich tippe das gerade so runter. :-)

    Nachtrag: Die benoetigten Audiodaten lassen sich nebenbei auch SEHR komprimiert speichern (32 Bit pro Phonem sollten machbar sein (Ausgabe dann ueber 3 Sinus-Oszis), waeren bei z. B. 40 Phonemen gerade mal 320 Byte und das Woerterbuch kaeme dann auf, eben mal ueberschlagen, rund 110 Byte).
    Die 32 Bit pro Phonem kommen so zustande: Je 5 Bit fuer relative Frequenz fuer ersten und zweiten Formant, plus 4 Bit fuer oberstes Frequenzband, plus 3 * 6 Bit fuer die Amplituden (koennte auch weniger reichen), F0/A0 fuer Stimmmelodie via Oszillatorreset dann im Woerterbuch codiert.
    Zusammen mit Blasebalg und Orgelpfeifen koennte man das vielleicht auch mit Waescheklammern bauen, wasserbetrieben. :-)
    Bin uebermuedet und hatte noch kein Abendessen/Fruehstueck und bin deshalb moeglicherweise etwas unterzuckert und albern… kann passieren…

    Like

  4. Kopfrechnen schwach…
    4*40 sind nicht 320 sondern 160. :-)
    Die angenommenen 40 Phoneme braeuchten also 160 Bytes bei 4 Byte pro.

    Like

  5. Die super-minimalistische Texteditor-Bibliothek mit der man aber “alles(?) machen” kann – oder was fehlt?

    de = dark editor, weil es hier keine Ein-/Ausgabe gibt.
    Von der C-Standard-Bibliothek sollten eigentlich nur sowas wie malloc()/free() und noch tolower() benoetigt werden (letzteres fuer die Suchfunktion).

    Editor-Struktur; ein Zeiger auf diesen Typ wird an alle Funktionen uebergeben.
    Der genaue Aufbau ist fuer die folgenden Beschreibungen unbedeutend, weil niemals auf die Strukturmitglieder direkt zugegriffen wird.

    typedef struct de_s de_t;

    Bestandteil der obigen Struktur ist ein Array von 16 Ankern, deren x-/y-Positionen ermittelt und gesetzt werden koennen.
    Ankernummer / Funktion:
    0: zeigt auf die Position HINTER dem letzten Zeichen des Gesamttextes.
    1: ist die aktuelle Text-Cursorposition.
    2: zeigt auf das erste Zeichen eines Blocks.
    3: zeigt auf das erste Zeichen HINTER einem Block.
    (gueltiger Block nur wenn Blockende > Blockanfang)
    4: zeigt nach einer Textsuche auf das erste Zeichen des gefundenen Textes
    (aktuelle Cursorposition auf das erste Zeichen HINTER dem gefundenen Text; gueltiger Fund-Block nur wenn Cursorposition > Fundposition).
    5: Hilfsanker fuer interne Zwecke (fuer Programmierer der Erweiterungen wie z. B. die Ein-/Ausgabe etc.)
    6-15: User-Anker 0 bis 9 = vom Anwender frei verwendbar.

    Funktionen (alphabetische Reihenfolge).

    Die Funktionsnamen bestehen (hinter dem de_-Praefix) aus zwei Zeichen mit folgenden Bedeutungen:
    1. a/c/d/f/g/i/j/m/o/s/t = append/clear/delete/(set)find/get/insert/jump/locate/overwrite/split/toggle
    2. a/c/l/m/o/s/x/y = anchor/char/line(length)/modified-flag/(find)option/string/x-pos/y-pos

    Es gibt, abgesehen von irgendwelchen de_create()/de_destroy()-Funktionen usw., die ich hier ignoriere, insgesamt 23 Funktionen, wenn ich mich nicht verzaehlt habe.
    Sofern sie den Text veraendern, tun sie das, mit Ausnahme von al() und sl() nur innerhalb einer Zeile (ebenso die Funktionenen zum Auslesen von Zeichen(ketten) und die Suchfunktion).

    int de_al(de_t *de); // al = append lines
    1. setzt die Cursorposition an das Ende der aktuellen Zeile.
    2. haengt Folgezeile an die aktuelle an, sofern moeglich.
    Liefert 1 bei Erfolg, sonst -1.
    In jedem Fall befindet sich der Cursor nach Aufruf der Funktion am (ehemaligen) Zeilenende (= hinter letztem Zeichen in der Zeile) vor dem Aneinanderhaengen.
    Anker werden angepasst und das Modified-Flag gesetzt.

    int de_cm(de_t *de); // cm = clear modified-flag
    loescht das Modified-Flag.
    Diese Funktion liefert immer 1 (Erfolg).

    int de_dc(de_t *de); // dc = delete char
    loescht das Zeichen unter der Cursor-Position und zieht den Rest der aktuellen Zeile heran.
    Diese Funktion arbeitet nur innerhalb der aktuellen Zeile!
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden angepasst und das Modified-Flag gesetzt.

    int de_ds(de_t *de, int n); // ds = delete string
    loescht n Zeichen ab der Cursor-Position und zieht den Rest der aktuellen Zeile heran.
    Diese Funktion arbeitet nur innerhalb der aktuellen Zeile!
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden angepasst und das Modified-Flag gesetzt.

    int de_fs(de_t *de, char *s, int n); // fs = find string
    sucht den String s mit Laenge n im Text.
    Suchoptionen werden mit fo() gesetzt (siehe dort).
    Gesucht wird immer nur innerhalb der aktuellen Zeile!
    Bei Erfolg liefert die Funktion 1 und der Anker 4 wird auf den Anfang des gefundenen Textes gesetzt, sowie die Cursorposition hinter das Ende des gefundenen Strings.
    Im Fehlerfall liefert die Funktion -1.

    int de_fo(de_t *de, int o); // (fo = (set) find-option
    setzt Optionen fur die Funktion fs().
    o besteht aus:
    Bit / Wert / Bedeutung wenn gesetzt
    0 / 1 / Gross-/Kleinschreibung ignorieren
    1 / 2 / globale Suche, beginnend ab Zeilenanfang/-ende (abhaengig von Rueckwaerts-Option), sonst ab Cursorposition
    2 / 4 / Rueckwaertssuche
    Diese Funktion liefert 1 bei Erfolg, sonst -1.

    int de_gc(de_t *de); // gc = get char
    liefert das Zeichen (0 bis 255) an der Cursorposition oder -1 im Fehlerfall.
    Das Zeichen 0 ist das Zeilenendezeichen.

    int de_gl(de_t *de); // gl = get (line) length
    liefert die Anzahl Zeichen (ohne Zeilenabschluss) der aktuellen Zeile oder -1 im Fehlerfall.

    int de_gm(de_t *de); // gm = get modified-flag
    liefert 1 wenn Modified-Flag gesetzt, sonst 0.

    int de_go(de_t *de); // get (find) option
    liefert die aktuelle Suchoptionseinstellung (siehe fo()).

    char *de_gs(de_t *de, int n); // gs = get string
    liefert einen Zeiger auf das Textzeichen unter der aktuellen Cursorposition oder NULL im Fehlerfall.
    Ein Fehler ist z. B. wenn s + n hinter dem Zeilenende liegt (s sei der gelieferte Zeichenzeiger).
    Es wird also nur dann s != NULL geliefert wenn sich ab der Cursorposition mindestens n Zeichen in der Zeile befinden.
    Der Inhalt s[…] sollte nicht direkt veraendert werden!

    int de_gx(de_t *de, int n); // gx = get x-position
    liefert die x-Position (Spaltennummer) des Ankers n (0 bis 15) oder -1 im Fehlerfall.
    Positionen beginnen immer bei 0.

    int de_gy(de_t *de, int n); // gx = get y-position
    liefert die y-Position (Zeilennummer) des Ankers n (0 bis 15) oder -1 im Fehlerfall.
    Positionen beginnen immer bei 0.

    int de_ic(de_t *de, int c); // ic = insert char
    fuegt ein Zeichen an der aktuellen Cursorposition ein und verschiebt sowohl den Cursor als auch den Text dahinter entsprechend nach rechts.
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden angepasst und das Modified-Flag gesetzt.

    int de_is(de_t *de, char *s, int n); // is = insert string
    fuegt den String mit Laenge n an der aktuellen Cursorposition ein und verschiebt sowohl den Cursor als auch den Text dahinter entsprechend nach rechts.
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden angepasst und das Modified-Flag gesetzt.

    int de_ja(de_t *de, int n); // ja = jump (to) anchor
    setzt die Cursorposition (Anker 1) auf die Position des Ankers n.
    Liefert 1 bei Erfolg, sonst -1.

    int de_jx(de_t *de, int nx); // jx = jump (to) x-pos
    setzt die Cursorposition auf Spalte nx (beginnend bei 0).
    Liefert 1 bei Erfolg, sonst -1.

    int de_jy(de_t *de, int ny); // jy = jump (to) y-pos
    setzt die Cursorposition auf Zeile ny (beginnend bei 0).
    Liefert 1 bei Erfolg, sonst -1.

    int de_la(de_t *de, int n); // la = locate anchor
    setzt die Position des Ankers n auf die aktuelle Cursorposition.
    Der geschuetzte Anker 0 (Textende) kann nicht veraendert, sondern nur abgefragt werden!
    Liefert 1 bei Erfolg, sonst -1.

    int de_oc(de_t *de, int c); // oc = overwrite char
    ueberschreibt das Zeichen an der aktuellen Cursorposition mit dem Zeichen c und bewegt den Cursor entsprechend weiter nach rechts.
    Am Zeilenende arbeitet die Funktion wie ic().
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden ggf. angepasst und das Modified-Flag gesetzt.

    int de_os(de_t *de, char *s, int n); // os = overwrite string
    ueberschreibt die Zeichen ab der aktuellen Cursorposition mit dem String s (Laenge n) und bewegt den Cursor entsprechend weiter nach rechts.
    Am Zeilenende angekommen arbeitet die Funktion wie is().
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden ggf. angepasst und das Modified-Flag gesetzt.

    int de_sl(de_t *de); // sl = split line
    teilt die aktuelle Zeile an der Cursorposition auf, wobei alle Zeichen ab der Cursorposition in eine neu eingefuegte Zeile wandern.
    Die Cursorposition veraendert sich nicht.
    Liefert 1 bei Erfolg, sonst -1.
    Anker werden angepasst und das Modified-Flag gesetzt.

    int de_tm(de_t *de); // tm = toggle modified-flag
    loescht das Modified-Flag, wenn es gesetzt ist bzw. umgekehrt.
    Diese Funktion liefert den neuen Zustand des Modified-Flags (0 = geloescht, 1 = gesetzt).

    Damit sollte sich auch ein komplexer Editor aufbauen lassen.
    Ein paar wertvolle Funktionen koennte man noch einfuegen:
    * Suchen mit regulaeren Ausdruecken
    * Undo-Funktion
    * Ein-/Ausschalten/Abfragen der Undo-Faehigkeit

    Wenn das Ding nun noch beliebig grosse Texte in guter Geschwindigkeit verarbeiten kann, isset eigentlich fast perfekt. :-) …dann wird malloc()/free() allerdings nicht mehr ausreichen…
    Noch perfekter wird es, wenn man das ganze in einem simplen Bytecode verfasst (FORTH ist zu derbe), dessen Interpreter in ein/zwei Stunden runter getippt ist.
    Dazu vielleicht mehr in der naechsten 80:120-Troll-Folge… muss ja zwischenzeitlich noch Orgelspielen lernen und die Waescheklammer-CPU bauen… und einen Kanal vom Fluss durch meinen Keller graben… :-)

    Like

    • Die Basis für ein Betriebssystem from scratch ist ein Texteditor. Um diesen zu programmieren braucht man eine Mini-Bibliothek aus Methoden. Der Sourcecode dafür muss nicht feststehend sein, wie bei existierenden Editoren wie VI oder Emacs sondern lässt sich über ein Bootstrapping Verfahren erstellen. Das heißt, er lässt sich im Sinne von sourceless programming entweder aus den Gehirnströmen des Users ableiten oder aber manuell über ein Keyboard eintippen wenn kein Brainwave-Tracker verfügbar ist. Hat man den Texteditor in der Forth-Umgebung bereitgestellt, ist das System in der Lage komplexe Aufgaben zu bewältigen, beispielsweise Datenbanken abzufragen.

      Like

      • Die Bedeutung eines Editors als zumindest wesentliche Teilbasis eines Betriebssystems (oder auch einer Datenbank) habe ich verstanden und kann ich nachvollziehen.
        Aber wie bootstrappt man einen Editor sourceless? Klingt irgendwie urknallmaessig…
        Bleiben wir der Einfachheit/Darstellbarkeit/Nachvollziehbarkeit halber mal bei der Tastatur-Variante und lassen den Brainwave-Tracker beiseite. :-)

        Like

      • > Bleiben wir der Einfachheit/Darstellbarkeit/Nachvollziehbarkeit halber mal
        > bei der Tastatur-Variante und lassen den Brainwave-Tracker beiseite. :-)

        Einverstanden, und wir zitieren auch nicht:

        “In i, electroencephalographic (EEG) activity is present in the theta-alpha bands, between the delta waves of deep sleep and the beta waves of the actively thinking mind” Frenger, Paul. “Emulating i.” Biomed Sci Instrum 46 (2010): 26-32.

        Like

  6. Ja, ich hatte sowas schon gelesen, weiss aber dennoch nicht was Sie mir sagen moechten.
    Na gut, wenn Sie unbedingt wollen, koennen Sie von mir aus auch Ihren Brainwave-Tracker verwenden…
    Wie geht es nun also weiter mit dem sourceless Bottstrappen des Editors?

    Like

    • > Wie geht es nun also weiter mit dem sourceless Bottstrappen des Editors?

      Unfortunately, my own knowledge about Forth and similar languages like APL is limited. In the past, I’ve only written some smaller hello world programs with a low quality. But I know somebody who is an Forth expert, and maybe he could answer the question, his name is Mentifex and he has created a website under the URL http://mind.sourceforge.net/m4thuser.html As far as I understood, the bootstrapping of an AGI works with natural language in the subject-verb-object form. That means the system understands English as default.

      Like

  7. Eine 32Bit-Word-Code-VM, MIPS-abgeleitet (aber nicht wirklich MIPS!).
    Es wird zu lang – deshalb keine lange Vorreden
    (siehe Bemerkung in der Troll-Ausgabe zum minimalist. Editor).
    Hoffe es ist kurz und klar genug (Mitdenken erforderlich *g*).
    Sihe auch Bemerkungen am Ende!

    Instruktionscode-Formate
    o6_4z6_2x6_2y6 : and or xor nor add sub jmpv jalv shlv shrv sarv slt sltu
    o6_4z6_2x6_3a5 : shl shr sar
    o6h5l5_2x6_2y6 : xmul xdm xmulu xdmu
    o6h5l5u16 : andi ori xori lui
    o6h5l5n16 : addi subi ldb ldh ldw ldbu ldhu stb sth stw slti sltiu
    o6h5l5b16 : beq bne blt ble bltu bleu
    o6j26 : jmp jal
    o6e6t6x6_2y6 : ver off
    o6e6t6x6p8 : inb inh inw inbu inhu inwu outb outh outw
    o6e6_4u16 : vmsys
    o6e6_20 : floating-point
    wobei:
    a=shift amount (constant), b=(relative) branch target, e=opcode-extension,
    j=(absolute) jump target, n=signed constant, o=opcode,
    p=port (unsigned constant), u=unsigned constant, h/l/t/x/y/z=register.
    Obwohl einige Registerfelder 6 Bit breit sind (oberstes Bit reserviert = 0),
    gibt es gegenwaertig nur 32 allgemein verfuegbare Register.

    Instruktionsanordnung:
    root:
    and or xor nor add sub – –
    jmpv jalv – – xmul xdm xmulu xdmu
    shlv – shrv sarv shl – shr sar
    >cext – >fext >dext slt sltu – –
    andi ori xori lui addi subi – –
    jmp jal beq bne blt ble bltu bleu
    ldb ldh – ldw ldbu ldhu – –
    stb sth – stw slti sltiu – –
    cext:
    ver off – – – – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    inb inh – inw inbu inhu – –
    outb outw – outw vmsys – – –
    fext:
    addf subf mulf divf pwwf negf unof cmpf
    – – eqf nef ltf lef gtf gef
    cwf cuf clf cqf cfw cfu cfl cfq
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    dext:
    addd subd muld divd pwwd negd unod cmpd
    – – eqd ned ltd led gtd ged
    cwd cud cld cqd cdw cdu cdl cdq
    cfd – – – cdf – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –
    – – – – – – – –

    Instruktionsbeschreibung
    Links steht Opcode in Hex, evtl. gefolgt von durch Slash
    getrennten Erweiterungscode. Weiter mit Mnemonic, Ein-/Ausgangsoperanden
    und der Beschreibung. Registerinhalte sind im folgenden, wenn nicht gecastet,
    unsigned. i8/i16/i32/i64 = int8_t/int16_t/int32_t/int64_t,
    u8/u16/u32/u64 = uint8_t/uint16_t/uint32_t/uint64_t, f32/f64=float/double.
    Zur Fliesskomma-Arithmetik siehe auch die Soft-Float-Beschreibung des gcc,
    insbesondere bezueglich der Vergleichsbefehle/-Soft-Float-Funktionen
    (Eingang immer ueber a0/a1/a2/a3/a0f/a1f/a2f/a3f/a0a1q/a2a3q/a0a1d/a2a3d,
    Ausgang immer nach v0/v1/v0f/v1f/v0v1q/v0v1d,
    wobei hier *f = f32, *d = f64, *q = u64, sonst u32).
    00 and -o z -i x -i y { $z = $x & $y; }
    01 or -o z -i x -i y { $z = $x | $y; }
    02 xor -o z -i x -i y { $z = $x ^ $y; }
    03 nor -o z -i x -i y { $z = ~($x | $y); }
    04 add -o z -i x -i y { $z = $x + $y; }
    05 sub -o z -i x -i y { $z = $x – $y; }
    08 jmpv -i y { nnpc = $y; }
    09 jalv -o z -i y { nnpc = $y; $z = pc + 8; }
    0c xmul -o h -o l -i x -i y { $h$l = (i64)(i32)$x * (i32)$y; }
    0d xdm -o h -o l -i x -i y { $h = (i32)$x % (i32)$y; $l = (i32)$x / (i32)$y; }
    0e xmulu -o h -o l -i x -i y { $h$l = (u64)$x * $y; }
    0f xdmu -o h -o l -i x -i y { $h = $x % $y; $l = $x / $y; }
    10 shlv -o z -i x -i y { $z = $x < > $y; }
    13 sarv -o z -i x -i y { $z = (i32)$x > > $y; }
    14 shl -o z -i x -i a { $z = $x < > $a; }
    17 sar -o z -i x -i a { $z = (i32)$x > > $a; }
    18/00 ver -o t { $t = VERSIONCODE; }
    18/01 off -i y { q = $y; goto quit; }
    18/30 inb -o t -i x -i p { inport(i8, $x + $p, $t); }
    18/31 inh -o t -i x -i p { inport(i16, $x + $p, $t); }
    18/33 inw -o t -i x -i p { inport(u32, $x + $p, $t); }
    18/34 inbu -o t -i x -i p { inport(u8, $x + $p, $t); }
    18/35 inhu -o t -i x -i p { inport(u16, $x + $p, $t); }
    18/38 outb -i t -i x -i p { outport(u8, $x + $p, $t); }
    18/39 outh -i t -i x -i p { outport(u16, $x + $p, $t); }
    18/3b outw -i t -i x -i p { outport(u32, $x + $p, $t); }
    18/3c vmsys -i u { vmsystemcall($u); }
    1a/00 addf { v0f = a0f + a1f; }
    1a/01 subf { v0f = a0f – a1f; }
    1a/02 mulf { v0f = a0f * a1f; }
    1a/03 divf { v0f = a0f / a1f; }
    1a/04 negf { v0f = -a0f; }
    1a/05 pwwf { v0f = powf(a0f, (f32)(i32)a1f); }
    1a/06 unof { v0 = unordered(a0f, a1f); }
    1a/07 cmpf { v0 = compare(a0f, a1f); }
    1a/0a eqf { v0 = equal(a0f, a1f); }
    1a/0b nef { v0 = notequal(a0f, a1f); }
    1a/0c ltf { v0 = less(a0f, a1f); }
    1a/0d lef { v0 = lessequal(a0f, a1f); }
    1a/0e gtf { v0 = greater(a0f, a1f); }
    1a/0f gef { v0 = greaterequal(a0f, a1f); }
    1a/10 cwf { v0f = (i32)a0; }
    1a/11 cuf { v0f = (u32)a0; }
    1a/12 clf { v0f = (i64)a0a1q; }
    1a/13 cqf { v0f = a0a1q; }
    1a/14 cfw { v0 = (i32)a0f; }
    1a/15 cfu { v0 = (u32)a0f; }
    1a/16 cfl { v0v1q = (i64)a0f; }
    1a/17 cfq { v0v1q = (u64)a0f; }
    1b/00 addd { v0v1d = a0a1d + a2a3d; }
    1b/01 subd { v0v1d = a0a1d – a2a3d; }
    1b/02 muld { v0v1d = a0a1d * a2a3d; }
    1b/03 divd { v0v1d = a0a1d / a2a3d; }
    1b/04 negd { v0v1d = -a0a1d; }
    1b/05 pwwd { v0v1d = pow(a0a1d, (f64)(i32)a2); }
    1b/06 unod { v0 = unordered(a0a1d, a2a3d); }
    1b/07 cmpd { v0 = compare(a0a1d, a2a3d); }
    1b/0a eqd { v0 = equal(a0a1d, a2a3d); }
    1b/0b ned { v0 = notequal(a0a1d, a2a3d); }
    1b/0c ltd { v0 = less(a0a1d, 2a3d); }
    1b/0d led { v0 = lessequal(a0a1d, a2a3d); }
    1b/0e gtd { v0 = greater(a0a1d, a2a3d); }
    1b/0d ged { v0 = greaterequal(a0a1d, a2a3d); }
    1b/10 cwd { v0v1d = (f64)(i32)a0; }
    1b/11 cud { v0v1d = (f64)(u32)a0; }
    1b/12 cld { v0v1d = (f64)(i64)a0a1q; }
    1b/13 cqd { v0v1d = (f64)(u64)a0a1q; }
    1b/14 cdw { v0 = (i32)a0a1d; }
    1b/15 cdu { v0 = (u32)a0a1d; }
    1b/16 cdl { v0v1q = (i64)a0a1d; }
    1b/17 cdq { v0v1q = (u64)a0a1d; }
    1b/18 cfd { v0v1d = a0f; }
    1b/1c cdf { v0f = a0a1d; }
    1c slt -o z -i x -i y { $z = (i32)$x < (i32)$y ? 1 : 0; }
    1d sltu -o z -i x -i y { $z = $x < $y ? 1 : 0; }
    20 andi -o h -i l -i u { $h = $l & $u; }
    21 ori -o h -i l -i u { $h = $l | $u; }
    22 xori -o h -i l -i u { $h = $l ^ $u; }
    23 lui -o h -i u { $h = $u < < 16; }
    24 addi -o h -i l -i n { $h = $l + $n; }
    25 subi -o h -i l -i n { $h = $l – $n; }
    28 jmp -i j { nnpc = $j < < 2; }
    29 jal -i j { nnpc = $j < < 2; ra = pc + 8; }
    2a beq -i h -i l -i b { if ($h == $l) nnpc = pc + 8 + ($b < < 2); }
    2b bne -i h -i l -i b { if ($h != $l) nnpc = pc + 8 + ($b < < 2); }
    2c blt -i h -i l -i b { if ((i32)$h < (i32)$l) nnpc = pc + 8 + ($b < < 2); }
    2d ble -i h -i l -i b { if ((i32)$h <= (i32)$l) nnpc = pc + 8 + ($b < < 2); }
    2e bltu -i h -i l -i b { if ($h < $l) nnpc = pc + 8 + ($b < < 2); }
    2f bleu -i h -i l -i b { if ($h <= $l) nnpc = pc + 8 + ($b < < 2); }
    30 ldb -o h -i l -i n { load(i8, $l + $n, $h); }
    31 ldh -o h -i l -i n { load(i16, $l + $n, $h); }
    33 ldw -o h -i l -i n { load(u32, $l + $n, $h); }
    34 ldbu -o h -i l -i n { load(u8, $l + $n, $h); }
    35 ldhu -o h -i l -i n { load(u16, $l + $n, $h); }
    38 stb -i h -i l -i n { store(u8, $l + $n, $h); }
    39 sth -i h -i l -i n { store(u16, $l + $n, $h); }
    3b stw -i h -i l -i n { store(u32, $l + $n, $h); }
    3c slti -o h -i l -i n { $h = (i32)$l < $n ? 1 : 0; }
    3d sltiu -o h -i l -i n { $h = $l > 20) // o6e6
    {
    default : q = ERR_ILL; goto quit;

    } // switch
    } // forever
    quit:

    return q;
    }

    Abschlussbemerkung:
    Dieser Befehlscode und die VM sind sozusagen semi-MIPS-kompatibel
    (allerdings little endian – hatte ich noch vergessen zu erwaehnen). Man kann
    unter bestimmten Voraussetzungen mit gcc Code fuer diese VM erzeugen lassen,
    d. h. man erzeugt zuerst MIPSEL32-Code fuer die klassische Version
    (R2000er oder was es noch gleich war) und stellt dann die Befehlscodes mit
    einem Hilfsprogramm um.
    Voraussetzungen damit das uebersetzte Programm lauffaehig ist
    oder um das wenigstens wahrscheinlicher zu machen
    (abgesehen von verfuegbaren Bibliotheken):
    MIPS’s add/sub fuehrt bei Ueberlauf eine Unterbrechung durch,
    dort addu/subu tut das nicht. MIPS’s add/sub/addi sollten wie addu/subu/addiu
    behandelt werden.
    Es sollten von gcc keine break-Instruktionen ausgegeben werden oder diese
    als nop behandelt werden.
    Gesamtspeicherbedarf max. 256 MB.
    lwl/lwr/swl/swr sollten nicht von gcc ausgegeben werden.
    Load-/Store-Befehle dienen bei obiger VM nicht zum Peripheriezugriff
    (damit die Instruktionen schneller sind); dafuer gibt es hier in* und out*.
    gcc sollte Code fuer Software-Floating-Point-Arithmetik ausgeben weil
    obige Instruktionen nach gcc’s Soft-FPA funktionieren.
    Die MIPS-typische Speicheraufteilung fuer Code/Daten sollte nicht verwendet werden
    (Linker-Script) weil das fuer die VM zu viel Platz braucht.
    Einiges kann man ueber Optionen/Linker-Scripts dem gcc beibringen, anderes muss
    man ueber den C-Programm-Code sicherstellen.
    Keinen Platz mehr um mehr zu schreiben, ca. 250 Zeilen muss reichen, aber
    kuerzer geht’s leider kaum…
    Hoffe jetzt nur noch, dass WordPress nichts unlesbar kaputt macht.
    In der naechsten Troll-Ausgabe vielleicht mehr Heiterkeit. :-)
    In meinem Editor ist das Zeile 245. Tut mir leid. Zukuenftig wieder kuerzer. :-)
    246: hoffentlich keine groesseren Fehler enthalten.
    247: Doch noch wichtig: Die Jumps/Branches brauchen die Verzoegerung fuer die
    248: Semikompatibilitaet – das kann man dem gcc natuerlich nicht abgewoehnen…
    249: In C braucht die Basis-VM als reiner Interpreter etwa so viele Zeilen wi
    250: dieser Kommentar. WP wuerde den Source aber kaputt machen.

    Like

  8. Ein paar Sachen hat WP natuerlich kaputt gemacht. :-/
    …die Shift-Operatoren z. B., sollte aber klar sein, was da hin gehoert.
    Die Interpreterschleife ist aber nicht zu entziffern, dabei stand da gar nix, was WP vermurxen sollte. %-/
    Also tippe ich die nochmal Pascal-aehnlich, weil das nicht so unwichtig ist.

    function vmrun(vm : vm_t) : u32;
    begin

    while true do
    begin
    pc := npc; npc := nnpc; nnpc := nnpc + sizeof(u32);
    load(u32, pc, opc); (* opc aus Speicher lesen *)
    case opc of

    else begin q := ERR_ILL; goto quit; end
    end; (* case *)
    end; (* forever *)
    quit:

    vmrun := q;
    end;

    Die Registerbeschreibung hat WP auch gekillt – bescheuert oder was?
    Deshalb habe ich das mit dem Bloggen auch aufgegeben – das ganze Gemurxe immer. :-/
    Also die Register sind wie bei der MIPS nur dass anstatt k0/k1 hier lo/hi untergebracht ist.

    Ich hoffe das war’s. :-)

    Like

  9. Ach ja, und dass man unter bestimmten Voraussetzungen einen MIPS-gcc-Cross-Compiler benutzen kann um fuer diese VM Programme zu uebersetzen (braucht allerdings ein Hilfsprograemmchen fuer die Code-Umstellung), hat WP auch gekillt.
    Ich habe mit obigem und einem MIPS-Cross-gcc jedenfalls schon ernsthafte Programme (teilweise halbwegs) zum laufen gekriegt…
    Na gut, das war’s zum Thema. Naechste mal wieder witzisch. :-)

    Like

  10. Ach und inder Befehlsbeschreibung hat er auch was gekillt.
    Naja, fuer eine Anregung sollte es reichen…
    Was soll das alles ueberhaupt?
    Frueher haben irgendwelche Leute so’n Bisschen Programmieren gelernt und dann ihre Ideen praesentiert.
    Die wurden dann leider immer runter gemacht, dass sie sich ja nur profilieren wollten.
    Und so gibt es diese Leute nicht mehr, was ich schade finde, weil einige Ideen trotz Anfaengerstatus trotzdem recht nett waren.
    Ich versuche also ein wenig die Profilierungs-Tradition wiederzubeleben. :-)

    Like

    • Zum Thema Profilieren: Für einen Computer-Neueinsteiger mag der gepostete Sourcecode mit den Opcodes imposant wirken, aber Virtuelle Machinen sind jetzt nicht wirklich etwas aufregendes. Hier https://rosettacode.org/wiki/Compiler/virtual_machine_interpreter#Forth ist eine URL zu einigen Beispielen auf der Rosettacode Website. Im Grunde geht es darum, ein Lexikon aus Befehlen zu implementieren die man von außen bequem aufrufen kann. In dem von dir geposteten Quellcode wären das Befehle wie and, or, sub usw. die auf die Prozessor-Register gemappt werden. Im großen und Ganzen ist das also friendly code …

      Like

      • Hallo Manuel
        Die anderen beiden Beispiele sind ja auch nicht komplex, auch wenn man z. B. ueber das Speichermanagement des Editors laenger philosophieren koennte. Ich liebe friendly Code! :-) Den Begriff kannte ich so uebrigens nicht. Was meint das genau, Ramsch? :-) Na Ramsch mag ich nicht, siehe ersten Kommentar, aber simple/schlichte Sachen schon… Was ist das Gegenteil von friendly Code?
        Die meiste Zeit hatte ich mich auch nicht mit der VM/dem Interpreter als solchen beschaeftigt, sondern mit dem Aufraeumen des Nicht-mehr-MIPS-Befehlscodes, dem Belassen der Semikompatibilitaet (damit der MIPS-Cross-gcc verwendet werden kann), der Vorausschau von moeglichen Erweiterungen ohne dass es wieder zum Chaos fuehrt (mehr Instruktionen, mehr Register, Erweiterung auf 64 statt 32 Bit usw.). So gesehen war es mehr eine Art Puzzle, hatte etwas von den Brettchen auf denen man unsortierte kleine bunte Quadrate mit Zahlen verschiebt bis diese wieder sortiert sind oder fuer juengere das Bild einer niedlichen Katze erscheint. :-)
        Man kann das als weitgehend platformunabhaengige Assemblersprache nutzen. Die Implementierung ist sicher einfacher als ein FORTH mit Vokabular und es duerfte auf den verbreiteten CPUs von Intel, AMD oder ARM auch schneller sein und trotzdem relativ bequem programmierbar (Low-Level-FORTH ist ja nicht wirklich easy handzuhaben, nur der Gesamtmechanismus leicht verstaendlich, weshalb die Sprache wohl auch nicht so oft genutzt wird, obwohl man die ganze Gewalt drueber hat). Und man kann, wenn man will, natuerlich auch ein FORTH in obigem implementieren und hat dann beides.
        Was die Profilierung angeht, kann jemand, der sich zu komplexerem Themen berufen fuehlt, gerne auch imposantere Dinge beschreiben (vielleicht sogar ohne Massen von bunten Bildern/Screenshots, so wie die guten alten RFCs und aehnlichem), was man aber dann vor allem im deutschsprachigen Raum/auf Deutsch auch nicht tut, wenn’s dafuer kein Geld gibt. Ohne Zaster bleibt es dann nur im Ungefaehren und so kommt es dann eben zu solchen “Experten” wie meiner einer, die sich zu ihren Waescheklammerbastelarbeiten zurueckziehen. :-)
        LG
        Michael

        Like

  11. Das koennte man vielleicht mit Waescheklammern bauen. :-)
    (Speicher wird aber brutal – vielleicht baut man es doch lieber erst mal mit Transistoren und Magnettrommel.)

    (Und WP macht jetzt hoffentlich nichts kaputt; habe extra alle Kleiner-/Groesserzeichen und eckige Klammern vermieden.)

    ##########
    #
    # WKR41 (W-klammernrechner mit 4 Operationen und 1 Instruktion) bzw.
    # WKR42 (WKR mit 4 Ops und 2 Instrs, siehe unten)
    #
    ##########
    Es gibt also vier arithmetische Operationen:

    or: *d = *a or *b
    xor: *d = *a xor *b
    rol: *d = roll_left(*a, *b)
    alt: if highestbit_set(*c) then *d = *a + *b
    (rol=roll left ohne Umweg ueber ein Carry-Flag oder sowas (es gibt keine solchen Flags), alt = add if less than)

    *a bis *d sind Zugriffe auf Speicherstellen; es gibt also keine gesonderten Register.
    Adressen sind immer Zellenadressen, bei einem 16-Bit-System also: byteadresse = zellenadresse * 2.
    (Es kann mit einer Instruktion nur auf Zellen, nicht auf einzelne Bytes zugegriffen werden.)

    Adresse : enthaelt :
    0 : *c (c=condition)
    1 : *a
    2 : *d (d=destination)
    3 : *i (Befehlszeiger)
    4 : *b fuer or (Schreiben in *b triggert or)
    5 : *b fuer xor (…triggert xor)
    6 : *b fuer rol (…triggert rol)
    7 : *b fuer atl (…triggert add wenn *c kleiner 0 (add if less than))

    (Die Zellenadressen 0x8 bis 0xf sind Portadressen zur Ansteuerung der Peripherie, die hier nicht weiter spezifiziert wird; ab 0x10 ist dann alles frei.)

    Die einzige Instruktion ist ein move der Form
    *y = *x
    und hat bei einem 16-Bit-System das Format
    xxxxxxxxxxxxxxxx (an gerader Zellenadresse)
    yyyyyyyyyyyyyyyy (an ungerader Zellenadresse)
    Man kann es auch so interpretieren, dass es zwei Instruktionen sind:
    * an gerader adresse: temp = *x
    * an ungerader Adresse: *y = temp

    Weil immer zellenweise adressiert wird, hat man bei einem 16-Bit-System also bis zu 128 KB zur Verfuegung. Allerdings schon moeglich, dass die obere Haelfte unbequem zu handhaben sein wird…?

    Damit sollte man eigentlich “alles” programmieren koennen.
    Weil das nur mit move-Befehlen aber ziemlich aetzend wird, ist ein einfacher Makro-Assembler wohl unerlaesslich.
    Damit programmiert man dann erst einmal eine einfache aber komfortablerere Register-VM, damit dann vielleicht eine noch komfortablere, damit dann ein FORTH und damit dann die Anwendung… wuerde ich mal so meinen. :-)
    … in der Hoffnung, dass noch genug Speicher fuer das FORTH und die Anwendung uebrig bleibt (sind ja immer 2 Zellen pro move, also bei einem 16-Bit-System 4 Byte).

    In C braucht das weniger als 100 Zeilen (nur die VM-Library, die allerdings relativ komfortabel ist: mit installierbarer Peripheriehandlern und Fehlerpruefungen).
    Vielleicht kann ich mich mal dazu ueberwinden ein FORTH darauf zu portieren. :-)

    PS: Zelle hier gleichbedeutend mit Maschinenwort

    Like

    • Translating the posting into English is a bit difficult. For our international readers it is important to explain first what a “W-klammernrechner” is. The idea is to use Clothespin to protect something before the wind. That means, the computer is inside a tornado on the ocean and must resist against nature. Only a bullet proof system is acceptable. English-based programmers would argue, that they bootstrap the system and build first a minimal computer in hardware, create a stable virtual machine and build on top an algorithm.

      This sounds like reggae and the rhythm is familiar. Often this kind of programming style is connected to a biography in which computers were not invented yet in the mainstream and electronics skills are mandatory. My fear is, that this will become the future. That means, all computer experts will build “klammernrechner” and “Makeshift apps”.

      Like

  12. Shit, beim Tippen des Assemblers ist mir aufgefallen, dass im WKR41/42 ein Fehler drin ist; da fehlt was.
    Es fehlt naemlich die Moeglichkeit fuer
    **y = *x
    oder
    *y = **x
    oder auch
    **y = **x
    Mindestens eines davon wird aber noch zusaetzlich zu *y = *x benoetigt um auf berechnete Adressen zugreifen zu koennen weil x und y ja KONSTANT sind (bilden ja den Befehlscode).
    Loesungsmethode #1 :
    Eine Loesung koennte sein (ich gehe immer von 16-Bit-Systemen aus), dass man den Befehlscode erweitert:
    sxxxxxxxxxxxxxxx dyyyyyyyyyyyyyyy
    wobei s und d einen indirekten Zugriff bewirken wenn gesetzt, also
    temp = *x mit gesetztem s wird zu temp = **x
    und
    *y = temp mit gesetztem d wird zu **y = temp.
    Man hat dann nur noch 15 Bit fuer die Adresse, weil das aber Zellenadressen sind, verbleiben noch 64 KB.
    Loesungsmethode #2 :
    Eine andere Moeglichkeit, die zwar **y = **x nicht zulaesst, dafuer aber *y = x (das heisst in C y=konstante), bestuende darin s und d zu einem 2-Bit-Modus zusammenzufassen:
    sd : bewirkt
    00 : *y = *x
    01 : *y = **x
    10 : **y = *x
    11 : *y = x // Sonderfall (nicht **y = x!)
    Nochmal: x und y sind Konstanten; mit Zahlen statt x und y saehe die obige Liste also so aus:
    00 : *90 = *91
    01 : *90 = **91
    10 : **90 = *91
    11 : *90 = 91 // Sonderfall (nicht **90 = 91!)
    Letztere Variante (also die mit dem Sonderfall) hat wie gesagt den Vorteil, dass man Konstanten direkt laden kann, was bislang nicht ging; die Konstanten mussten irgendwo im Speicher stehen und deren Adresse als Quelle angegeben werden.
    Allerdings koennen nur 15-Bit-Konstanten direkt geladen werden. Groessere vorzeichenlose oder negative Zahlen muessen entweder berechnet oder nach wie vor aus dem Datenspeicher geladen werden. Trotzdem: immerhin.
    Deshalb entscheide ich mich wohl fuer die zweite Erweiterung, also die mit dem Sonderfall, auch weil es sich beim bauen des Assemblers herausgestellt hat, dass das Laden von Konstanten sonst recht kompliziert wird.
    Und weil es nun eigentlich 4 Operationen und 4 Instruktionen sind (genauer 4 Adressierungsarten fuer den move), heisst das Ding jetzt WKR44.
    PS: Ja, den 1-Instruktions-Computer (OISC) a la SUBLEQ kenne ich, will aber doch einen Minimalkomfort; WKR44 ist so schon krass genug zu programmieren. :-)

    Like

  13. Ein erstes handassembliertes Hallo-Welt-Programm laeuft auf der VM, die wiederum auf dem Waescheklammernrechner laeuft.
    Allerdings hat der WKR im Moment noch 12 Operatoren um leichter Fehler zu finden und zu beseitigen:
    and or xor add shr sar shl sub aeq alt cmp cmpu.
    Auf diesem 12-Operatoren-WKR-Modell benoetigt die VM etwas weniger als 4 KB (also etwas weniger als 2048 Zellen, das sind weniger als rund 1024 WKR-move-Instruktionen) und das Hallo-Welt-Programm 28 Zellen (56 Bytes).
    Die Groesse des Hallo-Welt-Programm bliebe auf dem 4-Operatoren-WKR unveraendert; nur die VM waere dann groesser (evtl. 8 KB oder so).
    Man programmiert mit dem VM-Befehlssatz; die VM selbst ist also so eine Art Mikrocode, ohne den die Programmierung auf dem WKR zu kompliziert waere und die Programme schnell auch zu gross werden wuerden.
    Ein FORTH sollte sich mit dem VM-Befehlssatz in den ueblichen Groessenordnungen realisieren lassen (je nach dem wie schlank/fett es ist, schaetze mal, dass man mit 4 KB schon was fuer den Anfang brauchbares hinbekommen koennte – verblieben bei 64 KB also etwa 56 KB fuer die FORTH-Programme).
    Zur Performance kann ich augenblicklich noch nichts sagen, ausser dass es naturgemaess eher langsam sein duerfte weil z. B. die Interpretation des ersten jmp-Befehls schon 34 und die des ersten ldi-Befehls weitere 41 WKR-Instruktionen ausfuehrt, und das, wohlgemerkt, auf dem 12-Operatoren-WKR; das werden deutlich mehr auf dem 4-Op-WKR! Deshalb versuche ich es erst gar nicht mit einem SUBLEQ-Rechner oder aehnlichem. :-)

    Ich verlinke den WKR12 mit VM sobald die VM halbwegs fehlerfrei ist (der WKR besteht ja nur aus ein paar Zeilen).
    Und einen Assembler fuer den VM-Befehlssatz braucht es auch noch – habe nicht vor ein FORTH von Hand zu assemblieren. :-)
    Nachfolgendes also zur Vorfreude. :-)

    Die VM kennt auch Byte-Zugriffe auf den Speicher (WKR selbst ja nicht). Trotzdem habe ich den Text unten mit 2 Byte/Zeichen codiert. Es sollte fuer ein erstes HalloWelt-Programm dann leichter zu debuggen sein.

    // HalloWelt
    // Offsetzaehler b wird eigentlich nicht benoetigt,
    // aber ein wenig soll die VM ja schon zu tun haben.
    _vmprogramstart:
    jmp _main

    _msg: .w “\nHallo Welt!\n\0” // 2 Byte/Char

    _main:
    ldi a, _msg // a = Adresse von _msg (Basis)
    ldi b, 0 — b = 0 (Offset)
    L1:
    add d, a, b // d = a + b (d = aktuelle Zeichenadresse)
    xldw c, d, 0 // c = *(d + 0) (c = Zeichen)
    beq c, L2 // if (!c) goto L2
    gstw c, 2 // *(2) = c; (c an Peripherieanschluss 2; Zeichenausgabe)
    addi b, 2 // b += 2 (Offset erhoehen)
    jmp L1 // zum Schleifenanfang
    L2:
    ldi a, 0x1234 // a = exit-code
    gstw a, 0x1e // Portausgabe auf 0x1e = Waescheklammernrechner beenden
    L3:
    jmp L3 // Panik, Halt, Endlosschleife

    Die VM kennt augenblicklich, und das wird sich wohl auch nicht aendern, genau 50 Instruktionen und verfuegt ueber (leider nur) 8 Register plus Programmzaehler.
    * and, or, xor, add, sub, shlv, shrv, sarv, cmp, cmpu
    z. B. add a, b, c ist a = b + c (a…c sind Register).
    cmp/cmpu vergleichen vorzeichenbehaftet/-los zwei Operanden und liefern -1/0/1 bei kleiner/gleich/groesser.
    * shl shr sar
    z. B. shl a, b, 4, also mit konstantem dritten Operanden.
    * not mv neg cbw xchg
    z. B. mv a, b fuer einen einfachen Move.
    cbw ist eine vorzeichenbehaftete Erweiterung von 8 auf 16 Bit.
    xchg vertauschen zwei Registerinhalte (bei nur 8 Registern nuetzlich).
    * jmpv jsrv
    z. B. jmp a
    VARIABLER unbedingter Sprung/Unterprogrammaufruf (Ruecksprungadressen auf dem Stack).
    * mulu dmu
    mulu a, b, c und dmu a, b, c
    mulu liefert ein 32-Bit-Ergebnis, wobei der hoeherwertige Teil in das Hilfsregister h landet.
    Dort landet auch der Divisionsrest von dmu.
    * nop ret
    keine (expliziten) Operanden.
    * push pop
    z. B. push a
    * andi ori xori addi subi
    z B. addi d, 123 ist d = d + 123.
    Zu beachten: die Konstante fuer andi/ori/xori ist vorzeichenLOS, die fuer addi/subei vorzeichenBEHAFTET.
    * ldi
    ldi a, 123 laedt vorzeichenBEHAFTETE Konstante (die Vorzeichenbehaftung spielt nur eine Rolle bei der Groesse des Befehlscodes).
    * cmpi cmpiu
    z. B. cmp a, 123
    vergleicht Register mit Konstante (cmpu vorzeichenlos) und liefert -1/0/1 (kleiner/gleich/groesser) im Hilfsregister h.
    * jmp jsr
    z. B. jmp schleifenanfang
    unbedingter Sprung/Unterprogrammaufruf.
    * beq bne blt ble bgt bge
    z. B. beq a, schleifenanfang
    vergleicht Registerinhalt mit 0 und fuehrt ggf. Sprung aus.
    * xldb xldw xstb xstw
    z. B. xldb a, b, 4
    laedt ein Byte/Wort vom Speicher oder schreibt ein Byte/Wort in den Speicher.
    Die Adresse errechnet sich aus dem Inhalt des zweiten Registers plus dem konstanten vorzeichenbehafteten Offset.
    * gldb gldw gstb gstw
    z. B. gldw variable
    fuer globalen Datenzuggriff.
    Das waren alle Instruktionen.
    Die Implementierung von mulu und dmu in WKR-Assembler war nebenbei besonders spassig. :-)
    Ueber die Speicherbefehle wird auch die Peripherie angesprochen.
    Abschliessend noch die 8 allgemein verfuegbaren Register:
    a/b/c/d/g/l sind frei verfuegbar (g steht fuer global, l fuer local).
    s ist der Stackpointer
    h ist das Hilfsregister (siehe oben).
    i (das neunte, nicht allgemein zugaengliche Register) ist der Instruktionszeiger.

    Like

  14. TA TA! :-)
    Soeben lief die von 8086 portierte Version von Bill Muench’s eForth 1.01 aus dem Jahr 1990 auf dem WKR mit 12 Operatoren.
    Code: 4866 bytes
    Namen: 2060 bytes (ueber 200 Woerter)
    Fuer den WKR-Mikro-Code sind 8 KB reserviert, die aber nicht benoetigt werden (siehe unten).
    Von 8 KB Mikro-Code ausgegangen waeren also insgesamt 15 KB nicht frei.
    Bei 64 KB blieben also etwa 49 KB fuer eigene FORTH-Programme.
    Ein paar KB muss man aber noch abziehen, denn die Ursprungsversion von eForth hat ausser Zeichenein-/-ausgabe von/zur Konsole (oder serielle Schnittstelle, egal) und Programm-Beendigung nichts weiter was mit der Aussenwelt der CPU/des Speichers kommunizieren koennte.
    Ausserdem sind die allermeisten Woerter in FORTH geschrieben (nur etwa 30 in Assembler), auch solche, die man aus Geschwindigkeitsgruenden ueblicherweise nicht in FORTH implementieren wuerde, jedenfalls auf Nicht-FORTH-CPUs.

    Der 12-Operatoren-WKR-Mikro-Code braucht gegenwaertig uebrigens 3170 Bytes; man hat also noch ordentlich mehr Platz bzw. kann bei obiger Rechnung davon ausgehen, dass Zugriffe auf Massenspeicher, Uhr usw. ebenfalls vorhanden waeren, also bei etwa gleichem Restspeicherplatz.

    Like

  15. Habe mal einen fuer moderne Rechner nuetzlichen Maschinenbefehl erfunden, glaube ich… :-)

    Ein/der Grund, warum FORTH-Woerter vergleichsweise schnell ausgefuehrt werden koennen, ist, weil sie nicht decodiert werden muessen; hoechstens muss man den Befehlswert um 1/2/3 Stellen nach links verschieben und vielleicht noch eine Basisadresse aufaddieren und anschliessend eben zur entsprechenden Routine springen. Das war’s mehr oder weniger.
    Bei Registermaschinen muessen fuer gewoehnlich erst einmal oder zusaetzlich die Operanden (inklusive des Befehlscodes) separiert werden und das ist aufwaendig und wird von keinem mir bekannten Prozessor unterstuetzt, obwohl, wie ich meine, dass eine feine Geschichte waere.
    Deshalb schlage ich mal einen solch nuetzlichen Decodierbefehl vor.
    Mit dem klassischen x86-Registersatz wird das allerdings eng, will man nicht uebermaessig viele Speicheroperationen haben. Ich gehe deshalb mal von einer CPU mit 64 Bit Wortbreite und 64 allgemein verwendbaren Registern aus.
    Dann koennte ein solcher Decodier-Befehl, den ich mal SEP nenne, folgendermassen aussehen und funktionieren:

    SEP R10, R20, R30

    wuerde bedeuten, dass ein 64-Bit-Befehlswort (es muessen nicht alle Bits verwendet werden, insofern funktioniert das auch mit 32-Bit-Befehlen) in R20 decodiert wird und die Decodierinformationen in einer Tabelle ab Adresse R30 stehen. Die Ergebnisse werden in die Register R10, R11, R12,… geschrieben (je nach dem wieviele Operanden separiert werden – maximal 4).

    Der Aufbau der Decodierinformationstabelle, koennte dann z. B. so aussehen (laesst sich ggf. optimieren):

    ____aammsspppppp____aammsspppppp____aammsspppppp____aammsspppppp
    oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
    oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
    oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    (8 * 64 Bit = 512 Bit = 64 Byte = 8 Maschinenwoerter)

    Fuer jeden der maximal vier zu separierenden Operanden gibt es also ein 16-Bit-Eintrag in den ersten 64 Bit
    ____aammsspppppp
    wobei
    _ sind ungenutzte Bits
    aa ist ein Index, der auf keinen/den ersten/zweiten/dritten Offset (ooo…) verweist (Index 0 = kein Offset = 0-Offset).
    mm ist ein Index, der auf die erste/zweite/dritte/vierte Bitmaske (bbb…) verweist.
    ss bedeutet linksschieben um 0 bis 3 Stellen (Multiplikation mit 1/2/4/8).

    Die Seperation geschieht dann durch folgende Rechnung:

    targetreg_x = offset[aa_x] + ((rollright(source, pppppp_x) AND bitmask[mm_x]) SHL ss_x)

    … und das sollte sich zu grossen Teilen festverdrahten lassen (die Folge Rechtsrollen, AND, SHL und ADD auf jeden Fall).
    Rechts rollen statt rechts schieben macht es wahrscheinlicher zerstueckelte Befehlscodefelder zusammen(fassend) verarbeiten zu koennen.
    Nuetzlich sollte das fuer alle Interpreter sein (also Nicht-JIT-Compiler).
    Ich weiss gerade nicht wie der Bytecode des Python-Referenzinterpreters aussieht; vermutlich wuerde er durch einen solchen SEP-Befehl aber deutlisch schneller laufen (vorausgesetzt natuerlich, dass SEP selbst nicht lahm in der CPU implementiert ist).

    4 Operanden sollte in den meisten Faellen reichen.
    Anderenfalls kann man durch zwei solcher Befehle 8 Operanden separieren.
    Glueckliche Maschinen :) mit sehr vielen Registern koennen die Decodierinformationen samt Bitmasken und Offsets natuerlich auch in Registern halten; ich denke ab 64 Registern wird es interessant; 32 kann schon eng werden, sollen andere Dinge nicht unter SEP leiden. 32 Register mit der Tabelle im Speicher sollte aber vermutlich auch gut laufen…? Versuch macht kluch.

    PS: Bei vielen Befehlscode-Varianten wird man ggf. trotzdem nicht umhin kommen, die Tabellen im Speicher zu halten… es sei denn die CPU hat wahnsinnig viele Register (so ab 256). Waeren ja immerhin 8 Register pro Tabelle zu verbraten, bei 4 Befehlsvarianten also schon 32 Register… plus die 4 Zielregister, waeren im letzten Beispiel dann also 40 Register., was mit 64 Registern insgesamt dann schon knapp werden kann, je nach dem.

    Like

    • Nachtrag: Auch fuer JIT-Compiler kann SEP interessant sein, denn decodieren muessen die JITs den Bytecode ja auch und auch die JITs muessen schnell uebersetzen, soll der Ablauf nicht stocken.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.