AST matching and DAG analysis/optimization related features

[ct-clmsn]

Below are a couple of capabilities that could be added or extended to the ast-matcher that will be useful for testing. The capabilities can be used to perform ast/ir DAG analysis and optimization. The capabilities provide a reasonable way to get performance improvements (stochastic and/or heuristic) into the DAG analyzer/optimizer.

The capabilities will be useful when the data layout cost modeling is completed. The capabilities can provide further optimization mechanisms when the APEX and visualization technologies are available.

The capabilities are:

• [ ] Provide a "finite-state-machine styled" mechanism to create a set of ast/ir DAGs that can be used to perform exact matches against given an input ast/ir DAG.
• [ ] Provide a finite-state-transducer (weighted and un-weighted) that modifies or creates a new ast/ir DAG given an input ast/ir DAG. The transducer can be used to create, store, and apply stochastic and/or heuristic optimizations.
• [ ] Provide a hidden-markov-model or conditional random field styled mechanism that modifies or creates a new ast/ir DAG given an input ast/ir DAG. This technology is typically found in spelling correction systems and could be reapplied in this domain to create, store, and apply stochastic and/or heuristic optimizations.
• [ ] Provide serialization support (load/store) for each capability.
• [ ] Expose an api to python in order to simplify or facilitate fast phylanx fsms, fsts, hmms, or crf creation.

An existing open source technology that reflects a reasonable and extensive implementation of these capabilities can be found in the OpenFST project. The transducer and hmm capabilities can be considered a "machine learning" optimization capability. reference material

[ct-clmsn]

Moved the content of this ticket into a wiki page for research ideas.

[ct-clmsn]

I started work on implementing the tree transducer in C++, as defined in this paper. This will be a tree-to-tree transducer, or a weighted regular tree grammar (wRTG).

Requirements for implementation:

• [x] define a tree transducer in C++ using a format similar to pg 403.
• [ ] implement operations to support 'produce'
• [ ] implement 'produce' (algorithm 1)
• [ ] implement operations to support 'match'
• [ ] implement 'match' (algorithm 1)
• [ ] implement operations to support 'deriv'
• [ ] implement 'deriv' (algorithm 1)
• [ ] implement operations to support 'rtgprune'
• [ ] implement 'rtgprune' (algorithm 2)
• [ ] implement operations to support 'reach'
• [ ] implement 'reach' (algorithm 2)
• [ ] implement operations to support 'use'
• [ ] implement 'use' (algorithm 2)
• [ ] implement 'train' (algorithm 3), this creates a wRTG.
• [ ] implement wRTG transform algorithm