STRING AND LIST y PROCESSING SAMPLER L.K. Flanigan W.E. Riddle Department of Computer and Communication Sciences University of Michigan Summer 1972 XTY o. q~ 3= I5w

"lsk uric~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /5o5lr

PREFACE This compilation of notes and short papers is the final result of a seminar, entitled "String and List Processing", which was given during the summer of 1972 in the Department of Computer and Communication Sciences under the guidance of Professors Flanigan and Riddle. The intent of the seminar was to allow students to pursue interests in the general area of string and list processing languages and facilities and to report the results of their work to the seminar. Some twenty students participated in the seminar, which met once a week, for three hours, for presentations and group discussions. Each participant making a presentation also produced an outline for his talk which was made available at the presentation. In addition, those taking the seminar for academic credit were required to hand in a final report which extended their outlines. The outlines and final reports produced are here gathered into one volume. Further, those who reported on list and string processing languages also each produced a sample program which demonstrates the use of that language which they discussed; these sample programs have also been included. The material presented here has been given minimal editing by Professors Flanigan and Riddle. We did attempt to correct all known logical errors in the content of each paper; we did not correct minor misspellings and puncuation errors which did not harm the understanding of a paper. In some instances the sentence structure is a bit ambiguous; as long as the correct interpretation could be determined, we left the original text unchanged. Note, however, that we did detach the sample programs from each paper and combined them into the final section of the volume; each paper still contains references to the "attached sample program", although it is not attached in the final version. The following page shows the topics presented in the seminar together with the names of those who presented them. We wish to thank these participants for their work and their presentations, which provided an enjoyable and informative seminar. We also wish to thank the additional seminar participants who, although they did not make presentations, provided a responsive audience and made the seminar even more informative. We were pleased with the seminar and enjoyed participating in it; we hope this printed record of the seminar will carry some of the flavor of the real thing. L.K. Flanigan W.E. Riddle i

STRING AND LIST PROCESSING SEMINAR I. Language Externals (5/18, 5/25) SLIP,IPL/V Lucier PL/I Unger LISP Flanigan SIMSCRIPT Rinn POP-2 Brindle II. Virtual Machine Capabilities (5/31) Riddle A. Data Types B. Order Codes C. Dynamic Storage Management III. Language Internals (5/31, 6/8, 6/15) LISP Hafner PL/I Hoffman SNOBOL Lift SIMSCRIPT Henriksen IV. Selected Applications (6/22, 6/28) UMMPS Hamilton GRAPHICS Bauer STDS Katz ii

TABLE OF CONTENTS Page I. Language Externals A. IPL-V I.A.1 B. MTS SLIP I.B.1 C. PL/I - String/List Facilities I.C.1 D. LISP I.D.1 E. SIMSCRIPT II I.E.1 F. POP-2 I.F.1 II. Dynamic Storage Management III. Language Internals A. PL/I III.A.1 B. LISP III.B.1 C. SIMSCRIPT III.C. 1 D. SNOBOL III.D.1 IV. Selected Applications A. MTS-UMMPS Storage Allocation IV.A.1 B. UMMPS Paging Algorithm IV.B.1 C. Michigan Graphics Interpreter IV.C.1 D. S.T.D.S. IV.D.1 V. Example Programs V.1 iii

I.A.1 W. E. Riddle 5/19/72 An Introduction to the IPL- V Programming Language SYMBOLS: A. GLOBAL SYMBOLS ~ unique throughout program ~ a letter followed by (at most) 4 digits, e.g. A14. two types 1. pre-defined HXXXX accumulators and special registers e.g. HO -"communication cell"- push-down-stack general-purpose register H1 -instruction address register, also push- down H2 -head of available space list (user never has to use) H5 -condition code register, value either + or - WXXXX working, temporary storage JXXXX names of basic routines (more on this below) 2. user-defined - global symbols, other than those starting with H,W, or J; used as identifiers B. LOCAL SYMBOLS. have the form 9-XXXX ~used as names of sublists - scope is local to list where used C. ADDRESSES numbers which are storage addresses provided by system (in examples below, blank indicates occurrence of a system provided address) DATA TERMS: hold a piece of data p Q DATA 0 - decimal integer 1 - decimal flt-pt 1value 2- alphanumeric Q - octal Q = I flags this as data in context where data is being expected.

I.A. CELLS: have a name and hold a value A. formatQ S LINK SYMB is the item stored in the cell LINK is a pointer to another cell Q is "designation prefix" and indicates amount of indirection needed to get value of cell Q = 0 value is SYMB itself Q = 1 value is SYMB field of cell named by this SYMB field (i.e. one-level indirection) Q = 2 two-level indirection P is "operation prefix", explained below. B. Any cell is a push-down stack. C. cell can hold an instruction P Q SYMB LINK operation indirection link I code indicator symbol address notation: let S be the symbol or value obtained from SYMB by indirect addressing. operation codes: O-EXECUTE S -take next instruction from location S (push S onto H1) 1-INPUT S -push S onto HO 2-OUTPUT S -pop a symbol from HO and put it into SYMB field of S 3-RESTORE S -pop the pushdown stack S 4-PRESERVE S -push down S (i.e. make it possible to store a symbol in S without destroying the present contents) 5-LOAD S -replace current symbol at top of HO by S (don't push) 6-STORE S -replace SYMB field of S by symbol at top of HO (don't pop) 7-BRANCH S -take next instruction at S if H5 is -; otherwise, next instruction is at LINK. D. cell can be an element of a list. last element on list has LINK value zero an element on the list may be interpreted as an instruction; or it may merely be a symbol, naming some data item, instruction, or list.

I.A.3 the first element of a list is a special header cell. LINK points to cell holding first item on list; zero indicates empty list.. SYMB is usually zero; when non-zero it names a list which is interpreted as holding the values and names of various attributes of the list. EXAMPLE LISTS I. L1 L2 @ L3 L4 -a It L5 L1 0 The blank LINK fields actually hold 9-1 addresses of next sequential element. 9-2 Another way to write the list, using 9-3 0 explicit links, would be: 9-1 21 D L 9-5 9-2 21 0 9-4 9-2 9Y6 9-2 21 G 9-5 9-1 9-4 9-6 9-3 0 The other lists would be similar. II. The list L6 9-4 9-1 9-2 9-3 0 9-4 0 L2 L3 L4 L5 0 9-1 21 D 9-2 21 D 9-2 21 G is the same as L1 except the attributes (SIZE, LARGE) and (COLOR, BROWN) have been associated with it.

I.A.4 III. The list structure L7 0 L3 L5 L1 0 would diagrammatically look like: L7 ROUTINES * list of cells which are interpreted as instructions * pre-defined routines are named JXXXX and are part of TPL system (most all are machine code) notation: Let items in HO stack be named 0, 1, 2,... from the top. Then the symbol in SYMB field of top item on HO is (0), etc. JO noop J1 execute (0) J2 test if (0)=(1) N.B. test symbol only, set H5 + if yes, - if no J3 set HS - J4 set H5 + J5 reverse HS J6 interchange (0) and (1) JllO V(1) + V(2) - V(O) pop up (3) + (1) two (4) + (2) V(O) is value of symbol in SYMB field of top of HO items J111 V(1) - V(2) + V(O) and pop up two items J112 V(1) * V(2) + V(O) and pop up two items J113 V(1) / V(2) + V(O) and pop up two items J114 test if V(O) = V(1) JllS test if V(O) > V(1) J121 V(1) + V(O) and pop up one item

I.A.5 EXAMPLE tPL-V PROGRAMS These programs calculate n!, the first one iteratively and the second one recursively. A. Assume that C1 has the value 1, Ml contains n, and Al is to receive answer. F1 50 M1 M1 - (0) 10 Al Al pushed onto HO Al = M1 00 J121 V(Ml) -+ V(A1) 9-1 50 Cl Cl + (0) 10 M1 M1 pushed onto HO IF(M1.EQ.1) GO TO 9-2 00 J115 Test V(M1) > V(C1) 70 9-2 Branch if false 50 Cl Cl + (0) 10 M1 M1 pushed onto HO M1 = M1-1 10 Ml M1 pushed onto HO 00 Jlll V(M1)-V(Cl) -+ V(M1) 50 Al Al + (0) 10 M1 M1 pushed onto HO Al = Al*Ml 10 Al Al pushed onto HO 00 J112 V(M1)*V (Al) + V (Al) 00 J3 Set H5 to - 70 9-1 Branch if H5 is GO TO 9-1 9-2 00 JO 0 Noop END lPL-V Language Annotation Equivalent FORTRAN B. Assume that: C1 contains the value 1; M1 contains X1, the name of the cell with the value n; and M2 contains X2, the name of the cell where the answer is to go. Fl 50 C1 Cl -+ (0) Initialize value 11 M2 (M2) pushed onto HO of X2 to 1 and 00 J121 V(C1) + V(X2) put X1 on top 51 M1 (M1) - (0) of stack. 00 Fll 0 Fll 40 W1 preserve V(W1) ) Push W2's (Xl's 10 W1 W1 pushed onto HO the first time thru) 00 J121 V(X1) -+ V(W1) current value onto W1 10 C1 C1 pushed onto HO If value pushed 00 J114 Test V(W1)=V(C1) was 1 then stop 70 F12 0 Branch if false recursing down. F12 10 Cl C1 pushed onto HO Set W2's value to 10 W1 W1 pushed onto HO ( Wl's current value 10 W2 W2 pushed onto HO minus 1 and leave the 00 J111 V(Wl)-V(C1) -+ V(W2) symbol W2 on HO. 00 F11 Keep recursing 30 W1 Restore Wl's value Form next product 51 M2 (M2) + (0) in the series 10 W1 W1 pushed onto HO1 1234-5.....n 11 M2 (M2) pushed onto HO and put its value 1 J112 0 V (W1)*V(X2) + V(X2) in X2 IPL-V Language Annotation In English

I.B.1 MTS SLIP Dean W. Lucier June 23, 1972

I.B.2 SLIP (Symmetric List Processor) was developed by Joseph Wizenbaum of M. I. T. while he was with General Electric in 1963. He didn't hide the fact that SLIP was derived from at least four earlier list processors, including IPL-V. From Newell's IPL-Vhe used the concept of a list of available space and many of the SLIP functions are the same as basic processes in IPL-V. While SLIP was originally developed for use on the IBM 7090, the principles remain the same for MTS, even though the cell structure has changed. The descriptions herein will be for the MTS implementation. SLIP is a list processing system distinguished by the symmetry of its lists; each element (cell) has both a forward and backward link as well as a datum. It is not an independent language, but is intended to be embedded in a high-level language like FORTRAN which gives it great flexibility. Most SLIP processes (functions) are written in FORTRAN, while the processes which actually deal with the cell structure, called primitives, are written in assembly language. The description of SLIP can be divided into two parts: 1. The data structure which contains the information to be manipulated. 2. The program structure which is the means of carrying out the manipulations. First, the cell structure as designed by Wizenbaum and implemented on MTS consists of a pair of consecutive doublewords. I LNKL R LNKR bAT UM SLIP CELL

I.B.3 The ID field is 3 bits long and designates what type of cell it represents by its numeric value: ID = 0: this is a normal cell containing a piece of data. = 1: the datum is the name of a list. = 2: this cell is the header of a list. = 3: this cell is a reader of a list. The LNKL and LNKR fields contain the addresses of the predecessor cell and successor cell, respectively. On every list there is exactly one header (ID=2) cell. Therefore, an empty list consists of one header cell which points to itself in both the LNKL and LNKR fields. The MRK field is 3 bits long and contains whatever information the user designs. It is not used by the SLIP routines. The DATUM field is 64 bits long, (one doubleword or two fullwords or eight bytes). In type 0 (ID=0O) cells, it may contain anything which the user can fit into 64 bits. A simple list looks like the following diagram: MIMO&R ADDRESS 01ooQo f o 0..10. o'o""-0100 O1O2 Q lo...l00oloo0 010060 l Toe oF uSi3R D 9- M LC- 1ST l USER DATUrM OF LST 0 [~ 0 0 (. _ _ _ _ _ _ _., T O~

I.B.4 Much of the power of list processing systems is drawn from the ability to process list structures. Therefore, the capability of creating one list and linking it to anotl er list, forming a sublist structure, must exist. Recall that a name cell (ID=l) has the name of a list in its datum field. In the MTS implementation, the datum of a name cell is divided into 4 fields as shown: LINK TO LI~NK TO | DArTMA OF HEADER EADR NAM CELL (ID=1) The first and third fields are three bits long each and are constant. The second and fourth fields are 29 bits each and each contains the address of the same header cell, thereby providing the link between lists. An example of a sublist structure is the following: O ioo C, I _ oloo.j Coooto ~,o.'.....2............... I- i I,,1 0oooro J OlOC0 1 Cooo 1 1 01001 OC 6 oioo8o

I.B.5 One might raise the question that when adding a cell where does it come from? In SLIP, there exists a list of available space (LAVS) which is actually a one-way linked list, i.e. when cells are returned to the list, they are linked to the bottom, and when they are retrieved, they come from the top of the list. This is possible since SLIP has two reserved fields within its language code which maintain the current addresses of the top and bottom cells of the LAVS. This scheme enables one to erase an entire list rather than each individual cell. This is due to the reference count field of the header cell of a list. The reference count is maintained as the DATUM portion of a type 2 cell. Each time a list becomes a sublist of another list, this reference count is incremented by one. If the "parent" list is erased and thereby attached to the LAVS, the routine for obtaining new cells from the LAVS will decrement the reference count by one, and if the result is zero, then the sublist is erased and linked to the bottom of the LAVS. If the result is greater than zero, it still remains as a sublist to some other list, and is not linked to the LAVS. These processes bring up the question of who is responsible for maintaining the pointers in the structures and the handling of LAVS and other niceties? SLIP has the routines to handle these responsibilities and therefore all the user has to do is ask for a list to be created or a cell to be inserted or erased. SLIP will obtain the cell or list, process the reference count, update pointers, etc. 1. at the time the name cells in the "parent" list are reused.

I.B.6 Finally, as part of the data structure services provided by SLIP, it provides working storage cells which can be used as common areas for all user subroutines in which information can be transfered. There are 100 of these cells in consecutive doubleword pair locations, consisting of 100 empty lists. Looking at the routines in the program structure part of SLIP, they consist of certain assembly language routines, which are called primitives, and the other routines which are written in FORTRAN, and are normally functions. The primitives extract directly the information from the cell and store the information into the cell and, consequently, are machine and cell structure design dependent, whereas the other high level language routines manipulate the lists by calling the primitives where needed. For example, a primitive must be used to obtain the memory address of a cell. Therefore, one can see how flexible SLIP is in that only the primitives, approximately 12 in all, need really be rewritten if the cell design is altered or a different make of computer is used. Like other list processing systems, SLIP allocates storage dynamically. Therefore, before any lists can be builttthe LAVS must be initialized. This is done by the routine INITAS, acting upon a block of storage provided by the user. The type of nearly every SLIP quantity and function should normally be DOUBLE PRECISION and explicitly declared for each SLIP function called by the user in his program. A few functions should be declared as INTEGER. Therefore, it is a good practice to refer to CC MEMO #M197 until one becomes familiar with the functions.

I.B.7 The following is an example for setting up a list of available space: DIMENSION SPACE (1000) COMMON AVSL,W(100) I = 1000 CALL INITAS (SPACE,I) This will create an LAVS of 500 cells and a set of empty lists W(1)...W(100) which can be used as public storage. The COMMON statement should be included in any user program. In order to create a list (empty initially), there are 3 types of statements which can be used: 1 CALL LIST (LA) 2 LB = LIST (LA) 3 LB = LIST (9) The value returned by LIST is the address of the header cell createdt stored in a double word. Therefore, the DOUBLE PRECISION symbolic variables, LA and LB, will contain this address after execution and can be used to refer to the list just created, for that reason. The argument, integer 9, causes the reference count to be set to zero in the new header cell. Otherwise, when 9 is not used, the reference count is initialized at 1. As noted before, the reference count is incremented by one when it is made a sublist of another list. Therefore, sublists initially should have a zero reference count, so that when linked as a sublist, resulting in an updating of the reference count, they will be erased if the "parent" list is erased. If the reference count of a sublist is initially one, and updated to two, the erasinq of the main

I.B.8 list will result in the reference count decrementing by 1 and not reaching zero, the necessary requirement for erasure. The statement used to erase a list is: CALL IRALST (LA) This decrements the reference count of a list, LA, by one and if the result is 0, it will erase it by linking it to the bottom of the LAVS. There are a number of functions for placing cells on an existing list. In all cases, the value returned is the address of the new cell obtained. STUFF = NEWTOP(DATUM,LA) STUFF = NEWBOT(DATUM,LA) The above statements will cause a new cell to be inserted at the top or bottom of list LA, and the datum portion of the field of the new cell to be filled by the contents of DATUM. A precaution to note here is that SLIP checks the contents of DATUM to determine if it is the address of a header cell. If it is, the cell being created becomes a name cell (ID=1) and the appropriate format is constructed. Therefore, the user must be sure there will be no conflict with his data and the addresses which could be generated. In most cases, this is not a problem. For example, the attached sample program uses the datum field in a manner in which the conflict should not arise. Suppose a cell needs to be inserted in a location on the list which is neither the top or bottom. This can be accomplished with either of the following two statements: STUFF = NXTRGT(DATUM,KEEP) STUFF = NXTLFT(DATUM,KEEP)

I.B.9 The first statement will obtain a cell from LAVS, and then insert it to the right (successor) of the cell whose address is contained in KEEP. Then the datum is stored in the new cell. Similarly, NXTLFT refers to the insertion left of the existing cell using the predecessor (LNKL) pointer. The information contained in a cell can be changed by using: STUFF = SUBST (DATUM,KEEP) This results in the contents of DATUM being placed in the cell whose address is in KEEP, and then the old contents of the cell are put in STUFF. Similarly, the following functions will place data in the top and bottom cells of a list: SUBSTP (DATUM,KEEP) SUBSBT (DATUM, KEEP) There exist other extravagant routines in building lists: LB = LSSCPY (LA) A list, LB, is created and is an exact copy of the list, LA, except for addresses. INLSTL (LA,KEEP) INLSTR (LA,KEEP) These reoutines insert an entire list (LA), except for the header cell of LA, as the predecessor (left) or successor (right) of the cell whose address is in KEEP. The list LA then becomes an empty list. For example, the bottom cell of list LA is linked to the cell specified by KEEP and the top cell of list LA is linked to the predecessor if INLSTL is used. CALL DELETE (KEEP)

I.B.10 This routine will erase the cell specified by KEEP and return as a value the contents of the datum field of the cell. The actual searching of a list is done by SLIP, after receiving a command from the user program. Therefore, in order to perform these read functions, SLIP requires a cell to be acquired from LAVS which he uses to keep track of the current cell in the list structure where the user is positioned. The reader cell (ID=3) has the following format: LPN TR LOFk R R LCT READ1 P C ELL The LPNTR field contains the address of the cell currently being pointed to. The LOFRDR contains the address of the header cell of the list currently being looked into. The LCNTR is a count of how many levels ("depth" of sublists) the reader has descended into the list structure. The level of the main list is represented by 0. Each time the reader descends into a sublist, he obtains a new reader cell and forms a stack by using the LINK field after bumping the level counters of previous readers in the stack. There are two types of scanning or advancing operations available in SLIP, linear and structural. In both cases, a reader for the list must be obtained by using: READER = LRDROV (MAIN)

I.B.11 READER contains the address of the initial (in case of a stack) reader cell for the list specified by MAIN. The mnemonics for the advance operations represent 3 parameters: 1. type of advance 2. type of cell being searched (target) 3. direction of advance For example: STUFF = ADVLEL (READER,FLAG) The first letter L signifies linear advance, whereas S is structural. The second letter L represents in the left direction (using predecessor links), whereas R is in the right direction. The target specification is the letter E which signifies a search for type 0 cells (ID = 0). The letter N represents name cell search and the letter W represents either type. The argument READER represents the reader cell for the list to be searched and FLAG designates a DOUBLE PRECISION variable which will be set to zero or non-zero depending on whether the search is successful or not. The following are some of the advancing operations: ADVLER (READER, FLAG) ADVLNL (READER, FLAG) ADVLWR (READER, FLAG) ADVSEL (READE R, FLAG) ADVSNR (READER, FLAG) ADVSWL (READER, FLAG)

I.B.12 For the linear advance, if the search is successful, the datum of the matching cell is returned as a value and the flag is set to zero. If a header cell is encountered before a match, the flag is set to non-zero and the value returned is zero. The linear advance moves sequentially down or up a list without descending into the sublists. The structural advance will descend into the sublists if a name cell is encountered and the target cell has not been found. If the target cell has not been found in the sublist, the reader returns to the point of descension in the "parent" list and continues the search from there. All this is done by SLIP before control is given back to the user program. The flag is only set to non-zero, implying failure to find the target, if the header cell of the main list is encountered. Some of the other routines concerning the reader are: REED (READER) returns the datum of the cell which READER is currently pointing to. INITRD (READER) forces the reader to point to the head of the current list. LVLRVT (READER) returns to main list at the point (cell) where it descended into the sublists. INITRD (LVLRVT (READER)) returns reader to header cell of main list. IRARDR (READER) the reader is erased and returned to LAVS. Looking at the attached program listing and results, the following functions are used: CALL SETRAC (SPACE, I) CALL SLPDMP (SPACE, I )

I.B.13 If the LAVS is exhausted and SETRAC has been previously called a SLIP DUMP will be produced. This dump (not a core dump) is formatted so that tracing through the list structure is easily accomplished, and also through the reader stack to determine which cell was currently being pointed to at the time. The function SLPDMP explicitly calls for a SLIP DUMP and is good for debugging purposes. Another debugging tool is the function F4TRBK, whcih has no arguments, but will receive control on any type of error, and produce a SLIP DUMP before giving control back to MTS. Some of the advantages of SLIP stem from its feature of being written almost entirely in a high level language. This makes it essentially machine independent, and easily imbedded into a language like FORTRAN. There is no extra compile time since the routines are loaded at execution time along with the user modules, which also makes it easy on core since only those modules used need to be loaded. In addition, the two-way linked lists allow lists to be bulk erased rather than each individual cell. The retrieval time for the bottom cell on a list is the same as the top cell and is independent of the length of the list. I feel SLIP would be quite valuable to a number of high level languages like PL/1 or COBOL where the user must perform all the operations required in list processing. Certainly, if the type of list structure SLIP produces fits the application or vice versa, having SLIP available would be ideal.

I. B. 14 Re ferences 1. A. Newell and F. M. Tonge, "An Introduction to Information Processing Language V", Programming Systems and Languages, edited by Saul Rosen. 2. J. Wizenbaun, "Symmetric List Processor", Comm. ACM, p. 524-544, 1963, no. 6. 3. Douglas K. Smith, "An Introduction to the List Processing Language SLIP", Programming Systems and Languages, edited by Saul Rosen. 4. ComputingCenter Memo #M197, University of Michigan, 10-19-71.

I.C.1 CCS 500 Spring 1972 J.A.Unger STRING AND LIST PROCKSSING FACILITIS OF PL/1 - AN rRNAL VIEW - A. INTRODUCTION When considering the string and list processing facilities of PL/1, the potential user must remember that PL/I is a general purpos language and not an amalgam of many special-purpose languages. Thus, although PL/1 can be used to solve almost any typ. of problem, in general there will be a "better" language for the solution of any particular problem. However, if the application to be implemented encompasses several functional areas having, for example, list processing and computational requirements, then PL/1 with its wide range of capabilities may be the most appropriate implementation vehicle. Because it is a general purpose language, the various "primitives" usnluay are exceedingly primitive, and the programmer is often forced to write detail coding for routines which would have been provided had a different language been chosen, This caveat is especially true when the list and string processing facilities of PL/i are being compared to the facilities of other string and list processing languages: a few powerful, basic manip-lations are provided, and it is the responsibility of the prograsmer to use these building blocks to oreate his own processing routines. B. STRING PROCSSI FACILITIES The following is a inimal set of operations required for the definition uad manipulation of string data,

I.C. 2 * Definition and initialization of variables and constants a Assignrmnt of values *Combination of strings Selection of substrings by position or content Determination of the current length of a string The following PL/1 features form th. basic support for the above set of opetions string Data Attrib - It is possible to define an identifier as string type data, either CRHACTER or BIT, to define its length and whether this length is fixed or VARTING, and to establish an initial value for the string. 2. String Data perators - The assignaent (=) and concatenation (I1) operators, the logical operators (, t, ), and the comparison operators (r=, =, eto.) can be used with string data as operands. 3. String Built-in Functions - Of the approximately 10 built-in functions that operate on string data, the most important and most useful are INDX), LENGTH, and SUBSTR. Before any string manipulation examples can be discussed, a few comments should be made about the more important operations and functions. The assignment operation is the copying of data from a source to a receiving string with anyt necessary padding/truncation on the right. If a fixed length receiving field is longer than the source field, then blanks will be inserted on the right if it is of CHARACTER type andi binary seross will be inserted on the right if it is of BIT type. If a VARYING receiving field is longer than the source field, no padding will occur since the current length field within the receiving string's dope vector will be set acoordingly. If the length df the receiving field is less than that of the sending fields then the xcess digit/bits will be truncated. There is

I.C.3 no truncation interrupt, so the programmer must test for possible truncation if such an occurrence would cause an error. Concatenation is the forming of one composite string from 2 or more strings; it can be thought of as a 2-step operation, the first being the formation of a temporary string and the second being the assignMent of that temporary string to the indicated receiving field. All the rules of assignment apply, and unintentional error may occur. For example, the following statements DKCLARK Si CHARACTER (3) INITAL ('ABC'), S2 CHARACR (2) INITIAL (,ID'), S3 CHARACTER (5); S3 = S3llS2 result in string S3 containing'ABCDI' at the completion of their execution. Note that if SI were defined DICLARZ SI CHARACTER (5) INITIAL ('ABC'), then the statement S3. Sltll 52; results in S3 containing'ABC' because S1 would have been padded with blanks during initialisation and the temporary string'ABC DE' would have been truncated upon assignment. The SUBSTR function is the selection of a portion of a string based on its relative position within that string. The general form of the function is SUBSTR (string, startElength3) where "string" is the name of the string to be operated upon, "start" indicates the starting location relative to the first position in the string (which is position 1), and the optional Wel,,-hU- indicates the number of units to be in the resultant substring. For example, if string STR were declared to contain'ABCDE' then the statement SUB S- UBSTR (STR,3,2) would result in SUB1 containing'CD'. SUBSTR is one of a class of Anction which

I.C. 4 can be used on the left-hand side of an assignment statement, and, when so used, is known as a pseudo-variable. Given the above definition of STR, if the statement SUBSTR (STR, 3,2) ='IF'; were executed, then the result in STR would be'ABEFE'. The INDEX function is used to locate a character or bit configuartion within the specified string. A numeric value indicating the starting position of the pattern is returned if the pattern is found; if it is not found, the value returned is sero. For example, if it were desired to locate the first blank character in string S, the following statement could be used LOC = INDEX (S,'')I The following examples demonstrate typical string processing manipulations and techniques: Example t The follewing code deletes all blanks from a string S by constructing a new string consisting of the P characters to the left of the blank concatenated with the characters which lie to the right of it. Statement numbers I and 2 will be repreatedly executed until no blanks remain in the string (a return of 0 froma the INDEX function). DO WHILE (INDEX (S,'),u, 0); P = INDEX (S,'') - It Sw SUBSR (S,.,P) IOSSTR (SP.2); aple 2. The following code reverses the characters in string S by treating the string as two symetric halves and interchanging the contents of the corresponding character positions, The loop control is L/2 since 2 characters are being moved on each iteration. Note that if L is odd the integer aritohetic used in determining the loop counter results in truncation but tbat the center character need not be interchanged and thus no error occurs.

I.C.5 L = LENGTH(S); DO I = 1 TO L/2t T = SUBSTR (S,I,1); SUBSTR (,I,1) = SUBSTR (S, L-L+i,1); SUBSTR (S,L-+,l 1) - T END Example 3, The following code performs initial verification of an input message and has been extracted from the primary message-handling module of an on-line system. mhen this module is invoked, a message has already been received and assembled in TRANSACTION and its length has been inserted in LENGTH. This code searches for the first non-blank character in the mnssagel if more than one character, special processing is performed. Otherwise, the 1-character transaction code is extracted. from TRANSACTION, and its validity is checked by comparing it to the allowable codes in TRANSACTION CODES. If it is valid, the non-sero value returned from the INDEX function is used as a subscript into the LUGAL IN PHASE and LEGAL FOR USER bit tables. DEC'LRE TRANSCATION CHAR(L_TRAN) EXTERNAL, LENGTH FIXgD BINARY EXTERNAL, TRANSACTION CODES CHAR(24) INITITA ('BSVCDGRPMLIJNAQWrEZXK)_ STATjC, LIP TAB (0,4) BIT (24) NALIGD) nTAL ('00000000000000!000001111'B,'111111111i10111111111111'B,'001111111111111111111111'B,'000000000000000000000000'B) STATIC, LEGAL IN PHASE (0,4,24) BIT(1) UNALIGNED DFIN LIP TAB, LFUFTAB T2) BIT (21) UNGNd INZTAL ('11111100010111111Xlll1'B,'1111111111ii11111111111i'B) STATIC, LEGAL FOR USER (2,24) BIT (1) UNALIGNED DEFINED LFU TAB, (PHASE, USER TYPE) FD BINARY; SUBSTR(TRANSCATION,ISNGTFl,1)' DO I 1 I TO LENGTH-I WIIE (SU(BSR(TRANSACTIONI,) -'')s 3m, J = INDEX (SUBSTR(TRANSACTION,I+l),'' )g IF J, i THEN GO TO BOI9! XACT CODE = SUBSTR(TRANSCATION,I,1 ) I = INDEX (TRANSACTION CODESXACT CODE); I? I = O THEmN GO TO EmROR8 IF LEGAL_IN PH ASE (PEHSE,I) THEN GO TO ERROR9; IF IL _FOR_SR THEN GO TO ERROR 1O0

I.C.6 C. LIST PROCEISSING FACILITIES In order to implement list processing applications, the following general types of capabilities are necessary: - ELament definition 0 Dynanic creation/deletion of elements * Modification of element contents * Selection of list elements according to contents or relative list position Since PL/I s not internded to be specifieally a list processing lanuguage (in fact, the list processing facilities wre added after the balance of the language design ws substantially complete), it inludes only the bdasic list processing mechanis, leaving to the progrmeru the coding of many neessary functions. For eaple, PL/1 does not provide a routine which automatically adds an element to a list. BHwver, it does provide prograner-ao"ssible pointer data andi, by peritting unlike data items to be combined into a logical unit, allows the programer to design and code his own list building routine. The BASD storage allocation data attribute specifies that storage is to be assigned to its identifier when that identifier is explicitly allocated (rather than when its containing block is atm-a) and that that storage is to be released when that identifier is explicitly freed (rather than when its containing block is terminated). Thus, the stateent DECLARE II BASKDI (IPR), can be used to identity attributes associated with flB and its substrwcture while providing prograuer control over ITW storage allocation. When a BASED variable is allocated, storage is obtained for an instance of that variable and a pointer is set to locate. the beginning of the obtained storage. For eaple, the statement

I.C.7 ALLOCATE IT results in an instantiation of TTk arnd the setting of IPTR to the starting location of this core. It is possible to explicitly name a different pointer variable to be set when an instance of a BAS variable is allocated. For instance, ALLOCATE ITEM SET (P), causes pointer variable P to point to the first byte of the obtained storage, leaving IPTR urndisturbed. The statement FREE T! causes the storage located by the current contents of IPTR to be released, while FRE3E P>)ITS causes the instance of ITM located by P to be released. Associated with each reference to a BASED variable, then, is either an explicit or implicit reference to a pointer variable. If only the BASTD variable is named in a statement, the implication is that the desired instance of the variable is located by the pointer variable on which it is based. If a different instance of the varriable is desired, then an eplicit pointer reference must be me. The following examples demonstrate typical list processing mnipulations and techniques, Example 2. The following user code builds a one-way linked list of ITEM elements. Since pointer variables contain addresses, it is necessary to define a bit configuation that is guaranteed to be the address of nothing. This is the NULL configuration, X'FF000000t. Since there must be some way to recognise an empty list or the end of a list, by convoenti on the NULL pointer indicates that there are no fonlowing elements.

I.C.8 DCLARE I ITRM BASED (I PTR), 2 DATA CHAR(50), 2 NEXT POINTER, (I BASE,IPREV) POINTER I BASE,I PREV - NULLI ALLOCATE ITZ4; IF I BASE - NULL THEN DO; I BASE-xi I PTR; I PREV I PTRt ELSE MOt I PREV+ITEM.NET = I PTR I PREYV - IPTR END; ITEM. DATA - STUFFt ITEM.NETr = NULLt One of the drawbacks of dynamic list element allocation is that it is often difficult if not impossible to predict the amount of storage required for a particular program execution; reserving a fixed anunt may result in wasted sproae, or, oonversely, the reserved core may not be sufficient. Egr specifying that a particular area is to be used for the allocation of BSED variables, the PL/1 list processing programmer is able to control the aount of storage allocated to a list and can take corrective action if it is exceeded, The following declaration DCLARE I AREA AREAt reserves I AREA for the allocation of BASED variables, uad the statement ALLOCATE rITE IN (I AREA); causes space for one instance of ITEM to be obtained from that associated with the variable I AREA. As before, it is possible to set a pointer other than that named in the declaration of the BASED variable, ALLOCATE ITEM IN (.I_AA) ST (P); If no sise is specified in the area declaration, a default sise of 1000 bytes is assigned, The amount of AREA storage can be eplicitly specified either absolutely or relative to the BASED variable(s) it is to contain, For example, DELAI ZARI AREA (5g0o); causes 5000 bytes of area storage to be associated with I AREA, while the statement

I.C.9 D:CLLS I LRA AREA ((100) rM), oauses sufficient storage to contain 100 instawes of IT13 to be associated with I ARA. If space is not available within the specified area, the AREA ON condition will be raised, and it is the responsibility of the prograer to intercept this interrupt and to take appropriate action. Thus, at some initial point in the program should be a statement such as ON ARA GO TO MPTI A so that if an attempt is mde to allocate an rrIEM that cannot be contained in I AREA, control will be transferred to the designated routine. byr cobining the BASED and AREA attributes, it is possible to implement an OFFSET linkage scheme. (An OFFSET looator variable gives the displacement past the beginning of a named basd variable.) WEmle 2. The following code builds a one-wy linked list using an offset linkage scheme. Note that the based area A must be explicitly allocated because storage is not associated with it at prologue times this is in contrast to PEuaple I in which I AREA was deolared with the default attribute of AUTOMATIC uad had storage associated with it when its contairning block was entered. Note also that the declaration of the OFFSET variables, NEXT and I BASE, must specify the based area referenced by the offset. Two other cooments should be made about this example; the first is that in the explicit pointer referene, LIN1- ITiM. NEXT - I_PTR LINK must be a pointer and must contain a pointer value. The seoond is that an offest variable can be set only by assigrmnt of a pointer variable to it.

I.C. 10 DeCLARE A AREA BASED (APTR), I ITD4 BASED (I Pm), 2 DATA CHAR T50) 2 NMr OFFSET (A), LINK POL, I_BASE OFFSET (A); AJLIOCATE At I-BASR NULL; oN AREGO TO, MPT_ A, ALLOCATE, LLOCXATE IN (A); IF I_BASE NU LL THEN DO; I BASE = IPTR LINK = I_PTR, LINK —?IT, EX. = I PTR LINK = I_PTRm END; ITEC. DATA a STUFF; ITEM.NKX - NUL. _ZPTrA, W'ITE FILE (LISTFI ) FROM (A); A = 1NPTT; IASE = NULL L GO TO ALLOCAT;g In the V1-T_ Y A routine above, the statement A = 10GPTY; causes the extent of A, which measures the number of bytes within A already allocated, to be reset to sero, effectively freeing all the based variables within A. Thus, when the ARE ON condition is recognised, the current contents of A are written onto an external file, and A is emptied so that additional allocations can be performed. Notice that since this chain linkage is via displacements past the beginning of A, input/output operations can be performed 4ithout destroying the chain. The power of the PL/1 list processing facility lies in its flexibility. Because the programmer must define anf msintain his own chains, he is free to logically struicture his data in the way most appropriate to his particular application. Possible list strictures which can be built and maintained using PL/I

I.C.11 ares one-way linked list, multithreded list, ring, binary tree, etc. ampnl. 32 In defining a tree structure, it is possible for each node to contain pointers to all its children. Figure 1 below is a schematic of such a representation. If the tree structure has a fixed branching pattern, e.g., a binary tree, then such an approach is reasonable, If, however, the number of daughter nodes associated with any one node is variable, then such a structure becomes unwieldy and difficult to manage. In such cases, each node contains exactly three pointers, to its parent, to its next sibling, and to its first child. Figure 2 below is a schematic Of such a logical structure, and the PL/ procedure CHAIN will create a tree structure of this sort. It is assumed that elements are presented to GNAIN in order from top to bottom, left to right. The placement of the current element is determined by examining its level number. If the level number is 1, then this node is the highest node. Otherwise there are 3 possibilities, this is a sister of the most recently-added node (current level number = previous level number), this node is a daughter of the most recently-added node (current level number>e previous level number), or this node is a sister of some prOviously-added node (current level nmber <previous level nmber). A A B C B'o D Figure 1 Figure 2

I.C.12 CHUIN, PROCEDURE (RELEMNT); D3CLAR 1 EIINT, 2 LEVL_ NtUMBR FmE, 2 IDENTFIR CHAR (*), i TRmE NOD BSED (CU ), 2 DAUGHTZE POINTER, 2 SISR PONTR, 2 MOTR POINTR, 2- IEVEL NMMBgR N FD, 2. IDWrnIER CHAR (LENGTH ( NT. IDNTI7IER)), LAST POINTER STATIC TRNAL, TEP POINTER; ALLOCATS TRl NODE; TREE~NODS. LEVEL NUNBER = JELEMENT. LEL NUMBER; TRE _NOIE* IDENT IFIE =.ELENT IDETIIR IF TiEE NODE. VELNUMRR = I THI DO MOTDAUGER NULL; LiDUrt CU lRRlT 4 SISTER = NULL 1AST = C UKRRi T RETURN; IF T1RESX NODE. LEVEL, NIMEIR I LAST - TREENODE. mLVEL_ 3ER THmN DO; LAST - SISTER, CURRENT; MOTR LAST- MOTHER; GO TO L;s ENDI IF TRNODE. LEVIE_NUMB > LAST -- TEE NOE. LVEL_ NU THEN DOt LIST — DAGR = CURREN T MOTHER, LAST; GO TO Li;l DOm (L - TR_ NOD. EVEL NUBER> TNOD. LEVEL_)) TOW m LAST; LAST LAST —MOTHER; LST'TR NO L t IFAMT-aTR ~ NOD~.L~VL N~- ~- TRES —R NODE97N.LVCL UMBMR THNg LAST = TMP; LAST-;:SIS=TER S CURNT MOTHER = LAST - MOTBER; DAUGHTER = N~UL; SISTER = NUtLL LAST a CURRIT; END CHkIN; Example 4. It is possible to combine simple list structures in PL/1 and to define and manipulate a compound structure. For example. the struct ture represented in Figure 3 blow consists of ~ two-way linked list

I.C. 13 with rings attached to eaoh node. In this eample, this structure rspresents the logical relationships among corporate data; in the twoway list is stored data about corporate divisions, while each ring corresponds to the departments within a division. The following code assoe that the lists have already been oreated and that the nodes are in numeric order on division or department code. The prooedure RETRIEVE is called to access a specified node and return the indicated field value. An accessing bias is assnmed, and it is anticipated that division requests are likely to be clustered; that is, the division currently requested is likely to be close to that previously requested, and thus the current search starts where the previous search ended. RERIEVE searches up or down the division chain intil the desired division is located and then either searches the department ring until the indicated department is found or simply roetans the requested division value. 4,19 Figure 3 0 Er~RIEVE PROCEIU (CODEI,CODE2, STATISTIC) RTURNiS (VALUE); DICLARE CODl1 PICTURE (A999), CODZ2 PICTURE (A999), STATISTIC FIFD, VALUE FIXED (10,2), TANDI)M POINTER STATIC TERNAl INITIAL (HAD), HEAD POIRNT STATIC EXTERNA, I DIVISION BASE) (TAND~I), 2 UP POINTR, 2 DOWN POINTER, 2 COnr PICTUE (A999), 2 DPTCHIN POINTR, 2 VAL(5) FInD (10,2),

I.C. 1 I DEPARTMENT BSE (DEPT RING), 2 NE POINTE, - 2: PcmR (A999), 2 VALU ( ( (10,2) LU IF CODEi m DIVISION.CODE THEN GO TO DIV FOUND; IF COD1 > DIVISION.CODE THEN DO; TAND 11M DIVISIO.DW;I IF TANDIM = NULL I COD1 < DIfISION.CODE THEN DO L3: TANDE( m HLDW SIGNAL CONDITION (NOT_FOUND); END; GO TO LI; END; TANDEM s DIYISION.UPt IF TAsD m NULL CODEI DIVISION.CODE THEi GO TO L31 E1S5 GO TO LIt DIVISION FOUNDN IF0 CO2 - 0 TEEN DOI VALUE a DIVISIONVALTUJ(STATISTIC) DEPT RING = DEPTCHAIN; 14t IF CODE2 = DIPT CODE THEN GO TO DPT FOND DEPT RING = DEPARTMZ. S IF IWT RING - DEFPT CHAIN THEN GO TO I3; GO TO If1 DEPT FOUND: VAL 3C DIPARTMZN.VALUC(STATISTIC) D. CONCLUSION Many special purpose lnguages have ben designed to solve specific problms, but their design goals have led to rather rigid data organisations d thus to reduced general applicability. PL/, being a general pwrpose lamguage, is generally applicable to any type of probla. While it allows the prograrme great flexibility in smanipulating data, it does impose on hi the coding of functions considered as primitives in other languages. This is especially true when its list and string pDcCovsing facilities ar being insdrd, for only the eost bsic operations ar provided.

I.C.15 FL/I Referwce Msul, IBa Systrm/360, IM Pern Number C28-8201 PrLL -t'sde IB Systm/360 Operating ystan, IBM norm Ilson, Mark, The f I.mg - Ariais nd valuatio The University of Miol cens""' f asmer Conference adivaned topics corse in Computer ad Prograu Organition, Jim. 19-30, 1967 FlPaigan, Larry K., Note on the I PL/ ULgge, iversity of Micbigan, JmnA 1I, npub Lawson, Harold W.,"PL/I List Prooessing", CACM 10,358, 1967 Wegner, Peter, Pro esg Inforuation Structures, and Manchin Orguan~satiea -McGrav, Now Tork, N.T., I

I.D.1 II:. LISP L. K. Flanigan 5/25/72 In using a digital computer for numerically oriented tasks, a programmer usually arranges the data to correspond in some reasonable fashion to the linear layout of the computer memory. The data structure most used is that of the n-dimensional array, where given n subscripts a simple computation produces a single displacement for the actual reference to memory. Most algebraic compilers have such data structures as part of the language they accept, thus making it quite easy to use these structures. At the same time, these data structures are limited in their usefulness, since both the structure (here the number of dimensions) and the size are fixed at the time the structure is created; and this time of creation is often durin translation, rather than during execution, of a program. These structures have, nonetheless, served well in numerically oriented tasks. If, however, one turns to areas such as symbol manipulation, inrformation retrieval, language translation, artificial intellgence, and so on, one quickly finds that the usual data structures are unable to handle the demands of the programs. This occurs both due to the fixed size of the structures and to the nature of the structure. That is, in the above areas we find that the size of the data may vary tremendously, from moment to moment during execution, an. ibecomes imperative to have variable-size data structures and to be able to create and destroy these data structures at will during execution. Thus, the discipline by which memory is used must be dynamic, at any given time allowing the current program to accuire more memory or give up memory (but be able to retrieve it later if needed). There is no reason why n-dimensional arrays could not be handled in a dynamic manner, being created upon demand and destroyed w-.en. the need.for them disappears; this is, in fact, possible in most recent operating systems. However, the fact that arrays have a fixed structure denies these data structures the utility necessary for symbol manipulation and other such applications. In fact, in many nonnumeric computer applications, it is the structure, and not tshe value, of the data which is manipulated. Consider, as an example, the

I.D.2 organization of an encyclopedia. Here we have the gross structure: paragraph = set of sentences section = set of paragraphs volume = set of sections encyclopedia = set of volumes where we assume the sentence as the basic element. Over all this structure is imposed the usual ordering of inrormation by aDihabetic cri.eria a. several levels; a dictionary produces keys for finding specific sections. Note, now, that the DrobZlem of information retrieval is one of structure; that is, obtaining information from the encyclopedia (as a data structure) is independent of the specific information (except for keywords used in a dictionary search) and dependent upon the structure of the data. To add new elements to the encyclopedia, it is necessary to insert new data at several levels (volume, section, paragraph, sentence); fixed structures are not convenient for such tasks. To handle data in which structure, as well as content, is important, progranmmers have turned to list representations of the data. Lists (and list structures) provide the flexibility needed, often at the cost of storage (for pointers) and time (for list processing). t is interesting to note that to solve the problems of storage handli g in multiprogranmming and timesharing systems, with their dynamic demand. upon memory, these systems are in general using list-type storage organization. To make the use of list structures readily available, a number of list processors have been produced. These processors tend to fall into one of two groups: those that are part of an algebraic ianguage (often via subroutines), such as FLPL (4) or SLIP (5); and those that are written to directly manipulate lists and list structurec of varying types, such a IPL-V (6), CORAL (7), L~ (S), and rS? 1.5 (3, 10, 11) or LISP 2 (12, 13). Wc will here consider only IS? 1.S; for comparisons 9f the various list processors, see rCf'arcnces 14 cand 15. For a general introduction to list processing independent of particular languages, see Foster (3). Also, the section on lst and string processing in Rosen (1) contains several papers of inte~est.

I.D.3 tn the remainder of this paper, "LISP 1.5" will be abbreviated to LISP is a formal mathematical language, designed originaily to represent the partial recursive functions defined on a class of symbolic expressions known as S-expressions (ii). Programs in LISP are written as S-expressions, and data in LISP is also in the form of S-expressions. LISP has been applied to a large number of non-numeric areas (13). The most elementary type of S-expression is The atomic symbol or the atom. An atomic symbol is'a string of one to thirty capital alphabetic characters (A...Z) and/or numeric characters (0...9), the first of'which is alphabetic. Such symbols are atomic in tha' they are viewed as distinct, separate entities in LISP. (n a tomic symbol may Itself represent a complex structure; it is atomic because it is viewed as a single element, and its structure is thus not part of the structure of containing elements.) An S-expression is built out c: atomic symbols and the three delimiters "(",")", and "." as follows: a. An atomic symbol is an S-expression; b. If s1 and s2 are S-expressions, then (s1.s2) is an S-ex- ressson. Only expressions constructed from application of these two rules are S-expressions. Some sample S-expressions are: A (A.B) (A. (B.C)) ((A.B).C) ((A.B).(C.D)) ((X.Y).(X.(Y.(Z.A)))) Internally, S-expressions are represented as binary trees (i.e., as tree structures in which each:rcde has two branches). Because o tLi's, there is a graphical notation (9,16) which indicates this type f: structure and which often aids in understanding LISP struc.res. in this notation, we represent each node in the binary tree s"ruc-ure with the symbol

I.D.4 which indicates The e t. anfd rig. ranches from the node. or an atomic symbol, we simply write in the symbo', so that (A.B) is represented as IA B (Such notation should not be confused with the true situation; an atomic symbol is represented internally as a ponnter to the de:initio: of the symbol.) Figure Il-i gives more examples of the grahiical structure. Mote in Ite last two examples of Figure II-i that subexpressions may or may not be repeated in the structure without effect upon the S-expression. The dot notation as defined above is sufficient to reDresent all list structures in LISP and is the basic concept of the prograrming language. For convenierce, however, LISP allows a second way to writA S-expressions: that of list notation. A list is written in he form (SS2S37' 2' 3 n or in the form (s 2 S25s 3l -sn) where1 represents one or more blanks where s. is an S-expression. Such a list is internreted as the S-expression (s1.(s2 (s.(3( (s.NIL)..)))) where NIL is a special atomic symbol recognized as the terminator of a list. The empty list () and NIL represent the same element. Thus we have: (A B) - (A.(B.NIL)) (A B C) - (A.(B.(C.NIL))) (A)- (A.NIL) A list may have sublists: (A (B C)) - (A.((B.(C.NIL)).NIL)) ((A B) C) = ((A.(B.NiL)).NIL) ((A) (B))' ((A.NIL).((B.NIL).NiL)) ((A) B) - ((A.NIL).(B.NIL))

"Z jo ~ I Tad -I I O"aX T *j A./ I L~_ S_ o 0 | v' (((a'o)'E)'Y) i i a(i a i 1 I Ii ~ /fi i X V I ('o(D'v)~)) j~j J' I (D,( Y))

I.D.6 AA _~ ~ ~~~ A 1 i,.... \!/ ((A.B).(A.B)) [....,i A 2 f Figu2e I-i: Pert 2 of 2.

I.D.7 _-'a ~V, on ot nota+<on may be combined in w'i ing S-ex C S:ohS (. (_. )) - - (A. ((B.C) IL)) (A (3.C).(D A.((B3.C).:o te that any list structure or S-exDression may be writern in -ne dot notarion, and thus any S-exDression may be converted to t he sure dot not.ati on. Not all S-ex ressions may be writLen i. _s notat on, ncwever. In particular, a list structure ca.n e wr -ten in list notation only if each sublist, and the list self, te..r naes with a NIL. Thus, (A.B) cannot be written in list notation. Fig ue 1I-2 shows the graphics for some list and mixed notation S-exDressions. As stated earlier, LIS? is a language in whicn runctions of S-exp-essions may be written; we now introduce so.me elementary functions of S-exDressons. Function. names will be written iten wi lower case letters; their arguments will be piaced in square brackets seara-ted by seemicolons. S-expressions will be written with capital leters as previously defined.:-e f-rst elementary function is one which constructs S-express-ons ana is.ence named cons. It has two arguments from which it bulids an S-expression: consiX;Y] = (X.Y) cons[(A.B);C] = ((A.B).C) Note that the arguments and the value of cons are S-expressions; hence, composition is possible: ccns[cons[A;B];C] = ((A.B).C) cons[(A);cons[B;NIL]i = ((A).(B.NIL)) = ((A).(B)) Two additional primitive functions, car and cdr, are defined ro produce sulexpressions of an S-expression; they each have a sinzle argument, and each is undefined if the argum.entr is atom.ic. They are defined by: car (A.B)3 = A cdr[(A.B)3 = B

t/!~ ~~~~~! $ o T cape'g-IT acres~ /t\ _ i _ ~ f i J /I' ii Hi i' ( 1 (v). t, I (() (() (V)) 1, 1 1 j Y~~~~~~~~~~~j A'I t~~~~~~~~~~~~~~~~~~~~~~'' IT 7 /LN a, F —— vT s I rci i Ii.i i t i J~~~~~ / I' 1 7 - i$,I i., /1\~ ~ ~ ~~~~~~~\,.,. _ 8' a I

t i"-"- "-'" -,....,, C) ( ) C) I(':L::::1 > 0'~-L,- K.. r:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~; t —I~~~~~~~~~~~~~~~~~~~~~t I-4JC)Cr - I -t ii 1/~/ ~"** L..... V -i'(J, —I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' ro /...... / -.. "' L.......... l,j.. \i~~~~~~~ rL) C, I..~~~~~~~~~~~~~~~~~~~~~~.. _ (1 j._ I~~~~~~~~~~~~~~~~~~~~~~~~~~~,

t', Cr~ C; [-' f Cn /! i.,%. r: I ( I f, L1 F': bh f. %cJ'~1::J C0 j.' [,, p, h~.:'I'O C..O rt rt -'' r[ r ~ C: ij,r,r; Pc~ rt (3 C) (, ~ O, O~:J (L: r-'~ r -, f'-;::'' r I (f! ~ ~ " t fF:.:::~,,J~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~::'j rJ ~:',j ~.i (-;;':'.I..)''];]; " tJr} (; (;~: rt [J~.,; j (;; fI! f~ - In - "'- ~, ri r-I r' r,'J ~'I r —1J r-" r C! r-1 F....'. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~'ii I' ('~ 0> (~ "X- tq'", -".-. f;' " t;-; ~< ~' t )I ~5 r -'';,..0 C:.L r:t.':::,I C~:i L.. t-!.T ill C/ L.. I LII )J C ) ~ r','I':g t" p;'~5:5 tr' t' *'-I t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 21 r -~~~~~~~~~~~ C' I t ~f ti; C,:; C 1,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'1 [l I7 ['"] I) x.... ).ir,3 11 r —f (j II ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1 C~~~~~~~~~~ t-' ~ r~~~~~~~~~}j ~'' < ~T:'] i'' 0i:! -- b_ O: C.'t: ~r tl~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' s':~ t.. p t, ti,i t. J ~ 1 )J' V, (l~~~~~~~~~~~~~r pt I 0'~~~~~~~~~~~~~ I/ L.1 C~~~~~~~~~~~~r I, C~~~~~/:: t~,1 J1 o ~, ~,''I~~~~~~~~~~~~~~~~~~4 o-i III I II: - r.' ~-i,)' ~ 3",J I r t" O [ -''. O t_ t_~ H':I;' t:' (,[' O:'~ rf O ~q~I 3 t..~ ] f ~ J tJ -., G, C-';'5;.f:C/ g;, V:1 () ~- _ 5 ~' 1 t, ~)".,;3:5, O C'I'- ~ t t-' G -, I! tli cn, —f, (: t'.C/' ~ llf,3!t t i-l 0' J t'., f:; L. kC Z'i. () k: tj f.I, O] I.r _ ~',j: Ji LJj C. t,,, (,;~ P ~'' (O'I D'', (' t' C~~~~~~~~~~~~t - J,'::. t~.... "!' l't Cut-'. (b t', 0 1 0 1Jr/ j't, I:!~:C,, <: 6,f~ ta0t'G tJ',.' t', f:'~ ~S'; U~(. (I' i',3 ~;. Cv [t-' fi ~ CaLOrt CI-, U)' J'[ rt ~ P t','.J f(;'t rs f~'~Ci (:-),1',~., e( fu f: Cai: (iC,':I 5 ) ii 5 t" 6 tli~~ CO tr { "~ 6 t t: "; ( [:J~'j'-I fL j ~:5C I"r' r. ~~~~~~~~~~~'~ -.C,' ( (-" P''. ~ L'~ if, t ~~~~~~'~ ~ ~ ~ ~ ~ ~ ~ ~ ~ t rl rt i J ~l'I... p t t'C, l).1' I t t i; I: I tr ) It)~~~~~~~~~(. C ~~. (L Fl i; o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I. t'. ~, J p~?~~~~~~~~~~~~~~~~~~~~~(' i )' 1 ~' )' f': t -~ t'. /', 1 ~,~~ ~

I.D. 11 C........ \ - _..'~~~~~~~~\ r \, - * 21 /,- __ _ ___)\ L_~ ~ ~ ~ ~..__, t ~ ~ ~ ~~~~~~~~~~~~~'",'....;''~~~ ~- --— "

' " ~ r,,,' 3 r-t ~,'-~ ( (:' (~ (" t'.' j, I (')' I C. [~ t J'L! f:, *t,~ ~:, r l'-~ (.' ~', t' >' C,-.' t - C' r. ~;,:?,~ ~1~ ~, t j'L; C:~ t" ~',_,! (~ (..:,:-' (: [, r - r,' ~ j, [.,r~ (7, l;:-~' ()';': t'. ~',.. t i!, ~.:~ i" ( ~J r'.. ct t5 f!, C.',',} f..'.'..", C) 1'' t' OJ U: Cu f~ ~ - [':) C) r'-,,', [' r ~ C) (.? t-' ~-" (':., rt'tJ (~, t ( "; j',,",.. ~'':i [: ~ t r! r'~ ~.~ r ~ I ~-~'',, —-,',.');.'~ r i r[ r'~ 0 ~'1 t'- ~ t, (", t,' F'. C) L) ~ ~~ ~:~ ~,"'i r, ~ I~ i', ~I (": r' t" C) 6: ~'~?,''~'' C,; t ~:~ [-'~.:' C) ~'],-,' c_) /,;,:,,,-':~-, "S r-'~ C ) f: J Ci,,-, r[ I'. [,:,,,. [., c L)''1 ~,. 1:'~'I ~ ]!. J $'J C ) (.~ rJ:i (:.; C;]'k.l ~',:'i [: J''-''L~! " i.'~ of); () ~" ~ i 4. ~,..- ~'u v (~; o c..,'s r,, (i~,~'s (~; (,~,',..,.,.,, ~-J (? (' t" C:,~ ~ ~ () V t ],... (:2 Ii ('D r"-~ ["1, t:, fil r J (h i:~ (t~ ~':,' ~ J J-" ~LJ ~ F,:. t-'.;" [' ""'"- C~, ~-C -~- C,) ~ k; (~) t.... () (.~.'.~ J'. r J ~?.,'~ ~:~,', ~'~; t'"~. (.'q:] Ii r -~,~'..5 ~.'],:~:- el ~, ~.~ (g f''~ t'. C):~''3'k.~ r t ('., C, ~!:'.:-~ ~:; ( ~ r,,,'; C~ ~ S (;";:',J. 0 r,,'~ ~... C: (~ ~ ~ (~ r l t', (U I'- ~'~ L', r,) C;', C.~' ~ C) F~, ~)' ~j (!, (~ r ~;.: ~ l,,'-~ F''~ J'. c. f",,, ~j r.,; ~' ~,, [~., i', (r, ~:~,..... k~ (hi'; [':.,j t., rJ,..,~ [~, I-" L ~ ~ (,~ (") (.:'L~ t":' ". ~ (,~ CO r''t r: r'l! J;i:'i'..:-.!,. UI:;'-:i (' (.) t', ~j C, ~ j', }'. 0 (t; tl, (-:* " t'-...... ~,:J ~ t'. C ) rl ~? [~ ~'~,:~' }' rl ~ ~./ I } C:. (.: r'~ r~ [], t., ~' L ~ r-J' I'" ~'J'''.~ ~-: 5' ~i r.~ r:',',,. j. "; }', f,:. (t~ ~J ~.; 0 ~,') C.~ t-' "-.:,.. C~ ~: (~ f' ~ (.) r., ~ J' r (') }'. i: t.) C'.~'l r l ['!: t' t_ ~'~ (,.' t' t''i (' I',':'..- (:'s r',,('',..; 1'] f:' ~ ~ L.~ ~j 0~; ~ i~.: r I',~),( [': r. ~' i;; f,' () f' ~ t~ r -~ i C~. fi~ r-~ ~.: f'~"'~' 0 ~ t' r. ~, 0'C, 4-',' C:;:i f }'. t'- t' Ci,.-,. ~tt () L, ~.~ r ~ t" C;:i, j' J' (.'.'. f'~. () ('~ r', I'- ~; },'-:j L ~ C (:'' ~'~ r'i J;: i j, r t 5''.''.' }i~ "'i ~ (~ II f', C) (.:': ~'-..::J (~ (j ~' r',., I" "-' ~" C $': ~':-' (,' (' f' ( ) r t }'. ~-" ~ ~ ( )' ~'.,,' (:" C,'~ I',:' ('J [: ~ i~' I'l- }'. (.': 0,.,, ~ t ~'; (.; r'~ O,,:. ". r rt'~ }i,'J ~:''-:! ir~ (,. ~ () }i, i'. }'- C, 0 ~ ~ (. ~ () C.)' J ('-~'?"~ (: I'. C) (-) ~ i: C)' i,; r,, (:, (',~ ".~'5 C:' () ~'' ~: [: i' C'~ (~'' C:~ [' ~J f~ <: I'. ~j (. " U, ~' (J ~ J (ri:, i'..' ~r ~'i ~"!'. f l (; C. ~ C'., ~r, t'- ~J 1" t" t i~ },.''~) s, }' (J (", (., r l I"'' F'.~, [~' (; 6, r l'~ ~j'5 (~,, rl t'. I'..:: (), [", *:;' 3' ~' C,. C) U: t' t'. ~ (., [ ~'.i f! C) (!, ~', C.;'! [: f';' [' }',. "-' r [:':.~ c'.'~. I'~', () }'.'~, ~,,'l,,, It;'~' (,!, (': r rt C)'~'': C~:S r' },. ~'',' }'.,-. ~ I: (': (,.,'. () f. r;-~ }'. i" C~' (~ ~':':4,,',, ~' f.. f''5 (, (.,'l' i l:i; ['; }' ~ ('I,:, }' *' i:..' I f' ~j C~ (t, It:' I ~ t, (;~ (: ~.;,r ~ - ~ ~, ~,,,, ~',' ~'.,''l t' (. (~ (', ~',.: rl L)..... }'. (t..... I"': ~',~ [' U~' ~' (i~ ('~ (; r',:;, (. i" t'1'J''tJ I" ~(;):J' L'~ *'C[; I

I.D.13 cone by using.te iambda notaton of C.hurch (23). in hnis notaionG, an er: ess on like y + 5x is.called a forrm.. To convert a r-orm to a unac i on, one must. specify the dummry arguments and the form. This s. c-e via the not0 ation lambdacx;x x2;...;x 3;f] wnere the x. are arguments and f is a form. Thus, amcafib Z' x;y];y+ Sx]'s te name of a function or two arguments whose value is round by subsitu. ng the values of thQ argcuments in o the form y+Sx. Nioe that we may now add the values of the arguments to the above notatio to get a function value: lambda[[x;y];y+5x][3;10] = 25 That is, lambda[;xl...;xn ];f] is the na.e of a function, while lambdaLixl;...; Xn];f] [Y!;;Yn is the value of the function for the argument values [y;...;. Therefore, the definition of absolute value now becomes lambda[ Cx;;[x<O+-x;T-t+x and this may be applied to arguments. o use this notation with recursive function definitions re uires further notation, since we.must be able within the defin. ti n o indicate (recursively) that the whole definition is to be apDleed. To solve this problem, the label notation is introduced: label [a;e] states thaI the expression e has.he name a. We may now write.: previous function definitions as follows (this is now LS?-i ke notation): label[ff;!lambda[[x];[atom[xx-;T-+ffE[carxExl]J label[abs; lambda[ [x]; [x<O+-x;Txj ] label[fact;lambda[[nn];[n.<0c l;T+n;fact[n-i] ] 3] labelEgcd;lambda[dx;y]; [x>y ygcdCy;xy ]; remCy;x]O=x;T+gcdC[rem[y;x];x] ]

I.D.14 Obvi~ously, one of the problems in writing LISP progrars is pror,cr bracketing: One may write function definitions using eit.er the lambda or the label format; the label format is needed only if the.unct.ion is to be given a name. This naming is necessary in recursive function definitions since one must be able to reference the definition from within the definition. Now let us consider some functions which operate on S-expressions: a. subst [x;y;z] This function gives the result of substituting the S-expressic x for all occurrences of the atomic symbol y in the S-expression z: the definition is suDst - lambda[[x;y;zl];[atom[z] L eq[ z;y ]+x;T+z;T+ cons[subst[x;y;car[z]]; substix;y;cdr[ z ] ]] b. equal [x;yl This is a predicate whose value is T if x and y are the same S-expression; its definition: equal = lambda x;y]; [atom [x] [atom[y]+eq[x;y];T-+F]; equal[car[x]; carly l->equal [cdr[x];cdr[y]];T-,F] ] c. null x]3 This is a predicate whose value is T if x is the S-ex3ression NIL; its definition: null = lambda[[x3;[atom[x]- eq[x;NIL];T-*F]] d. maplist i;fL] This is a function with arguments x and f, where x's aS-expression and f is a function from S-expressions to Sexpress bnis; maplist applies the function f.o each suexpression of the S-expression x, producing an S-expression whose ele:.,~;:s are the corresponding results; its definition:

I.D.1S maplist = lambda[x;f3];[null[x]+ NIL;T-cons[fCxl;maplist[cdr[x -;f]ji] Now let us consider a more complicated function, one which computes the partial derivative of an expression written in a Polish-prefixlike notation. The S-expressions to'.be differentiated are written according to the rules: 1. an atomic symbol is an allowed expression; 2. If e1,e2,...,en are allowed expressions, then so are (PLUS el e2... en) (TIMES el e2... en) 1 2 n Thus, the mathematical expression X(X+A)(X+B) would be written (TIMES X (PLUS X A) (PLUS X B)) Our rules of differentiation are the standard'ules for partial differentiation: dx 1 dx 0 (y * x) dx d(u+v) du dv dx dx dx d(u'v) du dv v-+ Udx dx dx The definition of the differentiation function is: diff = lambda[[y;x];[atom[y] — [eq[y;x]-ONE; T1ZERO]; eq[car[y];PLUS]+cons[PLUS; maplist[cdr[y]l;lambda[[z]; diff[car[z];x]]];eqcar[y]; TIMES ]cons PLUS;maplist [cdry];lamnbda[[z];cons [TIMES;maplist[cdry];aambda [w];eqCz;w]carew];Tdiff [car [ w ];x]]]]]]]]

I.D.16 If tnhis function is applied to (TIMES X (PLUS X A) (PLUS X B)) the resulting S-expression is (PLUS (TIMES (PLUS X A) (PLUS X B)) (TIMES X (PLUS X B)) (TIMES X (PLUS X A))) It is possible to write a universal LISP function evalquote [fn;x] which for any two S-expressions fn and x, where fn must have a value which is a function name, produces the result of applying the function fn to the arguments x. That is, given a function definition fn and a set of arguments x, evalquote is able to produce the result of fn[xj; hence evalquote is a universal LISP function. Note,.-oweve that we have not been writing functions as S-expressions so:ar; in fact, we have used what Mc Carthy calls M-expressions to write functions. M-expressions use small alphabetic characters, square brackets, and semicolons. Therefore, to use our universal f.nct on evalquote, it is necessary to rewrite our M-express.ons as S-expressi The following transformation rules effect this conversion: I. If ~ is an S-expression, it is replaced by (QUOTE g) 2. Lower case variable and function names are written in upper case; thus, car becomes CAR 3. fel;...;en] becomes (f' e'... el), where prime denotes n transformation; thus, cons[car[x];cdr[x]] becomes (CONS (CAR X) (CDR X)) 4. [p -lel;'..;P e becomes (COND (p{ e)... (p e')) 5. lambda[[xl;...; xn];e becomes (LAMBDA (x'... x') &') 6. labella;el becomes CLABEL a' c') Applying these rules, T becomes (QUOTE T), ff[car[x]] becomes (FF (CAR X)), and [atom[x]~x;T*ff[carEx]]] becomes (CO,,D ((NACO X) X) ((QUOTE T) (FF (CAR X)))). Further, our function ff now becomes (LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))), and our function equal becomes (LABEL EQUAL (LAMBDA (X Y) (COND ((ATOM X)'(COND ((ATOM Y) (EQ X Y)) ((QUOTE T) (QUOT E F)))) ((EQUAL (CAR X) (CAR Y)) (EQUAL (CDR X) (CDR Y))) (QUOTE T) (QUOTE F))

I.D.17 Thus, we have that the functions which we have been writing in M-expressions can be written as S-expressions. Note that this means that LISP is a language in which data and program are written in the same languages: S-expressions. Further, the LISP interpreter itself is nothing more than the function evalauote, as far as the user is concerned. Thus, knowing this function definition tel25 the user all he need know about the LISP language. Due to its ccmplexity, the definition of evalquote is not given here. (See X.cCarzhy, et. al., (9).) The LISP system has a rather large set of builtin (predefined) functions and predicates for the user. Both integer and floating point arithmetic and constants are available in the system. in pure LISP, a function definition, via label or lambda, is presented, together with arguments, and the function is evaluated Aor those arguments according to evalquote. The function def ni.ions are then lost; that is, function definition via label and lambda is one-shot affair. Since this is obviously an inconvenient mode of operation, the programmer may use a define function to permanently cein.e (for a run) a set of functions, thereafter calling these functions by name as he does for cons, car, cdr, et. alo..Also, a prograam mode is available through which a limited amount of control transfer among LISP statements may be excercised during function evaluation. This is similar to procedures in ALGOL and PL/I. Thus, for exazmple, a function LENGTH, which counts the number of elements in the top level of a list, may be written as: DEFINE (((LENGTH (LAMBDA (X) (PROG (U V) (SETQ V 0) (SETQ U X) A (COND ((NULL U) (RETURN V))) (SETQ U (CDR U)) (SETQ V (ADD1 V)) (GO A)))))) In words, this may be read as: length is function of one arg x

I.D.18 it is a program with two program variables u and v store 0 in v store x in u A if u contains NIL, program is finished, value is content of v store cdr u into u store v+l in v loop back to A and continue The programmer may mix defines and progs to his heart's content to produce LISP programs! In the absence of the prog feature, the above function would have to be recursively defined: DEFINE (((LENGTH (LAMBDA (M) (COND ((NULL M) 0) (T (ADD1 (LENGTH (CDR M))))))))) Once defined, the length function may be applied as if it were a builtin function: i (LENGTH (A B C)) = 3 (LENGTH ((A B) (C D)) = 2 The representation of an atom in LISP is actually a list structure. The pointer to an atom points to this structure. An atom has an association list on which is kept its current definition and other information (including the fact that it is an atom and the BCD print name of the atom). There are LISP functions which allow the user to manipulate the association list of an atom, so control may be excercised over the current contents of this association list for any atom. Storage in LISP is quite dynamic. LISP places a large area of memory into free storage, and this area is formed into a free storage list. When a cons is executed, an element is taken from the free storage list and used t= create the new element. If there is no eiement remaining on the free storage list, the the LISP interpreter sweeps through its list storage (plus some other areas), finds those cells which are currently not being used, and returns these cells to the free storage list; this operation is known as garbage collection. It

I.D.19 is done automatically, so the user need never be aware of it or concerned with it. Here again the use of list structures provides a facility vital to the interpreter.

I.D.20 V. BiBLICGRA?'Y 1. Rosen, Saul (editor): Programaming Systems and Languages,.cGraw-.Hill Book Co., Ncw York, 1967 2. Notes for the advanced topics course in Computer and Program Organization, TAh.e University of Michigan Engineering Summer Conferences, June 19-30, 1967. 3. Foster, J. M.: List Processing. Macfocnald E Co.., London, 1967. 4. Gelernter, R..; A FORTRAN Compiled List Processing Language, JACM, 7:87, 1960. 5. Weizenbaum, J.: Symmetric List Processor, CACM, 6:524, 196'3. 6. Newell, A. (editor): Information Processing Language -V Manual, Prentice Hall, Englewood Cliffs, N. J., 1963. 7. Sutherland, W. R.: The Coral Language and Data Structures, in Tech. Report 405, MIT Lincoln Laboratory, Lexington, Mass., 1966. 8. Knowlton, K. C.: A Programrer's Description of L6, CACM, 9:No. 8, 1966. 9. *McCarthy, John, et. al.: LISP 1.5 Programmer's Manual, The MIT Press, Cambridge, Mass., 1965. 10. Bobrow, D. G., and d. C. Berkeley, (editors): The Programmuring Language LISP: Its Operation and Its Applications, The MIT Press, Cambridge, Mass., 1984. 21. McCarthy, J.: Recursive Functions of Symbolic Lxpressions and Their Computation by Machine, CACM, 3:'1, _360. (Reprinted in (l)).

I.D.21 12. Abrhas, P. W. ct. al.: Tc LiSP 2 Prograrming Languagc and Syste., Proc. AFI?S FJCC, 29:661, 1966. 13. A set of technical working papers on various aspects of the LISP 2 system; reprinted in (2). 1. Raphael, B. and D. G. Bobrow: A Comrparson of List Processir.g Cormouter Languages, CACM, 7:231, 19&4. (Reprinted in (1) with an expanded bibliography). 15. Raphael, B.: Survey of Computer Languages for Symbolic and Algebraic Manipulations, Final Report, Stanford Research Institute Project 6084, Ma.ci:, 1967 (Reprinted in (2)). 16. Weissman, Clark: LISP 1.5 Primer, Dickenson Publis;-.hing Co., Inc., Be+mont, Cal., 1967. 17. Strachey, C.: A General Purpose Macrogenerator, ComputeJ., Oct., 1965* 18. Mooers, C. N.; TRAC -A Procedure Describing Language for the Reactive Typewriter, CACM.9, No. 3, March, 1966. 19. Waite, W.: A Language-Independent Macro Processor, CACM, July, 1967. 20. COMIT Programmers Reference Manual, MIT Press, Cambridge, Mass., 1961. 21. Introduction to COMIT Prograrmming, MIT Press, Cambridg4e, Mass., 1961. 22. Farber, D. J., et. al.: SNIOBOL, a String-Manipulation Language, JACM 11, No. 1, Jan., 1964.

I.D.22 o. -..o;_c -aiia wh L-.LS?, t nmay be poinad out tOhz CAR ard CZR o UiS? car. be wri ten: CAR:?ROCEDUR-'?) RETURNS POINTER) D-^A'. ~ll 4..y 3.ASdD (? ) ) (2L4' 2 2RIG.) POINTER;;,:URN (CrT ); C3R: NRY (?) RE-ThRNS(POINTER) REURN (RG.T); E.ND C AR; and he Li S? CONS -unc.on.may be w-itte~n as CONS:?ROCZDURE (? Q) RETURNS(POINTER) DECLARE 1 LEM BASED (P ), (2 L, 2 R,?, Q) PONINTER; AL LOCATE ELM; L - P; R RETURN (PT); END; Ac uaily,!to be' precise, a LISP noda should be defined as DCLARE 2 ELE B.ASED (P ), 2 LE'T POINT'ER, 2 RIGHT POINTER, 2 IND i;T (6); w.ere ND is an indicator which identifies the type of inoa-o.. pointed to by the LET and RIGHT pointe-rs in the node. QMELk, oS 4 jL/Z 4Acl~ ~te4Loe~n/~s

I.E.1 SIMSCRIPT II CCS 500 Professor Riddle by John Rinn

I.E.2 INTRODUCTION First I shall list items not discussed in the paper: 1. I have not gone into the simulation capabilities of the language at all. 2. Noise words may be left out, or certain alternatives used. These possibilities have not been discussed, except as they appear in the examples. 3. Many functional words have alternates (symbols or words). Again these have not been discussed except for examples. 4. Many other capabilities of the language have not been discussed due to a lack of "time and space". Discussion usually includes the more simple aspects of the language. Complaints include: 1. The language is very incomplete on the 360. Copy *SIM2NEWS for details. 2. It is fairly difficult to get a non-trivial (and in many cases a trivial) program to run. 3. Simscript is very expensive. Example V cost over $10.00 to compile and run!!! 4. Error messages are very poor. In the example on the following page, the error is in line 27. the "ONE" should be a "1"

I.E.3 27 PRINT ONE LINE AS FOLO." S 28 READ C IN SCIENTIFIC NOTATION0 I*E AS E(9o3) 29 READ C AS /, E(9,3) 30 WRITE C AS B 12, E(9,3) 31 PRINT 1 LINE AS FOLLOWS 32 TYPE 0 TO STOP, OR I TO CONTINUE 33 READ E 34 IF E EQUALS O, GO TO STOP 35 OTHERWISE, GO TO START 36'STOP' STOP 37 END -*-* ERROR OF TYPE 1 INVOLVING'PRINT' AT STATEMENT 12: * —- ERROR OF TYPE 1 INVOLVING'ONE' AT STATEMENT 12*- HERR OR OF TYPE 1 INVOLVING'LINE' AT STATEMENT 12***- ERROR OF TYPE 1 INVOLVING'AS' AT STATEMENT 120*** ERROR OF TYPE 1 INVOLVING'FOLLOWS' AT STATEMENT 122..- ERROR OF TYPE 1 INVOLVING'IN' AT STATEMEN 13 **~- ERROR OF TYPE 1 INVOLVING'SCIENTIFIC' AT STA1'EiMENT 13. -*-* ERROR OF TYPE 1 INVOLVING'NOTATION' AT STATEMENT 13. **-* ERROR OF TYPE 1 INVOLVING'C' AT STATEMENT 13 -" — ERROR OF TYPE 1 INVOLVING'I.E' AT STATEMENT 13* — ERr..Oi. OF TYPE I INVOLVING'AS' AT STATEMLNT 130 9 —~ ERROR OF TYPE 1 INVOLVING'E' AT STATEMENT 13---- ERROR OF TYPE 1 INVOLVING'(' AT STATEMENT 13-**- EERRPOR OF TYPE 1 INVOLVING'9' AT STATEMENT 13-*** ERROR OF TYPE 1 INVOLVING',' AT STATEMENT 13---- ERROR OF TYPE 1 INVOLVING.'3' AT STATEMENT 130000 ERROR OF TYPE 1 INVOLVING )3' AT STATEMENT 13

I.E.4 SECTION II In this section we shall discuss the aspects of SIMS3SRIPT II which are prerequisite to the utilization of its set abilities. Inout/Ou tout The program in EXAPLE 1 gives many examples of different input and output formatting, and the two pages which follow it consist of two runs of the program with sample data. Notice that spacing between data items is not critical with the simple read statement. One blank is all that i3 necessary, but more may be used, if desired. The only time that I ran into trouble with the simple statements wa, i n the run at the bottom of the third page of this example, where I read ASDFG into A. I did not, however, have time to trace this down before the writting of this paper. in the first run, 12 was read into the left two digits of a five digit integer using a B 8, I 5 format. The result was the storing of 12000. It should also be pointed out thiat unless a new record is specified ("/"), a B n format item in a read statement will cause the next piece ofhdata to be read beginning at column n of the same record from which the last read statement read. I encountered much trouble tith exponential (scientific) notation on input (possibly on output, also). Again I lacked time to trace this down to determine if it was my problem, or the compiler's.

I.E.5 EXAMTPLE I > 1 PREAMPLE > 2 DEFINE A AS AN ALPHA VARIABLE > 3 NORMALLY, MODE IS INTEGER > 4 DEFINE B AND E AS VARIABLES > 5 DEFINE C AND F AS REAL VARIABLES > 6. DEFINE D AS A 1-D IENSIONAL ARRAY > 7 END > 8 PRINT 1 LINE THUS > 9 B IS I2 AND THE SUBSCRIPT SIZE OF ARRAY D > 10 READ B > 11 RESERVE D(*) AS B 12'START' PRINT 1 LINE WITH B AS FOLLOWS > 13 A IS A4, C IS D(7,2), AND D IS OF LENGTH ** AND A3 > 14 READ A, C AND D > 15 SKIP 3 OUTPUT LINES > 16 PRINT I LINE WITH AB,C AS FOLLOWS > 17 **** IS ALPHA, B = **, AND C = ***-.* > 18 SKIP 2 OUTPUT LINES > 19 FOR I = 1 TO BP PRINT 1 LINE WITH I AND D(I) THUS > 20 THE ** VALUE OF D IS ** ~ > 2 1 SKIP 4 OUTPUT LINES > 22 PRINT 4 LINES WITH B AS FOLLOWS > 23 A IS 5 LETTERS BEGINNING IS CL&OUMN 1 > 24 E IS I5 BEGINNING IN CLOUMN 8 > 25 C IS D(7,2) BEGINNING IN COLUMN 16 > 26 D IS A 1 BY ** ARRAY BEGINNING IN COLUMN 27 AS 13 AND *EVERY 4TH COLUMN > 27 READ A,E AND C AS /, B 1, A 5, B 8, I 5, B 16, D(7,2), B * 26 > 28 FOR I = 1 TO By READ D(I) AS S 1, I 3 > 29 WRITE A,E AND C AS *, B 25, A 5, B 35, I 5- B 45- D(C72) *, /, / > 30 FOR I = 1 TO B, WRITE D(I) AS I 3, S 3 > 31 SKIP- 3 OUTPUT LINES > 32 PRINT 1 LINE AS FOLLOWS > 33 READ F IN SCIENTIFIC NOTATIONS I.E. AS E( 123) > 34 READ F AS /, E(12.3) > 35 WRITE F AS-B 12, E(12,3) > 36 PRINT 1 LINE AS FOLLOWS > 37 TYPE 0 TO STOP, OR 1 TO CONTINUE > 38 READ E > 39 IF E EQUALS O, GO TO STOP > 40 ELSE GO TO START 41'STOP' STOP 42 END

I.E.6 D IS 12 AND THE SUBSCRIPT SIZE OF ARRAY D 4 A IS A4, C IS D(7,2), AND D IS OF LENGTH 4 AND A3 DFGH 32*1 45 67 78 345 DrFGH IS ALPHA, B " 4- AND C. 32*10 THE 1 VALUE OF D IS 45 THE 2 VALUE OF D, IS 67 THE 3 VALUE OF D IS 78 THE 4 VALUE OF D IS 345 A IS 5 LETTERS BEGINNING IS CLOUMN 1 E IS I5 BEGINNING IN CLOUMN 8 C IS D(7.2) BEGINNING IN COLUMN 16 D IS A 1 BY 4 ARRAY BEGINNING IN COLUMN 27 AS I3 AND EVERY 4TH COLUMN ABCDE 12 34.8 456 234 12 2 ABCD 12000 34, 80 456 234 12 2 *READ C IN SCIENTIFIC NOTATIONI I.E. AS EC12.3) 1-OQOE 00 1.000OE 00 TYPE O TO STOP, OR I TO CONTINUE

A IS A4, C IS D(7,2), AND D IS OF LENGTH 4 AND A3 I.E.7?XKL 561- 6 45 234 1 KKL IS ALPHA, B 4, AND C 56. 10 THE 1 VALUE OF D IS 6 THE 2 VALUE Or".D I$45.._ THE 3 VALUE OF D IS 234 THE 4 VALUE OF D I$S 1 A IS 5 LETTERS BEGINNING IS CLOUMN I E IS I5 BEGINNING IN CLOUMN 8 C IS D(7,2) BEGINNING IN COLUMN 16 D IS A 1 BY 4 ARRAY BEGINNING IN COLUSMN 27 AS I3 AND EVERY 4TH COLUMN ABCDEFG1234567845.333333331234567890 123456789 ABCD 12345 45 *33 123 567 901 345 READ C IN SCIENTIFIC NOTATION, I E- AS EC(123) 1-456E 05 AT LOCATION 50094A 0*~~~***U ERROR NUMBER 124 ****..e REAL NUMBER TOO LARGE FOR INPUT ERROR RET;.URN B IS 12 AND THE SUBSCRIPT SIZE OF ARRAY D 4 A IS A4, C IS DC7,2), AND D IS OF LENGTH 4 AND A3 ASDFG 2.4 2 3 4 5 AT LOCATI.ON 504C3C CALLED FROM 500338 ~*****"*** ERROR NUMBER 128 ***e..e*e* INVALID CHARACTER IN "D' OR'E' FORMAT DURING INPUT #ERROR RETURN ~

I.E.8 The Preamble The Preamble of a SIMSCRIPT II program written at this level is used to declare mode (the normal mode is real if not explicitly changed), to declare that a particular name is associated with an array, and to declare the dimension of each array. The dimension of each array must be declared in the preamble, but the subscript size is declared in an executable RESERVE statement when storage is actually allocated. The preamble must end with an END statement. The sample programs is this paper contain several samples of preambles. General Information and Examrnnles Table I describes the fact that arrays are stored with a set of pointers for each dimension. This design coupled with the fact that a RELEASE statement must be executed to return arrays to free storage, while resetting an array pointer without a release statement will not return the array to free storage, allows dynamic construction of a "ragged table". The first program of EXAIIPLE II will construct such a table in the form of a tree, while the second program will search the tree for a giver, entry. Tables II and III list functions available to the SIMSCRIPT II user. Functions of Table II use a calling sequence such as: LET SQ..N=SQRT.F(N) or ADD SQRT.F(N2 + M2) TO SUM while functions of Table III are called with a COMYPUTE statement. For examprle:

I.E.9 FOR I = 1 TO 100 WITH X(I) LESS THAN N COMPUTE NX = THE NUMBER, SUMX AS THE SUM, MEANX AS THE MEAN OF X(I) After execution of these statements, NX will contain the number of X(I) which were less than N, SUMX will be the sum ot these X(I), and MEANX will be their average. EXAMPLE III is fairly straight forward. Comments are enclosed in double quote marks ("..."), while statement labels are between single quotes ('...'). Labels are not, however, enclosed when referred to within a statement. In EXIAMXPLE III, I suspect that information should be read into the 4-dimensional array called CAPACITY in the statement noted "REID INITIAL DATA." This information would consist of the initial number of seats available for each route, with respect to the class of travel and the type of carrier (e.g. train, airplane, bus).

I.E.10 Table, COLUMN POINTER EI.FT4ENTS X(2 1.* ) 2 -,)1. X(1.. l) ~ROW POINTER i ~X(2.2.*,:2:, ~ RASE POINTER X3 N,*) E(3. X(I~ ~-!L~3.X(. 3,. *) X4, 1,*) No(~~(. 0X..) - F I.'t X. 2.. —-—' -\.: - _l Lr 3.:. 2) X(4. 3,*) 3 X(5, 1.) x\.s. 2If ) a =:~~~~~~~~~ICI a

I.E.11 EXAJPLE II2 PREAMLE NORMALLY, MODE IS INTEGER DEFINE LEVEL AND TREE AS 1-DIMENSIONAL ARRAYS END READ N RESERVE LEVEL(*) AS N FOR I-1 TO N,,; RESERVE TREE(*) AS 2**(I-l) READ TREE LET LEVEL(I)-TREE(*) LET TREE(*)-O LOOP END READ CODE FOR I-I TO N.'D0 LET TREE(*)=LEVEL(I) FOR J3l TO 2**(I-I), DO IF TREE(J) EQUALS CODE, GO TO PRINT OTHERWISE LOOPLOOP PRINT 1 LINE WITH CODE AS FOLLOWS UNABLE TO FIND AN ANCESTOR WITH THE CODE * STOP'PRIXT' PRINT I LINE WITH CODE. J AND I AS FOLLOWSANCESTOR, FOUND IN POSITION' OF LEVEL * STOP END

I.E.12 Table II3 SLMSCRIPT II LIBRARY FUNCTIONS NA" Arguments Operation FVnction Hode Rettrictioc ARS.F' * l i It -' mode of argument )AX.Ft value of larIget INTEGER if all argument INTEGER none argument REAL if ome argumnt REAL ZN'.Ft *a-t-*e value of smalleet INTEGER if all arnumant INTEGER so" argumnt REAL if oau arglat REAL bO.Ft a*Le2 ea-TRURtC. F(eI/e 2)12 IMTEGER if |11 &rsument INTEGER ~2 a REAL if a 6rginu.t RAM DIV.F | *F? @| TRMIC.F(e1/.2) INTEGER n d 1 INTEGER; INT.Ft. value of * rounded INTEGER to an integer REL.F ~ value of a expressed REAL f ~a decimal "ambet FRAC.F ~ fractional part d REL * mSt e RAL t S -TRUIC.F(e) TRUNC.F ~ iateger part of INTEGER *~ mt be Rt e; e-FRAC.F(e) SIoi. F i I if o O 0 INTEGER O if ~ O - if a O0 SFIELD.F _me as See..-1.J INTEGER free-foe lapt - only EFIELD.F ree sec. - 1 INTEGER free sform lapet omly DI.F v number of element INTEGER v a pointer it array poaited to SQRT.F, 4' REK AL ~ 0 and REAL EXP.F. exp(.) - EW.C* REAL a mst U REAL LOG.E.F ~ lo e(e) REAL > and REAL LOG.lO. *t lolo(0) R AL. > o and REAL SIN.. * aia(e) REAL REAL aud expressed in radLead COS.F ~ co.(e) REAL a REAL and.ex presaed in radiea AXSIx.F a arcI(s) REAL -< _ ~ _< 1 REAL ARCCOS.F * arcco( e) REAL -1.1 I d AiRTA. F e ar1.2 tet(e1/e2) REAL (e1se2) 0 (000) and REAL 0te a Lanti. es lds I.-Lr.. rathra thm ee a raeale.

I.E. 13 Table III4 STATISTICAL NAMES USED IN THE COMIPUTE STATEMENT Alternative or Statistic Abbreviation Computation NUMB4ER NUM Number of items selected in the iteration SUM Sum of the selected values of the expression MEAN AVERAGE, AVG SUM/NUMBER SUM.OF.SQUARES SSQ Sum of squares of the selected values of the expression MEAN. SQUARE MSQ SUM.OF.SQUARES/NUMBER VARIANCE VAR. MEAN.SQUARE - MEAN**2 STD.DEV STD SQRT.F(VARIANCE) MAXIMUM MAX Maximum value of the selected values of the expression MINIMUM MIN Minimum value of the selected values of the expression MAXIMUM(e) MAX(e) Value of computed e using the control variable values that produce the expression with the MAXIMUM value MINIMUM(e). MIN(e) Same a MAX(e) but for minimum

I.E.14 EXAWi:PLE T115 PREAMB3LE NORMALLY, MODE IS INTEGER DEFINE COSTS AS A 2-DIMENSIONAL ARRAY DEFINE MvoODE.FACTORS AND CLASS.FACTORS AS 1-DIMENSIONAL ARRAYS DEFINE CAPACITY AS A 4-DIMENSIONAL ARRAY DEFINE FROM, TO,MODE AND CLASS AS "GLOBAL" VARIABLES END MAIN READ NFROM, NTO, NMODE,NCLASS''READ MAXIMUM DIMENSIONS RESERVE COSTS(*,*) AS NFROM BY NTO, MODE.FACTORS(*) AS NMODE, CLASS.FACTORS(*) AS NCLASS,CAPACITY(*,*,t,*) AS NFROM BY NTO BY NCLASS BY NMODE READ COSTS, CLASS.FACTORS,MODE.FACTORS "READ INITIAL DATA'REQUEST' READ FROM,TO,MODE, CLASS'INQUIRE' CALL RESERVATION YIELDING ANSWER IF ANSWER EQUALS 1 NOW FIND.COST YIELDING PRICE PRINT 1KLINE WITH MODE,CLASS,FROM,TO,PRICE THUS MODE * CLASS * RESERVATION FROM ** TO ** IS AVAILABLE FOR -** DOLLARS GO TO "''NEXT CUSTOMER"'' REQUEST OTHERWISE''FIND OTHER SPACE SUBTRACT 1 FROM CLASS IF CLASS IS GREATER THAN 0 GO TO INQUIRE OTHERWISE LET CLASS=NCLASS SUBTRACT 1 FROM MODE IF MODE IS GREATER THAN 0 GO TO INQUIRE OTHERWISE PRINT 1 LINE WITH FROM AND TO LIKE-THIS THERE IS NO TRANSPORTATION AVAILABLE FROM'* TO ** TODAY GO TO REQUEST END''OF MAIN ROUTINE" ROUTINE FOR RESERVATION YIELDING ANSWER IF CAPACITY(FROM,TO,CLASS,MODE) IS GREATER THAN 0 SUBTRACT 1 FROM CAPACITY(FROM,TO,CLASS,MODE) LET ANSWER=1 RETURN ELSE LET ANSWER-O RETURN END ROUTINE TO FIND.COST YIELDING SUM LET SUMICOSTS(FROM O)*CLASS. FACTORS(CLASS)*MODE. FACTORS(MODE) RETURN END

I.E.15 SECTION II In this section we will be discussing Entities, Attributes, and Sets, and their associated declarations and operations. We begin with these definitions: "An ENTITY is a program element, much like a variable, that exixts in a modeled system. It is like a subscripted variable in that it has values, called ATTRI3UT7S, associated with it that, when assigned specific values, define a 6 particular configuration or state of the entity." "Sets...are collections of entities organized by systems of pointers. Set owners point to the first and last members of sets; set members point to one another. Sets are like arrays in that they are composed of elements that can be identified and manipulated, but are unlike arrays in their method of organization and their dynamic 7 and changeable, rather than static and fixed, nature." We begin the study of these "Objects" with a discussion of the Preamble in order to understand how they3lare declared. The Preamble Entity classes are given attribute catagories in the Preamble. Any attribute that any member of an entity class may have must be declared in the Preamble. if a member is later to be given it. For example, suppose an entity class —MAN has the following attributes: Age, Dependents, and a Social Security Number. This could be declared as follows: EVERY iMAN HAS AN AGE, SOME DEPENDENTS AND A SOCIAL -SECURITY. NUMBER

I.E. 16 If another entity has the attribute AGE, it must occur in the same relative position as it did in MAN. (i.e. EVERY DOG HIAS AN AGE AND A BREED is o.k., but EVERY DOG HAS A BREED AND AN AGE is not.) This is because AGE(entity) is translated into "the value found in the first word of the record indexed by the value entity" (where entity may be MAN or DOG in the above example).. There are two types of entities, temporary entities, and permanent entities, which will be discussed later. Every entity must be declared to be one or the other of these in the Preamble. The statements:: TEvMPORARY ENTITIES and PERMAUNENT ENTITIES precede the lists of each type (ie. the EVERY statements). It is important to remember that entities are not created in the Preamble (i.e, no storage space is allocated to an entity because it appears in the Preamble), but a class of entities must appear in the Preamble before it can be created in the program. Also remember that if only one member of an entity class has a particular attribute, that attribute still must be declared for that entity class (i.e. it is possible for any member of that class to have that attribute). Entities may "own" sets of entities,. and they may be "owned" by other entities, as in: EVERY COM~VfUNITY OWNS A MASONS EVERY MAN MAY BELONG TO THE MASONS

I.E.17 As with attributes, the possibility of set ownership or membership must be declared in the Preamble. Note that the words HAVE and HAS denote attributes assigned to entities; the words OWN and OWNS denote set ownership by an entity; and the words BELONG and BELONGS denote set membership of entities to the sets following these words. Temporary Entities If the temporary entity MAL is declared in the Preamble as follows: EVERY MAN HAS AN AGE, O\WNS A FAMILY, MAY BELONG TO THE MASONS AND HAS A BIRTH.DATE the statement: CREAT AM SAN CALLED JOHN results in JOHN pointing to a record in storage which looks like: AGE F.FAMILY L. FATiILY N. FAMILY P.M S ONS S.MASONS Nl. IASONS BIRTH.DAT TTP In this example, AGE is the value of the attribute AGE; F.FAMILY is a pointer to the first element in the set FAMILY(JOHN); L.FAMILY is a pointer to the last element in the set FAMILY(JOHN); P..MASONSis a pointer to the previous element in the set of masons in his community (MASONS(ANN.ARBOR))

I.E.18 (this pointer is zero if JOHN is not in the set, or if he is the first element of the set); Se.MASONS is a pointer to the next member of the set MASONS(ANN.ARBOR) (this pointer is zero if JOHN is not a member of the set, of if he is the last member of the set); M.MASONS is equal to one (1) if JOHN is a member of the masons, and is zero otherwise; N.FMi,'IlLY is the number of elements in the set FA.MILY(JOHN); and BIRTH.DATE contains the value of the attribute BIRTH..DATE. A temporary entity is created whenever it is needed and destroyed individually with a destroy statement. e.g. DESTROY THE MAN CALLED JOHN Permanent Entities If MAN is declared a permanent entity in the following statement: EVERY MAN HAS AN AGE,. OWNS A FAMiILY AND MAY BELONG TO THE MAS ONS then eve'Mry AlN is created at the same time (as contrasted with temporary entities, which are created as needed, and their total number is not fixed, as it is with permanent entities). The following two sets of statements each create the entities MAN: RE.AD N.MAN CREATE EVERY MAN or LET N.MAN = 5 CREATE EVERY MAN

I.E.19 The first two statements create the number of men read into the variable N.MAN, a system variable setup automatically when MAN was declared a permanent entity. In the second set of two statements this system variable is set to five, and thus five men are created. When the CREATE statement is executed, storage is setup in blocks, where each block contains the values of one particular attribute for all of the entities of the type MAN. (This is a completely different scheme than with temporary entities, which have their own record containing all of the attribute and set data for that particular entity). A permanent entity class looks like this in storage: IGI.....-IL - I 7 I.I -SOS.:.. SO MAN () MAN(2):AN (,N. MAN ) To destroy a permanent entity, all entities of that tyope must be destroyed at the same time. This is done by releasing all of the entity class's attributes. For example: RELEASE AGE,F..SFM-,ILY,L..FAMILY,N. FAMILY, P. MASONS, S. MASONS,M.i MASONS

I.E.20 Exampies of Simple Set Filing Routines The following are examples of filing and removal routines. Their individual functions are obvious. FILE ROVER FIRST IN KENNEL(1) FILE ROVER LAST IN KENNEL(l) FILE ROVER BEFORE SAM IN KENTNEL(2) FILE ROVER AFTER SAIM IN KENNEL(2) REMOVE FIRST DOG FROM KENNEL(1) REMOVE LAST DOG FROM KENNEL(1) REMOVE ROVER FROM KENNEL(2) The default for FILE is LAST, so FILE ROVER LAST IN KENNEL(l) and FILE ROVER IN KENNEL(1) are equivalent. The final two examples are easily understood and need no further explanation.

I.E.21 EXAMPLE.V8 424-:2 An I;tventory ControZ Porozgr PREA":3LE NOPRY.ALLY MODE IS INTEGER PERvANENT ENTITIES EVERY ITEM HAS A RP "REOROdR POINT', AN SCL "STOCK CONTROL LEVEL", A STOCK "A'kOUNT ON HAND", A DUE.IN "A'.OUNT ORDERED, NOT RECEIVED", A DUEOUT " AMOUNT OF aACK ORDERS" END VAIN READ N.ITEM CREATE EACH ITEM FOR EACH ITEM, READ RP(ITEM),SCL(ITEM),STOCK(ITEM) DUE.IN(ITEM), DUE.OUT(ITEM)'READ' IF DATA IS ENDED, GO TO FINISH ELSE READ TRANSACTION, ITEM, QUANTITY IF TRANSACTION= 1 " PROCESS AN ORDER IF STOCK GE QUANTITY, SUBTRACT QUANTITY FROM STOCK GO TO REORDER.CHECK OTHERWISE "INSUFFICIENT STOCK" ADD QUANTITY-STOCK TO DUE.OUT LET STOCKO'REORDER. CHECK' IF STOCK + DUE.IN- DUE.OUT LE RP, LET ORDER= SCL+DUE.OUT-DUE:IN-STOCK PRINT 1 LINE WITH ORDER,ITEM THUS ORDER *** UNITS OF STOCK NO. *** ADD ORDER TO DUE.IN REGARDLESS GO READ OTHERWISE "''PROCESS A RECEIPT" SUBTRACT QUANTITY FROM DUE.IN IF DUE.OUT > QUANTITY, SUBTRACT QUANTITY. FROM DUEOUT GO TO READ ELSE ADD QUANTITY-DUE.OUT TO STOCK LET DUE.OUT-O GO TO READ'FINISH' LIST ATTRIBUTES OF EACH ITD STOP END

-%): ~ z rs W Ell H Wt4 1 PI~EAMI?3 uFAM(E)) Ul V) () 2 pEPRNANENT ENTITIES (4 0 3 ~FVEiY FARM&% OWNS A KENNEL CQ C* c*J > Q 4 TEPi0ORARY ENTITIES.0 0(4 0 0 5 EVERY DOG HAS A NAME AND BELONGS TO SO1E KENNEL McO 4 <4 6 CEFINE NAME AS AN ALPHA VARIABLE 7 NO RX-ALLY Y.ODE IS INTEGER 8 END 4 9 LFT N.FARM: 2 S.~~~~C 10. CRE.ATE EVERY FARM I 1 1 rR AD 1NU&!-,:BER-0FoD GS 12. F ORi I = I TO N1Y-1IER.OF.D0GS I~~~~~~~C 13 DO 0 ) 0 14 CREATE f DOG RFAD NANJE(DOG) AND F AS /s A 4,-P I I' ~4 16 F ILE DOG FIRST IN KENNEL(F) c 0 fl.4 17 LOOP 18 F OR EACH DOG IN KENNEL(1) Q) 19 DO 0 ~4 20 PRINT 1 LINE WITH N.41E(DOG) AS FOLLOWS w ~4 *4' —~~[zJ4 (j4 21 IS IN KENNEtL1) I V)~ ~ CI vr ~4 x~ w tn r6 22 LOOP 23 F-OR EACH DOG IN XENNEL(2) o. 24 DO 4 25 PRINT 1 LINE WITH NMEM(DdG) AS FOLLOWS fr. 2.6 IS IN KFNNEL(2) 4[4[ ~4 27 LOOP U 28 ST) P XZ 0, 29 EID 1 - -Q N OF FILE o4c c 1 7LW3 ~Z x x)W ~.~ ~4 43

I.E.23 REFERENC ES 1. Kiviat, P.J., Villanueva, R., and Markowitz, H.M., The Simscript II Programning Language, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1965 (Rand Corp.). 2. Simscript II.5 Reference Handbook, Consolidated Analysis Center, Inc., 12011 San Vicente Blvd., Los Angeles, Cali., 1971. 3. *SIMSCRIPT2, MTS Vol. II, p. 288.1 (in CCIMEMO M198). 4. $COP.~ *SIM2NEWS FOOTNOTES All footnotes are taken fronm reference /#l, listed above. O. I omitted a reference to more 1/0 information from SECTION I. pp. 153-192 1. p.57 2. pp.62-63 3. p.91 4. p.149 5. p. 108 6. p. 194 7. pp. 223-224 8. pp. 248-249

I.F.1 Paul Brindle POP-2 A Data Structures Language I. History and Aims of the language A. Largely patterned after ALGOL, also has elements of LISP,LPL,CLBOL,PL/I, IPYL-VJOSSTRACFUlMULA ALGUL B. Block structured and algorithmic C. Immediate execution unless in function definition —interactive D. Numverical facilities ignored in favor of structure manipulation I I. Basic concepts and facilities. A. Operates on items (one-word entities) 1. Simple items —integers and reals represented by themselves 2. Compound items —pointers to data structure and functions 3. No types at declaration —manipulate items at "ill types checked at operation execution. Ex. FUNCTION A... END; VARS B; A -B3; B(17) — C; 4 e B; B+8 P; B. Standard data structures 1. Lists HD,TL' 2. Pairs V FRONT, BACK 3. Strips (vectors) and Character strips jSUBL 1VCI II(,STRIP) V1.| | |.| I.I \ \^ijzGu) A\

I.F.2 4. Words C C. Structures have 3 associated functions: 1. Constructor 2. Destructor 3. Doublet —accessor/updater fns for items in structure Ex. 7 - A; "RALPH" -i B; [%A,B,LISTLj. LIStB; CONS(CONSPAIR('ABQ',14),LISTB).-3 LISTB; D. Use of stack 1. Temporary store Ex. switch elements A,B' A -B; 2. Parameter passage Ex. F is function of one variable to operate on a number mod B: A // B;.ERASE;.F; I I. Definition capabilities A. Functions —implicit assignments in FUNCTION type declaration explicit assignments in LAMBDA type declaration Ex. FUNCTION F X Y; blah blah; END; is same as VARS F; (LAMBDA X Y: blah blah; END) - f;

I.F.3 B. Operations Ex. VARS OPERATION 7 ==; FUNCTION == x y;... END; IF J==P THEN... C. Partial application Ex. Given SORT(N,TEST,DOUBLET) FORT (%SUBSCR%) -- STRIPSORT; SORT (% ALPHATE ST,SUBSC R% ) -- ALPHASORT; ALPHASORT(DATALENGTH (5) ) )- S; D. Creation of new data structures 1. RECORDFNS — create new types of beads with custom fields get necessary functions to easily link the beads for yourself Ex. RECORDFNS( "PAIR"1, o o ) — BACK - FRONT — DESTPAIR — L C NSPAIR; RECORDFNS("PERSON", CO 0 0 1 77 ) -- AGE -- SEX -3 SPOUSE -SURNAME-3 FORENAME -3 DESTPERSON -- C iNSPERSON; CONSPERSON("JOHN","SMITH",O,O,22) — JOHN; FUNCTION MARRIAGE BOY GIRL; IF SEX(BOY) = SEX(GIRL) THEN PRINT('FROWNED UPON'); ELSE SURNAME (BOY) — ) SURNAME(GIRL); EBMIENT ADMITTEDLY SEXIST; GIRL —SPOUSE (BOY); BOY -7' SPOUSE (GIRL ); CLOSE; END; 2. STRIPFNS Ex. STRIPFNS("CHARsKXSTR", 8) -5 INITC -'SUBSCRC 3. NEWANYARRAY Ex. NEWANYARRAY( Ql,N,N2,N5%J,(LAMBDA X Y; X+Y; END), INIT,SUB iCR) -- ARRAY; NEWANYARRAY (I NIT, SUBSCR,) — NEWARRAY; IV. Summary —POP-2 presents the user with a very pleasing simplicity of manipulation and ability to define natural structures, making programming easy and transparent. V. References —POP-2 Reference Manual in Mitchie (ed.), Machine Intelligence, Vol. 2

II.1 DYNAMIC STORAGE MANAGEMENT William E. Riddle 5-24-72 I. Introduction A. Dynamic storage management is effected by a set of routines (DSM routines):. which are a part of either the system supervisor or the programming language support package,. and which provide an ability to acquire and release storage during program execution. B. The general benefit which accrues is an ability to delay the binding of a storage segment's size and/or location.. For the system supervisor this facilitates increasing overall system performance by allowing: * reuse of a storage segment for different jobs dynamic adjustment to system load For the higher-level language programmer this facilitates program generality by allowing:. increased generality inherent in not having to specify maximum data structure size ~ reuse of a storage segment for different data structures. data structures which have a size or organization which changes during program execution. recursive procedures C. The set of DSM routines must possess some or all of the following capabilities:. selection of a storage segment from available storage and of sufficient size to satisfy a request. reclamation of previously allocated but presently unused storage segments. recombination of (either adjacent or non-adjacent) available storage segments D. Two gross attributes of a set of DSM routines are:. their visibility to the user - must he explicitly command their invocation (as in PL/I) or are they implicitly invoked as required (as in LISP)

the general flavor of the allocation they perform:. "large" segments to be used for "long" periods of time such as during the entire execution of the program which requested the storage. "small" segments to be used for "short" periods of time such as during only part of the requesting program's execution E. Most all DSM routines operate in the following general manner: * maintain some private data structure, AVAIL, which identifies all of the available storage which can be used to satisfy a request * when a previously allocated storage segment is returned, update AVAIL so that the segment is known to be available. the information specifying the size and location of the segment:. could have been retained by the routines when the segment was allocated. or could have been saved within the segment (either protected or unprotected). or could be stated by the agent who returns the segment. the newly returned segment could be combined with other (usually adjacent) available segments * when a request for a storage segment is received, then it is satisfied by using the information in AVAIL to select a segment. the selected segment may be larger than requested.. if there are no segments identified by AVAIL which are large enough to satisfy the request:. the DSM routines may refuse to satisfy the request and (may or may not) notify the requester ~ the DSM routines may try to recombine several (adjacent or non-adjacent) segments to obtain a large enough one. the DSM routines may try to reclaim segments which were allocated previously and are no longer being used but have not been returned

11.3 II. Sequential Allocation A. All managed storage is assumed to be in one large block and there is a dividing point such that storage above that point has been allocated and storage below that point is still available. AVAIL is just a pointer, FREEPOINT, to the dividing point. B. A request for n bytes of storage is satisfied by allocating the next n bytes starting at FREEPOINT. If n is larger than amount of storage below FREEPOINT, try to recombine unused areas which fall above FREEPOINT before refusing to satisfy request C. Upon return of a storage segment can either:. mark it unused and leave recombination until later when it is necessary recombine the newly returned segment with the rest of available storage D. Two examples 1. "Stack" allocation - storage segments are returned in the reverse order of that in which they were allocated. Used for automatic variables in PL/I. ALLOCATED I I A AVAILABLE, /3/a PFREEPOINT Last segment allocated; next to be returned.

II.4 2. Sequential allocation without explicit return - must compactify allocated storage, reclaiming and recombining available segments. Used in XPL for strings. ALLOCATED CONSTANT r..... CHARACTER - AVAILABLE it STRINGS I, a. _.................... *He,. 1,+.......;...' FREEBASE LOWER BOUND FREEPOINT FREELII DESCRIPTORS FREELIMIT has a value which pointers is 256 short of the end of into the the managed area. area Upon receiving a request for n (<256) bytes: A. if FREEPOINT is < FREELIMIT then satisfy request and update FREEPOINT B. otherwise reclaim and recombine currently unused segments in ALLOCATED portion. B.1. try a minor compactification first B.1.1. copy into DX all those descriptors in DESCRIPTORS which point into area between LOWER BOUND and FREEPOINT B.1.2. sort DX and use result to control moving of referenced values up toward LOWER BOUND B.2. if not enough storage was reclaimed, then try a major compatification - same as above but work on region between FREEBASE and FREEPOINT. B.3. if still not enough storage was reclaimed then refuse to satisfy request. B.4. update FREEPOINT and LOWER BOUND to point at end of ALLOCATED region Indicates GENERAL RULE: the most work is done for the least benefit.

II.5 E. When there is more than one pool. 1. If there are two pools point them at each other so that limit of one is current extend of the other..../................................... / / FREEPOINT1 FREEPOINT2 2. If there are more than two: A. Initially, space them out either evenly or according to their estimated maximum size. B. When one runs into another: 1. allocate more to cramped region by: a. moving the information in next one b. taking space away from least active region and moving others accordingly c. taking some space away from each region in proportion to its activity III. Non-sequential Allocation A. Instead of having the unallocated regions (which DSM knows about) all contiguous within one area, they may be scattered through storage. To keep track of them, they are chained together on a linked list and part of AVAIL holds a pointer to the start of the chain. B. Explicit return - no need to do reclamation since DSM routines assume user will notify when a region is no longer needed. 1. If segments are all the same size then treat list of available segments as a stack, popping one off to satisfy a request and pushing a returned segment onto the stack. 2. If segments vary in size then there are some problems. a. If request is for segment of size n, then must first find an available segment of size m > n. Then allocate n bytes from the segment and return m-n byte segment to list of available segments. (Don't recombine.)

II.6 1. Best Fit: choose available segment such that m-n is minimized. This has a long search time and will proliferate small segments. 2. First Fit: choose first segment on list which has m > n. This has shorter search time and can be expected to generate fewer small segments. Shown in simulation by Knuth to be better. 3. Avoid small segment proliferation by never generating a segment of size <K. Must remember actual size. 4. Speed up best fit searching by having list ordered by increasing size. Will increase insertion time so very little overall gain. b. When a segment is returned, just stick it back onto list. However, if two available segments are actually contiguous, want to combine them and have one entry on list. 1. If list is kept ordered by starting address then check successor and predecessor and combine if warranted. Will want two way linked list. 2. Insertion is quicker if list doesn't have to be ordered. Store some information with the block and use BOUNDARY TAG Method (due to Knuth)...TAG SIZE TAG = 1 if available F POINTER = 0 if allocated B POINTER SIZE = n+8 n i POINTERs used only in available segments. t TAG 3 SIZE Neighbors of a block at location a can be checked by looking at a-l and a+SIZE. 3. Another way is to use the BUDDY SYSTEM (due to Knowlton). a segment's BUDDY is a contiguous block which the segment may be combined with both segment and its BUDDY have size 2k for some k. if segment's address is a and segment's size is. then BUDDY'S address is a+2k (addition without carry).

II.7. segments look like — TAG...... -'K. TAG = 1 if available F POINTER = 0 if allocated POINTER needed only in available segments. F POINTER is used to maintain a stack of available segments. A separate stack is kept for each size k, l<k<n.. When a request is received for segment of size 2k first look in stack for that size. If none available, then look for segments of size 2k+l. If one is available with that size, split it in half, allocate one half and put other on 2k stack. If none available look at 2k+2 and split it twice. Etc.. When a segment is returned, check to see if BUDDY is free and combine if possible. Keep combining more buddies as much as possible. Two problems: 1. adjacent non-BUDDYs may be available but not combined - Knuth's simulations show that this isn't frequent. 2. there is waste if there are many instances of needing slightly more than 2k for some k. C. Implicit return - the primary problem now is reclamation. 1. If segments are of differing sizes need to augment algorithms to take notice of segment size. In the rest of this section, assume that all segments are of the same size. 2. If segments don't all have the same pattern then need some extra information to indicate where pointers are within a segment. In the rest of this section, assume that all segments have the same pattern. 3. Whenever the list of available segments is empty, more segments are reclaimed by a "garbage collection" routine: 1. scan through entire managed area and mark all of those segments which are still being used (assume all segments are initially unmarked) 2. scan again, accumulating all unmarked segments into the list of available segments and unmarking all marked segments.

I I.8 4. In order to be able to mark segments need to set aside a bit for each either within the segment or in a bit table. 5. The first scan through the managed area must be guided by some information concerning the used areas. Usual situation is that managed area is laced with list structures. In such a situation, we assume that some table gives addresses to the heads of all the lists. To mark, we go down each list structure - a. At each node, push n-1 of the branch addresses onto a stack and follow the nth. When a terminal node is reached then pop an address off the stack and continue. Problem: need free storage (an arbitrary amount of it) to collect free storage. b. Pointer Reversal Technique (Schorr & Waite) Don't need an extra stack. Instead, the pointer fields of the nodes are used to hold a backward pointing chain (built while going forward) which can be followed to return to an as yet unfollowed branch.. Need another bit in a two-branch node:...... Mark.... Fa......................................... |Bit |Flag | Pointer Pointer Bit. Example: -I ID~ol,-~:.o.......I..'0:.o:1....?....~ Lt_.... i' -.....i. 0 0 olo,o, io, o_ i o t LY-0 1

II.9 ~, o' T,....... o.. —,o f-!oid L_._!fV i too 0.... 0 l 0 I l..........ow~~ 0 i i-L1X4 0 0Tk ~I I,-,-o 0..... I 4 I -o-!loyaf-01etc. If there are n branches from each node, need FLAG field k bits wide where 2k-1 < n < 2k 6. Instead of collecting the garbage when there is no more available space, collect it as it is generated by maintaining a reference count. The count is increased whenever a pointer is made to reference the node (or reference a node which references the node). The count is decreased when a pointer is made to not reference the node. A. To preserve integrity, some central agent must perform all pointer manipulation. B. Need extra storage in each node to hold the count C. Extra storage required may be reduced by keeping a count only for lists and sublists. (SLIP scheme, Weizenbaum) three node types L - reference count [r- r Header B POINTER I F POINTER L, LP i |,,, popinter _ Reference to a list i B POINTER FPOINTER N value N value Value on a list B POINTER I FPOINTER when reference count within a header goes to zero, put it onto the free list.. because of pointers in header this automatically puts all of the first level nodes on the free list.

II. 10. the reference counts in the sublists referenced by the list are not updated at this time.. when a node is taken off the free list check to see if it is of type LP.. if it is, then decrease reference count of list this node points to and put that list on if warranted. * this way, free storage is reclaimed ~ as it is generated. in larger segments - whole lists at one time ~ as it is needed. two problems: 1. if only part of a list is actually referenced, the whole list must be retained because there can be only one reference count. 2. a recursive list cannot be handled without special processing - its reference count would always be at least 1. IV. References A.J. Bertiss. Data Structures, Theory and Practice. Academic Press, 1971. Schorr and Waite. An efficient machine-independent procedure for garbage collection in various list structures. CACM 10, 8 (August 1967), 501. Tonge. Notes on Data Structuresjfn Engineering Summer Conference Notes, 1970. Knuth. The Art of Computer Programming, Vol. I. Addison-Wesley, 1968. Knowlton. A fast storage allocator. CACM 8, 10 (October 1965), 623-625. Weizenbaum. Symmetric List Processor. CACM 6, 9 (September 1963), 524-544.

III.A.1 PL/I LANGUAGE INTERNALS by Morton D. Hoffan PL/I was designed as a general purpose algorithmic language. As such, its list processing facility is designed to fit into a more general scheme. To provide the most general data structuring capability, PL/I provides a pointer data type bringing into the external language, a level of detail often reserved for the internal structure of other languages. For this reason the system cannot always know when a storage area is no longer useful, and storage management must often be explicitly invoked by the user. Therefore the internals of the list processing facility has two main components -- internal data representation and Dynamic Storage Management. 7 s - - - - - - - -- ------- _________________ Dynamic storage in PL/I is - H 2,, divided among three classes of:~ n-har.ard address variables: AUTOMATIC, CON' ~ - TROLLED, and BASED. AUTOMATIC.. egniste save area storage can be efficiently re~,.S C' ~cut _ ie claimed by PL/I since only AUTOMATIC variables are asso- 5 coun ciated with the invocation of -8 - o z- C..-, RO:; O: -- - a block. AUTOMATIC variables i -, S ad - eve. n w runfoer are stored in two structuresJ. Doe v ecors Dynamic Storage Areas (DSA) <i;0 C a t a ~A Variable Data Areas (VDA),. rete- i sts which together form the Run L —---- ___ ____________ Fiqusre 1?cr mat of tne Dynamic Szorage Time Stack (RTS). area (DSA)

III.A.2 The first of these, the Dynamic Storage Area (fig. 1) is associated with the invocation of a block, This is the prime area for storage of automatic variables. The Dynamic Storage Area is also the repository for all information of the environment peculiar to the block, Its address is held in a pseudo-register; together the set of pseudoregisters pointing to Dynamic Storage Areas is called the display,since this construct now contains the description of the complete environment of a block. The Dynamic Storage Areas are chained together to provide housekeeping for dynamic storage (i.e. if several blocks are exited by one statement, the Dynamic Storage Areas for the intervening block can be located through the chaining), The Variable Data Area (VDA) 7 7 31 is quite similar to the Dynamic 1, i.? Storage Area except in its uses 4 Chain-ckc address (fig. 2). One Variable Data s2 Area is created at the invoca- _______ 1Figure 2...;.t of the Variable Data tion of a block. In it reside Area (hDA) those automatic variables whose extent (length) is not known at compile time. Additional Variable Data Areas may be created for library work space (since the library routines are re-entrant, they require such external work space).. The first such area is called the Pseudo-Register Vector Variable Data Area (PRV VDA) and also contains the pseudo-registerso This area is allocated only once. Additional Variable Data Areas for library calls may be created in the form of secondary Librarzy Work Space Variable Data Areas (LWS VDA) in blocks as needed, All: tt Variable Data Areas are chained into the Dynamic Storage Area chain (Run TIme Stack) behind the

III.A.3 Dynamic Storage Area for their respective blocks. r- ~ -- - ----------- -. ——... --- ------- RV jV l ck 2 b I lo ck i I Used core! Used core I I I Ig....................~ < --- - <- I J Zt ~ I ~;I~ t~ II I I ~~ 1~i~,,,,,, - - - - - - - - - 1 1':! I! I 1 i i I! I ~~_______ __________ — II - t I _________j LI r —'.......-....-'. I I — I! I [ L(Free core)! i [ j I Block iength I i r-,,,,,, —-~c —-- -- - -; t L-4,- C1hain-back pointer Figur 3 Sui o Chain-forrar d pointer. —- V r a a I I, I I, r o; o s is CeGu-tedfro Th! crI Free core! a d olocy- lcrk l ot i! I o! [t L-_ Chai2.n-Zk:clnter: 1 IZ~t!ero I I I t [: { ]~ I j Free coe re *, I i! I 1 1 1.......I I j L Figure 3 Structure of tne Free-Core Chain for Automatic Variables The management for Dynamic Storage Areas and Variable Data Areas are performed together. Initially hK or 6K of storage is requested from the supervisor. As this storage is used, the remaining free area in this block is reduced. When a request can no longer be satisfied, an he free core areas in these blocks are cained in a doubly-lnked list in the order of allocation (fig. 3). Wen requests for core are Made, large enough to satisfy the request. In the event that a 2K area is

III.A.4 entirely freed, the free core length will be recognized equal to the block length (both are stored at the beginning of the free core area of the block) and the block returned to the supervisor. Since automatic storage is always freed in the reverse order from which it is allocated, freed storage is always at the bottom of a block and there is at most one free area in any block. - - - - - -- - - — ~ ~-J ~...,/ -?,- ~ ~'- - Controlled Storage cannot be so kandily anaged, since variables:pl~-,uzc 4 e an for a Co2. z'-sl Varianl Controlled Storage cannot be so handily nanaged, since variables ean be allocated and freed in arbitrary order. The result of this is that all ALLOCATE statements result in requests to the supervisor for an area large enough for the variable plus associated control information, Every controlled variable is represented by a chain of allocations off a pseudo-register (figure 4). When a controlled variable is first allocated, the pseudo-register (initially zero) is set to the address of this allocation. Each new.. allocation is chained in immediately following the pseudo-register. The address of the previous allocation is set in the new allocation, forming a chain of the generations of the controlled variable. In this scheme the chain forms a push-down stack, and the execution of a FREE statement results in the restoration of the previous allocation (popping the stack).

738 31 III.A.S O;e of cr t Free c., Zero if Free List: —;,ILenth of Free lcmnt Alloccte. L. O:'sst 1 sinI F re. I _ _ ___: L L- Ofset of next sinCO to'ree Free:lemaene Figuser T norote: If tf FAre Vririabl:r ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ lit bi C o th isr bt e X I,' E,~ment t i Aloate i;r —'r~ ~ L__e n g t h ~~ F g. ree Ele rn Fo t f A V rile, | Fr ee i i No, Al loca te d o.;' e...... 8, t o_'ea _.z e W, Fi gure ~. Fo.~r..at of Are Variable2

III.A.6 Based storage is handled in much the same way as controlled storage. All storage requests are passed on to the supervisor, but now without any area for control information, Control information and the control stack is not needed here since a based variable does not have generations associated with it. Based storage allocated within an area is handled differently. An area contains four words of control information, an area encompassing all allocated storage, and a final free area. Within the storage area encompassing the allocated storage (fig. 5' nd 6), there is a free list anchored to the third word of AREA control information. It is organized by the largest free element on the list. The beginning of each free element has the length of the free element and the address of the next smaller free element, The smallest element points to a zero word (which serves as a free element of length zero). When a storage request comes in, the free list is checked first. If there are free elements large enough, the smallest such element is taken off the free list, divided into an element to fit the request, and the amount of storage left over (if any). Tnis excess storage is put back on the free list in the position determined by its size. If no element on the free list is large enough, an allocation is made from the top of the last region of the area, which is unallocated storage. If this cannot satisfy the request, the request fails, restiting in a PL/1 AREA condition. Controlled Storage and Automatic Storage allocation and freeing are done in library module IHESA. Based variables, within and without AREAs are controlled by module IHELSP.

III.A.7 When storage in an AREA is freed, PL/I first attempts to merge it with an adjacent free element (and move the enlarged element to its new peoition on the free store chain). If it cannot be merged, it is then inserted by itself on the free list. It is not clear why the last free element in the area is kept off the free list. Also, the proposition that it is best to satisfy an allocation from the smallest frec element large enough to satisfy the request has been brought into serious question by recent simvlation studies.l f-i::.rcv{' a k e f or c ann e 2. Base elemer. t sh 2- aray', s irng a.nd sructre (lOpe s rC= _ consiGsts of one entry for each 0. 2 7 9 S0 15 re, nor sructure and basee..................... eann i:n.e or-cinal declaration. Eac.h 12 j;' en- ry consists of one word and can h.ave one L______ or two. fo-rm-ats; 6 17 1 23 2 31 1. S rucur ue: F1 = 1 Base e eme-nt G 1 2 7 8 F5 F 2 0 No _ end o- sc.uc _-; —.i T - 1 iEnd of structure F.! 2 _ N S__~, z -— J ~~ L = Level of eleent 16 31 F5 = 1 Area variabl e ~~ —.0 Not area va_:ace! "S Of o woffset A ~~~_____ _6_ F 1o Event van r_ e = 0 No event var able 7l = 0 Structure F3 -0 Not an a'icnei sit strng 2 = O = 1 Aiigned bi sr n.. Level of structure F4 = C Not a varvinc stri.I Varying strng N - Dimensionality, incl udin g inherited cimensions A Alignment in cats ( -o 63) Offsset Of set of c)ntaining, D = LenCh", -f not a s-.,'_ st ructur= from start of bi- s DVD = 0 a' a strinc, an;' ase = —- -- -1 for a major structure -ne lengt h'as an. te coe vector Figure 7. Dope Vector Descriptor (DID) 1Knulth, Donald E., The Art of Computer Programaing (Vol. 1)

III.A.8 As in most languages complex data is keyed by dope vectors giving the format of the data. However, in PL/I another level of description is provided in the form of the Dope Vector Descriptor (WJD) (fig. 7). For an array, the Dope Vector Descriptor includes information indicating the number of subscripts in the array. For a string it includes alignment and an indicator as to whether the string is varying. Its major purpose, howeven is to indicate the variable type so that the dope vector may be correctly read. For structures the Dope Vector Descriptor is more complicated. For each level in the structure, there is a dope vector descriptor giving its level in the structure, its dimensionality (including dimensions of containing sturctures) and the offset of the containing structure from the start of the Dope Vector Descriptor. Following the Dope Vector Descriptor are descriptors for the elements in the structure. Those elements include dimensions from the structure, since in PL/I, the elements inherit the subscripting of the structure. Again, parallel to these Dope Vector Deseriptors are the Dope Vectors for the structure 7 7 3I31 The most straightfor- V..:us o l. -;-.....L..................... ward of the dope vectors is 2 the kray Dope Vector (ADV) (fig. 8). It contains a...............................,::'.L, t- l~, -' L-: virtual origin (the loca- - - tion where all subscripts are zero -- even if this L-...__....__ _ __ is outside the array......... 8... bound ),?or':,';..:t' z?>*'e?-ray Jow Vetaor bounds), and for each

III.A.9 subscript a multiplier and upper and lower bounds. This generality allows array operations -- since the dope vector contains not only accessing information, but also bounds information. Arrays are accessed by the equation: Address =virtual origin +~/Si*Mi where Sis are subscripts and Mis are multipliers Note that this allows for interleaved arrays -- arrays which have their vectors separated in core (by equal sized areas outside the array). Interleaved arrays permit easy organization of structures in memory. Strings also have dope c 2 3 7 S 15 is 3o vectors (fig. 9). The 3o! String Dope Vector (SDV) e-....... —--- C -—._ — — CFigure'9 For;.t of the String Dope contains the address of Veczor (SSV) the string, and te maximum and current length of the string. For fixed length strings these two length are equal. The lengths are given in bits for BIT strings,. and in bytes for CHARACTER strings. For bit strings, the bit offset from the beginning of the of the byte is also given. Not much more 0 15 16 31 complicated is the String r —--- Array Dope Vector (SADV) ADV (fig. 10). This is used for arrays of strings. It consist of -- Figure 10 Forsaz o m e?ra S.... Array Do)G Veczor (S.ADV) a standard Array Dope Vector with a word appended to give the string length' (maximum and current), For fixed length strings these two lengths are equal. For varying length string arrays, the current length is set to zero, and

III.A.10 the array accessing algorithm yields the address of a standard string dope vector for the individual strings. This is necessary since in this case each string in the array has a (potentically) different length. The final item to consider is the Structure Dope Vector. The structure dope vector is simply the concatenation of dope vectors of the elementary data types in the structure in the order in which they appear. Subscripting is handled by having the subscripts inherited by the component data elements, using the interleaving array notation to skip over the other parts of the structure which intervene in the core memory. This is necessary since the core data layout is exactly that described by the external structure statement and not by the organization of accessing rules (with respect to inherited subscripting). Here it is especially important to note the use of the dope vector descriptor to interpret the dope vector. Within a routine some of this information may be contained in the code and the full data deoeription may not be read. However, when aggregrates of data are passed among routines, these mechanisms are brought into use. With them PL/I is able to manipulate the highly complex data representations at the heart of all list-processing applications. References (IBM Manuals): PL/I Subroutine Library Program Logic Manual Form GY 28 - 6801 PL/I (F) Language Reference Manual Form GC 28 - 8201 PL/I (F) Programmer' s Guide Form GC 28 - 6591 PL/I (F) Compiler Program Logic Manual Form GY 28 - 6800

III.B.1 Carole Hafner June 8, 1972 LISP INTERNALS 0. History - LISP 1.5 and MIT LISP A-list type binding Value cell binding Linear Atom/ Value Search | Atom —- Value Atom/ Value Hash e- Obarray Atom --- Value *,'Atoms ) Value 1. Atoms A. Atom Header |ID| A(Pname)I A(Plist) 1 A(Value) B. Property List i..A(Indl) J,A A(LValuel) A(Value2) 1 A(NAL) 2, Syntax and Semantics Input to READ: (APPLY FUNC (LIST (QUOTE A) X)) Value returned from READ A(APPLY) A(FUNC) A(NIL) A(LIST) A(NIL A(X) (X) A(NIL)

III.B.2 3. Functions in LISP A. How to invoke LISP functions: If argument of EVAL is an atom, value of EVAL is the value of that atom. If argument of EVAL is a list (...) then invoke (CAR (...)) as a function where (CDR (...)) is a list of its arguments. Ex. Input to EVAL: (APPEND L1 L2) Action of EVAL: Call function APPEND with arguments LI and L2 (CAR (...)) must be one of the following: a. A LAMBDA or LABEL expression. b. An atom with a function definition on its property list. c. An atom which has a LAMBDA expression bound to it as its value. d. A LISP expression which will itself EVAL to one of (a-d). B. Defining and Accessing LISP functions: An atom is defined as a function by having a function definition on its property list. The following special atoms, when used as indicators, indicate that the value to follow is a function definition. a. SUBR - the value is a pointer to the entry point of a machine-coded function. Arguments (a fixed number) are EVALed before being passed. b. FSUBR- the value is a pointer to the entry point of a machine-coded function. (CDR (...)) is passed as a single argument, and is not EVALed. c. LSUBR- the value is a pointer to the entry point of a machine-coded function. Arguments (any number) are EVALed before being passed. d. EXPR - the value is a LAMBDA expression. Arguments are EVALed. 1. LAIBDA-SPREAD - arguments are bound to dummy arguments 2, LAMBDA-NOSPREAD - arguments are pushed on stack and number of arguments bound to (single) dummy argument e. FEXPR- the value is a NLAMBDA expression. Arguments are not EVALed. 1. NLAMBDA-SPREAD - arguments bound to dummy arguments 2. NLAMBDA-NOSPREAD - list of arguments bound to single dummy argument. e. MACRO-the value is a NLAMBDA expression. The entire form (... ) is bound to a single dummy argument. The value returned from the macro function is itself then EVALed. If (CAR (...)) is an atom, EVAL looks for one of these indicators on its Plist, and does the appropriate things if it finds one. The pre-defined LISP function DEFUN is available for defining EXPRs, FEXPRs and MACROs.

III.B.3 Ex: (DEFUN CONC EXPR (LA LB) (COND ((NULL LA) LB) ((CONS (CAR LA) (CONC (CDR LA) LB))) ) Now: (CONC'(XY Z)'(A B C)) = (XY Z A B C) C. Applying LISP function - recursion Case 1. A is a SUBR,LSUBR, or EXPR. (EVAL'(A B C)) First EVAL B Then EVAL C Use the results as arguments to function A Case 2. A is FSUBR, FEXPR (EVAL'(A B C)) a+ Just use (B C) as the argument to function A Case 3. A is a MACRO (EVAL'(A B C)) * Use (A B C) as the argument to function A. When A returns a value, EVAL that as the value of (A B C). 4. Garbage Collection A. General outline of method. 0. Current-cell - POP Entry point, Current-cell is (A. B): 1. If current-cell is marked go to 0. Otherwise: *' IfF 1 2. Mark current-cell 3. Push (CDR current-cell) [Address of (E. F)] 4. Current-cell* (CAR current-cell) [(C. D] 5, Go to 1. B. Problems a. Pname table versus list structure b. Atom header space versus value property c. Concept of a T.W.A

III.B.4 If time permits.. 4. Some special implementation details A. Special system properties B. Atom pointers C. Binding conventions D. Argument passing 5. Running Compiled code in LISP A. Special versus local variables B. Stack manipulation 6. The FUNARG problem and free variables in LISP Example of a LISP macro: (DEFUN CDDR MACRO (X) (LIST'CDR (LIST'CDR (LIST'CDR (LIST'QUOTE X))))) Now lets EVAL (CDDR X Y Z Q ) Step 1. Apply the function CDDR as defined to the list (CDDR X Y Z Q ). This yields the list (CDR (CDR (CDR (QUOTE (CDDR X Y Z Q))))). Step 2. EVAL this result and get (Z Q).

III.C.1 Jim Henriksen History ot Siascript A. SII$CRuIPr- I, IMSCRuiPT 1.5 1. Develojped at Rand Corp. in earLy oO's 2. Rail on 2nd generation hardware of several manufacturers 3. Featured translation of Sirscript into Fortran-II 4. designed for simulation only B. Simscript-lI 1. Developed at sand in late btO's 2. iRuns on lIBl 360 3. Features translation into 360 dssembly language 4. iesigned as a fairly general hign level language 5. lmplementation incomplete C. Simscript II Plus 1. ProJrad product of Simulation Associates 2. Costl y D. Simscript 2.5 1. Program product ot C.A.C.I. 2. Costly General Projram Structure A. PREAMbL - Uefines global variables B. 5AIN program C. Subroutiaes I. Variable modes A. INTEGER B. REAL C. TZXT Variaole Types A. Scaiars B. Arrays 1. iimansionality declared at compile time: DEFINiE X AS A 2-DIMENSION AL AdLiAY DEF1INE AS A 1-DIMENSIGNAL ARRAY 2. Stora e allocated, a Ia EL/ "BASED" variables, at run time: RESERV~ X (*,*) AS 10 BY J RESSRVI Y~(*) AS N 3. Internal storage mode uses pointers, pointer vectors:

III.C.2 RESERVE X(*,*) AS 5 BY 3 RESERVE X(*) AS 10 Stored as stored a t ELEMENTS X(1, 1) ELEMENTS R O XI, X(1) R X(1. 3) -x(, 32 PREAMBLE NORMALLY, MODE IS INTEGER )DEFINE LEVEL AND TREE AS 1-DIMENSIONAL ARRAYSPOINTER (,) X(23) FORX(6) 1 TO N X(7) LEVEL(I)TREE(*) L3 TREE(*)2) (9) "'3', - ~~~~~~~~~~~~~~X(4 2) |X(5b.l-)- X(4, 3) x(5s. e) X(2.2),+ Notation, aitaougn clumsy, exists to Lanipulate polnters: PREAMBLE NORMALLY, MODE IS INTEGER DEFINE LEVEL AND TREE AS 1-DIMENSIONAL ARRAYS END READ N RESERVE LEVEL(*) AS N FOR 1=1 TO N,.DO RESERVE TREE(*) AS 2'*(I-1) READ TREE LET LEVEL(I)-TREE(*) LET TREE(*)-0 LOOP.ND For N-4, the memory seructure at the end of program execution loolk as follow:t LEVEL TREE 4 1 I c1819110 111112113 j 4 16

III.C.3 C, Eatities aau Sets 1. Eutitles hdae declared attrLioutes aiai declared [potentiai siet muembersiiips ana oiiier:siips. EVERY MAN HAS A NAME,AND AN ADDRESS,OWNS SOME CHILDREN AND MAY BELONG TO THE MASONS,A CHURCH, A FAMILY AND AN ALUMNI.CLUB EVERY X HAS A P,A Q,A Z AND AN A EVERY PROGRAM HAS AN ENTRY,OWNS SOME LABELS, BELONGS TO A PREAMBLE AND HAS A LENGTH 2. Set memDersli.p i mpiemented Ljy a strdightforward system ot ipljicitly allocateu ointecs: COMMUNITY F. MASONS MAN1 L MASONS P. MASONS 3. S.MASONSez.' MANl ai. Permanent entitles.stoed as arrays: word PASONS S, MASONS MAN3 MAN4 \I MASONSO S. MASONS 3* Entity storage allocation a. Perwfanent entiLtles stored (S drrdays: word 1 w.ord N.CITY O. Temporary entities stored as based structures

III.C.4 4. Entity field ana bit packiuy: Declaration: EVERY MAN HAS AN AGE(1/4), A NAME AND A SEX(1/4) Entity record: word 1 AGE word 2 NAME word 3 SEX Declaration: EVERY MAN HAS AN (AGE(1-8) AND NAME(9-32)) Entity record: 1 9 word 1 AGE NAME Declaration: EVERY PART HAS A (RIGHT.VALUE(2/2),LEFT.VALUE(1/2),ITOTAL.VALUE) Entity record: TOTAL.VALUE word 1 ILEFT.VALUEIRIGHT.VALUEI Declaration: EVERY MAN HAS AN (AGE(1/4),NAME(2/4),WEIGHT(17-32)) AND OWNS A FAMILY, Entity record:s word 1 AGE NAME WEIGHT word 2 F.FAMILY word 3 L.FAMILY Declaration: EVERY MAN HAS AN AGE(1/4),OWNS A FAMILY,HAS A (NAME(2/4) AND WEIGHT(2/2)) Entity record: word 1 AGE word 2 F.FAMILY word 3 LFAMILY word 4 INAME WE|-HT

III.C.5 5. Special putpose -suoroutlnes constructed to carry out imeoersuaip functions ot each set D, Eveat notices 1. Two types a interial D. Exogenous - read trom a naibiered I/O unit 2. Look like a temporary entity a. das implicit dttributes TiJiE.A,, the simulated time OL the eve at. aiia EJ NIT.A, the unit ~rom which the event aotice was zead b. Has implicit Membership i4 the set EV.S PREAMBLE EVENT NOTICES INCLUDE ARRIVAL, WEEKLY.REPORT AND END.SIM EVERY JOB.OVER HAS A NEXT.JOB AND OWNS SOME RESOURCES When created, records for these event notices look like ARRIVAL WEEKLY.REPORT END.SIM JOB.OVER word 1 TIME.A TIME.A TIME.A TIME.A word 2 EUNIT.A EUNIT.A EUNIT.A EUNIT.A word 3 P.EP.EVS P.EV.S P.EV.S P.EV.S word 4 S.EV.S S.EV.S S.EV.S S.EV.S word 5 M,EV.S M.EV,S M.EV.S M.EV.S NEXT.JOB F. RESOURCES L. RESOURCES N. RESOURCES

III.C.6 3. Priority ot event- iotices.iplemented vid xndoex into suOscLrpted set EV.S da Detdult priority OL event notices is in oraer of occurrence in ueclaraticas. b. Detduit overricden by "PRIORITY ORDIa IS" statement F. EV. S Event set are ordered by PRIORITY or their order of appearance in the PREAMBLE All sets are ordered by BREAK TIES specification or time ranking / 0 1 1 1 1 1 STOP. SIMULATION r ARRIVAL 0 SHIFt. CHANGE 0 0 END. OF. JOB 8TART. lOb

III.C.7 4. Zvenat notice creatioIn a. Crcated automaticdlly iOL exogeilous events: 1. At Lniitidillzdti aoi (1 T ART SIMULATION) 2. At exit frcm event o utille b. Created under program control for internal events by use ot the "SCHEDUISE" statement i. Control StLucture - a recursive calling.protocol 1 Rnmpw CSECT 2 USI NG *,1 5 labeled YIELDING Arguments, is the area in which yielding argument 3 USING H,7,8,9 vales are stored prior to return to the calling routine. The fourth 4 B F 5 DC AL2 L section, labeled Recursive Local Variables, is the area in which a1l 6C AL? (recursive local variables of the routine are located. When a routine 7 DC AL2 X a DC AL2 T-'+10) is called, XREC zeroes out the yielding and recursive areas. 9 F L 2,0(1) 10 DROP 15 11 BALR 0,2 UH. BODY 12 H EQU O The routine body must conform to several conventions concerning: Fig. 1 —Prologue fonrmat (a) accessing GIVING argu=ent values (b) returning YIELDING argument values t BALR instruction (line 11) passes control to XREC, a S-) ing ac) *ccesseng recurslve local variables:1 system routine that establishes a eanue:rea, and returns (d) using registers.'ess of the save area's first'byte in general register 6. The a:, illustrated in Fig. 2, is divided into four sections. GIVING Arguments General register 6 points to the first byte of the save area. S -ystem To access the value of the first GIVING argument, the -rogra=-er aust'Data refer to the first four-byte word after the System Data section of the (52 bytes) save area, i.e., the word whose address is 52 bytes greater than the GIVING | contents of general register 6. The first GIVING argument is at 52(6), Argument s the second at 56(6), etc. The i-th giving argument tis addressed as (4*g bytes) L [52 + 4*(i - 1)1(6). YIELDING bytes As an example consider the calling sequence: Argument / (4a bytes) /' CALL GET.DATA GIVEN I,J AND K YIELDING M AND N ~ L Racursive Local bytes value of I to stored at 52(6), the value of J at 56(6), and the Variables value of K at 60(6). (4*r bytes) __J YIELDING Arguments Fig. 2 —Save area format The first YIELDING argument follows the last GIVING argu=ent; in first section, labeled System Data, contains such items as general, the address of the t-th YIELDING argument value is mn point of the calling routine. It should not be used by 152 + 4*g + 4*(i - 1)1(6). In the above exanple. the value that wi''amer. The second section, labeled GIVING Arguments, con- be stored in M when control returns to the calling routine is at 6:(6) I tatue of the routine's giving arguments. The third section, The value that vill be stored in N is at 68(6). I. Storage Allocation A. Permanent entities, arrays - inaiviauai GFETMRAIT's B. Te porary eatities 1. ChecK jcol ot desired size 2. GETiAIN i:t nonie in pool 3. Released blocks returned to kools ana "branued.'" 4. Continues until no more storage available, tuen FLEEMALN ot all tree blocks acne

III.D.1 String and List Processing Seminar Thursday, June 15, 1972 G. Lift Snobol Internals Data Organization resident data - system things allocated data - handled by storage management routines all data created by source language programs Data Representation descriptor (Snobol's unit of storage) used for all source data objects (often several descriptors together) structure T F| V| T field: data type code (usually) F field: various flags eg., A flag means V field contains pointer to allocated data region V field: datum, or pointer to structure for datum simple examples: integer 5 IL I 5 pattern A I is the type code for integer, P for pattern internal objects often have other arrangements S/360 implementation: 2 words / v..F T 1 0 4 5 7 qualifier (for character strings) - 2 descriptors TI F V 0o L V: "base" pointer to string data 0: displacement of beginning of string from V pointer L: string length T,F as before example: string ALGORITHM string OR l X1 g 1.~I _9 iL i * J..3 }. 2 - ALGORITHM

III.D.2 Data Structures natural variables - in allocated data region NT --- descri value c title descriptor: T field - length variable name label c F field: T flag - title descriptor chain c N flag - natural variable! string value descriptor: value of variable, or pointer to structure label & chain descriptors (see below) string (var. name) stored in consecutive descriptors following chain descriptor, padded with blanks example HUNTER = 5 6 TNT- *I 0. means.IK i- | j written {HUNTER} note j..... means /.V-,..... l-. 1HUNTERHUNTER ='WOLF' changes value pointer to L I j 7 WOLF other data types (patterns, arrays...) - represented with blocks of descriptors, always beginning with a title descriptor: j *1- the T field contains the number of descriptors in the block, not counting the title descriptor arrays: block contains a descriptor for each array entry, a descriptor for each dimension containing the lower bound and extent of that dimension, and header information (# dimensions,...) all entries are allocated at definition tables: block contains two descriptors for each table entry (since an entry is an ordered pair), and header information user defined data types: block contains a descriptor for each field, and two descriptors for header information patterns: see later

III.D.3 statement labels: natural variable structure with label in'string field' has pointer to code in label descriptor code: sequence of function and operand descriptors function descriptors: T field: #arguments in call F field: F "function" flag V field: pointer to link descriptor pair for function operand descriptors: same form as source-language data link descriptor pair:.. ~........ > to function procedure / i, -, _'-" _... #arguments in function definition second descriptor used only for special functions e.g., user defined code is arranged in a prefix code format, with each function descriptor followd by its arguments example: X = Y * -SIZE(Z) S A descriptor p i t.....usuall -- (x}. 2: F -k-no 2 l -o o multiply(*) S A {y} 1 F -....! 1 unary S A several function descriptors may point to the same link descriptor pair, i.e. there is usually one pair per function. SNOBOL knows the location of all existing link descriptor pairs executing OPSYN alters the pointer in the link descriptor pair literals in code are handled by a procedure'lit' with one argument

III.D.4 2: F example X = Y S A - f f{X} S A - + {Y} X ='Y': S A - {X} 1 F lit S Agotos are handled by a goto function whose argument is a statement label Strings and Variables when string created by any source language operation, natural variable structure used to represent it only one copy of any string in allocated data (no'sharing' of substrings, though) example: after executing S A X ='AB''C' IL Y'A''BC' L X { } N1 T * 177] L LI

III.D.5 table of natural variables - each string in hash code table hash coding C (O<C<255) hashes into table of 256'chains'; string put on that chain hash coding N - chain ordered by increasing N both hashes are on char. string V field of chain descriptor has pointer to next on chain (last 0) T field of chain descriptor contains N access for variable (or string) involves search to determine if already present & creation if not Patterns construction each component corresponds to 1 matching operation component 3 F function descriptor V F -4 connector descriptor.. — heuristic descriptor i i.- [argument descriptor] if the matching function has no argument, there is no argument descriptor, and the T field of the function descriptor contains 2 i ~ Fr I _ iri3!F example LEN(4) X -'- -. "' - X. 3 i - > LENP # args as.i::. _-i # real args in call I 0 4 connector descriptor V field: offset of alternative (0:none) T field: offset of subsequent (0:none) offsets are from beginning of pattern note the number of arguments includes alternate/subsequent and heuristic

III.D.6 example pattern POS(O)(TAB(2) I LEN(4)) 12d T * 3 F 0.. pOS 4d O 0 heuristics 3 F 4... tab 0 0f8d1 — f- heuristics TI 0 12 3 F... len O t I o0 4o example pattern component for ARB 2 F 2 null 3 0 0 2 F j- 2 null o o 6 2 F 2 —-~ I farb AW (advance cursor) 0 0f 6

III.D.7 Storage Management allocation: allocate from free pointer, move free pointer down thru allocated region ex: allocate block of 5sL'11_.... 9 5d I T- d* descriptors free.-. o 0 0o i returned; —- - - pointer 0 0 0o;o 0 0 free —. pointer note that the descriptors in the block are zeroed ex: allocate natural (new) variable HUNTER ~ _ N * free pointer5 5 0 O o 0 0 prey var on chain N 0N —.next var on chain free pointer- - returned HUNTER pointer note some fields are zeroed, and the variable placed on the appropriate chain

III.D.8 garbage collection - useful objects are marked, then compacted into top of allocated area mark - M flag turned on in title block of object marking algorithm MARK - recursive procedure begin with basic blocks (resident data); at first flag encountered, find title block of object pointed to case 1: no mark on this title - mark this new block; push pointer to old block on SYSSTK; call MARK with new block case 2: marked title - ignore (this does not go thru the chains of natural variables) then mark any natural var. with non null label descriptor or non null value relocation of useful objects - phase 1: linear pass thru allocated area - change V pointers of marked title descriptors to new value phase 2: adjust all pointers (on linear pass) of basic blocks and marked objects (using new title V fields) phase 3: relocate & unmark (on linear pass) remove useless nat. var. from chains References not much available Griswold, RE. Snobol4 - Structure & Implementation Share XXXVII; 12 Aug 1971. Macro Implementation of Snobol4 WH Freeman, in press.

IV.A. 1 String & List Processing Seminar Thursday, June 22, 1972 Jim Hamilton MTS-UMMPS Storage Allocation and Selected Applications I. General Requirements A. Must be completely general, i.e. must provide variable size blocks B. Since storage allocation structures exist for as long as the system is up, storage must never be permanently "lost" due to causes such as fragmentation. Hence most structures are maintained in increasing location order. C. Must obviously be application independent, hence such things as garbage collection, reclaimation, compaction, etc. are impossible. The only relocation possible is that provided by the DAT hardware, hence the mechanisms will often be page-oriented. II. Storage Allocation for Supervisor Subroutines A. Requirements and properties 1. Speed - must be very fast, for commonly used block sizes (e.g. PCBs) because of heavy usage 2. Must never run out of space, since the system will crash if this happens; paging, plus some care in coding, avoid this problem 3. Supervisor code is "dependable", so little error checking need be done. 4. Storage demands are, in a sense, fixed, since the supervisor itself is a closed system (requests from tasks are considered separately in the next section) B. Pools 1. For very fastest allocation of fixed size (8 byte) entries for a. CPU Queue b. WAYT Queue c. I/O Queue 2. Separate, pre-allocated areas with space for 255 of each type 3. Free space is simple linked list, done with offsets 4. Use of pool index allows "pointers" to fit in one byte C. The Page Chain With the exception of the pools, all dynamically allocated storage is taken from, and occasionally returned to, a page chain which is just a simple linked list of available pages. The page chain is constructed at initialization. All other available storage structures are initially empty. The Supervisor never deals with blocks of real core larger than a page.

IV. A. 2 D. GRAB-FREE Subroutines 1. For every block size less than SVCASPEC (currently 96 bytes) there is a special chain containing blocks of the corresponding size. Calls to FREE always return small blocks to these chains, which are kept in LIFO order. Calls to GRAB will take a block from the proper chain if it is non-empty; otherwise it is allocated as described in 2. 2. There exist two chains of arbitrary size blocks, maintained in increasing location order to allow recombination. One is for blocks smaller than SVCABIG (currently 1024 bytes) and the other for larger ones. All blocks larger than SVCASPEC are returned to these chains, and blocks of any size less than a page are allocated from them, using a first fit algorithm, and splitting blocks when necessary. 3. If a block of the desired size or larger is not available, take a page from the page chain if there are any, and add it to the large or small chain according to size of the request, and try again. 4. If the page chain is empty, begin moving blocks from the special chains for small blocks to the arbitrary size chains, and continue until a large enough block has been found, or until all are moved. The latter case is followed by a superdump. 5. An example storage layout is shown in Figure 1.

IV. A. 3 III. Storage Allocation at the Task Interface A. SVC GETBUF, GETSEGX, and FREEBUF 1. Absolute tasks (GETBUF): a. Maximum of 4 buffers allowed b. Maximum size one page c. Does some error checking, then calls GRAB or FREE d. The address and length of the allocation are recorded in a 32 byte table pointed to from the job table (4 buffers X 8 bytes = 32 bytes). This is done so that the storage can be recovered if the task goes west. 2. Relocatable Tasks a. GETBUF implies segment 4, GETSEGX specifies any of 3 through 8 b. All requests rounded up to a page boundary c. For each task there is a PCB (Page Control Block) chain maintained in increasing virtual address order, one PCB per allocated virtual page. d. Supervisor scans PCBs until it finds a large enough hole in the desired segment, then GRABs the required number of PCBs (24 bytes each), initializes them and inserts them in the chain, it never explicitly allocates real core. It implicitly references the first page, however, into which it stores the length of the allocation. e. For FREEBUF the PCB chain is scanned for the PCBs describing the freed region. The real core pages, if any, are put back on the page chain, and the PCBs are removed from the task chain, and the Page Out Queue if necessary, and put on the Release Page Queue, where we will leave them for this discussion. Actually the FREEBUF routine is horrendously complex (more so than any other routine described here) but most of its complexity is irrelevant to us. B. SVC GETSC, FREESC 1. For absolute tasks only. 2. These go directly to GRAB and FREE after checking to be sure there is at least one page on the page chain. C. SVC GETRP, FREERP 1. Used only by the PDP to get or release pages of real core to be attached to PCBs. 2. GETRP just takes a page from the page chain if there are at least two pages there. 3. Otherwise it scans the small and large chains of supervisor pages and moves any full page blocks it finds over to the page chain. If it found any, it tries again. Otherwise it gives up, and the PDP will try again later. 4. FREERP essentially just adds pages to the page chain, unless they have been reclaimed or released.

IV.A.4 IV. Storage Allocation in MTS (GETSPACE/FREESPAC) A. General Requirements and Properties 1. Since this is the user interface, thorough error checking must be done. 2. It must be possible to recover the storage which has been allocated, in case user programs or various levels of system programs go west, or even when they terminate normally. 3. Storage management structures are maintained in system level storage, separate from the storage being managed; there are two reasons: a. It is undesirable to reference VM pages before they are needed. b. The user cannot be trusted to confine his references to storage which is allocated to him. 4. The VM integral must be computed, to keep the accounting people happy. B. Buffer Control Blocks (BCBs) The storage allocation structure is composed of fixed size (16 byte) buffer control blocks. These too must be allocated and freed. This is done using a conventional LIFO free space list. One page of BCBs is allocated initially (via SVC GETSEGX) and more are allocated if necessary, a page at a time. All BCBs are in segment 4. C. Storage Management Structures 1. One may wish to look at Figure 2 while reading the following. 2. Primary buffers: Storage requests obtained from the supervisor via SVC GETSEGX are called primary buffers. Each primary buffer is descirbed by two primary BCBs (PBCB1 and PBCB2) and one or more sub-buffer BCBs (SBCBs). VMI accounting is done at the primary buffer level. 3. Each primary buffer may be divided into one or more sub-buffers. Each sub-buffer is described by one SBCB. The SBCB also describes the free block following the allocated block. 4. The PBCB1 blocks are linked in increasing location order, and each points to a PBCB2 block, which points to a list of SBCBs, which are also in increasing location order. There is a separate list of PBCB1 blocks for each segment. D. Detailed BCB Definitions 1. PBCB1 (all entries are fullwords) a. length of longest free block in buffer b. location of first byte past end of buffer c. link to next PBCB1 d. link to PBCB2 for this buffer

IV. A. 5 2. PBCB2 a. number of sub-buffers (2 bytes) b. length of buffer in pages (2 bytes) c. location of first byte in buffer (4 b ytes) d. number of free bytes before first sub-buffer (4 bytes) e. link to first SBCB 3. SBCB a. storage index number (1 byte) (read volume 5 to learn about these) b. length of allocated block (3 bytes) c. location of first byte after block (4 bytes) d. length of free block following (4 bytes) e. link to next SBCB E. GETSPACE Algorithm 1. Search PBCB1 list for desired segment; looking for first one which has a free block equal to or longer than desired. If not found, go to step 4. 2. Search the SBCB list (including PBCB2) for the first free block equal to or longer than desired. There must be one, or we blew it. Insert a new SBCB after it to describe the new allocation and any remaining free block. 3. If the free block found in 2 is equal in size to the largest free block recorded in PBCB1, the SBCBs must be searched again to find the new largest free size. Then we are done - return. 4. Issue SVC GETSEGX; if this fails, go to step 5. Get and initialize a PBCB1, a PBCB2, and one SBCB, describing the requested allocation, plus any remaining space in the last page. Search the PBCBls and insert the new one at the appropriate place. Compute the VMI and new total page count. 5. Must be insufficient space left in this segment. If a specific segment was requested, or if we have already tried segment 8, tell somebody about this problem. Otherwise, increment the segment number by one and go to step 1. F. FREESPAC Algorithm 1. Find the SBCB whose allocated block completely contains the one being returned. This is a two step process, going down first the PBCBls, then the SBCBs. It is a nono if its not there. 2. Compare the freed block to the allocated block. There are 4 cases. a. same - this is the normal case. Update field d. of the previous SBCB with the sum of itself and fields b. and d. of this SBCB. Unlink and free this SBCB. Update the maximum free block in PBCB1 if necessary. Decrement the subbuffer count (in PBCB2); if this is zero, the entire buffer is free, so issue SVC FREEBUF, unlink and free the PBCBs, and do VMI accounting. Return.

IV. A. 6 b. Starting addresses the same. Update this and previous SBCB accordingly. c. Ending addresses the same. Update this SBCB accordingly. d. Neither address is the same. Get a new SBCB and insert it before the current SBCB. You should be able to figure out how to diddle the various fields. 3. Update the maximum free length in PBCB1 if necessary, and return.

IV. A. 7'MLE chtA e4t/.N P/ /i//6/L/g~ S9 41 cF 9'' o RMAM or ///////// SMKLL. F4RSEZ B Lo i m S LE"AXarT I FsZST L \ \o?4D t4K. RS Ok R~ tO L///// S cDevD AAs ARE ALoot ARJE&///AED UL%-t4KGD PAcgES hRE ALLOAE D

IV.A. 8:: Pc DI A 2- - A A2,iin ArLac T _ 6l 1 a~~ tj.._~ SHAD~~~-'~i!RA R LOAE FIGUK 2 - ~5 SoR~G Lo~r

IV. B. 1 UNIMPS PAGING ALGORITHM Jim Hamilton I. Before descending into the details of UMMPS and the PDP, it is probably instructive to say a few words about paging algorithms in general. They may differ in several important ways: 1. Demand paging vs. Anticipatory paging:Under demand paging, a system will move a page to main storage only when it is referenced. On the other hand, a system may attempt to anticipate the need for some pages, and page them in before they are referenced. Almost all current systems use demand paging. 2. The algorithm may be task oriented, or system oriented. That is, the decision as to which pages to move to and from main storage may depend heavily on the status of the task which owns them; this would be a task oriented algorithm. With a system oriented algorithm all pages in the system are treated identically, independent of their owners. 3. The replacement policy, for choosing pages to be removed from main storage,may vary considerably. This is probably the most important factor affecting the performance of paging systems. There are several possibilities discussed in the literature: a. FIFO - The oldest page in storage is chosen for removal. This is clearly not a very good choice, but early versions of UMMPS used it. b. Least Recently Used (LRU) - The page with the longest time since last reference is chosen for paging out. Note that this algorithm can only be approximated on the 360/67, and most other current processors. c. Working Set - The system keeps a record of recent references to pages by a task and attempts to keep a "working set" of pages belonging to a task in core. This is a task oriented policy, which attempts to estimate program behavior. It is said to be a nearly optimal realizable algorithm. d. A-Optimal - The page whose next reference is farthest in the future is chosen for removal. This is, in some sense, an optimal algorithm, but is unrealizable without knowledge of future page references. It is mainly a standard for comparison. UMNIPS uses basically a system oriented demand paging algorithm with an LRU replacement policy. The supervisor is totally responsible for these aspects of paging and their implementation is found in the GETWP SVC, which will be described in some detail later. The Paging Drum Processor (PDP) is responsible for the actual transfer of pages to and from the paging devices. In the remainder of these notes we describe 1) the UMMPS - PDP interface, 2) the PDP, 3) IJTMPS (mainly GETWP), and 4) a day in the life of the average page.

IV. B.2 II. The U~MPS - PDP Interface A. Data Structures: The primary data item containing information relevant to paging is the Page Control Block (PCB). A PCB is 24 bytes long and contains the following items: 1. Virtual address 2. Real Address 3. Pointer to owning TCB 4. Task page chain pointer 5. System Queue pointer 6. Reference Bit 7. Change Bit 8. External Address plus several other items which don't concern us here. PCBs are created by the GETBUF SVC, and are released by the PDP. There are four queues used by the system in managing paging. These are: Page-In Queue (PIQ) - Pages to be brought into core from secondary storage Page-In Complete Queue (PICQ) - Pages which have just been brought into core. Page-Out Queue (POQ) - Pages which are in core, ordered approximately from least recently used to most recently used. Release Page Queue (RPQ) - Pages which have been released (via FREEBF SVC). B. Special SVCs There are five special SVCs which are used only by the PDP. These are: GETRP - Get real page - Used to get a real page of core to read into, for a page-in operation. FREER.C - Free real core - Used to release the core allocated to a page after it has been paged out. GETWP - Get Write Pages - Removes a specified number of pages from the POQ, to be written out. GETQS - Transfer the contents of the PIQ and RPQ to the PDP. PDPWAIT - Tells UMMPS the PDP has nothing more to do. It will be restarted by a completion interrupt from any of its devices, or when UMMPS decides there is more for it to do (i.e., PIQ non-empty, or pages need to be written.

IV. B. 3 III. The Paging Drum Processor A. Overview - It is the responsibility of the PDP to manage the paging devices, which currently include two drums and one disk. Each drum holds 900 pages, and the disk holds 6400 pages, for a total of 8200 pages. The worst case observed to date has been something over 4000 pages, and a typical heavy load is between 2000 and 2500 pages. The disk is used only when the drums are nearly full, and at this time the PDP chooses pages on an LRU basis and moves them from drum to disk. This is called page migration. The PDP consists of two asynchronous parts: the first builds channel programs and starts them via SVC STIO, and the second handles the completion interrupts and posts the completion of the paging operations. B. In order to understand the operation of the PDP, it is necessary to understand the workings of the paging drum................ X-......" 1 page - 100 tracks, each with its own read-write head. The picture shows the logical structure of the paging drum. Physically there are 200 tracks, with 4 1/2 pages per track, but the PDP treats it as shown, with the difference obscured by a trick in the channel programs. The PDP constructs channel programs for all nine slots at a time. It will then chain these together if possible. The PDP is so designed that the drums can be kept running for an indefinite time with only one SIO, with reads in the appropriate slots, and with writes filling in the rest as necessary. Using this method, writes (i.e., page-outs) are essentially free. C. PDP Data Structures - The PDP maintains a huge data block for each drum. Each such block contains, among other things: 1. 9 Local Page-in queues, one for each slot. 2. 3 channel program buffers 3. Spaces for 27 PCB pointers for the PCBs associated with the 3 possible channel programs. 4. A bit table describing available space on the drum; organized by slot. 5. 9 migration lists, one for each slot of PCBs ordered from least to most recently used. ("used"t in this context means paged-in or paged-out.)

IV. B. 4 6. A local page-in complete queue There is also a data block for the disk. Since the disk is managed on a page at a time basis, with no attempt at optimization, this data block contains only one local page-in queue, one channel program, one current PCB pointer, and the bit table. There is also a "global" local page-in complete queue, on which the local PICQs from each device are collected, and whose contents are occasionally transferred to the supervisor's PICQ. D. The algorithm 1. Get the PIQ and RPQ via the GETQS SVC. 1.1 For each PCB on the RPQ, release its external address, free its real core page via SVC FREERC, if there is one, and free the PCB, via FREESC SVC (Free Supervisor Core). 1.2 For each PCB on the PIQ, add it to the end of the local page-in queue for the appropriate slot on the appropriate drum, or to the LPIQ for the disk. This process is called slot sorting. If the PCB has no external address, put it on the local PICQ now, since it must be a new page. 2. For each drum do the following: 2.1 Allocate a new channel program buffer if possible. If not, go try the next drum. 2.2 For each slot: if the LPIQ for the slot is non-empty, remove the top PCB, get a real page via SVC GETRP if possible, and construct a CCW to read the page in. If no core is available, go to step 2.3 immediately. 2.3 If there are slots available which don't contain reads, check drum availability; if there are less than MIGTH pages left on all drums, and if no migration is currently in progress, take a page from the top of the migration list for one of the available slots, and construct a CCW to read it into a page of supervisor core. Remember that a migration read has been started. MIGTH, the migration threshold, is currently set to 50 pages per drum, or a total of 100 pages, with 2 drums. This will probably be reduced in the future. 2.4 If there are slots available which have no reads, and which have unused tracks for writing, issue SVC GETWP, requesting as many pages as there are available slots. 2.5 For each PCB returned by GETWP, see if it has been chanced. If not, and it's on the drum, just issue SVC FREERC. If it has been changed, or is on the disk, free its existing external copy, and construct a CCW to write it into one of the available slots. 2.6 If there are still some available slots because of unchanged pages, issue another GETWP, and go to step 2.5.

IV.B.5 2.7 If any reads or writes were set up in 2.2 through 2.6 above, package up the channel program and either issue SVC STIO if no channel program is currently running, or chain it to the end of the current channel program, with a TIC command. This completes the setting up of channel programs for the drums. 3. For the disk, do the following: 3.1 If the disk is already running, do nothing. 3.2 If the local PIQ for the disk is non-empty, issue GETRP for a real page, and construct a CCW to read it in. Go' to step 3.4. 3.3 If a migration read was set up in 2.3, then allocate a disk page and construct a CCW to write it out. 3.4 If anything was done in 3.2 or 3.3, complete the channel program but modify it so only the seek is done, then issue SVC SIOG. This way the channel is not busy during the seek. 3.5 When the seek terminates, restart the channel program, doing the whole thing this time, unless we are doing a migration write, in which case we may have to wait for the completion of the read. This completes the setting up of disk channel programs. 4. Collect the local page-in complete queues from the several devices and add them to the "global" local PICQ. If there are any new pages on this queue, issue a GETRP for them. If GETRP fails, keep these pages on this local PICQ, but put all completed pages on the supervisors PICQ. The supervisor will eventually find them there and restart the waiting tasks. If any channel programs were started above, go to step 1. Otherwise PDPWAIT. This completes part one of the PDP. The remainder of the PDP consists of device-end and PCI (program controlled interrupt) interrupt routines. The PDP arranges to receive a task interrupt at the completion of any of its channel program buffers, i.e., once every logical drum revolution, from each drum. At such times it does the following steps: 5. For each PCB in the channel program just completed, do the following: 5.1 Add it to the bottom of the migration list for the appropriate slot, if this is a drum. 5.2 If it is a read operation, add the PCB to the local PICQ for this device. Go to step 5.4. 5.3 If it is a write operation, free the real core page, via FREERC. 5.4 Free the channel program buffer 5.5 If this was a device end, mark the status of the device as stopped. 5.6 Return and re-enable the interrupt.

IV. B.6 This completes the description of the PDP algorithm. Many details of the actual implementation have been omitted for simplicity, but most of the important ideas are there. IV. The Supervisor In this section we discuss the algorithms for the five PDP SVCs, plus the subroutine TRANS, which is called to handle paging exceptions, among other things. All but TRANS and GETWP are, at least conceptually, simple, but all are mentioned briefly, for completeness. PDPWAIT - Save the TCB pointer for the PDP (this is the only way the supervisor knows which task is the PDP). Remove it from the CPU queue. Save the restart address (a parameter in GRO) GETQS - Lock the PAGQ lock, pass the PIQ and RPQ pointers to the PDP, set these pointers to zero, unlock, and return. This must be an SVC because only the supervisor can do the required locking. There are several variables which control the page replacement policy, as implemented in the GETRP, FREERC, and GETWP SVCs. These are: 1. NFRPGS - Number of free pages available 2. MINFRPGS - Minimum number of free pages which must be maintained, currently = 1 3. NWRTPGS - Number of pages being written out 4. WRTFRPGS - The threshold for deciding when to write pages, currently = 15 GETRP - If the number of free pages is greater than or equal to MINFRPGS, remove a page from the free page chain and decrement NFRPGS. Otherwise indicate that no page is available. FREERC - Add the page to the free page chain and increment NFRPGS. GETWP - A little more complicated 1. If NFRPGS + NWRTPGS > WRTFRPGS, return zero pages. 2. For several reasons, the proper operation of GETWP requires that no CPU be relocatable. Therefore, if the other CPU is relocatable, a WRD instruction must be executed at this point, which causes an external interrupt to the other CPU. A flag is then set which will hold up the other CPU until GETWP finishes its work and resets the flag. 3. Starting at the top of the POQ, do the following for each PCB encountered, until either getting enough pages to fill tihe request, or until reaching the end of the POQ. 3.1 Update the reference and change bits in the PCB with those in the storage keys for the real page. 3.2 Set these bits in the storage keys to zero. 3.3 If the page has not been referenced, add it to the list of those to be paged out. If it belongs to a non-privileged task, page it out anyway. If it has been referenced, reset the reference bit and move it to the end of the POQ.

IV.B.7 3.4 If a page which has not been referenced belongs to a task which is running on the other CPU, don't page it out; instead leave it on the POQ. 3.5 Each page to be paged out is removed from its page table. 4. Update NWRTPGS, and return. TRANS - A supervisor subroutine called by anything which needs to reference a virtual address, which means mainly paging exceptions, but includes other parts of the supervisor as well. The algorithm for TRANS is: 1. Try an LRA instruction, if this works, return. 2. Search the task PCB chain, or shared PCB chain if segment 2. If not found, simulate program interrupt 5. 3. If the page is being paged in already, chain this request onto the previous and go schedule another task. 4. If the page is being paged-out, mark it as reclaimed, update the page-table, and return. 5. If the page has an external address, put the PCB on the PIQ, and schedule another task. 6. If the page has no external address, it must be new; try to get a real page for it. If successful, return, with the page table updated. Otherwise put it on the PIQ, and the PDP will retry. V. A Day in the Life of the Average Page The chart on the next page illustrates the various transitions which may be encountered by a page during its lifetime. Note: only those SVCs are shown which deal with the particular page we are watching.

IV. B. 8 _~~~~~~~i t - Xj< R —, - tw i s's I l t N~~~~~~~~ i" sJ, L; 44. f ~,-~,/r c~i n 1~~~~ —-~ ~~~~~~L(t _\ _~~U _) __.~L~~~~~~~~~~~~~~~~. +,.. _ _. _ _ec _ _(f~( _ _ Y~~c ~~ i i i~,~. - T- - r - - - - -c ( —J, I- - - - -... _ _ t c__! 4 i -, f~~~~~~~~~~ i _, 5C I. j lD \,'I~~- S)L>\4 thb I r _ i --- _ scc j Howe,)e I I ___X_____I o'.erS *48-Kv i t - l\;,l tt r\ it< a _ _ 1~~ i S >r3 is j~~~~~ I > t~ ~ ~ ~~~~~C _ _C O~ _~\ _, _, rt3 9;t I 5 Pcii \-'<X s~t 1 t _D v +r,> t -S~~~_t r~ ~ ~ ~~` t _ I NitCc i ~ ~~~~~~ | 5.,vh 12i'Y 4 l~~~~~~~k 75 t s t' f';Aa- 0~t ~5 U'..... 3 -\,>X?D C~r-i ic~\ i`?

Jon Bauer ccs 500 June 28,'72 The Michigan Graphics nterpreter1 In the few pages that follow, I'll describe the major features of the MGI routines and how they're implemented. A large portion of the paper will be devoted to describing the MGI routines setting the ground-work for explaining the implementation which is actually quite straightforward. The MGI system consists of a set of Fortran-callable routines. They were written to be device independent and to that end, they generate no hardware graphics commands directly. Rather, they return graphical data which, in turn, can be used to drive hardwaredependent graphic routines to draw the images. The MGI system was written to manipulate graphical objects called'elements'. Routines perform three basic operations. Elements may be created, transformed, and recovered by calls to the appropriate rout i nes. The current MGI system handles three types of elements:'parts','transforms', and'assemblies'. A part is an element which defines a three-dimensional graphical entity in terms of points and lines. A transform is an element which can cause a part to be scaled, rotated, viewed in a perspective, and/or translated (moved). An assembly is an element which defines a heirarchical relationship between parts and subassemblies and transforms. A transform can be applied to parts and assemblies.

IV. C. 2 Parts A part is completely defined by the following data... 1. A legal MGI name, 2. The number of points, 3. The homogeneous coordinates of each point, and 4. An attribute number for each point. A call to the appropriate routine with the above information causes the part to be created. A'legal MGI name' is defined to be a string of non-blank characters, left justified to a full word boundary followed by a blank. Up to six non-blank characters may be specified. (MGI nrames are also used to name transforms and assemblies.) Four homogeneous coordinates are used to define each point of a part. They can be written. (HX,HY,HZ,H) where the normal coordinates can be recovered by. HX HY HZ X=- Y- z= —Z H 4 — H If we wish to express the normal coordinates (X,Y,Z) as homogeneous coordinates, we could of course write (X,Y,Z,1) The reasons for representing points using homogeneous coordinates are.. 1. Three dimensional transformations may be represented and performed very simply in this coordinate system, and 2. Points at infinity can be described using finite numbers. The first and more important reason should be easier to understand after reading the next section on transforms. Attribute numbers (one per point) are generally used to specify the type of lines to be drawn to the corresponding points. For example, zero might be used to indicate invisible lines and one to three may indicate different line intensities.

IV. C. 3 I z Figure 1 Using this convention, the shape shown in Fig. 1 could be defined by: Point X Y Z Attribute 1 0 0 3 0 2 2 0 3 1 3 0 2 3 1 4 0 0 3 1 5 0 0 0 1 6 2 0 0 1 7 0 2 0 1 8 0 0 0 1 9 0 2 3 0 10 0 2 0 1 11 2 0 3 0 12 2 0 0 1

IV. C. 4 REAL X(12)/0., 2., 3*0., 2., 4*0., 2*2. /, & Y(1?.)/2*0., 2., 3*0.., 2., 0., 2*2., 2*0. /, & Z(12.)/4*3., 4*0., 3., 0., 3., 0. / INTEGER IAT(J2)/0, 7*1, 0, 1, 0, 1/ C CALL MGINIT (50) CALL MGPT2('WEDGE', 12, X, Y, Z, IAT, &800) This example creates a Part named WEDGE which may now be manipulated by the MGI routines.

IV.C. S Transforms A transform is defined by the following data. 1. A legal MGI name, and 2. A 4 x 4 transformation matrix. We can also represent a set of points, for example a part, as a matrix. A set on n points can be represented by the matrix. HX HY HZ H HX2 HY2 HZ H J-tH 2 2 2 2 HX HY HZ H n n n n Multiplying such a matrix (set of points) by a transformation yields a new matrix which represents the transformed set of points, eg. HXI HY: HZ1 H1 A B C D HX; HY' HZ' H' H x E F G H ~ HX' HY' H HX2 2 H2 2 X JKL 2 2 2 2 MN OP HX HY HZ H HX' HY' HZ' H' n n n n n n n n original part transform transformed part Let's look at some particular matrices and what they do. Identity 1 0 O0 O 1 0 O Causes no change. 0 1 0 0 0 1 Independent Scale Changes Oa O O Causes the x axis to be scaled by a factor of a. 0Ob c o Causes the y axis to be scaled by a factor of b. 1o 00 Causes the z axis to be scaled by a factor of c. 00 0i

IV. C.6 Uniform Scale Change 1 000 0 1 0 0 Causes the part to be scaled by a factor of d. O 0 1 0 0 0 l/d Trans lat ion 1 0 0 0 0 1 0 0 Causes the part to be shifted e units along 0 0 1 0 the x axis, f units along the y axis, and e f g I g units along the z axis. Rotation About x Axis cos 8 sin 8 0 0 -sin 8 cos e O 0 Causes a part to be rotated about the 0 0 1 0 x axis by an angle of 8. 0 0 0 1 Rotation About y Axis cos e 0 -sin 8 o 0 1 0 0 sin 0 0 cos e O 0 0 Rotation About z Axis 1 0 0 0 O cos e sin 8 O O-sin 8 cos 8 O 0 0 0 Project ion ~ooo~ 0 1 0 0 Causes a part to be distorted as if it O O 1 1/v were being viewed from a point along the 0 0 O 1 z axis, v units from the origin. Probably the nicest feature of this matrix representation of transformations (and the motivation behind using the homogeneous coordinate system) is that the above basic transformations can be combined in any amount and any order and the resulting more complex transformation can also be represented as one 4 x 4 matrix. It's easy to show this. Suppose we wish to apply n transformations

IV.C. 7 to a part (for example, we might want to move (translate) a part to the origin, rotate it about the x axis, rotate it about the y axis, enlarge (scale) it, and move it back to where we found it.) We could multiply each point in the part by each transformation matrix (in he proper order) to transform the part ie... ( 4w< 1 1 x _) *;T Or we could multiply all the transformation matrices first and apply the resulting transformation matrix to the part to be transformed, ie. A4 It, x L ) [ 4 r / This buys us two things. a) Once we've computed the composite transformation matrix, the computation costs for transforming a part are reduced by a factor of n. b) We can represent any combination of the above simple transformations, no matter how complicated, as one 4 x 4 matrix saving storage costs and simplifying our implementation of'assembl ies which will be described in the next section.

IV.C.8 C FX tMPLE P.- t\:J T R1 S. t7 C T, 8a F T1 Ta RF'J.T.. r - FCS rF. I J AL. FA,. nI c-)/()o o -.,. - r. ) i & Y ( 1)/2*! A,.,,,,, U, ".''.; 2 & P /. 1 4 5' INTFFE5 Tf;:)I/.'? P, 1* U* 1 / C C, INITITL!T' A'Xjl:.T'.. T''. C C(A\5l.. M, "Jf:, -[ (n:, ) i nitial ize the MGI rout i nes CPf/L, 1 i ~PT'~ Ae C'' "''" A I PI')o) C C F PCRACF FCP AF \ R- Ftr aA?SLF 10 CALL Cr( DEt? computek routine to erase the screen P R: N T ) 900 F RM ('' ENTTF A: 4NLr IN DFF. r'FF P:' > 90 5;:3REP T(F6. I) C C Lr'.F NJ FA N C r-t! r, " i t C C ) (t'C tP _ li I CALL Y2T k('TI'.,!,. ) define a transform C C t? ) TF'N1SL, T " - TtT N.: -',Tr',2 I> fT Ji.Cl I C C&LL r, fT (' 1,. - "' J- it:-, -'', ( a ) rCALL MC~PT ( * 1 I' A - *,~ ~fl'.,- ~ u. build up the C 3) CALL.. r'','',; ( /i.' All A..' C AL! T co, * t e ) k tn. r a- I n., Cr"i) and i-. C,CAL 4' -':,'f,':.; f'' i', +!i;. comnutek rout ine dra,.,s lines _'.isibiLe and invisible) to the ~.::1.^!.' Ccoordinates specified by the X Co and Y vectors. t' -, t' TM I ~ " CI 1,,. F Ca j \ V1E)i.

IV. C. 9 i 1 Wr~EDGE, Ang;le = -300 1; IEG~ nl=0

IV.C. lO Assemblies An assembly is defined by the following data. 1. A legal MGI name, 2. The address of a primary transform (optional), and 3. The number of subelements (one or more) 4. One or more of the following pair: a. The address of a subelement, and b. The address of a secondary transform to be associated with this subelement (optional). A call to the appropriate routine with the above information causes the assembly to be created. Assemblies are used to relate parts and other subassemblies with transformations. An assembly can be manipulated in much the same way as a part. As an example, consider an assembly named TOOT which consists of two parts named PROP ( a propeller) and PLANE (the rest of the plane). The points of TOOT may be transformed and recovered by calling the appropriate routine and referring to'TOOT' by name. It's also possiBle to associate a transformation with TOOT's subelements PROP and PLANE (for example, to rotate PROP about its x axis). A simplified graphical representation of the data structure for TOOT Is... TOOT Ti T2...T3 PROP LAN'

IV.C. 11 In the above diagram, T1 is the transform associated with the assembly TOOT. T2 is a transform associated with PROP and T3 is a transform associated wi-th PLANE. When the points of TOOT are to be recovered (to display the plane for example) the data can be thought to "flow" upward (see next diagram) T2 T3 PROP LANE from PROP and PLANE through T2 and T3 respectively. PROP and PLANE are called the'subelements' of this assembly. (In this example, the subelements are both parts, but they could be other assemblies.) Associated with each subelement of an assembly is a'secondary transform', in this case T2 and T3. When an assembly is recovered, the points of each subelement are transformed by the appropriate secondary transforms. Associated with each assembly is a'primary transform', in this case T1. After being transformed by secondary transforms, all the points of an assembly are transformed by the primary transform. It's thus possible, in effect, to manipulate the entire assembly by transforming the primary transform. (If no transformation is desired, the identity transform can be specified.)

IV.C. 12 List-Structure Implementation of MGI System The MGI routines maintain a dictionary of element (part, transform, and assembly) names along with a pointer from each name to the element's header.,,, n_ P. A. 7-me k - 2' rt5 FS- *00 I w/Ct 7*. Headers are eight words long and of the form.ds of storage mary transform of the assembly if it exists. (, 2, ordes are sixnumber of words long.of storae

IV.C. 13 - D44 ~~jse~ra/g - ______t __ _ _- Y... H... r.S,,.,dA,,,,,,f u:_~ T 7':,, T HTJz cP 77 | | I 1C2 _:o. v / C t 2 Mosa e A05 ctv wriC1c- Tc 3-v) In the part-node, HXi, HYi, HZi, and H. represent the homogeneous coordinates of a point, and IAT. represents the attribute associated with the line drawn to that point (eg visible or invisible). CP represents a continuation pointer which either points to the next part-node or is 0 indicating that the next part-node follows contiguously. Three contiguous transform nodes are used to hold the 16 elements of the transformation matrix. An assembly-node can contain two sets of pointers (in addition to the continuation pointer which has the same function as in the part-node). Each set of pointers points to an assembly subelement and the secondary transform which modifies it. Consider the following example's simple and then more complete diagrams to get an overview of how the dictionary, headers, and nodes i nterwork. Lg T/N L 1NE 2 (3; 2,2) (3, Zo t) (4, 3, ) (A 6,- O

IV.C. 14 /8ofg COMAL1ri A>foR 10 o __~~~. ~ ~~LIl/~~t __2_, / T'G LEYD 20 2O T. 2 o03 z T,,!. _ 3 References: 1. MGI Users' Guide, John Van Roekel (Available at Aero. Eng. Office) 2. Engineering Summer Conference Notes on Graphics, 1971 (On homogeneous coordinates) 3. Drawl: Concomp Report #30, AD-715952

IV.D. 1 S. T. D. S. - System Basics Beverly Katz ccS 500 26 June 1972

IV.D.2 Introduction In the process of presenting the basics of Set Theoretic Data Structures (STDS), several areas will be covered. First, the system's history and underlying philosophy will be discussed. This will be followed by a general discussion of information retrieval systems. Then the machine environment will be contrasted to the information environment and the use of set theory in information systems will be explained. This will be-followed by a discussion of system internals, implementation and limitations.

IV. D. 3 History and Underlying Philosophy At the beginning of the ConComp Project at the University of Michigan in 1967, Project Director Franklin H. Westervelt initiated an investigation of data structures. He felt that present efforts in data structure development were too machineoriented and that future needs would not be met. His contention was that users of large data bases should not be burdened with the intricacies of complicated data representation. Instead, data representation should be transparent to the user. Thus the need for a generalized data structure arose. This structure was not to be machine-oriented but information-oriented (where design emphasis was placed on information content instead of machine representation). Historically the development of a data structure was based on a particular problem for a specific machine and therngeneralized. Another approach would be to start with a general means of expressing any problem and then adapt the general representation for a particular machine. This approach eventually resulted in the development of Set Theoretic Data Structures (STDS) by Set Theoretic Information Systems, Inc. (STIS) of Ann Arbor. It took over three years for the concept of STDS to become a usable interface. The preliminary work in this area began with Timothy E. Johnson and Jerome A. Feldman with Associated Data Structures. From this work, Associated Data Structures

IV.D.4 introduced the functional notation A(O) = V Its significance is that something done in the information environment can have an arbitrarty implementation in the machine. Functional notation has the limitation that its arguments have to be single valued. For examples the square root function f((4) = 2 by convention. But f(4) = -2 would be equally correct. David Childs, formerly of the ConComp Project and now with STIS, felt that set theory could be used instead of functional notation. This doesn't pose the problem presented above since the arguments and parameters are sets, hence f(4)= =2,2}

IV.D.5 Information Retrieval Systems In understanding why there is a need to create a more general system, one must understand the limitations of standard information retrieval methods and data structures. The traditional way to implement a retrieval system has been to determine what questions are to be asked of the data, then to write a program and choose an appropriate data structure to answer those questions. Therefore one is limited to that class of questions. Data organization methods are utilized for storing, updating and retrieving data. Each task demands a different data representation to be efficient, These different data organizations are used to bridge the gap between logical user requirements and the physical realities of storage media and computer hardware. Common data organization falls into four classifications - sequential, random, list and networks. Each one has specific assets and limitations. Sequential organization offers fast accessing of sequential records but has difficulties in random accessing, inserting and deleting records. Random organization provides efficiency for queries and updates but not for insertions and deletions. In addition, one is required to have indices or keys which cause redundancy in data representation. Sometimes dictionaries are required which increase the storage overhead.

IV.D.6 List organization includes rings and simple and inverted list structures. In this type of organization, pointers are used to link the elements. These pointers increase the amount of storage used even though they increase retrieval efficiency. It is not uncommon for the pointers to take up more space than the data. The general network organization is one. in which several levels of pointes are used (i.e., tree structures). This structure is a collection of access paths, Each path is used to answer a specific type of questions* The problem with this type of structure is that it is almost impossible to tell when an existing path is obsolete since the user and his program become dependent on the paths. If all the paths are kept until the final reference then there exists an excessive number of paths using an excessive amountof storage. Since no one representation is best or even adequate for all retrievals because data is usually bound to a machine representation, there exists a need for a new type of system. E. F. Codd suggests that the relational view of data is much superior to the existing noninferential, formated data systems. "It provides a means of describing data with its natural structure only - that is, without superimposing any additional structure for machine representaion purposes." STDS epitomizes the relational model of data. It provides an efficient method (minimal cost) of making data transformation (i.e. changing data from one storage mode to another) wit hout effecting the form of the retrieval program. Then any retrieval requiremernt could be facilitated by the selection from machine representations availabl

IV.D.7 Any transformation can be made subject only to the gained or lost retrieval speed versus the increase or decrease in storage requirements. Therefore, the information is not limited by the restrictions imposed by machine representation. In order to accomplish this, the characteristics of the information had to be isolated from those of the machine. Many of the problems in data management arise as a result of failing to recognize this distinction. The former is the one that pervades current computer installations. It is represented by,'PROBLEM STATEMENT MACHINE DEDUCTIVE DEDUCTIVE ENVIRONMENT PROCEDURE STRUCTURE SOLUTION I -Schematically, the relationship of the IE, ME, and MES should look like this: PROBLEM STATEMENT DEDUCTIVE MACHINE PROCEDURE -ENVIRONMENT STRUCTURE SOLUTION Diagrams from STIS Corporation.

IV.D. 8 Machine Environment versus Information Environment In order to understand the distinction between the information environment and the machine environment, it is necessary to see which characteristics and properties are attributed to each. The information environment can be loosely characterized by items, data, relationships, queries, questions and answers while the machine environment can be described in terms of bits, bytes, words,' addresses, contents of addresses, registers, sorts, searches and pointers. Problem statements and solutions are inherently a property of an information environment: as is the deduction procedure used for obtaining the solution from the problem statement. Problem execution is a capability of a machine environment. The transformation operations are in this category. There exists a machine environment structure (IMES) which specifies the operational particulars of a given machine environment. These include word size, memory size, languages available, etc. and all the other considerations that allow a user to interface with the machine environment. The information environment structure (IES) is a deductive procedure which accomodates the information environment. In most systems, the IES must be a deductive procedure accomodating the information environment and the additional time and storage constraints imposed by the MES. In this case the

IV.D.9 IES is the same as the MES. In order to achieve separation, two requirements must be met. First, a general deductive procedure language that's potentially expressive of any information environment. The second requirement is the construction and implementation of a language that accomodates the storage and time constraints of the MES. Set theory with the appropriate machine environment interface provides these properties that are necessary for isolating the two environements. STDS provides the interface between the environments. Since set thcory provides the propcertics necessary for isolating the information cncironment from the machine environment, any implementation of set theory with the appropriat machine environment interface will suffice. IE ME IES STIE ME MES SET THEORETIC DATA STRUCTURE The implementation of a set tI'rct' itnformation etnironment (STIE) and a mJcbine environment interlsce (MEI) is called a set theoretic data structure (ST)S). The feasibility of an STDS has been shown. The viability of an STDS depends completely on the quality and caliber of the particular implementation. SET THEORETIC DATA STRUCTURE AS AN INTERFACE BETWEEN THE INFORMATION ENVIRONMENT AND THE MACHINE ENVIRONMENT

IV.D. 10 Set Theory in Information Systems "Any data structure is actually an isomorphism between the machine environment and the information environment preserving 4 the functional aspects of each." Hence STDS is a data structure that can map the myriad relationships of the information environment into the algorithmic world of the computer. This data structure is machine independent since the user can access his data without needing to know -which machine is used (subject to the limitations of certain machines). The second condition that is necessary for isolation is satisfied since general in. formation requests can be abstracted to set operations. Set operations are defined in terms of results, not in terms of the means for obtaining results. Thus any procedure giving the correct result is legitimate. For example, if an information request is expressed as a set operation, F+), given data as sets A and B with the retrieved result as set C, then the abstraction can be stated: A () B= C In order to define this abstraction and therby prove that f) is a valid set theoretic operation, it is necessary than an element X is a member of C if and only if there exists a truth function relating A, B and X (i.e., C = tX: t(a,B,X)% ). This is an existance criteria for C, not a procedure for constructing C. It is the fact that the function is decidable that makes') a set

IV. D. 11 theoretic operation and assures that C is defined. Nothing has constrained how A, B or C should be structured nor what procedure should be employed to construct C from A and B. For instance, let) be the same as U (union) then A U B = C. One doesn't care how thi3 union is constructed or how the machine denotes C as A U B. Therefore, any convenient and/or economic representation of data (e.g., the sets A and B) fulfills the necessary and sufficient condition of isolation of the information environment from the machine environment. Hence the STDS routines are essentially machine independent. Set operations are abstractions on sets yet the term "set3 has a vague meaning when applied to an information retrieval system. All data can be represented as sets. A set has to be well ordered since there are ni ways of ordering n records. Thus, the lexicographical ordering was chosen. These sets are a collection of n-tuples (a record) represented by blocks of contiguous storage. It is important to prove the assertion that any data can be represented by a set. The method of proof will be by example. In theseS' denotelthe address of the location that contains S and ~ defines a null pointer. A list structure is one of the most commonly used data structures. Consider this linear list: S Z The only information that this structure contains is that S comes before X:''hich is followed by Y which comes before Z. This information can be denoted by a set of three ordered pairs - {<SX>,<X,Y>,(Y,Z>~. If someone wanted to know the structural interpretation of the list, it could be represented by the

IV.D. 12 following set: 9, Sx,), (X,X,Y'>, <Y',YZ'> <Z',,z3 A set can be used to describe more complex list structures. They can describe the individual cells of a list structure. Let A be a set which contains only one 4-tuple: A = ((2, 6, 4, 4>} and let B be a set which also contains only one 4-tuple: B = {type,informationforward pointerbackward pointer>7 If a user wants to know what a cell looks like, all he has to do is list A + B. He will find that the type of cell is found in the first two bytes, the information in the cell is in the next six bytes, the pointer to the next cell is in the next four bytes and the pointer to the previous cell is is the last four bytes. If C is the list structure being described then C is a collection of n-tuples where an n-tuple is sixteen bytes (in this case). This scheme can be used to describe any list structure It might seem hard to transform a network structure into a set. This composite structure can be represented by the folhV $ a 3 e i k d m lowing set of twenty ordered pairs:

IV.D. 13 2SCg sh) - Ch X a>, d a f>. <a s b, dab g C> < V, d gc)> > Sc j> ej, k>, I c> <i-, d 9), cd>, (m, t> I (m. z*) -6d z> <d, y>) <d 9 s d e> ) <-e Hence, every data structure and all types of data can be represented as a set. Sets can be represented internally by many different data structures. Each different representation is referred to as a "mode". These data structures were developed by STIS Corp. which take advantage of the capabilities and limitations of a specific MES. It is through a set's transformation into these different modes that efficiency is achieved. STIS Corp. believes that for any retrieval request there exists a best data structure (mode). Since sets can be transformed easily from one mode to another, SrDS can provide the best data structure for each retrieval request, if the best mo'de is known. To understand the basic internal scheme of STDS, one must understand some basic properties of sets. Every stored representation of a set must preserve all of the properties of the set. Every representation of a particular set must behave identically under set operations. For example, let A be a set of students and B be a set of Michigan residents. Then to find the set C consisting of all students who are Micshigan residents, C would equal the intersection of A and B. Let A have mode(6) which may be assumed to have slow retrieval and small storage properties. Assign mode(3) to B and assume that it has fast retrieval characteristics but requires a large amount of storage. Consider the set theoretic expression A n B = C; C after the intersection operation will be of the default mode. If the mode of A were changed from 6 to 3 or if the mode of B were changed from

IV.D. 14 3 to 6 or if both modes were changed, the resulting set C would be exactly the same, only the time to execute the intersection operation and the resulting default mode for C might vary.

IV.D. 15 System Internals STDS is constructed in five structurally independent parts: (1) a collection of set operations, S (2) a set of datum names, B, which point to the ith generator setts header (3) the data which is a collection of datum definitions, one for each datum item (4) a collection of set names, N (5) a collection of set representations each with a name in N STDS consists of a series of modules, most of which are set operations, written in FORTRAN which access sets through the pointers in N. All information between sets can be expressed as a set theoretical expression generated from an operation in S. Here is one of the limitations of STDS. Since all retrieval requests have to be expressed in set theoretical expressions, there may exist a request which cannot be transformed into those terms. The set theoretical expressions determine what sets are to be accessed and which operations are to be performed so that all storage requirements are known prior to the execution of the operations. If a request requires more storage than can be obtained from the system, then the operation is not performed at all; there is no partial completion. There are no pointers between sets so the collection of set operations acts as the only structural tie between sets. B is the set of datum names which is considered a block in

IV.D. 16 set) which locates a section of core that list the generator set names that are used by the composite set. Suppose that a new set A is created so that two new elements are added to the N block. Let N(a) denote the generator set and N(a*) denote the composite set. The content pointer in N(a) locates a section of core which contains a*, the address of the data set in core. N(a*) points to a location of storage which only contains a. If more information, A', has to be added to A and more contiguous space i3 available, the N block has to be updated. A new generator set element a' is created. N(a') points to core which contains a', the address of A'. Nothing happens to the section of core pointed to by N(a). The location to which N(a*) points is now changed to denote that A is really A U A' which contains a and a'. There are no pointers between sets. The N block and B block are the only pointers in STDS. Each set has basically only one pointer in N associated with it so that it can be easily updated and relocated. Deletions can be easily accomplished. The element that is to be deleted is replaced by the least element of the set. The "new" set is well ordered and takes up one ntuple less storage so that an insertion can be easily completed. To add a new record to a set, it is put in the next contiguous location, if space is available, and then the set is re-ordered. If there is no more contiguous space, a new set is formed (unknown to the user) and the N block is updated as previously described.

IV.D. 17 ADD. B-BLOCK DATUM DESCRIPTIONS 0o COLLECTION OF Bo + 1 SET OPERATIONS Description 1-st datum namne i-th datum na-e S... o+#.8 2..... Description oT SET OPERATIONS B-th datum nam 1. 8 is the-set of datum names: B = {1,2,...,)B} 2. B,B +1,.....B +# are addresses of B-block. 3. 8-block contains pointers to datum descriptionsand lists of generator. sets, r, using the datum name. 4. For each datum name'i' in B, r. is a subclass of G SUBCLASSES OF SET REPRESENTATIONS ADD. n-BLOCK - G OR C no (generator oo+i Ao. Sets) 0A +1 i A A +* A: (composite C 0 th A0+#A C - sets) 0.; is the class of set names: 7. A09A0.1,..,.,Ao+#A are addresses of elements of 8 contained in set A 8. G is the class of generator sets: G a (1,.. 9. C is the class of composite sets: C i {',...' zeB' 11. The Ci ar subclasses of C n 12. The G are subclasses of G. Storage Schema of an STDS.

IV.D. 18 System Implement at i on STDS is implemented in four sections: 1. A series of efficient sorts 2. Modular set operations 3. Garbage collection routines 4. A series of linkages. The implementation discussed herein pertains to the demonstration version - STDS-DEMO. There is' a series of efficient algorithms which sort the whole n-tuple lexicographically. Hence a set is composed of records in lexical order. All of the set operations are modular routines and new operations may be added at any time without disturbing those previously implemented. The system is modular for an eventual adaptation to hardwired integrated circuits. STIS is currently trying to market a "hardware data management processor" which they call Set Theoretic Information Concentrator. This "concentrator" Is a hardware device operationally situated between the central proces — sing unit and the peripheral storage. The information concentrator interprets an I/O access as an information access and reads from the peripheral storage device as much information as will fib into memory. This process permits fewer I/O accesses to retrieve equivalent amounts of information, thus converting many I/O constrined sytems into CPU bound systems. The STIC offers many data management capabilities:

IV.D. 19 GENERAL DESCRIPTION OF A 6 SET THEORETIC INFORMATION CONCENTRATOR A set theoretic information concentrator (STIC) is a hardware device operationally situated between a central processing unit (CPU) and peripheral storage devices (PSD's) providing the following data management capabilities: * minimization r'f input/output (1/0) accesses with maximization of itnfornnmatiu content * unanticipated query.capability -multi-user access and concurrent updating * utilization of any or all data access methods * complete data management, processing. querying. and updating * separate control over optimization of storage size and retrieval times (S/T) * restricted access and manipulation protection from unauthorized users * data base management to optimize physical placement of data for different job loads or mixes * frees user from concern with machifie representation of data * no a priori restrictions on achieving "best times", "least storage", and "general interrogation" that a given CPU and PSD will allow * data can be stored in its theoretically most compact form and then transformed into its theoretically best retrieval form * provides information expansion through simultaneous access of multiple data bases * provides separation of information rcpresentation from storage representation

IV.DL. 2( PRINCIPAL OF INFORMATION CON CENTRATION7 USUAL COMPUTER INSTALLATION CONFIGURATION CPU' PSD r - memory _ * e J memory t overlay When the CPU needs new information in memory. an 1/0 access loads the memory from the PSD. The structure of the information in memory and the structure of the information in the PSD are identical. If the information in the PSD is structured so that only a small portion of usable information can fit in memory at any one time, then the host program can become I/O bound. COMPUTER INSTALLATION WITH AN INFORMATION CONCENTRATOR CPU IC PSD memory - 0 | The IC interprets an I/0 access as an information access and "gathers" as much information from the PSD as will fit into memory. This process permits fewer I/0 accesses to retrieve equivalent amounts of information, thus converting many I/O bound problems to CPU bound problems.

IV.D. 21 These capabilities must be taken in light of the fact that they are only promises as STIC is not yet an operational reality. When using STDS the user must keep track of the amount of storage that is being used. The user must explicitly call for the system's garbage collection routines or eventually run out of storage.. Set theoretic operations can be called by FORTRAN or PL/1 as subroutines. To accomplish this, STDS provides the necessary linkages. A set is represented as a sequential file with a maximum record size of 32,768 bytes. The input to STDS should be a sequential file; later versions will take a line file and do the conversion for the users. After the data is read in by STDS, it must be converted into a set. To be a set the N block,- B block and accempa,~ying regions must be updated and a set must be created. The header contains the maximum length of the n-tuples in the set and the setts cardinality, the number of n-tuples in the set.

IV.D.22 System Limitations Most of the current limitations are due to the vast storage requirements of set theoretic operations. The current input limit of 255 pages causes difficulties for users with large data bases. As stated previously, the amount of storage needed for a set theoretic operation is determined before its execution. Sometimes the system determines that much more storage is necessary for the completion of the operation than is needed to contain the end result. Thus the storage limitation will not allow the operation to execute, even though there might be enough roomo A similar problem is caused by the inability to get enough storage during peak time-sharing periods. Currently, STDS requires a virtual memory machines particularly the IBM System 360/67. Later versions are supposed to be free of this limitations however. One common problem is the userts inability to understand and use set theory with respect to information retrieval systems. Some users have trouble translating their ideas into set theoretic expressions.

IV.D.23 Conclusions Set theoretic data structures are a fresh approach to the current state of information retrieval systems. Further development in this area by STIS Corporation and others might lead to a universal, generalized information retrieval system.

IV.D.24 8 APPENDIX A Description of the Demonstration Files for STDS used in Appendix B Universe: March 1967 Current Population Survey with Income and Work Experience Supplements Included (Bureau of Labor Statistics). Married, Spouse Present, Head and Wife of Family or Subfamily, Age of Wife 21 or over, Living in 96 of largest 104 Standard Metropolitan Statistical Areas (SMSA). Item # Unit Characteristics Coding Family Files 1. Family Family Code Number 1-11629 2. Family Primary Family 0 Each Subfamily or b Secondary Family 1-6 3. Family Type of Family Primary Family 1 Subfarmily 2 Secondary Family 3 4. Family Weighta 0-999999 5. Family Presence of Own Children None 0 All 6-17 1 None Under 3, Some 3-5, Some 6-17 2 All 3-5 3 Some Under 3 4 6. Family Relation of Wife to Head of Household Wife 2 Child 3 Other Relative 4 Non-Relative 5,6 7. SMSA CPS Unemployment Rate 0-9.7% 0-97 Over 9.7% 98 8. SMSA BLS Employment Change, 1966-67 Under.1% 0 0.1-9.78 1-97 Over 9.7 % 98

IV.D.25 Item # Unit Characteristics Coding 9. SMSA Relative Opportunities.001-.997 1-997.998 or more 998 Wife Files 1. Family Family Code Number 1-11629 2. Family Primary Family 0 Each Subfamily or b Secondary Family 1-6 3. Family Race of Wife White 1 Negro 2 Other 3 4. Wife Age Age at last birthday 14-98 Age 99 or over 99 5. Wife Labor Force Status, March Not in Labor Force 1 In Labor Force 2 6. Wife Employment Status Employed: At work full-time 01 At work part-time 02 With a job,not at work 03 Unemployed: Looking for work 04 Temporary lay-off 05 New Job 06 New Job, School 07 Out of Labor Force: House 08 School 09 Unable 10 Unpaid,less than 15 hrs.ll Other 12 7. Wife Recoded-Intermediate Hours 1-34 Hours Usually full-time, Economic 1 Usually full-time, Other 2

IV.D.26 Item # Unit Characteristic Coding Usually part-time, Economic 3 Usually part-time, Other 4 35-39 Hours 5 40 Hours 6 41-47 Hours 7 48+ Hours 8 Intermediate Duration of Unemployment not coded 1 or 2 9 8. Wife Intermediate Duration of Unemployment Under 4 weeks 1 4 weeks 2 5-6 weeks 3 7-10 weeks 4 11-14 weeks 5 15-26 weeks 6 Over 26 weeks 7 Not unemployed 9 9. Wife Years of School Completed None 1 1-4 elementary 2 5-7 elementary 3 8 elementary 4 1-3 high school 5 4 high school 6 1-3 college 7 4 college 8 5 or more college 0 10. Wife FILOW Negative or none 0 Amount 1-24999 $25,000 or over 25000 Husband Files 1. Family Family Code Number 1-11629 2. Family Primary Family 0 Each Subfamily or Secondary Family 1-6 3. Husband Age Age at last birthday 14-98 Age 99 or over 99

IV.D.27 Item # Unit Characteristic Coding 4. Husband Labor Force Status, March Not in Labor Force 1 In Labor Force 2 Armed Forces 9 5. Husband Employment Status Employed: At work full-time 01 At work part-time 02 With a job,not at work 03 Unemployed: Looking for work 04 Temporary lay-off 05 New Job 06 New Job, School 07 Out of Labor Force: House 08 School 09 Unable 10 Unpaid,less than 15 hrs.ll Other 12 Armed Forces 99 6. Husband Recoded-Intermediate Hours 1-34 Hours: Usually full-time, Economic 1 Usually full-time, Other 2 Usually part-time, Economic 3 Usually part-time, Other 4 35-39 Hours: 5 40 Hours 6 41-47 Hours 7 48+ Hours 8 Intermediate Duration of Unemployment not coded 1 or 2 9 7. Husband Intermediate Duration of Unemployment Under 4 weeks 1 4 weeks 2 5-6 weeks 3 7-10 weeks 4 11-14 weeks 5 15-26 weeks 6 Over 26 weeks 7 Not unemployed 9

IV.D.28 Item # Unit Characteristic Coding 8., Husband Years of School Completed None 1 1-4 elementary 2 5-7 elementary 3 8 elementary 4 1-3 high school 5 4 high school 6 1-3 college 7 4 college 8 5 or more college 0 9. Husband FILOW Negative or none 0 Amount 1-24999 $25,000 or over 25000 aWeight in file is 100 times the true weight. bEach subfamily or secondary family within a primary family unit has a separate number. Subfamilies and secondary families are contiguous on the file to their respective primary family.

IV.D.29 9 APPENDIX B Example Use of STDS #FK IC47: bTj#EXECUTION BEGINS: ** SET-THEORETIC DATA STRUCTURE: INTERACTIVE DEMONSTRATION ** (2/18/70) FOR AN EXPLANATION ENTER "1": (See Appendix l)?GET (H) FILE.-=~ CPSH1 ENTER PRINT FOMAT: (918 ) DONE' Ln(*)=: 9 ( -:(*)'58122 ( 0.2912 SEC) H is the aet' lo: hwubands (heads od households) (See Appendix C)?GET (W) FILE = CPSWI ENTER PRINT FORMAT: (1017 ) DONE! L(*)= 10 I(*)= 5812 ( 0.3250 SEC) W i4 the 6et go wive4. See Appendix c.?SET(UNEM,4,6,5,7) * DONE!,' L(*-)= - 1 C(*)= 4 ( 0.0036 SEC) UNEM i6 the 4et -od codes otr "UNEMPLOYED"?RS (5,H,UNEM,UH) DONE! L(*)= 9 C(*)= 95 ( 0.4715 SEC) UH i6 set o6 u0.4ptoyed huabands?XPAN (2 W,,U,WUH, 1 DONE! L(*)= 17 C(*)= 95 (0.5356 SEC) WUH combine6s {matche) the wiveQ o6 unemployed husbands in a set o6 17-tupte:e (wife-hu.6band telationship sp )?IGTJ (WUH, 4 41,OLDR) DONE! L(*)= 17 C(*)- 13( 0.0023 SEC) OLDR is the set Ofs wviue. of unempeoyed ILusband's who ate oede. than theirt huts:band&.?RS (6,OLDR, UNMUM,UiT) DONE' L(*)= 1 C(*)= 1 ( 0.0023 SEC)

IV.D. 30 UNW is the set of unemployed wives of unempeoyed husbands who are otdet than theit hu.sbands.?LIST (UNW, 1,1,-1) ENTER OUTPUT FORMAT: (5110) 2006 0 1 57 2 5 9 6 3 6520 53 2 5 9 6 6 6321 By examining this with the codes in Appendix A, it may be zeen that we have located a 57 year otd wi6e o0 a 53 old hukband zuch that the FILOW Cfmamity income tes4 own wage.s fot each is in excess of 6000 doatas. This may be due to pensions, intetre6t, dividends, capital gains ot other sourtces, explaining the basis o6 this data sample instance. Obsertve the CPU times used to 6ind this resutlt,tom an initiat et o 5812. Totat time to do STDS MT#SIGNOFF operations =. 644 sec. #SIGNOFF #OFF AT 18:11.26 #ELAPSED TIME 1400.7 SEC.+ due targety to typed comments! #CPU TIME USED 10.471 SEC.+- due ta4ge.ty to ptogram "loading #STORAGE USED 929.573 PAGE-SEC. and "rteocation"! #DRUM READS 107 #APPROX. COST OF THIS RUN $2.42 #FILE STORAGE 841 PG-HR $.12 The above is an actual STDS session retyped for greater readability using italics to distinguish the comments.

IV.D.31 OPERATIONS EXTENDED TO N-TUPLES A = <p,q,r,s,t>, <k,z,m,n,o>, <a,b,cd,e>, <u~v~w~xy> <U, V, W, X, <f,g,h,i,j> I-TH DOMAIN of A DM(1,A,C) C = fa,f,k,p,ul DM(3,A,C) C = c,h,m,r,wj I-XH- RESTRICTION of A to B Let B = 1Z,sj then for RS(2,A,B,C) C = [<k,z,m,n,o>) and RS(4,A,B,C) C = <p,q,r,s,t>3 LET A - {<name,mother,father,spouse,sex>3 GIVEN x,find all sisters of x. let X = {xJ and W = Ifemalel RS(l,A,X,B) B = tn-tuples with x in position 13 DM(2,B,M) M = )x's mother, ml DM(3,B,:) I- lx's father, fJ RS(2,A,M,C) C = In-tuples with m in position 2j RS(3,A,,D) D = Ln-tuples with f in position 3, IN(C,D,G) G = tintersection of D and CV RS(5,G,W,9) H = Ln-tuples of G, female in 5 pos.l RL(DM(1,),X,S) S = sisters of x J

IV.D. 32 Footnotes E. F. Codd, "A Relational Model of Data For Large Shared Data Banks" CACM, June 1970, pp.377-387. 2S.T.I.S. Corp., "Set Theoretic Information Concentrator," 1972. 3Ibid. 4D. L. Childs, STIS Technical Report 1 - Development of a Set Theoretic Data Structure, p. 3. 5D. L. Childs,"Description of a Set Theoretic Data Structure," ConComp Technical Report No. 3, University of Michigan, March, 1968, p. 5. 6STIS Corp., Op. Cit. 7Ibi d. 8D. L. Childs, STIS Technical Report 1pp. Cl1-C5. 9Ibid., pp. DI-D2.

IV.D.33 REFERENCES Childs,D. L.,Description of a Set-Theoretical Data Structure, Technical Report No. 3, Concomp Project,University of Michigan, March 1968. Childs,D. L.,FeasibilitY of a Set-theoretic Data Structure, Techinal Report No.6, Concomp Project,University of Mlchigam, August 1968. Childs, D. L.,S.T'. I.S. Technical Report No. 1, Developement of a Set-Theoretical Data Structure-Basis for Machine Independent Information Mlanagement Svstem,S.T.I.S. Corp.,Ann Arbor, Mi.. Codd,E- F-,A Relational Model of Data for Large Shared Data Bank, Communications of A.C.M.,Vol. 13, No. 6, June 1970, pp377-87. Dodd,George G.,Elements of Data Mlana ement Systerns,Computing Surveys, Vol. 1, No. 2, June 1969, pp 132-177. Hershey, W. R. and Easthope,C. H., A Set-Theoretical Data Structure and Retrieval Lan ua.e, L.Li.I.S. Project,University of Mlichigan, kpril 1972. Ray, Paul H., Users Guide to STDS-Demo. System,; Ann Arbor,Mii., March 22,1971. S.T.I.S.,OPerations Manual for STDS-,S.T.I.S. Corp., Ann Arbor, Mi., December 1971.

V.1 SAMPLE PROGRAMS To provide some comparison between the various languages presented in the seminar, a sample problem was devised and the seminar participants provided solutions to this problem in several languages. The problem description is on the following page; the sample programs constitute the remainder of this section. We offer them with no further comment, other than the comments of the authors.

V.2 Simple Standard Problem for String and List Processing Seminar Participants Those persons who presented source language descriptions in the seminar are requested to write a small program (whose function is described later) for inclusion in the final seminar report. The obvious intent is to have one problem common to all reports, so as to gain some feeling for the differences in the various languages. The program should function as follows: 1. the input is a variable-size set of alphabetic strings (A,B,...,Z), each string being one to four characters in length 2. the strings should be placed in alphabetic order (standard dictionary sequence) by the program 3. the internal ordering mechanism should be the construction, as a function of the input, of an ordered binary tree (this will be discussed in class) 4. the program should then produce as output the alphabetized list of strings. Since there is a great deal of variation in the languages, we leave to each of you the design of the input formats and output format. Your program should read multiple data sets (as described in 1. and 2.); hence you will need one or two terminator symbols. For the final report, we would like: 1. a brief, at most one page, prose description of the program 2. a listing of the program 3. program results (if you are able to run the program in MTS) for the following input orderings: a. ordered b. reverse ordered c. randomly ordered each data set should contain a. C CC CCC CCCC b. at least one string < C c. at least one string > CCCC d. any other strings.

V.3 SLIP (Dean Lucier) The sample program takes as input a variable number of one to four character strings and proceeds to build a binary tree to represent their alphabetic ordering. The input format is one string per card, left justified with a blank used as a delimeter for the length of the character string. A period in column one denotes the end of the set of strings which need to be alphabetized. An asterisk in column one denotes the end of the file. Each string is examined to see if its duplicate is in the tree already. A header cell is created for each new letter at each level required. At the same time a type 0 cell is placed at the top of the list, which contains in the datum the letter it represents and a count of the number of times this letter, associated with previous letters by being linked as a sublist, was the last character in the string. On each of these lists are name cells which point to succeeding lists (letters in strings) which followed the letter representing the node. The routine to print out the tree structure is then quite simple. Starting with the main list and using the structural advance, it prints out the datum portion of all type 0 cells which have a termination count greater than zero. The function LCNTR(READER) provides the level of the sublist so the string can be rebuilt for printing. An example of the list structures for the strings ABC and AX are shown on the next page. The MTS SLIP as shown in the program listing does have a bug in the advance linear operations using the predecessor (left) linkage. Therefore, when the data strings are not in order, my routine which is used to insert a cell in front of another cell fails.

V. 4 M-AIN' A 1n 2.? | HEADER / / B v; l, f2 |...... [~~ [....... I A 1 C BOORA HE X~~~ (C x2 2, /I

I 3L I r'MIrLA rcqPLr'I5(rU C SLIP IS EMBFDOED IN FORTRAN. FOR EASIER 6.CO C IDENTIFICATInN 6.000 C EACH SLIP STATEMENT IS FOILLIwEO BY A LINE nF ASTERISKS. 7.000 C 8.030*************e 8.0 C 9.000 C THIS PROG,RAM WAS WRITTEN AS PART nF A THE COIURSE RFQUIREMENT 1 O.00 C IN A STRINrJ AND LIST PPrICESSING SEMINAR AT THF UNIVERSITY 11.000 C OF MICHIGAN IN MAY-JUNE 1q72. 12.000 AUTHOR. DEAN LUCIER 13,000 (001 COMMON AVSL,W(100) 14.030 nOnn?D OUBLE PRFCISIn'N SPACE(1230), INTTAS,4AINREADERtFLAG,STUFF, 15.000 X ASTI.)FF,INSARG, NFWLST,LST,NAME,LISTT,LRnROVI,LVLRVT, AVSER, 16.G00 X. A nOVLWI., ADV NR,LPNTR, SBIIBSTLVI RV l, FWTOP NEWBOTNXTLFT, 17.000 X LFRPnR, NITR)n 18.000 03Oq INTEGER A(4),LVL,PARENT,PCnO)NT I,B,C(2),STARPER IO, 19.00C X PLANK, tRALST, TRARR,L.CNTR 20.000 tno) r)DATA STAR/4H* /, PER lnn/4H. /, BLNK/4H / 21.000 000'5 EOTlI VALFNCF (STtIFF,PARFaT,C( 1) ( PCO UNT,C(2)) 22.000 0006 900 FNRMAT (4AI,7SX, Al) 23.00C 0n07 910 FNRMAT ( /4A) 24.000 008 q20 FnRMAT (/4A4) 25.000 OO p9 94( FORMAT (24H HnW AROUT THESE RESULTS) 26.000 0C 1n 960 FORMAT (/?7HIHERE ARE THF INPUT STRINGS) 27.000 001 1 980 FOMA.T ( /27HHFRE IS THE GENERATED TREF) 28.00O 0} 1 2 990 FnRMAT (/42Ht1HFPE- IS THF FINAL INTERNAL LIST STRUCTURE) 29.000 nO13 995 FORMAT ( /2H WE ARE ABOUT TO CRASH) 30.003 001 M -= 150 31.000 C THIS WItL PRnVIrF 75 SLIPCELLS ON LAVS (MTS USES 2 DOnUBLFWORDS) 3?.000 0015 CALL INI TAS( SPAF,M) 33.000 C CREATE A LAVS AND PUBLIC STORAGE 34.C00 O) 0016 CAl SETPAC( SPACE,M) 35.000 C *****t**** **** SFT UP SLIP DUMP IF LAVS EXHAIUSTED 36.000 00 17 10 CALL LTSTIMAIN) 37.r00 C ********* GFT MAIN LIST HEADFR CFLL 38.000 O01R8 RFADFR = LtRnPOV('4AIN) 39.000 C ACQUIRE A READER FOR THE LIST 40.003 C 1 9 WRITE (6,q60) 41.C00 n0?n 20 CAl L I! I T Pn (LVLRVT (PFAnFR 42.030 C **t*****4***** *** *t RETURN TO HEADER OF MAIN LIST 43.0CC0 OC?l 25 RFAD (5,9n0) (A( I),I=,4),B 44.00n 0022 WRITF (6,910) ((I1),I=1,41 45.000 0023 IF (A(l).FQ. STAP) GO TO 800 46.0N0 0024 IF (A(l).FQO.PFRTIO) r7 Tn 500 47.COO C AT THIS PnINT WF HAVE A STRING IN THE A ARRAY - LFFT JUSTIFIED 48.000 0075 LVL = 1 49.000 0026 50 STI)FF = A)VS PREA FP,Ft.AG) 5C.00 C C ***n************** LNOK FOR A SUBLIST 51.000 00?7 iF (FLAG.NF.Onr I Gn TO 450 5?.nOC OC?R IF (A(LV_ ).LT.PAP eF"JT) Gn TO 200 53.000 C STINC CHARACTERS APr LFFT-JUSTIFIED, THE HIGH-ORDER BIT IS ON 54.CGC C STINIFYING NEGATIVE 55.C00 0 0029 IF (A(LVL).GT.PARFNT) GO Tn 300 56.C00 a C THE CIJRRENT STRING MATCHES THIS LEVFL OF THE TREE 57.C00 0030 8R IF (LVL - 4) 90,95,95 58.000

MICHIGAN TERMINAL SYSTF' FORTRAN G( 41336) MAIN 06-22-72 18:43.51 PAGE P002 CC01 90 LVL = VL + 1 59.000 003? IF {(\(LVL).NF.,BLANKI GO Tn 400 60. 000 0033 95 0(OtUNT = PCOUNT + 1 61.CC0O 0034 ASTUFF = LPNTRIPEADFR) 62.00 C**** **** GET ADDRESS OF CURRENT CELL 63.000 0035 CALL SURST( STlJF,ASTUIFF) 64.000 C.**, ****,*** REPLACE INCREMENTED COUNTER 65.000 C AT THIS POINT - DONE WITH CURRENT STRING - GO GET ANOTHER 66.C000 0016 GO Tn 20 67.000 nm3,7 200 CALL LVLRVI (READFR),8.000 C ****,,:****** RETURN TO POINT OF DESCENSION 69.090 0038 INSARG = LPNTR(READERI 70.000 CC *8********** RETURNS ADDR OF CURRENT CELL 71.000 0039 PARENT = A(LVL) 72.000C 0040 PCOUNT = 0 73.C.00 0041 NFWLST = LIST(9g 74.000 ~C ~~********* GET NEW StUBLIST-REF COUNT = 0 75.000 0042 CALL NFWTOP(STJfFNEWLSTr 76.000 C***************** INSFRT PARENT ID ON SUBLIST 77.000 0043 CAlL NXTLFT(NEWLST,INSARG) 78.0C0 4C 3 t***************** L NK NEW SUBL I ST 79.000 0044 WP IT ( 6,q95) 80.000 C THE LEFT POINTFP FUINCTIONS HAVE A BUG TN THEM- WATCH ME CRASH 8 l.00n 0045 STUFF = ADVl WL(RFADFR,FLAG) 82.000 C ****************** PnSITION ON NEW NAME CELL 83.000 0046 WRITE (6,99g=) 84.000 C WE WILL NIEVER GET THIS FAR - I TOLD YOU SO 85.C00 0047 GO TO 50 86. 000 O04R 300 CA t.L LVLRVI (R_ AFR) e 7.000 C ********** RETURN TO POINT OF DESCENSION 88.000 n049 STUFF = ADVLNR(PEArFR,FLAG) 89.000 C L****************** LOOK FOR NEXT NAME CELL 9C.CO0,00O IF (FLAG.EO.ODrf) GO T) 50 91.C00 C AT THIS POINT - NFED TO ADD CELL 9?.00 C001 nO TO 450 93.000 005? 400 STUFF A IAVLNR(OEADER,FLAG) 94.000 C **************** LOOK FnR NAME CELLS 95.c00 0C5~~w [IF (FLAG.NE.000) GO TO 453 96.C00O 0054 GO TO 50 97.CO0 or005 450 PAPENT = A(LVL) 98.000 005( PCOIUNT = 0 qo000 007 NAME = LnFprnP(PEAnER) iCC.C00 C********* RFTUJRNS NAME OF LIST SCANNED 101.0C0O 0058 NFWLST = LIST(9) 102.COO C******** GET NEW SUBLIST - REF COUNT = 0 103.C00o 0059 CALL NEWTOP( ST(JFF, NEWLST) 1C4.C00 C INSERT PARENT ID ON SUBLIST 105.000 OO00 0 CALL NEWROT(NEWLST,NAME) 1c6.000O C LINK LISTS IC7.000O 0061 STUFF = ADVLNR(READER,FLAG) ICR.000 C ******************* POSITION ON NEW NAME CELL 1C9.C00 0062 GO TO 50 11C.000 o 0063 500 WPTTE (6,99q0) ill.COO 0064 CALL SLP)MP(SPACE,M) 112.000 C*************** DUMP LIST SRUCTURE 113.000

MICHIGAN TERMYNAL SYSTFM FORTRAN G(41336) MAIN 06-22-72 18:43.51 PAGE P003 C TIME Tn nISPLAY CnrNTNTS OF TRFE 114.000 CO5 WPITE (6,9Rn) 115.000 0066 520 STUtFF - AnVSFR(QFAfDEPQ,FtAG) 116.C00 C *****************4 SCAN FOR SUBLIST IDENTIFIERS 117.000 0067 IF (FLAG.NF.OD?) GO TO 7DO 11. 000 0068 LVL LCN TR(READER) 119. G000O C GET LEVEL OF STRUCTURE 12C.000 V" 69 A(LVL) = PARENT 121.000 n070 IF (LVL.EO.4) GO TO 550 122.0CC 0071 J = LVL + I 123.000 0072 on 549 I=J,4 124.0C0 OC 7 540 aM I ) = BLANK 125.CCO 0 74 550 IF (PCOIINT - 0) 520,520,575 126.000 0'37; 575 WRITE (6,q20) (A(I),Il1,4) 127. 000 r0 7A GO TO 520 128.000 0077 700 CALL IPADP(R EADER) 129.000 C t*********** ERASE THE READER 130.000 0078 CALL IRALST(MAIN) 131.000 C ERASE THE LIST 132.000 C079 GO TO 10 133.000 OA8r 800 WPlTF (6,949 } 134.000 r00)1 STnP 135.000 nC q ENn 136.000 *nPTIONS TN EFFFCT* IT, EBCDIC,SOlIRCE,NtLISTNr)DECKtLOADtNOMAP *nOTIONN TN FFFECT* NAME - MATN, LINFCNT = 57 *STATISTICS* SOlIRE STATEMENTS = 82tPROGRAM SIZE = 10302 *STATiSCT!CS* NO DIAGNOSTICS GENFRATED NO FRRORS TN MAIN NOl STATFMENTS FLAGGED IN THE ABOVE COMP[LATIONS, -..

HERE ARE THE TNPUT STRINGS V.8 ARD ASRT CC CCC CCCR CCCC ccrn cccr cccn OEAN DX ZZZZ2

****SLIP DUMP *** AVAILABLE SLIP STn1RArF FIRST AVAILABLF CELL IS 3005036E8 LAST AVAILABLE CELL IS 00503488 ADnRS TYPE LINK WOpn DATUM 1n LNKL M LNKR HEXADECIMAL EBCDIC REAL INTEGERS I NI MLK 5P136F8 ROR 3 5m031568I #0 037?8 00P0655000003O00 0.338l847532696294D-78 6569810053280000 5137?P RnR 3 503668 0 503648 00040659('00)01030 O. 33 8l8475326 P6294tD-78 656981 0C C280000 5'136481 OAT 0'5C3638 0 503358 F94040400oooOOzIo Z -0.5?689317153877C30 49 -3816652160702000000 503358 ROR 3 50365;8 0 503508 0004064RO0010003 0.3382?90222638992D-78 657C673053580001 503rfl8 RDQ 3 503578 0 503528 0004069F00000002 0.33822284519479170-78 6570552053480001 503528 ROR 3 533588 0 5034B8 003A06D900')O0001 R 0*338?527010288105D-78 657113105368C008 503)488 POR'3 503418 0 000000 000A065500000000 0.3381847532686294D-78 6569810053A80000 RFADERS AnDRS TYPE LINK WORD DATUM ID) LNKL M LNKR HEXADECIMAL EBCDIC REAL INTEGERS I NL MLK 5032B8 ROR 3 5032A8 0 000000 0004065500000000 0.33818475326862940-78 6569810053280000 L I S TS ADnpS TYPE LINK WORn DAT'JM In INKL M L NK P HEXADECIMAL EBCDIC RFAL INTEGERS I NL MLK 50311A8 HnP 2 5034IR 0 503?FA 00.)()O OOOOCOC'00 I 0.1198909146801202D-93 n 0000000 503?F8 NAM I'V).32?A 3 0 5034F9 203A0659C,00A0659 0l. 1l5')7914034 69 7qo- 39 537527897-107043 028653C 5034E84 NAM 1 503?E I 0 5035689 20A01699C00A0699 P R 0. 11509035073429710- 39 537527961-107047 048653C 5 35689 N AA 1 5034F8 0 5G'I668 2 0 "AC 6A 9 C0 0 A,6 A 9 1 Z 0.115093153331?264n-39 537527977-107045 C586534 503669 NAM I 1 St3 5 6R C0 503418 2'."0 A 06 n IC 0 0A 1 6 J J 0. 1 15 1 001 59 8? 3 54 9 6 D-39 53752801 7-107041 0686538 501341 R NAM 1 503668 C 5032AP 20A061069C00AD6D9 R R 0.1.151C156112?C1430-39 53 7 52802 5-107041 068653C 5032C8 HnR 2 5033F P 0 503308 oooooooooooooooil 0. 1199520.9146P012C20-93 01003000008 503308 OAT 0 5032C8 0 503348 C14043400000301 A -0.4015686035156249D 01 -10527538561602000008 503348 NAM 1 50330~ 0 5033F83 200A3665CC0AC665 0.115081242?942769D-39 537527909-10382715386038 5033Fq NAM I 503348 0,'5032C8 203A067BC00A0678 U 0.115085D958650'5460-39 537527931-107040 0386530

5r,32F8 HDFR 2 503318 0 503378 001,00000000000M 0.l1O95091468rJ2020-93 0 1 0 000P.0 0 000008 503377 OAT 0 5032FO 0 503318 C140404o00o01330 A -0.4(15686035156249D 01 -[052753856 0 6 020200 0 00000 503318 IqNAM 1 503378 Cn SC032?F 2OA0AI6FC0OA368F 0.I 1 50 8R599111 2 11630- 39 537527951-1073084785 1 503478 6 503478 n03328 HOP 2 503389 0 503338 000100030000000l 0.11985091468012020-93 0 1 0 000000 0 000008 503338 OAT 0 503328 0 503388 C240404C00000000 B -O.64?50976562500CO0 02 -1035976640 0 6 020200 0 00000 50I,88 NAMI I 5"'3338 0 503328 20 00660000A066) 0.1 1508264359274150-39 53752791 7-107308481 1 503368 6 503368 503'68 HOR 2 5013A8 0 503348 000oOC00o00OC01 0.11995091468012020-93 0 1 0 000000 0 000008 5031A8 OAT 0 503369 0 503768 C440404000000001 0 -0.16448249999999990 05 -1002422208 1 6 020200 0 000008 503308 HOR 2 503448 0 5033E8 000V)C0000000001 0.11985091468012C20-93 0 1 0 OUCOCO 0 000008 50)3lE8 nAT 0 5033D8 0 503448 F241404000003000 S -0.2186347438166925D 41 -499105728 0 7 020200 0 0000 503448 NAM 1 5033F8 C 503308 200(A685COA0685 E E 0.11598684748813540-39 53752794 1-1073084195 1 503428 6 503428 503408 HOR 2 503388 0 503388 00000000003301 0.11985091468012020-93 0 1 0 000000 0 000008 S033R8 OAr 0 503408 0 503409 C3404040003130C"1 C -0.lC?301 5624999"990 04 - 1019199424 1 6 020200 0 040008 503428 HOP 2 503489 0 503438 00o00o0oo0000000 0.119q509146801202n-93 0 1 0 00000C 000008 503418 DNT 0 503428 0 503488 094740430010C000 R -0.31815542579962120 30 -650100672 0 6 C20200 0 000000 503488 NAM 1 503438 0 511428 200A068DCC0A0680 0.11501884978660010-39 537527949-107308478 1 503468 6 503468 503468 HnR 2 5034A9 0 5034A9 0001C00000000001 0.11985091468012020-93 0 1 0 000000 0 000008 Sn014A8 OAT 0 503468 0 503468 E340404000000001 T -0.34981559010670800 42 -482328512 1 7 020200 0 000008 503478 HnR? 503398 0 503398 00C0000000000001 0.11985091468012020-93 0 1 0 000000 0 000008 5C3398 DAT 0 503478 0 503473 0540404000000001 N -0.48546665313662890 25 -717209536 1 6 020200 0 000008 5014C8 HOP 2 903518 0 503518 0000000000007)00 0.1198509146801202D-91 0 1 0 OQOCOC 0 000008 503918 OAT 0 503408 0 5034C8 C240434000000001 8 -0.64250976562500000 02 -1035976640 1 6 020200 0 000008 5n?4r8 HOP 2 503978 0 503538 0000000030000001 0.1198509146801202n-93 0 1 0 000000 0 000008 501518 OAT 0 5034F8 0 503578 F94C40404100000003 -0.58689317193877030 49 -381665216 0 7 020200 C 00000 5C';78 NAM 1 503538 0 5034F8?0OA06ABCO0O6AB 0.1150935C"365984250-39 537527979-1073084757 1 503558 6 503558 503r)48 HnR 2 501608 0 5039148 000000c7000003001 0.11985091468012020-93 0 1 0 000000 0 000008 5ml9A8 nAT 0 503548 0 503608 0J3404C4000000001 C -0.10280156249999990 04 -1019199424 1 6 020200 0 000008 503608 NAM I 5035AP 0 593548 200A0680000A3680 0.11539665657738830-39 537527997-1073084739 1 5035E8 6 50358 503598 HOP 2 503658 0 503508 000010090000001 C.11985091468012020-93 0 1 0 000000 0 000308 503508 OAT 0 503558 0 503658 F940404003030330 Z -0.58680317193877030 49 -381665216 0 7 020200 0 000000 Sn3658 NAM 1 503508 0 503558 20014C6C7000A06C7 G G 0.1150984C820046880-39 53752800 7-1073084729 1 503638 6 503638. 503588 Hnp 2 503618 0 503618 0000000000000001 0.1198q5091468012020-93 0 1 0 000000 0 00008 503618 DAT 0 503589 0 503588 C443134000000001 D -0.16448249999999990 CS -1002422208 1 6 020200 0 000008

. LL 7 -T t A I I J-L'I? I I IJL0JL U,u luU 5035F8 HDR 2 503698 C 503628 COOOOOOOQOO0001O C.1191509146801202 n-93 0 1 0 000000 0 000008 533A?8 OAT 0 5(~35F8 0 503698 C340404000033031 C -0.1028O15624q999990 04 -1019199424 1 6 02020C 0 COCOO8 503698 NAM 1 503628 0 5035F8 2-03A6CFCCOA06CF O.11509980949899350-39 537528015-1030721 1 503678 6 503678 503638 NnR 2 503458 0 503458 00o0o0l000000001 0.1198509146801202D-93 0 1 0 000000 0 000008 503458 OAT 0 503638 0 503638 F9404040000000C1 Z -0.58689317153877C3D 49 -381665216 020?C 0 000008 5f367P HNOR 2 5359 8 0 50368 ooooooc OvCool 0.1198509146801202D-93 0 1 0 000000 0 000008 5')36R8 OAT 0 5C33678 0 503738 C1414040000OO)31 C -0.10230156249909990 04 -1019199424 1 6 C?0200 0 000008 503719 NAM 1 5933688 0 503498 200AO6F3COOAC6F3 T T 0.11510331?7450951n-39 5375?803)-l073084701 1 503718 6 503718 503499 NAM 1 503738 0 503598 200406910COA0681 A A 0.1150861468389C310-39 537527937-1373084799 1 503408 6 503408 503198 NAM 1 903498 0 533678 200A3681 000A6R1 1 1 0.11509455462969100-39 537527985-1073084751 1 503588 6 503588 50368A HOP 2 51!qFR 0 503tA8 OOCOOOC000000col 0.11985091468012020-93 0 1 0 CoOCCO 0 000008 5036AR OAT 0 5036P8 0 5116F8 C 44n40404000000 D -0.1644P?49999)9999D 05 -1002422208 0 6 020200 0 003000 5036F8 NAM 1'5036A8 0 5035F8 2 CVA06E9CClA06E9 7 Z 0.115l043637l89436D-39 53752804 1-1073084695 1 503748 6 503748 50 3FRA NAM 1 5036F9 C 50368P 200Ai699C000A06R9 9 q 0.1150959559281557n-39 537527993-1073084743 1 5C35C8 6 5035C8 903608 HOR? 9C3988 0 5036D8 Oo0000oCOc 0ooooo 0.11985091468012020-93 01 0 000000 0 000008 503608 DrT C 5036CR C 533988 F940404000000030 Z -0.586q9317153877030 49 -381665216 0 7 0202CC 0 OCOCOC 5038;RP NAM 1 503608 0 5036C8 20)AO69FC0OAO69F 0.1150914037081456r)-39 537527967-1373084769 1 5034F8 6 5C34F8 503718 HnO 2 503208 C 533208 o000fo0f"Cl000S000 0.1193509146R01?02D-93 0 1 0 CCCC 0 00008 5032n? OAT 0 503718 0 503718 C240404000000001 B -C.6425097656250(00D C2 -10355176640 1 6 02020 0 000008 503748 HOp 2 5033CI 0 503708 OOnoc OO)O00001 0.11985C9146801202D-93 0 1 0 000000 0 000008 503708 nAT 0 9031748 0 5033C8 C54040400Pn00033 E -0.2631719999999999D 06 -985644992 0 6 020200 0 0000 5 0 330C 8 NAM 1 503708 0 503748 200AO65FCOOA065F 0. 1 1508019132042830-39 537527903-1073084833 1 5032F8 6 5032F8 PUBLIC LISTS AnORS TYPE LINK WORO OAT'JM TO LNKI M LNKR HFXM)ECIMAL EBCDIC REAL INTEGERS [0 LNKL M LNKR 906388 HOP 2 5)6388 0 506388 OOnOO0000000OFFF 0.49078949961509230-90 0 4095 0 000000 0 007&F 506398 HOP 2 506398 0 516398 OOOOOOOCOOOOFFF 0.49C7894956150923D-00 4095 0 000000 0 COFF8 5063A'8 HDO 2 5063A8 0 5C063AR8 00OoOOOOOOOFFF 0.4907814956150923D-90 0 4095 0 CCOOOO 0 CO7FF8 506388 HnR 2 506388 0 506388 OOOOOOOOOOOOOFFF 0.4907894956150923D-9C 0 4095 0 000000 0 007Ff8

c~06~,C~ HOP, 2 5'"63Cq 0 5963CR 000'"'m000000OOFFF 0.49078949561509230-90 0 4095 0 00000C 0 007FF8 506~.DR HOR 2'~063r~8 0 5063r)a OOOO900000000F~F 0.49078949561509230-q0 409~ 0 000000 0 007FF8 5063EQ HOg ~_ 5063E8 0 506.~ER OOCOOOOOOOOOOFFF 0.49078949561509230-90 4095 0 0000000007FF8 536~F8 HOR 2 5063~:~ 0 506~FR. O0(~0000COOOOOFFF 0.49378349561509230-90 4095 O 000000 0 007FF8 506408 HnR 2 506408 0 50640B 000n0C,,000003DFFF 0.490789~+9561509230-90 4095 0 000000 0 007FF8 ~.06418 HO~ 2 5064J8 0 506418 OOOOOOOOOOOOOFFF 0.4g~78949561509Z~D-90 4095 0 0000000 007FF8 506428 NOR 2 50542B 0 506428 OOOOOOOOOOOOOFFF 0.490789495615092]0-90 4095 0 0000000007FF8 50543,q NOR 2 506438 0 506438 OOOOOO~)0000OOFFF 0.4907894955[S09230-90 4095 0 0000000 O07FF$ 506448 HOR 2 596448 0 536448 OOOOr~OOOOOOOOFFF 0.49078949561509230-90 4095 0 000000 0 O0?FF8 5064'~R HF)R 2 50645~ 0 506458 OOOOO0:)000000FFF 0.4907894956t5092'~0-90 4095 0 000000 0 007FF8 50646~ HP~R 2 50645.~ 0 506468 OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 0 000000 0 007FF8 506478 HDR 2 506478 0 506478 OOOOOOOOOOOOOFFF 0.4907894956]509230-90 4095 0000000 0 007FF8 50548~ HO~ 2 506488 0 5064RR OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 00000000 007FF8':JO649R Hr)r~ 2 c~0649R. 0 50649R OOOOOOOOOOOOOFFF 0.49C789~95615092.~0-90 4095 0 000000 0 007FF8 5064~R HOR 2 5064AQ 0 5064/~ OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 0000000 0 007FF8 5064B.~ HDR ~. 5064R8 0 5064F~8 OOr)OOOOOOOOOOFFF 0.490759495615097~0-90 4095 0 GOOOO0 0 007FF8 5064C8 Hr~R 2 5064C8 0 5064CR OO09000~~OCOOOFFF 0.4907R949561509230-90 4095 0 000000 0 007FF8 $36408 Hr~R 2 50640R 0 506408 OOCOOO300OOOOFFF 0.49078949~61509230-90 4095 0 000000 0 007FF8 e i —J 5064FB HO~ 2 5364F_~' 0 5064E8 OOOOOOOOOOOg3FFF 0.49078949561509230-90 4095 0 0000000 OG7FF8 5064FR HOR 2 5064F8 0 5064F8 OOOOOOOOOODOOFFF 0.49078949561509230-90 0 4095 0 0000000007FF8

506~1R HDR 2 506518 0 506518 OOOOOOOOOOOOOFFF 0,49078~)4956150923D-90~ u 506~ HI~R 2 5065280506528 OOOOOOOOOOOOOFFF Oo4907Rq4qS6150923D-90 609500000000O07Pr~) 506538 HF)R 2 506538 0 50651)8 OOCOOCO~OCOOOFFF O~490789t)956150923D-90 4095 00000000007FF8 50654~ HDR 2 506548 0 506548 OOOOOOOOOOOOOFFF 0,4907894956150923D-90 4095 00000000 007FF8 50&55R HDR 2 506558 0 506558 OOOOOOOOOOOOOFFF 0,4007894956150973D-90 4095 00000000007FF8 506568 HDR 2 506568 0 506568 OOOOOOOOOOOOOFFF 0,4907894956150923D-90 6095 0 0000000 007FF8 506(578 Hr)R 2 506578 0 50(5578 OOOOOOOOOOO0OFFF 0,4007894956150923D-00 4095 0000000 0 007FF8 50658R Hr)R 2 506588 0 506588 OOqOOOOOOOOOOFFF 0o490789~+956150923D-90 4095 00000000 007FF8 50669R HDR 2 506598 0 506598 OOOOOOOOOOOOOFFF 0,4907894956150923D-90 4095 00000000007FF8 5065A8 H~R? 5065A8 0 5065A8 OOOOOOOOOOOOOFFF 0,490789~95615092~D-90 6095 C OOOOOC0 007FF8 506~B8 HDR 2 50650R 0 506588 OOOOOO900000OFFF 0,~907R949561509230-90 4095 00000000 007FF8 5O6r)CR HDt) 2 5D6508 0 (~0650R OOOOO03000000FFF 0,4907894956150973D-90 6095 0 OOOOGO O 007FF8 5065DR Hr)R 2 5065DR 0 5065DR OOOOOO3000000FFF 0,4907894956150923D-90 4095 0 0000000 007FF8 506~)FR HD~ 2 5065E8 0 5065ER OOOOqOOOOOOOOFFF 0,4907894956150923D-90 6095 0 000000 0 007FF8 5065F8 HD~ 2 $065F8 C 5065FR OOOCOOCOCOOOOFFF 0,49078949561509?30-90 4~}95 00000000 007FF8 506608 HDR? 5~6608 0 50660R OOOOOOOOOOOOOFFF 0,490789495615092~C)-90 4095 0000000 0OG7FF8 556618 HI~R 2 50661R 0 506618 OOOOOOOOOOOOOFFF 0,4907894956150923D-90 4095 0 0000000 007FF8 506~7R Hr)l~ 2 50.6628 O 50657R OOOOOOOOOOOOOFFF O,4907894956t50923D-90 4095 0 000~00 0 O07FF 50663R HOR 2 506638 0 506638 OOOOOOOOOOOOOFFF 0,4907894956150923D-00 0 4095 0GOOOOG 0 007F

..,-% $0664R HF)R 2 50664F~ 0 ~0664~ OOOOOOOOOOOOOFFF 0./*9078~49561509230-90 4095 0 000000 0 007FF8 5066~R HDR 2 5066~R 0 50~~658 OOOOOOOOOOOOOFFF 0.4907894956150923D-90 4095 0 0000000 007FF8 ~06668 HD~, 2 506668 0 50666R OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 00000000 007FF8 506678 HD~ 2 50667R 0 506678 OOOOOOOOOOOOOFFF 0.4937894956150923D-90 4095 0000000 0007FF8 506688 HOR? 506689 0 506688 OOOOOOOOOOOOOFFF 0,4907894956150923D-90 4095 00000000 007FF8.506698 HOP 2 506698 0 506698 OOOOOOOOOOOOOFFF 0.4907894956150923D-90 4095 00000000 007FF8 5066AR HOR 2 5066A8 0 $C66A8 OOOOOOOOOOOOOFFF 0o4907894956150923D-90 4095 0 0000000 007FF8 5.~6~R8 HOR 2 5066B8 0 5066R8 OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 0000000 0 007FF8 5066C8 HDR 2 5C66C8 0 5066C8 OOOOOOOOOOOOOFFF 0.4907894956150923D-90 4095 00000000 007FF8 50660R HDR 2 5066D8 0 5066D8 OOOOOOOOr~OOOOFFF 0.49078'-'14956150923D-90 4095 0000000 0 007FF8 5DB6Fq HDR 2 5066E8 0 5066E8 OOOOOOOOOCOOOFFF 0.4907894956150923D-90 409.~ 0 0000000 007FF8.~066FB HOR 2 5066F8 0 5066F8 OOOOOOOOCOOOOFFF 0.400789495615092)0-90 4095 0 000000 0007FF8 50670R HOf~ 2 50670cl 0 506708 OC'gOOOOOOOOOOFFF 0~4907894956[509230-90 4095 0 000000 0 007FF8 506718 NOR 2 ~067t8 0 506718 OOOOOOOOOOOOOFFF O.4907894956150923D-90 4095 0 OOOGO00 007FF8 -50677. R HDR 2 50677. R 0 506728 OOOOOOOOCOOOOFFF 0.4907894956150923D-90 4095 0 000000 0 007FF8 5.0.67~8 HOR 2 5067~Fi 0 506738 OO0.qOOOOOOOOOFFF 0.490789~956150923D-90 4095 0 000000 0 007FF8 5067~,R HDr~ 2 50674R 0 506748 O0'IOOOOO0,OOOOFFF 0.4907894956150923D-90 4095 0 000000 0 007FF8 5067~R HDR 2 506759 0 506758 OOOOOOOOOCO~IOFFF O~490789495&150923D-90 4095 0 0000000 007FF8 <:: 506768 HDR 2 50676R 0 506768 OOOOOOOOOOOOOFFF Oo490789495615092~D-90 4095 0 0000000 007FF8 506778 HDR ~, 506778 0 506778 OOOOOOOOOOOOOFFF O.490789495&I50923D-90 0 4095 00000000 007FF8

506798 HI)~, 2 506798 C 506798 OOOOOOOOCOOOOFFF 0.4907~Jg4956t509230-90 40q5 0 000000 0 007FF8 5067A8 HDR 2 ~067A8 0 5067A~ OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 0OOOOO00007FF8 506788 HDR 2 5067B8 0 506788 OOOOOOOOOOOOOFFF 0.4907894956150923D-90 4095 00000000007FF8 5D670~ HDR 2 506708 0 506708 0003000003003FFt:: O,4907894q56t50923D-90 4095 0000000 0 007FF8 5P67r)8 Hr)R 2 50671')R 0 50670P, OOOCOOOOOOOOOFFF 0o4907894956150923D-90 4095 0 000000 0 007FF8 5967F8 H[)R 2 5067F8 0 5067F8 OOOOOOOOOOOOOFFF 0.4907894956150923D-90 4095 0 000000 0 007FF8 5067Fq H~? 5067F8 0 5067F8 OOOOOOOOCCOOOFFF 0.4907894956150923D-90 4095 00000000 007FF8 506808 Hr~R 2_ 50680~ 0 50~80,q OOOOOOOOoOOOOFFF C.49078949561509230-90 4095 0 000000 0 007FF8 5~6818 HOR 2 5t~6818 0 506818 OOOOOOOOOOOOOFFF 0.490789495615092~D-90 4095 0 OOOOO0 0 007FF8 50682R HOI~ 2 506828 0 506828 OOO0)00000000FFF 0.4907894956150923D-90 4095 0000000 0 007FF8 5068~R HDR 2 50683,8 C 5')6838 OOOOOOOO90000FFF 0.4907894956].50923D-90' 4095 0 OOOOO0 0 007FF8 506848 HOR 2 5068,",8 0 506848 OOOCOOOOOO0~OFFF 0o4907894956150923D-90 40c)5 0000000 0 O0?FF8 5068~8 H[')R 2 506858 0 506858 O0,")0000000000!=FF 0o4907894956150923D-90 4095 0 000000 0 007FF8 50~86~ HO~ 2 50686~ 0 506868 0000000000009FFF 0.49078'94956],509230-90 4095 C 000000 0 007FF8 506878 HI")R 2 506879 0 506878 OOOOOOOOOOOOOFFF 0.49078949561509230-90 4095 0 000000 0 O0?FF8 506888 HO~ 2. 506RRR 0 50~888 OQOOOOOOnOOOOFFF 0.49078949561.509230-90 4095 0OOOC, 00 0 007FF8 506898'HOR 2'~06898 f', 506898 OOOOOOOOOOOODFFF 0.4907894956150923[)-90 4095 0 000000 0 007FF8 506RAq H~)R 2. 5068A8 0 5068AR OOOOOOOOOOOOOFFF 0o49078949561509230-90 4095 0000000 0 007FF8 506888 HDR ~ 5068B8 0 506888 OOOOOOOOOOOOOFFF 0.4907894956150923D-90 0 4095 C OOOOO0 0 007FF8

5068C R Hr~R 2 ~;068~8 0 5')68CR OCOOOOOOOOOOO FFF 0.40078q4956150 023D-90 0 4095 0 OOOOOC O OO7FF8 506,008 Hnq 2 5068D8 0 536808 OOO30~00000 00FIF 0.4907894956150923D-90 4095 00000000 O0?FF$ 5068FR HDI:) 2 5068F. 0 506PE R OOOO0000000~0fFF 0.4907894956150923D-90 0. 4095 0 000000 0 007FF8 506AF8 HOR 2 5068F8 0 5068F8 O OOOOOOCOOOOOFFF 0.4907894956150923D-00 4095 0000000 0 007FF8 506008S HDR 2 50600~J C 5069C8 OOOO030300(,000 FFF 0.49078q49561c;0923D0-900 4095 0 OCO0 0 007FF8 506918 HDR 2 5~6q1_8 0 5069].8 OC/'OO" OOOOOOODFFF 0o4907894956150923D-90 4095 0 000000 0 007FF8 50~928 HOR 2 596929 0 5")6928 OO00OoooocoOOFFF 0.4907894956150923D-90 069 000007F 506978HOR 2S~h 9~~0 SC6~8 000OQOOOOOOFFF0,49~894956~0923-90 04095 0 000000 0007FF8 5069'~8 HOR 2 806938 0 5C6493 00OOOOOOOOOO3CFFF O~&OO7894956150923D-9 0 4095 0 000000 0 007FF8 506q48 H[") 2 506948 0 506948 OOO00gOOOCCOOOF F F40R4510209 049 000007F 50696s H~9 2 36965 50696 OQ3~~0000~3 F~F0.4907894956150 923D- 90 4 095 0 000000 0 007FF8 5[}6978 HDR 2 506978 0 506958 OOOO~OOOOOOOOF FF G.4907 894956].50923D-90 4095 0OO 0 000 07FF8 506969 Hr)R 2 50696~ 0 506968 OOOOOOO03~QOFFF 0.4907894956]5092'~['-90 4095 0 OOOCO0 0 007FF8 50697~ HI'R 2. 5q69798 G 5069978 OOOOOOCOCOOFFF 0.4907894956 ]~0923D-90 4095 0 000000 0 007FF8 5r,'69RR HDR 2 506988 0 506988 00~r)OOOOOOOOOFFF 0.4907894956150923D-90 4095 0 000000 0 007FF8 50699B HDI:: 2 506(:9R 8 0 506998 00003000000003FFF 0.4907894956150923D- 90 4095 0 000000 0 007FF8 FRFE CE~LLS < **NO FREE CFLLS IN US1=**

HERE IS THE GENERATED TREE V.17 A A R r) A S R T B C C r C C C C C C B C c. C C C C C D fn F A N D X Z Z Z 2

HERE AR E THE IT NPUT Sf PT I NG S o~x WE AP MF lUT T1Tl CRASH oJSER PRflrGPAM TNTFRRPIPT. PSW 07150006 7050036A P5W = 0719'0006 76 036A GENPRAL REGI STERS (i***j5 20OAO6R5 0C50Ol1C 70500B72 00520fBAE 00503030 00000000 00000000 005050 OC-00000 0009000 oOOO 0500A90 005051E8 005051E8 00500A90 70500B8C 005003 FLnATING PIITNT REGISTERS.4343't"4 404G4040 400406fl3 00OA06C5 OOCOOOC0 00000000 00000000 00000000 NEXT C'\PO IS

V.19 PL/I (J. Unger) The following program reads sets of input character strings, sequences them by constructing a binary tree based on their relative alphabetic order, and then prints the ordered sets of input strings. The input data is read using stream I/O from SCARDS (default system input). A variable number of blanks are used to separate individual character strings within a set, while a set delimiter of'*' denotes the end of a set of strings. The end of all the input sets is recognized as the PL/1 ENDFILE condition. Each string within an input set is extracted using the SUBSTR function after the position of the first character and the number of characters within the string have been determined using DO...;HILE... and the INDEX function. A node representing the extracted string is then allocated and initialized. A new node is added to the tree using the following algorithm: 1. If the TREE BASE is NULL, this node becomes the top of a new tree. Otherwise, the base pointer TREE is set to point to the top of the tree. 2. The string associated with the new node is compared to the string in the tree node. 3. If the new value is greater, the P RIGHT pointer is followed. a. If P RIGHT is NULL, i.e., there is no other node with a value greater than the tree node's value, the new node is inserted at this point. b. If P RIGHT is not NULL, then there is at least one node with a higher value, TREE is set to point to the next node to the right, and steps 2 and 3 or 4 are repeated. 4. If the new node value is less than the tree node value, then the P LEFT pointer is followed. a. If P LEFT is NULL, i.e., there is no tree node with a a value less than the current tree node's value, the new node is added at this point

V.20 b. If P LEFT is not NULL, there is at least one tree node with a value less than the current tree node's value, and TREE is set to point to the next node to the left and steps 2 and 3 or 4 are repeated. Once all strings have been extracted and added to the tree, the tree node values are printed out in alphabetical order. This is accomplished by starting at the top tree node and using the following algorithm: 1. Follow the PLEFT pointers until a node with P LEFT = NULL is encountered. This contains the (next) lowest sequenced value and is to be printed. A flag is set to'1' to indicate that this node's contents have already been printed. 2. The P RIGHT pointer associated with the node just printed is examined. If it is not NULL, TREE is set to point to the next node to the right, and the process starting with 1 is begun again. If P RIGHT is NULL, step 3 occurs. 3. The parent of the current tree node is examined. If a back trace of a left sub-tree is occurring, the parent node has not yet been printed (PRINT=O), so it is printed and flagged and the process starting with 2 is begun again. If a back trace of a right sub-tree is occurring, the parent node has already been printed (PRINT=l), so the process beginning with step 3 is repeated. The top node of the tree is recognized by its NULL P PARENT pointer.

qAMPLF _PRG: ppfnCntaF OTION (AINs MAN); V.21 STMT t VFt NFT I SAMPLF _ PROG: PRCEF)P F nPTIrNS ( MAIN);'? FFL D AP 4RF INtlr)T CHAP ( 80) 1 F!nDF RAgrD (TPFF), 2 P_ r:t Po NTFR, D _RIC,"T POI N'T EPR, 2 o_PA4ENT PuINTFR, 2 VAl JF CHAR (4), I oTNIT CHAR(!), I X)T n r9TNIA~ V.(15,'?), J TXFn TrXRtY (TNI), rTXFF) RTINARY (1.5,), TRFF _BASE POINTFR, NFW POINTFR; 3 I nN FN-nF L E GO TO END_OF_JOQ; /* 1 I GETNFXT: T = 1;. I J =,: 7 lT F~ n SF =,t'lLL; o 1 GET FnrT ( INPUT) (A(0O ):) 9 I FX TR AC T _STP IN: M =! + J: 1it Pq 1 r) I = M4 Tn P3 WHILE (SLR3STr ( TNPT, Tl) ='' ); ND 1? 1 IF SIJSTR(I TINPIT,TI,) ='*' THFN Gn TO PRINT_R PJTINF; 14 1 J = TNnFX ( StIJSTR( TNPIT, 1+ I),' ); 1 1 TF J = n THEN J = INDEX (StIBSTR(IN PUT, I+1 ),'*'); 17 1 AIITLf) \ r)D: ALLrC.ATF trlr)nF SFT (NEW); IP 1 NcW4 -> _L t FFT = NILL; 1 t "NFNW -> P_ TGHT = NILL;?c 7 NeW -, P PAR ENT = NULL; 21. NEPW: -> PRTNT ='C': ") 1 NEW -W VALU)F = SUJRS TR ( INP PT I,J ); 2 3 1 ADD_Tn_TP EF:'c"-'!E TF TRFF_ ASF = NUILL THFN D3; -,:: 1 1 TRCFFRASF = NEW:?f~ 1 1 (,O TO F X TRAT_S TR ING; 77 1 1 END: 2R I TR EF TRFF_BA SE;?9 1 COM>AP F_VALIF: A3n 1 TIF NFW -> VALUlF = VALUF THFN G3 TO EXTRACT_STRING; 31 1 IF NEW -> VALUIE > VALUE 3' 1 THEN DO; 33 1 1 IF P_RIGHT = NULL 34 1 1 THF n O; ~3~ 1 2 P_ RTGIT = NEw;?A 2 NEW -> P_PARENT = TREE; ~7 11 2 GO TO EXTRACT_STRING; 39 1. 2END; 39 1 1 FLSE DO; 40 1 2 TRFE = P_RIGHT;

S MnLC PRiG: PpRC'EnUQp OnPTIONS (MAIN): V.22 qT'"T I FVFL NFS T 41 1? Gn Tn CnMPARE_VALLJE:; 4~ I 1 ENnD; 44 FLSF nn; 45 1! IF P_l..fFT - N IT.LL +4 1 THFN n': 47 1? P_ LFT = NEW; /4o t1? NW -' P_PARFNT = TRFE; 40) 1 Tn EXTPACT_STRING;'1 E~hFND:'=:1 1 1 FLSF nn; 5? I 2 TR FF = P_LFFT; ~'~ 1.? Grn Tn CnMPARF_V ALUE: 4 1 2 FNrn; ss 1 F1 JNn; 56 PR I PR T_POUI T T N F TQ FE = TPFF_RASE: 7 t CHFC K_P_ EF T: IF P _LFT = NUtLL, q 1 THFN r),n; 5 1 1 PUT FnTT ( VALUE) (A(4)); n F1 1 PRTNT:'1': 6 1 1 CHFCK _P_ RTGHT: IF P_R IGHT. - NUILL 6 1 THFN nn; 63 1 2 CHFCK_PR FNT: IF P_ ARFNT = NULL 64 1 THFN IF PRINT ='1' 65 1? THFN GO Tn GFT_NFXT; 6 f 1 - FLSF On TO PRINT_VALUE; 67 1 ELSF nn: 68 1 TRPF - P_PARENT; 6Q 1 3 IF PRQINT = 1' 7n 1 THEN GO TO CHFCK_PARENT; 71' FLSE nln: 72 1 4 PR INT_VAtJtlE: PIIT FDIT (VALUJE) (A(4) ); 7' 1 4 PRINT ='1': 74 1 4 Gn Tn CHECKP_RIGHT; 7 1 4 ENnD; 7A 1 EN F^D; 77 1 NFt; 78 FLSF nri; 7n 1 2 TREF = P_RIGHT; Pr 1 2 GO Tn CHECKPLEFT; P. 1 2 FND;? 2 1 FND; P3 1 ELSE DO; +4 1 1 TRFE = P_LEFT: 85 1 1 GO TO CHFCK_P_LEFT; 86 1 1 FND; /* 87 1 ENf_OF_JOB:

S, PLA_P pnG: PPoC Fnl JP nTTnNS t MA Nl V.23 V.23;,TT LFVFt. tr:ST R F TI IP N; pRQ I FNO SAMPLF_PPRG;

Rb F-Q-sb Ole-t~~~~Ee~cb 1~~_ M ~s P~ C Cr~ %C rm n~ A h ~\ C CC. T.CCC. CCcnr x A A f A C CC CCC CCCCrA X IIT'i T f7 DM T I>' A T PO -I~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~~~

V.25 LISP (Carole Hafner) LISP Program to Alphabetize Character Strings A node on the tree is represented by a LISP cell whose CAR is the element on the node and whose CDR is a dotted pair of the 2 daughter nodes. When a node is created, the program automatically creates the dotted pair, even though both daughter nodes are NIL at the time. This makes insertion and printing algorithms very simple.

V.26 CONCEPTUAL TREE AB AA C A D LISP STRUCTURE: AB,V AA C 1: 1 0// i~~~~~.. X. Xk_ I~~~ I,,,0 1

INPUT FILE TO LISP ET "ALPHA'(NIL B I: C D E F 13 H I.J t L 7 N 0 P Q F.' T U 1'' ].JX, Y 2) ) — FUN ORDER NIL.PROIG (:.' TREE) B (:'. ET'TREE (LIST ( READI: NIL))':: CoDD (: (lLL': CIR TREE:) ": PRINT'ALL-IDATAI-PROCES:SED)::S.TOP > )) A CIr D:: (HULL,:ET ->' ( REFD).':, (PR TREE TREE):: T FPITINTREE > TREE) (GD1 A:)' 1 O:::::, -FUN PUT I N TREE E ( TREE) (C: COt,:: LOIWER F,: C AFR TREE )'.:: COIND.:::NULL (.':CAIIR. TREE> )::RPF L AA:H:IDR TREE) (LIS:T X NIL)):U: PUTI NTREE X (CADIR TREE))))) U:.': LILL (::DICDR TREE) ):: FR PLt LE A:D lCDR TREE). (L I:ST I L.:: PLIT INTREE X (:CDR TF.'EE ) ) ) ) -FUIN'RTREE (TREE):. FR INT' IN-FORWF RD-ORRDER'::.PRF TREE),: F'R I NT' I N-REVERSE-ORDER ) PR: FR'F TREE):: F' I NT I -FNOTHER-ORDER):: PRO TREE:: FFL1M F'RF (TREE) CO::T: ND ((HNULL TREE) NIL:L (::T:FPRF (C~I.'-3R TREE)) (PRINT (CAR TREE)) (PRF (CDDR TREE))))., -FUN FRR (: TREE):C OND': ('ULL TREE ) NtIL.:T.FPRR I_-:DDR TREE.''.:: F RIN T TEE) PRR (CR TREER TREE))))) -IEFUH PRO (TREE) (: NOD,:( NULL TF;EE NIL":'T PRfINT.:CAR TREE" (PRO (CADR TREE)) ) (PRO:FIDDDR TREE R TREE)):FUN LOWER (LIST 1 LI ST2). PF'PRG ( Z (.:SET', ALF'HA::' I:: COND: ( HNLLL LI. ST 1) (RETURN T.: ). (.E-. (,CIA iR LIS'T1:',:ACR LIST2)) (RETURN::LOtWER (iCDR LISTI).C:D.R LI. T:).:,) O::r-rD ((El) (::AR LI ST ) (:: C-R Z)) (:F.ETURN T) ): El! C:.CAR L I -ST. ) (CAR Z)) ( RE TURN NIL)))::: E T Z,:r:iR Z., ) C1O20 AR ):.,:, ]RrER ):::' i: I. T: P.:L:.1 I F)1 T F' )

.-~,~',Lt I J Lll 1 L8.O 1 1 1. - _ U 1., _r U L rIUJUU'LL. (HILAB rIEF3HIIKLMNOPIR:&TLILoI <YZ) V.28 (NIL A B C, D E F G H I J K L M D P!:S T U V W'r' V.28 ORDER PUT I HTREE F'RTREE F'F F'RR F'PRO LEIAIER I It- F R.I RI D- D r E R H'::R,: E::; F,,':F CH' 1: IF),:.:,:,,: D D:,:F B I:)::L B: Ji':,,:L:: I:,:: R R:T: T):::T F' I t- RE'vER:'E E-OREIDER: T F.'., U,, 1:.- T)' L.'::,.:L B.",:: I F.::, 1:FB I.. Cr,:1 I H::' 1C. B H U:: L. I H-HR,'THER-BE RDER,:.I I R': Q: 1 1'''.:; R F.-' (F E I';,,: L B::, ALL- TFHA-F' R EC:.: D _-_,Ix'::'-i IIT T nN T'M T NIiT:I'

V.29 POP-2 (Brindle) String & List Processing Seminar Assigned problem, written in XPOP (POP-2) The program consists of 6 functions and'one global function call, followed by the data. The functions: INSERT - a general tree-inserting function which, given an item and a function with which to tell if items are in order (f(A,B) true iff A<B in some sense), inserts the item in tree TREE. BUILD - INSERT partially applied to a function comparator of character strips - lines 17 thru 26. BUILD is then a function of one variable, a cstrip, to insert cstrip in tree TREE. LAMBDA notation is for nameless function for two variables, S1 and S2 PRINTTREE - a specific function to linearize a tree of cstrip. EXISTS - produces a truth value. I represent null pointers by integer 0 in my tree structure. EXISTS(PTR) tells whether a pointer exists. Could also have been written FUNCTION EXISTS;.DATAWORD="NODE" END for example missing parameter for DATAWORD and = (in line 4) comes from stack - truth value left on stack by EXISTS. PR_CSTRIP - standard system routine PR prints cstrips with enclosing primes, so I wrote this for neater O/P. EXECUTE - performs bookkeeping for this application. Explanation of some XPOP features: SUBSCRC(I,STR) produces integer value of character I of cstrip STR SP(n) spaces n in O/P, NL(n) produces n newlines, CHAROUT takes integer code and outputs character ITEMREAD produces next token from I/P stream as either an integer or a cstrip function application is effected either with FN( ) or.FN RECORDFNS creates a record class called "NODE" with 3 full item fields, accessed by VAL, LEFT, & RIGHT in order. Also produces constructor and destructor conditionals are terminated with CLOSE; EXIT is a system macro for RETURN CLOSE #N (%ITEM%) denotes partial application, leaves a new function on stack

YPno CmpILFER --- VRSITON I TnnAY Is JUNE 74, 1977. TIMF =?1:?8:41.95. 1 1 VVAPS OFSTNmrE CNSNnODE RIWJT LEFT VAL TREE BUILD;' 1 p CRFF1PriENS("lVNr)F"ijQ C?)->RIGHT->LFFT->VAL->DESTNOIE->CONSN9OE; 5 1 4 l FtNC'r lI E ix I S TS; N T (1;O) F~N: COIMMENT DETERMINES IF TREE POINTER; 6, IFUNICTIIrN INSFPT SIR TNr, I.T; VAIS T; 7 TRF-r->T; CnlNSNnflDISTRTIN,,%,0); COMMENT LEAVE NEW NODE QN STACK; 8 1 IF TPEF=t THEN ->TPF TXTT: 9 1 LOOP: IF LT(STPUtr,,VAL(T)) THEN CIMMENT TEST ORDER USING GIVEN FUNC; IF T-LEFFT.FXISTS THFN LFFT(T)->T; GOTO LOOP LSE ->LFFT(T) EXIT; 1? 1 ELSE IF T.PI G'HT.EXISTS THEN PIGHT(T)->T: GOTO LJOP 113 ELSF ->0IrGHT(T) ExIT; 14 1 ~IA 17 1 T NS QTT LAmD RAn A1 5?; V ZPS 1 N I N? CH I CH2 I; 1i 1 nATAI fPNr, TH( S1 )->N1 DA T A L ENGT (S 2)-N2; 110 I 1->T t?O I L: SURSF.C ( TS1 )->CHI?l I SOiPS Pr ( I,?) ->f. H7'?7 1 IF N!nT(CH1=C4 THEN CHI<CH? EXIT; COMMENT LEAVES TRUTH VAL ON STACK;'3 1 1+1-1>I; F T>Nll? THEN FALSF EXIT; COMMENT FIRST STR >=SECONn IN LENGTH;?4 I F I>N1 T~IN TRUF EXI T; ClvMMNT FIRST SHnPTFR; 3 9 I n Tn I;?'6 1 FNP~) WIT8111; I COMMFNT BUILD NoW FINC OF ONE VAP TO INSERT USING?1 I TEST OF TWO CSTRS;?o 1 FIwIFTInN PRINT _TPI r TREE; -A 1 IF TRrF. FFT. XYTSTS THEN PRINTTREE(LFFT(TRFE)) CLOSE; 31 1 R D PP S TF T l (V AL(TT RiE)) SPM(;)'7 1 If TRF.RTICHT.FXI STS THEN PRINTJTRFE(RIGHT(TREF)) CLOSE; 33 IENFI;~ CnO mrfp TS PPCrSTRIP 34 1' IflfiNCT TnPN PP _CTSTPIP rSTR; VAPS I N; 1 I I->T: DATAI F NS')T'l( CSCfTR)->N; 17 L': r.FHAPnl!1T(SIJSC C(r,,CSTR)) q 1 I1+1->!; 3n I F 1=( N T1hEN GOnTfO L CLOSSF 40 FI ND; 41 1 47 IFIINCTT'N FXFClITE VARS TFR MIN STR; Cn'OmmFNT PERFORMS PROMLEM ASSSIGNED; 41 SI )BSCF-(1,. IT F IF AD)-> TFP MIN; COMMENT GET TERMI NATING CHAR; 3->TREE; 0 44 1 I T.TFmFA n->S TP 4'i 1 F SIS, JFRISC ( 1 ISTR3 TFAM I N THF N 46 2?. Ni PD I T TR E( TEFP)? 2. NL; 47.ITM0FA - >ST a 48 I r F StBSJRP'Pl, f 1STP)=TEPMTN THEN.KILL,

~s? I GnfT) L; V.31 54 1.FXF CIIT: i5; 1 A AIC C CC CCC CCCC PAUL 56 IA4 AC C' C.C CCC C.rCC PAIIL PA.UL CCCC CCC CC C ABC A (At.T oF I/E. 5.) 57 1s A AF. r Cr CCC CCCC PAUtJL CC PAUL CCC ABC C CCCC 4 $ (sr of LA 67) A nR C CC CCC S CC PAUL rND nF CnOMPlLATTnN JJNE 24, 1qS72. TTME = 21:28:45.87. 57 CARnrS WFR F C"FCKFD. NO FPRnRS WERE DETFCTFO. STACK ING fCt S ION.S-= ] 64/3 SCAN = 459 SYNTHFSIZE = 1211 MAXT! P M JSTACK SAGE 4 FXEC. STACK:5 F 53 FINC TTrlN STACK:5i9 OF 1 50 FrN NFSITTIG:n nF 13 CnNr) NFST NG:4 IF lC STORAGF PEMAINING nI CT ONAPY 164 ont IH STR FAM 651 STP tCTUJR F S TORF 143 FREF STRING AREA = 20398 TOTALT TT'IF IN COMPILER 0:0:3.57. ST tJP TT.F 1:O 0o 06, ACTUtAL COMPTILINGC TIME C::O 3.49. L FAN-liP TIMF AT En O:'0:0.02o XF CUTION TERMIN ATfE

V.32 SNOBOL (G. Lift) BRIEF DESCRIPTION OF SNOBOL PROGRAM FOR STRING-LIST PROBLEM The tree data structure is represented by a user-defined data type. Each node is an instance of the data type tree, having three fields. The first field, TWIG, is a pointer to a node containing a word "less than" this node; STEM is the word at this node; BRANCH is a pointer to a node containing a word "greater than" the word at this node. Null pointers are used to indicate no entry. The tree always contains at least one node, even if that node is completely empty. There are two recursive functions to manipulate the tree. HANG(NODE,LEAF) looks at the subtree defined by NODE to find (or create) the proper node for the LEAF (word). If NODE has no STEM (i.e., there is no word associated with this node) LEAF is placed on NODE. Otherwise, LEAF is compared to STEM(NODE) to see whether it should be placed on the right (greater than) or left (less than) subtree. If no subtree exists in the direction chosen, a one node subtree is created. Then HANG calls itself with the top node of the subtree and LEAF. FALL(NODE) prints the tree in sorted order. FALL calls itself to print the words in the left subtree of NODE, then prints the word at NODE, and then calls itself to print the words in the right subtree of node (i.e., a call with argument BRANCH(NODE)). Hence calling FALL with the root node of the tree will print the entire tree. The "main program" is quite simple. First an empty node is created; this is the root node of the tree. HANG is always called with this node. The program then reads in words, one at a time, calling HANG to put each on the tree. When the "end of set" is read, FALL is called with the root node to print the tree in sorted order. The tree is then emptied (by assigning a new value to the root node), and a new dataset is read in. notes: 1) the end of dataset character is "/". 2) words may be of any length, as long as they contain only alphabetic characters. 3) words are read in one per line (the word should be the first non-blank characters on the line. A word may be terminated by any non-alphabetic character, or the end of the line. 4) any end-of-file terminates the program.

t'm":'l 4 (.r'n~lnt 3.C, TD~l'!., 1..71) (!'T3 I"PLEF.':TTt~" T I" Y 1Y " "., 71) *1 1; TF.,,1', = 1;'T' " = 7; * 4 _t, =,r- ltl 7npnTt Y * ~5 I."Fr l "T jr(r('" lFt )') ~ C o i,(tf I (,,7r), *7 nT:('TTrF.(Tt,,7,-Tr, n..Ar t. I-F rPII E = (2',^"t(' p'). lj)I (';r /'( Pr!,) I *~ + "bLL). *9 nl'TDI'T =' *** T.rE rn-T'; r~,Tr'rT = *11 SFr-E:L' TIv =T"q T F = T () * 12 $t'rt.. E F I r'PIT'f. r r 11.F. * 3 I r FT ( tr pr): " P'F' F F.I r ) *14 n ( S (I tFi-T'I 1l F * ~15'ITP(r!T a~ tT{,T = F (T. t,',V FI,-1.( I Ir *17 2Tf'!" "T,',r) = l'rI T(PTE 0'rnr) r ) Inn:( T'l!) * 18!~T(L( rr rSTeC,(T Onr )'()) * ~22:. (Fr. T!-:, nf) *23 rFAL. L.' r(T' Ir"f F)). l(Tt.'v rrrn )) *214 l rnf T ='TFD!((' *25 nt: ( "'!('!,I (r>!"('0l! (nETl]',) ~*2E <t.4

V.34 *** TDrE SnRT., C CC Cr CC CCC Cr'. I z!; 7

rr V.35 r r) r r- r% Z rq zlfq z C C C rlcc lf'ac r;r c.P. C rc t!ec C C a rf t t-r r tnn ast ar iorn

A \ A Prn V.36 ^'T r rr CrC rrFST I'n;l X n I:. EA. A T') T r;E F t EST X XX / r?!OMA n TE rFI!ATin P r T I.EVEl O lIAST STATE?-1EfT EXECUJTEn 11AS 12

,~~*LA'L 5l$did().i ~iASs 10s14.02 06-21-72 # USER "JAiLi Sl(;IEi ()ON AT' lOs50.05 ()a 06-27-72 Ar ic55: stds-d ____ _ #EXECufI(): i bcEG I,'S ** SET-TriE()REtIC DATA STRUC'TUREs: INTERACI'IVE. DEMOihSTRAT.ION..** [ VR:UUM02. 14] EXPLANAT I(),J??data(examole,4, I11).Iv 5Tb5),'e 4a be..*e. FILL saimple L.,4'R IUT F()RAAT: (4a4) it;'5 w.l,_r-erc l ENTHR ()UIPUJf F()RMAA T (Ix,4a4) ~' I ^^?wset(examole) 4k~.o),* e D(),;_I L= 4.C=__. lO_ CPU= _.Q008 ELAPSE=... 4.631..?S1 samrple I AT. _ _.___._- _ _ _ _ —-—. -. -.. -. _ __ -.-.-. -~.. —.-F A A 1 _ 1 1 1. - > 2 B ALL > 4 C 1..v e4or4, nauer 4-.>. 5. _.CA t_. _ __....._..o _.. fCO o be rCacaJ 6 CC ~ ~ C.)ii b)nake t astt~ 0 0()03 > i I L()VE __...... EfT (S-t bS {teQ rci i:,ao ()F FILE 1i s t (exampl e,- 1).__.. __... C t; e O;; set ( u; LI < # < 22]s # 13 by _F.ORMALL(Ii~,%kD x.Aa4)a A f...bALL.......................... C A),~bS 4:i e L()VE?uata(example,,4, II).. rlL: = samoleI __ f.h, -M Il lA lL _ _RA'_ __ __- _ __. -- -— _.-. —---- -—. 4- -- ------.- - -- ----— a- -- Eitl:l ()U~PurF r()RiOAMAT: ( x,4a4) L "EXAM" FR-'HL) u(),i'! L= 4 C= 10 [CPU= 0.225.LAPSE= 358.89]?*set ( examnl e) D i)().E! L= 4 C= 0I O1Ci U= 0.008 ELAPSE= 1.84] > I L()VE > 2 D()G > 3 CCcc > 4 C(), > 5 CCC 6 CC _ ~> 7 CA > 8 C >~ Vy ALL > 10 HAI1.0

UNIVERSITY OF MICHIGAN {II 1 Iflll llll l lfl Ifi ~llllll II l ll Illflll:llll II IV. 38 3 9015 02826 3724?l ist(examole,-l ) I < # < 22]: #= 13 t()RMATs (Ix,4a4) A'f bALL CA CCC CCCC L()a A?aata(example,4, I __ ___ _ ___ ___ FILE = samole2 ENTER INPUT F()RMAT: (4a4) flTtR ()u'fPUT FORMAT: (1x,4a4) e "tXAM" FREED D(),4E! L= 4 C= 10 [CPU= 0.208 ELA-PSE= 38.053?*set( example) D()NE! L= 4 C= 10 [CPU= 0.009 ELAPSE= 3.42]?$1 samole2 > I L()VE > 2 BALL 3 C > 4 C(),v_ > 5 AT > 6 CCCC > 7 DO()G > 6 CA > 9 CCC..>.10.BALL > i11 CC # END ()F FILE?list(example,-l) [1 < # < 22]: #= 13 F()RMATt (lx,4a4) AT BALL CA CC CCC CCCC DOG 7 4