[GSoC 2015 Week 3]

Hi, this is my third post of weekly record for GSoC 2015.

What I did this week is to implement an optimization on local_dimshuffle_lift optimizer. This optimizer does following transfers,

DimShuffle(Elemwise(x, y)) => Elemwise(DimShuffle(x), DimShuffle(y))
DimShuffle(DimShuffle(x)) => DimShuffle(x)

This optimizer is a local optimizer, which means it will be called by global optimizers several times on different nodes. For example, here is a function graph,

DimShuffle{1,0} [@A] ''   
 |Elemwise{mul,no_inplace} [@B] ''   
   |DimShuffle{x,0} [@C] ''   
   | |Elemwise{add,no_inplace} [@D] ''   
   |   |<TensorType(float64, vector)> [@E]
   |   |DimShuffle{x} [@F] ''   
   |     |TensorConstant{42} [@G]
   |Elemwise{add,no_inplace} [@H] ''   
     |<TensorType(float64, matrix)> [@I]
     |DimShuffle{x,x} [@J] ''   
       |TensorConstant{84} [@K]

If we apply local_dimshuffle_lift on this graph, it can be applied for at least 6 times, looking carefully at how this optimization works we will find that an optimization applied on node @A results in two new subnodes that can be applied on again.

So the idea is to recursively apply the optimizer. So that the optimizer will applied less times than before. An additional test case is also added.

I think perhaps doing things recursively can be replaced by a iterative way? I'll do some experiments first to know recursion's efficiency. Also, this optimization makes me recall another optimization on the to-do list, which will also be done recursively. Is there possibility to extract this pattern out?