Updated 2012-06-14 01:15:19 by RLE

Arjen Markus (14 august 2003) It was just an idea: symbolic manipulation or manipulation of mathematical expressions via Tcl. This could be handy for some mathematical playthings I have already. I did not want to spend the time and effort (a true, full-sized system would be as difficult to build as, say, hunting a snark, so I wondered if someone else had. The newsgroup did not bring any suggestions and with Google, I saw naught but implementations in Java, C++, LISP.

I pondered upon how to proceed with such system. I gave myself about an hour to actually implement and test it. Here is the result. It lacks a front-end, that will be the most difficult thing to get right. And if you run the test cases, you will see extra, unnecessary parentheses, but I did give myself one hour for the whole thing :).

As RS mentioned, the technique used in Expression parsing will come in handy for building the front-end.

AM (25 april 2005) This morning I came across a completely different technique to compute the derivative of a function - rather than manipulate the expression by which the function is computed you use the rules of differentiation and go from there (a floating-point value must become a value and "its" derivative, but it can be done easily ...). If you are interested: the page Automatic differentiation is meant to clarify the idea.
``` # symbolic.tcl --
#
#    Experiment with symbolic (algebraic) manipulation:
#    determine the derivative of an expression
#
#    Note:
#    Parsing an expression like {\$x/(1+\$x)} is not implemented yet.
#    So you will have to do that yourself:
#    {/ \$x {+ 1 \$x}}
#    Derivative w.r.t. x:
#    {1/(1+\$x)-\$x/((1+\$x)*(1+\$x)) - not the simplest form, but
#    [expr] won't mind
#

# toexpr --
#    Reconstruct the expression from the parsed and manipulated
#    form
# Arguments:
#    parse_tree     The parsed and manipulated expression
# Result:
#    String representing the expression as [expr] would take it
# Note:
#    The result is safe, as far as brackets are concerned, but
#    very conservative
#
proc toexpr { parse_tree } {
if { [llength \$parse_tree] == 1 } {
return \$parse_tree
} else {
foreach {op operand1 operand2} \$parse_tree {break}
switch -- \$op {
"umin"  {return "-[toexpr2 - \$operand1]"}
"-"     {return "[toexpr2 - \$operand1]-[toexpr2 - \$operand2]"}
"+"     {set add1 [toexpr2 + \$operand1]
}
}
}
"*"     {set mult1 [toexpr2 * \$operand1]
set mult2 [toexpr2 * \$operand2]
if { \$mult1 == "1" || \$mult1 == "(1)" } {
return \$mult2
}
if { \$mult2 == "1" || \$mult2 == "(1)" } {
return \$mult1
}
if { \$mult1 == "0"   || \$mult2 == "0"   ||
\$mult1 == "(0)" || \$mult2 == "(0)"    } {
return 0
}
return "\$mult1*\$mult2"
}
"/"     {return "[toexpr2 / \$operand1]/[toexpr2 / \$operand2]"}
"npow"  {return "pow([toexpr \$operand1],[toexpr \$operand2])"}
"atan2" {return "atan2([toexpr \$operand1],[toexpr \$operand2])"}
"hypot" {return "hypot([toexpr \$operand1],[toexpr \$operand2])"}
default {return "\$op\([toexpr \$operand1])"}
}
}
}

# toexpr2 --
#    Reconstruct the expression from the parsed and manipulated
#    form, add brackets if necessary given the context
# Arguments:
#    context        Operator context
#    parse_tree     The parsed and manipulated expression
# Result:
#    String representing the expression as [expr] would take it
#
proc toexpr2 { context parse_tree } {
if { [llength \$parse_tree] == 1 } {
return \$parse_tree
} else {
set op [lindex \$parse_tree 0]
if { \$op == \$context || [llength \$parse_tree] == 2 } {
return [toexpr \$parse_tree]
} else {
return "([toexpr \$parse_tree])"
}
}
}

# deriv --
#    Construct the derivative w.r.t. a given variable
#
# Arguments:
#    var            Name of the variable
#    parse_tree     The parsed and manipulated expression
# Result:
#    Parsed expression representing the derivative
#
proc deriv { var parse_tree } {
#
# Two cases:
# - The parse tree consists of the expression "\$var" only
# - The parse tree is more complicated, then delegate the
#   task to the subexpressions and assemble
#
if { [llength \$parse_tree] == 1 } {
if { "\$parse_tree" == "\\$\$var" } {
return 1
} else {
return 0
}
} else {
foreach {op operand1 operand2} \$parse_tree {break}
switch -- \$op {
"umin"  {return [list umin [deriv \$var \$operand1]]}
"-"     {return [list - [deriv \$var \$operand1] [deriv \$var \$operand2]]}
"+"     {return [list + [deriv \$var \$operand1] [deriv \$var \$operand2]]}
"*"     {return [list + \
[list * [deriv \$var \$operand1] \$operand2 ] \
[list * \$operand1 [deriv \$var \$operand2] ] ]}
"/"     {return [list / \
[list - \
[list * [deriv \$var \$operand1] \$operand2 ] \
[list * \$operand1 [deriv \$var \$operand2] ] ] \
[list * \$operand2 \$operand2] ]}
"npow"  {return [list * \
[list * \$operand2 [deriv \$var \$operand1]] \
[list npow \$operand1 [expr {\$operand2-1}]]   ]}
"sin"   {return [list * \
[deriv \$var \$operand1] [list cos \$operand1] ]}
"cos"   {return [list umin \
[list * \
[deriv \$var \$operand1] [list sin \$operand1]] ]}
"exp"   {return [list * \
[deriv \$var \$operand1] [list exp \$operand1] ]}

default {error "Derivative for '\$op' not implemented"}
}
}
}

#
# Simple test
#
set x {\$x}
puts "Original expression: {\$x/(1+\$x)}"
puts "Reconstructed: [toexpr {/ \$x {+ 1 \$x}}]"
puts "Derivative: [toexpr [deriv x {/ \$x {+ 1 \$x}}]]"
puts "Original expression: {sin(\$x)*exp(\$x)}"
puts "Reconstructed: [toexpr {* {sin \$x} {exp \$x}}]"
puts "Derivative: [toexpr [deriv x {* {sin \$x} {exp \$x}}]]"```

If you run this, the result is:
``` Original expression: {\$x/(1+\$x)}
Reconstructed: \$x/(1+\$x)
Derivative: (((1+\$x))-(\$x))/((1+\$x)*(1+\$x))
Original expression: {sin(\$x)*exp(\$x)}
Reconstructed: sin(\$x)*exp(\$x)
Derivative: (cos(\$x)*exp(\$x))+(sin(\$x)*exp(\$x))```

Not bad, eh? For one hour's work.

There, I have said it thrice, and what I say thrice, is true!

(Note: I just had get Lewis Carroll in there somewhere :D)