Initial add of the generic optimizer code

Before digging into this code, look at the Rules implemented at the bottom of DagOptimizer.

There are several TODOS here:

- [x] After I split the code into separate files, I started hitting a scala 2.9 compiler bug, that I don't hit in 2.10. I'll try to work around, or possibly hope that Twitter finally gets on 2.9 before we need this.

- [x] Tests tests tests. I played around at the repl, but clearly we need super hardcore tests for any optimization framework.

- [ ] Actually call this code from an existing platform.
For that case match, I think you can make an object with a custom 
unapply method, something like

def unapply(item: Any) = {
   item match {
     case AlsoProducer(_) => None
     case x => Some(x)
   }
}

Or something like that. I can't code for shit anymore :)

> P. Oscar Boykin <mailto:notifications@github.com>
> August 21, 2014 at 2:48 PM
>
> In 
> summingbird-core/src/main/scala/com/twitter/summingbird/planner/DagOptimizer.scala:
>
> > + }
> > +
> > + /**
> > + * (a ++ b).flatMap(fn) == (a.flatMap(fn) ++ b.flatMap(fn))
> > + * (a ++ b).optionMap(fn) == (a.optionMap(fn) ++ b.optionMap(fn))
> > + * and since Merge is usually a no-op when combined with a grouping 
> operation, it
> > + * often pays to get merges as high the graph as possible.
> > + */
> > + object MergePullUp extends Rule[Prod] {
> > + //Can't do this operation if the merge fans out
> > + def apply[T](on: ExpressionDag[Prod]) = {
> > + case OptionMappedProducer(m @ MergedProducer(a, b), fn) if 
> (on.fanOut(m) == 1) =>
> > + Some((a.optionMap(fn)) ++ (b.optionMap(fn)))
> > + case FlatMappedProducer(m @ MergedProducer(a, b), fn) if 
> (on.fanOut(m) == 1) =>
> > + Some((a.flatMap(fn)) ++ (b.flatMap(fn)))
> > + case _ => None
>
> actually, I spent some time on this. This does not work in a very 
> clean way. Look at the AlsoPullUp rule. We want to leave Alsos alone. 
> Not matching the case does not work, because there is a catch all case 
> below. For that catch-all, we really want all BUT AlsoProducer. I 
> don't know how to implement such a case match in scala (if it is 
> indeed possible).
>
> I don't like the verbosity of the Some/None in the return, but some 
> kinds of rules are not easy to express without them. Instead, what 
> about adding a PartialRule that hase applyWhere that returns a 
> PartialFunction, and then calls lift on it. In that way, we can use 
> the most convenient option for each case.
>
> —
> Reply to this email directly or view it on GitHub 
> <https://github.com/twitter/summingbird/pull/537/files#r16567853>.
>
> P. Oscar Boykin <mailto:notifications@github.com>
> August 12, 2014 at 8:47 PM
>
> Before digging into this code, look at the Rules implemented at the 
> bottom of DagOptimizer.
>
> There are several TODOS here:
>
> 1) After I split the code into separate files, I started hitting a 
> scala 2.9 compiler bug, that I don't hit in 2.10. I'll try to work 
> around, or possibly hope that Twitter finally gets on 2.9 before we 
> need this.
>
> 2) Tests tests tests. I played around at the repl, but clearly we need 
> super hardcore tests for any optimization framework.
>
> 3) Actually call this code from an existing platform.
>
> ------------------------------------------------------------------------
>
>
>         You can merge this Pull Request by running
>
> git pull https://github.com/twitter/summingbird dag_processing
>
> Or view, comment on, or merge it at:
>
> https://github.com/twitter/summingbird/pull/537
>
>
>         Commit Summary
>
>   * Initial add of the generic optimizer code
>
>
>         File Changes
>
>   * *M*
>     summingbird-core/src/main/scala/com/twitter/summingbird/Producer.scala
>     <https://github.com/twitter/summingbird/pull/537/files#diff-0> (14)
>   * *A*
>     summingbird-core/src/main/scala/com/twitter/summingbird/graph/Expr.scala
>     <https://github.com/twitter/summingbird/pull/537/files#diff-1> (50)
>   * *A*
>     summingbird-core/src/main/scala/com/twitter/summingbird/graph/ExpressionDag.scala
>     <https://github.com/twitter/summingbird/pull/537/files#diff-2> (199)
>   * *A*
>     summingbird-core/src/main/scala/com/twitter/summingbird/graph/HMap.scala
>     <https://github.com/twitter/summingbird/pull/537/files#diff-3> (111)
>   * *A*
>     summingbird-core/src/main/scala/com/twitter/summingbird/graph/Literal.scala
>     <https://github.com/twitter/summingbird/pull/537/files#diff-4> (61)
>   * *A*
>     summingbird-core/src/main/scala/com/twitter/summingbird/planner/DagOptimizer.scala
>     <https://github.com/twitter/summingbird/pull/537/files#diff-5> (244)
>
>
>         Patch Links:
>
>   * https://github.com/twitter/summingbird/pull/537.patch
>   * https://github.com/twitter/summingbird/pull/537.diff
>
> —
> Reply to this email directly or view it on GitHub 
> <https://github.com/twitter/summingbird/pull/537>.
>

-- 
Sam Ritchie (@sritchie)
Paddleguru Co-Founder
703.863.8561
www.paddleguru.com <http://www.paddleguru.com/>
Twitter <http://twitter.com/paddleguru>// Facebook 
<http://facebook.com/paddleguru>