Inheritance in a composite structure

Question

Hello everybody,

i have a problem related to the design of a composite structure. I have an Expression abstract class that describes a generic mathematical expression. The idea is that an expression can be an atomic expression (like "x" or "3") or some kind of aggregation of atomic expressions (like summatories, productories, exponentiations, etc). That turns out to be well described by a Composite pattern, so for instance the class Summatory inherits from OperationTerm, that in turn inherits from Expression, and contains a list "augends" of Expression terms.

Everything is fine until I try to specialize some of these expression on the base of some properties; for example, if an Expression is made up by a Summatory of Monomial terms, it should be "labelled" as a Polynomial, in order to optimize certain kinds of operations (like integrals or derivatives) in a way that is transparent to the client code (that should handle only Expression objects).

Anybody has an idea on how I could design this kind of structure (possibly in an extensible way)?

Answer 1

If expressions are invariant ie they're never written to after creation, then you can just create instances of a specialised class (using a Factory pattern if you want to keep the details out of client code). If they're not invarient you can use the State pattern, and just treat the "labels" you talk about as different states of an expression.

Answer 2

You can't. Since you want to have different specialized expressions, you'll have to subclass Expression type.

Usually, when you define types that can be used to build Abstract Syntax Trees like that, you also provide a Visitor and/or a Modifier the client code can use to browse/modify a composite expression from a root.

As for the construction of a new composite expression tree, it should not be problematic since the client code knows what kind of expressions it wants to assemble.

Answer 3

If CompositeExpression is derived from Expression, and Polynomial is derived from CompositeExpression, then Polynomial is also an Expression (as you said, transparent to client code).

Answer 4

I think that you're going about it the wrong way. Don't worry about labelling things as a Polynomial etc.

Just ensure that your translation from whatever input into the actual data structure is simple and straightforward.

Things like Polynomial can be added later or tagged later onto the generic structure that you created originally.

This kind of design pattern comes up a lot in compilers/interpreters for both computer and natural languages. Basically, the first step is syntax analysis, where you build up a syntax structure, e.g. a syntax tree. Then, there is semantic analysis, where meaning is attached to the syntax. Judging by your descriptive terms, you are probably implementing an interpreter for mathematical expressions, so this would be a very close match.

Take a look at Kernighan and Pike for their dc (desk calculator) example, Aho Hopcroft and Ullman's books on data structures/language interpreters/compilers, examples of some modern simple compilers etc. They are a fruitful source of design patterns as well (although they predate the popularity of the term).