Multimetoda a Java

27. dubna 2005

•

Multimetoda je pojem známý hlavně z Common Lisp Object System. Tento výraz ve stručnosti znamená určení volané metody v závislosti na skutečném typu jí předávaných parametrů. Následující článek se zabývá tím, jak podobnou funkcionalitu implementovat v programovacím jazyce Java.

Příklad užití – výpočet průniku geometrických prvků

Řekněme, že vytváříme aplikaci, která má pracovat s geometrickými objekty. Jednotlivé typy objektů budou reprezentovány třídami, které budou mít společného předka sdružujícího společné vlastnosti všech geometrických objektů. Tyto objekty mohou spolu nějakým způsobem interagovat a nás zajímá výsledek jejich interakce – například to může být průnik či sjednocení a výpočet jejich obsahu.

Pro určení průniku dvou geometrických objektů můžeme použít obecný algoritmus, který bude fungovat pro všechny typy objektů. Tento přístup však může být pro některé kombinace sice funkční, leč neefektivní. Například pokud bychom určovali průnik dvou obdélníků, což je ve své podstatě triviální výpočet, bylo by jistě použití nějakého obecného algoritmu totéž, jako jít s kanónem na vrabce.

Efektivním řešením je tedy množina několika algoritmů, které budou použity v závislosti na typech geometrických objektů, jejichž průnik budeme počítat. V podstatě bychom implementovali následující hierarchii geometrických objektů a třídu, která bude představovat vlastní výpočet průniku:

abstract class Geometry {
   public String toString() {
      return „I am a Geometry“;
   }
}
class Rectangle extends Geometry {
   public String toString() {
      return „I am a Rectangle“;
   }
}
class Circle extends Geometry {
   public String toString() {
      return „I am a Circle“;
   }
}
class Triangle extends Geometry {
   public String toString() {
      return „I am a Triangle“;
   }
}
class IntersectionCalculator {
   public void calculate(Rectangle r1, Rectangle r2) {
      System.out.println(„Rectangle, Rectangle“);
   }
   public void calculate(Circle r1, Circle r2) {
      System.out.println(„Circle, Circle“);
   }
   public void calculate(Geometry r1, Geometry r2) {
      System.out.println(„Generic algorithm“);
   }
}

Statická a pozdní vazba

Poté, co jsme ukončili návrh řešení, zkusíme ho použít v praxi. Vytvoříme objekty jednotlivých typů geometrických objektů a vyzkoušíme výpočet průniku.

public class Example1 {
   public static void main(String[] args) {
      Rectangle rectangle = new Rectangle();
      Circle circle = new Circle();
      IntersectionCalculator c = new IntersectionCalculator();

      System.out.println(rectangle); // 1
      System.out.println(circle); // 2
      c.calculate(rectangle, rectangle); // 3
      c.calculate(circle, circle); // 4
      c.calculate(rectangle, circle); // 5
   }
}

Po zkompilování a spuštění programu dostaneme následující text na obrazovce (čísla v závorkách jsou shodná s čísly v komentářích ve zdrojovém kódu a určují řádek, který inicioval výstup na obrazovku).

I am a Rectangle (1)
I am a Circle (2)
Rectangle, Rectangle (3)
Circle, Circle (4)
Generic algorithm (5)

Na první pohled tedy funguje vše tak, jak má. Geometrické objekty se správně identifikují (řádky 1 a 2), pro výpočet průniku dvou pravoúhelníků a dvou kružnic jsou použity specializované algoritmy (řádky 3 a 4) a pro výpočet průniku kružnice a pravoúhelníku je použit obecný algoritmus (řádek 5).

Nyní přikročíme ke složitějšímu testu a necháme volat výpočet průniku pro všechny kombinace dvojic geometrických prvků. Abychom si usnadnili práci, objekty po vytvoření uložíme do kontejneru (typu List<Geometry>) a výpočet budeme volat ve dvou vnořených cyklech iterujících nad kontejnerem.

public class Example2 {
   public static void main(String[] args) {
      IntersectionCalculator c = new IntersectionCalculator();
      List<Geometry> list = new ArrayList<Geometry>();
      list.add(new Rectangle());
      list.add(new Circle());
      list.add(new Triangle());
      for (Geometry i: list) {
         for (Geometry j: list) {
            System.out.println(„(“ + i + „, “ + j + „)“);
            c.calculate(i, j);
         }
      }
   }
}

Výstup z programu nyní vypadá následovně:

(I am a Rectangle, I am a Rectangle)
Generic algorithm
(I am a Rectangle, I am a Circle)
Generic algorithm
(I am a Rectangle, I am a Triangle)
Generic algorithm
(I am a Circle, I am a Rectangle)
Generic algorithm
(I am a Circle, I am a Circle)
Generic algorithm
(I am a Circle, I am a Triangle)
Generic algorithm
(I am a Triangle, I am a Rectangle)
Generic algorithm
(I am a Triangle, I am a Circle)
Generic algorithm
(I am a Triangle, I am a Triangle)
Generic algorithm

Vidíme, že něco je špatně. Ačkoli se prvky v kontejneru správně identifikovaly dle svého typu, pro všechny kombinace (včetně těch, pro které máme zavedený specializovaný algoritmus) byl volán obecný algoritmus výpočtu. V čem je tedy problém?

Vysvětlení spočívá v pojmech statická (časná) a pozdní vazba. V případě statické vazby je volaná metoda vybrána již v době kompilace v závislosti na deklarovaném typu proměnné, kdežto v případě pozdní vazby je metoda vybírána až za běhu, v závislosti na skutečném typu proměnné.

Statická vazba se uplatňuje při výběru metody v závislosti na jejích parametrech. Deklarované typy parametrů jsou součástí signatury metody, takže deklarovaný typ předávaného parametru (v našem případě vždy předek Geometry) způsobí, že je volána vždy metoda se signaturou void calculate(Geometry, Geometry). V předchozím příkladě vždy deklarované typy odpovídaly typům skutečným, proto byly volány i metody specializované.

Pozdní vazba se uplatňuje při výběru metody s danou signaturou v rámci dědické hierarchie, čili zajišťuje jednu z vlastností objektově orientovaného programování – polymorfismus. Její uplatnění můžeme vidět na volání metody toString().

K obejití statické vazby pro parametry metody musíme zvolit některou ze speciálních technik – double-dispatch, dynamické volání metod nebo návrhový vzor Strategie.

Double-dispatch

Technika zvaná double-dispatch (dvojité odeslání) je speciálním využitím návrhového vzoru Visitor (Návštěvník), který je popsán například v knize „Návrh programů pomocí vzorů“. Základem techniky je vybudování paralelní hierarchie tříd, jejíž pomocí dojde k volání metody v závislosti na typech dvou objektů.

abstract class Geometry {
   public String toString() {
      return „I am a Geometry“;
   }
   public void calculate(Calculator c) {
      c.generic(this);
   }
   public abstract Calculator getIntersectionCalculator();
}
class Rectangle extends Geometry {
   public String toString() {
      return „I am a Rectangle“;
   }
   public void calculate(Calculator c) {
      c.rectangle(this);
   }
   public Calculator getIntersectionCalculator() {
      return new RectangleIntersectionCalculator(this); // 1
   }
}
class Circle extends Geometry {
   public String toString() {
      return „I am a Circle“;
   }
   public void calculate(Calculator c) {
      c.circle(this); // 3
   }
   public Calculator getIntersectionCalculator() {
      return new CircleIntersectionCalculator(this);
   }
}
interface Calculator {
   void generic(Geometry c);
   void rectangle(Rectangle c);
   void circle(Circle c);
}
abstract class BaseIntersectionCalculator implements Calculator {
   void computeGenericGeneric(Geometry c1, Geometry c2) {
      System.out.println(„Geometry, Geometry“);
   }
   void computeRectangleRectangle(Rectangle r1, Rectangle r2) {
      System.out.println(„Rectangle, Rectangle“);
   }
   void computeRectangleCircle(Rectangle r1, Circle r2) {
      System.out.println(„Rectangle, Circle“);
   }
}
class RectangleIntersectionCalculator extends BaseIntersectionCalculator {
   private Rectangle rectangle = null;
   public RectangleIntersectionCalculator(Rectangle a) {
      rectangle = a; // 2
   }

   public void generic(Geometry c) {
      computeGenericGeneric(rectangle, c);
   }
   public void rectangle(Rectangle c) {
      computeRectangleRectangle(rectangle, c);
   }
   public void circle(Circle c) {
      computeRectangleCircle(rectangle, c); // 4
   }
}
class CircleIntersectionCalculator extends BaseIntersectionCalculator {
   private Circle circle = null;

   public CircleIntersectionCalculator(Circle a) {
      circle = a;
   }

   public void generic(Geometry c) {
      computeGenericGeneric(circle, c);
   }
   public void rectangle(Rectangle c) {
      computeRectangleCircle(c, circle);
   }
   public void circle(Circle c) {
      computeGenericGeneric(circle, c);
   }
}
public class Example3 {
   public static void main(String[] args) {
      List<Geometry> list = new ArrayList<Geometry>();
      list.add(new Rectangle());
      list.add(new Circle());
      for (Geometry i: list) {
         for (Geometry j: list) {
            System.out.println(„(“ + i + „, “ + j + „)“);
            i.calculate(j.getIntersectionCalculator());
         }
      }
   }
}

Diagram tříd pro double-dispatch (plná velikost, cca 10 kB)

Výstupem programu je:

(I am a Rectangle, I am a Rectangle)
Rectangle, Rectangle
(I am a Rectangle, I am a Circle)
Rectangle, Circle
(I am a Circle, I am a Rectangle)
Rectangle, Circle
(I am a Circle, I am a Circle)
Geometry, Geometry

V tomto případě jsou již použity speciální metody tam, kde jsou dostupné. Při výpočtu průniku nyní jeden geometrický prvek vytvoří objekt (1), který představuje Návštěvníka. Ten v sobě nese informaci o typu objektu (2), který jej vytvořil. Následně je tento Návštěvník předán druhému objektu, který zavolá metodu reprezentující jeho vlastní typ (3). Volaná metoda Návštěvníka má tedy informace o obou typech, jedna je zapouzdřena přímo v Návštěvníkovi a druhá je předána jako parametr metody, a může tak použit požadovaný algoritmus (4). Postup vyjádřený graficky ve formě sekvenčního diagramu:

Sekvenční diagram pro double-dispatch (plná velikost, cca 5 kB)

Ačkoli jsou v příkladu použity v rozhraní Calculator metody generic(), rectangle() a circle(), je možné jim dát stejné jméno, protože při jejich volání je znám skutečný typ předávaného parametru a kompilátor je bude schopen rozlišit. Totéž platí i pro metody compute...() ve třídě BaseCalculator.

Výhody řešení:

Rychlost – režií je jedno volání funkce navíc.
Úplná typová kontrola již při kompilaci.

Nevýhody řešení:

Nutnost udržovat paralelní hierarchii tříd, což je problémem u často modifikované hlavní hierarchie. Při vytváření nového geometrického objektu je nutné vytvořit nejen novou třídu odvozenou od Calculator, ale přidat přímo do třídy Calculator novou metodu a tím i do všech tříd z ní odvozených.
Omezení na použití dvou parametrů. Ačkoli je principiálně možné rozšířit řešení na více parametrů, dochází rychle ke kombinatorické explozi, což znemožňuje praktické využití.

Dynamické volání metod

Další technikou je využití mechanismu reflexe. Reflexe v Javě umožňuje nejen introspekci deklarovaných tříd, ale také dynamické volání metod. Při dynamickém volání metod jsou jméno metody a typy jejích parametrů vyhodnocovány až za běhu.

interface Multimethod<E, ER> {
   ER invoke(E… arguments);
}
abstract class BaseMultimethod<E, ER> implements Multimethod<E, ER> {
   protected E[] arguments;

   protected abstract int getNumberOfArguments();
   protected abstract String getMethodName();
   protected abstract ER handleMissingMethod();

   public ER invoke(E… a) {
      arguments = a;
      if (arguments.length != getNumberOfArguments()) {
         throw new IllegalArgumentException();
      }
      Class[] types = new Class[arguments.length];
      for (int i = 0; i < arguments.length; i++) {
         types[i] = arguments[i].getClass();
      }
      try {
         Method method = getClass().getMethod(getMethodName(), types); // 1
         return (ER)method.invoke(this, arguments); // 2
      }
      catch (NoSuchMethodException e) {
         return handleMissingMethod(); // 3
      }
      catch (IllegalAccessException e) {
         return handleMissingMethod();
      }
      catch (InvocationTargetException e) {
         return handleMissingMethod();
      }
   }
}
class Intersection extends BaseMultimethod<Geometry, Integer> {
   private static final String METHOD_NAME = „calculate“;
   private static final int NUMBER_OF_ARGUMENTS = 2;

   public int calculate(Rectangle r1, Rectangle r2) {
      System.out.println(„Rectangle, Rectangle“);
      return 1;
   }
   public int calculate(Circle r1, Circle r2) {
      System.out.println(„Circle, Circle“);
      return 2;
   }
   public int calculate(Circle r1, Rectangle r2) {
      System.out.println(„Circle, Rectangle“);
      return 3;
   }
   public int calculate(Geometry r1, Geometry r2) {
      System.out.println(„Geometry, Geometry“);
      return 4;
   }

   protected int getNumberOfArguments() {
      return NUMBER_OF_ARGUMENTS;
   }
   protected String getMethodName() {
      return METHOD_NAME;
   }
   protected Integer handleMissingMethod() {
      return calculate(arguments[0], arguments[1]); // 4
   }
}
public class Example4 {
   public static void main(String[] args) {
      Multimethod<Geometry, Integer> m = new Intersection();
      List<Geometry> list = new ArrayList<Geometry>();
      list.add(new Rectangle());
      list.add(new Circle());
      list.add(new Triangle());
      for (Geometry i: list) {
         for (Geometry j: list) {
            System.out.println(„(“ + i + „, “ + j + „)“);
            m.invoke(i, j);
         }
      }
   }
}

A výsledek programu:

(I am a Rectangle, I am a Rectangle)
Rectangle, Rectangle
(I am a Rectangle, I am a Circle)
Geometry, Geometry
(I am a Rectangle, I am a Triangle)
Geometry, Geometry
(I am a Circle, I am a Rectangle)
Circle, Rectangle
(I am a Circle, I am a Circle)
Circle, Circle
(I am a Circle, I am a Triangle)
Geometry, Geometry
(I am a Triangle, I am a Rectangle)
Geometry, Geometry
(I am a Triangle, I am a Circle)
Geometry, Geometry
(I am a Triangle, I am a Triangle)
Geometry, Geometry

Nejdříve zjistíme skutečné typy předaných parametrů voláním metody getClass() (1)a poté se pokusíme najít metodu, jejíž signatura obsahuje přesné typy objektů předaných jako parametry (2). Pokud byla taková metoda nalezena, je zavolána s předanými parametry (3). Pokud nebyla nalezena, nebo volání skončilo s chybou, je zavolána obecná implementace (4). Vlastní implementace tohoto mechanismu je provedena s využitím návrhového vzoru Template Method (Šablonová metoda).

V tomto případě existuje prostor pro mnohá zlepšení. Je možné upravit například vyhledávání metody tak, aby byl při nenalezení správné metody proveden nový pokus s pozměněným pořadím parametrů. Další možností je implementovat vyhledávání podobné tomu, které používá kompilátor, a netrvat na striktním typu, ale vyzkoušet vyhledávání i s nadřízenými typy a podobně.

Výhody řešení:

Vysoká flexibilita řešení. Pokud se jakkoli změní hierarchie geometrických objektů, stačí přidat nové algoritmy do třídy představující multimetodu. Pokud takové algoritmy nejsou, pak je automaticky volána obecná implementace algoritmu.
Možnost realizace pro více než dva parametry

Nevýhody řešení:

Nižší rychlost volání. Tato vlastnost vyplývá ze samé podstaty použití dynamického volání a její vliv je silně závislý na použitém virtuálním stroji. Určité orientační hodnoty staršího data jsou dostupné například v článku Denisse Sosnoskiho.

Strategie

Pro poslední techniku využijeme návrhový vzor Strategy (Strategie). Základem řešení bude rozhraní MethodSpecialization a třídy, které ho budou implementovat. Každá taková třída bude představovat jednu speciální implementaci algoritmu. Dále zavedeme třídu Multimethod, která bude udržovat instance rozhraní MethodSpecialization.

Implementace by mohla vypadat takto:

interface MethodSpecialization<E, ER> {
   ER invoke(E g1, E g2);
}
class Multimethod<E, ER> {
   private final Map<String, MethodSpecialization<E, ER>> registry = new HashMap<String, MethodSpecialization<E, ER>>();

   private MethodSpecialization<E, ER> defaultSpecialization;
   private String makeKey(Class<? extends E> c1, Class <? extends E> c2) {
      return c1.getName() + „+“ + c2.getName();
   }
   private String makeKey(E c1, E c2) {
      return c1.getClass().getName() + „+“ + c2.getClass().getName();
   }
   public Multimethod(MethodSpecialization<E, ER> defaultSpec) {
      defaultSpecialization = defaultSpec;
   }

   public void register(MethodSpecialization<E, ER> specialization, Class<? extends E> param1, Class<? extends E> param2) {
      registry.put(makeKey(param1, param2), specialization);
   }
   public void unregister(Class<? extends E> param1, Class<? extends E> param2) {
      registry.remove(makeKey(param1, param2));
   }
   public ER invoke(E g1, E g2) {
      MethodSpecialization<E, ER> spec = registry.get(makeKey(g1, g2)); // 3
      if (spec != null) {
         return spec.invoke(g1, g2);
      }
      return defaultSpecialization.invoke(g1, g2); // 4
   }
}
interface Intersection extends MethodSpecialization<Geometry, Integer> {
}
class RectangleRectangle implements Intersection {
   public Integer invoke(Geometry r1, Geometry r2) {
      Rectangle rect1 = (Rectangle)r1; // 5
      System.out.println(„Rectangle, Rectangle“);
      return 1;
   }
}
class CircleCircle implements Intersection {
   public Integer invoke(Geometry r1, Geometry r2) {
      System.out.println(„Circle, Circle“);
      return 2;
   }
}
class CircleRectangle implements Intersection {
   public Integer invoke(Geometry r1, Geometry r2) {
      System.out.println(„Circle, Rectangle“);
      return 3;
   }
}
class Generic implements Intersection {
   public Integer invoke(Geometry r1, Geometry r2) {
      System.out.println(„Geometry, Geometry“);
      return 4;
   }
}
public class Example5 {
   public static void main(String[] args) {
      Multimethod<Geometry, Integer> m = new Multimethod<Geometry, Integer>(new Generic()); // 1
      List<Geometry> list = new ArrayList<Geometry>();
      list.add(new Rectangle());
      list.add(new Circle());
      list.add(new Triangle());
      m.register(new RectangleRectangle(), Rectangle.class, Rectangle.class); // 2
      m.register(new CircleCircle(), Circle.class, Circle.class);
      m.register(new CircleRectangle(), Circle.class, Rectangle.class);
      for (Geometry i: list) {
         for (Geometry j: list) {
            System.out.println(„(“ + i + „, “ + j + „)“);
            m.invoke(i, j);
         }
      }
   }
}

Diagram tříd pro strategii (plná velikost, cca 5 kB)

Po spuštění dostáváme takovýto výsledek:

Aplikace nejprve vytvoří instanci multimetody s obecnou implementací (1). Poté zaregistruje několik specializací s požadovanými typy parametrů, pro které se dané specializace budou volat (2). Při volání multimetody je nalezena specializace dle předaných parametrů a zavolána (3). Pokud taková specializace není k dispozici, voláme obecnou implementaci (4). Před použitím musíme objekt přetypovat (5). Sekvenční diagram:

Sekvenční diagram pro strategii (plná velikost, cca 10 kB)

Také zde je možné řešení ještě vylepšit. Místo podpory dvou parametrů by mohla být v rozhraní MethodSpecialization uvedena výpustka, registrace specializací by nemusela být „zadrátována“ napevno v kódu, ale mohla by být načtena z konfiguračního souboru.

Výhody řešení:

Vysoká flexibilita řešení podobně jako u dynamického volání.
Možnost realizace pro více než dva parametry.
Změna chování multimetody za běhu programu voláním register() a unregister.

Nevýhody řešení:

Snížená typová bezpečnost. Jestliže specializaci zaregistrujeme a voláme s parametrem, který neodpovídá typu, na nějž ve specializaci přetypováváme, je tato chyba detekována až za běhu programu. Je tedy nutné klást zvýšené nároky na testování.
Nutnost registrace jednotlivých specializací před jejich použitím.

Shrnutí

Ukázali jsme si tři způsoby, jak implementovat multimetody v Javě. U každého jsme si uvedli jeho pozitiva i negativa. Výběr vhodné techniky pro ten který projekt je samozřejmě věcí uvážení, ale obecně lze říci, že potřebujete-li rychlost, volte double-dispatch, pokud potřebujete často měnit hierarchii objektů nebo chcete hodně muziky za málo peněz, použijte dynamické volání a pokud vám nevadí kompromis, použijte strategii.

Odkazy a zdroje

Java programming dynamics, Part 2: Introducing reflection – Dennis M. Sosnoski
Modern C++ Design: Generic Programming and Design Patterns Applied – Andrei Alexandrescu
Návrh programů pomocí vzorů – Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides
JavaTM 2 Platform Standard Edition 5.0 API Specification
The Java Language Specification – James Gosling, Bill Joy, Guy Steele, Gilad Bracha