DataFlow.jl is a code intermediate representation (IR) format. It can be thought of as antithetical to SSA form; where SSA allows only statements, DataFlow allows only expressions. Closures are represented explicitly, allowing full programs to be easily represented and manipulated and complex whole-program transformations to be applied. Moreover, programs can be kept in a high-level form that's very human-readable.
A data flow graph is a bit like an expression tree without variables; functions always refer to their inputs directly. Underneath it's a directed graph linking the output of one function call to the input of another. DataFlow.jl provides functions like
postwalk which allow you to do crazy graph-restructuring operations with minimal code, even on cyclic graphs. Think algorithms like common subexpression elimination implemented in one line rather than hundreds.
julia> using DataFlow: vertex, constant, Call
DataFlow.jl provides the
IVertex data type, which behaves a lot like Julia's
Expr type. We can construct vertices, and use them as inputs to other vertices, to build expressions.
constant is a shortcut for vertices representing constant values.
julia> using DataFlow: vertex, constant, Call, Constant julia> a, b = constant(1), constant(2) (IVertex(1), IVertex(2)) julia> c = vertex(Call(), constant(+), a, b) IVertex((+)(1, 2))
Call() object is analagous to the "head" in Julia's
Exprs, so this is like
Expr(:call, f, x...).
A key difference from
Expr is that the
IVertex is a graph, not a tree, and reuse is explicitly represented. Consider multiplying the expression
c by itself:
julia> d = vertex(Call(), constant(*), c, c) IVertex( bison = (+)(1, 2) (*)(bison, bison))
In order to represent the structure of the graph in text, DataFlow.jl prints an expression tree with a made-up variable binding (
bison). This variable is not present in the graph itself, but just used for presentation.
Graphs can also be dumped to Julia expressions using
DataFlow.syntax, which will similarly create variable bindings where needed.
julia> DataFlow.syntax(d) quote ##edge#668 = (+)(1, 2) (*)(##edge#668, ##edge#668) end julia> eval(ans) 9
Graphs are also allowed to be cyclic. We can introduce cycles using
thread!, which pushes a new argument into an existing vertex.
julia> DataFlow.thread!(c, c) IVertex(bison = (+)(1, 2, bison))
Notice that the cycle is represented by the circular dependency of
bison on itself.
Transformations are carried out via
postwalk functions very similar to those in MacroTools (see there for more explanation).
julia> DataFlow.prewalk(d) do v v.value isa Call && v.value == Constant(+) ? vertex(constant(-), v[2:end]...) : v end IVertex( bison = (IVertex(-))(1, 2) (*)(bison, bison))
There are also in-place variants of prewalk and postwalk, which can be used for more advanced transformations.
4 days ago