Automatic Differentiation of IL (ADIL)

"Automatic Differentiation (AD) is a set of techniques based on the mechanical application of the chain rule to obtain derivatives of a function given as a computer program. AD exploits the fact that every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations such as additions or elementary functions such as sin(), cos(), exp(), etc. By applying the chain rule of derivative calculus repeatedly to these operations, derivatives of arbitrary order can be computed automatically, and accurate to working precision." www.wikipedia.org

Requirements:

We intend to implement an Automatic Differentiation of .NET IL methods using the existing SolidOpt infrastructure. The realization of such an algorithm should not be difficult due to the existing representations: CFG and TAC. A decompilation of IL into these intermediate code models (representations) already exists in the SolidOpt framework and this simplifies the task.

The implementation of AD at IL level makes the project relatively different from other existing AD implementations. Unlike the other existing systems that are based on SCT (Source Code Transform), in our case the dependence on the programming language is minimized. There is no need to use the OO (Operator Overload) approach, which distinguishes our project from almost all known .NET (and not only) implementations.

At the beginning we shall concentrate on partial derivatives of simple functions/methods (for example, float functions with multiple float parameters). Later we shall consider the partial derivatives of arbitrary functions (including ones with non-numeric parameters). Also, we must be able to find derivatives of functions/methods including branching algorithms and loops.

Example:

The AD by first parameter of the following method

public float f(float x, float y, float z) {
  return x*x + y*y + z*z - 1;
}

must produce

public float df_x(float x, float y, float z) {
  return 2*x;
}

For the sake of simplicity, the methods in the example are written in C# but ADIL should work with their IL code.

Expected results: The final project should fulfill the requirements, have unit testing and be ready for adoption in our mainline.

Knowledge Prerequisite: C#, AST/TAC/CFG models, Decompilation, IL, Math

More info: http://en.wikipedia.org/wiki/Automatic_differentiation, www.autodiff.org, SolidOpt - ADIL presentation

Mentor: Alexander Penev