I. rész: Memóriakezelés

Az előadáson bemutatott kifejezésfás program egy igazi állatorvosi ló. A probléma viszonylag egyszerű, ugyanakkor matematikailag jól körülhatárolható, ezért a modellezése is egyszerű, és jól illeszkedik az OOP-s elvekhez. Nem véletlen, hogy több könyvben is példának választják, a tárgy előadásanyagába is ezért került bele.

Ebben az írássorozatban az előadáson elkészült kód több lépésből álló refaktorálását mutatom be. Az egyes részek:

• A memóriakezelés automatizálása okos pointerekkel (ez az írás).
• Egy kis kitérőt a gyártófüggvények és a CRTP irányába.
• A fákon végzett műveletek kiszervezése külső osztályokba a Visitor tervezési minta segítségével.
• A Visitor tervezési minta megvalósítása egy felsorolt típus segítségével.
• A Visitor tervezési minta más nyelvekben.

Az írások elkészítését Arne Mertz Simplify C++ című blogja inspirálta – bár jópár helyen egész más tervezési döntések születtek nála, mint ebben a verzióban.

Az eredeti feladatunk így szólt: egy fát kell felépítenünk, amely négy alapműveletből felépített kifejezéseket tárol. Például a 4*(5+x) műveletsort az ábrán látható fa írja le. Lényegében ez egy szintaxisfa; a fa hierarchiája adja meg, mely műveletekhez mely operandusok tartoznak, így nyelvtani szabályokra, az operátorok közötti precedenciák és asszociativitások meghatározására itt nincsen szükség.

A fán különféle műveleteket kellett végeznünk, úgymint:

• Kiírás infixes alakban, például az itt látható fánál ez a 4*(5+x), vagy az egyszerűség kedvéért a (4*(5+x)) sztring megépítését jelenti.
• Kiértékelés egy adott x helyen, pl. f(3) = 4*(5+3) = 32.
• Szimbolikus deriválás az x változó szerint, új kifejezésfa előállítása.
• Egyszerűsítés.

A megoldást egy osztályhierarchia felépítése adta. (Letölthető innen: expression_eloadas.cpp.) A kifejezés ősosztály leszármazottai a konstans, változó, összeg és szorzat. Az egyes műveletek pedig virtuális függvényekként implementálhatóak, mivel azok az egyes típusokra jellemző módokon végezhetőek: egy konstans kiírása egy valós szám kiírását jelenti, az összeg deriválása pedig egy másik összeg objektum előállítását, amibe a bal- és a jobb oldali részfa deriváltja került. Az absztrakt ősosztály lényegi része:

class Expression {
  public:
    virtual double evaluate(double x) const = 0;
    virtual void print(std::ostream &os) const = 0;
    virtual Expression * derivative() const = 0;
    virtual Expression * simplify() const = 0;

    virtual ~Expression() {}
};

Az eltérő típusú objektumok kezelése ránk kényszerített egy indirekciót. A kompozit műveletek (összeg, szorzat: kifejezések összege és szorzata) számukra ismeretlen típusú objektumokkal dolgoztak, amelyet kénytelenek voltak indirekten, pointer segítségével tárolni. Ugyan valószínűleg a fa egyes csomópontjait enélkül is dinamikusan foglaltuk volna, hiszen a csomópontok száma a program bemenetétől függ, ez mégis programozói többletmunkát jelentett. A kompozit objektumokhoz destruktort kellett írnunk, amely a tartalmazott objektumokat felszabadítja:

class TwoOperand : public Expression {
  public:
    TwoOperand(Expression *lhs, Expression *rhs) : lhs_(lhs), rhs_(rhs) {}

    ~TwoOperand() {
        delete lhs_;
        delete rhs_;
    }
    
  protected:
    Expression *lhs_, *rhs_;
};

Ezzel egyben előírtuk azt is, hogy ezek építéséhez dinamikusan foglalt objektumokat kell felhasználni (a konstruktornak paraméterként adott két Expression kötelezően a new operátorral létrehozott kell legyen), továbbá az ősosztályban kért, új kifejezésfákat előállító műveletek (deriválás, egyszerűsítés) hasonlóképp kell viselkedjenek. (Viszont felhasználtuk a virtuális destruktort.) A dinamikus memóriakezelés további bonyodalmakat okozott több helyen is. A szorzat deriválásánál, amely az (a*b)' = a'b*ab' szabály alapján egy új fa építését jelenti, figyelnünk kellett, hogy ne csak a pointert másoljuk, mivel akkor kétszer hívódna a delete ugyanazokra az objektumokra:

virtual Expression * Product::derivative() const override {
    return new Sum(
       new Product(lhs_->derivative(), rhs_),  // a fa nem másolódik
       new Product(lhs_, rhs_->derivative())
    );
}

Hanem ilyenkor a részfákat is másoljuk, amihez pedig egy újabb virtuális függvényre, a clone()-ra volt szükségünk:

virtual Expression * Product::derivative() const override {
    return new Sum(
       new Product(lhs_->derivative(), rhs_->clone()),  // így már másolódik
       new Product(lhs_->clone(), rhs_->derivative())
    );
}

A nyers pointerek használata, new-olás, delete-elés önmagában is code smell, de a szintaxisfa használói számára is kényelmetlenséget, hibalehetőséget jelent. Például minden fa létrehozási művelet esetén, nem csak akkor, amikor ő maga írt new-t, hanem például egy deriválás esetén is, kézzel kell felszabadítania az objektumot egy delete kifejezéssel. Emiatt a következő sor memóriaszivárgást eredményez:

Expression * e = ...;

e->derivative()->print(std::cout);

És a kiíró (inserter) operátorral írt forma is:

std::cout << *(e->derivative());

Mivel a derivative() által visszaadott pointer nincs eltárolva, és a print()-en kívül a delete-nek is odaadva. De a fenti sorok írója számára nem túl természetes eltárolni a pointert, hiszen csak egyszer akarta használni az értékét, a derivált kifejezést.

Lássuk, hogy fejleszthető ez a program!

Első lépésként az ősosztály erőforráskezelését érdemes kicsit megvizsgálni. A vonatkozó kódrészlet:

class Expression {
  public:
    Expression() = default;
    Expression(Expression &) = default;

    virtual ~Expression() {}
};

Tudjuk, hogy polimorf osztálynak virtuális destruktor kell, ezért deklaráltunk egyet. A deklaráció hatására a fordító már nem írta azt meg, ezért definiálnunk is kellett azt, még akkor is, ha csak egy üres függvénytörzsről van szó.

A destruktor deklarálásának azonban van egy kellemetlen mellékhatása. Tudjuk, hogy az erőforrásokat kezelő osztályoknak általában a destruktora mellett másoló konstruktora és értékadó operátorra is van szüksége. Ez olyan általános érvényű szabály, ami miatt a C++11-ben a fordító már nem generál másoló konstruktort, ha a programozó által deklarált destruktort lát, mert valószínűleg nem lenne helyes. Ezért kellett szólni neki a másoló konstruktor melletti = default jelöléssel, hogy mi viszont tudjuk, hogy helyes, ezért engedélyt adunk a fordítónak a megírására. A másoló konstruktor deklarálása viszont azt jelenti, konstruktort deklarálunk – így eltűnt az alapértelmezett konstruktor, amit szintén „vissza kell hoznunk”.

Tudjuk azt is, hogy az értékadó operátor (assignment operator) hasonlóan működik. Az ősosztályban úgysincs még adattag, azt hasonlóképp definiáltathatnánk a fordítóval. Ugyanez áll a jobbértékes konstruktorra és értékadásra is (move constructor és move assignment operator). Igazából mindegyik lehetne default, de nem törölhetjük ki őket, mert a destruktornak virtuálisnak kell lennie:

class Expression {
  public:
    Expression() = default;

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

    virtual ~Expression() = default;
};

Talán legjobb mindig mind az öt függvény deklarációját kiírni, még akkor is, ha mindegyiket default-oljuk. De ha egyet leírtunk az öt közül, akkor biztos mindről nyilatkoznunk kell.

Nagyobb falat a memóriakezelés refaktorálása. De tudjuk, hogy okos pointereket használva egyszerűsödne a kód, az osztályok használói számára pedig jelentősen biztonságosabbá válna. Ha a derivative() függvény nem nyers pointerrel:

class Expression {
    virtual Expression * derivative() const = 0;
};

Hanem okos pointerrel térne vissza:

class Expression {
    virtual SomeSmartPtr<Expression> derivative() const = 0;
};

Akkor a memóriakezelés miatt neki sem kellene izgulnia: a visszaadott objektum destruktora tudná, mi a teendő a kifejezés objektummal.

Okos pointert valószínű nem kell majd írnunk, használhatjuk a C++11 beépített osztályait is. A szabványos referenciaszámlált pointer (std::shared_ptr), és a tulajdonjoggal rendelkező pointer (std::unique_ptr) is szóba jöhet, csak át kell gondolni, melyiket válasszuk.

std::unique_ptr

Az std::unique_ptr természetes választás, mert eddig is tulajdonjoggal rendelkező volt az összes pointerünk.

std::shared_ptr

A referenciaszámlálás használatának egy komolyabb hozománya is lehetne: kigyomlálhatnánk a clone() függvényeket. Ugyanis akkor nem lenne gond, hogy a kifejezésfáknak közös részfái (a memóriában közös részfái!) vannak, és nem kellene például a deriválásnál kifejezéseket másolgatni.

Szerencsére a körkörös hivatkozásokkal biztosan nem lenne bajunk, mert kifejezésfákról van szó – fákban meg nem lehet kör.

Az erőforrásmegosztásnak viszont ára lenne: konstansként kellene kezeljük a fákat. Mert az nem lenne menő, ha egy fát megváltoztatunk, és közben egy számunkra ismeretlen fát is módosítottunk. De eddig sem akartuk a fákat módosítani, minden műveletünk új fát hozott létre. Ez vállalhatónak tűnik.

Az érdekessége miatt az std::shared_ptr-es megoldást választottam.

A refaktort az ősosztálynál érdemes elkezdeni. Törölhető a clone(). Az Expression * visszatérési értékű függvények std::shared_ptr<Expression> értékűre cserélhetőek. A függvények szerepét magyarázó kommentek is frissíthetőek, nem kell már beleírni, hogy dinamikusan foglaltak a kifejezések:

class Expression {
  public:
    /* returns value of expression at x */
    virtual double evaluate(double x) const = 0;

    /* outputs expression as string to stream os */
    virtual void print(std::ostream &os) const = 0;

    /* return derivative expression */
    virtual std::shared_ptr<Expression> derivative() const = 0;

    /* return simplified version. */
    virtual std::shared_ptr<Expression> simplify() const = 0;

    /* ... */
    virtual ~Expression() {}
};

Ez a két apró változtatás nagyon sok mindent ki fog kényszeríteni. Az összes clone() függvény törlését (mivel azok mind override-dal vannak megadva), és a hívásait is. A visszatérési értékek típusának megváltoztatása miatt pedig az összes derivative()-re és simplify()-ra rá kell majd néznünk, és akkor már átdolgozzuk a kódjaikat is. Például egy viszonylag egyszerű függvény, a változó deriválása így fog kinézni, természetesen std::make_shared<>() használatával:

class Variable final : public Expression {
  public:
    /* ... */
    virtual std::shared_ptr<Expression> derivative() const override {
        return std::make_shared<Constant>(1);                       // !
    }
};

De ne feledkezzünk meg az adattagok konstanssá tételéről sem! Ez fontos. A kifejezésfáknak a megosztott részfák miatt konstansoknak kell lenniük, és ezt így ellenőriztetni tudjuk a fordítóval:

class Constant final : public Expression {
  private:
    double const c_;    //!

  public:
    Constant(double c): c_(c) {}
    /* ... */
};

A TwoOperand osztályból az összes erőforráskezelő függvény eltűnik. De ne feledjük, ennek az osztálynak van destruktora, amelyik a shared_ptr-ek destruktorát hívja, úgyhogy az ősben a virtuális destruktorra még mindig szükségünk van – ahogy mindig. Az egészből a két shared_ptr marad meg, de a bal és a jobb operandust amúgy is tárolnunk kellene:

class TwoOperand : public Expression {
  public:
    TwoOperand(std::shared_ptr<Expression> lhs, std::shared_ptr<Expression> rhs)
        : lhs_(lhs), rhs_(rhs) {}
    
    /* ... */

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

A szorzat deriválásából is eltűnhet a clone(), és itt tényleg erőforrásmegosztásunk van:

Expression* Product::derivative() const {
    return new Sum(
        new Product(lhs_->derivative(), rhs_->clone()),
        new Product(lhs_->clone(), rhs_->derivative())
    );
}

std::shared_ptr<Expression> Product::derivative() const {
    return std::make_shared<Sum>(
        std::make_shared<Product>(lhs_->derivative(), rhs_),    // !
        std::make_shared<Product>(lhs_, rhs_->derivative())
    );
}

Végül pedig, a simplify()-okat kell rendbe tenni, de szerencsére azok is sokat egyszerűsödnek. Az eredeti kódok a Constant típusú objektumok kereséséhez dynamic_cast<>-ot használtak. Az nyelvi elem, csak nyers pointeren működik, viszont a <memory> header okos pointerekhez is biztosít hasonló függvényt, az std::dynamic_pointer_cast<>()-ot. Ezzel a minimalista egyszerűsítő algoritmusok hasonlóan megírható, ahogy eddig, csak az okos pointerek miatt már sokkal tisztábban. Eltűnik a sok delete:

std::shared_ptr<Expression> Sum::simplify() const {
    auto lhs_simpl = lhs_->simplify();
    auto rhs_simpl = rhs_->simplify();
    auto lhs_cons = std::dynamic_pointer_cast<Constant const>(lhs_simpl);
    auto rhs_cons = std::dynamic_pointer_cast<Constant const>(rhs_simpl);
    
    if (lhs_cons != nullptr && lhs_cons->get_value() == 0.0)    /* 0 + a = a */
        return rhs_simpl;
    if (rhs_cons != nullptr && rhs_cons->get_value() == 0.0)    /* a + 0 = a */
        return lhs_simpl;
    if (lhs_cons != nullptr && rhs_cons != nullptr)             /* c + c = c */
        return std::make_shared<Constant>(lhs_cons->get_value()
                                          + rhs_cons->get_value());
    
    return std::make_shared<Sum>(lhs_simpl, rhs_simpl);
}

De a sok delete eltűnése nem csak azért fontos, mert látszólag rövidebb lett tőle a kód, hanem mert sokkal könnyebb megírni. Nem kell gondolkozni azon, hogy melyik kifejezést kell megtartani, melyiket nem – amelyiket nem használjuk, felszabadul magától.

A főprogramunk ilyesmi lehet:

int main() {
    std::shared_ptr<Expression> c = std::make_shared<Product>(
                        std::make_shared<Constant>(5),
                        std::make_shared<Sum>(
                            std::make_shared<Constant>(3),
                            std::make_shared<Variable>()
                        )
                    );
    std::cout << "f(x) = " << *c << std::endl;
    std::cout << "f(3) = " << c->evaluate(3) << std::endl;
    
    std::cout << "f'(x) = " << *(c->derivative()->simplify()) << std::endl;

    std::cout << "f''(x) = " << *(c->derivative()->derivative()->simplify()) << std::endl;
}

A műveletek bátran láncolhatóak, mert a köztes lépésekben előállított fákat a shared_ptr-ek fel fogják szabadítani. Így már egy ->derivative()->derivative()->simplify() sem okoz memóriaszivárgást.

Az elkészült kód letölthető innen: expression_shared.cpp.

• Hal Abelson, Jerry Sussman and Julie Sussman: Structure and Interpretation of Computer Programs.
• Arne Mertz: Simplify C++.
• Scott Meyers: A Concern about the Rule of Zero.