One of the SymPy devs here. Without looking too into your code, I'd like to comment on the pattern-dispatch system, with regards to associative-commutative expressions. This has been on my mind a lot lately, as I've been working on a rewrite of our pattern matcher to be more efficient/versatile.
With dispatch on patterns for symbolic computation, there seem to be two schools of thought. If you read papers from the theorem proving world, most use a sufficiently-smart-matcher(tm) that can handle patterns with certain properties (associative, commutative, identity, etc...). Most of these result in a single, heavily optimized data structure that then performs all pattern dispatches. In this case, you'd load all your rules, and then run the rewrite system. In contrast, most of the computer algebra work use a more heuristic-y approach, with preprocessing of the patterns, and formation of many smaller matching structures. These are then applied manually in human-written logic code. By this I mean that you may have a structure for trig rewriting rules, and one for logarithm rules, etc... And then in your main routine (let's say a simplification routine), you would apply these manually (match(expr, trig_rules), match(expr, log_rules), etc...). The idea behind this is that in most cases you have some knowledge about the structure of the expression, which can reduce the number of rules you'd need to check. For larger collections of patterns, a good way is to use a discrimination net (a trie like structure), which can aid in faster matching. This paper is a good reference: Associative-Commutative Discrimination Nets <http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CB4QFjAA&url=http%3A%2F%2Fwww.cs.tufts.edu%2F~nr%2Fcs257%2Farchive%2Fleo-bachmair%2Fac-discrimination-nets.pdf&ei=WK3FVJDcMMyWgwSw-4KwCQ&usg=AFQjCNFqz6nwjmmU5qUsVKQt9lXYbMHWjQ&sig2=IsgVbf9v2ClZgXyeHI7_vQ>. This approach is great if you have a large group of patterns. For smaller collections of patterns, Richard Jenk's paper "A Pattern Compiler" <http://dl.acm.org/citation.cfm?id=806324&dl=ACM&coll=DL&CFID=621425526&CFTOKEN=54560421> is a decent starting point. This system is much more similar to that of Mathematica's than the one dscribed above (describes the pattern compiler for SCRATCHPAD, which later became AXIOM). Unfortunately, it doesn't deeply discuss the implementation, but the basic idea behind it is given. The gist is that a collection of patterns is preprocessed, and all possible combinations of rules (associative/commutative/identity) are expanded. A matching program is then created and evaled, creating a specialized rewrite function for that set. For small patterns/collections of patterns (which for computer algebra is the norm) this is a great system, and one that I think could be implemented in Julia. Sorry for the long response, this is something I've just been thinking about a lot lately. - Jim On Sunday, January 25, 2015 at 8:07:22 PM UTC-6, lapeyre....@gmail.com wrote: > > Hi, > > Here is some code I have been working on. It is for symbolic computation > based on pattern matching. > If you find it interesting, any feedback is welcome! > > https://github.com/jlapeyre/SJulia > > --John >
