Symbolic differentiation in Tcl: reusing the Tcl parser for symbolic algebra

Kevin B. Kenny Computational Biology Laboratory, GE Global Research Center, Niskayuna, NY

Symbolic differentiation is one of the easier problems in symbolic algebra; it is often presented as a student exercise in artificial-intelligence courses. Even though it is easy, it remains useful (and often underutilized) for mathematical computations such as rootfinding, minimization and maximization of functions, and solving ordinary differential equations. The most time-consuming part of writing a symbolic differentiator, in many languages, is writing a parser for the expressions to be differentiated. Fortunately, Tcl, being an interpretive language, comes with a parser for expressions that is available at run time. While the parser is not normally exported to scripts, the parser interface that the instrumentor in TclPro uses allows for script access via an extension. One advantage to using the built-in parser is that the programmer can be certain that the language of expressions to be differentiated is exactly the language of expressions to be evaluated. The differentiator begins with a Tcl expression whose derivative is to be found, and the variable with respect to which it is being differentiated. The first thing that it does is to se the `parser' extension to parse the expression. It then rewrites the parse tree into a form that is suitable for evaluation as a Tcl command. For instance, the Tcl expression,
2 * sin($x) * cos($x)
would be rewritten into the Tcl command:
{operator *} \ {{operator *} \ {constant 2.} \ {{operator sin} \ {var x}}} \ {{operator cos} \ {var x}}

Various rewritings are then available by evaluating the command in various namespaces. In particular, the command:
namespace eval math::symdiff::differentiate \ [linsert $parseTree 1 $varName]
differentiates the given expression with respect to the given variable.

The result is a tree in the same form: second and higher derivatives can be obtained by the same method. The differentiator itself is fairly stupid. It includes the rules for finding the derivatives of sums, differences, products, quotients and powers. It also has the basic rules for differentiating the built-in functions, and a number of these rules also invoke common code for the Chain Rule. A typical rule, in fact an unusually complex one, is the one for the two-argument arc-tangent function:


proc {math::symdiff::differentiate::operator atan2} {var f g} { 
  set df [eval [linsert $f 1 $var]] 
  set dg [eval [linsert $g 1 $var]] 
  return [MakeQuotient \
         [MakeDifference \
	 [MakeProd $df $g] \ 
	 [MakeProd $f $dg]] \ 
	 [MakeSum \ [MakeProd $f $f] \ [MakeProd $g $g]]] 
}

Tcl 8.5 is not far from being an extremely capable system for ad-hoc mathematical calculations; extensions such as this one point the way.