SimpleVM #7: Operator overloading

Category: 

Durch Operator overloading kann man eigene Typen um Operatoren erweitern. Dadurch ist man in der Lage, Objekte direkt mit +, -, etc. zu Verarbeiten. In diesem Artikel wollen wir unsere Tables um dieses Feature erweitern.

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

Mehr Operatoren

Falls noch nicht geschehen, können wir erst einmal die Operatoren erweitern. Bisher haben wir uns auf Addition und Subtraktion beschränkt. Die anderen Operationen sind natürlich analog zu den bisherigen:

public abstract class VMObject {
  // ...
  public VMObject mul(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject div(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject mod(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject unary() throws VMException {
    throw new VMException();
  }
  public VMObject and(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject or(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject xor(VMObject other) throws VMException {
    throw new VMException();
  }
  public VMObject not() throws VMException {
    throw new VMException();
  }
  // ...
}

mul, div, etc. sind natürlich einfache Binäre Operatoren. Zusätzlich haben wir jetzt aber auch zwei Unäre Operatoren: unary und not. Diese haben keine Parameter, da sie nur auf einem Operanden arbeiten. Innerhalb von VMFloat und VMInt implementieren wir diese nun analog zu add und sub:

public class VMFloat extendsss VMNumber {
  @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();
  }
  @Override
  public VMObject mul(VMObject other) throws VMException {
    if (other instanceof VMNumber)
      return new VMFloat(value * ((VMNumber)other).asFloat());
    throw new VMException();
  }
  @Override
  public VMObject div(VMObject other) throws VMException {
    if (other instanceof VMNumber)
      return new VMFloat(value / ((VMNumber)other).asFloat());
    throw new VMException();
  }
  @Override
  public VMObject mod(VMObject other) throws VMException {
    if (other instanceof VMNumber)
      return new VMFloat(value % ((VMNumber)other).asFloat());
    throw new VMException();
  }

  @Override
  public VMObject unary() throws VMException {
    return new VMFloat(-value);
  }
  // ...
}

and, or, etc. implementieren wir für VMFloat nicht, sondern nur für VMInt:

public class VMInt extends VMNumber {
  // ...
  @Override
  public VMObject mul(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();
  }

  @Override
  public VMObject div(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();
  }

  @Override
  public VMObject mod(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();
  }

  @Override
  public VMObject unary() throws VMException {
    return new VMInt(-value);
  }
  @Override
  public VMObject and(VMObject other) throws VMException {
    if (other instanceof VMInt)
      return new VMInt(value & ((VMInt)other).value);
    throw new VMException();
  }
  @Override
  public VMObject or(VMObject other) throws VMException {
    if (other instanceof VMInt)
      return new VMInt(value | ((VMInt)other).value);
    throw new VMException();
  }
  @Override
  public VMObject xor(VMObject other) throws VMException {
    if (other instanceof VMInt)
      return new VMInt(value ^ ((VMInt)other).value);
    throw new VMException();
  }
  @Override
  public VMObject not() throws VMException {
    return new VMInt(~value);
  }
  // ...
}

Abschließend müssen wir selbstverständlich noch passende OpCodes erstellen und diese auch innerhalb der Ausführungslogik von VMFunction implementieren:

case OpCode.MUL:
  other = stack.pop();
  obj = stack.pop();
  stack.push(obj.mul(other));
  break;
case OpCode.DIV:
  other = stack.pop();
  obj = stack.pop();
  stack.push(obj.div(other));
  break;
case OpCode.MOD:
  other = stack.pop();
  obj = stack.pop();
  stack.push(obj.mod(other));
  break;
// etc.

Overloading

Jetzt sind wir soweit, das wir die Operatoren überladen können. Dazu überschreiben wir die jeweiligen Methoden in unserer VMTable Klasse.
Die Grundidee ist, dass ein Table besondere Funktionen bereitstellen kann, welche aufgerufen werden, wenn ein bestimmter Operator angewendet wird. Der Addition Operator, macht ja nichts anderes, als auf dem ersten Objekt die add-Methode aufzurufen und dabei den zweiten Operanden als Parameter zu übergeben. In unserem VMTable überschreiben nun diese add-Methode und schauen ob dieser Table eine Methode namens _add besitzt. Falls dem so ist, so wird die Methode aufgerufen und die beiden Parameter als Objekte übergeben.

public class VMTable extends VMObject {
  // ...
  @Override
  public VMObject add(VMObject other) throws VMException {
    VMObject fun = member.get("_add");
    if (fun != null)
      return fun.call(new VMObject[] {this, other});
    throw new VMException();
  }
}

Wie man es bereits aus dem OOP Kapitel kennt, ist der erste Parameter das Table Objekt selbst. Natürlich geben wir den Rückgabewert der _add-Methode direkt zurück. Falls es keine passende Methode gibt, so wird weiterhin eine Exception geworfen. Die anderen Operatoren implementieren wir natürlich analog.

Hier können wir nun noch einen Schritt weitergehen und sogar die call-Methode überschreiben. Dadurch können wir auf Wunsch auch einen Table als Funktion betrachten:

public class VMTable extends VMObject {
  // ...
  @Override
  public VMObject call(VMObject[] params) throws VMException {
    VMObject fun = member.get("_call");
    if (fun != null)
      return fun.call(params);
    throw new VMException();
  }
}

Hier müssen wir wieder eine kleine aber wichtige Entscheidung treffen. Soll der Table selber implizit als erster Parameter mitgegeben werden oder soll das manuell im Bytecode gemacht werden? Grundsätzlich hat beides Vor- und Nachteile. Hier werden wir uns darauf beschränken, dass der Benutzer den Table manuell als Parameter mitgeben muss. Grund für diese Entscheidung ist folgende Tatsache:
Wenn man diese _call-Methode nun direkt aufruft, verhält sie sich anders, als wenn man sie implizit über den Table aufruft:

table._call()
table()

Denn bei dem direkten Aufruf erhält die Methode keinen Parameter, während sie im zweiten Fall den Table als Parameter erhält. Da dies aus Benutzersicht kein homogenes Verhalten ist, habe ich mich hier dagegen entschieden. Daher muss der Benutzer in meinem Ansatz den Table bei Bedarf selbst als Parameter mitgeben.

Vergleiche

Was machen wir nun mit den Vergleichsoperationen? Grundsätzlich sollten wir diese auch überschreiben, aber hier gibt es ein kleines Problem. Bisher haben wir eine equals und eine compareTo Methode. Da wir bisher nur Zahlen mit größer/kleiner vergleichen konnten, haben wir einfach eine Exception geworfen, falls es nicht vergleichbar war. Jetzt wollen wir aber grundsätzlich alles miteinander vergleichen können, da ist es aber etwas unschön immer ne Exception zu erhalten, falls etwas nicht verglichen werden kann. Stattdessen wäre es angenehmer im Notfall einfach false zurückzugeben. Mit dem compareTo Ansatz geht dies leider nicht.
Dementsprechend ändern wir diesen Teil der VM. Die compareTo Methode löschen wir und ersetzen sie durch zwei andere Methoden: gt (greater than) und ge (greater equals)
Diese geben nur true oder false zurück und erfüllen somit genau unsere Anforderungen. Analog könnten auch lt und le Methoden definieren, jedoch brauchen wir sie nicht, da wir für sie einfach ge oder gt aufrufen und das Ergebnis negieren. Theoretisch könnten wir uns auch die ge-Methode sparen, indem wir auf gt || equals prüfen. Aus Performance Gründen behalte ich die ge-Methode jedoch.
Außerdem ändere ich den Namen der equals-Methode zu eq, damit der Name besser zu gt und ge passt. Dies ist allerdings nur eine Schönheitsanpassung.

public abstract class VMObject {
  // ...
  public boolean eq(VMObject other) throws VMException {
    return this == other;
  }
  public boolean gt(VMObject other) throws VMException {
    return false;
  }
  public boolean ge(VMObject other) throws VMException {
    return false;
  }
}

In unseren Unterklassen müssen wir dies natürlich auch noch anpassen:

public VMFloat extends VMNumber {
  // ...
  @Override
  public boolean eq(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMNumber)
      return ((VMNumber)other).asFloat() == value;
    return false;
  }
  @Override
  public boolean ge(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMNumber)
      return ((VMNumber)other).asFloat() >= value;
    return false;
  }
  @Override
  public boolean gt(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMNumber)
      return ((VMNumber)other).asFloat() > value;
    return false;
  }
}
public class VMInt extends VMNumber {
  @Override
  public boolean eq(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMInt) return ((VMInt)other).value == value;
    if (other instanceof VMFloat) return ((VMFloat)other).value == value;
    return false;
  }
  @Override
  public boolean ge(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMInt) return ((VMInt)other).value >= value;
    if (other instanceof VMFloat) return ((VMFloat)other).value >= value;
    return false;
  }
  @Override
  public boolean gt(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMInt) return ((VMInt)other).value > value;
    if (other instanceof VMFloat) return ((VMFloat)other).value > value;
    return false;
  }
}

Potentiel könnte man bei den Strings auch lexikographische Sortierung durchführen, dies lasse ich hier aber weg und lasse nur auf Gleichheit prüfen:

public final class VMString extends VMObject {
  // ...
  @Override
  public boolean eq(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMString) return value.equals(other.toString());
    return false;
  }
  @Override
  public boolean ge(VMObject other) throws VMException {
    if (other == null) return false;
    if (other instanceof VMString) return value.equals(other.toString());
    return false;
  }
}

Natürlich ist jetzt auch die Ausführung des Bytecodes nicht mehr funktionsfähig. Dementsprechend müssen wir nun die verschiedenen If-Befehle anpassen:

case OpCode.IF_EQ:
  jump = code[pc++];
  other = stack.pop();
  obj = stack.pop();
  if (obj.eq(other)) pc += jump;
  break;
case OpCode.IF_NE: // ...
  if (!obj.eq(other)) pc += jump;
  break;
case OpCode.IF_GT: // ...
  if (obj.gt(other)) pc += jump;
  break;
case OpCode.IF_GE: // ...
  if (obj.ge(other)) pc += jump;
  break;
case OpCode.IF_LT: // ...
  if (!obj.ge(other)) pc += jump;
  break;
case OpCode.IF_LE: // ...
  if (!obj.gt(other)) pc += jump;
  break;

Natürlich können wir jetzt auch diese Operatoren für die Tables überladen. Dies funktioniert im Grunde genau wie bei den mathematischen Operatoren. Der Unterschied ist nur, das wir einen boolean zurückgeben, anstatt einem VMObject. Dementsprechend können wir noch eine kleine Hilfsfunktion in unser VMObject einbauen. Diese Funktion sagt nur aus, ob der Wert zu true oder false evaluiert werden kann. Grundsätzlich gehe ich davon aus, dass nur 0 und null als false interpretiert werden.

public class VMObject {
  // ...
  public boolean bool() { return true; }
}

public abstract class VMNumber extends VMObject {
  // ...
  @Override
  public boolean bool() { return asFloat() != 0; }
}

Die überladenen Vergleichsoperatoren können diese Hilfsfunktion nun einfach verwenden:

public class VMTable extends VMObject {
  @Override
  public boolean eq(VMObject other) throws VMException {
    VMObject fun = member.get("_eq");
    if (fun != null) {
      VMObject result = fun.call(new VMObject[] {this, other});
      return result != null && result.bool();
    }
    return false;
  }
  @Override
  public boolean ge(VMObject other) throws VMException {
    VMObject fun = member.get("_ge");
    // ...
  }
  @Override
  public boolean gt(VMObject other) throws VMException {
    VMObject fun = member.get("_gt");
    // ...
  }
}

Mehr OOP

Auch wenn es nicht wirklich etwas mit Operator overloading zu tun hat, so würde ich trotzdem gerne nochmal etwas auf das Objektsystem eingehen. Genauer gesagt auf die "primitiven" Typen. Wir haben zwar schon eine Art Standartbibliothek, um z.B. die Länge eines Strings zu erhalten, aber wäre es nicht schöner, wenn man direkt auf dem String eine Methode aufrufen könnte? Im Grunde brauchen dir dazu nicht mal so viel machen. Im Grunde reicht es, wenn wir die get/set Methoden nicht nur im Table bereitstellen, sondern allgemein im VMObject. Diese können wir dann in den primitiven Typen überschreiben und bei Bedarf eine passende Funktion oder direkt einen Wert zurückgeben. Um beim Beispiel des Strings zu bleiben, könnte die String Klasse direkt die Länge zurückgeben oder auch eine substring Methode bereitstellen. VMInt und VMFloat könnten auch direkt mathematische Funktionen bereitstellen, wie z.B. eine Wurzelfunktion.

public abstract class VMObject {
  // ...
  public VMObject get(String name) throws VMException {
    throw new VMException();
  }
  public void set(String name, VMObject obj) throws VMException {
    throw new VMException();
  }
}

Nun überschreiben wir die get Methode in der jeweiligen Unterklasse. Die set Methode könnten wir zwar auch überschreiben, macht bei den primitiven Typen aber keinen Sinn.
Da wir nun in der String Lib, als auch in jedem String die gleiche Funktion bereitstellen, speicher ich diese Funktion statisch in der StringLib.

public final class VMString extends VMObject {
  // ...
  @Override
  public VMObject get(String name) throws VMException {
    switch(name) {
      case "len": return new VMInt(value.length());
      case "substring": return StringLib.substring;
      case "upper": return StringLib.upper;
      case "lower": return StringLib.lower;
    }
    throw new VMException();
  }
}

Hierbei gilt es natürlich wieder zu beachten, das es sich um Instanzmethoden handelt. Daher muss als erster Parameter wieder der String selber mitgegeben werden. Aber dank dem SELF Befehl wird das auch wieder vereinfacht. Allerdings muss man den Typecast innerhalb des SELF Befehls entfernen: Aus stack.push(((VMTable)obj).get(name)); wird also stack.push(obj.get(name));
Die verschiedenen mathematischen Funktionen werden sowohl von VMInt, als auch von VMFloat benötigt, daher können wir es auch direkt in VMNumber reinpacken. Folgende Funktionen kann man beispielsweise direkt in VMNumber legen: abs, floor, ceil, log, log10, sqrt, ...
All diese Funktionen benötigen nur einen Parameter, d.h. wenn sie Instanzmethoden sind, haben sie nur das this-Objekt als Parameter. Hier können wir uns nun überlegen, ob wir dann weiterhin eine Funktion zurückgeben wollen oder doch direkt das Ergebnis. Im Grunde ist dies eine reine Geschmacksfrage. Im folgenden werde ich die erste Variante wählen und Funktionen zurückgeben.

public abstract class VMNumber extends VMObject {
  // ...
  @Override
  public VMObject get(String name) throws VMException {
    switch(name) {
      case "abs": return MathLib.abs;
      case "floor": return MathLib.floor;
      case "ceil": return MathLib.ceil;
      case "log": return MathLib.log;
      case "log10": return MathLib.log10;
      case "sqrt": return MathLib.sqrt;
    }
    throw new VMException();
  }
}

Auf Aufruf wie 9.sqrt() könnte man nun einfach wie folgt im Bytecode darstellen:

GET_GLOBAL 0 // get print function
PUSH 9
SELF 2
CALL 1 // call sqrt
CALL 1 // call print

Overload get & set ?

Nun können wir wieder einen Schritt weitergehen und auch die get/set Methoden vom VMTable überladen. Dadurch könnte man z.B. erreichen, dass der Inhalt eines Tables nicht überschrieben werden kann.

public class VMTable extends VMObject {
  // ...
  @Override
  public VMObject get(String name) throws VMException {
    VMObject fun = member.get("_get");
    if (fun != null)
      return fun.call(new VMObject[] {this, new VMString(name)});
    return member.get(name);
  }

  @Override
  public void set(String name, VMObject obj) throws VMException {
    VMObject fun = member.get("_set");
    if (fun != null)
      fun.call(new VMObject[] {this, new VMString(name), obj});
    else
      member.put(name, obj);
  }
}

Aber hier muss man sehr aufpassen! Denn wenn eine _get/_set Methode nun selbst auf den Table zugreifen will, wird dieselbe Methode erneut getriggert! D.h. wir müssen irgendwie in der Lage sein, get/set direkt zu nutzen, ohne dabei die jeweilige _get/_set Methode aufzurufen.
Dafür erstellen wir zwei neue Methoden:

public class VMTable extends VMObject {
  // ...
  public VMObject rawget(String name) {
    return member.get(name);
  }
  public void rawset(String name, VMObject obj) {
    member.put(name, obj);
  }
}

Doch brauchen wir nun auch neue OpCodes, um diese Methoden direkt aufzurufen?
Im Grunde nicht, stattdessen fügen wir neue globale Funktionen hinzu, welche sich darum kümmern: rawset(table, name, value)

public class BasicLib extends VMTable {
  public static void install(VMTable globals) {
    // ...
    globals.rawset("rawget", new JavaFunction() {
      @Override
      public VMObject call(VMObject[] params) throws VMException {
        if(params.length!=2) throw new VMException();
        VMTable table = (VMTable)params[0];
        String name = params[1].toString();
        return table.rawget(name);
      }
    });
    globals.rawset("rawset", new JavaFunction() {
      @Override
      public VMObject call(VMObject[] params) throws VMException {
        if(params.length!=3) throw new VMException();
        VMTable table = (VMTable)params[0];
        String name = params[1].toString();
        table.rawset(name, params[2]);
        return null;
      }
    });
  }
}

Wenn man nun die get/set Methoden überschreiben will, so sollte man besser innerhalb der jeweiligen Methode dann die rawget/rawset Methoden nutzen.

Abschluss

Damit sind wir auch am Ende dieses Parts angekommen. Wir haben heute gelernt, wie wir unsere Tables um Operator overloading erweitern, sowie wie wir auch primitiven Objekten Funktionen mitgeben können.
Im nächsten Teil kümmern wir uns noch um einige kleine Details unserer VM und beenden damit die eigentliche VM. #08 Details & Loading from File

Quellcode zu diesem Teil der Serie: 07_overload.zip