\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}