Error propagation: Single variable case

For the case where $f$ is a function of a single measurable $x$, the right hand side of Eq. 1 can be evaluated as follows. Each leaf of the parsing tree will either be (1) a constant, (2) a variable, or (3) another sub-tree representing a sub-expression. The derivatives can be computed by the repeated application of the derivative chain rule. Starting from the bottom of the tree, a value of $1$ is pushed on the Derivative Stack (DS) (equivalent of putting $\partial x / \partial x$ on the stack) for every leaf of the tree (which, at the bottom, correspond to the symbols from the symbol table or constants). The nodes of a tree corresponds to one of the arithmetic operators ('+', '-', '/', '*', '^', and '**') or built-in functions, which are implemented as function calls. These functions push the result of the operations on the VMS while the corresponding partial derivatives are pushed on the DS.

The final result and the error propagation will in general use the values from both the stacks (the VMS and the DS). E.g. for $f(x)=\sin(x)*\cos(x)$, when the execution reaches the node for the '$*$' operator, the VMS will have two values, namely $\sin(x)$ and $\cos(x)$. The DS also has two values, namely the two derivatives $\partial \sin(x) / \partial x = \cos(x)$ and $\partial \cos(x) / \partial x = -\sin(x)$. The value of $f$ is pushed on the VMS, and its derivate ( $\partial \sin(x) / \partial x * \cos(x) + \sin(x) * \partial \cos(x) / \partial x$), computed using both the stacks, pushed on the DS. The '=' operator rule finally takes the value from the DS, and compute the right hand side of Eq. 1.

An arbitrary expression composed of user defined variables or built-in functions, will itself be represented as a sub-tree. Hence, applying the above algorithm recursively, case (3) above (a sub-expression) will also be correctly handled.

Example

Figure: The parsing tree for the expression $f(x)=\sin(x)*\cos(x) + \sin(\cos(x))$

Let $f(x)=\sin(x)*\cos(x) + \sin(\cos(x))$ (this includes three sub-expressions one of which is a functional), represented as a tree in Fig. 1. A value of $1$ is pushed on the DS whenever a symbol from the symbol-table is pushed on the VMS. When branch 1 in the above tree is reduced, a call to the built-in function $\sin$ pops a value from the VMS (which is $x$) and a value from the DS (say $dx$, which is $1$). It then pushes the value of $\sin(x)$ on the VMS and a value of $dx*\partial \sin(x) / \partial x = 1*\cos(x)$ on the DS. Similar operations are done for evaluating $\cos(x)$. When the execution reaches node 2, the VMS has the values $\sin(x)$ (L) and $\cos(x)$ (R) and the DS has $\cos(x)$ (dL) and $-\sin(x)$ (dR). Since '$*$' is a binary operator, when node 2 is reduced, two values each from the VMS and the DS are poped. The multiplication operator then pushes L*R= $\sin(x)*\cos(x)$ on the VMS while L*dR + R*dL= $\cos^2(x)-\sin^2(x)$ is pushed on the DS (note that this uses values from the DS as well as from the VMS). Both the stacks now have one value each - VMS the value of the sub-expression $\sin(x)*\cos(x)$ and the DS the value of the derivative of this sub-expression.

Next, branch 3 is evaluated. Again, $1$ and $x$ are pushed on the DS and the VMS respectively. A call to $\cos$ compute the derivative of $\cos(x)$ (namely, $-\sin(x)$) and multiplies it by the top of the DS (which is $1$). When call for $\sin$ is made, its argument ($\cos(x)$) and the derivative of the argument are on the DS and VMS respectively. A value from the VMS and DS each (say L=$\cos(x)$ and dL =$-\sin(x)$) respectively) are poped. $\sin(L)=\sin(\cos(x))$ and dL $*\sin(L)=-\sin(x)*\sin(\cos(x))$ are pushed on the VMS and DS respectively. This is the equivalent of Eq. 2 for branch 3. At this stage, the two values on the VMS are the values of the two sub-expression and DS has the values of the partial derivatives of the two sub-expressions.

Reduction of the node 4 will then again invoke the rule for the derivative and the binary operator for addition: pop two values each from the VMS and DS, push the result of the operator on the VMS, and the derivative (dL+dR in this case) on the DS. Top of the DS now has $\partial f / \partial x$ and the '=' operator computes Eq. 1.