4ide - ANSI-C based Forth like Interactive Data Explorer

4ide - ANSI-C Forth Interactive Data Explorer

31.10.2014, Andreas Klimas, klimas@w3group.de

Inhaltsverzeichnis

Übersicht  

4ide (gesprochen fide) ist ein extrem einfacher interaktiver Interpreter und Compiler zum Erweitern, Experimentieren und Verstehen. 4ide ist vollständig in C implementiert und in die C Umgebung integriert und daher auch explizit zum Experimentieren für eigene C Funktionen / Anwendungen, oder auch Skripting, geeignet.

Im Gegensatz zu C, aber auch vielen anderen Programmiersprachen, unterliegt 4ide keinerlei anderen Beschränkungen oder Regeln als jenen die man sich selbst auferlegt. Da ist niemand der verbietet auf den Stack direkt zuzugreifen, oder berechnete goto's zu implementieren, oder den Promille-Wert eines String-Pointers zu berechnen.

4ide ist von der Programmiersprache Forth abgeleitet, vereinfacht und an die C-Umgebung angepasst.
Der Compiler generiert 4ide-vm (indirect threaded) Code. Es ist ein Leichtes beliebig anderen Code (C, Java, ...) generieren zu lassen, oder aber 4ide selbst in jeder anderen Programmiersprache / Programmierumgebung zu implementieren.

Hintergrund  

Ich bin der Meinung dass Einfachheit und Interaktivität eine sehr wichtige und unterschätzte Eigenschaft ist. Die meisten interaktiven Programmiersprachen bieten nur eine grobgranulare Interaktivität an. Und die höheren Compiler enthalten so komplexe Syntax und Semantik Regeln, dass man selbst nach Jahren noch bis dahin unbekannte Regeln entdecken kann.
Ich kenne keine Programmiersprache deren Virtuelle Maschine so einfach und klein ist, dass sie in 25 Zeilen C-Code passen.

Einsatzbereiche  

• Spieleentwicklung, um z.B. eine GameEngine zu erforschen aber auch Spiele interaktiv zu entwickeln.
• Simulation und Visualisierung von Programmabläufen.
• Funktionsweise vom Computer Visualisierung (Speicher, Stack, I/O)
• Implementierung einer Provisionsabrechnung für Versicherer

Download  

4ide.tgz (20k)
Ein eigenes Betriebssystem mit Interpreter, Compiler und VM mit nur einem Tag Arbeit und etwa 1000 Zeilen Programm-Code ? Ich jedenfalls bin von dem Gedanken fasziniert. Ermöglicht es doch auf jeder beliebigen Plattform ein eigenes Betriebssystem haben zu können mit der Möglichkeit eigene Programme laufen zu lassen. Egal ob das Programm dann auf einer Graphik-Karte oder einem Smartphone läuft. Der Unterschied ist der, Sie sind nicht mehr davon abhängig ob es ein Entwicklungswerkzeug auf Ihrem Lieblingsystem gibt. Meistens ist es doch so, dass man den C-Code nur Cross compilieren kann und dann das Programm auf die Zielplattform übertragen muss. Aber das ist noch längst nicht alles, wir bekommen auch noch eine Programmiersprache geliefert die sehr einfach und flexibel ist. Sie ist sowohl sehr einfach zu implementieren (20-25 Zeilen Programm-Code) als auch zu programmieren. Kein 1000 Seitiges Regelwerk mit Syntax / Semantik und Ausnahmen. In wenigen Zeilen Text ist die Funktionsweise beschrieben. Ein eigenes Betriebssystem, mit Benutzer und Multitasking (wenn man extra Multitasking braucht oder will). Erforschen der Lieblingsplattform. Ausprobieren diverser Funktionen und Funktionalitäten, ohne langwierige Compile-Link-Upload Zyklen. SIGSEGV: Von einem Betriebssystem würde ich mir erwarten dass wenn ein Programm mal daneben greift (z.B. 0-Pointer) es nicht gleich abstürzt. Unterstützt uns die Hardware und das darunter liegende Betriebssystem, können wir natürlich einen Signal-Handler benutzen. Ist das nicht möglich, können wir manuell alle Speicherzugriffe überwachen. (-> Performance) MULTITASKING: Da unsere VM in etwa so aussieht: for(;;) {W=*ip++; W->primitive();} können wir diese einfach erweitern. for(;;) { if(ms_run>100) task_switch(); W=*ip++; W->primitive(); } Ich habe aber bisher noch nie Multitasking verwendet, daher kann ich nichts über die Praktikabilität aussagen. EINGABE UND AUSGABE: Wir müssen natürlich die Möglichkeit haben mit dem System zu kommunizieren. Auf einem Unix oder Windows ist das sehr einfach (stdin, stdout, console) auf einem Cluster benötigen wir vielleicht eine Netzwerk-Verbindung (Sockets) und auf einer Graphikkarte ein Stück gemeinsamen Speicher und ein eigenes kleines Terminal Programm. Um vom IO unabhängig zu sein wird dem Interpreter / Compiler der Quellcode via Speicher zur Verfügung gestellt. FORGET: Da Interpreter und Compiler sehr schnell sind, müssen die 4ide-Quellen nicht compiliert vorgehalten werden. Sie können JIT (just in time) direkt in den Speicher compiliert werden. Das impliziert folgende Möglichkeit: 1. Setzen einer Marke des Systems 2. Laden, Compilieren und Ausführen der Anwendung. 3. zurücksetzen des Systemstatus auf Punkt 1. Damit ist es nicht notwendig mit einem Garbage-Collector die temporären Datenstrukturen aufzuräumen. Und wir haben für den nächsten Aufruf wieder ein 'definiertes' System. Persistente Änderungen werden über die Datebank eingebracht. DATENBANK: Wird grundsätzlich im Speicher gehalten und ist in ========== 32 Byte Blöcke aufgeteilt. Ein Block sieht wie folgt aus: obj $0 next $1 owner $2 type-id(12 Bit), remain info flags $3 $4 $5 $6 $7 extensions (optional) Design-Hinweis: Sollte ein 32 Byte Objekt für die Attribute nicht ausreichend sein, so kann z.B. $7 als Extension verwendet werden. Alle weiteren Extensions dieses Objektes hängen dann auf $7. Durch ihre type-id sind sie eindeutig zu identifizieren. Durch den onwer, der auf $3 bis $7 seines Parents zeigt, ist es möglich durch die gesamte Datenbank zu navigieren. Satz: Eine Liste ist dadurch gekennzeichnet,dass wenn wenigstens ein Element vorhanden ist, so zeigt dieses (also das erste Element) mit seinem Owner auf das Ursprungs-Owner Feld. Eine Referenz zu einem Objekt das in einer anderen Liste hängt hätte demnach auch einen anderen owner. : list? vm.vertraege @owner /owner = ; Satz: owner modulo 32 ergibt die Adresse des Parents (obj) Konventionen: obj>attribut : 3 cells + ; obj.attribut : obj>attribut @ ; attribute/ : Sind Listen =attribute= : Sind Referenzen R.classes/ R.vertraege/ Wir brauchen noch Iteratoren. Argument1 Argument2 Function Root_01 R .extensions/ find-class Root: $0 next (immer 0) $1 owner (immer 0) $2 class (Zeigt auf Root-Class) $3 *free* (die Free-Block Liste) $4 *classes* (Zeiger auf die Class-Blöcke) $5 *user* (unsere Anwender) $6 *nullstr* (Ein Pointer auf einen 0-String Block) $7 *extensions* Root-ext-01: $0 (Bits, Version) $6 end (das Ende des Hauptspeichers) $1 $2 $3 $4 $5 $6 $7 (Von meinem Schatz!):-))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) 1111111111111111111111111111111111111111111111111111 Was mir nicht gefällt ist dass wir keinen reinen Pointer in der Hand halten. Ich würde vielleicht doch folgende Erweiterung vorsehen $0 next $1 owner $2 class Kann ebenfalls auf ein obj zeigen $3 $4 $5 $6 $7 Die nächste Frage ist. Wenn ich auf ein Attribut im Objekt zugreife, z.B. class, also obj.class erhalte ich dann den owner oder die class ? Ich erwarte mir die class, sonst würde ich besser schreiben : obj>class ( obj -- &class) 2 cells + ; : obj>owner ( obj -- &next) cell+ ; : obj.class ( obj -- class) obj>class @ ; : obj.is ( class obj -- 0) obj.class = ; : obj.next ( obj -- next) obj:next @ ; ; blk-find (owner blk_id-blk|0) swap @ type : blk-get (owner blk_id--blk) swap (blk_id owner) @ type ( blk_id type| blk_id 0) if else \ Der Pointer war 0 then swap @ type = if ; then cell+ ; : vermittler.produktion (vm -- &prod) /extensions 101 blk-find /produktion ; vermittler_get_extension(101).produktion 101 blk-find Eine noch offene Frage sind die Dependents. Auch sie können sehr Zeit- intensiv werden, wenn sie als verkettete Liste angelegt werden. Typische Vertreter sind n:m Verbindungsobjekte. Die Zeitintensivität folgt aus dem Entfernen und Umhängen. Ich versuche nun ohne dependents aus zu kommen. Das Problem entsteht beim delete von Objekten die referenziert werden. Ich würde an dieser Stelle dem delete besondere Aufmerksamkeit schenken und vielleicht notwendige Aktionen dort ansetzen. Ist es vielleicht besser solche Objekte als 'gelöscht' zu markieren. Man könnte die ungültig gewordenen Referenzen durch suchen ermitteln oder eine GC erstellen. Das bringt mich zur Frage generell mit GC zu arbeiten ? Die Frage ist hierbei folgende. Gibt es einen Slot auf [2]-[7] der auf ein Objekt zeigt das gelöscht wurde. Woher weiss ich denn dass dieses Referenz überhaupt eine zu behandelnde Referenz darstellt. Und wenn es eine zu löschende RI ist, kann ich vermeiden dass ununterbrochen der GC angeworfen wird ?. Ich benötige in diesem Fall einen Iterator. ObjId.slot=>gültiges Obj. Infix vs. Prefix // Betrachte folgende Syntax foo(bar(), dog(brown(dog(0)))); // Äquivalent wäre etwa int vdog=dog(0); int vbrown=brown(vdog); vdog=dog(vbrown); vbar=bar(); foo(vbar, vdog); // Was die Auflösung der Infixnotation bedeutet // in 4ide würde das Ganze so aussehen: 0 dog brown dog bar foo // als kommentierter Code: 0 dog // Lege 0 auf den Stack führe die Funktion dog aus brown // nimm das Ergebnis von dog und führe brown aus dog // numm das Ergebnis von brown und führe nochmal dog aus bar // führe bar aus foo // führe die Hauptfunktion foo aus. // betrachten wir die Notationen neben einander, welche ist einfacher zu // verstehen ? C : foo(bar(), dog(brown(dog(0)))); Forth: 0 dog brown dog bar foo Lisp : (foo (bar) (dog (brown (dog 0)))) Nicht nur ist die Forth-Syntax leichter zu verstehen, auch der Parser ist deutlich einfacher. Es muss kein Parser-Baum erstellt, interpretiert und wieder abgebaut werden. Der Interpreter funktioniert wie folgt: 1. Suche das eingegebene Wort, wenn du es findest führe es aus 2. Wenn das Wort nicht gefunden wurde, versuche es in eine Zahl umzuwandeln und lege diese auf den Stack. 3. Wenn das auch nicht geklappt hat, dann gib einen Fehler aus. Der Compiler funktioniert wie folgt: 1. Suche das Wort im Makro-Verzeichnis und wenn es dort ist führe es aus. 2. Wenn das Wort nicht im Makro-Verzeichnis war, dann suche es als normale Funktion. Wenn du sie findest compiliere einen Funktionsaufruf dorthin 3. Wenn das Wort wieder nicht gefunden wurde versuche es in eine Zahl zu wandeln und compiliere eine Anweisung die bei der Ausführung die Zahl auf den Stack legt. 4. Wenn auch das nicht geklappt hat, gib einen Fehler aus. Die VM funktioniert wie folgt: Jede Anweisung ist ein xt (Execution Token). Das ist ein numerischer Index in eine Tabelle von Funktionen. Die VM führt in einer Endlosschleife Anweisung für Anweisung aus. Eine Anweisung kann eine Grundlagenfunktion wie z.B. * (multiplikation) oder JMP (Sprung) sein. Aber auch eine eigene Funktion, die solche Grundlagenfunktionen oder eigene definiert Funktionen aufrufen. Da wir die VM unter eigener Kontrolle haben ist es trivial ein Multitasking einzuführen. Sowohl cooperativ als auch preemtiv. Wir können breakpoints, watchpoints, watchdog ... was auch immer beliebig einsetzen. Der Phanatsie sind keine Grenzen gesetzt. Das wäre wohl mit dem GDB (Gnu Debugger) mit erheblich mehr Aufwand, wenn überhaupt möglich, verbunden. ########################### - Die Basis, wie funktioniert die Virtuelle Maschine. Eine Liste von Anweisungen. Eine Anweisung ist ein Word * SIGSEGV, SIGINT, terminate, Return und Daten-Stack - Wie funktioniert der Interpreter * Dictionary, Daten-Stack - Wie funktioniert der Compiler * Variablen, Funktionen, 4ide-Source-Code - Wie funktioniert die Datenbank * mmap, 32-Byte Blöcke, Result-Stack, qsort - Erweiterte Features, C ruft 4ide, 4ide ruft C, create does> Dateinamen und Quell-Blöcke Bidlschirm-Steuerung (Farben etc.) base64 tty, stdin, input Here/Dictionary/find tick Strings, Stringsegment Virtuelle-Maschine: Threaded Code, Primitive(jmp, jz), if/then, see Words/Macros/Interpreter/Compiler/load Forth-C C-Forth SIGINT/SIGSEGV/Terminate load-unwind