ENH: add expression evaluation functionality via eval
closes #3393
closes #2560 

cc @jreback
# `eval` Roadmap
## PyTables

allows natural syntax for queries, with in-line variables allowed

some examples
`"ts>=Timestamp('2012-02-01') & users=['a','b','c']"`

`['A > 0']`

`'(index>df.index[3] & index<=df.index[6]) | string="bar"'`

```
dates=pd.date_range('20130101',periods=5)
'index>dates'
```

Todos:
- [x] Release Notes
- [x] v0.13.txt examples (and link to docs)
- [x] update docs / need new examples
- [x] API changes (disallow dict, show deprecations for separated expressions)
- [x] tests for `|` and `~` operators
- [x] tests for invalid filter expressions
- [x] code clean up, maybe create new `Expr` base class to opt in/out of allowed operations
    (e.g. `Numexpr` doesn't want to allow certain operations, but `PyTables` needs them,
     so maybe define in the base class for simplicity, and just not allow them (checked in `visit`),
     which right now doesn't allow a `generic_visitor`)
- [x] can `ops.Value` be equiv of `ops.Constant`?
## `query` method
- [x] a few more doc examples
- [x] add a section in `query` docstring to show use of `__getitem__` and then add to `indexing.rst`
- [x] `query` docstring
## `DataFrame.eval` method
- [x] implement query in terms of this
- [x] tests
## Documentation
- [x] **RELEASE NOTES**
- [x] v0.13.txt examples & link to docs
- [x] document `in` and `not in`
- [x] enhancing performance section
- [x] `eval` docstring
- [x] Warn users that this is _not_ a magic bullet
  - E.g., `x = 3; y = 2; pd.eval('x // y', engine='python')` is many times slower than the same operation in actual Python.
## Engines
- [x] `python` engine for testing (basically a restricted eval, should make sure nothing dangerous a la `eval('os.system("sudo rm -rf /")')`) is possible here
- [x] `numexpr` engine
## Parsers
- [x] `python` parser is currrently not failing on complex bool ops involving subscripting like it should (potentially could `eval` the compiled AST instead of dispatching to function calls)
- [x] preparse should handle subscripting
- [x] `pandas` parser should handle subscripting, i.e., `df.query(...) == pd.eval('df[...]')`
- [x] `pandas` parser
- [x] `python` parser
- [x] `pytables` engine and parser (internal)

Should python be the default engine for small frames?
## Functions
- [x] toplevel `isexpr`
- [x] move `eval` to top-level pandas
## Error Handling
- [x] syntax error handling
- [x] name error handling
- [x] ugly stack overflow when an expression is not in frame...issue with variable resolution in `expr.py`. should fail fast.
## Alignment
- Algorithm
  1. flatten the tree of terms
  2. resolve the variables, special casing only numpy arrays/scalars/single unary operations (probably room for more  abstraction here)
  3. align by joining on the indices using the current broadcasting behavior
  4. update the original namespace with the newly aligned version of the underlying numpy array
  5. reconstruct the final object with the aforementioned joined indices and type
- [x] unary alignment
- [x] binary alignment
## Scope
- [x] add `@a` syntax for referencing local variables with the same name as a column
- [x] deal with global scoping issues (not sure if this is tested well enough...which means probably not)
- [x] allow `Expr` objects to be passed to `eval` (`Expr` will pull in the local and global variables from the calling stack frame)
## Miscellaneous
- [x] support for `MultiIndex` queries
- [x] **remove instance testing methods once series ndframe is merged**
- [x] `str` ops (implemented using `isin`)
- [x] basic `Timestamp` and `datetime` functionality
- [x] vbench!
- [x] single variable or constant evaluation e.g., `pd.eval('1')` or `pd.eval('df')`
- [x] reconstruct the final object to return the expected output type, e.g., `df + df2` should return a `DataFrame` if `df` and `df2` are both `DataFrame` objects.
- [x] change `Expression` to `Expr`
- [x] add `truediv` keyword to `Expr`, default to `True`
- [x] allow `and`, `or` and `not` aliases for the operators `&`, `|` and `~`, respectively
- [x] chained comparisons
- [x] attribute access syntax e.g., `df.A`
## Operators
- [x] `%`
- [x] `**`
- [x] unary ops don't play well when they are operands of binary ops
## Tests
- [ ] `PeriodIndex` objects are untested at large (a few scattered tests for basic things)
- [x] add tests for strange column names e.g., `df['@awesome_domain']`, `df['df["$10"]']`
- [x] Python 3 handles complex scalars differently, so test that
- [x] **revert equality testing in `align.py` once #4379 is merged**
- [x] boolean ops fail with a `DataFrame` with a `PeriodIndex` in the columns
- [x] test alignment of `DatetimeIndex` objects
- [x] rewrite a few tests in the python evaluator to make sure the `//` operator works as it should (it works, but there may be edge cases that I haven't though of yet)
- [x] `//` `numexpr` only supports scalar evaluation here: variables are not allowed so this will always eval in python space (half-assed it a bit in the tests here need to fix that)
- [x] truediv keyword tests
- [x] add tests for nans
- [x] fix `**` associativity issue in testing
## Syntax (Easier)
- [x] handle `in`, `not in` ( ~~was thinking~~ implemented as `a in b` -> `b.isin(a)` and `a not in b` -> `not a in b` -> `~b.isin(a)`)
## Syntax (More difficult)
- reductions (`sum` and `prod`)
- math ops (sin, cos, tan, sqrt, etc.), i.e., whatever `numexpr` supports
- ~~function calls~~ (we're not building a Python interpreter here :wink:)
## Optimizations

There's a quite a bit of recursion going on here, where maybe something stack-based might be more efficient. For example, an expression like `df['f in g and a < b < (c ** 2 + b ** 2 - a ** 3) and d in b not in e']` will make 3 recursive calls to eval (not including the top level call). One for the first `in` expression and two for the `in`/`not in` chain. A stack-based implementation of the parser (instead of recursively visiting nodes) could possible shave off a few milliseconds. Not sure if this is worth it though.
## Others
- ~~alignment for `NDFrame`~~ #4336 
- ~~replace current `evaluate` function~~

ok....was able to pull/push just fine now....

maybe the original rebase caused me to look at something different?
 ok so no rebasing until later...agreed?
 ```
[sheep-jreback-~/pandas] git remote show origin
* remote origin
  Fetch URL: git://github.com/pydata/pandas.git
  Push  URL: git://github.com/pydata/pandas.git
  HEAD branch: master
  Remote branches:
    PR_json-normalize-proto                    tracked
    add-msgpack                                tracked
    eval-3393                                  tracked
    index-not-ndarray                          tracked
    master                                     tracked
    range-index                                tracked
    refs/remotes/origin/PR-test-3503           stale (use 'git remote prune' to remove)
    refs/remotes/origin/applymap               stale (use 'git remote prune' to remove)
    refs/remotes/origin/c-parser               stale (use 'git remote prune' to remove)
    refs/remotes/origin/cython-refactor        stale (use 'git remote prune' to remove)
    refs/remotes/origin/datetime64-inference   stale (use 'git remote prune' to remove)
    refs/remotes/origin/eval3                  stale (use 'git remote prune' to remove)
    refs/remotes/origin/eval4                  stale (use 'git remote prune' to remove)
    refs/remotes/origin/groupby-apply-refactor stale (use 'git remote prune' to remove)
    refs/remotes/origin/large-excel-files      stale (use 'git remote prune' to remove)
    refs/remotes/origin/maintenance/0.7.x      stale (use 'git remote prune' to remove)
    refs/remotes/origin/maintenance/0.9.x      stale (use 'git remote prune' to remove)
    refs/remotes/origin/meta                   stale (use 'git remote prune' to remove)
    refs/remotes/origin/modes                  stale (use 'git remote prune' to remove)
    refs/remotes/origin/nanoseconds            stale (use 'git remote prune' to remove)
    refs/remotes/origin/period-unit-change     stale (use 'git remote prune' to remove)
    refs/remotes/origin/string-methods         stale (use 'git remote prune' to remove)
    refs/remotes/origin/timezone-fixes         stale (use 'git remote prune' to remove)
    refs/remotes/origin/tseries-plotting       stale (use 'git remote prune' to remove)
    refs/remotes/origin/unicode-fix            stale (use 'git remote prune' to remove)
    refs/remotes/origin/unsafe-assign-dtype    stale (use 'git remote prune' to remove)
  Local branches configured for 'git pull':
    eval-3393 rebases onto remote eval-3393
    master    rebases onto remote master
  Local refs configured for 'git push':
    eval-3393 pushes to eval-3393 (up to date)
    master    pushes to master    (up to date)
```

this eval-3393 push to eval-3393 is good (was not there previously).

maybe having a different local name was a problem somehow
 why don't you try rebasing those last 2 commits into one?
 see what happens
 ok let's see...
 i picked up the change.....

so I guess as we don't rebase at the same time or while one is working, maybe ok
 going to be hard to coordinate that though
 in any event....let's just push for now...can fix commits later

you are welcome to create `BaseExprVisitor` or somesuch if you want
 not as long as we push/pull.....just don't rebase
 right yeah that's what i meant
 should the numexpr engine allow the `=` syntax for equality? i would tend toward making the smallest possible superset of syntax allowed preferable there's nothing extra, except later maybe and or not and we change the precedence of bitwise operators...so i would only allow `=` to replace `==` in pytables expressions
 i would make `=` raise in `Numexpr` as maybe someday can implement it; for now should be an error I think
 got a `query` method going and `df['b + c < a + b']`-style indexing going + refactor the base visitor class

throwing a `NameError` in some tests in the expression in getitem, need to figure out why rather than just catching and then passing to the usual functionality (which works, but i need to know why)
 hm maybe query for now and indexing later. seems to break a ton of stuff i don't have it down just yet what the rules should be for indexing with something that _could_ be an expression
 actually only a few tests were broken by indexing, my refactor seems to have broken the other things
 ok.....lmk when I should take a look....I am pretty much done for now....(maybe will start on docs soon)
 thanks for the pytables stuff!
 it was built on a nice base!
 ah shucks, thanks :)
 i will support chained comparisons--they aren't a big deal to add...although things will be evaluated twice by `numexpr`.

e.g., `a < b < c` -> `a < b & b < c`

more generally

`x1 < x2 < ... < xN` -> `x1 < x2 & x2 < x3 & ... & xN-2 < xN-1 & xN-1 < xN`

so inner terms will be evaluated 2 \* (N - 2) times

something like

``` python
reducer = lambda x, y: BinOp(op=BitAnd, operands=[Compare(op=node.op, comparators=[x, y])])
reduce(reducer, node.comparators)
```
 i wish github had latex
 are u doing this transform directly?

I don't think me will mind the extras prob optimize them away anyhow
 yes i would do it in the base class

essentially build a new node and then visit it similar idea to assignment.

compare nodes will be passed over `N + 2 * (N - 2) + 2` times i believe (where `N` is the number of operands in the chain), since there will be a loop over each comparator in the "real" chained comparison parse, that's the first N then when compares are parsed again into a `BinOp` tree the first and last operand are evaluated once that's 2 and each of the N - 2 "inner" operands is evaluated twice. i think that's right...

that shouldn't be a big deal for parsing unless you have a ridiculously large chained comparison like 1000 compares or something.
 if its easy ok

otherwise u can just detect it for now and disallow
 @jreback just added the `query` method, could probably use some more tests

i think indexing should be off limits for now b/c of date strings, since `df['1/1/2001']` could be division or a date string index, unless u can think of a way to get around that...
 I agree

and I like query / eval better
 @jreback resolution is now there. i opted for a `dict`-like object to be passed around and have its `get` method called at name resolution time. that way any object implementing a dict-like interface can be used, which is consistent with how Python itself does name resolution
 @jreback can any of ur list above be checked off?
 @meteore if you're interested you can pull down this pr and play around with query. Still need to put in the index fallback. Shouldn't be a big deal to add. 

That reminds that I need to write a test to make sure that constants don't ever get used as keys.

Also for now only numeric columns work.

Thinking further about the relational db issue, I think it would be nice to be able to collect related frames together with a schema class and a RelationalDataFrame class. Like @meteore I often have a slew of frames related to each other that I would like to pass around as a single object and perform queries on. Very rough idea but might be worth exploring. 
