Arjen Markus (13 december 2012) Several years back I wrote TIP 309 in pursuit of a method to manipulate arithmetic expressions. The idea: go beyond ordinary arithmetic and make it possible to use complex numbers in the same way as real numbers or to implement (basic) symbolic manipulation.
The start of the Tcl novem development is an opportunity to look at it again.
Here is a simple program that shows how this can actually be used (it uses a mock-up version of the proposed command, of course):
# example.tcl --
# Example of using the proposed command s-expr
#
# s-expr --
# Mock up version of the proposed command
#
# Arguments:
# expression An - in principle - arbitrary arithmetic expression
#
# Result:
# A prefix version of the expression.
# In this mock-up just "+ $x $y"
#
proc s-expr {expression} {
return [list {+ $x $y} x y]
}
# complex --
# Namespace defining complex number operations
#
namespace eval ::complex {
variable expressions
}
# number --
# Construct a complex number
#
# Arguments:
# real Real part
# imaginary Imaginary part
#
proc ::complex::number {real imaginary} {
return [list $real $imaginary]
}
# + --
# Complex addition
#
# Arguments:
# z1 First argument
# z2 Second argument
#
# Result:
# Complex sum of the two arguments
#
proc ::complex::+ {z1 z2} {
lassign $z1 x1 y1
lassign $z2 x2 y2
return [list [expr {$x1+$x2}] [expr {$y1+$y2}]]
}
# cexpr --
# Evaluate complex arithmetic expressions
#
# Arguments:
# expression Arbitrary arithmetic expression
#
# Result:
# Value of the expression
#
proc ::complex::cexpr {expression} {
variable expressions
#
# Construct a new procedure if the expression has not been handled before
#
if { ![info exists expressions($expression)] } {
set parsed [s-expr $expression]
set prefix [lindex $parsed 0]
set vars [lrange $parsed 1 end]
set expressions($expression) 1
set upvars {}
foreach var $vars {
append upvars "upvar 2 $var $var\n"
}
proc $expression {} "$upvars$prefix"
}
$expression
}
# main --
# Test this example
#
set x [::complex::number 0 1]
set y [::complex::number 1 0]
puts "Sum of i and 1: "
puts [::complex::cexpr {$x + $y}] As you can see: the [cexpr] command behaves (superficially) in the same way as the [expr] command, but takes complex numbers in stead of ordinary reals.
My second example is automatic differentiation as a simple form of symbolic manipulation:
# example_deriv.tcl --
# Example of using the proposed command s-expr:
# automatic differentiation
#
# s-expr --
# Mock up version of the proposed command
#
# Arguments:
# expression An - in principle - arbitrary arithmetic expression
#
# Result:
# A prefix version of the expression.
# In this mock-up just "exp [* $a $x]"
#
proc s-expr {expression} {
return [list {exp [* $a $x]} a x]
}
# autodiff --
# Namespace defining automatic differentiation facilities
#
namespace eval ::autodiff {
variable expressions
}
# exp --
# Exponentiation
#
# Arguments:
# value Value and the derivative wrt the variable
#
# Result:
# Value of exp(value) and the derivative
#
proc ::autodiff::exp {value} {
lassign $value v dv
return [list [expr {exp($v)}] [expr {$dv * exp($v)}]]
}
# * --
# Multiplication
#
# Arguments:
# x First argument and the derivative wrt the variable
# y Second argument and the derivative wrt the variable
#
# Result:
# Value of x*y and the derivative
#
proc ::autodiff::* {x y} {
lassign $x x dx
lassign $y y dy
return [list [expr {$x*$y}] [expr {$dx*$y + $x*$dy}]]
}
# deriv --
# Evaluate the derivative of arithmetic expressions
# with respect to a given variable
#
# Arguments:
# dvar Name of the variable (must be a scalar)
# expression Arbitrary arithmetic expression
#
# Result:
# Derivative of the expression
#
proc ::autodiff::deriv {dvar expression} {
variable expressions
#
# Construct a new procedure if the expression has not been handled before
#
if { ![info exists expressions($expression)] } {
set parsed [s-expr $expression]
set prefix [lindex $parsed 0]
set vars [lrange $parsed 1 end]
set expressions($expression) 1
set upvars {}
foreach var $vars {
append upvars "upvar 2 $var _$var\n"
}
foreach var $vars {
if { $var ne $dvar } {
append upvars "set $var \[list \$_$var 0.0]\n"
} else {
append upvars "set $var \[list \$_$var 1.0]\n"
}
}
proc $expression {} "$upvars\nlindex \[$prefix\] 1"
}
$expression
}
# main --
# Test this example
#
set a -0.5
foreach x {0 1 2 3 4 5} {
puts "[::autodiff::deriv x {exp($a*$x)}] (expected: [expr {$a*exp($a*$x)}])"
}It occurred to me that we can use this same method to implement units.
(An example is forthcoming)
RLE (2012-12-14): Note, tcllib already contains a units package for handling units conversion.
AM (14 december 2012) That package is about converting values expressed in one unit to values expressed in a different but compatible unit. What I have in mind is:
expr { 1meter + 1kelvin } ==> error: units incompatible JBR : Operator precedence expression parser
AM (14 december 2012) Yes, I like that stuff :), but if we use Tcl's parser functionality there can be no discrepancy. Still, that parser could be an alternative (though I do want real numbers to be recognised).
Below you will find code that uses the testexprparser command from the Tcl test suite to implement the transformation from infix to prefix notation. Just a first step and not very well tested either, but for the expressions given below it works fine.
Note: I use Tcl 9.0 for this - the commands used for the Tcl test suite are stored in a loadable library, rather than in a separate shell.
# transform_expr.tcl --
# Transform an expression from infix to prefix
#
lappend env(PATH) ../tcl-novem/win
load tcltest90
proc transformExpr {expr} {
set parsed [testexprparser $expr -1]
lassign [TransformExprPriv $parsed 0] result postfix variables
return [list [string range $result 2 end-1] [lsort -unique $variables]]
}
proc TransformExprPriv {parsed insubexpr} {
#puts "-Invoking priv"
set result {}
set variables {}
set isvar 0
set current 0
set postfix ""
for {set current 0} {$current < [llength $parsed]} {incr current 3} {
lassign [lrange $parsed $current [expr {$current+2}]] mnemonic string numberComponents
#puts "$mnemonic -- $string -- $current -- $isvar"
switch -- $mnemonic {
"-" -
"" {
# Ignore these mnenomics - start and stop
}
"subexpr" {
set start [expr {$current+3}]
set end [expr {$start + 3*$numberComponents-1}]
#puts "==> [lrange $parsed $start $end]"
lassign [TransformExprPriv [lrange $parsed $start $end] 1] subexpr op newvars
append postfix ""
append result " $subexpr$op"
set variables [concat $variables $newvars]
incr current [expr {3*$numberComponents}]
continue
}
"operator" {
set postfix "]"
append result "\[$string "
}
"variable" {
set isvar 1
if { $insubexpr } {
append result "$string "
}
}
"text" {
if { $isvar } {
lappend variables $string
} else {
append result "$string "
}
set insubexpr 0
set isvar 0
}
}
#puts ">>> $result$postfix"
#puts ">>> $result"
}
#puts "-Returning from priv"
return [list $result $postfix $variables]
}
foreach expr {
{1 / (1+$a)}
sin($a)
min($a,$b,$c)+1
{max(0, min($a, 1))}
{(1+$a*$b) / (1+$a**2)}
{1+$a*$b*$c}
sin($a*$b)
{1 + $a($b)}
{$a in {1 2 3}}
{$a > 0? 1 : 0} } {
puts "Expression: $expr"
puts " Infix: [transformExpr $expr]"
}