[OO/Patterns] Geparametriseerde algoritmen instantiëren

[Soultaker]

Ik ben bezig met een project waarin een aantal eigenschappen van grafen bewezen moeten worden. De details zijn niet zo van belang. Waar het echter om gaat is dat er een aantal verschillende algoritmen zijn die op verschillende niveaus met elkaar samenwerken, en ik heb wat moeite dat op een nette manier in code om te zetten.

Heel abstract omschreven is de invoer een Probleem en de uitvoer een Oplossing. Om een Probleem op te lossen bestaat er een zogenaamde Universele Solver die het probleem opsplitst in subproblemen, elk stukje afzonderlijk oplost met een specifiek algoritme (een Solver) dat speciaal voor dit subprobleem wordt geïnstantieerd, en de resultaten samenvoegt tot een complete oplossing. Deze Solvers zelf kunnen op hun beurt weer geparametriseerd worden met verschillende parameters, waaronder de te gebruiken heuristieken. Deze heuristieken hebben een gemeenschappelijke interface, maar de implementatie verschilt per heuristiek, en de heuristieken hebben zelf ook weer (verschillende) parameters.

Het probleem waar ik nu mee zit, is de vraag hoe ik de boel kan structureren zodanig dat ik een universele solver kan instantiëren, die op zijn beurt solvers kan instantiëren voor subproblemen, die op hun beurt weer heuristieken kunnen instantiëren, waarbij ik van te voren kan configureren welke strategie en heuristieken er gebruikt gaan worden.

Momenteel heb ik alleen de Solvers (dus niet de Universele Solver) geparametriseerd en dan nog wel op een weinig geraffineerde manier: ik krijg een stringomschrijving van een heuristiek op de command line mee en die geef ik simpelweg mee aan de solver. De base class van de Heuristiek classes heeft een factory method om op basis van zo'n stringbeschrijving een specifiek klasse en (eventueel) specifieke constructor aan te roepen.

De huidige situatie in semi-pseudo-code samengevat:

C++:

class Heuristic {
    virtual int guessNext() =  0;  // dit is de methode die een solver gebruikt

    Heuristic *create(const Problem &p, string desc) {
        if (descr matcht "a:(float)")
            return new HeuristicA(p, parse_float_arg(descr, 1));
        if (descr matcht "b:(int):(int)")
            return new HeuristicB(p, parse_int_arg(descr, 1), parse_int_arg(descr, 2));
        return null;
    }
};

class HeuristicA : public Heuristic {
    HeuristicA(const Problem &p, float param_x) { .. };
    int guessNext() { .. };
};

class HeuristicB : public Heuristic  {
    HeuristicB(const Problem &p, int param_y, int param_z) { .. };
    int guessNext() { .. };
};

class Solver {
    Solution solve(const Problem &problem) = 0; 
};

class SolverX {
    Solver(string descr) { .. }
    Solution solve(const Problem &p) {
        Heuristic *h = Heuristic::create(p, descr);
        // solve met behulp van h ..
    }
};

Nu wil ik dus de universele solver implementeren, op zo'n manier dat ik 'm kan instantiëren met een solver-beschrijving ongeveer net zoals het nu met heuristieken werkt. Het probleem is dan dat je vrij ingewikkelde strings krijgt die je overal moet parsen. Echt netjes vind ik dat niet. Ik zou liever het parsen één keer doen in main() (aangezien ik command line arguments toch een keer moet parsen) en verder de configuratie van heuristics en solvers op een nettere manier geäbstraheerd hebben.

Een manier die ik hiervoor al bedacht had, is om naast de abstract classes voor Heuristic en Solver, ook een abstract factory class voor elk van beiden te maken. Ik heb dan een abstracte HeuristicFactory en een abstracte SolverFactory, en instanties daarvan als HeuristicAFactory, die ik kan instantiëren met de gewenste parameters. Het voordeel daarvan is dat de universele solver een SolverFactory instance kan accepteren, die al geparametriseerd is met alle argumenten, en die één methode (create() ofzo) heeft om een solver te instantiëren voor een subprobleem.

Een mogelijk nadeel van zo'n aanpak is dat ik allerlei factory objecten dynamisch moet instantiëren (anders dan singletons); volgens mij is dit niet zo gebruikelijk. Verder zit je met een wildgroei aan klassen: behalve de base Heuristic en HeuristicFactory heb je voor elke heuristiek ook een HeuristicX klasse en een HeuristicXFactory klasse. Er zit gelukkig wel structuur in, maar heel eenvoudig is het niet.

Vandaar mijn vraag hier: zijn er wellicht andere patterns die beter op deze situatie van toepassing zijn? Of hebben jullie andere suggesties hoe dit aangepakt zou kunnen worden?

[Confusion]

Volgens mij kan je dit gemakkelijk oplossen door een dependency injection framework te introduceren en verschillende configuratiebestanden te schrijven voor de verschillende configuraties waarmee de applicatie opgestart moet kunnen worden. Dan heb je alle configuratie overzichtelijk bij elkaar en hoeft je code bovendien niet te weten hoe het andere delen van de code kan instantieren, waardoor je bijvoorbeeld gemakkelijker kan omgaan met solvers die verschillende (hoeveelheden) parameters accepteren.

Enigszins op Spring geinspireerd, maar in een poging het universeel te houden:

XML:

<DI-config-file>

   <entity id="solver" class="net.tweakers.forum.sea.di_solver">
      <property name="solver_part_A" ref="solverA">
      <property name="solver_part_B" ref="solverB">
   </entity>

   <entity id="solverA" class="net.tweakers.forum.sea.solvers.solverA" />
   <entity id="solverB" class="net.tweakers.forum.sea.solvers.solverB" >
      <property name="param1" value="foo" />
      <property name="param2" value="baz" />
   </entity>

</DI-config-file>

Bij een goed framework heb je alleen maar setters voor de bestaande properties nodig en weet je code helemaal niet dat er een DI framework gebruikt wordt.

Edit: on second thought, volgens mij is dit zelfs gewoon precies een van de redenen dat DI frameworks bestaan.

[ Voor 46% gewijzigd door Confusion op 06-12-2009 17:17 ]

[Soultaker]

Ik moest even bijlezen wat Dependency Injection precies inhoudt^1,2 en dat klinkt op zich in de goede richting: ik wil inderdaad het instantiëren van specifieke services (heuristieken, solvers) loskoppelen van de objecten die er gebruik van maken, maar de situatie is niet helemaal hetzelfde omdat ik wel de configuratie maar niet zozeer de lifecycle van de dependencies wil loskoppelen. Dat komt omdat de dependencies niet stateless zijn, en geïnstantieerd moeten worden per (sub)probleem.

Simpelweg een setter aanroepen op een solver voldoet niet, omdat de solver pas tijdens het solven kan bedenken welke subproblemen er bestaan en hoeveel/waarvoor 'ie heuristiek-instanties nodig heeft.

Ik krijg dus de indruk dat ik met de voorgestelde constructie met abstract factories aardig in de richting zit van wat Martin Fowler beschrijft als Constructor Injection (waarbij de factories worden gebruik om specifieke instanties aan te maken, zonder dat de dependents - solvers in mijn geval - dependencies hoeven te configureren). Dat klinkt alvast zinnig, maar dan zit ik nog met al die factory classes.

Een andere optie, waarbij ik me die factories kan besparen, is wat Fowler een Service Locator noemt: een klasse die voorgeconfigureerd is om bepaalde instanties van heuristieken/solvers op te leveren als dependents er om vragen. In plaats van een abstract factory per klasse te hebben moet de Service Locator wel alle mogelijke klassen en parameters kennen, en in plaats van een factory-object geef ik dan de Service Locator mee aan solvers (of ik gebruik een singleton).

Ik ben er nog niet helemaal over uit wat mooier is...


<sub>1. Wikipedia: Dependency injection
2. Inversion of Control Containers and the Dependency Injection pattern</sub>

[ Voor 5% gewijzigd door Soultaker op 06-12-2009 18:40 ]

[oeLangOetan]

Dit lijkt een mogelijke kandidaat voor DCI (Data/Context/Interactions) pattern
hier vindt je een voorbeeld (in C++): http://www.artima.com/articles/dci_vision.html & http://blog.jaoo.dk/2009/...cture-in-the-agile-world/ (video, meer uitleg)
De methode is in principe redelijk eenvoudig, je injecteert gedrag in een klasse met een template. Uiteindelijk bekom je een klasse met het gedrag die jij wenst. (net zoals met mixins, traits etc)
Dit pattern is (met c++) niet bruikbaar als je zeer veel mogelijke combinaties zijn die geïnstantieerd kunnen worden. Aangezien je voor elke combinatie een nieuwe klasse moet definiëren.

[Soultaker]

Hier zal ik morgen nog eens in detail naar kijken, want het klinkt wel interessant, maar mijn eerste indruk is dat dat niet precies een oplossing is in mijn situatie, omdat ik eigenlijk niet at-compiletime wil moeten parametriseren.

Dit pattern is (met c++) niet bruikbaar als je zeer veel mogelijke combinaties zijn die geïnstantieerd kunnen worden. Aangezien je voor elke combinatie een nieuwe klasse moet definiëren.

In mijn geval kunnen er niet zozeer veel verschillende combinaties zijn, maar er zijn ook parameters die geen klassen zijn (maar b.v. ints of floats, zoals in m'n voorbeeld) waardoor je nooit alle mogelijke instanties at compiletime kunt instantiëren... Ik denk dat ik dan toch beter af ben met een dynamische aanpak, of zie ik dat verkeerd?

[Confusion]

Een Service Locator lijkt me hier niet van toepassing: je weet welke (lokale) klassen je de gewenste instanties kunnen leveren. Je wilt kunnen zeggen "geef me een SolverA", die tijdens zijn bezigheden roept "geef me een HeuristicX" en "geef me een HeuristicX_B". Aan een Service Locator vraag je "Geef me de plaats waar ik een SolverA kan instantieren". Dat is een abstractielaag die je volgens mij niet nodig hebt.

Volgens mij zit je met Abstract Factories ook niet helemaal op het goede spoor: daarmee zeg je bijvoorbeeld "Geef me een ProblemAFactory", waarmee je vervolgens een "SolverA" en een "HeuristicA_1" produceert en later "Geef me een ProblemBFactory" waarmee je vervolgens een "SolverB" en een "HeuristicB_1", omdat de Solvers en Heuristics parametriseringen delen. Als dat laatste niet het geval is (en dat lijk ik te begrijpen), dan heb je 'gewone' factories nodig.

Dependency Injection en Abstract Factories sluiten elkaar overigens niet uit. Je kan middels DI zorgen dat er een singleton instantie van iedere factory beschikbaar is, zonder dat die factory al volledig geparametriseerd is. Je kan dan gewoon roepen SolverFactory.getSolver(parameter1, parameter2, ...). Als de relevante HeuristicFactories in de SolverFactory geinjecteerd zijn, heb je in ieder geval die logica geisoleerd. Je kan bijvoorbeeld ook eenvoudig referenties naar HeuristicFactories aan je Solver instanties meegeven. Uiteindelijk ontkom je toch niet aan het parsen van 'identifiers' die eerst vertellen welke solver je nodig hebt en vervolgens welke Heuristic er gefabriceerd moet worden.

Hoe je het ook wendt of keert: er is een bepaalde hoeveelheid logica die ergens geimplementeerd moet worden. Er is geen design pattern waarmee dat minder wordt: er zijn alleen patterns waarmee je het kan isoleren. En er zijn een heleboel patterns die je kan misbruiken om de logica uit te smeren over een scala aan class(trees), maar dat is vaak juist niet de bedoeling.

[ Voor 10% gewijzigd door Confusion op 07-12-2009 07:43 ]

[Soultaker]

Ik dacht dat een Service Locator ook mogelijk was omdat ik die zou kunnen configureren voordat ik 'm meegeef aan solvers; die service locator heeft vervolgens factory methods om instanties van solvers en heuristics enzo te creeëren op basis van de configuratie. Maar misschien is dat niet wat normaalgesproken onder een Service Locator wordt verstaan. Laten we die voor het gemak dan maar even vergeten.

Confusion schreef op maandag 07 december 2009 @ 07:39:
Volgens mij zit je met Abstract Factories ook niet helemaal op het goede spoor: daarmee zeg je bijvoorbeeld "Geef me een ProblemAFactory", waarmee je vervolgens een "SolverA" en een "HeuristicA_1" produceert en later "Geef me een ProblemBFactory" waarmee je vervolgens een "SolverB" en een "HeuristicB_1", omdat de Solvers en Heuristics parametriseringen delen. Als dat laatste niet het geval is (en dat lijk ik te begrijpen), dan heb je 'gewone' factories nodig.

Het klopt dat Solvers en Heuristics geen parametriseringen delen (hoewel een solver met een bepaalde heuristic-configuratie geparameteriseerd wordt) maar ik zie nog niet precies waarom ik hier een 'gewone' factory zou gebruiken. Voor zover ik het begrijp, zou een 'gewone' factory altijd dezelfde klasse instantiëren, maar verschillende heuristieken (en solvers) worden door verschillende klassen geïmplementeerd omdat hun gedrag verschillend is, hoewel ze een abstract baseclass delen omdat ze dezelfde interface hebben (en het de solver niets kan schelen welke concrete klasse gebruikt wordt).

Vandaar dat ik denk: abstract factory, zodat er een concrete factory is voor elke verschillende heuristiek (en een niveau hoger: solver).

Dependency Injection en Abstract Factories sluiten elkaar overigens niet uit. Je kan middels DI zorgen dat er een singleton instantie van iedere factory beschikbaar is, zonder dat die factory al volledig geparametriseerd is. Je kan dan gewoon roepen SolverFactory.getSolver(parameter1, parameter2, ...). Als de relevante HeuristicFactories in de SolverFactory geinjecteerd zijn, heb je in ieder geval die logica geisoleerd.

Dit klinkt goed, en is ook waar ik gisteravond naar neigde. Als ik de injectie gewoon doe via de constructor, zou dat naar mijn idee zoiets kunnen worden:

C++:

class HeuristicFactory {
  virtual Heuristic *create(const Problem &problem) = 0;
};

class FooHeuristicFactory : public HeuristicFactory {
    FooHeuristicFactory(int param_x, int param_y) { .. };
    Heuristic *create(const Problem &problem) {
        return new FooHeuristic(problem, x, y);
    }
};

class BarHeuristicFactory  : public HeuristicFactory {
    BarHeuristicFactory(float param) { .. };
    Heuristic *create(const Problem &problem) {
        return new BarHeuristic(problem, param);
    }
};

class SolverFactory {
    virtual Solver *create(const Problem &problem) = 0;
};

class QuuxSolverFactory : public SolverFactory {
    QuuxSolverFactory(HeuristicFactory *hf, int solver_param) { .. }
    Solver *create(const Problem &problem) {
        return new QuuxSolver(problem, hf, solver_param);
    }
};

Solution QuuxSolver::solve() 
{
   while (..) {
     Heuristic *h = hf.create(); 
     // doe dingen met h
   }
   return ..;
}

int main()
{
    // Instantieer een geschikte HeuristicFactory aan op basis van command line args
    HeuristicFactory *hf;
    if (parse command line args)
        hf = new FooHeuristicFactory(x, y);
    else
    if (parse command line args)
        hf = new BarHeuristicFactory(z);

    // Instantieer een geschikte SolverFactory op basis van command line args
    SolverFactory *sf = new SolverFactory(hf, parse some other arg);

    Problem p = read problem;
    Solution s = sf->create()->solve(p);
    write s;
}

(In deze mockup heb ik de SolverFactory niet specifiek nodig, maar die is wel nuttig als ik 'm aan een universele solver zou meegeven, die ik voor 't gemak maar even heb weggelaten.) De factories bevatten zo het vaste deel van de configuratie, en krijgen de rest (het subprobleem, dat niet van te voren bepaald kan worden) mee in de factory methods.

Naar mijn idee is dit een aardige oplossing. Heb ik nog dingen over het hoofd gezien of compleet verkeerd begrepen?

Hoe je het ook wendt of keert: er is een bepaalde hoeveelheid logica die ergens geimplementeerd moet worden. Er is geen design pattern waarmee dat minder wordt: er zijn alleen patterns waarmee je het kan isoleren.

Accoord; ik probeer die logica ook niet te ontduiken, maar ik had gevoelsmatig het idee dat het mogelijk zou moeten zijn om interpretatie van de context en configuratie van de algoritmen zo dicht mogelijk bij main() af te handelen (waar de contextinformatie tenslotte beschikbaar is, in de vorm van commandline argumenten in dit geval, maar het kan natuurlijk net zo goed uit een config file komen). Dat lijkt op deze manier redelijk te kunnen.

Ik vind het in ieder geval de moeite waard er even goed over na te denken, en de reacties in dit topic helpen daar ook bij, waarvoor mijn dank.

[Soultaker]

Bij gebrek aan verdere reacties heb ik het maar geïmplementeerd zoals hierboven beschreven. Lijkt voorlopig wel aan m'n eisen te voldoen (en is in ieder geval een stuk beter wat 't was).

Bedankt voor de reacties.