Rewrite Rules Roadmap

Rewrite rules were introduced in PR 1560. They are an attempt to separate mathematical programming from algorithmic programming. They are currently used in the MatrixExpressions module but could be applied more broadly in SymPy if they demonstrate merit.

They are inspired by the Maude System and Stratego/XT.

What else remains to be done? Here is a list of tasks that someone could take on if they're interested in helping with this endeavor.

1. Apply rules to other parts of matrix expressions (trace, inverse, etc...)
2. Create an assumptions system for matrix expressions (the logic programming of assumptions goes hand in hand with rewrite rules). This opens some interesting doors.
3. Develop a pattern matching solution so that we have a higher level alternative to write rules instead of python functions.
4. Look at the expr code and think about other highly general rules. This probably involves more thinking than coding. I have a strong preference here to keep the ruleset orthogonal (i.e. very few very general complementary functions) so as a warning I'll probably be very critical during pull requests to the rules module (although it sounds like you might share my coding philosophy here). Probably we shouldn't actually change the expr code for a while though.
5. Convert the sets module to use rules. It's already halfway there in spirit. Check out all of the _union and _intersection methods as well as reduce. This was the predecessor to the rules module.
6. Create a cool example to show off debug. Having a system that shows how SymPy does what it does step by step has been on the GSoC project list for a wihle. I think that this project is an effective side-effect of the debug strategy :) It would be nice to have a good example and write it up. This will be much cooler if we have 2.
7. Look at branching strategies. If our rules are not confluent then we can arrive at different results by applying rules different orders. We need a mechanism to iterate through these possibilities efficiently. We also need a way to search this space while trying to minimize something (like the length of the string representation). We need a way to iterate this set (generators) and a way to search (dynamic programming?). The current strategies may need to be transformed to handle generators instead of exprs. This should probably exist separately from the existing strategies.

I'm personally building up to recreating (and then extending) this project in SymPy. I think I've sent out this link before, not sure. Anyway, that's my personal vision. 1, 2, and 3 are about that. 4 is more long-run thinking for SymPy. 5 is just fun. 6 is very cool. 7 pushes us past any other CAS. It has been implemented in StrategoXT but not, (to my knowledge) used to any great extent.

Alternatively, think of something else. What other non-core modules could we try this on that would teach us different lessons from what we've learned in Matrix Expressions?