41

2

5

4

Espresso Expression transformation package.

Symbolic manipulation

Espresso provides functions for finding, matching, substituting and rewriting Julia AST. A few examples:

Match power expression and extract its first argument

pat = :(_x ^ 2)  # anything starting with `_` is a placeholder, placeholder matches everything
ex = :(A ^ 2)
matchex(pat, ex)
# ==> Dict{Symbol,Any} with 1 entry:
# ==>   :_x => :A    -- placeholder _x captured symbol :A

Find all function calls with any number of arguments:

pat = :(_f(_a...))    # `_a...` will match 0 or more arguments
ex = quote
x = foo(3, 5)
y = bar(x)
z = baz(y)
end

findex(pat, ex)
# ==> 3-element Array{Any,1}:
# ==>  :(foo(3, 5))
# ==> :(bar(x))
# ==>  :(baz(y))

Substitute symbol y with quux(x):

ex = :(z = 2x + y)
subs(ex, Dict(:y => :(quux(x))))
# ==> :(z = 2x + quux(x))

Rewrite all function calls with corresponding broadcasting:

ex = :(z = foo(x) + bar(y))     # take this expression
pat = :(_f(_a...))              # match recursively to this pattern
rpat = :(_f.(_a...))             # and rewrite to this pattern
rewrite_all(ex, pat, rpat)
# ==> :(z = (+).(foo.(x), bar.(y)))

See rewrite.jl for more expression transformation functions and their parameters.

Expression graph

Sometimes we need more sophisticated transformations including those depending on argument types. Espresso can parse expressions into a graph of basic calls and assignments using ExGraph type, e.g.:

ex = :(z = x ^ 2 * (y + x ^ 2))
g = ExGraph(ex; x=3.0, y=2.0);     # `x` and `y` are example values from which ExGraphs learns types of these vars
evaluate!(g)                       # evaluate all expressions to fill values of intermediate nodes
g
# ==> ExGraph
# ==>   ExNode{input}(x = x | 3.0)
# ==>   ExNode{input}(y = y | 2.0)
# ==>   ExNode{constant}(tmp390 = 2 | 2)
# ==>   ExNode{call}(tmp391 = x ^ tmp390 | 9.0)
# ==>   ExNode{constant}(tmp392 = 2 | 2)
# ==>   ExNode{call}(tmp393 = x ^ tmp392 | 9.0)
# ==>   ExNode{call}(tmp394 = y + tmp393 | 11.0)
# ==>   ExNode{call}(z = tmp391 * tmp394 | 99.0)

Such representation, although somewhat cryptic, is more flexible. For example, using it we can easily get rid of common subexpressions (x ^ 2):

g2 = eliminate_common(g)
# ==> ExGraph
# ==>   ExNode{input}(x = x | 3.0)
# ==>   ExNode{input}(y = y | 2.0)
# ==>   ExNode{constant}(tmp390 = 2 | 2)
# ==>   ExNode{call}(tmp391 = x ^ tmp390 | 9.0)
# ==>   ExNode{call}(tmp394 = y + tmp391 | 11.0)
# ==>   ExNode{call}(z = tmp391 * tmp394 | 99.0)

to_expr and to_expr_kw construct a Julia expression back from ExGraph:

to_expr_kw(g2)
# ==> quote
# ==>     tmp390 = 2
# ==>     tmp391 = x ^ tmp390
# ==>     tmp394 = y + tmp391
# ==>     z = tmp391 * tmp394
# ==> end

07/27/2016

11 days ago

200 commits