Arjen Markus (7 september 2005) The other day Lars Hellström sent an email to a discussion on the Tcllib developers' list, regarding the extensibility of the [expr] command.
I found this "essay" rather illuminating, so I took the liberty of putting it in its entirety on this page. For an implementation of these ideas, see Vector spaces.
My apologies if the following is a bit long, but it concerns a matter I have often thought about, and since a neighbouring matter came up in the discussion last week I might just as well put forth my findings on the matter.
At 21.39 +0200 2005-08-30, Techentin, Robert W. wrote:
>Andreas Kupries
>> However the only extensibility hooks which are exposed are
>> math functions. Operators are whole different kettle of fish.
>> I haven't looked at the parser code, but nevertheless believe
>> that the operator priorities are hardwired.
>
>I wasn't thinking about adding new operators or priorities. Just redefining
>existing operators so that they know how to handle a new "data type." The
>BLT vector expression, for example, does different things for "double +
>double" and "double + vector." Tcl_CreateMathFunc() lets me replace the
>atan() function with one of my own cooking, and it would be nice if I could
>replace the operators as well.
>
>Of course, more complexity is always more fun. :-) If I wanted to teach
>expr to handle complex numbers, then I'd have to be able to specify
>operands and parameters that went beyond int/wide/double. Same for vectors
>and other stuff.
I'd advice *against* aiming to extend expr to handle new types (as sketched above); in a way it already tries to handle too many. A better approach would be to have a cexpr for calculating with complex numbers, a vexpr for vectors, etc.
The reason I say this is that in my opinion as a mathematician, the usual mathematical notations for operations are grossly unsuitable for the task of instructing a computer. The basic problem is that in mathematical writing the actual meaning of pretty much everything depends on the context (is e.g. * ordinary multiplication, inner product of vectors, multiplication of matrices, or what?) and the TRANslation of a FORmula to computer text generally fails to capture anything but minute traces of that context. As a consequence, there are a number of standard tricks around that are routinely employed for rediscovering that context.
The most common trick is to have a fixed standard context which everything is relative to, and this is pretty much where expr is today. In the many languages where it is a task in its own right to even store any piece of data more complicated than a double, this is of course a very natural approach. It is however fundamentally impossible to rely upon in a system that can be extended.
The most celebrated trick is polymorphism/overloading: the combination of argument types decide which of the identically named operations should be applied. Here one can furthermore distinguish between static ("compile-time") and dynamic ("run-time") variants, since the role of the programmer in specifying the context are somewhat different.
Static polymorphism is actually something one sees quite a lot in mathematical formulae; it is for example traditional to denote vectors by bold letters, matrices by upper case letters, and scalars by lower case letters; one knows Au denotes matrix-vector product because A is a "matrix letter" and u is a "vector letter". In most computer languages this takes the form of explicit type declarations for variables, so that the choice of operation implementation can be guided by the types of the operand variables. Since Tcl doesn't type-tag variables however, static polymorphism isn't much of an option for us.
What one could possibly do (and I tend to think that this is not a bad idea, but not something I particularly wish to engage in) is to introduce a little "math" language that was more powerful than that of expr, and seek to make that extendable. If a little language has variables of its own, then these can be declared with types, and static polymorphism becomes possible. If one allows several statements per "math" Tcl command, then one may find that very mathematical Tcl procedures can be written with bodies entirely in the little "math" language, so there is no need to make tight coupling between general Tcl variables and the little language variable. If the little math language is implemented by a compiled extension (it probably should be, for speed reasons), then it could have its own bytecode engine so that we wouldn't need to petition the TCT for hooks into the core engine, etc. But that isn't the kind of suggestion that was discussed above.
What remains for us is rather dynamic polymorphism, where the values of the operand determine the operation applied. This too exists in the present expr, and has its most striking appearance for "/", where for example expr 3/2 is quite different from expr 3.0/2.
Even dynamic polymorphism faces some rather obvious obstacles in a typeless language like Tcl, since there is no existing type system and no visible tagging of the values to fall back on; it is in principle necessary that the values are repeatedly examined to see if they can be seen as belonging to a particular type. Efficiency-wise this can be a great burden, but there are probably ways to minimise the effects in practice.
More problematic is that the type of a value will probably not be unique. A reasonable encoding of a complex number is as a two element list of doubles, but that is also the natural encoding of a vector in R^2, so how is {1.0 0.0}+{0.0 1.0 0.0} to be interpreted? Scalar (although complex) plus vector (automagically interpreted as "add this scalar to each vector element"), or an error because the vectors are of different lengths, or what? The ambiguities will get pretty severe once one starts combining code by different authors.
My main critique of such dynamic polymorphism is however not the above, but that it is in almost all cases stupid. I, as a programmer, typically _know_ when I write a command _exactly_ which operation I want performed (e.g., is this going to be a vector-vector or matrix-vector product?), so a programming language that doesn't allow me (or even merely discourages me) to tell the computer this certainly has a built-in flaw. That the computer guesses my intentions when I write commands interactively is nice, but in a programmatic situation it is of little use and very likely to lead to unexpected run-time errors further on. It should be avoided whenever possible.
If one has a cexpr command that is like expr but computes with complex numbers (upgrading doubles and integers whenever necessary, and preferably doesn't has a special case for integer division), then the ambiguities can be kept somewhat under control, since the author of this cexpr has taken on the task to sort the edge cases out. The same goes for a vexpr for vectors. Edge cases still exist, but they don't arise accidentally when different extensions are combined in the same interpreter, only when someone actually extends someone else's extensions.
The downside of this is that if someone has done a cexpr for complex numbers and a vexpr for real vectors then there's no automatic way of combining these features to make a cvexpr for complex vectors---instead it will be necessary to duplicate the code. Sensible resolution of ambiguous expression interpretations probably requires doing it that way, but since vectorification and complexification are mostly orthogonal one might still wish for some kind of modularisation that would make it easy to combine the two. Ideally one should be able to pick a "complex" module and a "vector" module off the shelf that would trivially combine into a "complex vector" module!
Actually, this modularity is pretty straightforward to accomplish in Tcl, if only one is prepared to give up on the traditional underspecified notation. A notation that will work well is instead a prefix notation, where one first specifies the "number system" (more properly: algebraic structure) in force, then the operation within that system, and finally the operands. Supposing that Z, Q, and C are the integers, rationals, and complex numbers respectively, one might imagine calculations such as the following (with % for prompt):
% Z * 12 5 60 % Q + 2/3 3/5 19/15 % C / 1+2i 3+4i 0.44+0.08i % Q * [Q - 2/3 3/5] 5/4 1/12
(Realistic pure Tcl implementations would probably use {2 3} and {1 2} as representations rather than 2/3 and 1+2i, but the more traditional forms of these representations here make the examples easier to understand.)
The point of having such "number system" commands is that they make it very easy to generically implement e.g. vectors. Instead of having one codebase for real vectors, another for complex vectors, etc., one can have just a single vectorspace command that constructs a vector space on top of an arbitrary base field1. To make C^2 a two-dimensional complex vector space one might say
vectorspace C^2 -scalars C -dim 2
after which the following would probably work:
% C^2 + {{1.0 0.0} {0.0 0.0}} {{0.0 0.1} {0.0 2.0}}
{1.0 0.1} {0.0 2.0}(this result being (1.0+0.1i,2.0i)); whereas to make R^3 a three-dimensional real vector space one would say
vectorspace R^3 -scalars R -dim 3
and similarly to make W an eight-dimensional rational vector space
vectorspace W -scalars Q -dim 8
etc. (Personally I more often need to define polynomials over some particular ring than vectors, but the approach is the same in both cases.) What the commands created by this vectorspace command do is simply that they pick apart the vectors they are handed as arguments into components, but rely on the specified -scalars command to implement the necessary arithmetic with these components. That way, it is straightforward to build complex vectors as vectors on top of complex numbers.
All it takes, really, is good specifications of the interfaces between the various modules. Primarily people must agree on what to call things ("+" or "plus" or "add"?). Secondarily there is the need for introspection. Sometimes a higher level operation must be implemented in different ways depending on what is available on the lower level, and then this "what is available" query must be possible to perform programmatically. But here I'm getting waaaaay ahead of things.
My basic point is that one shouldn't be too concerned about getting expr to do fancy things, since it's not a very good way to do things anyway, it just happens to be one we're very used to.
Lars Hellström
PS:
1 An algebraic structure which supports addition, subtraction, multiplication, and division of arbitrary elements (except division by zero) while satisfying the usual laws of arithmetic is known as a /field/. This is not in any way related to "vector fields", which are just a traditional name for "vector-valued function".