<<TOC>>
** Rational **
*** State of the art ***
Playing with [TIP 759], I ended up with weird constructs like :
======
[foreach row $M {(
...
[foreach e $row {(
...
)}];
)}];
======
While this is working well, anybody can admit there is an over-abondance of delimiters.
*** Trying to introduce some commands as func ***
So, First, I imagined to create a Foreach mathfunc command. The code is less weird.
======proc tcl::mathfunc::Foreach {args} {
set body [lpop args]
uplevel [list foreach {*}$args ($body)]
}
...
Foreach("row", $M, {
...
Foreach("e", $L, {
...
});
});
======But this was really inneficient. Moreover, because of the neccessity to quote arguments, <<br>>
as well as the need to separate them by comas, <<br>>
I was even not totreally satisfied with the writing., wich for looks too verbose : <<br>>
''I like the command syntax minimalism on that aspect''<<br>>
Moreover, the resulting code was really inneficient, allmost one order of magnitude slower.
*** Raw Command Idea : keyword in expr, end of command at first operator ***
Then I came up to a new idea. <<br>>Expr parser is more rigid than Tcl parser. In Expr, we can have keywords. Things are not intended to change like they are in command parser. That's how I came up with this "Raw command" concept. <<br>>
What if, in expr, we define some commands as keywords ?
We can detect those keywords during the parsing and report them as a new kind of lexem : I named this new lexem code "`COMMAND"`.
Of course, the parsing of this `COMMAND lexem` can't follow the rules of the usual `SCRIPT lexem`, since there is no bracket around it. The function `Tcl_CompileTokens` would not be able to handle it as usual. So we have to define a new Token type, and to make `Tcl_CompileTokens` handling it correctly. I named this TOKEN : `TCL_TOKEN_CMD_IN_EXPR`.
To know where to stop the parsing of this command, we must make the parse function `Tcl_ParseCommand` aware of twheat kind of code it is parsing. To do so, iI defined a new nested mode : `TCL_CMD_NESTED_IN_EXPR` which has a value of 2.
I defined a new TYPE_OP char type and affect this value to every Ascii Operator in the `tclCharTypeTable` of tclParse.c, then I defined that `Tcl_ParseCommand` has to stop tohe parse wheat any char that is of type `TYPE_OP`.
Finally, the boundaries of this new command lexems type can bre defined to be from the begining of the keywords, to the char just before the next ascii operator (or end of script).
This allows to write the previous example like this :
======
foreach row $M {(
...
foreach e $row {(
...
)};
)};
======
It is as fast as using script substitution, there is no need to use comas, no need to quote arguments (except if they contain ascii operators), it is more clear.
Moreover, this has interesting consequences.
** Examples **
*** Simple example : dot product ***
Consider this proc, that is working as expected in tip-759b-tcl90 branch :
======
proc dot@ari {U V} {(
+ lindex $U 0 * lindex $V 0
+ lindex $U 1 * lindex $V 1
+ lindex $U 2 * lindex $V 2
)}
======
Let's compare with the same kind of proc taken from tcllib math package :
======
proc dot@cmd {vector1 vector2} {
set inproduct 0.0
foreach v1 $vector1 v2 $vector2 {
set inproduct [expr {$inproduct + $v1 * $v2}]
}
return $inproduct
}
======
Let's make measurments :
======
% string length [info body dot@ari]
# 99
% string length [info body dot@cmd]
# 143
% timerate {dot@ari {1 2 3} {4 5 6}}
# 0.470540 µs/# 2125215 # 2125217 #/sec 999.999 net-ms
% timerate {dot@cmd {1 2 3} {4 5 6}}
# 0.823209 µs/# 1214757 # 1214758 #/sec 999.999 net-ms
======
The code is shorter, but also faster.
Why faster ? A very expensive operation is the assignement operation. Sometimes, we are using assignement of variables, not because we need it, but because we are trying to make the code more clear. The loop has a cost, too.
On my point of view, the code of the `dot@ari` proc is cristal clear. It doesn't need to use extra variables to improve its clarity. It doesn't need loop either. That's why, it the speedest possible.
*** More complex examples : matrix product ***
In tcllib math package, the matrix product proc is using two auxilliary procs :
* the dot product proc above.
* a proc to transpose a matrix : **** Transposing a matrix ****
======
# Cmd syntax version in tcl lib:
proc transpose@cmd {matrix} {
set c -1
lmap col [lindex $matrix 0] {
incr c
lmap row $matrix {
lindex $row $c
}
}
}
# timerate {transpose@cmd {{1 2 3} {4 5 6} {7 8 9}}}
# 1.897695 µs/# 526954 # 526955 #/sec 999.998 net-ms
# TIP 759 raw commands version :
proc transpose@ari {M} {(
(lindex $M 0 0, lindex $M 1 0, lindex $M 2 0),
(lindex $M 0 1, lindex $M 1 1, lindex $M 2 1),
(lindex $M 0 2, lindex $M 1 2, lindex $M 2 2)
)}
# timerate {transpose@ari {{1 2 3} {4 5 6} {7 8 9}}}# 10.2912004655 µs/# 774441110548 # 774441110549 #/sec 999.999 net-ms
======The test shows that the raw command version is twice faster (no vars, no loops). The possiblity of removing the first level of bracket allows to get a good level of readibility.
**** Multiplying two matrixes ****
What about the multiplication itself ?
======
# cmd version from tcllib
proc matmul@cmd { mat1 mat2 } {
set newmat {}
set tmat [transpose@cmd $mat2]
foreach row1 $mat1 {
set newrow {}
foreach row2 $tmat {
lappend newrow [dot@cmd $row1 $row2]
}
lappend newmat $newrow
}
return $newmat
}
# timerate {matmul@cmd {{1 2 3} {4 5 6} {7 8 9}} {{1 2 3} {4 5 6} {7 8 9}}}
# 11.5052 µs/# 86916 # 86917.0 #/sec 999.988 net-ms
# Arithmetic proc version :
proc matmul@ari {M N} {(
T = [transpose@ari $N];
lmap i {0 1 2} {
lmap j {0 1 2} {
dot@ari [lindex $M $i] [lindex $T $j]
}
}
)}
# timerate {matmul@ari {{1 2 3} {4 5 6} {7 8 9}} {{1 2 3} {4 5 6} {7 8 9}}}# 87.36858948321 µs/# 1357128806 # 1357128806 #/sec 999.9989 net-ms
======
Once again, the proc build with arithmetic script is faster.
But aAvoiding the use of transpose and dot procs, we can even get a faster proc
======
proc matmul@ari {M N} {
lmap i {0 1 2} {
lmap j {0 1 2} {(
lindex $M $i 0 * lindex $N 0 $j + lindex $M $i 1 * lindex $N 1 $j + lindex $M $i 2 * lindex $N 2 $j
)}
}
}
# timerate {matmul@ari {{1 2 3} {4 5 6} {7 8 9}} {{1 2 3} {4 5 6} {7 8 9}}}# 4.71682552302 µs/# 212073269 # 212073269 #/sec 999.9976 net-ms
======TBut the loop as still have a cost. Avoiding any loop, we can get the fastest proc possible :
======proc matmul@ari {M N} {
list \
[list\
[(lindex $M 0 0 * lindex $N 0 0 + lindex $M 0 1 * lindex $N 1 0 + lindex $M 0 2 * lindex $N 2 0)]\
[(lindex $M 0 0 * lindex $N 0 1 + lindex $M 0 1 * lindex $N 1 1 + lindex $M 0 2 * lindex $N 2 1)]\
[(lindex $M 0 0 * lindex $N 0 2 + lindex $M 0 1 * lindex $N 1 2 + lindex $M 0 2 * lindex $N 2 2)]]\
[list\
[(lindex $M 1 0 * lindex $N 0 0 + lindex $M 1 1 * lindex $N 1 0 + lindex $M 1 2 * lindex $N 2 0)]\
[(lindex $M 1 0 * lindex $N 0 1 + lindex $M 1 1 * lindex $N 1 1 + lindex $M 1 2 * lindex $N 2 1)]\
[(lindex $M 1 0 * lindex $N 0 2 + lindex $M 1 1 * lindex $N 1 2 + lindex $M 1 2 * lindex $N 2 2)]]\
[list \
[(lindex $M 2 0 * lindex $N 0 0 + lindex $M 2 1 * lindex $N 1 0 + lindex $M 2 2 * lindex $N 2 0)]\
[(lindex $M 2 0 * lindex $N 0 1 + lindex $M 2 1 * lindex $N 1 1 + lindex $M 2 2 * lindex $N 2 1)]\
[(lindex $M 2 0 * lindex $N 0 2 + lindex $M 2 1 * lindex $N 1 2 + lindex $M 2 2 * lindex $N 2 2)]]
}
# timerate {matmul@ari {{1 2 3} {4 5 6} {7 8 9}} {{1 2 3} {4 5 6} {7 8 9}}}
# 3.369625 µs/# 296768 # 296768 #/sec 999.997 net-ms
======
The latter is a little faster that the pure arithmetic proc (see below) because TIP 759 use `list` as a mathfunc : TEBC has to resolve the name at run time, instead of using the BC instruction. I have to correct this point.
======
# pure arithmetic proc version
proc matmul@ari {M N} {( ( # First row
(lindex $M 0 0 * lindex $N 0 0 + lindex $M 0 1 * lindex $N 1 0 + lindex $M 0 2 * lindex $N 2 0),
(lindex $M 0 0 * lindex $N 0 1 + lindex $M 0 1 * lindex $N 1 1 + lindex $M 0 2 * lindex $N 2 1),
(lindex $M 0 0 * lindex $N 0 2 + lindex $M 0 1 * lindex $N 1 2 + lindex $M 0 2 * lindex $N 2 2)
), (# Second row
((lindex $M 1 0 * lindex $N 0 0 + lindex $M 1 1 * lindex $N 1 0 + lindex $M 1 2 * lindex $N 2 0),
(lindex $M 1 0 * lindex $N 0 1 + lindex $M 1 1 * lindex $N 1 1 + lindex $M 1 2 * lindex $N 2 1),
(lindex $M 1 0 * lindex $N 0 2 + lindex $M 1 1 * lindex $N 1 2 + lindex $M 1 2 * lindex $N 2 2)
),( # Third row
((lindex $M 2 0 * lindex $N 0 0 + lindex $M 2 1 * lindex $N 1 0 + lindex $M 2 2 * lindex $N 2 0),
(lindex $M 2 0 * lindex $N 0 1 + lindex $M 2 1 * lindex $N 1 1 + lindex $M 2 2 * lindex $N 2 1),
(lindex $M 2 0 * lindex $N 0 2 + lindex $M 2 1 * lindex $N 1 2 + lindex $M 2 2 * lindex $N 2 2)
)
)}
# timerate {matmul@ari {{1 2 3} {4 5 6} {7 8 9}} {{1 2 3} {4 5 6} {7 8 9}}}# 3.87888545945 µs/# 257820512 # 257820612 #/sec 999.9969 net-ms
======To be compare with its equivalent command proc :
======
proc matmul@cmd {M N} {
list \
[list \
[expr {[lindex $M 0 0] * [lindex $N 0 0] + [lindex $M 0 1] * [lindex $N 1 0] + [lindex $M 0 2] * [lindex $N 2 0]}]\
[expr {[lindex $M 0 0] * [lindex $N 0 1] + [lindex $M 0 1] * [lindex $N 1 1] + [lindex $M 0 2] * [lindex $N 2 1]}]\
[expr {[lindex $M 0 0] * [lindex $N 0 2] + [lindex $M 0 1] * [lindex $N 1 2] + [lindex $M 0 2] * [lindex $N 2 2]}]]\
[list \
[expr {[lindex $M 1 0] * [lindex $N 0 0] + [lindex $M 1 1] * [lindex $N 1 0] + [lindex $M 1 2] * [lindex $N 2 0]}]\
[expr {[lindex $M 1 0] * [lindex $N 0 1] + [lindex $M 1 1] * [lindex $N 1 1] + [lindex $M 1 2] * [lindex $N 2 1]}]\
[expr {[lindex $M 1 0] * [lindex $N 0 2] + [lindex $M 1 1] * [lindex $N 1 2] + [lindex $M 1 2] * [lindex $N 2 2]}]]\
[list \
[expr {[lindex $M 2 0] * [lindex $N 0 0] + [lindex $M 2 1] * [lindex $N 1 0] + [lindex $M 2 2] * [lindex $N 2 0]}]\
[expr {[lindex $M 2 0] * [lindex $N 0 1] + [lindex $M 2 1] * [lindex $N 1 1] + [lindex $M 2 2] * [lindex $N 2 1]}]\
[expr {[lindex $M 2 0] * [lindex $N 0 2] + [lindex $M 2 1] * [lindex $N 1 2] + [lindex $M 2 2] * [lindex $N 2 2]}]]
}
% (string length [info body matmul@cmd] - string length [info body matmul@ari])
148
# timerate {matmul@cmd {{1 2 3} {4 5 6} {7 8 9}} {{1 2 3} {4 5 6} {7 8 9}}}
3.507285 µs/# 285120 # 285120 #/sec 999.997 net-ms
======
Which is, once again, longer to write, with similar speed.
** Conclusion **Most''Raw cofmmand in arithme time,c while trsying tax'' proposes maknother way Tto call for some commands in `expr` morini-language. rThe command nablme, wmust be recognized upby tohe introduc`expr vpariablser` as a ndew looexem typse. EvThe `command ifparser` musthey arbe instruct to stop at rtheal needxt fascii oper ator. Theis allogic,ws theyo aremove athe bfigrst nlevedl forf breadcket, ibmprovility.ng But thise readability of thase a cost in speede.
Adding to this property, the native list support of [TIP 759], in the matmul@ari example above, the number of delimiters at the end of line is reduced, the maximum beeing `)),` while it has to be `]}]]\ ` in a pure command context.
The command version is so inconfortable, that most of us will just end up, in such a case, with creating variables, and using loops, even if they are not a real need for the logic, just for readibility. But this has a cost in speed.
For instance, the implementation of matrix multiplication in Tcl lib math package is about 3 times slower than the fastest implementation.
To improve readiblility, without lost of speed, tcl could be made to expand constant size loop (like lmap i {0 1 2} {...}) as a simple lists of instruction (that the programmer want Tcl engine write for him).
"Raw commands" in expr have this advantage that the code is visualy less polluted by brackets, so can remain readable, even in reasonnably long command.
<<discussion>>
What do people think about this ?