Category: Programmation

… and in no way symbolic nor numerical

Symbolic differentiation is an automatic differentiation: otherwise, I don’t know what we’re talking about, except for the high school student on his hand-made exercises.

Numerical differentiation is not automatic as a technique in itself but is probably the most easily automated method. And even it becomes, in a somewhat abusive manner, an algorithmic differentiation to the coarsest grain…

Both methods are defined only by their flaws

Symbolic differentiation faces the difficulty of converting a computer program into a single mathematical expression and can lead to inefficient code. Numerical differentiation (the method of finite differences) can introduce round-off errors in the discretization process and cancellation. Both of these classical methods have problems with calculating higher derivatives, where complexity and errors increase. Finally, both of these classical methods are slow at computing partial derivatives of a function with respect to many inputs, as is needed for gradient-based optimization algorithms.

Idem

How do these flaws prevent a method from being automatic? To lead to an inefficient code is to arrive at a code!

The ideas presented should be developed further.

My conclusion: a Wikipedia entry for algorithmic differentiation

It is necessary to return the term automatic to its usual meaning: automatic does not mean algorithmic, except abusively in a special context. Algorithmic differentiation is an automatic differentiation of code. The other automatic differentiations must be presented and shown how they differ, in particular their advantages and their disadvantages, and reference must be made to a special article for algorithmic differentiation, thus avoiding this double bias: usurped equivalence with one method and relegation of the competing methods.

Wikipedia is also faulty: a search for “algorithmic differentiation” or “computational differentiation” lands back to “Automatic_differentiation”. It’s marble-graved equivalent, you’re told!

Nonetheless, the relevant scheme involving symbolic and algorithmic differentiation must be used and detailed. See button below.

C++ has the drawback of being a bit binary… in its way of processing n-ary operations that does not care about the associative intent of the programmer. Do we have to wait for a quantum compiler with non-binary states to process together the operands associated by the parentheses? 😉

The problem

Although the + and * operators are mathematically associative, C++ treats their operands 2 by 2 from left to right. Thus a+b+c+d is seen as: ((a+b)+c)+d, without there being any way of specifying that one wants a sum of four operands other than by the less expressive call of a function such as sum(a, b, c, d). Admittedly, by the classic means of expression-templates, one could arrive at the desired result, but at the cost of losing respect for parentheses. For example, if the programmer writes (a+b+c)+d, a template-expression could group the first three terms together, but eventually aggregate the fourth. Unless a static operator () is added to the C++ standard, which would operate on the result of a+b+c, there is no way to keep track of parentheses.

This is a serious problem for a programming interface, because it is important to respect the user’s expressed intention.

Proposal for C++

Let Expr be a type on which we propose the possibility of defining the following + operator:

enum ExprOperator { ..., OpSum, ... OpProduct, ...};
struct Expr { ExprOperator; std::vector<Expr> operands;};
std::vector<Expr> to_vector(Expr... ee);

Expr operator+(Expr e, Expr... ee) // <- proposition
{
    return Expr { OpSum, to_vector(e,ee...) };
}

Note that such a program gets compiled but the operator+ is taken as a binary one. The variadic argument stands for one and only one We want it to be accepted as n-ary. With this, we are able to translate (a+b+c)+d into Expr{OpSum,{Expr{OpSum,{a,b,c}}, d} respecting the original.

Of course, all variants taking const Expr& and Expr&& are possible.

Implicit conversions or operations with other types

Often, because we have an Expr variable a, we want to add a numeric type, such as 1, as in a+1 or 1+a without specifying a+Expr(1) or Expr(1)+a, which would ruin the elegance of our expression. The + binary operator conventionally makes it possible to process this. How can it be generalized to a sum of multiple operands, such as in 1+a+b or a+1+b? We propose to use the concepts by allowing to write:

Expr operator+(Expr e, auto convertible_to<Expr>... ee)

The problem is that we don’t always have an Expr type in the first position, as in the case of 1+a+b. We therefore propose that C++ interpret this definition as: multiple operands, one of which is of type Expr and the others of type convertible_to<Expr>. Perhaps a more acceptable way for compilers would be to write:

Expr operator+(auto convertible_to<Expr>... ee1, Expr e, auto convertible_to<Expr>... ee2)

in which it would be the first among the operands which is of type Expr. This possibility would be reserved for non-Boolean associative operators (+,*,…). For Boolean operators, a better proposal should be given.