"LIE)R.AR.Y 
 
 OF THE 
 U N IVERSITY 
 or ILLINOIS 
 
 s\o. a<v 
 
Digitized by the Internet Archive 
 
 in 2013 
 
 http://archive.org/details/taxicrinicunitof150ibuk 
 
no. 84- 
 
 X j^^Y- DIGITAL COMPUTER LABORATORY 
 
 ^Q ISO UNIVERSITY OF ILLINOIS 
 
 COD.Z. URBANA, ILLINOIS 
 
 REPORT NO. 150 
 THE TAXICRINIC UNIT OF ILLIAC III: A TENTATIVE DESIGN 
 
 Kimio Ibuki 
 
 August 16, 1963 
 
 This work was supported in part by 
 Contract No. AT(11-1)-1018 of the Atomic Energy Commission 
 

 ACKNOWLEDGMENT 
 
 I am very grateful to Professor B. H. McCormick for revision of 
 the original manuscript in "both content and. presentation^ and also to 
 Dr. R. Narasimhan for the fruitful discussions about list processing. 
 
TABLE OF CONTENTS 
 
 Page 
 
 1. INTRODUCTION .....= « ....... 1 
 
 1.1 The Taxicrinic Unit as One of Several Independent 
 
 Processors ....................... 1 
 
 1.2 Operations of a List Processor .... ........ . 2 
 
 2. DESIGN OF THE GENERAL LIST TRANSFORMATION FACILITIES ..... 3 
 
 2.1 Internal Representation of a List ............ 3 
 
 2.2 Memory Organization ................... 6 
 
 2.3 Instruction Set for Internal Transformations ...... 7 
 
 2.k Examples of Syntactic Transformation Programs ...... 12 
 
 2.5 Skeleton Outline of the Internal Transformation Hardware 1^ 
 
 2.6 Stack Operations ............ l6 
 
 2.7 Sequence Control of Instruction Execution ........ 17 
 
 2.8 Execution of Instructions ................ 17 
 
 3. OUTLINE OF THE AUXILIARY FACILITIES ............. 20 
 
 3.1 Conversion from External to Internal Form of a List ... 20 
 
 3.2 Communication with Another Unit 20 
 
 3.3 Garbage Collection . 21 
 
 3.^ Bilateral List Instructions for a Graph Processor .... 21 
 
 4. SUMMARY 22 
 
 BIBLIOGRAPHY ... .......... 23 
 
 -111- 
 
1 . INTRODUCTION 
 
 This is an interim report of the logical design of the Taxicrinic 
 Unit (TU) of ILLIAC III. 
 
 This report attempts to specify an instruction set and hardware design 
 for the transformation of lists. Within the TU a special representation for 
 lists is employed. It is therefore the manipulation of lists^ presented in the 
 proposed internal form that the body of this paper describes. 
 
 An auxiliary part of the design provides conversion between external 
 and internal representations of lists^ communication with other processing units^ 
 and certain special problem-oriented instructions. At this stage of design only 
 an outline is provided for this portion of the Taxicrinic Unit. 
 
 1,1 The Taxicrinic Unit as One of Several Independent Processors 
 
 Complex information storage and retrieval requires various operations: 
 parallel visual processing^ serial input/output^ arithmetic computation^ and so 
 on. These subprocesses are intertwined with one another. We propose to separate 
 each global process into subprocesses^ assigning a suitable unit for each sub- 
 process^ and communicate partial results between these subprocessors to manipulate 
 the intertwined part of the computation. This compartmentalized construction of 
 processors permits multiple sequences to be executed independently^ while the 
 intertwined processing requires processors to be shared by an interruption 
 technique. 
 
 For example^ the PAU^ TU and AU might process three independent 
 sequences simultaneously. If the process in the TU requires parallel processing 
 or arithmetic computation^ an interruption of the PAU or AU respectively is 
 made momentarily. This feature is more efficient than a construction in which 
 an expensive parallel processor, list syntax processor and arithmetic circuits 
 are provided every unit . 
 
 At present memory elements can be obtained in large quantity at 
 appreciably less expense than can control elements. Accordingly, complex serial 
 processing information is now stored in memory as a program and related list 
 processing is divided into minute basic operations. The development of inexpen- 
 sive control elements and appropriate assembly techniques would suggest a 
 
 -1- 
 
completely different organization of the processor. At present^ however^ it 
 
 does not appear that these techniques have developed sufficiently to build the 
 
 machine as it should be built. We therefore adopt a semi -conventional con- 
 struction; in particular^ the stored program system. 
 
 1 .2 Operations of a List Processor 
 
 In arithmetic computation we are familiar with the basic operations-- 
 addition^ subtraction^ multiplication^ division;, and indexing-- into which any 
 arithmetic process can be decomposed. A contemporary general-purpose computer 
 has these basic operations as instructions. In addition a problem-oriented 
 computer^ for example a differential analyzer^ may have wired-in macro instruc- 
 tions found useful for some limited class of problems^ but not sufficiently 
 flexible for all general-purpose computation. 
 
 This situation has its parallel in the list processor. We first 
 introduce a set of basic operations of general purpose^ and then augment this 
 set by the inclusion of certain problem-oriented instructions. Only general 
 syntax transformations of lists are done in the Taxicrinic Unit. If^ in the 
 course of processing^ an arithmetic computation is required^ the arithmetic 
 unit is interrupted for that purpose. 
 
 In Section 2, the instruction set and logical design of that part of 
 the Taxicrinic Unit for general transformations of lists having the specified 
 internal format is described. In Section 3 is given an outlined of the design of 
 the auxiliary part of the Taxicrinic Unit which provides conversion between 
 external and internal list representations^ communication with other units^ 
 garbage collection^ and certain problem-oriented instructions. 
 
2. DESIGN OF THE GENERAL LIST TRANSFORMATION FACILITIES 
 
 2=1 Internal Representation of a List 
 
 In order to implement complex transformations of lists easily^ lists 
 are represented within the Taxicrinic Unit (TU) in a special internal form 
 described below. However^, the computer must be able to manipulate a list of 
 arbitrary format. To this end, the external form is first converted to the 
 canonical internal form; internal processing is done in this format; and the 
 list reconverted to the external form upon exit from the TU. This format 
 conversion will be treated in Section k. 
 
 In list processing, the coexistence of both random access and dynamic 
 storage allocation requirements suggests a large capacity associative memory, 
 which unfortunately is prohibitively expensive at present. Alternatively, we 
 shall adopt a labeling scheme in which heads of labeled information are stored 
 at an absolute address given by a label and the remainder stored at an address 
 specified by a link. 
 
 A list is constructed of words, each with format shown in Fig. 1. 
 
 65 bits 
 
 1 bit 
 
 identification 
 
 U8 bits- 
 content 
 
 -16 bits- 
 link 
 
 Figure 1. Format of a List Word 
 
 ■3- 
 
There are two types of list word: a syntactic word and a semantic 
 word (Fig. 2). 
 
 I 
 
 h 
 
 address of 
 the left part 
 
 address of 
 the right part 
 
 N <i link — ^ 
 
 (a) Syntactic Word 
 
 ^ 
 
 data 
 
 -W<|— link — {J 
 
 (b) Semantic Word 
 
 Figure 2 . Two Types of List Word 
 
 Three representations of the list H = ( (ABC)d(EF)g) are illustrated 
 in Fig. 3' (a-) parentheses form^, (b) tree form^ and finally (c) the internal 
 form employed in the Taxicrinic Unit, 
 
 Typically (A(BC)) will be abbreiriated (ABC)o 
 
H = ((A(BC))(D((EF)G))) 
 
 (a) Parentheses Form 
 
 B C E F 
 
 ("b) Tree Form 
 
 Syntactic form J 
 
 Semantic form ^ 
 
 Address 
 
 r 
 
 1 
 
 2 
 
 3 
 h 
 5 
 6 
 
 7 
 8 
 
 9 
 
 10 
 
 11 
 
 12 
 
 13 
 
 1^ 
 
 15 
 
 V 16 
 
 > 
 
 1 
 
 5 
 
 o 
 
 
 1 
 
 13 
 
 3 
 
 
 1 
 
 8 
 
 li 
 
 
 1 
 
 l6 
 
 
 
 
 1 
 
 10 
 
 6 
 
 
 1 
 
 11 
 
 7 
 
 
 1 
 
 12 
 
 
 
 
 1 
 
 \h 
 
 9 
 
 
 1 
 
 15 
 
 
 
 
 
 
 A 
 
 
 
 
 B 
 
 
 
 
 r^ 
 
 
 
 
 D 
 
 
 
 
 E 
 
 
 
 
 F 
 
 
 
 
 G 
 
 
 (c) Internal Fo 
 
 rm 
 
 Figure 3- Three Representations of a List 
 
In the internal representation zero in the address field signifies 
 the termination of the list. Semantic data can be in any form: word^ array^ or 
 list--provided this form is specified in the identification field and detected 
 in the AU. If a form requiring more than one word is used^ successive parts 
 are specified hy the link field^ or on occasion, left to the option of the 
 programmer. The use of the link address will be explained later. 
 
 2 .2 Memory Organization 
 
 Memory used by the Taxicrinic Unit can be conceptually classified 
 into six categories : 
 
 (1) Label Table 
 
 All temporary storage stacks and program strings 
 are specified through the label table. The address field 
 of an instruction specifies data indirectly through the 
 label table to allow relocation and potential concatena- 
 tion of data. In particular, the label table contains 
 the stack pointers of all temporary storage stacks . 
 
 (2 ) Available Space 
 
 Except for the label table, all memory spaces are 
 
 taken from the head of available space, if put into use, 
 
 and returned to the tail of available space, if removed 
 
 from use. Words of available space are connected by 
 
 links. The head is pointed to by the head available 
 space pointer (HAP); the tail by the tail available 
 
 pointer (TAP). The return process is called garbage 
 collection. 
 
 (3) Temporary Storage Stacks (TS) 
 
 These stacks are pointed to by the label table. 
 
 Each stack has a string of words connected by links. 
 
 Two stacks can be concatenated together. These stacks 
 
 assume the role of addressable words in a conventional 
 machine , 
 
(4) Working Storage Stack (WS) 
 
 This is a stack of l6-bit cells connected by link 
 addressing. The first (top) and second cell are in 
 the control unit^ in working register 1 (WRl ) and 
 working register 2 (WR2 ) respectively. The address 
 of the third cell is held in the working storage stack 
 pointer (WP). 
 
 Push down and pop up of the stack is automatic 
 and under program control. Registers WRl and WR2 can 
 be interchanged in the course of processing to shorten 
 access time to the memory, 
 
 (5 ) Common Storage 
 
 Lists are stored in the comm.on storage and pointed 
 to from temporary storage stacks by syntactic words and 
 links. Programs are also stored in the common storage 
 and are pointed to from the label table by links . 
 
 (6) Subroutine Stack 
 
 When the instruction "do" is executed^ a link is 
 stored in the subroutine stack^ and returned back by an 
 "end" instruction. This link is pointed to by the sub- 
 routine stack pointer (SP). Recursion to any depth is 
 available using this procedure. 
 
 2 . 3 Instruction Set for Internal Transformations 
 
 The form of an instruction will be seen in Fig. ^a. Two instructions 
 are stored per word^ as shown in Fig. 4b. 
 
 A string of instructions are connected by links and executed in 
 sequence^ unless a "go to" or "do" operation occurs. 
 
 We shall now describe each instruction. The function part will be 
 denoted by a capital letter, with or without a subscript. The address part will 
 be denoted by lower case letters . 
 
^^ 
 
 8 bits^ V"^ / lb bits 
 function — A Z — address 
 
 (a) Instruction Foraiat 
 
 W— instruction »M instruction ^W link — W 
 
 (b) Word Format 
 Figure k. Instruction Word Format 
 
 (l ) Transfer Operations 
 
 Let X be the address of a space in the label table, 
 For brevity we say "contents at address x" to mean 
 "contents of space pointed to by the entry in the label 
 table at address x." 
 
 T„x : Transfer contents at address x to WS 
 
 T x: Same as T^^ with pop up TSx 
 
 T x : Same as T with push down WS 
 
 T X : Same as T with push down WS and pop up TSx 
 
 T, X : Store the data from WS at x 
 
 Tp.x: Same as T, with push down TSx 
 
 T^x : Same as T, with pop up WS 
 
 T X : Same as T, with pop up WS and push down TSx 
 
(2 ) Stack Operations 
 
 T^^MiiS 
 
 none 
 
 PU 
 
 PD 
 
 none 
 
 
 ^2 
 
 ^3 
 
 PU 
 
 \ 
 
 ^5 
 
 ^6 
 
 PD 
 
 ^7 
 
 ^8 1 Sg 
 
 (3) List Manipulation in WS 
 
 L : Concatenate WRl and WI^, that is, construct a new 
 
 c ' ' 
 
 list which has WR2 as left address part and WRl 
 as right address part = Put the address at which 
 the new list is stored in WRl and pop up WS. 
 
 Lpi Split WRl and take the left part of the list, 
 
 that is, take the left part of the address which 
 is specified by the WRlo 
 
 L : Split WRl and take the right part of the list, 
 
 that is, take the right part of the address which 
 is specified by the WRl. 
 
 As an example of the execution of the above instruc- 
 tions, we shall illustrate the change of WS through the 
 execution of the program: 
 
 begin; T^x; L^; T^y; L ; L ; L ; T^x: end 
 
 (see Fig. 5) 
 
Before the process 
 
 10 
 
 Label 
 Table ; 
 
 y 
 
 TS: x' 
 
 y 
 
 X 
 
 V 
 
 11 
 
 Y 
 
 ^1 
 
 \ 
 
 
 Instructions 
 
 
 Change of WS 
 
 1 
 
 1 
 
 P 
 
 3 
 
 Before the process 
 
 A 
 
 B 
 
 c 
 
 Tqx 
 
 X 
 
 B 
 
 c 
 
 h 
 
 ^1 
 
 B 
 
 c 
 
 T^y 
 
 Y 
 
 ^1 
 
 B 
 
 Lr 
 
 ^2 
 
 \ 
 
 B 
 
 L. 
 
 Z 
 
 B 
 
 C 
 
 L 
 r 
 
 \ 
 
 B 
 
 c 
 
 T X 
 
 \ 
 
 B 
 
 c 
 
 After the process 
 
 X 
 
 Label 
 Table : 
 
 y 
 
 TS: x' 
 
 Y 
 
 \ 
 
 \ 
 
 
 
 \ 
 
 Y 
 
 1 
 
 
 \ 
 
 \ 
 
 
 Figure 5 
 
11 
 
 (4) Predicate Operations 
 
 The Control flipflop (FF) represents the predicate 
 value^ true or false. If the test condition is satisfied 
 it is left on^ "l"; otherwise it is turned off^ "Oo" 
 The flipflop is examined in the conditional "go to" 
 operation. 
 
 If the address which is specified by WRl contains 
 a semantic word^ set the flipflop on; otherwise^ 
 off. 
 
 If WRl is 0^ set the flipflop on; otherwise off. 
 
 If the contents at the address specified by WRl 
 equal that specified by WP^;, set the flipflop on; 
 otherwise off. 
 
 Set the flipflop on (true). 
 
 Set the flipflop off (false). 
 
 Complement the flipflop. 
 
 Arithmetic test operations required as part of a Taxicrinic 
 Unit program would normally be executed in the AU, and 
 therefore require interruption of the AU, 
 
 (5) Jump (go to) Operations 
 
 G x: Go to the program which is specified by the label x. 
 
 G x: If FF is on^ same as G x; otherwise, no operation. 
 
 G, x : If FF is on. halt; otherwise same as G x. 
 h ^ u 
 
 (6) Subroutine Operations 
 
 Dx : Placing link in SP, do the subroutine which is 
 specified by label x. 
 
 E: End the subroutine and return to the routine at 
 next higher level, which is specified by SP. 
 
 UNiVtkSlfy OF 
 ILUHOIS LIBjlARf 
 
12 
 
 2.4 Examples of Syntactic Transformation Programs 
 
 (1) Text syntax equality of lists x and y: 
 
 Program 
 
 Pq: T^x; P^; T^y; G^p^; P^; G^p^; L^; T^y; 
 
 L^; V' ^^0^ V2^ ^ 
 p^: P^i S^x; S^y; E 
 
 p^: TgX; L^; T^x; T^y; L^; T^y; Dp^; E 
 
 (2) Extract the leftmost syntax pattern from a list x which 
 matches a list y. Leave it in WS: 
 
 Program 
 
 q^: Tgx; T^y; Dp^; T^y; T^x; G^q^; P^; G^q^; 
 
 L^; T^x; Dq^; S^; G^q.^; T^x; L^; T^x; Dq^; 
 
 S, ; E 
 
 q^: E 
 
 q^: P^; E 
 
 Example 
 
 X - ((abc)d(ef)g(hi)j) 
 
 y - ((12)3) 
 result = ((EF)g) 
 
 (3) Locate the sublist in Z corresponding to the symbol x 
 in y. Substitute this sublist by a list w. Leave the 
 modified list in WS : 
 
13 
 
 Program 
 
 T^y; L^; T^y; T^z; L^; T^z^ Dr^; L^; E 
 
 r^: Tgx; P^; S^y; T^z; G^r^i E 
 
 rg : TqW; E 
 
 Example 
 
 X = 3 
 
 y = (i(23)M(56)7)8) 
 
 z = ((ab)(c(de))(fg)((hi)g(kl))m) 
 
 123 45678 
 w = (pq(rs)t) 
 
 result = ((AB)(c(PQ(RS)t))(FG)((HI)g(KL))m) 
 
 (h) Test whether WRl is additive form or not (here y = "+" ) 
 Sq- l^/ L^i T^y; Pg^ Sg^ s^; E 
 
 (5) Test whether x is a simple factor string or not: 
 t^: Tgx; L^; Dt^; G^t^; E 
 
 t^: T^x; P^; G^ty Ds^; G^t^; T^x; Dt^; S^i E 
 
 t^: Tgx; L^; m^; E 
 
 t^ : S[-X^ E 
 
 1 1 I Oi X j P 9 E 
 
 (6) Remove parentheses from a polynomial by use of the 
 distributive law: 
 
Ik 
 
 Program 
 
 T3X; L^i DUq; L^; DUq^ E 
 
 u^: TgX; L^; Du^; T^y; T^x; L^; L^; Du^; L^; 
 
 L ; E 
 
 '^3'^^ ■'^^^ '^3^^ ■'^r^ ^r^ ""^c^ '^0^° ""^c' ""^c^ ^ 
 
 u, : E 
 4 
 
 Example 
 
 WS = (A + B)(c(D + E) + F) 
 result = (ACD) + (ACE) + (AF) + (BCD) + (BCE) + (BF) 
 
 2 .5 Skeleton Outline of the Internal Transformation Hardware 
 
 Figure 6 is a skeleton diagram of the internal transformation 
 hardware of the Taxicrinic Unit. Registers are connected to a bus through 
 gates controlled by the command control box of Fig. 6, Registers AR (address 
 register)^ WP^ SP^ ILR (instruction link register )j, HAP^ TAP and SI are I6 
 bits eacho MR is 65 bits. IR (instruction register) stores two instructions 
 concurrently and is a ^8-bit register, WRI and WRII are 2h bits each and act 
 the roles of WRI and ¥R2 alternatively. 
 
 Operation of this register complex will be described in the following 
 paragraphs . 
 
Word read from memor' 
 
 from CC 
 
 1 r 
 
 J . L 
 
 T 
 
 left I I right i link 
 
 6 
 
 Memory Register (MR) 
 
 FF 
 
 cc -^O*- 
 
 Comparator 
 
 1 
 
 WRl 
 
 WRII 
 
 AR 
 
 Instruction Register (IR) 
 
 To each 
 gate (O) 
 
 Decoder 
 
 SP 
 
 r--^ tl— 4 
 
 Command Control (CC) 
 
 ILR 
 
 yo*- 
 
 ^o^ 
 
 V 
 
 '^-O- 
 
 <-o-*- 
 
 -•-O*- 
 
 >o- 
 
 TAP 
 
 ZH^ 
 
 SI 
 
 -*-0*J 
 
 15 
 
 -*^ To Memory 
 Interface 
 
 Read or write command 
 
 Figure 6 
 
16 
 
 2,6 stack Operations 
 
 Push down and pop up of the stack are basic operations of the 
 processor. The sequence of commands for these operations is as follows: 
 
 (1) PDl (x^y): Push down stack pointed to by x (and write y) 
 
 HAP -> AR 
 
 read 
 
 link of MR -^ HAP 
 
 X -^ link of MR (y "* contents of MR) 
 
 AR -^ X 
 
 write 
 
 (2 ) PD2 (x^y): Same as (l) except that x specifies address 
 of the pointer . 
 
 HAP -^ AR and SI 
 
 read 
 
 link of MR -* HAP 
 
 X -^ AR 
 
 read 
 
 SI -* AR (y -> contents of MR) 
 
 write 
 
 AR -^ link of MR 
 
 X -* AR 
 
 write 
 
 (3 ) PUl (x^y): Pop up stack pointed to by x (and read it 
 into yj ^ 
 
 X -^ AR 
 
 read 
 
 link of MR -* X (contents of MR -» y) 
 
 AR -^ link of MR 
 
 TAP -» AR 
 
 link of MR -^ TAP 
 
 write 
 
17 
 
 (k) PU2 (x^y); Same as (3) except x specifies instead the 
 address of the pointer . 
 
 X -* AR 
 
 read 
 
 TAP -> AR 
 
 link of MR, -> TAP 
 
 write 
 
 link of MR -^ AR 
 
 read 
 
 X -* AR (contents of MR, -> y) 
 
 write 
 
 2 .7 Sequence Control of Instruction Execution 
 
 Figure 7 shows the flow diagram of sequence control of instruction 
 execution. Switch LRSW identifies whether executed instruction is left or right, 
 Execution of the instructions^ except sequence control instructions, will be 
 described in the following paragraphs. 
 
 There is another method, not shown, in which number of reading cycles 
 could be chopped in half by adding ^0 bits of registers. 
 
 2 ,8 Execution of Instructions 
 
 (1) T and S Instructions 
 
 Push down and pop up of TS are done by PD2 (IR, WR) 
 and PU2 ( IR, WR) respectively. 
 
 Push down and pop up of WR are done by PDl (WP, WR) 
 and PUl (WP, WR) respectively, if both WR's are full or 
 empty. 
 
ILR -* AR 
 
 read 
 
 18 
 
 inverse and check LRSW 
 
 L 
 
 LI of MR -> IR 
 
 decode function of IR 
 
 PDI (SP, 
 ILR and LRSW) 
 
 read 
 
 MR -> ILR 
 
 unless G, D, E 
 
 PUI (SP, ILR 
 and LRSW) 
 
 execute 
 
 Figure 7 
 
19 
 
 (2) L Instruction 
 — c 
 
 If WR's are full^ as follows: 
 
 HAP -> AR 
 
 read 
 
 link of MR -^ HAP; WRl ^ left of MR; WR2 -> right of MR 
 
 write 
 
 AR -* WR2 
 
 pop up WS 
 
 If WR's are not full;, as follows: 
 
 WR -^ AR 
 
 read 
 
 left of MR -> SI (or WRl) 
 
 WR2 -^ left of MR 
 
 right of MR ^ WR2 
 
 SI (or WRl) -» right of MR 
 
 -^ identification hit of MR 
 
 write 
 
 AR -> WRl 
 
 (3) Lfl and L Instructions 
 
 WR -* AR 
 
 read 
 
 left of MR (L^) 
 
 right of MR (L ) 
 
 r ■ 
 
 WR meaning WRl if full and WR2 if not full 
 
 (k) P Instruction 
 V — s 
 
 WR -^ AR 
 
 read 
 
 identification of MR -^ FF 
 
 (5) P Instruction 
 ^ — n 
 
 If WR = 0_, set FF on 
 
20 
 
 (6) P Instruction 
 \ — e 
 
 If both WRs are full, 
 
 WRl -* AR 
 
 read 
 
 contents of MR -> comparator 
 
 WR2 -* AR 
 
 read 
 
 contents of MR -^ comparator 
 
 set FF according to the result of comparator 
 
 If WR's are not full, 
 
 WR2 -> AR 
 
 read 
 
 contents of MR -* comparator 
 
 WP -^ AR 
 
 read 
 
 left of MR -^ AR 
 
 read 
 
 contents of MR -» comparator 
 
 set FF according to the result of comparator 
 
 (T) P , F , and P Instructi 
 
 ons 
 
 -f^ 
 
 Set FF on, off, or complement, according to the 
 function of IR„ 
 
3. OUTLINE OF THE AUXILIARY FACILITIES* 
 
 3.1 Conversion from External to Internal Form of a List 
 
 It is desired that the external forms of the list structure to be 
 converted can be as flexible as possible. These forms include a string of 
 symbols, a string of instructions, data produced in another unit, and so on. 
 
 First, these forms are converted into linear list forms by instruc- 
 tions (given below) for conversion. Subsequently, they are converted into the 
 proper internal form by internal transformations. Examples of suggested con- 
 version instructions include : 
 
 set source address 
 
 save source address 
 
 take source address 
 
 search for symbol 
 
 compare symbol 
 
 count number of symbols 
 
 set left symbol 
 
 find right symbol which matches set left symbol 
 
 make linear list 
 
 name list label, etc. 
 
 3.2 Communication with Another Unit 
 
 To avoid duplication of circuitry, communication with other units is 
 desired. In TU processing occurrence of an arithmetic computation, such as a 
 "square root" or "larger than" test, requires momentary use of arithmetic 
 circuitry. In this situation the AU is interrupted by TU. In like manner, 
 occurrence of parallel processing, such as direct association--not list 
 association--causes interrupt of the PAU. Similarly, input and output of a 
 list requires use of the l/o unit. 
 
 For these purposes, the following instructions should be provided: 
 
 A detailed design of this part of the Taxicrinic Unit has not been done; 
 only an outline will be given here . 
 
 -21- 
 
22 
 
 interrupt PAU; and start program from address x 
 
 interrupt AU, and same as above 
 
 interrupt l/O, and same as above 
 
 test communication flipflop i 
 
 store the word specified by WS into the absolute address x 
 
 Design of these instructions depends upon design of other units^ in 
 fact, of the whole system. 
 
 3.3 Garbage Collection 
 
 Usage of available space requires garbage collection instructions. 
 
 3 . h- Bilateral List Instructions for a Graph Processor 
 
 Bilateral methods for graph manipulation have been introduced and 
 explained in a companion report. Instructions for bilateral list processing 
 include : 
 
 cancatenate 
 
 invert 
 
 convert into internal form 
 
 convert from internal form 
 
 etc. 
 
 ■X- 
 
 Kimio Ibuki: Preliminary Discussion of List Processor Design, Digital 
 Computer Laboratory File No. 5^7; August 15, I963. 
 
h . SUMMARY 
 
 A tentative design of a processor of lists having specified internal 
 format has been described. A set of instructions^ programming examples^ 
 skeleton diagram of hardware required^ and associated sequence of micro- 
 commands to execute each instruction have been explained. An outline of 
 prospective auxiliary facilities of the Taxicrinic Unit has been appendaged. 
 
 By construction, the machine would be able to implement any known 
 list transformation, including dynamic storage allocation and programming at 
 machine instruction level to any depth of hierarchy with possible recursions. 
 The design described in this report is, however, tentative and will be modified 
 and revised into final form through further detailed design, results of program 
 simulation, and adjustments to make the unit compatible with the other units 
 of the computer. 
 
 -23- 
 
BIBLIOGRAPHY 
 
 1. A. W. Holt: A Mathematical and Applied Investigation of Tree Structures 
 for Computer Syntactic Analysis, Doctoral Thesis of Univ. of Pennsylvania, 
 1963 
 
 2. C. Y. Lee and et al. : A Language for Symbolic Communication, Sept., I962 
 
 3. J. McCarthy: Recursive Functions of Symbolic Expressions and Their 
 Computation by Machine, Part I, Comm. of A. CM., Vol. 3, No. h, p. l8^, 
 April, i960 
 
 k. B, H. McCormick: Design of a Pattern Recognition Digital Computer, Part I: 
 General Introduction, Digital Computer Laboratory Report No. 125, Oct., I962 
 
 5. R. Narasimhan and B. H. Mayoh: The Structure of a Program for Scanning 
 Bubble- Chamber Negatives, Digital Computer Laboratory File No. 507^ 
 Febr., 1963 
 
 6. A. Newell: Information Processing Language V Manual, Prentice-Hall, Inc., 
 1961 
 
 7. A, Newell and H. A. Simon: The Logic Theory Machine, PGIT of IRE, IT-2, 
 No. 3, Sept., 1956 
 
 8. The Research Lab, of Elec, and Comp. Center, MIT: COMIT Programmer's 
 Reference Manual, I961 
 
 9. V. H. Yngve: The COMIT System for Mechanical Translation, Proc. of I.C.I, P., 
 p. 183, 1959 
 
 -2k-