II. rész: Adatszerkezet és tevékenységek

Előzőleg az előadáson bemutatott kifejezésfás programot fejlesztettem tovább, egy okos pointerekre épülő memóriakezeléssel egyszerűsítve a programot. Az osztályhierarchia és a tevékenységek szétválasztása céljából a Visitor OOP tervezési mintát használom.

Van egy dolog, ami nem igazán stimmel ezzel a programmal. Vessünk egy pillantást ennek megértéséhez a kétoperandusú kifejezések osztályára!

class TwoOperand : public Expression {
  public:
    TwoOperand(std::shared_ptr<Expression> lhs, std::shared_ptr<Expression> rhs);
    virtual double evaluate(double x) const override final;
    virtual void print(std::ostream &os) const override final;

  private:
    virtual char get_operator() const = 0;
    virtual double do_operator(double lhs, double rhs) const = 0;

  protected:
    std::shared_ptr<Expression> const lhs_, rhs_;
};

Azt vehetjük itt észre, hogy ennek az osztálynak két feladata van. Egyrészt egy adatszerkezetet ad meg: ebből épül majd a kifejezések bináris fája. Másrészt pedig műveleteket definiál: kiértékelés, kiírás, ezeken kívül a többi osztályban volt még deriválás és egyszerűsítés is. Ez azért probléma, mert így egy új műveletet nem tudunk anélkül hozzáadni, hogy ne kellene az összes osztályt módosítani. Egy új művelethez az ősbe előbb egy virtuális függvényt tennénk, aztán megnyitnánk az összes leszármazottat, és implementálnánk azt a függvényt. Ezzel szemben, ha új típust veszünk föl (pl. hatványozás), akkor mindegyik eddigi lezárva marad, csak egy új osztályt írunk és kész. Nem csak egy új típus, hanem egy új művelet hozzáadása is ennyire egyszerű kellene legyen.

Mindezt pontosan az okozza, hogy dupla szerepe van az osztálynak. Szét kellene valahogyan választani a kettőt: az adatszerkezetnek a műveletektől függetlenül kellene tudnia létezni, mégis valahogy a műveleteknek tudniuk kellene, hogy épp milyen típusú adaton (összeg, szorzat stb.) dolgoznak. Erre való a Visitor tervezési minta.

A látogató (Visitor) tervezési mintát egy másik, egyszerűbb példán szokás megmutatni.

Tegyük fel, hogy az a feladatunk, hogy kapunk egy heterogén kollekciót (pl. alakzatok), és meg kell mondanunk, hogy az egyes objektum típusokból (pl. kör, téglalap) hány darab van. Ehhez legegyszerűbb megoldásként csinálnánk egy struktúrát, benne a számlálókkal, aztán odaadnánk azt az összes alakzat valamelyik virtuális függvényének. A függvények pedig a típusnak megfelelő számlálót növelnék:

struct ShapeCounter {
    int circles = 0;
    int rectangles = 0;
};

class Shape {
  public:
    virtual void count(ShapeCounter & counter) = 0;
};

class Circle final : public Shape {
  public:
    virtual void count(ShapeCounter & counter) override {
        counter.circles += 1;
    }
};

class Rectangle final : public Shape {
  public:
    virtual void count(ShapeCounter & counter) override {
        counter.rectangles += 1;
    }
};

ShapeCounter c;
for (auto shape : my_shapes)
    shape->count(c);
std::cout << c.circles << " circles and " << c.rectangles << " rectangles.\n";

A probléma tehát az, hogy ehhez módosítani kellett az alakzatokat. És persze az is, hogy az egyes számlálókat növelő kódrészleteket szét kellett szórni ezekbe az osztályokba.

Csináljunk ezért a ShapeCounter struktúrából osztályt! A műveleteket, a számlálók növelését tegyük át ebbe, bízzuk azt a ShapeCounter tagfüggvényeire!

class ShapeCounter {
  private:
    int circles = 0;
    int rectangles = 0;
  public:
    void count_circle() {
        circles += 1;
    }
    void count_rectangle() {
        rectangles += 1;
    }
};

class Circle final : public Shape {
  public:
    virtual void count(ShapeCounter & counter) override {
        counter.count_circle();
    }
};

class Rectangle final : public Shape {
  public:
    virtual void count(ShapeCounter & counter) override {
        counter.count_rectangle();
    }
};

Így a műveletek összegyűltek az osztályban, ez jó jelnek tűnik! Az alakzatokban lévő count() függvények pedig nagyon egyszerűek, csak annyi a dolguk, hogy meghívják a ShapeCounter megfelelő típushoz tartozó függvényét – mivel a saját típusukat ismerik a Shape::count() függvény virtuális volta miatt, dynamic_cast sem kell.

A fenti elv a Visitor tervezési minta alapötlete: az alakzatokba, tehát a feldolgozni kívánt heterogén kollekció osztályaiba (itt: Circle, Rectangle) szigorúan csak annyit írunk, hogy a műveletet végző, a heterogén kollekció elemeit feldolgozó objektum (itt: a ShapeCounter) adott típusra jellemző függvényét meghívjuk (itt: count_circle(), count_rectangle()). Ez azért érdekes, mert a ShapeCounter valami egészen más is lehetne. A count_circle() és count_rectangle() függvények akár virtuális függvények is lehetnének, process_circle() és process_rectangle() néven, egy ShapeProcessor ősosztály interfészét megvalósítva. Az egyes alakzatokban lévő process_xxx() hívások a tevékenységektől már teljesen függetlenek. Az alakzatok függvényei átadhatnák a process_xxx() függvényeknek saját magukat, így a feldolgozó objektum látná az alakzatok adatait is. Így az alábbi kódot kapjuk:

class ShapeProcessor {
  public:
    virtual void process_circle(Circle & c) = 0;
    virtual void process_rectangle(Rectangle & r) = 0;
};

class Circle final : public Shape {
  public:
    virtual void accept_shapeprocessor(ShapeProcessor & p) const override {
        p.process_circle(*this);
    }
};

class Rectangle final : public Shape {
  public:
    virtual void accept_shapeprocessor(ShapeProcessor & p) const override {
        p.process_rectangle(*this);
    }
};

ShapeCounter counter;
for (auto shape : my_shapes)
    shape->accept_shapeprocessor(counter);   /* counter.count(shape); */

ShapeDrawer drawer;
for (auto shape : my_shapes)
    shape->accept_shapeprocessor(drawer);    /* drawer.draw(shape); */

Ennek a kódnak érdemes jól megfigyelni, megérteni a működését. Amikor a heterogén kollekciót feldolgozzuk, minden alakzatnál két függvényhívás történik. Először is, meghívjuk az adott alakzat accept_shapeprocessor() függvényét, amely paraméterként kap egy ShapeProcessor-t. Ez az objektum fogja majd elvégezni a tevékenységet: számlálás, kirajzolás stb. Az accept_shapeprocessor() függvényhívás virtuális, a kör, téglalap stb. osztályok függvénytörzseibe jutunk általa, tehát olyan helyre a programban, ahol az alakzat konkrét típusa ismert. Itt tehát az adott ShapeProcessor alakzat típusa szerinti függvénye, process_circle(), process_rectangle() stb. meghívható. Ezen a ponton az alakzat típusok szerinti esetszétválasztás megtörtént. A meghívott process_xxx() függvények pedig szintén virtuálisak, azokat pedig az adott tevékenységet végző ShapeProcessor valósítja meg olyan módon, hogy az adott tevékenységet, a számlálást vagy a kirajzolást elvégezze. Ezek paraméterként kapják az alakzatot, ráadásul ismert típussal, és így tudnak dolgozni vele.

Kényelmi céllal írhatunk még függvényeket a ShapeProcessor-ok számára, hogy az alakzatok feldolgozását elindítsuk. A counter.count(shape) például jobban kifejezi, hogy a számláló dolgozik az alakzaton, elvégre is a számláló az, aki a tevékenységet végzi, nem az alakzat.

class ShapeProcessor {
  public:
    virtual void process(Circle & c) = 0;
    virtual void process(Rectangle & r) = 0;
};

A fentiek alapján az adatszerkezetet és a tevékenységeket el tudjuk választani egymástól. Két osztályhierarchiát fogunk kapni ezáltal: a kifejezésfa típusait (konstans, összeg, szorzat), és a tevékenységeket (kiírás, kiértékelés, deriválás). Új tevékenység hozzáadásához elegendő lesz csak a tevékenység ősosztályból, tehát a Visitor-ból leszármazni.

Első lépésként a kifejezések ősosztályából az egyes tevékenységek virtuális függvényeit (print(), evaluate() stb.) törölhetjük. Az összeset helyettesíti az accept_visitor() függvény:

class ExpressionVisitor;

class Expression {
  public:
    virtual void accept_visitor(ExpressionVisitor &v) = 0;  // print, evaluate, ... helyett

    Expression() = default;
    Expression(Expression const &) = default;
    Expression(Expression &&) = default;
    Expression & operator=(Expression const &) = default;
    Expression & operator=(Expression &&) = default;

    virtual ~Expression() {}
};

Ezen felül, a tevékenységeket végző osztályok interfészét, a Visitor-t is definiáljuk:

class Expression;
class Constant;
class Variable;
class Sum;
class Product;

class ExpressionVisitor {
  public:
    virtual void visit_constant(Constant &) = 0;            // ahányféle kifejezés van
    virtual void visit_variable(Variable &) = 0;
    virtual void visit_sum(Sum &) = 0;
    virtual void visit_product(Product &) = 0;
    
    ExpressionVisitor() = default;
    ExpressionVisitor(ExpressionVisitor const &) = default;
    ExpressionVisitor(ExpressionVisitor &&) = default;
    ExpressionVisitor & operator=(ExpressionVisitor const &) = default;
    ExpressionVisitor & operator=(ExpressionVisitor &&) = default;
    
    virtual ~ExpressionVisitor() {}
};

Utána pedig két feladatunk van:

• Az egyes konkrét kifejezés osztályokban az accept_visitor() függvényeket definiáljuk. Ezek triviális, egy soros függvények, amelyeket a minta alapján kell elkészíteni; ha valamelyik kimarad, a fordító szólni fog, mert az interfész függvényét mindenképpen implementálni kell. Például:

  void Constant::accept_visitor(ExpressionVisitor &v) {
      v.visit_constant(*this);
  }

• A feldolgozó függvényeket pedig ki kell gyűjteni, a konkrét kifejezés osztályokból törölve, Visitor leszármazottakba áthelyezve. Ha valamelyiket bent felejtenénk, a fordító szintén szólni fog, hiszen ezeket a függvényeket a leszármazottakban mind override kulcsszóval adtuk meg.

Az utóbbi összetettebb feladat. Eddig a kifejezések virtuális függvényei paramétereket is kaphattak, pl. a print(std::ostream & os) hogy hova kell kiírni a kifejezést, az evaluate(double x) pedig a függvénybe behelyettesítendő értéket. Most viszont a visit_xxx() függvényeknek nem lehet ilyen paramétere, mert a Visitor interfésze a tevékenységtől független kell legyen. Ezeket a paramétereket a kifejezéseket feldolgozó Visitor objektumokba kell tennünk, mint ahogy azt funktoroknál szoktuk. Például a kiírásnál így:

class ExpressionPrinter final: public ExpressionVisitor {
  private:
    std::ostream &os_;

  public:
    explicit ExpressionPrinter(std::ostream &os) : os_(os) {}

    void print(Expression &e) {
        e.accept_visitor(*this);
    }
    
    virtual void visit_constant(Constant &c) override {
        os_ << c.get_value();
    }
    
    virtual void visit_variable(Variable &v) override {
        os_ << 'x';
    }
    
    virtual void visit_sum(Sum &s) override {
        print_twooperand(s, '+');
    }
    
    virtual void visit_product(Product &p) override {
        print_twooperand(p, '*');
    }

  private:
    void print_twooperand(TwoOperand &t, char op) { // csak segédfüggvény
        os_ << '(';
        print(*t.get_lhs());
        os_ << op;
        print(*t.get_rhs());
        os_ << ')';
    }
};

A többi Visitor-nál is hasonlóan gondolkozhatunk. Az egyes visit_xxx() függvények tagváltozókon keresztül kommunikálhatnak egymással.

A kétoperandusú kifejezések kiírásánál használtunk eddig egy trükköt: volt egy privát virtuális függvényünk, amellyel a kódduplikációt tudtuk elkerülni. Ilyesmire most is van lehetőség. Az ExpressionPrinter osztályunknak tetszőleges számú, tetszőlegesen paraméterezhető segédfüggvényt adhatunk. Fent a visit_sum() és a visit_product() függvények közösen a print_twooperand() privát függvényt használják. Ez talán még így kényelmesebb is, mert egy egyszerű paraméterezés könnyebben érthető, mint a sablonfüggvény. (A fenti kódban a bal és a jobb oldali kifejezés kiírásához elvileg egy újabb Printer-t kellene példányosítani, de ez nem fontos. Az új objektum csak ugyanazt az std::ostream referenciát tartalmazná, mint ez, tehát ugyanúgy viselkedne.)

A kiírásnál volt egy másik trükk, amellyel a kiíró operátort látszólag virtuálissá tudtuk tenni. Ennek lényege az volt, hogy a kiíró operátorból a kifejezés virtuális print() függvényét hívtuk. Erre továbbra is van lehetőség: a kiírás most egy ExpressionPrinter példányosításával fog kezdődni. Az ostream-et ez a konstruktorparaméterben kapja meg, a kifejezést pedig a kiírást elindító tagfüggvényének paramétereként:

std::ostream & operator<<(std::ostream & os, Expression &e) {
    ExpressionPrinter ep(os);
    ep.print(e);
    return os;
}

A kiértékelést végző osztály hasonlóképp írható meg. Itt is összegyűlnek egy osztályba a kiértékelések metódusai. Az eredményt mindegyik függvény a result_ tagváltozóba teszi, a kiértékelés befejezése után pedig onnan olvassa ki az evaluate() függvény az eredményt:

class ExpressionEvaluator final: public ExpressionVisitor {
  private:
    double x_;
    double result_;

    void evaluate_twooperand(TwoOperand &t, double (*do_op)(double, double)) {
        double left = evaluate(*t.get_lhs());
        double right = evaluate(*t.get_rhs());
        result_ = do_op(left, right);
    }

  public:
    explicit ExpressionEvaluator(double x) : x_(x) {}
    
    double evaluate(Expression &e) {
        e.accept_visitor(*this);
        return result_;
    }
    
    virtual void visit_constant(Constant &c) override {
        result_ = c.get_value();
    }
    
    virtual void visit_variable(Variable &v) override {
        result_ = x_;
    }
    
    virtual void visit_sum(Sum &s) override {
        evaluate_twooperand(s, [](double a, double b) { return a+b; });
    }
    
    virtual void visit_product(Product &p) override {
        evaluate_twooperand(p, [](double a, double b) { return a*b; });
    }
};

Nézzük meg, mit nyertünk ezzel! Alapvetően a kód hosszabb lett, és látszólag bonyolultabb is, mert több osztályunk van, mint eddig. Viszont a karbantarthatóság szempontjából kifejezetten előnyös az átalakítás:

Lokalitás

Eddig az egyes műveletekre jellemző függvények szét voltak szórva az osztályokban. Például a kiértékelés lépései öt különböző osztályban is szerepeltek. Most az összes kiértékelő függvény egy osztályban van, az ExpressionEvaluator-ban. Az összes kiírást végző függvény pedig az ExpressionPrinter-ben. A lokalitás előnyös.

Új művelet hozzáadása

Mi a helyzet új művelet hozzáadásakor? Eddig egy új művelet miatt a kifejezés ősosztályba tisztán virtuális függvényt kellett tennünk, ami miatt az összes leszármazottat módosítanunk kellett. Most viszont elég csak egy új ExpressionVisitor leszármazottat létrehozni, a kifejezések osztályai változatlanok maradnak.

Új típus hozzáadása

Az új típus (pl. hatványozás) hozzáadása eddig egy egyszerű leszármazás volt; benne természetesen a kifejezések összes tagfüggvényét (print(), evaluate() stb.) meg kellett valósítanunk. Most egy kicsit nehezebb a dolgunk, ugyanis az új típus miatt egy új virtuális függvény fog kerülni az ExpressionVisitor interfészbe; hatványozás esetén pl. ez a visit_exponent(Exponent & e) lesz. Emiatt pedig az összes Visitor-t módosítanunk kell – bár igaz, olyan függvénytörzseket fognak kapni, amiket amúgy is meg kellett volna írni. Ez kódsorok számát tekintve több, de tervezésben lényegében ugyanannyi feladat.

Összefoglalva: ha inkább számítunk arra, hogy később új műveletet kell hozzáadni, akkor a Visitor minta alapján megírt program könnyebben karbantartható. Ha valószínűbb, hogy később új típusokat kell hozzáadni, akkor lehet jobb maradni a sima, virtuális függvényes változatnál.

Az így refaktorált változat innen tölthető le: expression_visitor.cpp. Ez nem tartalmazza a deriválás, egyszerűsítés műveleteket, és a hatványozás típust sem. Az új típus és művelet hozzáadása kipróbálható rajta.