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 some of these ideas, see VectorSpaces.
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 field[1]. 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".