Implementation Details

High-level Design

Core Functions: Static Structure

The centural data structure in autodiff are Expression and ElementaryFunction (which is the common interface shared by Add, Mul, Pow, Exp, Sin…). Expression represents a mathematical expression. It is composed of one ElementaryFunction plus two sub-Expression’s. Expression has two child class: Variable, which represents a ‘base’ variable and Constant, which represents a constant.

Core Functions: Dynamic Behavior

When a Expression’s derivative_at method is called, it will pass its sub-Expression(‘s) to the ElementaryFunction’s derivative_at method. ElementaryFunction’s derivative_at method will then compute the derivative based on chain rule. In this process, the ElementaryFunction will need the values and derivatives of the sub-Expression(s), so it will call the evaluation_at method and derivative_at method of the sub-Expression(‘s), and use the returned value to calculate the derivative. In other words, Expression and ElementaryFunctions will be calling each other recursively, until the base of this recursive process is reached.

The base of this recursive process lies in the Constant class and the Variable class. When a Constant is called to give its derivative, it returns 0. When a Variable is called to give its derivative, it checks whether itself is the variable to be taken derivative with respect of, if yes, then it returns 1.0, otherwise it returns 0.0.

On Second Order derivatives

The implementation of second order derivative is conceptually very similar to the implementation of first order derivative, except that it implements a different chain rule. The knowledge of the chain rule is encompassed within the derivative_at method of ElementaryFunction. Because all the ElementaryFunctions involves either one or two sub-Expression, the Faà di Bruno’s formula is actually much less frightening to implement than it seems in the following figure.

Core Classes

The core class of autodiff is Expression and its child classes (Variable and Constant). They share the same interface: all implements their own evaluation_at and derivative_at methods. The dunder methods of Expression is overridden so that any operation on Expression will also return an Expression. Variable and Constant inherites these dunder methods so that they have the same behavior as Expression.

Expression is composed of one ElementaryFunction and two sub-Expressions. ElementaryFunctions like Sin, Exp and Add implements the chain rule associated with the corresponding elementary function. Note that sin and exp are different from Sin and Exp. The former two are actually factory functions that returns a Expression which has Sin and Exp as its ElementaryFunction.

External Dependencies

autodiff depends on numpy. All of autodiff’s calculation is done in numpy for the efficiency and the advantage of vectorization. The optimize moduel depends on scipy for solving linear systems. The plot module depends on matplotlib for plotting.