In praise of MuSimp

The MuSimp progamming language was a Lisp dialect developed in the mid 1970s by Albert Rich and David Stoutemyer of the University of Hawaii and used as the basis for the MuMath symbolic algebra system.

Unlike the other computer algebra systems of that era such as Reduce and Macsyma, MuMath was targeted at the microcomputer market which meant running in less than 64k bytes of memory. Clearly there was some loss in functionality, but MuMath managed to provide a very respectable system in that small space.

Even today, computer algebra systems are usually based around an interactive command interpreter and MuMath was no exception. One of the techniques to reduce memory requirements was to use the MuSimp command interpreter directly - avoiding the need to write another one. So MuMath was very much an extension of the underlying MuSimp.

In this article we discuss some of the characteristics of MuSimp that made this possible.

If we try and evaluate an unbound or undefined variable in a conventional Lisp (or most other languages) we can expect an error of some sort. For example, here is the dialog from David Betz's XLisp implementation:

> X
Error: The variable X is unbound.

But in MuSimp, the dialog is as follows:

? X;
@: X

Instead of an error, we get the name of the variable itself. MuSimp is giving each "undefined" variable a value that is the symbol that represents its own name. In Lisp terminology this is called "autoquoting", and that's the main semantic change from conventional Lisp that MuSimp needs to support a computer algebra system.

Now a symbolic algebra system that only supported unbound variables would not be much use, we also need to work with expressions containing such variables.

Consider the following MuSimp dialog:

? 1+X;
@: FALSE

So while MuSimp is happy to pass the symbol X to the addition function, the function itself doesn't know how to handle it so just returns FALSE. To proceed further with a computer algebra system we need to redefine addition. Fortunately as a Lisp dialect MuSimp has a ready made data type, the list, which we can used to represent expressions in a new version of addition:

FUNCTION +(A,B),
   LIST('+, A, B),
ENDFUN$
*** REDEFINED: +

? 1+X;
@: 1 + X

Of course, we've now lost the ability to actually add numbers together:

? 1+2;
@: 1 + 2

So the addition function needs to look at the type of its operands:

FUNCTION +(A,B),
   WHEN INTEGER(A) AND INTEGER(B), PLUS(A,B) EXIT,
   LIST('+, A, B),
ENDFUN$
*** REDEFINED: +

? 1+X;
@: 1 + X

? 1+2;
@: 3

This is not prefect yet:

? 1+X+2;
@: 1+X + 2

This isn't exactly wrong, but it would be nice if all the numbers could be added together. At this point, our code will start to justify the name 'computer algebra' since we'll need to take advantage of the commutative and associative rules of addition.

The next version of the function will re-order the expressions so any number is at the front. Then it becomes easier to extract and add the numeric portion of any sub-expression.

FUNCTION +(A,B),
   WHEN INTEGER(A) AND INTEGER(B), PLUS(A,B) EXIT,
   WHEN INTEGER(A) AND ATOM(B), LIST('+, A, B) EXIT,
   WHEN ATOM(A) AND INTEGER(B), LIST('+, B, A) EXIT,
   WHEN INTEGER(A) AND FIRST(B)='+ AND INTEGER(SECOND(B)), 
      LIST('+, PLUS(A, SECOND(B)), THIRD(B)) EXIT,
   WHEN FIRST(A)='+ AND INTEGER(SECOND(A)) AND INTEGER(B), 
      LIST('+, PLUS(SECOND(A), B), THIRD(A)) EXIT,
   WHEN FIRST(A)='+ AND INTEGER(SECOND(A)) AND FIRST(B)='+ AND INTEGER(SECOND(B)),
      LIST('+, PLUS(SECOND(A), SECOND(B)), LIST('+, THIRD(A), THIRD(B) )) EXIT,
   WHEN FIRST(A)='+ AND INTEGER(SECOND(A)),
      LIST('+, SECOND(A), LIST('+, THIRD(A), B)) EXIT,
   LIST('+, A, B),
ENDFUN$

This version will allow us to say:

? X + 1 + Y + 2 + Z + 3;
@: 6 + (X+Y+Z)

Hopefully its possible to see now how this could be extended to produce a 'proper' system, as was done for MuMath. Using an object orientated language would make this a bit simpler since we could use method overriding to support our extended form of addition.