Stackmaschine, die nativ mit dynamischen Strings arbeitet?



  • Hallo!

    Für meine Skriptsprache möchte ich eine Stackmaschine implementieren, die nativ mit dynamische allokierten Strings arbeitet. Die Implementierung soll in ANSI C vorgenommen werden.

    Generell hab ich mir überlegt, das man Werte von Variablen (ebenfalls allesamt allokierte char-Zeiger) und Konstanten (Adressen sind bekannt) direkt auf den Stack legen kann, und zwischengespeicherte Werte mit einem Flag versehen werden, so daß der Speicher beim poppen wieder freigegeben wird (bzw. gecached und für einen nachfolgenden, zwischengespeicherten Wert, der in den allozierten Speicherbereich passt, wiederverwendet wird).

    Daher quasi für jedes Stapelelement eine Struktur

    struct _operand
    {
    	unsigned is_malloced:1;
    	char*	p;
    };
    

    Mir ist klar, dass solch eine Implementierung nicht gerade sehr Ressourcenschonend ist, aber ich brauche die Dynamik dahinter.

    Eventuell plane ich auch, für Berechnungen direkt double-Werte zu pushen, die aus Variablen oder Konstanten kommen, um diese nur einmal zu konvertieren und bis zur STORE in eine Variable im jeweiligen Datenformat zu belassen (ist natürlich deutlich schneller!). Dies wäre ein Optimierungsprozess meines Compilers.

    Meine Frage ist allerdings: Gibt es bereits solch eine Implementierung die ich mir ggf. mal anschauen könnte, oder was könnte ich an dieser Idee verbessern? Ist hier eine Stackmaschine überhaupt sinnvoll?

    Danke,
    ~code_pilot



  • Hallo

    Ich verstehe nicht ganz was du mit diesem stack bezwecken willst? Willst du damit Funktionsaufrufe abwickeln oder reverse polish was machen?

    Erläuter mal genauer, was das Ziel sein soll.

    WX



  • Er spricht von einer Stackmaschine - eigentlich ziemlich klar was das ist (Stackmaschine vs. Registermaschine). Und die Umgekehrte polnische Notation ist im Prinzip wie man Code für eine Stackmaschine schreibt, ja.

    Die MSIL (das ganze ".NET" Zeugs) verwendet z.B. auch eine Stackmaschine.



  • Jup exakt. Der Stack soll sowohl für reverse polish als auch für funktionsaufrufe und evtl. zur reservierung von Speicher für lokale Variablen von Funktionne dienen.

    Hmm die Intermediate Language von MS ist auch stack-basierend? Da wäre aber die Frage, ob die nativ mit Strings arbeiten können - und ein (überschaubares) Beispiel kann man sich sicherlich auch nicht davon ansehen (also ich will mich nicht in die Mono-Sourcen einlesen ;)).

    Grüße
    ~codepilot



  • code_pilot schrieb:

    Daher quasi für jedes Stapelelement eine Struktur

    struct _operand
    {
    	unsigned is_malloced:1;
    	char*	p;
    };
    

    wofür dieses 'is_malloced'?
    🙂



  • warum als bitfield? ds ganze wird doch eh auf volle bytes(mindestens) gepadded.



  • @fricky: ich schätze "is_malloced" ist false für String-Literals.

    @code_pilot:
    Das war auch nicht so sehr als Vorschlag gedacht was du dir anschauen könntest, sondern eher als Hinweis dass es nicht unüblich ist eine Stackmaschine für sowas zu verwenden.

    Und ja, sowohl die MSIL VM als auch die Java VM sind beides Stackmaschinen wenn ich mich nicht sehr irre.

    Beispiel was man sich ansehen könnte kann ich dir leider keines nennen, weiss ich einfach nix. Ich denke auch dass fertige Implementierungen eher schlecht als Beispiel funktionieren, da die wohl alle schon mehr oder weniger optimiert sein werden -- was der Leserlichkeit wohl kaum dient. Speziell wenn ein JIT Compiler im Spiel ist ist es vermutlich aus mit schönem verständlichen Code.

    Was deine Variablen angeht: viele Sprachen verwenden Variants - sei es nun String-basierte wie du sie beschreibst oder welche die intern mehrere verschiedene Typen haben können die dann on-the-fly konvertiert werden. Ob du mit doubles arbeiten willst musst du selbst entscheiden -- doubles haben halt gewisse Eigenschaften die für manche Dinge nicht ideal sind. z.B. wenn man mit Zahlen im Dezimalformat rechnet die auch mal Stellen hinter dem Komma haben dürfen.

    Wofür willst du überhaupt sowas basteln? Und hast du dir überlegt eine fertige Sache wie z.B. LUA zu verwenden?



  • Also wenn du "milde" Lektüren zu diesem Thema suchst, empfehle ich mal "Jack Crenshaw - Lets Write a compiler" (findest du auf compilers.iecc.org) und natürlich "Compilers Principles, Techniques and Tools" von Alfred V.Aho (The Dragon Book). Wirths "Compilerbau" ist auch noch Ok, vielleicht aber schon etwas zu trocken.

    Prinzipiell solltest du aber den Rat mit Variants zu arbeiten nicht verfolgen. Dafür gibt es Symbolbäume die genau den Typ, Länge und ggf. Inhalt einer Variable definieren. (Ich hoffe mal du hast sowas bereits in der einen oder anderen Form implementiert? Wenn nicht kann ich dir mal eine meiner implementations zuschiessen)

    Für Funktionsaufrufe ist das Prinzip recht einfach. Du unterteils den Stack einfach in 2 Hälften, bei Intel ist das zb der Base Pointer (BP Register = meist SP+return value+return address). Unten (also in die Richtung wo der Stack in den Speicher hineinwächst) hast du deine lokalen Variablen (BP-n), und Oben (BP+n) hast du deine return address und returnwert. Das lässt sich teilweise auch mit Registern lösen, ist aber glaube ich derzeit nicht Sinn der Übung. Der Typ und Länge (ggf. wieder Inhalt) wird durch den Parser mittels Symbolbaum bestimmt.

    WX



  • Hallo zusammen,

    danke für die vielen und hilfreichen Antworten!

    hustbaer schrieb:

    @code_pilot:
    Das war auch nicht so sehr als Vorschlag gedacht was du dir anschauen könntest, sondern eher als Hinweis dass es nicht unüblich ist eine Stackmaschine für sowas zu verwenden.
    Und ja, sowohl die MSIL VM als auch die Java VM sind beides Stackmaschinen wenn ich mich nicht sehr irre.

    Das Java eine Stackmaschine benutzt hab ich auch gelesen, es ist echt gut schonmal zu wissen das sowas auch für wirklich produktive Systeme genutzt wird.

    hustbaer schrieb:

    Ob du mit doubles arbeiten willst musst du selbst entscheiden -- doubles haben halt gewisse Eigenschaften die für manche Dinge nicht ideal sind. z.B. wenn man mit Zahlen im Dezimalformat rechnet die auch mal Stellen hinter dem Komma haben dürfen.

    Das ist mir bekannt, aber es sollen mit meiner Sprache keine wissenschaftlichen Berechnungen durchgeführt werden. Es geht in erster Linie um die Einfachheit, möglichst wenig Code für ein mögliches hohes Resultat zu schreiben.

    hustbaer schrieb:

    Wofür willst du überhaupt sowas basteln? Und hast du dir überlegt eine fertige Sache wie z.B. LUA zu verwenden?

    Ich programmiere eine Skriptsprache, die bereits schon einen sehr hohen Bekanntheitsgrad hat, das Problem ist nur, das die Vorgängerversionen einen Interpreter haben, der wirklich aus trial-and-error programmierten Techniken entstanden ist. Wie ein richtiger Parser funktioniert, davon hatte ich bis zur letzten Version (deren Release vor drei Jahren war!) gar keine bzw. sehr wenig Ahnung.
    Inzwischen habe ich durch ein privates Compilerbaustudium (= viel Lesen und Experimentieren!) sehr viel über Parsingtechniken, sowohl resursive-descent LL als auch tabellengesteuerte LL/LR/LALR/SLR und Packrat gelernt, hab sogar meinen eigenen Parser Generator geschrieben, um wirklich ins Detail zu gehen, vor allem bei LR(1) und LALR(1). Nur haben meine bisherigen Compiler die ich programmiert habe immer rekursive Strukturen als "Maschinen" erzeugt, die dann durch einen auf diesem Baum ablaufendem Interpreter ausgeführt wurden (im Grunde handelte es sich bei diesem Maschinen um ein attributiertes Abbild des Parsebaums, der rekusriv ausgeführt wurde). Da ich aber für meine Skriptsprache nun auch einen Optimizer schreiben will, muss ich ja eine Art Bytecode erzeugen, die dann durch eine Stackmaschine implementiert wird. Und ich habe festgestellt, dass dieses Thema, Compilerdesign genau mein Ding ist. Es macht wirklich irrsinnig viel Spaß an sowas praktisch rumzucoden und diesen theoretischen Kram mal praktisch umzusetzen und zu nutzen. Nur mit der Theorie alleine hab ich's halt nicht so 😉 - bin hat ein pragmatischer Coder, der wissen will, wie's geht ohne sich durch unverständliche Formeln und mathematischen Quatsch durchzuwühlen (vielleicht bin ich auch einfach nur zu doof dafür :)).

    WeaponX2007 schrieb:

    Also wenn du "milde" Lektüren zu diesem Thema suchst, empfehle ich mal "Jack Crenshaw - Lets Write a compiler" (findest du auf compilers.iecc.org) und natürlich "Compilers Principles, Techniques and Tools" von Alfred V.Aho (The Dragon Book). Wirths "Compilerbau" ist auch noch Ok, vielleicht aber schon etwas zu trocken.

    Sind mir alle bekannt, das Drachenbuch und Wirths Compilerbau habe ich auch hier. Die Stackmaschine von Wirth habe ich auch in C mal nachprogrammiert, daher ist mir die Logik mit den Funktionsaufrufen (Stackframe) auch schon bekannt. Aber ich werd wohl nochmal im Crenshaw gucken, was der so über Stackmaschinen schreibt.

    WeaponX2007 schrieb:

    Prinzipiell solltest du aber den Rat mit Variants zu arbeiten nicht verfolgen. Dafür gibt es Symbolbäume die genau den Typ, Länge und ggf. Inhalt einer Variable definieren. (Ich hoffe mal du hast sowas bereits in der einen oder anderen Form implementiert? Wenn nicht kann ich dir mal eine meiner implementations zuschiessen)

    Auf Variants zu gehen hatte ich auch nicht vor, aber von den Symbolbäumen könnte ich sicherlich auch noch was lernen. Kannst du mir deinen Source dann mal geben, sofern du ihn aus der Hand geben würdest?

    WeaponX2007 schrieb:

    [...] ... wird durch den Parser mittels Symbolbaum bestimmt.

    Ich bin auch irgendwie aus dem Thema raus, wie Wirth's VM für PL/0 nochmal im Detail funktionierte, ich denke da werde ich auch das Feature "dynamische Parameterlisten" draus herleiten können! Aber nochmal danke für die Erklärung!

    Ich denke ich sollte mal klein Anfangen und dann alles weitere ausbauen - und dann gucken, inwieweit das performant ist.

    Grüße und Danke schonmal!
    ~codepilot 😃



  • Ich denke ich beschäftige mich jetzt erstmal ein wenig mit bestehenden Systemen wie FORTH, vielleicht kann ich davon etwas abkupfern. Danke erstmal für eure Hilfe.

    ~cp


Log in to reply