SimpleVM #4: Funktionen

Category: 

In diesem Artikel erweitern wir die VM um Funktionen. Außerdem erweitern wir die VM um lokale Variablen, wodurch der Bytecode etwas effektiver wird.

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

Funktionen

Bisher sind wir nur in der Lage einen Codeblock auszuführen. Nun wollen wir aber auch den Code anderer Funktionen aufrufen können. Dazu erstellen wir den neuen Typen VMFunction, welcher ebenfalls von VMObject erbt. Außerdem erweitern wir den abstrakten Typen VMObject um eine weitere Methode, welche für Funktionsaufrufe dient:

public abstract class VMObject {
  // ...
  public VMObject call(VMObject[] params) throws VMException {
    throw new VMException();
  }
}
package com.infectedbytes.tutorials.simplevm.types;
import com.infectedbytes.tutorials.simplevm.VMException;
public class VMFunction extends VMObject {
  public final byte[] code;

  public VMFunction(byte[] code) {
    this.code = code;
  }
 
  @Override
  public VMObject call(VMObject[] params) throws VMException {
    // ???
  }
}

Doch was genau machen wir nun in der call Methode? Im Grunde soll diese wiederum die VM run Methode mit neuem Code aufrufen, allerdings benötigt dann jede Funktion eine Referenz auf die VM. Das wäre jedoch etwas unschön. Warum benötigen wir die VM Klasse überhaupt? Im Grunde sind es ja die Funktionen, welche den Code ausführen. Daher können wir den Code der run-Methode in die call-Methode der VMFunction packen und anschließend die VM-Klasse löschen.

package com.infectedbytes.tutorials.simplevm.types;

import java.util.Scanner;
import java.util.Stack;

import com.infectedbytes.tutorials.simplevm.OpCode;
import com.infectedbytes.tutorials.simplevm.VMException;

public class VMFunction extends VMObject {
  private final byte[] code;

  public VMFunction(byte[] code) {
    this.code = code;
  }

  @Override
  public VMObject call(VMObject[] params) 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++];
      VMObject obj, other;
      int jump;
      switch (instruction) {
        case OpCode.DUP:
          stack.push(stack.peek());
          break;
        case OpCode.PUSH:
          byte value = code[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;
        case OpCode.READ:
          stack.push(new VMInt(in.nextInt()));
          break;
        case OpCode.IF_EQ:
          jump = code[pc++];
          other = stack.pop();
          obj = stack.pop();
          if (obj.equals(other)) pc += jump;
          break;
        case OpCode.IF_NE:
          jump = code[pc++];
          other = stack.pop();
          obj = stack.pop();
          if (!obj.equals(other)) pc += jump;
          break;
        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;
        case OpCode.IF_LT:
          jump = code[pc++];
          other = stack.pop();
          obj = stack.pop();
          if (obj.compareTo(other) < 0) pc += jump;
          break;
        case OpCode.IF_LE:
          jump = code[pc++];
          other = stack.pop();
          obj = stack.pop();
          if (obj.compareTo(other) <= 0) pc += jump;
          break;
        case OpCode.JUMP:
          jump = code[pc++];
          pc += jump;
          break;
      }
    }
    in.close();
    return null;
  }
}

Wie man sieht, bekommt diese Methode nun die Parameter als Array übergeben, vorerst ignorieren wir die. Nun fügen wir einen neuen OpCode CALL hinzu. Dieser soll ein Byte als Parameter haben, welches angibt, wieviele Werte wir vom Stack als Parameter an die Funktion geben wollen. Im Stack liegt dann direkt unter den Parametern auch die Funktion, die aufgerufen wird. Wenn der Aufruf beendet ist, wird das Ergebnis auf den Stack gelegt.

Doch was wenn wir eine void Funktion aufrufen wollen? Hier mogeln wir etwas und erlauben keine void Funktionen. Falls man dennoch eine solche Funktion nutzen möchte, so kann man einfach null zurückgeben und nach dem Aufruf einfach das oberste Element vom Stack entfernen. Das sollte man auch unbedingt machen, da der Stack sonst ggf. sehr schnell wachsen könnte.

case OpCode.POP:
  stack.pop();
  break;
case OpCode.CALL:
  int n = code[pc++];
  VMObject[] args = new VMObject[n];
  for (int i = n - 1; i >= 0; i--) {
    args[i] = stack.pop();
  }
  obj = stack.pop();
  stack.push(obj.call(args));
  break;

Hier sollte man darauf achten, dass wir das Parameter Array rückwärts füllen. Da der Stack ja von unten nach oben wächst und somit das letzte Argument ganz oben auf dem Stack liegt.
Sinnvollerweise sollten wir jetzt auch noch eine RETURN Anweisung einführen, welche einfach den obersten Wert vom Stack zurückgibt:

case OpCode.RETURN:
  return stack.pop();

Wie bekommt man Funktionen auf den Stack?

Wir können nun zwar Funktionen theoretisch aufrufen, aber dazu müssen wir sie erst einmal auf den Stack bekommen! Bisher haben wir aber keinerlei Möglichkeit dazu.
Hierzu können wir jeder VMFunction bei der Konstruktion einfach ein Array an anderen Funktionen mitgeben. Mit einem passenden OpCode können wir dann ein Element des Arrays auf den Stack legen.
Hier mag man vielleicht protestieren, da wir somit im Voraus alle benötigten Funktionen kennen müssen. Aber keine Sorge, hier geht es erst einmal nur um die Funktionen, die wir direkt kennen wollen. Im OOP Kapitel zeige ich euch dann noch wie man an Funktionen heran kommt, ohne sie direkt bei der Konstruktion mitzugeben.

public class VMFunction extends VMObject {
  private final byte[] code;
  private final VMFunction[] functions;

  public VMFunction(byte[] code, VMFunction[] functions) {
    this.code = code;
    this.functions = functions;
  }

  @Override
  public VMObject call(VMObject[] params) 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++];
      VMObject obj, other;
      int jump;
      switch (instruction) {
        // ...
        case OpCode.PUSH_FUNCTION:
          obj = functions[code[pc++]];
          stack.push(obj);
          break;
      }
    }
    in.close();
    return null;
  }
}

Damit können wir nun ein Programm schreiben, welches eine andere Funktion aufruft:

public class Program {
  public static void main(String[] args) {
    VMFunction[] functions = new VMFunction[2];

    functions[0] = new VMFunction(new byte[] {
        PUSH_FUNCTION, 1,
        CALL, 0
    }, functions);

    functions[1] = new VMFunction(new byte[] {
        PUSH, 42,
        PRINT
    }, functions);
    try {
      functions[0].call(null);
    } catch(VMException e) {
      e.printStackTrace();
    }
  }
}

Function 0 legt als erstes Function 1 auf den Stack und ruft diese dann ohne Parameter auf. Function 1 legt die Zahl 42 auf den Stack und gibt den Wert auf der Konsole aus.

Damit sind die Funktionen nahezu komplett. Jetzt müssen wir nur noch irgendwie an die Parameter herankommen. Doch dazu müssen wir uns erst noch mit lokalen Variablen beschäftigen.

Lokale Variablen

Wie bereits in der Einleitung erklärt, kann man eine Stack Machine etwas effizienter gestalten, indem man sie um lokale Variablen erweitert.
Doch wieviele lokale Variablen soll eine Funktion haben? Ganz einfach, jede Funktion gibt bei der Konstruktion an, wieviele sie benötigt:

public VMFunction(byte[] code, VMFunction[] functions, int localCount) {
  this.code = code;
  this.functions = functions;
  this.localCount = localCount;
}

Nun müssen wir nur noch ein Array der passenden Größe erzeugen, aber Achtung! Dieses Array darf nicht als Instanzvaraible angelegt werden! Denn ansonsten zerstören wir uns die rekursiven Aufrufe!
Das Array der lokalen Variablen, wird immer innerhalb der call-Methode neu erzeugt:

public VMObject call(VMObject[] params) throws VMException {
  Scanner in = new Scanner(System.in);
  Stack<VMObject> stack = new Stack<VMObject>();
  VMObject[] locals = new VMObject[localCount];
  // ...
}

Nun wollen wir natürlich noch lokale Variablen laden und speichern:

case OpCode.LOAD:
  obj = locals[code[pc++]];
  stack.push(obj);
  break;
case OpCode.STORE:
  locals[code[pc++]] = stack.pop();
  break;

Falls wir nun irgendwelche komplizierten Werte berechnen, können wir sie einfach als lokale Variablen speichern und beliebig oft laden, ohne sie neu berechnen zu müssen!

Parameter

Nun wollen wir auch auf die Parameter einer Funktion zugreifen. Doch warum sollten wir dafür die lokalen Variablen benötigen? Können wir nicht einfach einen neuen OpCode GET_PARAM einbauen, welcher uns einfach einen Parameter auf den Stack legt?
Klar kann man das machen, es funktioniert auch wunderbar. Aber im Grunde bringt es einem mehr, wenn man die Parameter einfach als lokale Variablen betrachten kann. Um zu verstehen, warum wir das wollen, sollte man sich den folgenden Beispielcode ansehen:

function test(x)
  local y=123
  print(x+y);
end

Bei so einem Code müssten wir nun immer überprüfen, ob eine Variable eine lokale Variable ist oder ein Parameter. Und was passiert wenn jemand den Parameter wieder überschreiben will: x=42 ?
Dafür bräuchten wir dann ja ein SET_PARAM oder sollen wir in dem Fall das ganze in eine Variable schreiben? ...
Um das also alles so übersichtlich wie möglich zu halten, sollte man die Parameter direkt als lokale Variablen betrachten können.
Dementsprechend müssen wir die Parameter erst in die lokalen Variablen kopieren. Allerdings müssen wir aufpassen, denn der Aufrufer kann ja beliebig viele Parameter mitgeben! Daher bietet es sich an, der Funktion bei ihrer Konstruktion zu sagen, wieviele Parameter sie denn maximal annehmen darf.

private final int paramCount;
public VMFunction(byte[] code, VMFunction[] functions, int localCount, int paramCount) {
  this.code = code;
  this.functions = functions;
  this.localCount = localCount;
  this.paramCount = paramCount;
}

Falls paramCount größer ist als localCount, kann man auch direkt einen Fehler werfen. Ansonsten müssen wir nur noch die Parameter in die lokalen Variablen kopiert:

public VMObject call(VMObject[] params) throws VMException {
  // ...
  VMObject[] locals = new VMObject[localCount];
  if (params != null && params.length > 0) {
    int len = Math.min(params.length, paramCount);
    System.arraycopy(params, 0, locals, 0, len);
  }
  // ...
}

Und nun alles zusammen

Damit haben wir nun lokale Variablen, Funktionen und Zugriff auf die Parameter. Das ganze können wir nun in einem ganz einfachen Programm einmal testen:

public class Program {
  public static void main(String[] args) {
    VMFunction[] functions = new VMFunction[2];

    functions[0] = new VMFunction(new byte[] {
        PUSH_FUNCTION, 1,
        PUSH, 42,
        PUSH, 100,
        CALL, 2,
        PRINT
    }, functions, 0, 0);

    functions[1] = new VMFunction(new byte[] {
        LOAD, 0,
        LOAD, 1,
        IF_GE, 3,
        LOAD, 1,
        RETURN,
        LOAD, 0,
        RETURN
    }, functions, 2, 2);

    try {
      functions[0].call(null);
    } catch(VMException e) {
      e.printStackTrace();
    }
  }
}

Function 0 legt die beiden Werte 42 und 100 auf den Stack und ruft Function 1 auf. Diese Function gibt nun den größeren der beiden Werte zurück.

Abschluss

Damit haben wir unsere kleine VM schon um einiges voran gebracht! Jetzt wäre es nur schön auch noch eine Art Objektsystem zu haben. Doch wie das geht lernen wir im nächsten Teil: #5 OOP

Code zu diesem Artikel: 04_functions.zip