SimpleVM #3: Bedingte Sprünge

Category: 

Dieses Mal geht es darum, die VM um bedingte Sprünge zu erweitern. Dadurch erhalten wir endlich mehr dynamik in unserer VM.

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

Eingaben

Um ganz simpel anzufangen, können wir einfach einen weiteren OpCode READ erzeugen. Wenn dieser ausgeführt wird, lesen wir eine Zahl von der Konsole ein und legen sie auf den Stack:

// ...
public class VM {
  public void run(byte[] code) throws VMException {
    Scanner in = new Scanner(System.in); // Scanner zum einlesen erzeugen
    Stack<VMObject> stack = new Stack<VMObject>();
    int pc = 0;
    while (pc < code.length) {
      // ...
      switch (instruction) {
        // ...
        case OpCode.READ:
          stack.push(new VMInt(in.nextInt())); // Zahl einlesen und auf den Stack legen
          break;
      }
    }
    in.close(); // Scanner wieder schließen
  }
}

Bedingte Sprünge

Bisher läuft jedes Programm immer exakt gleich ab. Dies können wir jedoch ändern, indem wir if-Abfragen hinzufügen. Doch wie genau funktioniert eine if-Abfrage?

if x>y then
  do something
end if

Im Grunde ist dies recht einfach. Falls die Bedinung true ergibt wird der Block ausgeführt, ansonsten übersprungen. Überspringen heißt, dass wir unseren pc um einen bestimmten Wert erhöhen.
Betrachten wir dazu erst einmal nur die beiden Befehle IF_EQ und IF_NE. Der erste führt genau dann einen Sprung durch, wenn die beiden obersten Werte auf dem Stack gleich sind. Der zweite führt den Sprung aus, wenn sie eben nicht gleich sind.

case IF_EQ:
  byte jump = code[pc];
  pc++;
  other = stack.pop();
  obj = stack.pop();
  if(other == obj) pc += jump;
  break;

Erst einmal holen wir uns den Parameter, welcher angibt wieweit gesprungen werden soll. Danach holen wir die beiden obersten Objekte vom Stack und vergleichen sie anschließend. Falls sie gleich sind springen wir. Doch moment, wir können dir Objekte nicht einfach mit == vergleichen. Falls es z.B. zwei ints sind, so sollen deren Werte verglichen werden. Wenn es strings sind, so soll deren equals Methode genutzt werden. Da dies wieder komplett von dem Objekt selbst abhängt, ist es das Beste dem Objekt die Überprüfung zu überlassen.
Hier können wir wieder die abstrakte VMObjekt Klasse um eine Methode erweitern:

public boolean equals(VMObject other){
  return this == other;
}

Standartmäßig wird einfach mit == geprüft, spezielle Objekte, wie Zahlen und Strings können selbst definieren wie sie sich verhalten:

public final class VMString extends VMObject {
  // ...
  @Override
  public boolean equals(VMObject other) {
    if (other == null) return false;
    if (other instanceof VMString)
      return value.equals(((VMString)other).value);
    return false;
  }
}
public final class VMFloat extends VMObject {
  // ...
  @Override
  public boolean equals(VMObject other) {
    if (other == null) return false;
    if (other instanceof VMNumber)
      return value == ((VMNumber)other).asFloat();
    return false;
  }
}
public class VMInt extends VMObject {
  // ...
  @Override
  public boolean equals(VMObject other) {
    if (other == null) return false;
    if (other instanceof VMFloat)
      return value == ((VMFloat)other).value;
    if (other instanceof VMInt)
      return value == ((VMInt)other).value;
    return false;
  }
}

Die einzelnen Objekte sind nun in der Lage auf Gleichheit bzw. Ungleichheit zu prüfen. Nachdem wir die beiden OpCodes IF_EQ und IF_NE hinzugefügt haben, können wir jetzt auch die VM korregieren:

public class VM {
  public void run(byte[] code) throws VMException {
    Scanner in = new Scanner(System.in);
    Stack<VMObject> stack = new Stack<VMObject>();
    int pc = 0;
    while (pc < code.length) {
      byte instruction = code[pc];
      pc++;
      VMObject obj, other;
      int jump;
      switch (instruction) {
        // ...
        case OpCode.IF_EQ:
          jump = code[pc];
          pc++;
          other = stack.pop();
          obj = stack.pop();
          if (obj.equals(other)) pc += jump;
          break;
        case OpCode.IF_NE:
          jump = code[pc];
          pc++;
          other = stack.pop();
          obj = stack.pop();
          if (!obj.equals(other)) pc += jump;
          break;
      }
    }
    in.close();
  }
}

Manchmal möchte man natürlich nicht nur unter bestimmten Bedingungen springen, sondern immer. Dafür sollten wir noch einen generellen Sprungbefehl einführen: JUMP
Dieser Befehl wird z.B. benötigt, um Schleifen zu implementieren. Eine while Schleife der folgenden Form:

while(condition) {
  do something
}

Sieht im Bytecode ungefähr so aus:

start:
if condition goto label
  do something
goto start
label:

Am Ende einer while Schleife wird direkt wieder zum Anfang gesprungen, dort wird die Bedingung geprüft und ggf. ans Ende gesprungen.
In unserer VM sieht das ganze dann so aus:

case OpCode.JUMP:
  jump = code[pc];
  pc++;
  pc += jump;
  break;

Sprung Test

Nun sind wir wieder soweit den bisherigen Code zu testen. Dazu wollen wir diesen Pseudocode ausführen:

start:
x = read()
if x!=0 goto start

Das Programm soll einfach die ganze Zeit eine Zahl vom Benutzer einlesen, bis dieser eine 0 eingibt. In unserem Bytecode Format sieht das dann so aus:

READ,
PUSH, 0,
IF_NE, -5

Als erstes lesen wir eine Zahl ein, pushen eine 0 auf den Stack und prüfen ob die beiden ungleich sind. Falls dem so ist, springen wir 5 Bytes zurück, d.h. wir landen wieder beim READ Byte.

Größer/kleiner Vergleiche

Als nächstes brauchen wir natürlich noch Vergleiche für größer/kleiner. Da uns dort die equals Methode nicht mehr weiterhilft, benötigen wir eine neue Methode. Dazu bietet es sich an eine compareTo Methode zu erstellen. x.compareTo(y) gibt dann -1, 0 oder 1 zurück, je nachdem ob x kleiner, gleich oder größer y ist.

public abstract class VMObject {
// ...
  public int compareTo(VMObject o) throws VMException {
    if (this == o) return 0;
    throw new VMException();
  }
}
public final class VMInt extends VMObject {
  // ...
  @Override
  public int compareTo(VMObject o) throws VMException {
    if (o instanceof VMFloat) {
      float other = ((VMNumber)o).asFloat();
      return Float.compare(value, other);
    }
    if (o instanceof VMInt) {
      int other = ((VMNumber)o).asInt();
      return Integer.compare(value, other);
    }
    throw new VMException();
  }
}
public final class VMFloat extends VMObject {
  // ...
  @Override
  public int compareTo(VMObject o) throws VMException {
    if (o instanceof VMNumber) {
      float other = ((VMNumber)o).asFloat();
      return Float.compare(asFloat(), other);
    }
    throw new VMException();
  }
}

Wenn man möchte kann man bei den Strings ebenfalls einen größer/kleiner Vergleich einbauen, welcher die lexikographische Ordnung wiederspiegelt:

public final class VMString extends VMObject {
  @Override
  public int compareTo(VMObject o) throws VMException {
    return value.compareTo(o.toString());
  }
}

Nun können unsere Objekte verglichen werden, fehlen nur noch die passenden OpCodes:

  • IF_GT: größer als
  • IF_GE: größer oder gleich
  • IF_LT: kleiner als
  • IF_LE: kleiner oder gleich
case OpCode.IF_GT:
  jump = code[pc++];
  other = stack.pop();
  obj = stack.pop();
  if (obj.compareTo(other) > 0) pc += jump;
  break;
case OpCode.IF_GE:
  jump = code[pc++];
  other = stack.pop();
  obj = stack.pop();
  if (obj.compareTo(other) >= 0) pc += jump;
  break;

IF_LT und IF_LE analog.

Um etwas Schreibarbeit zu sparen und auch um den Code übersichtlicher zu gestalten, sollten wir den code-Array Zugriff etwas optimieren. Der Code: x = code[pc]; pc++; ist äquivalent zu: x = code[pc++];

Im Grunde könnten wir jetzt auch auf die equals Methode verzichten und stattdessen einfach folgendes machen:

if (obj.compareTo(other) == 0) pc += jump;

Das ist im Grunde Geschmackssache, das Wichtige ist nur, dass wenn equals true ist, compareTo 0 liefert.

Der nächste Schritt ist dann der Aufruf von Funktionen. Mehr dazu im nächsten Teil: #04 Funktionen

Quellcode zu diesem Teil: 03_jumps.zip