SimpleVM #2: Prototyp

Category: 

In diesem Artikel soll es darum gehen, einen simplen Prototypen einer virtuellen Maschine zu entwickeln. Als grundlegende Befehle reichen uns vorerst Rechenoperationen und die Ausgabe auf der Konsole.

Dieser Artikel ist Teil der Serie: Simple Virtual Machine
#1 Einstieg
#2 Prototyp
#3 Bedingte Sprünge
#4 Funktionen
#5 OOP
#6 Globale Variablen und Java Funktionen
#7 Operator overloading
#8 Details & Loading from File
#9 Bonus: Assemblercode

Typsystem

Als erstes kümmern wir uns um das grobe Typsystem. Wie bereits im letzten Artikel erläutert, wollen wir als "einfache" Datentypen nur int, float und string unterstützen. Zusätzlich hätten wir gerne noch Funktionen und Objekte, aber darum kümmern wir uns später. Da wir die verschiedenen Objekte allesamt auf dem Stack speichern können wollen, sollten sie eine gemeinsame Oberklasse haben. Am besten definiert man dazu eine neue abstrakte Klasse, welche alle Operationen bereitstellt, die von den jeweiligen Datentypen genutzt werden sollen.
Die Add-Operation sollte am besten direkt von allen unterstützt werden. Integer und Floats führen dadurch eine einfache Addition aus, während Strings konkateniert werden. Ebenso bietet es sich an, auch die anderen mathematischen Operation direkt in die Oberklasse aufzunehmen. Einen String zu dividieren macht vielleicht wenig Sinn, jedoch vereinfacht sich unser VM Design durch diese allgemeine Schnittstelle ungemein. Denn ohne diese Vereinfachung müssten wir bei einer Addition immer erst prüfen, ob die Typen denn auch ints oder floats sind.
Für Operationen die nicht ausgeführt werden sollten, können wir einfach eine Exception werfen. Die String add Methode konkateniert also zwei Strings, während die String div Methode eine Exception wirft.

Die Exception Klasse kann man sehr einfach gestalten:

package com.infectedbytes.tutorials.simplevm;
public class VMException extends Exception {
  public VMException() {}
  public VMException(String msg) {
    super(msg);
  }
  public VMException(Exception e) {
    super(e);
  }
}

Das allgemeine VMObject beinhaltet vorerst nur die Rechenoperationen. Wenn eine Unterklasse eine der Operationen unterstützt, dann überschreibt sie die jeweilige Operation einfach:

package com.infectedbytes.tutorials.simplevm.types;
public abstract class VMObject {
  public VMObject add(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject sub(VMObject other) throws VMException {
    throw new VMException();
  }
}

Die VMString-Klasse erhält als Konstruktor Parameter den eigentlichen String. Die add-Methode gibt dann einen neuen String zurück, welcher nichts weiter als die Konkatenation des gespeicherten Strings, sowie dem other-Objekt ist. Wir rufen auf dem anderen Objekt die toString-Methode auf, dementsprechend sollten auch all unsere Datentypen diese sinnvoll implementieren.

package com.infectedbytes.tutorials.simplevm.types;
public final class VMString extends VMObject {
  public final String value;
  public VMString(String value) {
    this.value = value;
  }

  @Override
  public VMObject add(VMObject other) throws VMException {
    return new VMString(value + other.toString());
  }

  @Override
  public String toString() {
    return value;
  }
}

Da wir zwei verschiedene Zahlentypen haben, sollten wir ihre Gemeinsamkeiten in einer gemeinsamen Number Oberklasse definieren. Um es etwas übersichtlicher zu gestalten, bietet es sich an diese in ein separates package zu legen:

package com.infectedbytes.tutorials.simplevm.types;
public abstract class VMNumber extends VMObject {
  public abstract int asInt();
  public abstract float asFloat();
}
package com.infectedbytes.tutorials.simplevm.types;
public final class VMInt extends VMNumber {
  public final int value;
  @Override
  public int asInt() {
    return value;
  }

  @Override
  public float asFloat() {
    return value;
  }

  public VMInt(int value) {
    this.value = value;
  }

  @Override
  public String toString() {
    return String.valueOf(value);
  }

  @Override
  public VMObject add(VMObject other) throws VMException {
    if (other instanceof VMInt)
      return new VMInt(value + ((VMInt)other).value);
    if (other instanceof VMFloat)
      return new VMFloat(value + ((VMFloat)other).value);
    return new VMString(value + other.toString());
  }

  @Override
  public VMObject sub(VMObject other) throws VMException {
    if (other instanceof VMInt)
      return new VMInt(value - ((VMInt)other).value);
    if (other instanceof VMFloat)
      return new VMFloat(value - ((VMFloat)other).value);
    throw new VMException();
  }
}

package com.infectedbytes.tutorials.simplevm.types;
public final class VMFloat extends VMNumber {
  public final float value;
  @Override
  public int asInt() {
    return (int)value;
  }

  @Override
  public float asFloat() {
    return value;
  }

  public VMFloat(float value) {
    this.value = value;
  }
  @Override
  public String toString() {
    return String.valueOf(value);
  }

  @Override
  public VMObject add(VMObject other) throws VMException {
    if (other instanceof VMNumber)
      return new VMFloat(value + ((VMNumber)other).asFloat());
    return new VMString(value + other.toString());
  }
  @Override
  public VMObject sub(VMObject other) throws VMException {
    if (other instanceof VMNumber)
      return new VMFloat(value - ((VMNumber)other).asFloat());
    throw new VMException();
  }
}

Damit sind unsere einfachen Typen erst einmal fertig. Als nächstes sind dann die Instruktionen an der Reihe.

OpCodes

Unser virtueller Programmcode besteht aus einer Folge von Instruktionen, diese bestehen wiederum aus einem OpCode und ggf. Parametern. Grundsätzlich kann man diese OpCodes als Enums realisieren, allerdings besteht unser Code aus einer Folge von Bytes und daher müssten wir das jeweilige Byte erst in den Enum umwandeln. Diesen Umweg sparen wir uns lieber und definieren die Codes direkt als Byte Konstanten.
Lasst uns nun eine OpCode Klasse erstellen, in welcher wir nur unsere OpCodes als Konstanten definieren:

package com.infectedbytes.tutorials.simplevm;
public class OpCode {
  public static final byte DUP = 0x00;
  public static final byte PUSH = 0x01;
  public static final byte ADD = 0x02;
  public static final byte SUB = 0x03;
  // ...
  public static final byte PRINT = 0x10;
  // ...
  private OpCode() {}
}

Wie man die einzelnen Konstanten durchnummeriert, ist im Grunde egal, das Wichtige ist nur, dass kein Wert mehrmals verwendet werden darf. Idealerweise sollten die Konstanten allesamt aufsteigend durchnummeriert werden. Zusätzlich sollte man noch einen privaten Konstruktor definieren, damit niemand auf die Idee kommt ein OpCode-Objekt zu erzeugen.
Für den Anfang reicht es uns nur wenige OpCodes zu definieren. Zwei mathematische Befehle reichen uns zum testen, jedoch benötigen diese auch bereits Werte auf dem Stack, daher brauchen wir auch noch einen push Befehl, welcher ein Byte auf den Stack legt. Der print Befehl soll den obersten Wert vom Stack auf der Konsole ausgeben. Zusätzlich nutzen wir noch den duplicate Befehl, welcher das oberste Element des Stack dupliziert. Dies ist praktisch, wenn wir Zwischenergebnisse ausgeben wollen.

VM

Damit fehlt uns nur noch die Ausführungslogik, also die eigentliche VM. Grundsätzlich sieht das so aus, dass der sogenannte ProgramCounter (pc) immer auf die nächste Instruktion zeigt.
Immer wenn wir eine Instruktion lesen, erhöhen wir den pc, damit wir im nächsten Schleifendurchlauf auch den nächsten Befehl beziehen können. Mit Hilfe eines Switch-Statements prüfen wir immer um welchen Befehl es sich denn genau handelt. Bei Bedarf können wir dann noch weitere Parameter einlesen.

package com.infectedbytes.tutorials.simplevm;
import java.util.Stack;
import com.infectedbytes.tutorials.simplevm.types.VMInt;
import com.infectedbytes.tutorials.simplevm.types.VMObject;

public class VM {
  public void run(byte[] code) throws VMException {
    Stack<VMObject> stack = new Stack<VMObject>();
    int pc = 0;
    while (pc < code.length) {
      byte instruction = code[pc];
      pc++;
      VMObject obj, other;
      switch (instruction) {
        case OpCode.DUP:
          stack.push(stack.peek());
          break;
        case OpCode.PUSH:
          byte value = code[pc];
          pc++;
          stack.push(new VMInt(value));
          break;
        case OpCode.ADD:
          other = stack.pop();
          obj = stack.pop();
          stack.push(obj.add(other));
          break;
        case OpCode.SUB:
          other = stack.pop();
          obj = stack.pop();
          stack.push(obj.sub(other));
          break;
        case OpCode.PRINT:
          System.out.println(stack.pop());
          break;
      }
    }
  }
}

Betrachten wir nun noch einmal kurz die Instruktionen. Falls es sich um eine push-Instruktion handelt, so benötigen wir noch den Wert, welchen wir auf den Stack legen sollen. Da der pc bereits erhöht wurde, zeigt er nun direkt auf unseren Parameter. Diesen lesen wir aus, erhöhen den pc erneut und legen den ausgelesenen Wert auf den Stack. Add und sub holen sich jeweils die beiden obersten Werte vom Stack, führen die jeweilige Operation aus und legen das Ergebnis wiederum auf den Stack. Anschließend haben wir noch die beiden Befehle dup und print. Dup dupliziert nur den obersten Wert, während print ihn auf der Konsole ausgibt.

VM Test

Jetzt sind wir soweit, ein erstes kleines Test Programm laufen zu lassen. Dieses soll erst einmal nur folgende Berechnung durchführen und das Ergebnis ausgeben: 50-10+2
Den Code müssen wir momentan noch direkt als byte Array angeben:

package com.infectedbytes.tutorials.simplevm;
public class Program {
  public static void main(String[] args) {
    byte[] code = {
        OpCode.PUSH, 50,
        OpCode.PUSH, 10,
        OpCode.SUB,
        OpCode.PUSH, 2,
        OpCode.ADD,
        OpCode.PRINT
    };
    VM vm = new VM();
    try {
      vm.run(code);
    } catch(VMException e) {
      e.printStackTrace();
    }
  }
}

Um es etwas übersichtlicher zu gestalten, kann man auch einen sogenannten statischen Import durchführen, wodurch wir nicht immer OpCode.xyz schreiben müssen:

package com.infectedbytes.tutorials.simplevm;
import static com.infectedbytes.tutorials.simplevm.OpCode.*;
public class Program {
  public static void main(String[] args) {
    byte[] code = {
        PUSH, 50,
        PUSH, 10,
        SUB,
        PUSH, 2,
        ADD,
        PRINT
    };
    // ...
  }
}

Wenn wir das ganze ausführen, erhalten wir wie erwartet das Ergebnis 42. Doch immer und immer dieselbe Berechnung auszuführen ist relativ langweilig. Daher sollten wir die VM noch um zwei Dinge erweitern:

  • Eingaben
  • Bedingte Sprünge

Mehr dazu im nächsten Teil: #3 Bedingte Sprünge

Der Quellcode zum derzeitigen Stand: 02_proto.zip