Assigning a variable used in the right hand side of the expression

[lbenet]

Hi,

first of all, thanks for provinding this package!

I came to the following error:

julia> using Espresso

julia> ExGraph(:(x = x + 2) )
ERROR: StackOverflowError:
Stacktrace:
 [1] #get_vars#48 at /Users/benet/.julia/v0.6/Espresso/src/indexing.jl:120 [inlined]
 [2] (::Espresso.#kw##get_vars)(::Array{Any,1}, ::Espresso.#get_vars, ::Expr) at ./<missing>:0
 [3] #get_var_names#51 at /Users/benet/.julia/v0.6/Espresso/src/indexing.jl:135 [inlined]
 [4] get_var_names at /Users/benet/.julia/v0.6/Espresso/src/indexing.jl:135 [inlined]
 [5] dependencies at /Users/benet/.julia/v0.6/Espresso/src/exnode.jl:106 [inlined]
 [6] collect_deps!(::Espresso.ExGraph, ::Espresso.ExNode{:call}, ::Int64, ::Set{Symbol}) at /Users/benet/.julia/v0.6/Espresso/src/expand_deps.jl:8
 [7] collect_deps!(::Espresso.ExGraph, ::Espresso.ExNode{:call}, ::Int64, ::Set{Symbol}) at /Users/benet/.julia/v0.6/Espresso/src/expand_deps.jl:10 (repeats 32738 times)
 [8] collect_deps!(::Espresso.ExGraph, ::Symbol, ::Int64, ::Set{Symbol}) at /Users/benet/.julia/v0.6/Espresso/src/expand_deps.jl:28
 [9] collect_deps(::Espresso.ExGraph, ::Array{Symbol,1}, ::Int64) at /Users/benet/.julia/v0.6/Espresso/src/expand_deps.jl:62
 [10] remove_unused(::Espresso.ExGraph, ::Array{Symbol,1}) at /Users/benet/.julia/v0.6/Espresso/src/optimize.jl:40
 [11] #fuse_assigned#99(::Void, ::Function, ::Espresso.ExGraph) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:345
 [12] #ExGraph#81(::Bool, ::Dict{Any,Any}, ::Array{Any,1}, ::Type{T} where T, ::Expr) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:28
 [13] Espresso.ExGraph(::Expr) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:23

Any advice to get around this?

[dfdx]

This is expected - ExGraph represents an algebraic expression graph where each node is a unique single-assignment variable. This allows to do all kinds of fun things like symbolic differentiation, common subexpression elimination, code generation for CPU & GPU, etc. The exception you see indicates that Espresso tries to collect dependencies of x, and since in your expression x depends on itself, Espresso falls into an infinite loop.

What are you trying to do? In most cases it's enough to replace LHS x with some other name to make it working.

[lbenet]

Thanks for your answer (and sorry for my late reply). I did use the trick you suggest, but thought there was another way around. In any case the explanation of the design and purpose clarified lots of things!

I am using Espresso to infer the graph structure (detect subexpressions, binary or unary) within a function (passed to a macro), which I somehow transform to rewrite the function in an "optimized" way. With my very primitive approach, I exploit some of Espresso.jl functionality to have some sort of parser. I already have something working (see this if you are interested), which allows me to parse indexed variables (by renaming them), but it does not yet allow me to parse for loops, which is what I am currently trying to solve. If you have any comments or suggestion, they are always welcome!

(Feel free to close this at any time.)

[dfdx]

Looks great! I think we can improve Espresso itself to better handle the tasks you described. For example, there's actually no reason for ExGraph not to support indexing - I mostly develop Espresso in the context of XDiff.jl which reserves indexing for EinGraph (ExGraph analogue for Einstein indexing notation), but we can as easily allow it in vectorized (not Einstein) notation.

for loops, conditions and modification of variables are more complicated and certainly restrict use cases (e.g. non static single assignment will break topological sort as it's implemented now), but if you don't use these features, there's no reason not to allow these features. Let me think about it a bit.

Meanwhile, you may be interested in pluggable codegens (which I plan to move from XDiff to Espresso when I get a better idea about their design). In particular, I was thinking about making a function like blassify that takes a "naive" expression and rewrites it into an optimized version using BLAS, broadcasting and buffering to improve performance. I already use it for generating derivative expressions, and optimizations sometimes give 100x boost in speed.

[lbenet]

I've been playing with the for loops and, as you describe, they are more complicate and very tricky. Within my approach, bookkeeping is a bit subtle, so I haven't quite manage the cases I have in mind, but i don't think I am too far.

I will certainly take a look on blassify; I guess the basic goal of @taylorize_ode is precisely that; optimize memory usage and performance time. So far, for simple demonstrations, I've got speed-ups in the 5x-10x range.

[dfdx]

Can you describe the case you have in mind and what you have already achieved?

I'm thinking about a new type of node - ExNode{:for} - which holds a reference to another graph and act like a function call. Roughly speaking, we can transform:

x = 0
for i=1:10
    x = x + 1
end
y = 2x

to:

x = 0
new_x = forloop(x, 1:10)
y = 2 * new_x

where forloop refers to a graph equivalent to:

new_x = x + 1

That is, we can treat all variables used in a loop as inputs (node dependencies) and all variables modified in the loop as outputs. Not sure if it's helpful for any particular task, but at least this representation should play well with existing tools.

[lbenet]

My naive approach is book-keeping each expression of the graph structure of the function/loop, to somehow separate those auxiliary variables that need to be declared at the beginning of the transformed function. My approach reflects what you mention above, without the elegance of the whole design of Espresso.

I should push soon commits that allows parsing the for loops. Yet, since I am in a conference, I am not 100% working on that. Sorry for this.

[lbenet]

Sorry for the long silence on my side, but I was traveling and, once I was back we had the earthquake in Mexico.

So, I have pushed a couple of commits addressing two cases of for loops of our interest, and I guess that the implementation does not work always. The case I was playing with, resembling yours above, looks like this:

r2 = zero(x[1])
for i in eachindex(x)
    r2_aux = r2 + x[i]^2
    r2 = r2_aux
end

Essentially what I did was, first, get rid of the indexed variables (tmp1 = x[1], tmp2=x[i]), and then use to_expr(ExGraph(ex)) for each argument of the for-loop block, separately. (I need to have r2_aux becauseof the stack overflow which initiated this issue.) The tricky part was, again, the proper bookkeeping: r2_aux = r2 + x[i]^2 gets transformed into two expressions, tmp3 = tmp2^2 and r2_aux = r2 + tmp3, and for our case it is important to have tmp3 be an indexed variable, i.e., tmp3[i]; it was tricky to recognize when you need it to be indexed, and when not (r2_aux should not be indexed). This is more or less the current status.

I have another question/suggestion (maybe I should open another issue, but for the time being, I'll stick to this one): Some times, within the args of the function I which go through ExGraph I encounter cases like myfunction(x,y,z), a function built by the user. Currently, ExGraph throws an UndefVarError which I understand. The question is whether there is a list of the functions recognized by ExGraph. The idea is to check in advance if the function called exists, and if not, simply copy verbatim that function call to the (final) transformed expression?

Once again, thanks a lot for the effort and the nice package!

[dfdx]

Hope you are doing well! I heard about the earthquake from the news, but such things always sound like something far far away until you meet a person from there.

and for our case it is important to have tmp3 be an indexed variable, i.e., tmp3[i]; it was tricky to recognize when you need it to be indexed, and when not (r2_aux should not be indexed).

Would it help if Espresso recognized indexing as a separate expression? I'm currently deprecating everything about Einstein notation (which used indexing extensively) and adding new features to ExGraph. It already can recognize indexing with constants, i.e.:

julia> ExGraph(:(y = x[1]))
ExGraph
  ExNode{ref}(y = x[1] | nothing)

I can add indexing with variables (e.g. x[i]) if it helps, but can't promise it won't be broken in the nearest future. Does it make sense for you?

Currently, ExGraph throws an UndefVarError which I understand.

It's a bug. I fixed it and pushed to master. However, it uncovers one feature that might be interesting to you: when parsing a function, ExGraph calls canonical(module, function_name) to get a convenient name of the function. For example, if it encounters a call to foo() that comes from module Bar, it replaces it with a qualified name, i.e. Bar.foo(), to guarantee that it will be found in a client code. At the same time, names like Base.+ are replaced with a simpler name + for brevity. It shouldn't impact your code much, but don't be surprised to see such transformations.

[lbenet]

We are all well, luckily. During a week essentially all activities were somehow affected or interrupted, since the damages were vast and help was needed. Things are getting back to normal for most people.

Would it help if Espresso recognized indexing as a separate expression? I'm currently deprecating everything about Einstein notation (which used indexing extensively) and adding new features to ExGraph.

I guess it would clean and shorten the code; for the time being, the trick with renaming the variables first, and later renaming them back was enough. So, I guess it is better that you go on, and later, perhaps in a separate branch, we can test that.

Currently, ExGraph throws an UndefVarError which I understand.

It's a bug. I fixed it and pushed to master. However, it uncovers one feature that might be interesting to you: when parsing a function, ExGraph calls canonical(module, function_name) to get a convenient name of the function. For example, if it encounters a call to foo() that comes from module Bar, it replaces it with a qualified name, i.e. Bar.foo(), to guarantee that it will be found in a client code. At the same time, names like Base.+ are replaced with a simpler name + for brevity. It shouldn't impact your code much, but don't be surprised to see such transformations.

Thanks a lot! I will play now with this feature to see if more complicate functions can now be parsed. The speed-up I am getting are worth!

I'll keep you informed.

[lbenet]

Again, sorry for the long silence; I have been busy working on parsing our ODEs, and trying to solve some specific issues. It is slowly getting to a point that it can be used, though now always.

In doing so, I just encountered the following issue (should I report it in another issue?), which seems quite odd to me. Below is what I obtain from a new started session in the REPL (Julia 0.6.2-pre.0).

julia> using Espresso

julia> to_expr(ExGraph(simplify( :(X = Array{Taylor1{Float64}}(N, N)) )))
quote  # /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl, line 79:
    X = Array{Taylor1{Float64}}(N, N)
end

So far, so good, and this is the behavior I am actually after. Now comes the odd part, again, from a brand new session:

julia> using TaylorIntegration, Espresso

julia> to_expr(ExGraph(simplify( :(X = Array{Taylor1{Float64}}(N, N)) )))
ERROR: MethodError: no method matching function_name(::Type{Array{TaylorSeries.Taylor1{Float64},N} where N})
Closest candidates are:
  function_name(::Function) at reflection.jl:861
Stacktrace:
 [1] canonical(::Module, ::Expr) at /Users/benet/.julia/v0.6/Espresso/src/utils.jl:169
 [2] parse!(::Espresso.ExGraph, ::Espresso.ExH{:call}) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:229
 [3] parse!(::Espresso.ExGraph, ::Expr) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:176
 [4] parse!(::Espresso.ExGraph, ::Espresso.ExH{:(=)}) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:202
 [5] #ExGraph#85(::Bool, ::Dict{Any,Any}, ::Array{Any,1}, ::Type{T} where T, ::Expr) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:26
 [6] Espresso.ExGraph(::Expr) at /Users/benet/.julia/v0.6/Espresso/src/exgraph.jl:23

I should probably add that TaylorIntegration loads (and @reexports) Espresso; I simply loaded it explicitly to make it simpler calling ExGraph.

Any ideas where the problem may be?

[dfdx]

Hmm, I can't reproduce it with latest master of TaylorIntegration and Espresso. Are you on the same versions?

Note, that I've never tested functions with type parameters, so I'm even surprised it has been parsed at all :)

[lbenet]

Sorry, forgot to describe the actual status: I am using commit :88c73c4 of TaylorSeries.jl (loaded by TaylorIntegration), and I am using the branch "parse_eqs" of TaylorIntegration. The reason to use that commit of TaylorSeries.jl is because master includes some breaking changes, that break precisely TaylorIntegration. I hope this info allows you to reproduce the problem.

[dfdx]

Got it, now it's reproducible. Indeed, one of the used functions accepts functions, but not constructors (i.e. types). I'll check it tomorrow.

[lbenet]

Thanks a lot!

[dfdx]

Please, check out parametric-types branch and report if there any remaining issues.

Some details you should be aware of.

1. The difference between using Espresso and using TaylorIntegration, Espresso is that in former case Taylor1 is undefined and thus expression is passed further as is, while in later case type definition becomes available and Espresso tries to qualify its name. Since name parameters were not supported, name resolution failed. Now it should be mostly fixed.

2. Type parameters are tricky. For ordinary functions and constructors there's exactly one easily identifiable module they come from, e.g. Float64 is defined in Core and ExGraph is defined in Espresso. However, composite types like Array{ExGraph} include types from several modules, which Espresso doesn't expect and may handle incorrectly. Moreover, union types like Array{Taylor1} (which is in fact Array{Taylor1, N} where N) are UnionAll and not DataType, and this add more even more complexity.

I tested parametric-types with ordinary constructors, fully defined parametric types (e.g. Array{Taylor1, 1}) and UnionAll (e.g. Array{Taylor1}), but there may be many more cases, so support for parametric types should be considered experimental.

[lbenet]

I've checked-out to the parametric-types branch as suggested, and it does work! Thanks really a lot!