matrix implementation, was: patch for $addrow needed?

On 4/20/06, Robert Dodier <robert.dodier at gmail.com> wrote:
> > > I see your point, but the line between data structures and
> > > mathematical objects is pretty blurry, so I don't think it's
> > > practical to try to distinguish the two. A uniform policy would
> > > be easy to explain -- I am inclined to support a policy of
> > > never sharing data (or at least never appearing to share
> > > data).

Maxima language semantics are based on Lisp semantics, which treat
scalar-like things (numbers, symbols) as immutable and composite
things (lists) as mutable.  Assigment and argument-passing are by
object, not by value.

Thus, if you assign or pass a matrix or a list, you are assigning the
object handle, and modifying one modifies the other.  For example:

        L1: [2,3,4]$
        M1: matrix([1,2],[3,4])$

        L2: L1$      same list
        M2: M1$     same list
        L2[1]:10$       modifies both L1[1] and L2[1]
        L2: rest(L2)$   modifies only L2
        L1 => [10,3,4]
        L2 => [3,4]

        exch1(L1,L2):=block([olda:a[1],oldb:b[1]],a[1]:oldb,b[1]:olda,true)$
        exch1(L1,L2)$
        L1 => [3,10,4]    note effect of sharing!
        L2 => [10,4]

To have value semantics, not only every assignment, but also every
*argument passing* would require a copy (or some complicated
copy-on-write scheme).  This is sometimes called "deep copy"
semantics. This would make programming with lists prohibitively
expensive.  Even simply iterating down a list using 'rest' would
require N copies.  You could of course use subscript indexing, but
that would require N^2 time, because lists are stored as linked lists.
 (And in theory a very clever compiler could realize that the copies
weren't necessary -- though that doesn't affect the interpretive
case.)+

Of course, if you make lists immutable, value semantics are trivial. 
But then, many important programming techniques become impossible. 
You couldn't sort a list in place, for example.

So far, I've talked specifically about lists.  So one could perhaps
argue that lists are programming constructs, and matrices are
immutable mathematical constructs.  This sort of works, except that
lists are commonly used in Maxima to represent vectors and 1xn
matrices.  True, the col and row functions return matrices, not lists,
but they are the exception rather than the rule. And certainly users
seem to like the convenience of writing [1,2,3].  If you made matrices
immutable, operations like row exchange would become expensive,
requiring a complete copy.

Other languages have similar kinds of problems.  For example, Fortran
*explicitly* defines argument passage of arrays as reference, not
copy, and does not prohibit aliasing (compilers are allowed to
optimize on the assumption that argument arrays do not overlap). 
Python probably has the cleanest approach, distinguishing explicitly
between mutable objects and immutable ones, and giving them different
roles.  But that seems like too much computer-science sophistication
for a computer algebra system.

As I've said before, Maxima semantics are a mess in this area as in
many others....  Beyond the above issues, Maxima also provides arrays,
with different semantics again (for example, they don't support row
extraction).

I am not sure what the right answer is, but I hope I've shown that
"just" making everything immutable, or "just" using deep value copies
rather than reference are no better than the status quo.

              -s