Thank you for your reply.
You mention two complexities: the complexity we implement patterns with recursion, and the pattern for reasoning it. To minimize these complexities, I will adjust the plan to do the followings first:
- solve the bugs in the current version of dominate pattern.
- rethinking the optimizations I have done via pattern matching, and express the patterns by dominate pattern if possible.
- Use the redirecting operation only for the case that the pattern can not be expressed by existing pattern language.
The algorithm efficiency is a deep topic. Note that GroupMatches, Partition and Rewriting requires traversing the full computational graph. In the current implementation, in the best case that every attempt to match a subgraph succeeds, and every AltPattern matches its left branch, the algorithm may only need to visit each node of computational graph once. In this view, perhaps the efficiency can be characterized by: 1. the probability of failure to match (including the failure to match a branch of AltPattern) and 2. and the average length of the subgraph of the computational graph that fails to match.
A recursive pattern does not necessarily have a larger probability of failure, nor a long average length of the subgraph that fails to match. So I think the recursion itself may not directly affect the algorithm efficiency. An interesting future research direction is the faster algorithm for matching (perhaps algorithms for regular expression matching may shed some lights).