summaryrefslogtreecommitdiff
path: root/web/reduce/rweb/appl/tools.web
blob: 8429c276c1fbe68312bf5e8ecafbda97e8c16681 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
% Copyright (c) 1991 Marcel Roelofs, University of Twente, Enschede,
% The Netherlands.
%
% $Header: tools.web,v 1.4 92/02/06 17:32:32 roelofs Exp $
%
\input specification 
\def\Version$#1Revision: #2 ${Version #2}
\def\title{TOOLS}
\font\titlefont=cmcsc10 scaled\magstep3
\font\ttitlefont=cmtt10 scaled\magstep4
\def\topofcontents{\null\vfill
\centerline{\titlefont The {\ttitlefont TOOLS} package for REDUCE}
\vskip15pt\centerline{\Version$Revision: 1.4 $}
\vskip15pt\centerline{\sc Marcel Roelofs}\vfill}

@*  Introduction. In this \.{RWEB} file we will describe some tools
which facilitate working with algebraic operators and can be seen as
rather general extensions to REDUCE. At the moment these tools
are:\medskip

\item{1.}Procedures to find one or all kernels of some specified
algebraic operators in a standard form.

\item{2.}The procedure |operator_coeff|, which is the analogue of the
standard REDUCE procedure |coeff| for kernels of operators. The
procedure |operator_coeff| is intended for expressions which are
linear with respect to kernels of some specified algebraic operators
and returns a list of these kernels, together with their coefficients.
Related to this procedure is the procedure |independent_part| which
extracts the part of an expression, not being a polynomial expression
in kernels of some operators.

\item{3.} The procedure |multi_coeff|, for finding the coefficients of
the basis elements of a polynomial ring in an arbitrary number of
variables.

\item{4.} The procedure |simp_multilinear| to simplify a multilinear
operator.

\item{5.}The procedure |linear_solve| to solve linear expressions
with respect to some specified kernel.

\item{6.}The procedure |solvable_kernels| which analyses if an
algebraic expression is linear with respect to kernels of some
specified operators and returns all those kernels for which the
coefficients do not depend on other operators.  \medskip

The ``banner line'' defined here is intended for indentification
purposes on loading. It should be changed whenever this file is
modified. System dependent changes, however, should be made in a
separate change file.

@d banner="Algebraic operator tools for REDUCE 3.4, $Revision: 1.4 $"

@ We define the following macros for clarity. The reading of the file
is done in symbolic mode.
@d change_to_symbolic_mode =symbolic@;
@d change_to_algebraic_mode =algebraic@;
@d stop_with_error(string_1,expr_1,string_2,expr_2) = @/
  msgpri(string_1,expr_1,string_2,expr_2,t) @;
@d message(string_1,expr_1,string_2,expr_2) = @/
  msgpri(string_1,expr_1,string_2,expr_2,nil) @;

@u change_to_symbolic_mode$@/
write banner$ terpri()$@/
change_to_algebraic_mode$

@ The following macros are intended as common programming idioms.
@d incr(x) = (x:=x+1)@;
@d decr(x) = (x:=x-1)@;

@*  Finding kernels of operators in standard forms. If one wants
perform a lot of automated computations on algebraic expressions
containing algebraic operators, it is very convenient to have a
procedure that extracts one or more kernels of some specified
operator(s) from these algebraic expressions automatically.  For this
purpose we will write the procedures |get_first_kernel|,
|get_all_kernels| and |get_recursive_kernels| which extract one or all
kernels from standard forms.  We have chosen to let the procedures act
on standard forms, because algebraic expressions are recursively built
up out of standard forms.  Therefore, in doing so, the searching can
be done in an easy to understand recursive manner.

A kernel of an operator looks like |a(1,2)| or |a()|, in general an
algebraic operator together with its arguments. In lisp mode these
kernels look like lists, the |car| of which is an algebraic
operator, the |cdr| being its arguments.


@ \specs |@!get_first_kernel|, |@!get_all_kernels| and |@!get_recursive_kernels|.
\descr Syntax: \descno 1.|get_first_kernel(form,oplist)|,\nl
               \descno 2.|get_all_kernels(form,oplist)|,\nl
	       \descno 3.|get_recursive_kernels(form,oplist)|. 
\descr Arguments:
   \arg |form|: standard form.
   \arg |oplist|: identifier or (algebraic or lisp) list of identifiers,
                  which should be algebraic operator(s).
\descr Result: \descno 1.
                    the first kernel of operator(s) on
                     |oplist| occuring in |form| at top level,
		     i.e.\ not occuring as argument of another
		     operator.\nl
                \descno 2.a (lisp) list of all kernels of
                     operator(s) on |oplist| occuring in |form| at
		     top level.\nl
                \descno 3.a (lisp) list of all kernels of
                     operator(s) on |oplist| ocurring in
		     |form| at any level.

@ The actual work of the procedures described above is done by
recursive procedures one level below, which examines the main variable
for the desired kernels and recursively examines the leading
coefficient and the reductum (which are also standard forms). These
recursive procedures have three arguments, the standard form involved,
the list of operators and a list of kernels found so far
(initially |nil|).

The following macro definition makes sure that the second argument
becomes a lisp list of identifiers.
@d make_oplist(op_list)=@/if null op_list then op_list else if atom
op_list then list op_list else if
car op_list='list then cdr op_list else op_list @;

@ The first procedure we want to discuss is
|get_first_kernel(form,oplist)|. It returns the first occurence of a
kernel of the specified operators occuring at top level. We can stop
examining the standard form if we encounter a domain element.

@u lisp procedure get_first_kernel(form,oplist);
gfk(form,make_oplist(oplist),nil)$@#

lisp procedure gfk(form,oplist,l);
  if l or domainp form then l 
    else gfk(red form,oplist,
              gfk(lc form,oplist,
                   if not atom x and member(car x,oplist)
                   then x @+else l))
    where x=mvar form$

@ The procedure |get_all_kernels(form,oplist)| returns a list of all kernels
of the specified operators occuring in |form| at top level.  In |gak|
we use |aconc| instead of |cons| to add new kernels to |l|. We do
this because most times we want to actually use the list obtained to
reorder the standard form and in this way the reordering can be minimized.

@u
lisp procedure get_all_kernels(form,oplist);
gak(form,make_oplist(oplist),nil)$@#

lisp procedure gak(form,oplist,l);
  if domainp form
    then l
    else gak(red form,oplist,
              gak(lc form,oplist,
                   if not atom x and member(car x,oplist) and not member(x,l)
                     then l:=aconc(l,x) @+else l))@|
      where x=mvar form$

@ The procedure |get_recursive_kernels(form,oplist)| returns a list of all
kernels of the specified operators occuring at any level in |form|
(i.e. as main variables, arguments, arguments of arguments, etc).

@u
lisp procedure get_recursive_kernels(form,oplist);
grk(form,make_oplist(oplist),nil)$@#

lisp procedure grk(form,oplist,l);
  if domainp form
  then l @+else grk(red form,oplist,
            grk(lc form,oplist,@|
                 @<Add all kernels occuring in |x| at any level@>))
    where x=mvar form$

@ We don't want to use the list obtained by |grk|
for reordering, so here new operator elements are simply added to |l| by
|cons|.
@<Add all kernels...@>=
                 if not atom x
                   then begin scalar y;
                          for each arg in cdr x do
                            if (y:=simp arg) neq 0 then
                              l:=grk(numr y,oplist,l);
                          return if member(car x,oplist) and not member(x,l)
                          then x . l @+else l end
                   else l@;

@*  Finding coefficients of operator expressions.  In REDUCE there is
an easy way to get all coefficients of an algebraic expression
regarded as polynomial expression w.r.t.\ some kernel, namely the
procedure |coeff|.  However, there is no mechanism available to get
all coefficients of an algebraic expression regarded as a linear
expression w.r.t.\ kernels of some specified operators, whereas such a
mechanism is very often needed if one wants to do automated
computations on expressions containing algebraic operators.

Therefore, in this section we will write the analogue of the procedure
|coeff| for kernels of some specified operators, the procedure
|operator_coeff|.

@
\spec |@!operator_coeff|.
  \descr Syntax:|operator_coeff(exprn,oplist)|.
  \descr Arguments:
    \arg |exprn|: algebraic expression.
    \arg |oplist|: identifier or (algebraic or lisp) list of identifiers,
                   which should be algebraic operator(s).
  \descr Result: returns an algebraic list, the first element of which
		 is the part of |exprn| being independent of
		 operator(s) on |oplist|, followed by zero or more
		 algebraic lists consisting of kernels of operators on
		 |oplist| and their coefficients in |exprn|. Here we
		 regard |exprn| to be a linear expression with respect
		 to all kernels of operator(s) on |oplist|. Before
		 the analysis, |exprn| is simplified.
  \descr Errors: stops with an error message if |exprn| is not linear with
                 respect to all kernels of operator(s) on |oplist|.
  \descr Examples: the call |operator_coeff(2*x(1)+3*y(2)+5*z(3),{x,y})| returns
                   the list \30|{5*z(3),{x(1),2},@/{y(2),3}}|, whereas
		   |operator_coeff(x(1)*x(2),x)| stops with an error message.

@ Keeping in mind the procedure |get_all_kernels| we have written
above, it is not difficult to think of how the procedure
|operator_coeff| could act: first get a list of all desired kernels
with help of |get_all_kernels| and reorder the numerator of |exprn|
w.r.t.\ this list. Once one has done so, one is sure that, in case of
linearity, all desired kernels occur as a main variable in a reduced
part of the numerator and it's a piece of cake to check the linearity
and to construct the desired list. In fact this is the way the first
version of |operator_coeff| worked. 
Unfortunately it is not the most efficient way to obtain the
desired result, since the numerator of |exprn| is scanned twice,
namely in the procedures |get_all_kernels| and |reorder|.

In the current version we will scan the expression $E$ only
once and at the same time construct a list $L$, which contains the
part of $E$ independent of operators on |oplist| together with all
kernels of operators on |oplist| and their coefficients and which is
almost ready for returning.

As in the first version scanning is performed on standard forms. The
actual version is based on the following fact: a standard form consist
of a number of standard terms $T_i$, each of which is the product of a
leading power $P_i$ and its coefficient $C_i$ which again is a
standard form. In the sequel we will assume that the switch |exp| is
|on|; this a legal assumption because otherwise |coeff|'ing and also
|operator_coeff|'ing would become rather useless. We can now find all
the kernels of operators on |oplist| and their coefficients in a
standard term $T_i$ if we distinguish between the following
situations:\medskip

\item{1.} $T_i$ is |nil|. We have to take no action.
\item{2.} $T_i$ is a domain element. In particular it is not a kernel
of one of the operators on |oplist|, hence we can add up $T_i$  to the
independent part of $L$.

\item{3.} The main variable of $P_i$ is a kernel of one of the
operators on |oplist| (the fact that |exp| is |on| assures us that
the main variable is a kernel).  If the leading degree is 1 and $C_i$
does not contain kernels of operators on |oplist|, we can update $L$,
otherwise we have to stop with an error message because the expression
is not linear w.r.t.  the operators on |oplist|.

\item{4.} The main variable of $P_i$ is not a kernel of one of the
operators on |oplist|. We can recursively examine $C_i$ for the
occurence of appropriate kernels, if we keep in mind that the
coefficients of kernels found there have to be multiplied with the
additional factor $P_i$.  \medskip

@ The actions described above are implemented in the procedure
|split_f|, which examines the leading term and recursively the
reductum.  The third argument |fact| is the standard form
representing the product of all previous factors, by which the
coefficients of kernels found in |form| have to be multiplied. Hence at
top level it has to be initialized to 1.  |kc_list| is a
dotted pair the |car| of which is the part of the expression
independent of operators on |oplist|, the |cdr| an association list of
kernels and (standard form) coefficients.  At top level it has to be
initialized to |nil . nil|.

@u
lisp procedure split_f(form,oplist,fact,kc_list);
if null form then kc_list
else if domainp form then 
  addf(multf(fact,form),
       car kc_list) . cdr kc_list
else if not atom mvar form and member(car mvar form,oplist) then 
if not ldeg form = 1 or get_first_kernel(lc form,oplist) then 
stop_with_error("SPLIT_F: expression not linear w.r.t.",
                        'list . oplist,nil,nil)
else split_f(red form,oplist,fact,
     update_kc_list(kc_list,mvar form,multf(fact,lc form)))
else split_f(red form,oplist,fact,
       split_f(lc form,oplist,
         multf(fact,!*p2f lpow form),kc_list))$

@ For convenience we will write a surrounding procedure
|split_form|, which can be called at top level and initializes the
third and fourth argument of |split_f|

@u
lisp procedure split_form(form,oplist);
split_f(form,oplist,1,nil . nil)$

@ For updating the |kc_list| as efficient as possible we
need an |assoc|-like procedure |list_assoc|. If applied to an
association list $L$, this procedure returns the remainder of $L$, the
|car| of which would be the result of |assoc| applied to $L$.

@u lisp procedure list_assoc(car_exprn,a_list);
if null a_list then a_list else if caar a_list= car_exprn then a_list
else list_assoc(car_exprn,cdr a_list)$

@ In order to update the |kc_list| we first have to find out
if the kernel w.r.t.\ which we update the list, is already occuring on
it. If so, we have to adjust its coefficient, otherwise we can |cons|
the kernel and coefficient in front of the list. Adjusting a 
coefficient is performed by using the procedures |list_assoc| and
|rplaca| in order to avoid rebuilding of the entire list. The reader
should verify that |rplaca| does not do any harm in this application,
since it is replacing a list.

@u lisp procedure update_kc_list(kc_list,kernel,coefficient);
(if rest_list then @+<<rplaca(rest_list,caar rest_list . addf(cdar
rest_list,coefficient)); kc_list>> else
car kc_list . (kernel . coefficient) . cdr kc_list) 
where rest_list=list_assoc(kernel,cdr kc_list)$

@ The procedure |operator_coeff| should be available in algebraic mode.
We will, however, not make it an ordinary lisp operator, since this
leads to unnecessary simplifications of the arguments and the result
of |operator_coeff| (this is done in the standard REDUCE procedure
|reval1|). Instead we will give |operator_coeff| the property |psopfn|
with value |operator_coeff_1|. By this declaration the arguments of
|operator_coeff| are passed to the procedure |operator_coeff_1| as one
unevaluated list and the result is returned without further
simplification. 

The procedure |operator_coeff_1| only checks for the right number of
arguments, and passes them as genuine arguments to the lisp procedure
|operator_coeff|. This means that we have access to |operator_coeff|
in both algebraic and symbolic mode with the same appearance. In
algebraic mode, however, the lisp procedure |operator_coeff| is not
directly accessible (since it is not an lisp operator) but only via
the construction described above. In symbolic mode |operator_coeff| is
called directly.

@u 
put('operator_coeff,'psopfn,'operator_coeff_1)$
@#
lisp procedure operator_coeff_1 u;
if length u neq 2 then rederr("OPERATOR_COEFF: wrong number of arguments")
else operator_coeff(car u,reval cadr u)$

@ The real work is done by the procedure |operator_coeff|, which
is quite simple: simplify the expression |exprn|, get its numerator,
and finally apply |split_form| to it. After that we have to divide all
coefficients by the denominator of |exprn| and convert the list
returned by |split_form| into a list of algebraic lists.

To simplify |exprn| we use |simp!*| instead of |simp| because |exprn|
may sometimes be an expression which hasn't been simplified before
(like an argument of some other simplification procedure), so we want
a full simplification of |exprn| including a call of |subs2|, which is
done by |simp!*|.

In order to admit the second argument of |operator_coeff| to be a
single operator as well as a list of operators we use the macro
|make_oplist| described above.

@u
lisp procedure operator_coeff(exprn,oplist);
begin scalar numr_ex,denr_ex,kc_list;
  oplist:=make_oplist(oplist);
  exprn:=simp!* exprn;numr_ex:=numr exprn;denr_ex:=denr exprn;
  kc_list:=split_form(numr_ex,oplist);
  return 'list . !*ff2a(car kc_list,denr_ex) . 
    for each kc_pair in cdr kc_list collect@|
      list('list,car kc_pair,!*ff2a(cdr kc_pair,denr_ex));
end$

@ Sometimes we are only interested in the part of an expression
independent of some operators instead of in the whole kernel
coefficient list. Of course one can apply |operator_coeff| to the
expression and get the independent part of it, but in time critical
applications it is better to have a procedure |dump_operators| that
only performs the essential actions of the procedure |split_f|,
together with surrounding procedures |independent_part| and
|independent_part_1|.

The basic ideas to get the independent part of an expression during
the scan of a standard form are exactly those underlying the procedure
|split_f|, except that updating the kernel coefficient list is
replaced by doing nothing.  Notice that we have skipped the checks for
linearity, hence |independent_part| is even more general than
|operator_coeff| in the sense that we can also get the independent
part of an expression which is not linear w.r.t.\ all kernels of the
specified operator(s).

However, we can get rid of the last argument |kc_list| of |split_f|,
since we can simply add up all independent parts using |addf|.

@u
lisp procedure dump_operators(form,oplist,fact); 
if null form then nil
else if domainp form then multf(fact,form)
else if not atom mvar form and member(car mvar form,oplist) then @|
  dump_operators(red form,oplist,fact)
else
  addf(dump_operators(red form,oplist,fact),@|
       dump_operators(lc form,oplist,multf(fact,!*p2f lpow form)))$

@ We copy the surrounding procedures without further comment.
@u
put('independent_part,'psopfn,'independent_part_1)$
@#
lisp procedure independent_part_1 u;
if length u neq 2 then rederr("INDEPENDENT_PART: wrong number of arguments")
else independent_part(car u,reval cadr u)$
@#
lisp procedure independent_part(exprn,oplist);
begin scalar numr_ex,denr_ex;
  oplist:=make_oplist(oplist);
  exprn:=simp!* exprn;@/numr_ex:=numr exprn;denr_ex:=denr exprn;
  return !*ff2a(dump_operators(numr_ex,oplist,1),denr_ex);
end$

@ The successful implementation of |operator_coeff| inspires us to
also introduce a more general version of |coeff|, namely a procedure
for finding the coefficients of basis elements of polynomial rings in
an arbitrary number of variables. Given a list |kernel_list| of
generators of such a ring, we can find all all basis elements and
their coefficients together with the independent part of a standard
form $F$ by analysing each standard term $T_i$ in $F$ in the following
way, where $P_i$ and $C_i$ have the same meaning as in the
introduction to the procedure |split_f|:\medskip

\item{1.} $T_i$ is |nil|. We have to take no action. 

\item{2.} $T_i$ is a domain element. In particular does not contain a
kernel of one of the generators on |kernel_list|, hence we can add up
$T_i$ to the independent part of $L$.

\item{3.} The main variable of $P_i$ is a kernel occuring in
|kernel_list| (again the fact that |exp| is |on| assures us that the
main variable is a kernel). Hence $T_i$ will give rise to at least one
basis element. At the time being we cannot, however, be sure about the
final form of the basis element, since $C_i$ may contain additional
factors. Therefore we will add $P_i$ to the variable |multi_power|
which is the list of powers found so far.  Here we explicitly use the
fact that the ordering of standard forms assures us that the powers of
basis elements found twice in $F$ will be stored on |multi_power| in
exactly the same order.

\item{4.} The main variable of $P_i$ is not a kernel occuring in
|kernel_list|. We can recursively examine $C_i$ for the occurence of
appropriate kernels, if we keep in mind that the coefficients of
kernels found there have to be multiplied with the additional factor
$P_i$.  \medskip

The analysis described above is implement in the procedure
|multi_split_f|.

@d update_pc_list=update_kc_list
@u
lisp procedure multi_split_f(form,kernel_list,multi_power,fact,pc_list);
if null form then pc_list
else if domainp form then 
  if multi_power then update_pc_list(pc_list,multi_power,multf(fact,form))
  else addf(multf(fact,form),car pc_list) . cdr pc_list
else multi_split_f(red form,kernel_list,multi_power,fact,
  if member(mvar form,kernel_list) then @|
    multi_split_f(lc form,kernel_list,lpow form . multi_power,fact,pc_list)
  else multi_split_f(lc form,kernel_list,multi_power,
                     multf(fact,!*p2f lpow form),pc_list))$


@ As usual |multi_power|, |fact| and |pc_list| have to initialized to
1 and |nil . nil|, respectively, at top level. Again we have a
surrounding procedure |multi_split_form| to take care of this.

@u
lisp procedure multi_split_form(form,kernel_list);
multi_split_f(form,kernel_list,nil,1,nil . nil)$

@ At algebraic level we want to have a procedure
|multi_coeff(exprn,kernel_list)| to our disposal, with |exprn| the
multivariate expression to be analysed and |kernel_list| the list
generators of the polynomial ring. The result of |multi_coeff| is a
list, the first part of which is the independent part, followed by
zero or more pairs of basis elements with their coefficients. Notice
that unlike |coeff| returns its result in a sparse way.

In order to avoid unnecessary simplification we will again use the
|psopfn| mechanism to make |multi_coeff| available in algebraic mode.
 
@u 
put('multi_coeff,'psopfn,'multi_coeff_1)$
@#
lisp procedure multi_coeff_1 u;
if length u neq 2 then rederr("MULTI_COEFF: wrong number of arguments")
else multi_coeff(car u,reval cadr u)$

@ There is no use of analysing the numerator of |exprn| if it is
not polynomial in the variables in |kernel_list|. Therefore we have to
check that the denominator of |exprn| does not depend on any of the
variables in |kernel_list|, before applying |multi_split_form| to the
numerator of |exprn|.

@u lisp procedure multi_coeff(exprn,kernel_list); 
begin scalar numr_ex,denr_ex,pc_list;
  kernel_list:=make_oplist(kernel_list);
  exprn:=simp!* exprn;@/
  numr_ex:=numr exprn;denr_ex:=denr exprn;
  for each generator in kernel_list do if depends(denr_ex,generator) 
  then stop_with_error(@|"MULTI_COEFF: expression is not polynomial w.r.t. ",
      'list . kernel_list,nil,nil);  
  pc_list:=multi_split_form(numr_ex,kernel_list);
  return 'list . !*ff2a(car pc_list,denr_ex) . 
    for each pc_pair in cdr pc_list collect@|
      list('list,convert_multi_power car pc_pair,!*ff2a(cdr pc_pair,denr_ex));
end$

@ A |multi_power| returned by |multi_split_f| is a list of standard
powers, i.e. dotted pairs, the |car| of which are leading variables, the
|cdr| leading degrees. For use in algebraic expression we have to
convert it to the proper product of powers. Of course if the leading
degree is 1, we can omit it from the result.

@u
lisp procedure convert_multi_power multi_power;
'times . for each power in multi_power collect
if cdr power=1 then car power else list('expt,car power,cdr power)$

@*  Simplifying multilinear operators. In REDUCE there is a rather
elementary construct for dealing with operators that are linear in one
argument. Using the procedures written above it is not very hard to
deal with multilinear operators, if we take the notion of linearity as
introduced above.  Therefore we will introduce multilinear operators
as a new type of operators in REDUCE by implementing a new
simplification procedure |simp_multilinear| for multilinear operators
and at the same time implement a |multilinear| statement to set up an
environment for multilinear operators.

Before we continue, let us give a more detailed description of what we
understand by multilinearity exactly. If $P$ is multilinear operator
w.r.t.\ operators $P_1,\dots,P_n$ and the result of |operator_coeff|
applied to an expression $a_k$ w.r.t.\ the operators $P_1,\dots,P_n$
is $$ a_k=f_{k,0}+\sum_{i_k=1}^{N_k} f_{k,i_k}p_{k,i_k}=
\sum_{i_k=0}^{N_k} f_{k,i_k}p_{k,i_k}\qquad\hbox{with $p_{k,0}=1$}$$
where $f_{k,0}$ is the part of $a_k$ independent of one of the
operators $P_1,\dots,P_n$ and $p_{k,i_k}$ are operator elements of one
of the operators $P_1,\dots,P_n$, then $P(a_1,\dots,a_m)$ must be
simplified to
$$P(a_1,\dots,a_m)=\sum_{i_1=0}^{N_1}\cdots\sum_{i_m=0}^{N_m}
f_{1,i_1}\cdots f_{m,i_m} P(p_{1,i_1},\dots,p_{m,i_m})$$ To give an
example, suppose that \\{wedge} is an operator representing the
exterior multiplication of differential geometry and suppose that we
have declared \\{wedge} to be multilinear w.r.t.\ to \\{wedge} and $d$,
then $\\{wedge}(x+f(1)+d(1),wedge(d(1),d(2)))$ will be simplified to
$(x+f(1))*\\{wedge}(1,wedge(d(1),d(2)))+\\{wedge}(d(1),\\{wedge}(d(1),d(2)))$
where the components have to be simplified separately to take account
for any other properties of exterior multiplication.

@ The first step of simplifying a multilinear operator is splitting up
its arguments. We can do this by applying |split_form| to the
numerators of all arguments and at the same time keep track of the
product of the denominators of all arguments, since the final result
of the simplification has to be divided by this product.

The actions necessary for splitting the arguments and keeping track of
the denominators are implemented in the procedure |split_arguments|.
The result (and third argument) |splitted_list| of |split_arguments|
is a dotted pair, the |car| of which is the product of all
denominators as a standard form, the |cdr| being the list of results
of |split_form| applied to the numerator of all arguments in reverse
order.  |split_arguments| applied to a list of arguments |arg_list|,
processes the first argument by updating the product of denominators
and |cons|'ing the result of |split_form| applied to the numerator of it
in front of the list of splitted arguments, and recursively splits the
rest of the arguments. Hence at top level |splitted_list| has to be
initialized to |1 . nil|.

The procedure |split_arguments| is normally called from within a
simplification procedure. This means that the arguments have not been
simplified before. Therefore we must enforce full simplication of
these arguments by applying |simp!*| to them before processing.

@u
lisp procedure split_arguments(arg_list,oplist,splitted_list);
if null arg_list then splitted_list
else split_arguments(cdr arg_list,oplist,
       multf(denr first_arg,car splitted_list) . @|
       split_form(numr first_arg,oplist) . 
       cdr splitted_list) @|where first_arg=simp!* car arg_list$

@ For convenience we will write a surrounding procedure
|split_operator|, in order to hide the last two arguments of
|split_arguments|. Its only argument is an operator element, the
arguments of which are to be splitted. For its proper operation it
assumes that the multilinear operator under consideration has the
property |oplist|, which is the list of operators w.r.t.\ which the
operator is multilinear.

@u lisp procedure split_operator u;@/
split_arguments(cdr u,get(car u,'oplist),1 . nil)$

@ Once we have a list of splitted arguments we can build up the sum of
operator elements of all possible combinations of components of the
(splitted) arguments. Since the list of splitted arguments is stored
in reverse order, this can be done most conveniently by recursive
procedures. If we consider one (splitted) argument of the operator
under consideration as a list of components, and the whole argument
list of the operator as a stack of component lists, we can build up
the sum by applying two recursive procedures |process_arg_stack|,
|process_comp_list| to the argument stack and component list(s)
respectively.

The procedure |process_arg_stack| and |process_comp_list| work as follows.
The procedure |process_arg_stack| applies the procedure
|process_comp_list| to the first component list of the argument stack
it has been offered.

The procedure |process_comp_list| applies the procedure
|process_independent_part| to the independent part of the component
list and adds it to the result of applying |process_components| to the
other components.

The procedure |process_components| takes the first component of the
component list it has been offered and |cons|'es the kernel part of
this component in front of the argument list of the elementary
operator element being built up and updates the factor with which this
elementary operator element has to be multiplied at the end by
multiplying it with the coefficient part of the component being
processed.  Now, if the remaining part of the argument stack is
empty the argument list of the elementary operator element is ready
and we can simplify it, multiply it with the product of the
coefficients and add it to the result (in fact this is done in the
procedure |process_arg_stack|).  Otherwise we must continue to build an
argument list of an elementary operator element by applying
|process_arg_stack| to the remaining part of the argument stack.
Finally |process_components| has to be applied on the remaining part of
the component list being processed. The procedure
|process_independent_part| takes the similar actions appropriate for
the independent part of a component list.

Throughout the calls of all procedures explained above we need to
know what is the current argument list and the current factor being
built up. We therefore pass them to all procedures as the arguments
|arg_list| and |fact|, which is the factor being build up as a
standard form. Hence it is clear that the argument list and the factor
have to be initialized to |nil| and 1, respectively.

@ We mentioned that the elementary operator elements have to be
simplified before they can be added.  It would, however, be unwise
simply to apply |simp| since the operator under consideration will
have the procedure |simp_multilinear| as its simplification
function\dots, leading to an infinite loop. For ordinary cases
applying |simpiden| will be sufficient, but since we wish to take
account for use of multilinear operators in special packages, we will
add to each multilinear operator a property |resimp_fn|, which is the
simplification function to be applied to an elementary operator
element.

With this knowledge we can implement the procedure |process_arg_stack|
right away. Note that |fact| has to be converted into a standard
quotient before multiplying the (simplified) operator kernel with it.
This is done with help of the procedure |!*f2q|.

@u lisp procedure process_arg_stack(arg_stack,op_name,arg_list,fact);
if null arg_stack then multsq(!*f2q fact,
                        apply1(get(op_name,'resimp_fn),op_name . arg_list))
else process_comp_list(car arg_stack,cdr arg_stack,op_name,arg_list,fact)$

@ The procedure |process_comp_list| consists of adding the results of
applying |process_independent_part| and |process_components| to the
current component list.

@u
lisp procedure process_comp_list(comp_list,arg_stack,op_name,arg_list,fact);
addsq(process_independent_part(car comp_list,arg_stack,op_name,arg_list,fact),
      process_components(cdr comp_list,arg_stack,op_name,arg_list,fact))$

@ Following our description of multilinearity, processing the
independent part of an argument boils down to multiplying |fact|
with it and adding the argument 1 to |arg_list|. If, however, the
independent part is |nil|, i.e.\ the operator element being built up
will contain a zero argument, thanks to multilinearity this operator
element will not contribute to the result and we can return |result|
immediately.

@u lisp procedure process_independent_part(independent_part,arg_stack,
                                           op_name,arg_list,fact);
if null independent_part then nil . 1
else
   process_arg_stack(arg_stack,op_name,1 . arg_list,@|multf(fact,independent_part))$


@ The procedure |process_components| has to process the |comp_list|
until there are no more components of the argument being processed.

@u lisp procedure process_components(comp_list,arg_stack,op_name,arg_list,fact);
if null comp_list then nil . 1
else 
  addsq(process_components(cdr comp_list,arg_stack,op_name,arg_list,fact),
        process_arg_stack(arg_stack,op_name,caar comp_list . arg_list,
                    multf(fact,cdar comp_list)))$

@ To hide the rather illogical arguments of |process_arg_stack| we will
write a surrounding procedure |build_sum| for it. Recall that
|arg_list| and |fact| have to be initialized to |nil| and 1,
respectively.

@u lisp procedure build_sum(op_name,arg_stack);@/
process_arg_stack(arg_stack,op_name,nil,1)$

@ With the procedures written above, the simplification function
|simp_multilinear| can be written at once. We recall that the result
of |split_arguments| is a dotted pair, the |car| of which is the
product of the denominators of all arguments, the |cdr| the list of
splitted arguments, a argument stack.

For simplifying a multilinear operator it is clear that we need to
know the operator name, in other words the |car| of the argument
offered to |simp_multilinear| must be the operator name. To achieve
this we must flag the operator under consideration |full|.

@u lisp procedure simp_multilinear u;
quotsq(build_sum(car u,cdr splitted_list),!*f2q car splitted_list) @|
where splitted_list=split_operator u$

@ The last step towards a successful introduction of multilinear
operators in REDUCE, is the implementation of a procedure
|multilinear| to set up the right environment for multilinear
operators.  It is our purpose to give meaning to the declaration
$$\hbox{\\{multilinear} $P$(operator${}\mid{}$list of operators
[,resimplification function]);}$$ as to declare $P$ a multilinear
operator w.r.t.\ the operator(s) of the first argument and, if
present, with the second argument as it's |resimp_fn|, otherwise
|simpiden| if $P$ doesn't already possess a simpliciation or
resimplification function.

@ If we give |multilinear| the property |stat| with value |rlis| in
order to allow for more multilinear declarations at a time, the
declaration \\{multilinear} $P_1(\dots),\dots,P_n(\dots)$ will lead to
the call $\\{multilinear} ((P_1\ \dots)\ {\dots}\allowbreak (P_n\ \dots))$. With
this knowledge the source of |multilinear| is rather straightforward.
Notice that since |stat=rlis| the procedure |multilinear| need not be
a lisp operator.

@u
put('multilinear,'stat,'rlis)$@#

lisp procedure multilinear u;
for each decl in u do 
begin scalar op_name,resimp_fn;
  if length decl neq 2 and length decl neq 3 then@|
     stop_with_error(nil,decl,"invalid multilinear declaration",nil);
  if not idp(op_name:=car decl) then 
     stop_with_error(nil,op_name,"invalid as operator",nil);
  put(op_name,'oplist,make_oplist(cadr decl));
  if (length decl=3 and (resimp_fn:=caddr decl)) or 
     (resimp_fn:=get(op_name,'resimp_fn)) or@|
     (resimp_fn:=get(op_name,'simpfn)) then put(op_name,'resimp_fn,resimp_fn)
  else put(op_name,'resimp_fn,'simpiden);
  put(op_name,'simpfn,'simp_multilinear);
  flag(list(op_name),'full);
end$

@*  Solving linear expressions. We prefer not to use the REDUCE
procedure |solve| for solving a kernel from an algebraic expression
which we demand to be linear w.r.t.\ that kernel, because |solve|
doesn't check for linearity and can give more than one solution in
case of non linearity. Therefore we will write two quite
straightforward procedures which do the job properly.

@ \specs |@!linear_solve|, |@!linear_solve_and_assign|.
  \descr Syntax: \descno 1. |linear_solve(exprn,kernel)|,\nl 
                 \descno 2. |linear_solve_and_assign(exprn,kernel)|.
  \descr Arguments:
    \arg |exprn|: algebraic expression.
    \arg |kernel|: kernel.
  \descr Result:
                \descno 1. solves |exprn| for |kernel| and returns the
                    solution, regarding |exprn| to be a linear equation w.r.t.\ 
		    |kernel|. Before solving, |exprn| is simplified.\nl
                \descno 2. as |linear_solve|, 
          but also sets |kernel| equal to this solution.
  \descr Errors: stops with an error message if |kernel| is not a
                 kernel, or if |exprn| is not linear w.r.t.\ |kernel|.

@ The procedure |linear_solve| should be available in algebraic mode.
We will use the same construction as for |operator_coeff| in order to
avoid unnecessary simplification.

@u 
put('linear_solve,'psopfn,'linear_solve_1)$
@#
lisp procedure linear_solve_1 u;
if length u neq 2 then
rederr("LINEAR_SOLVE: wrong number of arguments")
else linear_solve(car u,cadr u)$

@ If we are given an expression |exprn| linear in some kernel
|kernel|, we should be aware that |exprn| may be multiplied by some
factors, which might give trouble when solving the equation. In order
to prevent this we will first determine the factor depending on
|kernel|. For this purpose we shall use the standard REDUCE procedure
|fctrf| which finds all factors in a standard form as a list
containing the first factor as a standard form and all other factors
as a standard quotient. If there are more factors depending on
|kernel|, the system is not linear and we can return with an error
message.

@<If possible find the factor |form| of |exprn| that depends on |kernel|@>=
exprn:=fctrf numr simp!* exprn;@/
exprn:=if domainp car exprn then cdr exprn @+else (car exprn . 1) . cdr exprn;
form:=for each factor in exprn join@+
  if depends(factor,kernel) then list factor;
if length form=1 then form:=numr car form else
  stop_with_error("LINEAR_SOLVE: expression not linear with respect to",
                       kernel,nil,nil)

@ The linearity of |form| can be checked rather easily: reorder form
w.r.t.\ |kernel|. After this, |form| is linear w.r.t.\ |kernel| if and
only if the main variable of |form| is |kernel|, the leading degree of
|form| is 1 and the leading coefficient and the reductum of |form| do
not depend on |kernel|.

At this place it is convenient to explain how reordering of kernels is
performed in REDUCE. In algebraic mode the kernel ordering can be
affected by the command |korder|. This command puts all kernels
following it on the list |kord!*| (a fluid system variable) and forces
reevaluation of all algebraic expressions. The actual reordering is
done by the procedure |reorder| which reorders standard forms using
the list |kord!*|.

If we declare |kord!*| to be local within all procedures where we want
to reorder standard forms, we don't have to worry about the kernel
ordering afterwards, because the values of fluid variables, which are
used locally within a procedure, are saved on a stack when entering
the procedure and restored after leaving it.

The procedure |!*a2k| checks whether |kernel| is a kernel.  

@u
lisp procedure linear_solve(exprn,kernel); 
begin scalar kord!*,form;
  kernel:=!*a2k kernel;
  @<If possible find the factor |form| of |exprn| that depends on |kernel|@>;
  setkorder list kernel;
  form:=reorder form;
  if (mvar form=kernel) and (ldeg form =1) and 
   not depends(lc form,kernel) and not depends(red form,kernel) then
      return !*ff2a(negf red form,lc form)
  else stop_with_error("LINEAR_SOLVE: expression not linear with respect to",
                       kernel,nil,nil);
end$

@ |linear_solve_and_assign| can simply use the procedures |setk| and
|linear_solve|. It will also get the |psopfn| mechanism to make it
available in algebraic mode.

@u 
put('linear_solve_and_assign,'psopfn,'linear_solve_and_assign_1)$ 
@#
lisp procedure linear_solve_and_assign_1 u;
if length u neq 2 then
rederr("LINEAR_SOLVE_AND_ASSIGN: wrong number of arguments")
else linear_solve_and_assign(car u,cadr u)$
@#
lisp procedure linear_solve_and_assign(exprn,kernel);
setk(kernel,linear_solve(exprn,kernel))$

@*  Restricted solving of linear expressions. In our programs we want
to do a lot of automated computations on algebraic expressions
containing algebraic operators. In particular we think it is
convenient to have, together with the procedures |linear_solve| and
|linear_solve_and_assign|, a procedure that searches an algebraic
expression for kernels of some specified operator with respect to
which the algebraic expression is linear, but with the coefficients of
these kernels not depending on some other operators.

Let us give an example in which such a procedure can be used
fruitfully. Suppose we have an expression |a(3)*a(2)-a(1)| from which
we want to solve one the |a(i)|'s automatically. Taking the first
operator element at sight, we would get |a(3):=a(1)/a(2)|. This,
however, is undesirable, because |a(2)| may be equated to 0 during the
process, in which case we are in trouble. Therefore the solution
should be |a(1):=a(3)*a(2)|.

But how can we discover that we must solve for |a(1)|?  The answer to
this question is to use the procedure |solvable_kernels|, which
we will specify in a moment: the call
|solvable_kernels(a(3)*a(2)-a(1),a,a)| searches the expression
|a(3)*a(2)-a(1)| for kernels of operator |a| (second argument), but
only those which don't have coefficients containing kernels of
operator |a| (third argument). Hence this call returns the list
|{a(1)}| which is exactly the list of all kernels for which we may
solve without risc.

@ \spec |@!solvable_kernels|.
  \descr Syntax: |solvable_kernels(exprn,k_oplist,c_oplist)|.
  \descr Arguments:
    \arg |exprn|: algebraic expression.
    \arg |k_oplist|: identifier or (algebraic or lisp) list of identifiers,
                     which should be algebraic operator(s).
    \arg |c_oplist|: identifier or (algebraic or lisp) list of identifiers,
                     which should be algebraic operator(s).
  \descr Result: returns an algebraic list of all kernels
                 |opkern| for wich all the following conditions are
		 satisfied:\nl
      \descno 1. |exprn| contains the kernel |opkern| for
	           some operator on |k_oplist|\nl
      \descno 2. |exprn| is linear w.r.t.\ |opkern|\nl
      \descno 3. the coefficient of |opkern| in |exprn| is
                   not a polynomial expression in any kernel of
		   operator(s) on |c_oplist|.\nl
                 Before the analysis, |exprn| is simplified.
  \descr Examples: the call
                   |solvable_kernels(a(1)*(b(1)+c(1))+a(2)*b(2),a,c)|
                   returns the list |{a(2)}|.

@ For |solvable_kernels| we will use the same construction as
for |operator_coeff| to make it an lisp operator.

@u 
put('solvable_kernels,'psopfn,'solvable_kernels_1)$
@#
lisp procedure solvable_kernels_1 u;
if length u neq 3 then 
rederr("SOLVABLE_KERNELS: wrong number of arguments")
else solvable_kernels(car u,cadr u,caddr u)$

@ As for |operator_coeff| all the essential actions are taken while
scanning the numerator $E$ of |exprn|, which is a standard form.
Seeing $E$ as a sum $E=\sum T_i$ where $T_i=P_i\cdot C_i$, the product
of a leading power and a leading coefficient, again, we can
distinguish the following states for each term $T_i$: \medskip

\item{1.} $T_i$ is domain element, hence in particular not a kernel of
one of the operators on |k_oplist| or |c_oplist|. We have to take no action.

\item{2.} The main variable of $P_i$ is a kernel of one of the
operators on |k_oplist|. If the leading degree is one and $C_i$ does
not contain kernels of operators on |c_oplist|, this kernel is a
possible candidate for solving, otherwise it has to be marked as
unsolvable.

\item{3.} The main variable of $P_i$ is a kernel of one of the
operators on |c_oplist|. We can now recursively examine the standard
form $C_i$ and mark all kernels of operators on |k_oplist| found there
as unsolvable.

\item{4.} In all other cases we can recursively examine the standard
form $C_i$, ignoring the factor $P_i$.

\noindent Note that also in case 2.\ we have to check the form $C_i$,
keeping in mind the conditions of case 3.: the main variable of $P_i$
can be forbidden as well as allowed as a coefficient.

@ Implementing the actions described above requires a function for
merging an new element into a list. It is rather straightforward.

@u
lisp procedure list_merge(element,merge_list);
if member(element,merge_list) then merge_list else element .
merge_list$
 
@ The actions described above are implemented in the procedure
|mk_kernel_list|. The procedure examines the leading term and
recursively the reductum of the standard form.

The fifth argument of the procedure, |kernel_list|, is a dotted pair,
the |car| of which is the list of all possible candidates for solving,
the |cdr| the list of unsolvable kernels and is returned at the end.
It is clear that, at top level, it has to be initialized to |nil . nil|.

The fourth argument |forbidden| is a flag indicating if, at some
higher level, a kernel of an operator on |c_oplist| has been
encountered, hence that all kernels op operators on |k_oplist| found
have to be marked as unsolvable. At top level is has to be initialized
to |nil|.

@u lisp procedure mk_kernel_list(form,k_oplist,c_oplist,forbidden,kernel_list);
if domainp form then kernel_list
else (
  if not atom kernel then
    mk_kernel_list(red form,k_oplist,c_oplist,forbidden,@|
        mk_kernel_list(lc form,k_oplist,c_oplist,
          if member(car kernel,c_oplist) then t @+else forbidden,
          if member(car kernel,k_oplist) then
            if not forbidden and ldeg form=1 and 
              not get_first_kernel(lc form,c_oplist) then@|
               list_merge(kernel,car kernel_list) . cdr kernel_list
            else
              car kernel_list . list_merge(kernel,cdr kernel_list)
          else kernel_list))
  else mk_kernel_list(red form,k_oplist,c_oplist,forbidden,@|
         mk_kernel_list(lc form,k_oplist,c_oplist,forbidden,kernel_list))
  ) where kernel=mvar form$

@ The procedure |solvable_kernels| is a piece of cake now:
simplify |exprn|, get its numerator, apply |mk_kernel_list| to it and
finally delete all unsolvable kernels from the list of possible
candidates for solving. The list obtained in this way is the list of
all solvable kernels in |exprn|.

Again we use |simp!*| to simplify |exprn|, because |exprn| hasn't been
simplified before and we want a full simplification including a call
of |subs2|.

@u
lisp procedure solvable_kernels(exprn,k_oplist,c_oplist);
begin scalar form,kernel_list,forbidden_kernels;
  form:=numr simp!* exprn;
  k_oplist:=make_oplist(k_oplist);
  c_oplist:=make_oplist(c_oplist);
  kernel_list:=mk_kernel_list(form,k_oplist,c_oplist,nil,nil . nil);
  forbidden_kernels:=cdr kernel_list;
  kernel_list:=car kernel_list;
  for each kernel in forbidden_kernels do kernel_list:=delete(kernel,kernel_list); 
  return 'list . kernel_list;
end$

@ The end of a REDUCE input file must be marked with |end|.

@u end;

@*  Index. This section contains the cross reference index of all
identifiers, together with the numbers of the modules in which they
are used. Underlined entries correspond to module numbers where the
identifier was declared.