Author dpsanders
Popularity
33 Stars
Updated Last
1 Year Ago
Started In
November 2020

# ReversePropagation.jl

A Julia package for reverse propagation along a syntax tree, using source-to-source transformation via Symbolics.jl.

## Basic usage: Reverse-mode automatic differentiation

The `gradient` function calculates the gradient of an expression or function with respect to given variables:

```julia> using Symbolics, ReversePropagation

julia> f( (x, y) ) = x + (x * y);

julia> vars = @variables x, y;

julia> ∇f( (1, 2) )
(3, (3, 1))```

The `gradient` function returns both the value of the function and the gradient.

## Basic usage: Forward–backward contractor (interval constraint propagation)

The forward–backward contractor corresponding to an expression takes a box and tries to exclude parts of the box that do not satisfy a constraint.

The contractor is constructed from a symbolic version of the constraint expression:

```julia> vars = @variables x, y

julia> ex = x^2 + y^2

julia> C = forward_backward_contractor(ex, vars)  # construct the contractor

julia> constraint = 0..1

julia> X = IntervalBox(-10..10, 2)

julia> C(X, constraint)```

Here the contractor corresponds to the constraint expression `x^2 + y^2`.

The result of the final call tries to exclude regions of the input box `X` that do not satisfy `x^2 + y^2 ∈ 0..1`, where `0..1` denotes the interval [0, 1]. This call returns the contracted box, as well as the value of the original function over the input box.

Parameters may be included in the expression; their symbolic expressions must be passed in when constructing the contractor, and their numerical values when executing the contraction:

```julia> @variables a

julia> ex = x^2 + a * y^2

julia> C = forward_backward_contractor(ex, vars, [a])

julia> aa = 1..1  # value of the variable `a` to use

julia> C(X, constraint, aa) == ( (-1..1, -1..1), 0..200 )```

## Tracing and transformations

The package works by tracing an input Julia function into a `Symbolics.jl` expression. It then transforms that expression into a static single-assignment (SSA) form, before finally emitting Julia code.

The unexported `gradient_code` function can be used to inspect this process:

```julia> ex = f(vars);  #  x + (x * y)

julia> code
7-element Vector{Assignment}:
Assignment(_a, x*y)
Assignment(_b, _a + x)
Assignment(_b̄, 1)
Assignment(_ā, _b̄)
Assignment(x̄, _b̄)
Assignment(x̄, x̄ + _ā*y)
Assignment(ȳ, _ā*x)```