~ubuntu-branches/debian/squeeze/maxima/squeeze

« back to all changes in this revision

Viewing changes to doc/maximabook/programming/prog.tex

  • Committer: Bazaar Package Importer
  • Author(s): Camm Maguire
  • Date: 2006-10-18 14:52:42 UTC
  • mto: (1.1.5 upstream)
  • mto: This revision was merged to the branch mainline in revision 4.
  • Revision ID: james.westby@ubuntu.com-20061018145242-vzyrm5hmxr8kiosf
ImportĀ upstreamĀ versionĀ 5.10.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
%-*-EMaxima-*-
2
 
\label{prog-lang}
3
 
 
4
 
This chapter assumes that readers are familiar with the basic ideas of
5
 
algebraic manipulation from Chapter~\ref{primer},
6
 
and know at least one programming language, and wish to use \Max\
7
 
for more ambitious tasks than can be handled in a few sequential
8
 
commands. If you are familiar with Pascal or Algol 60, you will probably
9
 
find this adequate as a programming background. Familiarity with Fortran
10
 
or Basic is less useful.
11
 
 
12
 
\Max's user-programming language\footnote{The system-programming language used 
13
 
for implementing \Max\, namely LISP, is quite different. If you wish to see 
14
 
how \Max\ was constructed, you need to know LISP to understand the source code.}
15
 
is designed to allow you
16
 
to define program modules or {\it functions} for algebraic manipulation.
17
 
Each module uses zero or more arguments, and returns an
18
 
algebraic expression.  Since numbers are special cases
19
 
of algebraic expressions, \Max's user-language
20
 
can be used as a numeric language too.  Because the language
21
 
is implemented as an interpreter it is usually
22
 
more general than compiler-based languages, and also
23
 
tends to be rather slow in tight inner loops of simple operations,
24
 
by comparison.
25
 
It has novel linguistic features, some of which are illustrated below.
26
 
 
27
 
\section{Some Examples}
28
 
 
29
 
{\tt f1} and {\tt f2} defined below, are versions of the {\it factorial} 
30
 
function.   Observe the punctuation
31
 
carefully.  Assignment is {\tt :}, function definition is {\tt :=}, 
32
 
statements are separated from one another by {\tt ,} (not {\it terminated}
33
 
by commas). The label {\it loop} is set off by a comma as though it
34
 
were a statement too.  We have added indentation to make the programs
35
 
conform to what you might expect, but extra spaces and tabs are optional.
36
 
There is a conditional execution statement (the {\tt if}) which has
37
 
an optional {\tt else} clause.
38
 
 
39
 
\beginmaximasession
40
 
f1(x):=if x<1 then 1 else x*f1(x-1)$
41
 
f1(5);
42
 
f2(x) := block ([temp],
43
 
                temp:1,
44
 
                while x > 1 do (
45
 
                        temp:x*temp,
46
 
                        x:x-1),   /*end while*/
47
 
                temp)$
48
 
f2(5);
49
 
\maximasession
50
 
(C1) f1(x):=if x<1 then 1 else x*f1(x-1)$
51
 
 
52
 
(C2) f1(5);
53
 
 
54
 
(D2)                                  120
55
 
(C3) f2(x) := block ([temp],
56
 
                temp:1,
57
 
                while x > 1 do (
58
 
                        temp:x*temp,
59
 
                        x:x-1),   /*end while*/
60
 
                temp)$
61
 
 
62
 
(C4) f2(5);
63
 
 
64
 
(D4)                                  120
65
 
\endmaximasession
66
 
 
67
 
Observe the simplicity of using \Max\ compared to, say, Pascal.  There is no
68
 
need to write a {\it driver} or main program
69
 
with input or output commands.  The input is provided through
70
 
function application on an argument, and the output is the displayed value.
71
 
 
72
 
Every command or function in \Max\
73
 
has a value, and may, in addition, have some side-effects, such as the
74
 
setting of variables, or the printing of messages.
75
 
 
76
 
The {\tt block}
77
 
construction illustrated above
78
 
is analogous to a procedure declaration.
79
 
The first part of it is a list of local variables, and following
80
 
that, expressions which are evaluated in order.
81
 
Certain expressions or commands make sense only within a block, not
82
 
at 
83
 
\Max's command level:
84
 
these are labels, {\tt return}
85
 
s and {\tt go}
86
 
s. The semantics of each
87
 
of these
88
 
commands conforms to the usual intuitive meaning.  If the last statement
89
 
in a {\tt block}
90
 
does not cause a transfer of control, and {\it execution
91
 
falls through the bottom}, the value returned from the 
92
 
{\tt  block}
93
 
is the value of the last expression evaluated.
94
 
 
95
 
\section{Unconventional Conditionals}
96
 
 
97
 
The next example shows a function with a side-effect, but the major
98
 
point is to illustrate some subtleties which you may not have thought
99
 
about in
100
 
conditional statements ({\tt if-then-else}
101
 
).
102
 
 
103
 
If you were asked, {\it Is A greater than B}, it would seem you could respond
104
 
either {\it yes} or {\it no}. In your conventional programming language, certainly,
105
 
that would be a reasonable assumption.  But really, wouldn't it
106
 
be appropriate in some circumstances for you to answer, {\it How should I know?}?
107
 
 
108
 
That option is preserved in \Max.  If the flag {\tt prederror}
109
 
is set to {\tt true}, the default, and if \Max\
110
 
is unable to evaluate a predicate, it signals an error, and unless
111
 
directed otherwise, returns control to the top-level
112
 
\Max\
113
 
command monitor.
114
 
However, if the {\tt prederror}
115
 
flag is {\tt false}, execution continues
116
 
to the next statement, ignoring both 
117
 
{\tt then}
118
 
and {\tt  else}
119
 
clauses!
120
 
 
121
 
This is illustrated below:
122
 
 
123
 
\beginmaximasession
124
 
test(x,y):=block([],
125
 
        if x > y then print(x, "is greater than", y)
126
 
                 else print(x, "is not greater than", y),
127
 
        return(alldone))$
128
 
test(4,3);
129
 
test(3,4);
130
 
test(y^2+1,-y);
131
 
prederror:false$
132
 
test(y^2+1,-y);
133
 
\maximasession
134
 
(C5) test(x,y):=block([],
135
 
        if x > y then print(x, "is greater than", y)
136
 
                 else print(x, "is not greater than", y),
137
 
        return(alldone))$
138
 
 
139
 
(C6) test(4,3);
140
 
 
141
 
4 is greater than 3 
142
 
(D6)                                alldone
143
 
(C7) test(3,4);
144
 
 
145
 
3 is not greater than 4 
146
 
(D7)                                alldone
147
 
(C8) test(y^2+1,-y);
148
 
 
149
 
MACSYMA was unable to evaluate the predicate:
150
 
ERREXP1
151
 
#0: test(x=y^2+1,y=-y)
152
 
 -- an error.  Quitting.  To debug this try DEBUGMODE(TRUE);)
153
 
(C9) prederror:false$
154
 
 
155
 
(C10) test(y^2+1,-y);
156
 
 
157
 
(D10)                               alldone
158
 
\endmaximasession
159
 
 
160
 
Note that no message was printed for line 
161
 
{\tt d10,}
162
 
but the return value, {\it alldone}
163
 
was displayed.
164
 
 
165
 
\section{Assumptions}
166
 
 
167
 
What do YOU think? Is $y^2 + 1 > -y$ ?  For this question to make sense,
168
 
both sides of the inequality must be in the same ordered domain.  We
169
 
do not know, offhand, whether $y$ can assume values which are matrices,
170
 
complex numbers, sets, or even programs!
171
 
 
172
 
If $y$ were known to be real, or more specifically, positive real, a program
173
 
could try some deduction.  \Max\ has some features of this nature, as 
174
 
illustrated below.
175
 
 
176
 
\beginmaximasession
177
 
assume(y>0);
178
 
test(y^2+1,-y);
179
 
\maximasession
180
 
(C11) assume(y>0);
181
 
 
182
 
(D11)                               [y > 0]
183
 
(C12) test(y^2+1,-y);
184
 
 
185
 
 2
186
 
y  + 1 is greater than - y 
187
 
(D12)                               alldone
188
 
\endmaximasession
189
 
 
190
 
If we wish
191
 
\Max\
192
 
to forget that assumption,
193
 
 
194
 
\beginmaximasession
195
 
forget(y>0);
196
 
\maximasession
197
 
(C13) forget(y>0);
198
 
 
199
 
(D13)                               [y > 0]
200
 
\endmaximasession
201
 
 
202
 
\section{Arbitrary Numbers of Parameters}
203
 
 
204
 
Ambitious packages of programs have been written by many
205
 
\Max\
206
 
users.
207
 
Sometimes the requirement that a command has a fixed number of arguments
208
 
causes discomfort\footnote{The language Pascal does not allow you to define
209
 
a function {\tt f} which can
210
 
be used with a variable number of actual parameters, although
211
 
the Pascal design includes built-in procedures with variable numbers of
212
 
arguments ({\tt write} for example).}.
213
 
It is possible to write a \Max\ program which counts the
214
 
number of arguments it is given, sets default values for others, and
215
 
does any number of clever things. A simple example is shown below. Note
216
 
the way the {\it left-hand-side} of the {\it :=} is set up.
217
 
 
218
 
\beginmaximasession
219
 
prog3([l]) := block( [],
220
 
             print ("l is bound to", l, "and l[1] is" ,l[1]),
221
 
             return(length(l)))$
222
 
prog3(a,b,c,d);
223
 
prog3(a,b);
224
 
\maximasession
225
 
(C14) prog3([l]) := block( [],
226
 
             print ("l is bound to", l, "and l[1] is" ,l[1]),
227
 
             return(length(l)))$
228
 
 
229
 
(C15) prog3(a,b,c,d);
230
 
 
231
 
l is bound to [a, b, c, d] and l[1] is a 
232
 
(D15)                                  4
233
 
(C16) prog3(a,b);
234
 
 
235
 
l is bound to [a, b] and l[1] is a 
236
 
(D16)                                  2
237
 
\endmaximasession
238
 
 
239
 
\section{Arrays}
240
 
 
241
 
Arrays are a useful data structure, and are provided in most programming languages. 
242
 
\Max\ provides arrays, but does not require that they be declared, or that
243
 
they have numeric (integer) index-sets. 
244
 
Rather than writing a program to fill up an array and then iterating
245
 
through all elements, sometimes it is easier to describe a program
246
 
to generate elements as they are called for.  Such array-associated
247
 
functions are often quite convenient.  The usual
248
 
way you set them up is to provide specific values for certain
249
 
index values, and then let others be assigned as needed.  
250
 
Note carefully the use of {\tt :=} and {\tt :}.
251
 
 
252
 
\beginmaximasession
253
 
a[4]:4*u;
254
 
a[22/7]:%pi;
255
 
a[x]:mystery;
256
 
a[h]:=cos(h);
257
 
a[3];
258
 
a[x+1];
259
 
\maximasession
260
 
(C17) a[4]:4*u;
261
 
 
262
 
(D17)                                 4 u
263
 
(C18) a[22/7]:%pi;
264
 
 
265
 
(D18)                                 %PI
266
 
(C19) a[x]:mystery;
267
 
 
268
 
(D19)                               mystery
269
 
(C20) a[h]:=cos(h);
270
 
 
271
 
(D20)                            a  := COS(h)
272
 
                                  h
273
 
(C21) a[3];
274
 
 
275
 
(D21)                               COS(3)
276
 
(C22) a[x+1];
277
 
 
278
 
(D22)                             COS(x + 1)
279
 
\endmaximasession
280
 
 
281
 
 
282
 
You might wonder what the value of $a$ is, after all this.  Most
283
 
disappointing:
284
 
 
285
 
\beginmaximasession
286
 
a;
287
 
\maximasession
288
 
(C23) a;
289
 
 
290
 
(D23)                                  a
291
 
\endmaximasession
292
 
 
293
 
The information that you are after is available this way:
294
 
 
295
 
\beginmaximasession
296
 
arrayinfo(a);
297
 
\maximasession
298
 
(C24) arrayinfo(a);
299
 
 
300
 
                                     22
301
 
(D24)              [HASHED, 1, [3], [--], [4], [x], [x + 1]]
302
 
                                     7
303
 
\endmaximasession
304
 
 
305
 
The list of information supplied indicates several aspects
306
 
of the array.  It is
307
 
{\it hashed}: uses the data-structure of a hash-table for storage
308
 
(this is a common encoding trick discussed in data structure texts).
309
 
The number of subscripts is 1. The specific indexes for which it has
310
 
recorded values are listed.  The array-associated function defined
311
 
on line
312
 
{\tt c20}
313
 
can be displayed
314
 
by {\tt dispfun}.
315
 
 
316
 
\section{Iteration}
317
 
 
318
 
{\tt For} loops provide the major iteration facility in \Max.
319
 
Three examples which illustrate variants of this are the factorial
320
 
functions below:
321
 
 
322
 
\beginmaximasession
323
 
f3(n) := block([temp],
324
 
                temp:1,
325
 
                for i:1 thru n do temp : temp*i,
326
 
                return(temp))$
327
 
f4(n) := block([temp],
328
 
                temp:1,
329
 
                for i:n step -1 thru 1 do temp : temp*i,
330
 
                return(temp))$
331
 
f5(n) := block([temp],
332
 
                temp:1,
333
 
                for i:n unless i <= 1 do (temp : temp*i , i:i-2),
334
 
                return(temp))$
335
 
\maximasession
336
 
(C25) f3(n) := block([temp],
337
 
                temp:1,
338
 
                for i:1 thru n do temp : temp*i,
339
 
                return(temp))$
340
 
 
341
 
(C26) f4(n) := block([temp],
342
 
                temp:1,
343
 
                for i:n step -1 thru 1 do temp : temp*i,
344
 
                return(temp))$
345
 
 
346
 
(C27) f5(n) := block([temp],
347
 
                temp:1,
348
 
                for i:n unless i <= 1 do (temp : temp*i , i:i-2),
349
 
                return(temp))$
350
 
 
351
 
\endmaximasession
352
 
 
353
 
Decrementing $i$ by 2 in the previous program was needed because the default
354
 
step size of 1 is added to $i$ each time through. {\tt F5}
355
 
is certainly
356
 
a perverse program.
357
 
Incidentally, {\tt return}
358
 
s from within a {\tt for}
359
 
exit from the loop, and not from
360
 
the enclosing 
361
 
{\tt block.}
362
 
It is important to
363
 
note that one can group a collection of statement to be {\it done} together
364
 
with parentheses, as illustrated in
365
 
{\tt f5.}
366
 
 
367
 
\section{Serious Business}
368
 
 
369
 
Most serious users of
370
 
\Max\
371
 
find that they are repeatedly using the same programs, and need to
372
 
save them for another day.  Some users also find they rarely get
373
 
the programs or the data quite right the first time, and would rather
374
 
type these things in to a text editor, and have
375
 
\Max\
376
 
gobble the text up from a file rather than the keyboard.
377
 
Publication quality programs require comments and other features you
378
 
are unlikely to want to type into
379
 
\Max\
380
 
interactively.
381
 
 
382
 
Some people perfect a function or get an algebraic
383
 
expression correct by typing definitions and commands into a file,
384
 
say, {\tt newstuff}, using an editor such as  {\tt vi}
385
 
or {\tt emacs}
386
 
and then within
387
 
\Max\
388
 
type {\tt batch(newstuff);}.  If your file-name has funny characters
389
 
like periods or slashes, you must use quotes. For example, {\tt batch("/usr/local/maxima/demo.begin")}.
390
 
 
391
 
\Max\
392
 
then reads the statements the file, assigning labels etc., and if there are syntax
393
 
or other errors, prompts for help from the keyboard.  If you want it
394
 
to continue on to the next line after an error, type {\tt batcon(true);}.
395
 
 
396
 
Reading very large text files of programs and data can be slow using
397
 
{\tt batch}, and if
398
 
you are not changing the text, you might prefer saving your environment
399
 
in another way.
400
 
You can use {\tt save(savedstuff,all);}
401
 
to save every named or labelled
402
 
object in a
403
 
\Max\
404
 
system, on the file 
405
 
{\tt savedstuff}
406
 
in your working directory.  
407
 
(You better have write-permission or you'll get an error message.)  Another
408
 
time you can start up from where you left off by typing
409
 
{\tt loadfile(savedstuff);}
410
 
into a fresh \Max.
411
 
You can load several saved files into a single system. Naturally if the
412
 
files contain items with identical names, there is a potential for
413
 
conflict. These will be resolved in favor of the last item read in.
414
 
 
415
 
If you want to save only some material you have produced, say only the
416
 
functions defined and the values of variables x, y, and z, you can type 
417
 
\begin{center}
418
 
{\tt save(savfunxyz,functions,x,y,z);}
419
 
\end{center}
420
 
 
421
 
A neat way to save a useful section of your environment is
422
 
to (carefully) use {\tt kill}
423
 
to remove useless
424
 
items first, and
425
 
then save {\tt all}
426
 
that is left.  Doing {\tt kill(labels,...)}
427
 
after first making sure that any useful result also has a name
428
 
other than a c or d-label is sometimes a good start.  You generally
429
 
should not save every computation, since disk space is not
430
 
infinite.
431
 
 
432
 
\section{Hardcopy}
433
 
 
434
 
If you print out the files produced by {\tt save}
435
 
to show to your
436
 
colleagues who are as yet unconvinced of the merits of
437
 
\Max\,
438
 
you will be disappointed.  While such files are {\it ASCII} character
439
 
text, they do not make easy reading for persons uninitiated in various
440
 
arcane matters.
441
 
 
442
 
What you might want to do, then, is store human-readable versions of
443
 
your output on a file.  This is especially useful if you have a
444
 
display terminal, or a slow hardcopy printer.
445
 
\Max\
446
 
provides a way of opening a file for echoing both input and output of
447
 
the system.
448
 
The command
449
 
{\tt writefile(fn);}
450
 
where fn is a filename, starts the echoing, and
451
 
{\tt closefile();}
452
 
stops the echoing.
453
 
If you want the output to be human-readable after being run through
454
 
a typesetting program (\TeX, for example), you can experiment with
455
 
the output produced by setting {\tt typeset : true}.
456
 
(Suggestion: {\tt gcprint : false} is a good idea.)
457
 
 
458
 
 
459
 
\section{Return to Arrays and Functions}
460
 
 
461
 
\Max\
462
 
provides a fascinating trick: arrays of functions. Imagine an array, each
463
 
of whose elements is a function.  For example, Legendre polynomials have
464
 
an index, and an argument.  Thus we can refer to $ P_4 ( z^2 )$.
465
 
Just as arrays can
466
 
have an associated function, function-arrays can have such an associated
467
 
function.
468
 
 
469
 
Because we like to show off occasionally, and typesetting can be done by the 
470
 
\Max\ system, we illustrate this feature here.
471
 
This was produced by saving output in a file
472
 
and running it through \TeX{}.
473
 
 
474
 
\beginmaximasession
475
 
p[n](x):=ratsimp(1/(2^n*n!)*diff((x^2-1)^n,x,n));
476
 
p[4];
477
 
p[4](y+1);
478
 
\maximatexsession
479
 
\C31.  p[n](x):=ratsimp(1/(2^n*n!)*diff((x^2-1)^n,x,n)); \\
480
 
\D31.   p_{n}(x):=\mathrm{RATSIMP}\left({{1}\over{2^{n}\*n!}}\*
481
 
 \mathrm{DIFF}\left(\left(x^{2}-1\right)^{n},\linebreak[0]x
482
 
 ,\linebreak[0]n\right)\right) \\
483
 
\C32.  p[4]; \\
484
 
\D32.   \mathrm{LAMBDA}\left(\left[ x \right] ,\linebreak[0]{{35\*x^{4}
485
 
 -30\*x^{2}+3}\over{8}}\right) \\
486
 
\C33.  p[4](y+1); \\
487
 
\D33.   {{35\*\left(y+1\right)^{4}-30\*\left(y+1\right)^{2}+3}\over{8}}
488
 
  \\
489
 
\endmaximasession
490
 
 
491
 
The {\it lambda} ($\lambda$) notation for a raw function of one
492
 
variable appears on line {\tt c29}.  This notation comes from the 
493
 
{$\lambda$-calculus} used to describe the programming language LISP, 
494
 
and illustrates the fact that \Max\
495
 
can talk about such structures. You can generally ignore this fact, however.
496
 
 
497
 
\section{More Useful Examples}
498
 
 
499
 
As has been indicated earlier, procedures in \Max\ can be used for almost any 
500
 
classical programming purposes (e.g. numerical techniques, combinatorial 
501
 
search).
502
 
We have already indicated some differences from a purely numerical
503
 
language, such as FORTRAN.  We have seen that in \Max\ there are no required
504
 
type declarations, and floating-point numbers, while {\it contagious}
505
 
in the sense that mixed-mode (floating-point + integer) is converted
506
 
to floating-point, do not
507
 
necessarily arise from certain calculations.  For example,
508
 
{\tt sin(3)} normally results in {\tt sin(3)} in \Max\,
509
 
rather than its floating-point equivalent.
510
 
{\tt sin(3.0)} will, however, return a floating-point number.
511
 
The numerical subroutine below, a Newton's method zero-finder
512
 
sets the flag {\tt numer} to {\tt true} to force \Max\
513
 
to convert most expressions free of indeterminates to numbers.  
514
 
 
515
 
This program uses Newton's method to find a zero of the expression {\tt exp}
516
 
which depends on the variable {\tt var.} The iteration starts with {\tt var=x0}
517
 
and terminates when the expression, evaluated at the trial-point,
518
 
has absolute value less than {\tt eps.} The derivative of {\tt exp}
519
 
is computed algebraically, and its value is computed at various
520
 
points as the search is being conducted:
521
 
 
522
 
\beginmaximasession
523
 
 newton(exp,var,x0,eps):=                   /* 1 */
524
 
                block([xn,s,numer],             /* 2 */
525
 
                numer:true,                     /* 3 */
526
 
                s:diff(exp,var),                /* 4 */
527
 
                xn:x0,                          /* 5 */
528
 
          while abs(subst(xn,var,exp)) >  eps do 
529
 
                xn:xn-subst(xn,var,exp)/subst(xn,var,s),
530
 
          return(xn) )                         /* 8 */$
531
 
\maximasession
532
 
(C1) newton(exp,var,x0,eps):=                   /* 1 */
533
 
                block([xn,s,numer],             /* 2 */
534
 
                numer:true,                     /* 3 */
535
 
                s:diff(exp,var),                /* 4 */
536
 
                xn:x0,                          /* 5 */
537
 
          while abs(subst(xn,var,exp)) >  eps do 
538
 
                xn:xn-subst(xn,var,exp)/subst(xn,var,s),
539
 
          return(xn) )                         /* 8 */$
540
 
 
541
 
\endmaximasession
542
 
 
543
 
This procedure for Newton's method uses an explicit expression
544
 
for the first argument {\tt exp} (e.g. {\tt sin(x)*erf(2*x)-\%e\^x}).
545
 
It is not a function name, e.g. {\tt f}
546
 
as we used before.  The use of such an expression is straightforward and
547
 
probably the best way for a beginner.  The resulting program is
548
 
somewhat verbose, because, as illustrated in lines 6 and 7 above,
549
 
it is necessary to substitute values for variables in the expression
550
 
and its derivative, {\tt s}, to get numbers.  Note the setting of {\tt numer}
551
 
on line 3 to assure that the {\tt if} statement on line 6 would get numerical 
552
 
values for its test.  The rest of the procedure is the classical Newton 
553
 
iteration.  The advantage of this procedure 
554
 
over a purely numerical one is that it takes advantage
555
 
of the ability to compute the derivative of {\tt exp}
556
 
algebraically and automatically, once, before evaluating it at any point.
557
 
 
558
 
Another item to observe here is the use of comments in the text of
559
 
programs which are 
560
 
{\tt batch}
561
 
ed in to the system. {\tt  /* This is a comment */ .}
562
 
 
563
 
There are often many different ways of expressing the same computation,
564
 
and some of them may be substantially more convenient or efficient
565
 
than others.  While it may not make much of a difference in
566
 
efficiency in this case, the following revision of the
567
 
{\tt newton}
568
 
procedure illustrates some techniques you may find useful
569
 
in
570
 
\Max.
571
 
 
572
 
\beginmaximasession
573
 
newton(exp,var,x0,eps):=                   /* 1 */
574
 
block([ xn:x0, s:diff(exp,var), numer:true],    /* 2 */
575
 
        define(f(var), exp),                    /* 3 */
576
 
        define(fprime(var),s),                  /* 4 */
577
 
  loop, if abs(f(xn)) < eps then return(xn),    /* 5 */
578
 
        xn: xn - f(xn)/fprime(xn),              /* 6 */
579
 
        go (loop) )                             /* 7 */ $
580
 
\maximasession
581
 
(C2) newton(exp,var,x0,eps):=                   /* 1 */
582
 
block([ xn:x0, s:diff(exp,var), numer:true],    /* 2 */
583
 
        define(f(var), exp),                    /* 3 */
584
 
        define(fprime(var),s),                  /* 4 */
585
 
  loop, if abs(f(xn)) < eps then return(xn),    /* 5 */
586
 
        xn: xn - f(xn)/fprime(xn),              /* 6 */
587
 
        go (loop) )                             /* 7 */ $
588
 
 
589
 
\endmaximasession
590
 
 
591
 
Observe the list of local names at the beginning of the 
592
 
{\tt block,}
593
 
which are initialized at the same time they are declared on line 2.
594
 
Lines 3 and 4 are interesting because they define two new functions,
595
 
{\tt f}
596
 
and 
597
 
{\tt fprime}
598
 
each to have as their bodies, the values of
599
 
{\tt exp}
600
 
and {\tt s}.
601
 
The Newton iteration is more easily observed in functional
602
 
rather than {\it substitution} notation.
603
 
An even smaller version of {\tt newton}
604
 
could be defined by
605
 
using a single function for {\tt exp/diff(exp,var)}.
606
 
 
607
 
Let us try this last function:
608
 
 
609
 
\beginmaximasession
610
 
h:expand((x-1)*(x-3)*(x-5));
611
 
newton(h,x,3.5,1.0e-10);
612
 
\maximasession
613
 
(C3) h:expand((x-1)*(x-3)*(x-5));
614
 
 
615
 
                              3      2
616
 
(D3)                         x  - 9 x  + 23 x - 15
617
 
(C4) newton(h,x,3.5,1.0e-10);
618
 
 
619
 
(D4)                           2.999999999994028
620
 
\endmaximasession
621
 
 
622
 
You might wonder how many iterations that took.  One way is to use
623
 
the very convenient debugging feature provided by
624
 
\Max\
625
 
which allows you to watch the assignment of values to variables.
626
 
You set the variable
627
 
{\tt setcheck}
628
 
to a list of the variables you wish to watch. (or 
629
 
{\tt all}
630
 
to watch all the variables.)
631
 
 
632
 
\beginmaximasession
633
 
setcheck:[xn]$
634
 
newton(h,x,3.5,1.0e-10);
635
 
\maximasession
636
 
(C5) setcheck:[xn]$
637
 
 
638
 
(C6) newton(h,x,3.5,1.0e-10);
639
 
 
640
 
xn set to 3.5
641
 
xn set to 2.923076923076923
642
 
xn set to 3.000228597554008
643
 
xn set to 2.999999999994028
644
 
(D6)                           2.999999999994028
645
 
\endmaximasession
646
 
 
647
 
(That message {\tt [*flonum: ...]} is a message from the
648
 
garbage collector, mentioned in Section~\ref{gc}.)
649
 
 
650
 
That tells us that only three iterations were needed in this case.
651
 
 
652
 
We claimed that two functions were defined in running this
653
 
program.  To display a function using the same syntax that
654
 
you would use to type it in, you use the {\tt grind}\footnote{When 
655
 
computers were slow and programs were large, reformatting programs
656
 
took a long time. The name of a program at MIT
657
 
to {\it grind out} LISP function definitions was {\tt grindef}.  
658
 
The name was carried over to \Max.  Now, most LISP systems call this 
659
 
reformatting {\it prettyprinting}.} command.
660
 
 
661
 
\beginmaximasession
662
 
grind(fprime);
663
 
\maximasession
664
 
(C7) grind(fprime);
665
 
 
666
 
 
667
 
Error: cursorpos doesn't know position
668
 
Fast links are on: do (si::use-fast-links nil) for debugging
669
 
Error signalled by MACSYMA-TOP-LEVEL.
670
 
Broken at ERROR.  Type :H for Help.
671
 
\endmaximasession
672
 
 
673
 
\section{Part Hacking}
674
 
 
675
 
An important tool for applications programs in
676
 
\Max\
677
 
the ability to extract and test parts of expressions.  These are
678
 
used for the 
679
 
definition or extension of algorithms which do
680
 
various conditional manipulation of formulas.
681
 
For example, you can write
682
 
a symbolic differentiation algorithm for expressions
683
 
by applying the rules below:
684
 
$$
685
 
{d \over dx}\  x \ =\  1 \ \ \ \ \ \ \ {d \over dx}\  y \ =\  0 \ \ (y \neq x)
686
 
\eqno (1)$$
687
 
$$
688
 
{d \over dx}\  ( u + v) \ =\  {d \over dx}\  u \ +\  {d \over dx}\  v
689
 
\eqno (2)$$
690
 
$$
691
 
{d \over dx}\  ( u \cdot v) \ =\  v {d \over dx}\  u \ +\  u {d \over dx}\  v
692
 
\eqno (3)$$
693
 
 
694
 
The technique we shall consider for implementing a version of the
695
 
differentiation program is to take the expression apart using the 
696
 
{\tt part}
697
 
command, and use the rules above to guide the manipulation.
698
 
 
699
 
First, we check to see if the expression is an
700
 
atom (e.g. number, variable).
701
 
Thus we begin our differentiation program as follows:
702
 
 
703
 
\begin{verbatim}
704
 
 
705
 
newdiff(expr,var):=
706
 
        if atom(expr)=true then
707
 
                (if expr=var then 1
708
 
                             else 0)
709
 
\end{verbatim}
710
 
This fragment implements both parts of
711
 
rule 1.  If the 
712
 
{\tt if}
713
 
statement falls through to the 
714
 
{\tt else }
715
 
clause,
716
 
then we have a composite expression.  We then check what its leading
717
 
operator is by selecting its zeroth {\it part} via
718
 
{\tt part(expr,0).}
719
 
Based on its value we apply the appropriate rule.
720
 
\begin{verbatim}
721
 
        else if part(expr,0)=}+} then
722
 
             newdiff(part(expr,1),var)
723
 
                     + newdiff(part(expr,2),var)
724
 
        else if part(expr,0)=}*} then
725
 
             part(expr,2)*newdiff(part(expr,1),var)
726
 
                     + part(expr,1)*newdiff(part(expr,2),var)
727
 
        else 'newdiff(expr,var)$
728
 
 
729
 
\end{verbatim}
730
 
Note the last clause which returns a 'newdiff form, that is, quoted,
731
 
as a result when
732
 
the program doesn't know how to handle the leading operator.
733
 
With some thought, you
734
 
should now be able to extend newdiff to accommodate expressions including
735
 
{\tt sin} and {\tt cos} as well as
736
 
sums and products with more than two terms. 
737
 
(The \Max\ language does not at the moment have a {\tt case} 
738
 
\marginpar{Is this stiil true ????} statement, which would make 
739
 
this particular program look better.)
740
 
 
741
 
\section{User Representation of Data}
742
 
 
743
 
There is no {\it record} or {\it structure} data-type {\it constructor} in
744
 
\Max\,
745
 
but there is a way of doing something similar.  If you have used a
746
 
language like Pascal which has such a feature, you may appreciate
747
 
its usefulness. Modern dialects of LISP use such structures, but when
748
 
\Max\
749
 
was first designed and initially implemented (in 1967), this was not
750
 
in widespread use.  It also influenced the user-level programming language.
751
 
 
752
 
It
753
 
is natural to have to deal with collections of information in writing
754
 
programs. For example, you might wish to provide as input or output
755
 
data, a pair of expressions representing a lower and an upper bound on
756
 
a formula. One way of handling this is by making up a new {\it function}
757
 
name, say {\tt bounds}
758
 
and using it as though it were a record designator or
759
 
constructor,
760
 
but never associating it with an algorithm.  Thus {\tt bounds(1,x)}
761
 
could
762
 
be an expression representing the ordered pair $<1,{\tt x}>$.
763
 
Another example would be the use of {\tt integer\_vector(1,3,5,7)}
764
 
to designate a sequence (presumably of arbitrary length, in general),
765
 
of integers.  There is a built-in form in
766
 
\Max\,
767
 
namely a {\it list}, which can be used to deal with such collections.
768
 
It is part of the LISP heritage indicated earlier that there was initially
769
 
only one type of structure: lists of any length or element type in
770
 
\Max.
771
 
A list, when printed, looks like square-brackets
772
 
enclosing a sequence of items. Thus you could express the bounds above
773
 
as [{\tt 1,x}
774
 
]. However, if you used lists for all collections, you
775
 
would not know, on the face of it, whether [1,2] was an instance of
776
 
{\tt bounds}
777
 
or
778
 
{\tt integer\_vector.}
779
 
\Max\
780
 
allows you to designate functions you intend to treat as lists, although
781
 
you can use a different {\it header} like
782
 
{\tt bounds}
783
 
with each different type.
784
 
\Max\
785
 
makes available certain built-in
786
 
functions which can then be used on such list-like constructions
787
 
such as {\tt integer\_vector}.  These are declared by, for example,
788
 
{\tt declare(integer\_vector,list).}
789
 
The built-in operations include
790
 
{\tt cons, append, member, endcons, map, rest.}
791
 
 
792
 
\noindent {\tt list2:cons(element,list1)}
793
 
returns a (new) {\tt list2} which has the given
794
 
element inserted at the beginning of 
795
 
{\tt list1;} {\tt List1} and {\tt list2}
796
 
have a common {\it shared} tail.
797
 
 
798
 
\noindent {\tt list3:append(list1,list2)}
799
 
returns a (new) {\tt list3} which is a
800
 
combination of the two lists, sharing a common tail with list2. 
801
 
{\tt Member(element,list)}
802
 
returns true or false depending on a test
803
 
for membership.
804
 
 
805
 
\noindent {\tt Endcons(element,list)}
806
 
returns an (unshared) list where the given element has been
807
 
attached to the end of
808
 
given list
809
 
 
810
 
\noindent {\tt Map(fn,list)} returns a new list where each element
811
 
has had the function fn applied to it in turn.
812
 
 
813
 
\noindent {\tt Rest(list,n)} returns the part of the list beginning n items from
814
 
the front. 
815
 
 
816
 
These functions are parts of the fundamental repertoire of
817
 
the programming language LISP.
818
 
 
819
 
The use of list-like objects should be considered whenever you are
820
 
dealing with a collection of elements: a set of coordinates, a series
821
 
of coefficients, a system of equations, a set of solutions, etc.
822
 
 
823
 
Independent of the {\it whole list} operations above,
824
 
\Max\
825
 
has some selection and alteration operations which are available on
826
 
the same collections of data by the use of a numeric index.
827
 
If you wish to use these indexing facilities, as we will illustrate for the
828
 
notion of 
829
 
{\tt complex}
830
 
below, you {\tt declare(complex,list).}
831
 
Then, if you define a complex
832
 
number by {\tt x:complex(3,4)}
833
 
meaning that 
834
 
{\tt x}
835
 
has real part 3, and imaginary
836
 
part 4, the notation {\tt x[1]:10;}
837
 
is supported, and changes the value of
838
 
{\tt x}
839
 
to
840
 
{\tt complex(10,4).}
841
 
The declaration explains to the
842
 
\Max\
843
 
system that the data structure for
844
 
{\tt complex}
845
 
will be implemented (in effect) as a list of items, and should be decomposable
846
 
using the semantics of the
847
 
\Max\
848
 
list-handling commands.
849
 
In fact, both selection and alteration is supported, and if you set the
850
 
notation up by {\tt (real:1,imag:2)\$}
851
 
you can use the following command:
852
 
{\tt x[imag]:-x[imag]}
853
 
to change 
854
 
{\tt x}
855
 
to its complex conjugate.
856
 
 
857
 
An important caution must be observed.  When
858
 
\Max\
859
 
deals with compound structures, they are usually not recopied, and if
860
 
there are two names for the same object and the object is changed, then
861
 
both names refer to the changed object.
862
 
If {\tt x} and {\tt y} refer to the same {\tt complex} number, then changes to
863
 
{\tt x[real]} are also made to the corresponding component of {\tt y}.
864
 
If these items are to be kept separate, {\tt x:copylist(y);} will give {\tt x}
865
 
a different representation, but whose value is the same as {\tt y} 's.
866
 
You can then change their components separately.
867
 
 
868
 
\Max's built-in lists mentioned earlier, which use square-brackets, 
869
 
can be altered and selected by indexing.
870
 
 
871
 
There are two other compound structures in \Max\
872
 
which we mention here, which may be useful for
873
 
collections of data: arrays and matrices.
874
 
The matrix form is useful for two-dimensional rectangular tables of
875
 
data.  The matrix data format is supported by a number of special
876
 
commands oriented toward the conventional interpretation of
877
 
matrices in mathematics: inverses, determinants, etc.
878
 
Matrices can be used for other kinds of data, but you should be
879
 
cautious about using them in a manner that is too far distant from
880
 
the conventional: arithmetic operations in \Max\,
881
 
in particular, have already been defined.
882
 
 
883
 
Arrays are unusual in their flexibility in \Max.
884
 
They are usually treated as global tables, although they can be
885
 
declared to be local to a function; they cannot be passed around 
886
 
as parameters as is the case with matrices.  The
887
 
names of arrays may be passed from program to program, but the data
888
 
itself is not recopied, nor is it convenient to even make a copy
889
 
of the data into another array. {\it Hashed} arrays are particularly
890
 
ingenious, and have been illustrated earlier. Functions can be associated
891
 
with arrays to provide new values for entries as they are required.
892
 
 
893
 
At this point you should be able to make use of the
894
 
\Max\
895
 
manual to learn more details for representation of
896
 
new data types as you develop your application.
897
 
%.sh 1 More\ learning
898
 
 
899
 
The true programming buff may also be interested in the macro-expansion
900
 
capabilities of
901
 
\Max\
902
 
and its extensible syntax.  At this point we would discourage the use of
903
 
these facilities by novices, but encourage their use by persons willing
904
 
to experiment in providing the most versatile user-oriented packages within
905
 
the
906
 
\Max\
907
 
framework.
908
 
 
909
 
There is a {\it compilation} facility which allows users to translate
910
 
\Max\
911
 
code into potentially faster running code.  Since most of the time in
912
 
most programs is used by calls to LISP programs, this is usually ineffective.
913
 
In general, this should be avoided by novices and most experienced users, since
914
 
time spent on this is more wisely spent on mathematical restructuring of
915
 
the solution method, or (in the case of primarily numerical computation),
916
 
using a numerical library routine written in a suitable language.