ReverseDiffSource internals

All the core of the functions in the package ( differentiation, removal of neutral statements, factorization of identical calls) rely on 2 structures:

  1. The ExNode composite type that represents either:
    • a single operation (a function call)
    • an external reference (a variable that can be a parameter for derivation or a reference to a variable outside the scope of the expression)
    • a constant
ExNodes have parents which are typically the arguments of the function. Collectively they make a DAG but with several additions :
  • the order of arguments (parent nodes) is significant ( a ^ b is not the same as b ^ a)
  • there needs to be additionnal ordering information as statements not related sometimes need to execute in a specific order, this information is in the precedence field.
  1. The ExGraph composite type that stores
    • ExNodes in a vector (in the order of execution),
    • information on how to map ExNodes to variable names (used and set),
    • and optionnaly information on how to map nodes to ‘outer’ nodes. This last mapping is necessary when the ExGraph is embedded in another parent graph ( for example the inner scope of for loops is represented as a subgraph).

Showing the code graph

Starting from an expression, it is possible to have a dump of the nodes composing its equivalent graph with the (unexported) tograph() call :

ex = quote
a = 1 + x 2 * exp(-a)

end

g = ReverseDiffSource.tograph(ex)

node | symbol | ext ? | type | parents | precedence | main | value | —- | ———- | —– | ———- | ——– | ———- | —– | ————- | 1 | | | [constant] | | | 1 | (Float64) NaN | 2 | x >> | | [external] | | | :x | (Float64) NaN | 3 | a << | | [call] | 11, 1, 2 | | :call | (Float64) NaN | 4 | | | [constant] | | | 2 | (Float64) NaN | 5 | | | [call] | 8, 3 | | :call | (Float64) NaN | 6 | | | [call] | 10, 5 | | :call | (Float64) NaN | 7 | nothing << | | [call] | 9, 4, 6 | | :call | (Float64) NaN | 8 | | | [constant] | | | - | (Float64) NaN | 9 | | | [constant] | | | * | (Float64) NaN | 10 | | | [constant] | | | exp | (Float64) NaN | 11 | | | [constant] | | | + | (Float64) NaN |

Additionnaly, the plot() function (also unexported) will generate a GrapViz compatible graph description :

using GraphViz

Graph( ReverseDiffSource.plot( g ))

Should produce :

_images/test.png