Sign in to follow this  
King Mir

Design Question (C++)

Recommended Posts

I'm trying to build a library that can simplify mathematical expressions. I have an ExpressionPrt type, that is the base for all the different parts of an expression. Different expression parts include Constant, Variable, and Add (addition operator/function). Theses three are probably the most common, so they serve more as warning of future problems rather than problems themselves. But ultimately I want to have more complicated operations such as exponentiation and possibly derivation. The problem is how to build a dependency tree so that the user of this template library does not have to include the whole thing. In the case of addition, Add can simplify and organize statements contained in addition expressions, in order. So it can simplify y+3+x+7 to 3+7+x+y. It can identify that 3 and 7 are potentially addable (cause they are both constants). But in order to add the two numbers I need a component that knows about both the concepts of addition and of constants. How can I have such a component, without forcing the user to include all addable expression parts whenever he wants to add, and without forcing the user to include the operations that can be preformed on a constant whenever he wants to use constants. Similarly, how do I ensure that a default addition operation exists for those expression parts that cannot be added (that being to not simplify). My present solution is to just dump all functions that need to know about more than 1 expression part/concept into the base ExpressionPrt class. Obviously this is a bad solution because a)Adding more expression parts requires me to modify the ExpressionPrt class, and b) the default behavior for such operations often requires me to include the associated operation before ExpressionPrt, thus effectively forcing the user to include the entire library in each file that uses any small part. Help me find a better solution.

Share this post


Link to post
Share on other sites
Some of your statements suggest that your goal is to do this at compile time ? - if so then i think this is a really big ask. the following remarks assume that this is not the case.

Consider seperating the concept of the representation of the tree from the operations that are performed on the expression tree. I dont think trying to load overriden functionality into classes helps much or that inheritance or polymorphism works well with this type of problem. personally in the past i have just used an enum representing the node type and then when i want to manipulate the node have cast it to the correct form.

For example, you have an expression syntax tree (generated from a parse or deserialised from binary form for example) and then you have modules/functions etc that do things like constant folding, expression reordering, pruning of non side-effects expressions etc as seperate recursive transforms on the input expr tree. This is a reasonably modular approach - each operation becomes a seperate pass and can be put in a different file/library and can be more easily debugged, optimised or ommitted/included in testing.

Also i dont know what level you are aiming at and/or if its for fun and you can more afford to spend time experimenting but consider writing something whereby you can rapidly match a subsection of a tree with a set of pre-established patterns which also have specific transform rules associated with them. then you can generically recurse the tree (generally bottom up) matching against the patterns and performing the arbitrary associated transorm. this is a nice decoupling and buys you the ability to more-simply express many things the changes to the tree structure that you might want to make.

Share this post


Link to post
Share on other sites
Quote:
Original post by chairthrower
Some of your statements suggest that your goal is to do this at compile time ? - if so then i think this is a really big ask. the following remarks assume that this is not the case.
No, runtime; there's a simplify method that gets called to simplify the expression. But the issue is this compile time dependency. I want to be able to simplify y+x to x+y without including the Constant class.

Quote:
Consider seperating the concept of the representation of the tree from the operations that are performed on the expression tree. I dont think trying to load overriden functionality into classes helps much or that inheritance or polymorphism works well with this type of problem. personally in the past i have just used an enum representing the node type and then when i want to manipulate the node have cast it to the correct form.
How does doing this (using enums and casts) simplify the problem?

Quote:
For example, you have an expression syntax tree (generated from a parse or deserialised from binary form for example) and then you have modules/functions etc that do things like constant folding, expression reordering, pruning of non side-effects expressions etc as seperate recursive transforms on the input expr tree. This is a reasonably modular approach - each operation becomes a seperate pass and can be put in a different file/library and can be more easily debugged, optimised or ommitted/included in testing.

Are you're saying is instead of having a single recursive simplify method, I should instead have a sequence of recursive actions, one for each simplification step? How does that help? I still don't know which passes to make, since ultimately there is one simplify method.

Quote:
Also i dont know what level you are aiming at and/or if its for fun and you can more afford to spend time experimenting but consider writing something whereby you can rapidly match a subsection of a tree with a set of pre-established patterns which also have specific transform rules associated with them. then you can generically recurse the tree (generally bottom up) matching against the patterns and performing the arbitrary associated transorm. this is a nice decoupling and buys you the ability to more-simply express many things the changes to the tree structure that you might want to make.

This is for fun, so yeah I can spend time experimenting. However, I don't understand what you are suggesting here.

Also I want this to be a template. Any number type should be usable including bool, int, double, and complex types.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this