TRI - REDUCE Computer Algebra System
Contents
1. M vs hs insert a matrix and eat up all arguments on passing by put vs as a vertical separator and hs as a horizontal separator between the rows and columns APPLY fun apply function fun to remaining argument list These tags are assembled to a tag list or pattern respectively For each functor i e the head of a prefix list e g PLUS MINUS or SQRT such a list is bound to its property TEXPATT For instance the functor PLUS has got the pattern X F R bound to it and the functor EXPT possesses the pattern X Z The following two boxes with pseudo code figures 3 and 4 survey the two major functions performing the expansion of a prefix REDUCE expression into a TeX item list At this point the way we use our LISP pseudo code should be explained Words typeset in boldface are reserved words e g begin and end We use a PASCAL like syntax which is actually used by REDUCE Lisp too but with a few differences we use 11 p in the terminologv of the programming language Prolog function mktag tag outer precedence associative begin if tag is empty then return nil else if tag is an atom then return get the TEX item fortag else begin the tag is a list precedence precedence of this tag or 999 now expand the expression the first element is the functor the following elements are the arguments term makefunc car tag cdr tag precedence check for parentheses term is surrou2. offsetof base baseindent length indentof base total total widthof base while top and length pagewidth do begin consider this node for end of the line node car top penalty penaltyof node if node is a passive node then len len node else begin node is an active node badness compute current badness from length andbaseindent penalty penaltyof node offset offsetof node if badness lt tolerance or badness lt 1 penalty or this is the rightmost delta node then begin we have a feasible breakpoint demerits basedemerits badness penalty abs penalty if node is a delta node then begin if demerits lt demeritsof node better path found then begin save current demerits and baseid to node compute amount of indentation end end else begin feasible feasible 1 create new delta node with feasible baseid demerits compute amount of indentation end if penalty 10000 then top lt nil must break here end length length wdithof node end if top then top cdr top end save the total length so far to the delta node step ahead to next delta node and count total length end Fig 10 The code segment from trybreak dealing with line breaking Earlier we introduced the concent of badness derived from Trex But actually this is not the only measure answering the question whether a certain point in the breaklist is feasible or not
3. The task of setting the break points i e break items in the breaklist is up to the function trybreak During this phase some active nodes are selected as feasible break points Thus they will be extended and called delta nodes furtheron By default the first and last node in a breaklist are delta nodes When trybreak has finished the ptr s of the delta nodes point back to the best preceding delta node in terms of minimal total demerits So by stepping through this pointer list it is easy to find the best path for breaking the whole breaklist apart We use some terminology we d like to explain width width of this item both active and passive nodes penalty a numeric value which prohibits line breaking if negative line break ing will be merited offset distance to the most recent opening bracket id number the identification number of this delta node 1 2 3 ptr pointer to the best delta node to come from with respect to the mini mal demerits path Note a zero pointer indicates the very bevinnine 000000 0 915227 163840 O 0 1347128 163840 1097271 163840 321308 163840 390 0 1347128 163840 1097271 163840 598015 163840 O 0 1674808 163840 820564 163840 598015 163840 390 0 1674808 163840 820564 163840 598015 163840 O 0 1674808 163840 820564 163840 598015 163840 390 0 1674808 163840 820564 163840 598015 163840 0 0 1674808 163840 820564 163840 598015 163840 390 0 1674808 1638
4. 8008 vl w 11440 v wi 12870 v w 11440 v w 8008 v w 4368 v wl 1820 v wt 560 v wt 120 v wt 16 v wt wt int 1 x 3 2 x 2b 2 V3 arctan 2422 I 2t 28 02 2 In 2 2 12 int 1 x 44 3 x 2 1 x Va 8 YvVB 3 vT m yv 3 v3 2 2 3 YVI 3 VI m yV 3 V3 2 2 13 vis 3 In 4 Vid 3 v2 2 2 13 vi3 3 In Vi5 3 vV3 2 2 2 6 2a 4 184 Be Sacha se vV v13 3 v2 26 y V13 3 arctan e A 104 VV13 3 v2 solve x 3 x 2 mutnu 0 x a 0 VEF vas pan VA Yon 2 9 VI p v4 27 7 2 V3 p 27 V3 v vir 2 9 VE peu F27 v 2 V3 p 27 V3 v 2 38 28 Va yo 6 9 avr oT 2 V3 yann vie N voir ew ale Se TT 2 ge 9 VA BT oF 2 p 27 V3 v Vi wi 9 VA pS V 27 7 2 V3 p 27 V3 v u 2 9 VE pv 27 03 2 V3 p 27 V3 v at d 2 VA abi a el lan 6 9 VA FT 2 V3 p 27 V3 v za 9 VEG VERT 2 Va p 27 VA 9 VE pV 427 2 V3 p ki VEn atat AB A 3 0 VEET a Vi an V3 v 24 3 alr i mat 1 a b 1 c d ak 2 b 2 1 sqrt c a b c d sqrt d 1 9 Caveats Techniques for printing mathematical expressions are available everywhere This TRI adds only a highly specialized version for most REDUCE output The emphasis is on the word most
5. One major caveat is that we cannot print SY MBOLIC mode output from REDUCE This could be done best in a WEB like programming plus documentation style Nevertheless as Knuth s WEB is already available for PASCAL and C hopefully someone will write a LISP WEB or a REDUCE WEB as well Whenever you discover a bug in our program please let us know Send us a short report accompanied by an output listing We ll try to fix the error The whole TRI package consists of following files tris tex This text as a TEX input file tri red The REDUCE LISP source code for the TRI tridefs tex The TEX input file to be used together with output from the TRI redwidth tex The TEX input file for interactive determination of TEX item widths tritest red Run this REDUCE file to check if TRI works correctly tritest tex When you have run tritest red just make a TEX run with this file to see all the nice things TRI is able to produce 10 References ANTWEILER W STROTMANN A PFENNING TH WINKELMANN V 1986 Zwischenbericht ber den Status der Arbeiten am REDUCE Tpx Anschluf Internal Paper Rechenzentrum der Uni versitat zu K ln November 1986 FATEMAN RICHARD J 1987 TEX Output from MACSYMA like Systems ACM SIGSAM Bulletin Vol 21 No 4 Issue 82 November 1987 pp 1 5 KNUTH DONALD E PLASS MICHAEL F 1981 Breaking Paragraphs into Lines Software Practice and Experience Vol 11 1981 pp 1119 1184 KNUTH DONALD E 1986 T
6. TEX items itself We provide a way for adding standard TEX items of any class ORD BIN REL OPN CLO PCT and LOP except for class INN which is reserved for internal use by TRI only You can call the function TeXitem item class list of widths e g together with a binding TeXitem nla b l a ORD 655360 327680 163840 TeXlet NABLA nta lb l a where item is a legal TEX code name class is one of seven classes see above and list of width is a non empty list of elements each one representing the width of the item in successive super subscript depth levels That means that the first entry is the breadth in display mode the second stands for scriptstyle and the third stands for scriptscriptstyle in TEX terminology But how can you retrieve the width information required For this purpose we provide the following small interactive T X facility called redwidth tex documented in figure 15 Simply call tex redwidth on your local machine Then you are prompted for the TEX item you want the width information for Type end when you want to finish the session newbox testbox newcount xxx newif ifOK def endloop end def widthof 1 message width is wwidthof displaystyle 1 wwidthof scriptstyle 1 wwidthof scriptscriptstyle 1 def wwidthof 1 setbox testbox hbox 1 xxx wd testbox message the wd testbox the xxx sp loop message Type in TeX item or say end rea
7. but with local instead of total 5 Postprocessing with the TEX module tridefs tex When a TEX output file has been created with the TRI it has to be processed by TRX itself But before you run TEX you should make sure the file looks the way you want it Sometimes you will find it necessary to add some TEX code of your own or delete some other TEX code This job is up to you before you finally run TEX During the TEX run the sizes of brackets are determined This task is not done by the TRI In order to produce proper sized brackets we put some left and right TEX commands where brackets are opened or closed A new problem arises when an expression has been broken up into several lines Since for every line the number of left and right TEX commands must match but bracketed expressions may start in one line and end in another we have to insert the required number of dummy parentheses i e right and left TEX commands at the end of the current line and the beginning of the following line Therefore we have to keep track of the depth of bracketing See the following figure 14 for the TEX code actually applied There is a caveat against this method Since opening and closing brackets needn t lie in the same line it is possible that the height of the brackets can differ although they should correspond in height That will happen if the height of the text in the opening line has a height different from the text in the closing l
8. There are three conditions which decide whether a breakpoint is feasible or not The first condition requires the badness to be smaller than the value of tolerance as specified by the user This condition can be overridden if the active node under consideration has a negative penalty whose absolute i e positive amount is greater than the badness That means you can buy a breakpoint if you ve got enough money i e a bonus negative penalty to pay the price i e the badness The third condition just forces the rightmost delta node to be considered feasible anyway At this point we introduce a second measure called demerits which is defined as the sum of the demerits so far i e up to the beginning of the line currently under consideration the squared badness and the sign propagated square of the penalty Now we have a measure which not only refers to the current line but to the previous lines too Therefore our modified KNUTH algorithm optimizes not only over one line but over all lines Figure 11 should make clear what is happening to the breaklist and the TEX item list For readability purposes we display the latter but really it is the breaklist under consideration within trybreak As in the previous display of our example you can identify the active nodes These are the three element number lists The third element which is zero here is used as an offset width to the last opening bracket This information is used for
9. as pattern isn t empty begin tag car pattern pattern cdr pattern if tag is an atom then aur lt nil else if tag is F then aur get the TEX item forfunctor else if argument list is empty then auz nil else if tag is X then begin aut mktag car argument list precedence nil argument list cdr argument list end else if tag is Y then begin aut mktag car argument list precedence T argument list cdr argument list end else if tag is R then tail recursive pattern if cdr argument list more than one argument remaining then begin pattern pattern for functor argument list nil end else begin aurz lt mktag car argument list precedence nil argument list cdr argument list end else if tag is L hs M vs hs or APPLY xxx then begin aur result from call to a special routine argument list nil end else aux nil if auz then concatenate it to the end of term end return term end Fig 4 The function makefunc As well as the function mktag this function performs the prefix to TEX notation Its major task is to unify operators and their arguments with predefined patterns in order to build up lists of TEX items additional commands you find at the beginning and ending of the output and as Nnl commands within the output Nevertheless the structure of the output would be much the same with our normal TEX mode The actual printing of T
10. node width penalty offset pnassive node width 163840 0 12 163840 cdot 163840 163840 66 163840 cdot 163840 163840 220 163840 cdot 163840 163840 495 163840 cdot 163840 163840 79 2 163840 cdot 163840 163840 924 163840 cdot 163840 163840 9 2 163840 cdot 163840 163840 495 163840 cdot 163840 163840 220 163840 cdot 163840 163840 66 163840 cdot 163840 163840 12 163840 cdot 163840 163840 Fig 7 A TEX item list extended with glue items delta node active node appendix appendix id number ptr demerits indentation The breaklist will be created using the function breaklist line breaking is per formed with this list only the TEX item list becomes modified only indirectly since the active nodes are shared That means that the active nodes aren t copied while creating the breaklist Instead their memory addresses are put into the breaklist as a reference This is both memory saving and necessary since later we deal with the TEX item list itself again in order to insert nl commands So remember there exist two lists sharing all the active nodes and hence all the delta nodes Figure 8 contains the breaklist from our x y example Bear in mind that passive nodes are sums of widths The first line and the last line contain the beginning and ending delta nodes respectively By default their id numbers are 0 and 1 respectively
11. used if a line should be broken at this point The algorithm for inserting glue items is easily described for every consecutive pair of TEX items get their classes and create a glue item according to the value found in the glue item table For some special TEX items use special penalties instead of the default values That s all Let us return to our example from the last chapter When the functions insertglue and interglue have finished the TEX item list will be left temporarily extended with glue items You can find them as the two element lists in the example All glue items there have by chance the same width 163840 But they have different penalties 0 50 and 390 The latter therefore indicates a very good breaking point because it is a negative penalty i e a bonus See the following figure 7 for the changes made to the TEX item list Setting break points requires the creation of a breaklist A breaklist is a sequence of passive and active nodes where each active node is followed by a passive node and vice versa Active nodes represent glue items Passive nodes are integer atoms which represent the width of a sequence of ordinary TEX items which must not be interspersed with glue items Each breaklist consists of at least one passive nodes surrounded by delta nodes representing the beginning and ending of the list breaklist delta node inner list delta node inner list passive node active node passive node active
12. 40 820564 163840 598015 163840 O 0 1674808 163840 820564 163840 598015 163840 390 0 1347128 163840 820564 163840 874722 163840 O 0 1347128 163840 543857 163840 874722 163840 390 0 1384446 0 O 41140184 1 O 2147483647 0 Fig 8 A breaklist Three types of objects are included in a breaklist Active nodes are the lists with three elements Delta nodes contain exactly seven elements Passive nodes are integer atoms representing a width of the breaklist demerits total demerits accumulated so far indentation amount of indentation when breaking at this point The algorithm itself will be described now To determine the quality of a line we introduce a value called badness It simply is a heuristic describing how good looking a line comes out This concept is due to Knuth Plass 1981 and is a major concept of TEX We use a slightly different heuristic here We do not measure badness in terms of stretchability and shrinkability Instead we measure how full a line is where full means that three quarters of the page width are optimal Furthermore we add a surplus badness for the indentation the less indentation the better The badness is a value between 0 and 10000 and is calculated with the following code displayed in figure 9 Surprisingly we got a higher speed with floating point arithmetic here than with integer arithmetic function badnessof length indentation begin temp abs le
13. 92 QX 8 495 C x 9 220 X 10 66 X 11 12 CY 1 DT Fig 1 Standard Quotient Notation This form is the way REDUCE represents terms The term has been indented by hand to retain the structure of this expression Actually the denominator is 1 as you easily find out from the last line Obviously the standard quotient form is a bit complicated for further manipulations It can be changed to a real prefix notation as displayed in figure 2 Here too the term was edited by hand to make it a bit more readable and comparable to the other forms Note that PLUS is not a binary but a n ary operator i e it takes an arbitrary number of arguments while MINUS is always a unary operator This causes a bit of trouble because real binary operators are much easier to handle To tackle this problem we have introduced the gt TEXUBY property which is used to change a unary into a binary form if possible 8 The T in the last line is an already simplified flag indicating that the term doesn t need to undergo any more processing Edit only means we have provided some additional indentation We have changed neither the expression nor its structure 10 The same problem arises with the RECIP operator which is the unary form of the binary OQUOTIEBNT operator TIMES TIMES TIMES TIMES tal TIMES TIMES TIMES TIMES TIMES TIMES TIMES PS P P P P P P
14. RI output in this example is easilv readable since the expres 2 1 0 9 8 7 6 5 4 3 2 HKONOMoOONOONOHr NOOCONFVQGKNOOON i PHY YY YY Yee S sssssssssss MA YY YY Ye Fig 5 A TEX item list A TEX item is either a letter a digit or another plain character or it is a TEX command Every TEX item belongs to one out of eight TEX item classes displaylines qdd x 12 12 cdot x 11 cdot y 66 cdot x7 10 cdot y 2 220Ncdot x 9 cdot y 3 495 cdot x 8 Ncdot y 4 792 cdot x 7 cdot y 5 n1 924 cdot x 6 cdot y 6 792 cdot x 5 cdot y 7 495 cdot x 4 cdot y 8 220Ncdot x 3 cdot y 9 66 cdot x7 2 cdot y7 10 12Ncdot x cdot y 11 y 12 NL Fig 6 Output produced by the TRI This TEX code has to be postprocessed by TEX This example includes commands for line breaking as produced with the second level of TRI sion is not deeply nested Complications arise if expressions to be printed are deeply nested use many subscripts and superscripts have fractions and large operators and the like Then output structure is worsened especially if the whole expression extends over several lines We provide a cheap way of indentation to retain some of the structure but our solution is far from perfect As the need for post TRI editing rises the output from TRI should be made better However our quick and dirty solution should suffice 4 Breaking REDUCE expressions into lines As men
15. S DS Fig 2 Prefix Notation This list represents the state after application of makeprefix A REDUCE expression is expanded using the two functions mktag and makefunc Function mktag identifies the operator and is able to put some brackets around the expression if necessary makefunc is a pattern oriented unification function which matches arguments of a REDUCE expression in order of appearance with so called uni fication tags as explained below Thus mktag and makefunc are mutually dependent and highly recursive functions A unification tag list is a list or a pattern if you like which consists of single unfication tags Each REDUCE operator is associated with a unification pattern While expanding the expression each tag is replaced by the appropiate TEX item or partial TEX item list created subsequently A tag is defined as either an atom declared as a TEX item or one of the following F insert operator X insert non associative argument Y insert a left or right associative argument Z insert superscript subscript argument R use tail recursion to unify remaining arguments necessary with oper ators having more than two arguments e g the plus operator asso ciativity depends on previous X or Y tag L hs insert a list of arguments eat up all arguments on passing by put hs as a horizontal separator between the arguments e g a separator could be a comma for simple argument lists
16. Typesetting REDUCE output with TEX A REDUCE TEX Interface WERNER ANTWEILER ANDREAS STROTMANN VOLKER WINKELMANN University of Cologne Computer Center West Germany June 29 1999 Abstract REDUCE is a well known computer algebra system invented by Anthony C Hearn Although a pretty printer is already incorporated in REDUCE the output is produced only in line printer quality The simple idea to produce high quality output from REDUCE is to link REDUCE with Donald E Knuth s famous TREX typesetting language This draft reviews our efforts in this direction We introduce a program written in REDUCE Lisp which is able to typeset REDUCE formulas using TeX Our REDUCE TEX Interface incorporates three levels of TEX output without line breaking with line breaking and with line breaking plus indentation This paper deals with some of the ideas we have put into LISP code and it summarizes some of our experiments we have made with it yet Furthermore we compile a small user s manual introducing to the use of our REDUCE TEX Interface Keywords Line Breaking Algorithm LISP Prefix to Infix Conversion REDUCE TEX Typesetting 1 Introduction REDUCE is a well known computer algebra system invented by Anthony C Hearn While every effort was made to improve the system s algebraic capabilities the read ability of the output remained poor by modern typesetting standards Although a pretty printer is already incorporated in REDUCE the o
17. ard TEX output or TeXBreak to receive broken TRX output or TeXIndent to 16 That means we assigned the result of an evaluation to an itermediate variable and then we printed this intermediate variable Thus we could eliminate the time overhead produced by pure eval uation Nevertheless in terms of effective interactive answering time the sum of evaluation and printing time might be much more interesting than the pure printing time In such a context the percentage overhead caused by printing is the critical point But since we talk about printing we decided to document the pure printinge time receive broken TEX output plus indentation Thus the three levels of TRI are enabled or disabled according to On TeX switch TeX is on On TeXBreak switches TeX and TeXBreak are on On TeXIndent switches TeX TeXBreak and TeXIndent are on Off TeXIndent switch TeXIndent is off Off TeXBreak switches TeXBreak and TeXIndent are off Off TeX all three switches are off More specifically if you switch off TeXBreak you implicitly quit TeXIndent too or if you switch off TeX you implicitly quit TeXBreak and consequently TeXIndent The most crucial point in defining how TRI breaks multiple lines of TEX code is your choice of the page width and the tolerance As mentioned earlier tolerance is related to TEX s famous line breaking algorithm The value of tolerance determines which potential breakpoints are con
18. baseindent for the currently line That ll work if the line currently under consideration contains at least one opening bracket which hasn t become closed in the same line This case may be labelled the opening bracket case But what shall we do in the other cases We have to decide if we ve got a closing bracket case i e if we have at least one more closing bracket than we have opening brackets or if we ve got a no change case i e the number of opening brackets in the current line matches the number of closing brackets in this line This decision is made by comparing offset lt baseoffset If the baseoffset i e the offset at the beginning of the line is greater than offset i e the offset at the current point then we ve got the closing bracket case otherwise we ve got the no change case In the latter the amount of indentation for the next line is just the amount of indentation for the current line But the closing bracket case causes us much trouble So we need an extra function dealing with this case as displayed in figure 13 This macro searches the list of delta nodes previously created until it reaches a delta node at least the very first delta node in the breaklist where the total width accumulated so far i e the variable local is less than offset i e the offset at the 15 Macros become expanded where they are called and thus share all variable names defined in the code block where t
19. d 1 to answer ifx answer endloop 0Kfalse else O0Ktrue fi ifOK widthof answer repeat end Fig 15 The file redwidth tex This TEX code you can use to determine the width of specific TEX items Finally let us discuss how you can compile the TRI into a binary We refer to PSL but other LISP versions work quite similar First of all start REDUCE Than type in on comp symbolic 18 Please note that any TEX name ending with a letter must be followed by a blank to prevent from interference with letters of following TEX items Note also that you can legalize a name by defining it as a TEX macro faslout tri in tri red faslend bye We stress the fact that this procedure is definitely LISP dependent Ask your local REDUCE or LISP wizards how to adapt to it 8 Examples Some examples which we think might be representative shall demonstrate the capabilities of our TRI For each example we state a the REDUCE command i e the input b the tolerance if it differs from the default and c the output as produced in a TEX run x y 16 v w 16 x16 16 x y 120 x14 y 560 27 y 1820 2 yt 4368 x1 y5 8008 z1 y 11440 x y 12870 x y 11440 a y 8008 x oy 4368 ae y1 1820 ay 560 2 y 120 x y4 16 x y y v 16 vt w 120 v w 560 v w 1820 vl wt 4368 v1 w
20. e algebraic result REDUCE nor TeX TeX TeX Expression mal Break Indent a y 82 75 3 42 3 47 24 ty ty 3 ety osu solve 1 a 2 a x solve a a w v 2 This short table should give you an impression of the performance of TRI It goes with out saying that on other machines results may turn out which are quite different from our results But our intention is to show the relative and not the absolute performance Note that printing times are a function of expression complexity as shown by rows three and six 7 User s Guide to the REDUCE TEX Interface If you intend to use the TRI you are required to load the compiled code This can be performed with the command load package tri During the load some default initializations are performed The default page width is set to 15 centimeters the tolerance for page breaking is set to 20 by default Moreover TRI is enabled to translate greek names e g TAU or PSI into equivalent TEX symbols e g T or w respectively Letters are printed lowercase as defined through assertion of the set LOWERCASE The whole operation produces the following lines of output xFunction TEXVARPRI redefined set GREEK asserted set LOWERCASE asserted hsize 150mm tolerance 20 Now you can switch on and off the three TRI modes as you like You can use the switches alternatively and incrementally That means you have to switch on TeX for receiving stand
21. ement before end of math group def N1 hfill cr Fig 14 The file tridefs tex This is the code you have to use on the TEX side in order to typeset output produced by our TRI There is at least one more line of TEX code you have to insert by hand into the TEX input file produced by TRI This line runs input tridefs and inputs the module tridefs tex into the file This is necessary because otherwise TEX won t know how to deal with our macro calls If you use the TEX input file as a stand alone file don t forget a final Nbye at the end of the text If you use code produced by TRI as part of a larger text then simply put the input line just once at the beginning of your text 6 Experiments We measured performance using the TIME facility of REDUCE which can be switched on and off with the two commands ON TIME OFF TIME We have tested our TRI on a u VAX T operating under VAX VMS with no other users operating during this phase in order to minimize interference with other processes e g caused by paging The TRI code has been compiled with the PSL 3 2a Compiler The following table presents results obtained with a small number of different terms All data were measured in CPU seconds as displayed by LISP s TIME facility For expressions where special packages such as solve and int were involved we have taken only effective output time i e the time consumption caused by producing the output and not by evaluating th
22. etting quality e The intermediate files TEX input files should be easy to edit The reason is that it is likely that the proposed line breaks are sub optimal from the user s point of view e We apply a TEX like algorithm which optimizes the line breaking over the whole expression This differs fundamentally from the standard left to right one line look ahead pretty printers of REDUCE LISP and the like 2 From REDUCE to TEX concepts REDUCE uses the function varpri to decide how to output a REDUCE expression The function gets three arguments the expression to be printed a list of variables to each of which the expression to be printed gets assigned and a flag which determines if the expression to be printed is the first last or only expression in the line varpri may be called consecutively for preparing a line for output So our task is to assemble all expressions before finally printing them When TeX is true varpri redirects output to our function TeXvarpri which receives a REDUCE expression translates it into TEX and pushes it onto a variable called TeXStack before eventually printing it once the line is completed The TeXvarpri function first calls a function named makeprefix Its job is to change a REDUCE algebraic expression to a standard prefix list while retain ing the tree structure of the whole expression Generally this is done using a call prepsq simp expression but lists and matrices need some special treat
23. fo indicating an indentation level which is used later for computing the actual amount of indentation Active nodes are used as potential breakpoints Moreover while creating the breaklist the TEX item list will be modified if necessary according to the length of fractions and square roots which cannot be broken if retained in their classical form Hence fractions look like if they don t fit into a single line especially in the case of large polynomial fractions The major function for this job is named breaklist which calls resolve if necessary The third and most important level is the line breaking algorithm itself This al gorithm embedded in the function trybreak will be described below The idea how to break lines is based on the article by Knuth Plass 1981 Line breaking can occur at active nodes only So you can loop through the breaklist considering all potential break points But in order to find a suitable way in a reasonable amount of time you have to limit the number of potential breakpoints considered This is performed by associating a badness with each potential breakpoint describing how good looking or bad looking a line turns out If the badness is less than a given amount of tolerance as set by the user then an active node is considered to be feasible and becomes a delta node A delta node is simply an active node enlarged by four further infos an identification number for this node a pointe
24. he TEX book Addison Wesley Readings Ma sixth printing 1986 HEARN ANTHONY C 1987 REDUCE User s Manual Version 3 3 The RAND Corporation Santa Monica Ca July 1987 19 You can reach us with e mail at the following addresses Werner Antweiler antweil epas utoronto ca ff Andreas Strotmann strotmann rrz uni koeln de and Volker Winkelmann winkelmann rrz uni M koeln de
25. hey are called So there is no need for argument passing if certain variable names in the code block don t differ from call to call macro function findindent macro functions share all variables of outer code blocks begin first check if we can save search time for equal destination if offset lastoffset and baseptr lastbaseptr then return lastindent else begin search the delta node stack for previous indentation stack deltastack lastoffset offset p lt lastbaseptr baseptr while stack do as long as we have a delta node ahead begin node car stack current delta node if p idof node then begin p lt ptrof node local totalof node if local lt offset then stack nil end if stack then stack cdr stack end lastindent offset local indentof node return lastindent end end Fig 13 The macro function findindent This macro is used to compute the amount of inden tation in the closing bracket case It causes some trouble since we have to travel back to previous delta nodes end of the line under consideration and computes the amount of indentation from the difference of offset and local plus the amount of indentation so far Plainly speaking we go back the lines until we find a line where we find the opening parenthesis matching the closing parenthesis in the current line When we ve found it we compute the amount of indentation as described in the opening bracket case
26. indentation The delta nodes are remarkable These are the number lists with seven elements Count them by their fourth element They run 0 1 2 through 8 9 1 The fifth element gives you the way back through the list Start at the last delta node There the best way to come from is 1 So go to delta node 1 where you find 0 as the best way to come from Delta node 0 is the beginning so you re finished The sixth element stands for the total demerits so far The seventh element stands for the amount of indentation Here it is a zero because the term isn t nested in our example We haven t mentioned how we generate indentation yet Generally speaking inden tation is entirely directed by brackets either round curly or dummy brackets But how do we compute the amount of indentation First let s turn to the code segment which deals with this problem within the big line braking algorithm shown before The contents of figure 12 explains what happens to the amount of indentation compute amount of indentation begin if offset gt total then indent offset total baseindent opening bracket case else if offset lt baseoffset then indent findindent closing bracket case else indent baseindent no change case save indent to delta node end Fig 12 The code segment from trybreak dealing with indentation The logic of this code segment is easily summarized The offset is a measure of how distant the last o
27. ine We haven t found a wav of tackling this problem yet but we think it is possible to program a little TEX macro for this task Furthermore some macros deal with tricks we had to use in order to provide for indentation fraction handling and the like def qdd quad quad A simply a double quad def frac 1 2 1 over 2 fractions from prefix notation newcount parenthesis A nesting of brackets parenthesis 0 A intialize newcount n A a temporary variable A round and curly brackets def global advance parenthesis by1 left def global advance parenthesis by 1 right def global advance parenthesis by1i left lbrace def global advance parenthesis by 1 right rbrace def relax dummy parenthesis def relax dummy parenthesis A provide for looping using tail recursion 7e Nloop what Nrepeat def loop 1 repeat global n 0 global let body 1 iterate def iterate body let next iterate else let next relax fi next A conditions and statements for loop interior def 1ldd ifnum n lt parenthesis global advance n byl left nulldelimiterspace 0pt mathsurround 0pt def rdd ifnum n lt parenthesis global advance n byl Nright Nnulldelimiterspace Opt mathsurround Opt A newline statement as issued by TRI def nl1 loop rdd repeat hfill cr quad quad loop ldd repeat A indentation statement as issued by TRI def OFF 1 hskip 1sp relax A last newline stat
28. ment Af ter this has been done the new intermediate expression is passed to the most important module of the TRI the mktag makefunc family These functions recursively expand the structured list or operator tree into a flat list translating each REDUCE symbol or expression into so called TEX items on passing by For that reason this list is called the TEX item list If the simple TEX mode without line breaking was chosen this list is then printed immediately without further considerations Translation and printing this way is almost as fast as with the standard REDUCE pretty printer When line breaking has been enabled things get a bit more complicated The greatest effort with TRI was to implement the line breaking algorithm More than half of the entire TRI code deals with this task The ultimate goal is to add some break items i e nl TpX commands marking in a certain way optimal line breaks Additionally these break items can be followed immediately by indentation items i e NOFF TEX commands specifying the amount of indentation applicable for the next new line 2 The reason why it was called TRI and not RTI is simply due to the fact that TRI corresponds better to the three level tri level mode The whole family currently has five members The parents are the mktag and makefunc functions which do the most burdensome job The children aremakearg makemat and makeDF which handle special case
29. nce values This is necessary because badness is worsened by indentation So TRI has to try harder to find suitable places where to break Reasonable values for tolerance here lie between 700 and 1500 A value of 1000 should be your first guess That ll work for most expressions in a reasonable amount of time Sometimes you want to add your own REDUCE symbol to TEX item translations For such a task TRI provides a function named TeXlet which binds any REDUCE symbol to one of the predefined TEX items A call to this function has the following syntax TeXlet REDUCE symbol TEX item Three examples show how to do it right TeXlet velocity v TeXlet gamma G la lm m a TeXlet acceleration vialritthle tia 17 You can also specify page width in scaled points sp Note 1 pt 65536 sp 1 72 27 inch The function automatically chooses the appropiate dimension according to the size all values greater than 400 are considered to be scaled points Besides this method of single assertions you can choose to assert one of currently two standard sets providing substitutions for lowercase and greek letters These sets are loaded by default You can switch these sets on or off using the functions TeXassertset setname TeXretractset setname where the setnames currently defined are GREEK and LOWERCASE So far you have learned only how to connect REDUCE atoms with predefined TEX items but not how to create new
30. nded by parentheses in order to prevent it from overruling by precedence if associative and precedence outer precedence or precedence lt outer precedence then term put a pair of brackets around term return term end end Fig 3 The function mktag This function deals with the transformation from prefix notation to TEX notation One important task of it is to decide whether or not brackets should be placed around the term the word function to indicate that a value is returned and we use return to return the value of the function and therefore to exit the function This is in contrast to the use of return in REDUCE Lisp where return is used only to return the value of a begin end block Identifiers are printed in italics Where identifiers are used as logical values e g in conditions they are either false if their value is nil or true otherwise regardless of their exact value Pseudo operations are printed in roman and are put in angle brackets Comments too are printed in roman but they are put in curly brackets Assignments are typeset by the assignment operator thus indicating the direction of assignment Semicolons are used as in PASCAL and REDUCE as separators In order to improve readability mathematical expressions are given in mathematical form instead of real code Finally the operator is used to identify a pseudo code operation with its real code We do not provide proper data type decla
31. ngth 3 pagewidth pagewidth return min 10000 100 temp 2500 indentation pagewidth end Fig 9 The badness function Badness is just a heuristic to compute a numerical value describing how good looking a line comes out A correction term is applied to provide for indentation Figure 10 summarizes the line breaking algorithm The code is part of the function trybreak and describes the heart of our algorithm Basically it consists of two loops the outer loop steps through the breaklist considering each delta node as a potential start of a new line while the inner loop looks ahead exactly one line bounded by the page width or by the rightmost delta node checking each active node if it is a feasible breakpoint and if so saving it as the best path of breaking Or to put it in another way simply imagine a window as wide as a page which moves over the unbroken expression from the very left to the very right The left end of the window is put on every feasible breakpoint determined earlier The right end of the window just defines the border of the search for feasible breakpoints within the window bottom breaklist pagewidth user defined page width set all variables not mentioned explicitly to zero or nil while bottom do begin try a new line starting at this delta node base car bottom top cdr bottom baseid idof base baseptr ptrof base basedemerits demeritsof base baseoffset
32. pening bracket is from the beginning of the whole expression So in the 13 This is necessary since the end of the expression is naturally a breakpoint even if it is a bad one and the last delta node is needed for accounting purposes as well as for storing the pointer to the preceding breakpoints 14 The latter is evaluated as the product of the value which can be positive or negative and the absolute value which can be positive onlv 0 163840 o 0 163840 163840 163840 163840 163840 163840 163840 163840 163840 163840 163840 390 0 163840 o 0 163840 390 0 163840 o 0 XO o Oo S S d an BR OWONO ee ee 163840 18624949 0 151875 163840 20463597 0 2500 Ww 163840 21448001 2500 163840 22209856 al 163840 163840 163840 163840 163840 163840 163840 163840 163840 25794763 0 142299 163840 0 0 163840 32964577 207875 XO O o O o Pa vyv 163840 0 0 163840 38009479 149350 163840 38717176 149374 1 1 163840 39755738 303975 O 41140184 7 151866 Fig 11 A TEX item list extended with delta nodes From this list the line breaking way can be derived Start with node 1 go to node 1 and from there to node 0 That makes one break point at node 1 case where offset is greater than the total width accumulated until the very beginning of the line the indentation is just the difference between total and the sum of offset and the amount of indentation
33. r to the best feasible break point i e delta node to come from the total amount of demerits i e a compound value derived from badness and penalty accumulated so far and a value indicating the amount of indentation applied to a new line beginning at this node When trybreak has stepped through the list the breakpoints will have been determined Afterwards all glue items i e active nodes are deleted from the TEX item list while break and indentation items for those nodes marked as break points are inserted Finally the TEX item list is printed with regular ASCII characters We didn t put much emphasis on the question on how to format the intermediate output since it will be input directly into TEX The best way to characterize the routine texout is to call it quick and dirty The readabiltiy of the output is low but it may be quite good enough for users to do some final editing work Nevertheless texout keeps the nesting structure of the term visible when printed so it will be easy to distinguish between parenthesis levels simply by considering the amount of indentation 6 For example the plus and the difference operator have special impact on the amount of penalty T Tf one were to break the formula at this delta node the best place to start this line is given by this pointer 3 Creating a TEX item list The first TEX specific step in preparing a typesettable equivalent of a REDUCE expres sion is to expand the operator tree genera
34. rations for variables since this seems to be superfluous in LISP where you only deal with atoms and lists You can bind a TEX item to any REDUCE atom except the operators you like This is supported by binding the TEX item to the specific atom by its property TEXNAME You can choose to have some default TEXNAME properties for your variables Function makeset defines a set of such default names At the moment two sets are provided for greek and for lowercase letters Refer to the User s Guide for how you can use them But now turn back to the state of modifications our example term has undergone With our set of functions we have expanded the prefix form into a TEX item list consist ing of single TEX items such as numbers letters TEX macros TEX primitives and other TEX symbols The result is shown in figure 5 The cdot command is the multiplication sign whereas indicates the beginning of a superscript The term has been edited by hand to provide for proper indentation The last box in this chapter i e figure 6 is a verbatim copy of the output from TRI for our example Because our example will be used to demonstrate line breaking too some additional commands appear which won t occur in normal TEX mode These 12 REDUCE Lisp uses the phrase svmbolic procedure here function makefunc functor argument list precedence begin term nil pattern pattern of this functor or default pattern while pattern do as long
35. s such as list construnction or differentiation operators We do not review the minor functions since they are easily understandable This is not a TEX primitive but a TRI specific TEX macro command which expands into a lot of stuff see previous footnote The problem is to choose the right points where to insert these special TEX items Therefore the TEX item list undergoes three further transformation steps First the TEX item list gets enlarged by so called glue items Glue items are two element lists where the first element is a width info and the second element is a penalty info The penalty is a value in the range 10000 10000 indicating a mark up on a potential break point thus determining if this point is a fairly good if negative or bad if positive choice The amount of penalty depends a on the kind of TEX items surrounding the glue item b on the bracket nesting and finally c on special characteristics The function handling this job is named insertglue which implicitly calls the function interglue The latter determines the glue item to insert between a left and a right TRX item During the second level the TEX item list becomes transformed into a so called breaklist consisting of active and passive nodes A passive node is simply a width info giving the total width of TEX items not interspersed by glue items On the other hand active nodes are glue items enlarged by a third element the offset in
36. sidered feasible and which not The higher the tolerance the more breakpoints become feasible as determined by the value of badness associated with each breakpoint Breakpoints are considered feasible if the badness is less than the tolerance You can easily set values for page width and tolerance using TeXsetbreak page width tolerance where page width is measured in millimeters and the tolerance is a positive integer in the closed interval 0 10000 You should choose a page width according to your purposes but allow a few centimeters for errors in TRI s metric For example specify 140 millimeters for an effective 150 or 160 millimeter wide page That way you have a certain safety margin to the borders of the page Now let s turn to the tolerance A tolerance of 0 means that actually no breakpoint will be considered feasible except those carrying a negative penalty while a value of 10000 allows any breakpoint to be considered feasible Obviously the choice of a tolerance has a great impact on the time consumption of our line breaking algorithm since time consumption increases in proportion to the number of feasible breakpoints So the question is what values to choose For line breaking without indentation suitable values for the tolerance lie between 10 and 100 As a rule of thumb you should use higher values the deeper the term is nested if you can estimate If you use indentation you have to use much higher tolera
37. ted by REDUCE into a so called TEX item list The operator tree is preprocessed by makeprefix in order to receive an operator tree in standard prefix notation A TEX item is either a character letter or digit or special character or a TEX primitive or macro i e a LISP symbol with properties CLASS TEXTAG TEXNAME and only if the item represents an operator TEXPREC TEXPATT and TEXUBY bound to them depending on what kind of TEX item it actually is The latter three properties are used for operators only TEXPREC is the precedence of the operator a number between 0 and 999 Here the value itself is less important than the position with respect to other operators precedences The remaining properties will be described later First let s have a look at how a REDUCE expression arriving at TRI s main entry the function TeXvarpri is transformed through several levels of TRI processing For instance let us consider the expression x y which expands into a polynomial ei 12 x y 12 x yl y when evaluated REDUCE uses a special form to store an expression This form is called standard quotient because it in fact represents a quotient of two polynomials The contents of the following figure 1 shows the standard quotient form of our example SA CCK 1 C x 1 12 Xx 2 66 Xx 3 220 Xx 4 495 Xx 5 792 Xx 6 924 Xx 7 7
38. tioned earlier there are a few properties bound to each TEX item two of them dealing with line breaking The following list gives you a survey of these two properties and the values they can take CLASS one of the following class specifiers ORD ordinary symbols LOP large operators such as integrals BIN binary operators REL relational operators OPN opening symbols left parentheses CLO closing svmbols richt parentheses 9 PCT punctuation symbols INN inner TEX group delimiters TEXTAG this is either an atom describing an INN class or a list of widths defining the width of a TEX item where succeeding elements of the list will be used depending on the TeX inner group level i e the nesting of subscripts or superscripts Glue items are to be inserted between consecutive TEX items similar to what TEX does with its items The following table specifies for each left and right class of a TEX item the corresponding glue measure The glue item values have following meanings 0 no space 1 thin space 2 medium space and 3 thick space An asterisk means that this case never arises and values put in brackets indicate no space in the case of sub or superscripts Left Right Class Class ORD oP BIN meL OPN GLO POT m 0 0 0 0 1 C2 Actually a glue item is a list consisting of two elements a width info characterizing the width of this item in scaled points and a penalty to be
39. utput is produced only in line printer quality The simple idea to produce high quality output from REDUCE is to link REDUCE with Donald E Knuth s famous TEX typesetting language This draft re views our efforts in this direction We introduce a program written in REDUCE Lisp to typeset REDUCE formulas with TeX Our REDUCE TEX Interface incorporates three levels of TFX output without line breaking with line breaking and with line breaking plus indentation While speed without line breaking is comparable to that achieved l The authors are with Rechenzentrum der Universitat zu K ln University of Cologne Computer Center Abt Anwendungssoftware Application Software Department Robert Koch Strafe 10 5000 Koln 41 West Germany e with REDUCE s pretty printer line breaking consumes much more CPU time Never theless we reckon with a cost increase due to line breaking which is almost linear in the length of the expression to be broken This paper deals with some of the ideas and algorithms we have programmed and it summarizes some of the experiments we have made with our program Furthermore at the end of this paper we provide a small user s manual which gives a short introduction to the use of our REDUCE TEX Interface For simplicity s sake the name REDUCE TEX Interface will be abbreviated to TRI in this paper At this point we should mention major goals we pursue with TRI e We want to produce REDUCE output in types
Download Pdf Manuals
Related Search