[C++] return-waardes interpreter-pattern

[JeromeB]

Ik probeer een simpele interpreter te programmeren. Ik heb een expression-class en enkele afgeleide classes waarmee ik een zogenaamde expression-tree kan opbouwen. Iedere expression bevat een methode evaluate() die ik kan aanroepen, het zogenaamde interpreter-pattern. Deze methode moet in bepaalde gevallen een waarde teruggeven. Deze waarde kan bijvoorbeeld een int, een float of een functionpointer zijn.

Ik twee oplossing bedacht:

1. De methode evaluate() geeft een expression-pointer terug die ik vervolgens naar de juiste value cast. Deze methode vereist veel downcasts.
2. Een andere oplossing is om een union (met pointers naar values) terug te geven.

Ik vroeg mij af wat de voor- en nadelen zijn van deze oplossingen. Zijn er ook alternatieve oplossingen binnen het kader van het interpreter-pattern (dus geen bytecode-interpreter oid)?

Voorbeeld middels expression-pointer:

C++:

class expression
{
    public:

    enum id_type
    {
        // a lot of exppression-id's
    };

    ~virtual expression() { }

    virtual inline const expression::id_type type() const
    {
        return expression::EXPRESSION;
    }

    virtual void translate(std::ostream& out) { }

    virtual expression* evaluate(expression* parent, /* some more arguments */) { }
};

class int_value : public expression
{
    public:

    int_value(int v) : value(v) { }

    virtual ~int_value() { }

    virtual inline const expression::id_type type() const
    {
        return expression::INT;
    }

    virtual void translate(std::ostream& out) { }

    virtual expression* evaluate(expression* parent)
    {
        return this;
    }

    void set_value(int v)
    {
        value = v;
    }

    int get_value()
    {
        return value;
    }

    private:

    int value;
};

class add_operator : expression
{
    public:

    add_operator(expression* a, expression* b) : operand_a(a), operand(b) { }

    virtual ~add_operator() { }

    virtual inline const expression::id_type type() const
    {
        return expression::ADD_OPERATOR;
    }

    virtual void translate(std::ostream& out) { }

    virtual expression* evaluate(expression* parent)
    {
        // this part is a bit simplified, some typechecks need to be done first.
        int a = static_cast<int_value*>(operand_a->evaluate(this))->get_value();
        int b = static_cast<int_value*>(operand_b->evaluate(this))->get_value();
        return new int_value(a+b);
    }

    private:

    expression* operand_a;
    expression* operand_b;
};

void test()
{
    expression* add1 = new add_operator(new int_value(4),new int_value(3));
    expression* add2 = new add_operator(add1,new int_value(5));
    expression* add3 = new add_operator(add2,new int_value(3));
    std::cout << static_cast<int_value*>(add3->evaluate(NULL))->get_value() << std::endl; // output = 15
}

[prototype]

Wikipedia: Visitor pattern :-)

[Soultaker]

@prototype: Ik zie niet direct hoe een Visitor het probleem van de TS oplost. Kun je dat misschien toelichten?

@JeromeB: Ik denk dat het Interpreter pattern meestal iets anders werkt. Je hebt nu de wat ongebruikelijke keuze gemaakt om waarden ook instanties van expressies te maken. Dat kan de bedoeling zijn (LISP werkt met dit principe) maar in de meeste programmeertalen zijn expressies (statisch) gescheiden van waarden (dynamisch); heb je dat niet, dan kom je meestal op constructies als closures uit en dan lijkt het Interpreter pattern me niet meer zo'n logische constructie.

Dit is echter niet heel erg van belang. De kern van je probleem zit erin dat twee operands van bijvoorbeeld een binaire expressie waarschijnlijk verschillende soorten geldige waarden kunnen hebben (twee ints, of twee floats, of twee strings, of een string en een int, etc.) Dé manier om dat te ondersteunen is door een common base class te gebruiken en specifieke instanties te bekijken om uit te zoeken wat de bedoeling is; een union van waarden is is natuurlijk gewoon een handmatige implementatie daarvan. Dat zijn dus precies de twee mogelijkheden die je al had geïdentificeerd.

[prototype]

Soultaker schreef op zondag 29 maart 2009 @ 13:25:
@prototype: Ik zie niet direct hoe een Visitor het probleem van de TS oplost. Kun je dat misschien toelichten?

Polymorphic visitors zijn een manier om dit soort AST's te interpreten: vertalerbouw op de UT gaf iirc ook de voorkeur aan deze methode boven de composite tree/interpreter pattern doordat het meer flexibiliteit zou bieden: immers houd je dan datastructuur helemaal gescheiden van gedrag, maar goed, daar valt nog wel het e.e.a. voor te zeggen. Bijkomend voordeel is ook dat TS door double dispatching niet meer specifiek hoeft te downcasten. Een uitgebreid verhaal met voorbeeld --die het probleem van TS aanpakt en oplost met polymorphic visitors-- ter ondersteuning: http://www.cs.rice.edu/~cork/book/node62.html

Indien voor TS nog niet helemaal duidelijk is hoe dit toepasbaar is op zijn code zou ik aanraden om even in code te kijken van open source talen die Polymorphic visitors toepassen op de welbekende ConstantFolder optimalisatie pass. Ik heb onlangs dit ook geimplementeerd voor mijn hobby taal :-)

[ Voor 40% gewijzigd door prototype op 29-03-2009 13:44 ]

[Zoijar]

Volgens mij is visitor ook vrij standaard hier. Je krijgt dan dingen als een evaluation visitor, een printing visitor, een constant folding visitor etc.

[Soultaker]

Hm mja, volgens mij mis je het punt. (Of ik, natuurlijk.) Het opbouwen van de AST is het probleem niet (dat is al gebeurd als ik de TS goed begrijp) het probleem is dat waarden van de TS eigenlijk polymorf zijn. In het boek wat je quote geven ze dat ook aan:

In our application of the visitor pattern above, the for methods of the visitor classes and the accept methods for the ArithExpr classes returned values of type int. This convention is acceptable as long as all the computations we ever want to perform over ArithExprs have integer results. [..]
We can address this problem by redefining the for and accept methods so that they return a more general type.

Vervolgens definiëren ze een nieuwe Const class die dus overeenkomt met de Expression class van de TS en laten ze alle visitor methoden Objects returnen, die de visitor instantie vervolgens weer moet casten naar Const. Dat is dus precies het "probleem" wat de TS nu ook heeft (voor zover het een probleem is).

Ik ben overigens wel met je eens dat een Visitor een elegante manier kan zijn om zo'n interpreter te implementeren (in ieder geval als je taal geen multimethods of iets als extension methods ondersteunt), maar ik heb het idee dat het verder los staat van het huidige probleem.

[prototype]

Ander vraagje btw voor TS, ik zie dat je een enum bijhoudt voor Type ID's. Aangezien je hier al met polymorphic types en dynamic_cast werkt veronderstel ik ook dat je de typeinfo header al hebt geinclude (e.g. voor std::bad_cast). Kan je dan ipv al die getters handmatig schrijven niet eenvoudiger gewoon de typeid operator gebruiken hiervoor? Volgens mij doet dat namelijk eigenlijk precies hetzelfde, alleen minder error prone misschien doordat je niet die type() method van je hoeft te schrijven elke keer en niet rare dingen kan schrijven als:

C++:

class int_value : public expression {
    virtual inline const expression::id_type type() const
    {
        return expression::LONG; // om maar even iets te roepen
    } 
}

Voor elke type die je toevoegt hoef je dan ook niet de Expression class aan te passen om de enum bij te werken.

edit
@Soultaker:
Ah, excuses, te snel overheen gelezen denk ik. In dat geval denk ik dat je het antwoord al hebt gegeven: ik heb dit "probleem" op soortgelijke manier opgelost door een common base class te maken (Number) welke een ConstantExpressie is in mijn type hierarchie. Vervolgens heb ik hier de arithmetic operators voor zitten overloaden en daarbij dus in de parameter argumenten aangegeven hoe deze class dient te werken met de type die opgegeven is in de parameter. Deze returned op zijn beurt dan weer een value waarvan het type een subtype is van Number* (specifieker, covariant is aan Number*). Met visitor pattern heb ik de juiste dispatching hiervoor toegepast.

Nog een extra tip voor TS: pas flyweight pattern toe voor constante waarden :-) Het n maal voorkomen van "1" in je AST zou niet gelijk moeten staan aan n maal een instantie hebben van int_value, maar in plaats daarvan, 1 instantie "1" met n referenties.

[ Voor 35% gewijzigd door prototype op 29-03-2009 14:35 ]

[Zoijar]

Ik heb ook ooit zoiets geschreven in C++; een wiskundige rekenmachine waar je expressies met variabelen en constanten had. Kan het alleen even niet meer vinden... volgens mij had ik dat ook opgelost met overloading; i.e., de optelling van een of twee expressies levert een expressie op (de niet-expressie wordt dan automatisch geupcast naar een expressie) en de optelling van twee constanten geeft weer een constante. Volgens mij is dat hetzelfde als wat prototype zegt. Ik zal eens kijken of ik het nog kan vinden.

[JeromeB]

prototype schreef op zondag 29 maart 2009 @ 04:12:
Wikipedia: Visitor pattern :-)

Ik ben helaas niet zo bekend met de meeste design-patterns, maar het lijkt me niet direct toepasselijk op mijn probleem. Ik zal me er wat dieper in verdiepen.

offtopic:
Het wordt toch eens tijd dat ik een goed boek over design-patterns aanschaf

Soultaker schreef op zondag 29 maart 2009 @ 13:25:
@JeromeB: Ik denk dat het Interpreter pattern meestal iets anders werkt. Je hebt nu de wat ongebruikelijke keuze gemaakt om waarden ook instanties van expressies te maken. Dat kan de bedoeling zijn (LISP werkt met dit principe) maar in de meeste programmeertalen zijn expressies (statisch) gescheiden van waarden (dynamisch); heb je dat niet, dan kom je meestal op constructies als closures uit en dan lijkt het Interpreter pattern me niet meer zo'n logische constructie.

Ik heb voorheen een (onafgewerkte) Scheme-interpreter geschreven. Met die kennis in het achterhoofd ben ik aan dit project begonnen.

Ik begrijp helaas niet helemaal wat je bedoelt met de scheiding tussen 'waarden' en 'expresssies'. Ik zal mijn 'constants' toch ergens in mijn expression-tree moeten opslaan? Hopelijk wil je dit even verder toelichten.

Soultaker schreef op zondag 29 maart 2009 @ 13:25:
Dit is echter niet heel erg van belang. De kern van je probleem zit erin dat twee operands van bijvoorbeeld een binaire expressie waarschijnlijk verschillende soorten geldige waarden kunnen hebben (twee ints, of twee floats, of twee strings, of een string en een int, etc.) Dé manier om dat te ondersteunen is door een common base class te gebruiken en specifieke instanties te bekijken om uit te zoeken wat de bedoeling is; een union van waarden is is natuurlijk gewoon een handmatige implementatie daarvan. Dat zijn dus precies de twee mogelijkheden die je al had geïdentificeerd.

Inderdaad, ik vroeg mij dus af of er nog andere mogelijkheden zijn om dit te implementeren.

Soultaker schreef op zondag 29 maart 2009 @ 14:16:
Hm mja, volgens mij mis je het punt. (Of ik, natuurlijk.) Het opbouwen van de AST is het probleem niet (dat is al gebeurd als ik de TS goed begrijp) het probleem is dat waarden van de TS eigenlijk polymorf zijn. In het boek wat je quote geven ze dat ook aan: ...

Ik heb inderdaad al een parser geschreven. Op dit moment is de uitvoer een token-tree, maar het is vrij eenvoudig om mijn implementatie aan te passen zodat de output een expression-tree wordt.

offtopic:
Voor de geïntereseerden, een eenvoudige tutorial waarmee je zonder enige voorkennis een uitgebreide parser kan programmeren: Parsing Expressions by Recursive Descent

Soultaker schreef op zondag 29 maart 2009 @ 14:16:
Vervolgens definiëren ze een nieuwe Const class die dus overeenkomt met de Expression class van de TS en laten ze alle visitor methoden Objects returnen, die de visitor instantie vervolgens weer moet casten naar Const. Dat is dus precies het "probleem" wat de TS nu ook heeft (voor zover het een probleem is).

Ik ben overigens wel met je eens dat een Visitor een elegante manier kan zijn om zo'n interpreter te implementeren (in ieder geval als je taal geen multimethods of iets als extension methods ondersteunt), maar ik heb het idee dat het verder los staat van het huidige probleem.

Ik zal het visitor-pattern eens goed bestuderen.

prototype schreef op zondag 29 maart 2009 @ 14:21:
Ander vraagje btw voor TS, ik zie dat je een enum bijhoudt voor Type ID's. Aangezien je hier al met polymorphic types en dynamic_cast werkt veronderstel ik ook dat je de typeinfo header al hebt geinclude (e.g. voor std::bad_cast). Kan je dan ipv al die getters handmatig schrijven niet eenvoudiger gewoon de typeid operator gebruiken hiervoor? Volgens mij doet dat namelijk eigenlijk precies hetzelfde, alleen minder error prone misschien doordat je niet die type() method van je hoeft te schrijven elke keer en niet rare dingen kan schrijven als:

C++:

class int_value : public expression {
    virtual inline const expression::id_type type() const
    {
        return expression::LONG; // om maar even iets te roepen
    } 
}

Voor elke type die je toevoegt hoef je dan ook niet de Expression class aan te passen om de enum bij te werken.

Daar had ik eigenlijk helemaal niet aan gedacht. Ik gebruik momenteel helemaal geen dynamic_casts, immers kan ik upcasts ook doen middels een static_cast.

prototype schreef op zondag 29 maart 2009 @ 14:21:
Nog een extra tip voor TS: pas flyweight pattern toe voor constante waarden :-) Het n maal voorkomen van "1" in je AST zou niet gelijk moeten staan aan n maal een instantie hebben van int_value, maar in plaats daarvan, 1 instantie "1" met n referenties.

De memory-footprint van mijn expression-tree is opzich geen probleem, maar het is wel een goede tip. Ik zal er aan denken als ik eindelijk een 'werkende' implementatie heb.


Iedereen bedankt voor de tips en antwoorden.

[prototype]

Urgh, moet wel een hele ruige nacht voor me zijn geweest dat ik dynamic_cast lees waar static_cast staat -_-".