\section{Return to Arrays and Functions}
Macsyma
provides a fascinating trick: arrays of functions.
Imagine an array, each
of whose elements is a function.
For example, Legendre polynomials have
an index, and an argument.
Thus we can refer to $P_{4} ( z ^{2})$.
Just as an array can
have an associated function, a function-array can have an associated
function.
Because we like to show off occasionally, and typesetting
can be done by many UNIX
Macsyma
systems, we illustrate
this feature here.
This was actually produced by saving output in a file
and running it through an alternative type-setting program, \TeX, which
is the system we are using for the rest of this material.
\begin{verbatim}
(c28) p[n](x):=ratsimp(1/(2^n*n!)*diff((x^2-1)^n,x,n));
\end{verbatim}
\setcounter{equation}{27}
\begin{equation}
p_{n} [ x ] := {\rm ratsimp} ( \frac{1} { 2 ^{n} n !}
\frac{d ^{n } } { d x ^{n} } ( x^{2} - 1) ^{n} )
\end{equation}
\begin{verbatim}
(c29) p[4];
\end{verbatim}
\begin {equation}
\lambda ( [ x ] , \frac{ 35 x ^4 - 30 x ^ 2
+ 3 } {8} )
\end{equation}
\begin{verbatim}
(c30) p[4](y+1);
\end{verbatim}
\begin {equation}
\frac{ 35 ( y + 1 ) ^4 - 30 ( y + 1 ) ^ 2 + 3 } {8}
\end{equation}
\medskip
The $\lambda$ (lambda) notation for a raw function of one
variable appears on line \verb|c29|.
This notation comes from the ``lambda-calculus''
used to describe the programming language Lisp, and illustrates the fact
that
Macsyma can talk about such structures.
You can generally ignore this fact, however.
\section{More Useful Examples}
As has been indicated earlier, procedures in
Macsyma
can be used for almost any classical
programming purposes (for example,
numerical techniques, combinatorial search, sorting)\footnote
{Although to be completely honest, Macsyma
does not provide easy access to
commercial data processing facilities.}
We have already indicated some differences from a purely numerical
language, such as FORTRAN.
We have seen that in
Macsyma
there are no required
type declarations, and floating-point numbers, while ``contagious''
in the sense that mixed-mode (floating-point + integer) is converted
to floating-point, do not
necessarily arise from certain calculations.
For example, if you type
\verb|sin(3)| to Macsyma, you will ordinarily see
\verb|sin(3)| as a response,
rather than what you might expect. If you type
\verb|sin(3.0)|
you will get a floating-point number.
To force Macsyma to produce numerical answers whenever possible,
you can set the \verb|numer| variable to \verb|true|. This
is shown in the numerical subroutine below, a Newton's method zero-finder.
This program uses Newton's method to
find a zero of the expression $exp$
which depends on the variable
$var$.
The iteration starts with $var = 0$
and terminates when $exp$, evaluated at the trial-point,
has absolute value less than
$eps$.
The derivative of
$exp$
is computed algebraically, and its value is computed at various
points as the search is being conducted:
\begin{verbatim}
(c1) newton(exp,var,x0,eps):= /* 1 */
block([xn,s,numer], /* 2 */
numer:true, /* 3 */
s:diff(exp,var), /* 4 */
xn:x0, /* 5 */
while abs(subst(xn,var,exp))> eps do
xn:xn-subst(xn,var,exp)/subst(xn,var,s),
return(xn) ) /* 8 */$
\end{verbatim}
This procedure for Newton's method uses an explicit expression
for the first argument
$exp$
(e.g.
\verb|sin(x)*erf(2*x)-%e^x|).
It is not a function name, e.g.
\verb|f|
as we used before.
The use of such an expression is straightforward and
probably the best way for a beginner.
The resulting program is
somewhat verbose, because, as illustrated in lines 6 and 7 above,
it is necessary to substitute values for variables in $exp$
and its derivative, $s$,
to get numbers.
Note the setting
of \verb|numer|
on line 3 to assure that the \verb|if| statement on line
6 would get numerical values for its test.
The rest of the procedure
is the classical Newton iteration.
The advantage of this procedure
over a purely numerical one is that it uses Macsyma's
ability to compute the derivative
of $exp$ algebraically once, before evaluating it at any
point.
Another item to observe here is the use of comments in the text of
programs which are
batched in to the system.
\verb|/* This is a comment */ |.
There are often many different ways of expressing the same computation,
and some of them may be substantially more convenient or efficient
than others.
While it may not make much of a difference in
efficiency in this case, the following revision of the
newton
procedure illustrates some techniques you may find useful
in
Macsyma.
\begin{verbatim}
(c2) newton(exp,var,x0,eps):= /* 1 */
block([ xn:x0, s:diff(exp,var), numer:true], /* 2 */
define(f(var), exp), /* 3 */
define(fprime(var),s), /* 4 */
loop, if abs(f(xn)) < eps then return(xn), /* 5 */
xn: xn - f(xn)/fprime(xn), /* 6 */
go (loop) ) /* 7 */ $
\end{verbatim}
Observe the list of local names at the beginning of the
\verb|block|,
which are initialized at the same time they are declared on line 2.
Lines 3 and 4 are interesting because they define two new functions,
\verb|f|
and
\verb|fprime|
each to have as their bodies, the values of
\verb|exp|
and \verb|s|.
You can see the Newton iteration more easily in this functional
rather than ``substitution'' notation.
As an exercise,
see if you can define an even smaller version of \verb|newton| by
using a single function for \verb|exp/diff(exp,var)|.
Let us try the version on line \verb|c2|:
\begin{verbatim}
(c3) h:expand((x-1)*(x-3)*(x-5));
3 2
(d3) x - 9 x + 23 x - 15
(c4) newton(h,x,3.5,1.0e-10);
(d4) 2.999999999994027
\end{verbatim}
You might wonder how many iterations that took.
One way is to use
the very convenient debugging feature provided by
Macsyma
which allows you to watch the assignment of values to variables.
You set the variable
\verb|setcheck| to a list of the variables you wish to watch.
(or
\verb|all|
to watch all the variables.)
\begin{verbatim}
(c5) setcheck:[xn]$
(c6) newton(h,x,3.5,1.0e-10);
xn set to 3.5
xn set to 2.923076923076923
xn set to 3.000228597554006
[*flonum:20{5%}; list:634{17%}; fixnum:43{2%}; ut:0%]
xn set to 2.999999999994027
(d6) 2.999999999994027
\end{verbatim}
(That message ``\verb|[*flonum: ...]|'' is a message from the
garbage collector, mentioned in section~\ref{sec-gc}.)
That tells us that only three iterations were needed in this case.
We claimed that two functions were defined in running this
program.
To display a function using the same syntax that
you would use to type it in, you use the \verb|grind|\footnote{When computers were
slow and programs were large, reformatting programs
took a long time.
The name of a program at MIT
to ``grind out'' LISP function definitions was \verb|grindef|.
The name
was carried over to
Macsyma.
Now, most LISP systems call this reformatting ``prettyprinting''}.
command.
\begin{verbatim}
(c7) grind(fprime);
fprime(x):=3*x^2-18*x+23$
(d7) done
\end{verbatim}
\section{Part Hacking}
An important tool for applications programs in
Macsyma
the ability to extract and test parts of expressions.
These are
used for the
definition or extension of algorithms which do
various conditional manipulation of formulas.
For example, you can write
a symbolic differentiation algorithm for simple expressions
by applying the rules below:
\begin{eqnarray}
\frac{d}{dx} x &=& 1 \\
\frac{d}{dx} y &=& 0 \\
\frac{d}{dx} (u+v) &=&\frac{du}{dx}+\frac{dv}{dx} \\
\frac{d}{dx} (uv) &=& v\frac{du}{dx}+u\frac{dv}{dx} \\1 \\
\end{eqnarray}
In describing this
differentiation program to Macsyma, we will
take the expression apart using the
\verb|part|
command, and then use the rules above to guide the manipulation.
First, we check to see if the expression is an
\verb|atom| (e.g.
number, variable).
Thus we begin our differentiation program as follows:
\begin{verbatim}
newdiff(expr,var):=
if atom(expr)=true then
(if expr=var then 1
else 0)
\end{verbatim}
This fragment implements the first two rules.
If the
\verb|if|
statement falls through to the
\verb|else|
clause,
then we have a composite expression.
We then check what its leading
operator is by selecting its zeroth ``part'' via
\verb|part(expr,0)|.
Based on its value we apply the appropriate rule.
\begin{verbatim}
else if part(expr,0)="+" then
newdiff(part(expr,1),var)
+ newdiff(part(expr,2),var)
else if part(expr,0)="*" then
part(expr,2)*newdiff(part(expr,1),var)
+ part(expr,1)*newdiff(part(expr,2),var)
else 'newdiff(expr,var)$
\end{verbatim}
Note the last clause which returns a \verb|'newdiff| form, that is, quoted.
As a result of this ``escape hatch'' when
the program doesn't know how to handle the leading operator, it will
just leave it ``undone''.
With some thought, you
should now be able to extend \verb|newdiff| to accommodate expressions including
\verb|sin|
and
\verb|cos|
as well as
sums and products with more than two terms.
(The
Macsyma
language does not at the moment have a
{\em case}
statement, which would make this particular program look better.)
Another technique which has gained momentum recently, namely ``object-oriented''
or ``data-driven'' programming provides a better approach to this task:
attach to each new operator the information needed to differentiate
that operator with respect to its arguments. See Macsyma's
property-list functions for more hints about this type
of programming(section~\ref{sec-proplist}). In fact, Macsyma's
differentiation program {\em is} largely data-driven, and you can
add new differentiation rules by using \verb|gradef| (see section~\ref{sec-gradef}).
\section {User Representation of Data}
There is no ``record'' or ``structure'' data-type ``constructor'' in
Macsyma,
but there are ways of making composite data records nevertheless.
If you have used a
language like Pascal which has such a feature, you may appreciate
its usefulness.
Modern dialects of LISP use such structures, but when
Macsyma
was first designed and initially implemented (in 1967), this was not
in widespread use.\footnote{
The lack of such structures
influenced not only the underlying implementation,
but also the user-level programming language.}
It
is natural to have to deal with collections of information in writing
programs.
For example, you might wish to develop programs to deal with interval
data, where a pair of expressions represent both a lower and an upper bound on
a formula.
One way of handling this is by making up a new ``function''
name, say \verb|bounds| and using it as though it were a record designator or
constructor,
but never associating it with an algorithm.
Thus \verb|bounds(1,x)| could
be an expression representing the ordered pair \verb|<1,x>|.
Another example would be the use of \verb|integer_vector(1,3,5,7)|
to designate a sequence (presumably of arbitrary length, in general),
of integers.
There is a built-in form in
Macsyma,
namely a ``list'', which can be used to deal with such collections.
It is part of the LISP heritage indicated earlier that there was initially
only one type of structure: lists of any length or element type in
Macsyma.
A list, when printed, looks like square-brackets
enclosing a sequence of items.
Thus you could express the bounds above
as \verb|[1,x]|.
However, if you used lists for all collections, you
would not know, on the face of it, whether \verb|[1,2]| was an instance of
\verb|bounds|
or
\verb|integer_vector|.
Macsyma
allows you to designate functions you intend to treat as lists, although
you can use a different ``header'' like
\verb|bounds| or
\verb|integer_vector|
with each different type.
Macsyma
makes available certain built-in
functions which can then be used on such list-like constructions
such as \verb|integer_vector|.
These are declared by, for example,
\verb|declare(integer_vector,list)|.
The built-in operations include
{\tt cons, append, member, endcons, map, rest}.
These are described in section~\ref{sec_listfuns}.
You can change components of such structures separately by indexing
into them numerically, or you can select from them using \verb|part|.
There are two other compound structures in
Macsyma
which we mention here, which may be useful for
collections of data: arrays and matrices.
The matrix form is useful for two-dimensional rectangular tables of
data.
The matrix data format is supported by a number of special
commands oriented toward the conventional interpretation of
matrices in mathematics: inverses, determinants, etc.
Matrices can be used for other kinds of data, but you should be
cautious about using them in a manner that is too far distant from
the conventional: in particular arithmetic operations in Macsyma,
have already been defined.
Arrays are unusual in their flexibility in
Macsyma.
They are usually treated as global tables, although they can be
declared to be
\verb|local|
to a \verb|block|; they cannot
be passed around as parameters
as is the case with matrices.
The
names of arrays may be passed from program to program, but the data
itself is not recopied, nor is it convenient to even make a copy
of the data into another array.
``Hashed'' arrays are particularly
ingenious, and have been illustrated earlier.
Functions can be associated
with arrays to provide new values for entries as they are required.
\medskip
At this point you should be able to make use of the
``Using Macsyma'' chapters following
to learn more details for representation of
new data types as you develop your application.
\section{More learning}
A true programming buff may also be interested in the macro-expansion
capabilities of Macsyma
and also its extensible syntax.
There are some system routines available for connecting menu-based
interactive routines to Macsyma programs.
Once you are comfortable in using Macsyma and have developed working
programs
you may find additional challenges in refining the user interface or
the notational conventions. If you have the time to devote to
such efforts, it will undoubtedly assist others with similar problems
to use your programs.\footnote{Of course
your first obligation is to make sure your programs are correct,
documented, and reliable. A fancy user interface rarely makes up for a
buggy program!}
Although there is a ``compilation'' facility (see section~\ref{sec-translate})
which allows users to translate
Macsyma
code into potentially faster-running code, this may not be loaded
in your system.
Since most of the time in
most programs is used by calls to LISP programs, perfecting the
compilation of your program is usually much less effective than
time spent on mathematical restructuring of
the solution method, or (in the case of primarily numerical computation),
using a numerical library routine written in a suitable language.
Linking to programs written in C or Fortran is discussed in section~\ref{sec-foreignfuns}.
\section{Maxims for the Macsyma User}
Some beginning users of algebraic manipulation systems
find that their
previous experiences with traditional programming systems do
not translate easily into algebraic programming.
\bigskip
While we cannot provide a complete education in efficient and effective
programming in Macsyma,
we have collected a few
``maxims'' in an attempt to help you with some of these ``start-up'' problems.
Algebraic manipulation is a new and different
computational approach for which prior experience with
computational methods may be misleading.
You should attempt to learn the ways in which algebraic
manipulation differs from other approaches.
For
example, consider the problem of inverting an $n \cross n$
matrix.
In numerical analysis we learn that the problem
requires on the order of $n ^{3} $ operations.
Theoreticians
will point out that for $n$ sufficiently large, one can
reduce the number of multiplications below $n ^ {3}$ to $n ^{2.8}$.
This analysis is unfortunately not relevant in dealing with matrices
with symbolic entries.
Consider the number of terms in
the determinant of the general $n \cross n$ matrix whose elements
are the symbols $a_ {i,j}$.
When the inverse is written out
in a fully expanded form, just the
determinant (a necessary part of representing
the inverse) has $n !$
terms.
It is impossible to compute this determinant in less than ``time
proportional to $n !$'' In fact,
for large $n$, it is just not feasible
to compute this form explicitly on existing computers.
The combinatorial
or exponential character that some algebraic manipulation
problems have when they are approached with an inefficient algorithm, makes for a vastly
different game from numerical computation, where the {\em size} of objects
is generally known at the onset of the calculation (e.g. 64 bits per
number), and does not increase.
Needlessly
generalizing a problem usually results in unnecessary expense.
For example, if you wish to obtain determinants
for a collection of matrices whose general
pattern of entries is represented by parametric formulas,
you might consider obtaining the determinant
of the general matrix and substituting various values for the parameters
into the
result.
This may work for matrices of low order, but
is probably a poor plan for dealing with the exponential
growth inherent in computing symbolic determinants.
It would probably
be better to substitute the parameters first, since this would
drastically reduce the cost of the determinant calculation.
Sometimes, when humans are dealing with formulas, it is
preferable to use an indeterminate, say G in a formula
which is really known to be, say, 3/5.
On the other
hand, it is likely (although not certain!) that the calculation
using 3/5 will take less time than the calculation with G.
Since the cost inherent in some computations is usually
a function
of the number of variables in the expression, it pays to reduce the
number of variables in a problem as much as possible.
You should be aware of the types of calculations which in the general
case become exponentially more expensive as the size of the input
grows linearly.
For example,
many matrix calculations with symbolic
entries, repeated differentiation of products or quotients, and solution of systems
of polynomial equations are some of the calculations which can get
very costly as the problems increase incrementally.
You should anticipate a certain amount of trial-and-error in calculations.
Just as in other problem-solving activities,
often the first technique that comes to mind is not the best.
While it
occasionally happens that brute force carries the day, cleverness in computing
can be as important as cleverness in hand calculations.
It is natural, during hand calculations, to apply critical simplificiations
or substitutions in computations.
These simplifications include
collecting terms selectively or striking out terms which do not ultimately
contribute to the final answer because of physical interpretations.
Computer algorithms which do not incorporate these same tricks may bog down
surprisingly soon.
Thinking about these shortcuts may be important.
In fact,
it is one of the more
rewarding aspects of computer algebra systems that they give the problem solver
an opportunity to organize, encapsulate and distribute
a particularly clever piece of mathematical manipulation.
Try to reduce your problem so that it can be performed in a simpler domain.
For example, if your problem appears to involve trigonometric functions, logs,
exponentials, etc.
see if you can reduce it to a rational function (ratio of
polynomials) problem.
If it appears to be a rational function, see if you can, by substitutions,
make it into a polynomial problem, or a truncated power-series problem.
If it appears to be a problem involving rational numbers, consider the use of
floating-point numbers as an alternative, if the growth in the size of numbers
presents difficulties, and absolute accuracy is a luxury.
There are other special data forms that are especially efficient.
In a number
of areas of investigation it pays to convert all expressions to the internal rational form
(using \verb|rat|) or into Poisson-series form (using \verb|intopois|) to
avoid the overhead the the general representation.
The price you may
pay here is that the structure of the formulas may be significantly different
from those you began with: The canonical transformations used by these
representations drastically re-order, expand, and modify the original expressions.
Sometimes someone else has already started on your problem.
You should look through the ``\verb|share|'' directory programs available to see
if there are contributed packages that might be of use either as subroutines or as
models for programming. These are described (perhaps somewhat inaccurately
as most have not been reviewed adequately) in documentation and in
documentation files in the directory ``\verb|/usr/mac/share|''.
You should also consider writing programs that
you develop in solving your problems in a form suitable for sharing with
others.
Pattern matching allows you to ``tune'' the system simplifier to your
application, and develop rule-replacement programs.
Learning to use
the pattern-matching facilities effectively is a nontrivial task.
Nevertheless
if you have a fairly complex problem involving the recognition and application
of identities, you should consider making an effort to use these facilities.
In recent years, advocates of ``rule-based expert systems'' have claimed
that this type of formalism can or should be used to incorporate varied types of
knowledge.
Algebraic manipulation programs have depended on pattern matching
since at least 1961, for some of their power.
\medskip
Finally, we would like to point out that algebraic manipulation systems,
in spite of their pitfalls, can be of major assistance in solving difficult
problems.
If you are willing to invest some time in learning, there may be
enormous benefits in using such a system.
We think it is unfortunate that
some users reserve
Macsyma
for difficult problems.
Those of us who have grown up with
Macsyma
near at hand find it of great use in routine computations as well.
\bigskip
Many hands and minds have contributed to Macsyma, in developing
it as a research program, and tuning it for use by others.
We have enjoyed constructing
Macsyma and we hope that you will enjoy using it.
We hope you will consider
contributing to program libraries at your local installation and at
other sites.
\bigskip
Richard Fateman
University of California, Berkeley
(Last revision 7/86)
\end{document}