Ban »BBwmini mmmSSSSSSi mssmsm W$F Digitized by the Internet Archive in 2013 http://archive.org/details/gimligimlmachine856henn UIUCDCS-R-77-856 f 7 - jn/L'CU UILU-ENG 77 1708 COO-2383-0037 E GIMLI AND GIML A MACHINE AND PROGRAMMING LANGUAGE FOR LOW COST INTERACTIVE GRAPHICAL SYSTEMS by NEAL MICHAEL HENNEGAN April 1977 UIUCDCS-R-77-856 GIMLI AND GIML A MACHINE AND PROGRAMMING LANGUAGE FOR LOW COST INTERACTIVE GRAPHICAL SYSTEMS by NEAL MICHAEL HENNEGAN April 1972 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS 61801 Supported in part by the Energy Research and Development Administration under contract US ERDA/EY-76-S-02-2383 and submitted in partial fulfillment of the requirements of the Graduate College for the degree of Master of Science. iii ACKNOWLEDGMENT I would like to express tny profound gratitude to Professor C. W. Gear for his ideas, suggestions, and wisdom, to Jin Stynes for his ear- lier work on this topic, to hob Goldberg for his sound advice, and most of all to my wife Martha for her unfailing support. iv TABLE OF CONTENTS 1. INTRODUCTION 1 2. ARCHITECTURE 3 2.1 The Variable Stack 3 2.1.1 .Addressing Modes 4 2.1.2 Stack Variable Types 5 2.2 Instruction Space . 8 2.2.1 Control Transfer Instructions 9 2.2.2 Uniqueness of the Value of the Stack 'Pointer at Labels 10 2.3 Procedure Stack 11 2. A Text Ruffer 12 2.5 File Structure 15 3. 10 AND PROCEDURE INVOCATION STRUCTURE 22 3.1 The Display and Related Instructions 29 3.2 Screen Coordinate Related Instructions 29 4. DEBUGGING FACILITIES 31 5. IMPLEMENTATION 32 5.1 GIMLI — GIML Interpreter 32 5.1.1 Active File Management 33 5.1.2 Input Handling 39 5.2 CAS — CIML Assembler 40 5.2.1 Forward References 40 5.2.2 Symbol Table 41 5.2.3 Symbol Table Pun Time Data 44 5.2.4 Perspectives for Development . 45 LIST OF REFERENCES 46 APPENDICES A. Instruction Synopsis 47 B. Instruction Opcodes and Assembler Formats . . 52 ■ r: ■■"■I i r ■ J i; c: 1. INTRODUCTION The need to provide a simple and efficient means for the produc- tion of interactive graphical systems has lead to the formulation of a hypothetical computer whose machine language is referred to as GIML, The class of interactive graphics systems for which this hypothetical machine is intended consist of those which accept input in the form of text lines and screen coordinates and employ two dimensional pictorial representations which change in an incremental fashion. These systems are low cost and generally do not involve extensive processing. Typi- cally, the systems function as intelligent terminals constructing a data hase which is analyzed remotely. The design objectives of the hypothetical machine and program- ming language are twofold. The first objective is to aid in the translation of the conceived man-machine dialogue into an actual pro- gram. This aid to translation consists of two forms. T he first is a powerful instruction set which places particular emphasis in the areas related to user communication. The second aid to implementation deals with program control. By integrating input response into the nesting of procedure invocation, structure is imposed on the program, and equally important, the scheme provides for the scoping of input response which greatly simplifies the programmer's task. The second design objective is to facilitate the management of the data base and graphic information which represents the sum total of the user's interaction. This is accomplished by incorporating both the data base and display information into highly structured, though flexible, Mata files and by providing t ". lan^ua;»f- with a suffi- cient number of powerful data structure commnr Because the design is intended for a low-cost system supporting one, or perhaps a few, praphic terminals of the storage tube type, a number of constraints have been recognized in the design. These include limited primary memory smen and the need to sbare code NlOflg several users. Use of the liypothetical computer is possible throuob the development of two programs. The first of these programs emulates the liypothetical machine and is called GDfLI for Graphical Interactive Machine I,an",uaj^e Interpreter. The second propran, CAS, is an assembler for the HTML propranivinp lanpuape. This paoer details the architecture of the liypothetical machine, outlines the CI"L instruction set and as- sembler directives, and finally presents the major implementation features of the interpreter and GIML assembler . 2. ARCIUTIXTURF In order to facilitate a complete description of the machine's architecture the. instruction set is categorized according to dependence on architectural features. The hypothetical rnchine consists of the processor (i.e., the Mechanisms for the operation of the machine), five distinct information spaces, and several registers relate! to program status such as the stach pointer and program counter. The processor can be implemented in hardware, firmware, software, or in any combination of the three. To date the machine has been implemented in software only. The five information spaces are the procedure stack, the variable stack, the text buffer, the active files, and the instruction or program space. Ve begin discussion with the information spaces and related instruc- tions. 2.1 The Variable Stack The machine uses a stach having a sixteen-bit word length for variable storage. T he programs we want to deal with principally refer- ence two areas of data — data local to the current procedure and data plobal to the program. ' r he address structure uses and encourages this by utilizing the two ends of the stack for the two areas. because the range of addresses within the two areas is usually small, few address bits are needed to provide direct access. Certain instructions refer- ence only the top of the stack; others reference variables located within the stack. The latter instructions utilize one byte of the instruction as a stach level address field. The eight-bit address field can reference the stacl in one of three- iw'cs: Local, global, and Indirect* 2.1.1 Address hip, 'lodes Local addressing snecifies the address of = < local stacl: level expression> This pseudo op associates the variable identifier on the left with the stack level giver by the expression on the right. A local stack level exnression consists of a local stacl level variable and an optional sp- 1 2 3 1 4 2 5 3 G A 7 5 Address of "x" is 007 or 102 fipure la. sp- 177776 375 376 177 Address of "b" is 376 or 102 fi^urp lh. sp =» v: 40003 Address of "y" is 00?, 105, or 102 fipure lc. All numbers are in octal numeric expression involving '+' and/or '-'. "'lie period, '.', is recog- nized by the assembler to represent the current top level of the stack, and is treated as a local variable. The following are valid local vari- able declarations: w = . x = . - 1 (one level down from the top of the stack) y = x z = 1 + y (one level above "y") The second means of declaring a local variable is the construction: dclloc [] The statment generates an instruction which loads the value of on the stncl and associates the. local variable with the new top of the stack. If no number is specified, zero is used. Global variables are those located at the base of the stack and are referencev! using global addresses. A.n important feature of these variables is that their address fields remain invariant with respect to the stack. The OT?tL language takes advantage of this fact and. extends the definition of these variables to the entire program — hence the name "global". Global stack variables are defined using the assembler pseudo op: dclglob The pseudo on associates the identifier with the next free global stack level, but in itself, does not create space on the stack. At the beginning of program execution, the stack pointer points to the base of the stack.. If one knows the number of global locations needed in the program, one can create space at the base o r the stack with a PllSr oiumber of levels> instruction at the beginning of the program. The assembler features the ^LLOCGLOFS directive which counts the number of global variable definitions in the entire program and automatically <-enerates n PUSH instruct inn for the appropriate number of 1 < -. ■ The third type of variable is the - - 1 p.Tr.--- tter \ >■- fined in the PROCEDURF declaration statement. The follow! f L itate- nent Indicates the beginning of procedure "abc" Fines the parameters :c , y , an<*. v. ; procedure abc(x, y, z) A simple •in' 1 flexible call-by-reference scheme for parameter linkage is occopipl ished using the indirect addressing node as follows, cedure Ls called, the address field of each actur] parameter is loaded onto the stacl in their order in the call stater tut. Any reference to a formal paraneter in thr procedure is a simple indirect through the stack level containing the address field. The displacement to t^e stack level containing the address fiel 1 is known at assembly ti^e fror the position of the formal paraneter In the procedure lefinition and from the current level of the stack in the procedure. The programmer need not he overly concerned with the linkage mechanics. The r >.\F assembler automatically generates load instructions for the parameter address fields and uses the indirect addressing mode whenever a f ornal parameter is referenced. All stack variables must be defined Trior to use as an operand. Local and formal parameters are defined only in the procedure containing the declaration. Global vari ables are defined in all procedures in the program. 2.2 Instruction Space The OIML instruction space is byte addressable (8 bits per byte) and not modified during execution. It is therefore totally re-entrant. Because of this, code can be shared and, when code has to he swapped in for large programs, only a one-way transfer fron disk is necessary . "he instruction opcode length is one byte. Only seven of the eight bits in the byte are required to specify uniquely the nearly 12P, instructions. The low order hit is used to nircoprogram some, of the instructions. For example, the low order bit may indicate whether or not ths stack should be popped. Most of the instructions are fixed length; the Majority con- sist of only one byte, the opcode. Those of variable length have a byte following the fixed length containing the number of following bytes to be included in the instruction. The maximum program size is 2**16 or 65,536 bytes requiring 16-bits to specify an absolute address. Absolute addresses and all other 16 bit values are assembled into machine code as two bytes; the low order eight bits of the value is in the byte with the lower address. 2,2.1 Control Transfer Instructions Control transfer instructions permit the transfer of control either forward or backward in the current procedure. The destination address in the instruction is represented either as a sixteen-bit abso- lute address or as an eight-bit offset relative, to the program counter. The absolute address can represent any location in the program. The eight-bit relative offset allows for branching un to 128 locations forward and 127 locations backward. The program counter is incremented after each fetch so that the offset to the label prefix is calculated from the address containing the offset plus one. 10 2.2.2 Uniqueness of the Value of the T^tack Pointer at Labels Due to the dependence of the address field of local variables on the stack pointer the stack pointer must be unique at each instruction. A major function of the CAS assembler is to monitor the stack level and check for instances in which the stack pointer could have more than one value. The effect of each instruction on the stack pointer is constant. Therefore discrepancies in the stack pointer can occur only at locations in which control continues from more than one source (i.e., at a label). The first encounter of a label in the source during assembly, either as a label prefix or as a branch address, establishes the value that the stack should have at the label. As an example, during the assembly of the following code: load x (1 beq done (2 (3 (A done: load y (5 if the label "done" in line 2 has not been referenced earlier, then the stack level associated with the label "done" is the level at the con- clusion of the BEG instruction. The value of the stack at all subse- quent occurrences of the label "done", including line 5, is checked for equivalence and if unequal, an error message is produced. Ambiguity of the stack pointer arises during assembly when the label following an unconditional control transfer instruction (BR, JMP, or RETURN) has not beon encountered in the preceding source. The value of the stack immediately following an unconditional transfer is irrel- evant since execution will not continue through to the next statement. If the label following the unconditional transfer has been encountered earlier, then the value of the stack at the label has been established. 11 If, on the other hand, the label has not been encountered, then the level at which to set the stack is uncertain. In these situations the assembler produces an error message and continues with the current stack pointer. The ambiguity can always be avoided (and in my opinion should) by placing previously unreferenced sections of code after at least one reference to the label prefix. If this should prove undesirable, the set stack level pseudo op . ■ < local stack level expression> can be used to establish the stack pointer relative to the current value or some local variable. 2.3 Procedure Stack Interaction handling can lead to complex programs when each pro- cedure must recognize all acceptable forms of input. Therefore, many of the controlling mechanisms have been built into the "hardware" of the machine. The principle tool is a procedure stack whose use is described in Chapter 3. This stack holds implicit parameters associated with pro- cedure invocation. The parameters include the return address, the value of the stack prior to the call, the address of the current object file name, and the address of the current screen partition or grid. The later two parameters require further explanation. There are two types of call instructions in OIML, CALLI (call internal) and CALLE (call external). The CALLI instruction invokes a procedure in the current program. The absolute address of the procedure is assembled as part of the instruction. The CALLE instruction invokes a separate program. The name of the object file of the external program is either part of the instruction or is contained in the text buffer. 12 At the instance of the call external Instruction, the name of the object file is loaded onto the top of the new procedure stack level and control is transfered to the first location In the new file. During the CALLI instruction the object file does not change. In this case no name is copied; the implicit parameter containing the address of the current ob- ject file name in the new procedure stack level is set to that of the old level. The last implicit parameter deals with a machine mechanism which partitions the screen into areas. The partition which is in the form of a grid affects the handling of the joy stick input and can be dynamical- ly identified with procedures. That is to say, if a partition is estab- lished in a procedure (see SETGRD), the partition will remain in effect across calls to other procedures which may establish entirely different partitions. It is necessary therefore to store the partition in the procedure stack. At the instance of the call, the implicit parameter In the new level contianing the address of the grid is initialized to that of the old. The called procedure thereby inherits the grid of the call- ing procedure. If a new grid is established, it is loaded into the top of the new procedure stack level and the implicit parameter is set to its address. The grid of the outer procedure is not affected. Figure 2 shows the appearance of the stack after one internal call and one exter- nal call to an object file "exproc". Notice that the top level of the stack has inherited the grid of the calling procedure, 2.4 Text Buffer Strong emphasis has been given to the text processing capabili- ties of the machine. Text lines are one of the basic 1-0 forms and are 13 Procedure Stack 071732 07.1734 071736 071740 071742 071744 071700 071744 071712 'exnroc previous stack level return address name pointer stack level before call grid pointer procedure nane 071700 071702 071704 071706 071710 071712 071714 07171.6 071720 071722 07172/, 071726 071730 071640 072 071652 073274 071712 2 100 200 4 10 20 30 40 previous stack level return address name pointer stack level before call grid pointer ft of x coords in grid /' of v coords in <*rid 071640 071642 071644 071646 071650 0716.52 071660 071662 071664 071666 071670 071672 071674 071676 027 071652 073276 071660 Vain' 3 10 20 400 3 20 70 120 previous stack level return address nane pointer stack level before call grid pointer procedure nane i? of x coords in grid // of y coords in grid figure 2. u an integral part of the screen displays and data structure-. ■ ,1 the design philosophy of the machine is the ninlnization of data space that need he highly accessihle. The emphasis has heen to shift as nuch data storage into active files which can he brought into core when necessary. The machine provides one highly accessihle (in core) text buffer and a multitude of text processing instructions which operate on this buffer. In conjunction with the text buffer, the machine provides three reg- isters, one of which, "In", is read-only and contains the number of characters in the buffer. The other two registers, referred to as "pi" and "p2", are pointers into the text buffer and are used to delineate strings and point to character positions. The first character position in the text buffer is numbered zero. The pointers "pi" and "p2" can range from zero to the number of characters in the text buffer. A point- er with a value equal to the number of characters in the line is one position past the last character in the buffer. The pointers can be moved at will and are interchangeable in many instances. However, a convention is used throughout whenever the text in the buffer behaves as an operand. The characters moving right from "pi" up to but not includ- ing the character at "p2" form the standard operand text string often referred to as the "text between pi and p2". A null text string is an acceptable operand and occurs when "pi" = "p2". Consequently, while the pointers are free to assume any relative position, "pi" is generally less than or equal to "p2". The convention is further reinforced when text is loaded or inserted into the buffer. As long as "p2" is greater than or equal to "pi", "p2" will change directly with the number of characters in the buffer. That is to say, if text is inserted or de- leted, "p2" will continue to denote the right boundary of the text string. 15 2.5 File Structure The basic end products of the graphical systems for which GIML has been designed are graphical displays, or pictures, and data struc- tures which convey the sum total of the user's interactions. Central to the machine is the integration of the display file and the data base into what is referred to as an active file. Active files are character- ized by two features which make them highly suited to their use as display files and as a data base. The first feature is that the files are processed linearly for display which makes for very fast and effi- cient translation into display code. A single instruction displays the contents of an entire file (this is discussed in the following section). The second feature is the highly structured, though flexible, format which is conceptually very simple. The simplicity provides for easier programming and equally important, yields a more usable end product. A file is intended to be a complete graphical entity. It may represent a composite of many disimilar forms. Files consist of struc- tures termed blocks . Blocks, on the other hand are collections of very similar forms or data elements. Each of these similar forms is con- tained in a separate structure termed entry . Entries are the basic element in an active file and are struc- tured to contain three data types. These are line segments in the form of x-y quads, information words, and text lines. Line segments and text lines in an active file can be displayed on the screen. These two types form the composition of all pictures. Information words contain data which is not part of the display and are available to the programmer for If general information storage. Typically, these words contain additional information about the data in the entry. For example, if a line con- nects two items it may be advantageous to store pointers to the two items. Entries are grouped into data structures termed blocks. All en- tries within a block have the same number of information words and x-y quads. These numbers are established at the creation of the block. However, the number of text lines is not prescribed and can vary from entry to entry. The structure of an entry is detailed in figure 3. The first word contains the displacement count in words to the end of the entry. A null entry, that is one without x-y quads, information words, or text lines, has a displacement count of zero. The space following the displacement is set aside at the creation of the entry for the number of information words specified in the block head. Following the informa- tion words is the x-y quad section of the entry. An x-y quad consists of two x-y pairs which form the end point of a line segment. Each coor- dinate uses one word and is considered to be a two's complement integer. Following the x-y quads is the text portion of the entry which consists of an unspecified number of text lines with position coordinates. Text lines are stored as text groups, which is to say, one character per byte (i.e., two per word) with the first byte containing the character count. Text groups begin and end on word boundaries. Hence, if a line contains an even number of characters, the group length is odd and a null byte is padded onto the end. The first two words in the text portion contain the x and y position coordinates of the first text line. Subsequent text lines are displayed beneath the previous line. Space for the text coordinates exists only if there is at least one text line in the entry. ENTRY 17 Disolacenent to end of entrv Information words (# of words specified in block header) X-Y quads (i!' of quads specified in block header) Unspecified nunber o* 7 text lines with display coordinates TEXT PORTION TEXT POFTION OF ETITPY Y display coordinate of text X display coordinate of text Character 1 Length of text line in characters Character 3 Character 2 Character 5 Character A • • Character 1 Length of text line in characters Character 3 Character 2 • • figure 3 Peleting the Jast text lino In nn entry would .ilso vided for the text coordinates. The next structure in the hierarchy Lfl the block which outlined in figure A. \ block consists of a I and any number of entries. The first word in the blockhead contains the displacement in words to the end of the block. An empty block has a displacement equal to seven. Notice the two words in the block head which contain the num- ber of information words and x-y quads per entry. The last two words in the block head contain displacements in the x nnd y directions, I)X and DY, which are to be applied to all coordinates contained in the block. Figure 5 details the structure of the file. The file consists of a one word header and a variable number of blocks. The maxii up file size is 65,536 sixteen-bit words. There are two types of files — those which are active and those which are not. Only when a file becomes ac- tive can data within be referenced. There are two reasons for this. First, for efficiency active files are identified by number, "eference to different active files requires only a table index to ?et the address of the file instead of the comparison of text strings. Furthermore, less data is required in the program to specify the file. At present there can be at most eight active files, each identified by a number between zero and seven. The second reason for two types of files has to do with the internal storage. A non-active file is continuous and in the proper sequence. '\ctive files, however, are paginated. They exist in segments which nay be scattered in randon order throughout the file. This fact is an implementation feature of the machine and is transparent to the language and programmer. The reason for the pagination scheme is that space within the file is very often inserted or deleted as ELOCT* 19 Displacement count to end of bloc!' Block identifyin g number Current entry number Current text line number Tunl •er of information w ords per entry Ilumber of X-Y quads per entry DY DX Entry 1 Fntry 2 firuro 4 FILE Current block numb er Block T_ Block i lpure j 20 substructures are appended, deleted, created, etc. Without this scheme the remainder of the file would have to be shifted either up or down and for long files, this could be a very expensive process. Non-active files can be made active using the FLOAD instruction which copies the named file into an active file. Similarly, active files can be made non-active using the FSAVE instruction which copies the current active file into the named file. (In the l'DP-11 implementation of the hypothet- ical machine, file names are standard UNIX pathnames.) The identification and access methods of substructure elements have been treated lightly thus far. As stated, active files are identi- fied by number. All other substructures, blocks, entries, text lines, information words, etc. are identified also by number. Blocks are as- signed an identifying number at the creation of the block. Any sixteen-bit number is allowable as long as it is unique with respect to the existing blocks in the file. All other substructures are identified by position. The first entry in a block is entry one; the first text line in an entry is line number one; etc. If a structure is inserted or deleted within a list of structures, the identifying number of all fol- lowing structures change by one. A necessary concept in the use of active files is that of "current structure number". Data within files exists at a number of levels and to reference a particular element it is necessary to specify the element and all higher level structures. Access to data in the file has been greatly simplified with the use of current structure numbers in the block and file heads and the current active file register, reference to an element pertains to the particular element which is in the "current" higher level structures. For example, the instruction LDW 1 21 (load first information word) loads the information word from the current entry, in the current block in the current active file. The particular structure considered current can be changed explicitly by in- struction such as SETBN, which sets the current block number, or implic- itly as a consequence of an instruction. For example APPTL, which appends a text line to the current entry, sets the current text line number in the block head to the number of the new text line. An additional feature of the "current" structure is that the current block number, entry number and text line number are stored in the block and file heads. This means that if one switches between active files or blocks, the lower level current structure numbers do not have to be reset to refer to the same data structures. 22 3. 10 AND PROCEDURE INVOCATION STRUCTURE Unlike most programming situations, the interactive graphics programmer, who is interfacing a human being to some computer aided task, is confronted with input of a highly non-deterministic nature. In fact the graphics system should encourage the spontaneity of the input, for constraining the user will only stifle creativity. Tn an environ- ment such as this there are two ma-jor problems associated with input: control and buffering. Program control deals with the response of the program to input and its future consequences. Newman [1969] presents the state machine representation of interaction control. Interaction is thought of as state transitions in which the type and source of input determine the next state and corresponding action. Figure 6 demonstrates a state di- agram of a simple graphical operation. ^.Tiile the state machine is an excellent conceptual tool, it suffers from two practical draw backs. First, as the task becomes more complex and the number of allowable in- puts increase, the total number of states and transitions increase very rapidly. Secondly, although a number of functions may be common to several sections, in the present form the state diagram is not suited to the concept of subroutines. Related to the first problem of control is that of input buffer- ing and the handling of undesired or unexpected data. Typical graphics systems are, of course, interfaced to at least one user's terminal and very often are linked to remote computers which handle the analysis of the user's input. If the remote analysis is run through batch, the graphics system programmer may have little control over when the output 23 State Diagram JOY STICK HIT JOY STICK HIT MOVE CURSOR TEXT figure f>. 24 arrives or at what rate. The machine is intended for low cost system* generally lacking large amounts of space for buffering. Therefore, the strategy of simply buffering input until required by the program is not a wise choice. The low buffer space dictates that the input is dealt with quickly and not allowed to amass in large queues. The aforesaid problems of interaction, that of control and buf- fering, have been given considerable weight in the design input of the hypothetical machine. A tenable solution has been reached by integrat- ing input response into the procedure invocation structure. The ap- proach adds structure to program control and allows for "scoping" of in- put response. That is to say, a particular input response is inherited by invoked procedures and will remain in effect until a new response is indicated or control returns to a higher level. Central to the mechanism is the WAIT instruction which suspends execution and waits for input. The assembler form of the instruction is: WAIT , where is a device mnemonic such as DTIMER for timer input or DCONTX for text input from the user's console. These mnemonics correspond to logical devices. Actual physical devices may be divided by input types into several logical devices. For example, the console is one physical device but it has been divided into two logical devices, the joy stick and keyboard. (It is shown later that the joy stick is given special status and can be further divided into many logical sub- devices determined by the current grid.) Sixteen bits of the UAIT instruction, collectively termed the device word, are used to indicate which logical devices have been 25 specified in the WAIT instruction. Each logical device is assigned a device number and is permanently associated with one of the bit posi- tions. During assembly of the WAIT instruction, bits corresponding to the listed device mnemonics are set in the device word of the instruc- tion. At run-time the UAIT instruction suspends execution until the machine receives input. Once input is received, the WAIT instruction takes one of two actions. If the bit corresponding to the input is set, the number of the device is loaded on the stack and control resumes at the following instruction. If, however, the corresponding device bit is clear, a RETURN instruction is simulated transfering control to the first instruction following the last procedure call. In both cases, the input remains "pending" and continues as such until the input is either explicitly accepted, using the appropriate receive instruction, or flushed using the FLUSH instruction. WMT's encountered during execu- tion while the input is pending treat the input as before — either simu- lating a return or continuing with the first instruction after the UAIT. The joy stick device features added capabilities. Specific grid numbers can be listed with the device mnemonic to indicate which areas of the screen are to be accepted by the WAIT instruction. If joy stick input does not lie in one of the specified grid areas, the WAIT behaves as in instances where the device is not specified for the input and con- sequently simulates a RETURN. Figure 7 demonstrates good programming style and effective use of the WAIT instruction. A powerful consequence of the simulated RETURN following unspecified input at a WAIT statement is that the programmer need only concentrate on the input which directly relates to the current process. Unexpected or erroneous input can be handled automatically by Illustration of tb<- 7I'J instruction nroce< lure l.inese r '() londi initf load! 1 loadi load! 1 Inltb set^rd x(0,5 loop: Wfl i t dcon j pop 1 revcon j s tstp,rd move • *- pop hrtble loon, /* Initialize active Pile 1 /* load block i" of block to be crt /* Initialize bloc! with info vol /* ..and 1 xy quad per entry /•'•• Lnitilize block x(0, 500, 1024) y(0,50,r;on) /* wait for any jnv stick imut / : ' : pop device number /* receive x L y coords of is hit /* compare icy pair on strck with current prid /'•'•' novo prid nun! or down two levels /* pop top two levels fro-' the stack >n, /* use grid number returned from tstgrd add, del / ; ' : ..to branch throu"h table add: calll adline() br loop del: calli deline() br loop /* The following orocedure accepts nnirs of jov stick, hits in grid /* areas 1 and 2 and enters these as t line segment in a new entry. /* Any joy stick hit outside of prid areas 1 or 2 returns control / : ' : to the calling nrocedurc. procedure adline() adll: wait dconis(l,2) /* wait for innut in areas 1 and 2 pop 1 /* remove device numb er revcon-js /* receive -joy stick, coordinates wait dconjs(l,2) /* wait for input in areas 1 and 2 pop 1 revcon js appe /* append cntrv in current block stq 1 /* store coords of line segment in quad area stq 2 /* ..of new entry in the following order: stq 3 /* y2, x2, yl, xl Stq 4 dispe /* disnlay current entry br adll /* continue accepting joy stick pairs in /* prid areas 1 and 2. fipure 7. 27 procedures at higher levels. The program segment in figure 7 demon- strates this ability. Basically, the segment allows the user to add and delete line segments from active file zero. (Only the add routine has been included in the example.) The particular function is chosen by joy sticking either of two areas at the bottom of the screen. The areas of the screen are determined by the SETGRD instruction and illustrated in figure 8. A joy stick hit in area three (lower left) choses the add segment function. A joy stick hit in areas one and two are accepted by the procedure but have no effect. Once in the add line segment mode, consecutive pairs of joy stick hits in the upper areas of the screen (grid areas 1 and 2) are interpreted as line segment endpoints and are added to the active file in the form of an x-y quad. Joy stick hits outside of areas one and two return control back to the statement after the call which branches to the label "loop". The WAIT statement at "loop" accepts all joy stick input which is then checked against the grid. This allows the user to switch between the add and delete func- tions simply by joy sticking the appropriate function. Notice in the procedure "adline" that the first of each pair of joy stick hits is stored on the stack and that an entry is not appended to the current block until the second hit is received. A good programming technique is to store all intermediate input in the stack or text buffer and to leave the data structure unchanged until the input sequence is complete. This insures the integrity of the data structure in the event of erroneous or unexpected input. A side effect of the simulated RETURN is that inter- mediate data can be lost (in fact a certainty if the data is stored in local stack variables). In most instances, the loss of input is not serious, however, because the input sequence is usually very short and ;creen Partitioning With SETORD V. ('), 0) 2, 1024) Y(Q,' , 800 50 500 1000 figure 3. 29 little effort is wasted. In situations where the loss of input may be irritating to the user, the intermediate input can be saved by storing the information in global variables or in stack variables defined in sufficiently higher level procedures. For example, the procedure "adline" could be called with two parameters used to store the coordi- nates of the first joy stick hit. In this way the input is stored in a stack level accessible in the procedure "lineseg" and can be recovered in the event of erroneous input. 3.1 The Display and Related Instructions The display instructions place pictorial information in the form of line segments and text lines on the screen. All but one of the in- structions are used to display specific file structure types. The remaining instruction is used to display text which is in the text buf- fer or in the instruction space. The screen is a storage tube type which means that data cannot be selectively removed from it. The screen must be entirely erased with the ERASE instruction and redrawn if any item in the display is to be moved or deleted. However, information can be added to the screen at any time simply by displaying the information. The computer displays presently in use have a screen size of 1024 by 780 in the x and y directions respectively. The origin is in the lower left hand corner of the display. 3.2 Screen Coordinate Related Instructions Coordinate processing is given the same emphasis as text proces- sing in the machine. User input is by far the most common input, and therefore, it is natural to place special importance in these processing capabilities. Moat of the instructions in this section are self ex- planatory. However, the grid instructions which have been touched on briefly command further attention. The SETCRD instruction partitions the screen into areas. The partition or grid is defined by lists of x and y coordinates which divide the screen in the horizontal and vertical directions. The bounded rectangular areas are assigned consecutive grid numbers beginning with one in the upper left most area and proceeding left to ripht, top to bottom. Unbounded regions, those outside all specified ordinates, are assigned grid number zero. A minimum of two coordinates in each axis are required to specify a bounded region, nevertheless, if no coordi- nates are specified for one of the axis, the machine interpretes this as bounding the entire axis. Figure 8 illustrates the grid defined by in- struction: SETCRD x(0, 512, 1024) y(0,50,800) As mentioned earlier with regard to procedure invocation, a grid can be defined at any time in the program and is defined across all procedure calls. Called procedures inherit the grid of the calling procedure and any changes made to the grid in the called procedure do not affect those at higher levels. 31 4. DEBUGGING FACILITIES The pdp-11 implementation of the machine contains a number of powerful debugging instructions. These instructions have the capabili- ties of tracing program execution, dumping the current active file, and listing the console vector which contains the data stack, subroutine stack, text buffer, program counter, stack pointer, active file number, etc. The output from these debugging instructions is entered in a rum time file named "glog" which is created in the user's working directory at the initialization of the program. 5. IMPLEMENTATION 5.1 GIMLI--CIML Interpreter OIMLI is a pdp-11 implementation of the GIML hypothetical machine. The program is coded in the C programming language and execu- tes under the Bell Laboratory time-sharing system UNIX. The implementa- tion features fast response time, comprehensive diagnostics, efficient data structure management, extensive debugging facilities for GIML pro- grams, and a run-time log file, High transportability of the program has been achieved by employing only standard UNIX systems calls. Core requirements vary with the allotment of buffer space and optional GIML program debugging facilities. The current configuration which allows for two active file structures to be in core requires under AOK bytes. A minimal program providing space in core for one active file structure and incorporating only a few debugging aids requires 25K bytes. While execution speed is program dependent, it should be noted that the major GI?!L program now in use is interpreted three to five times faster in the former case in which space is provided for two ac- tive file structures. If in the future GIML programs frequently ref- erence three or more active files in tight loops, then the trade off between more buffer space and less disk 10 should be considered. Most of the program code is a straight foreward implementation of the GIML instruction set and does not require elaboration. Two areas of the program are not reflected in the language description and neces- sitate additional discussion. These areas are active file management and input handling. 33 5.1.1 Active File Management Central to the hypothetical machine are the active files. To the CxIML instruction set, these data structures appear as compact linear aggregations of smaller substructures. These files are word addressable and have a maximum file size of 65K words. Due to the large file size and the fact that substructures are often inserted or deleted, active files are not stored on disk in a linear compact form; rather the active files are stored in pages which need not be full nor in sequence. Fach of the eight active files are stored in a paginated scheme on disk in eight of nine distinct UNIX files named "ACTFILA", "ACTFILB", etc. The additional UNIX file is necessary when the number of pages used to contain an active file reaches a maximum and the file is "compressed" into a new file. The correspondence between the active file number and the name of the UNIX file is contained in an array of pointers, "afnp", to the file names. A pointer to the unused UNIX file name is contained in "af freename". A short digression about the UNIX filing system is in order. UNIX files are stored on disk in block of 256 words. A number of system calls are available which allow for efficient access to the blocks such as seeking, reading, and writing. For this reason, the page size used to store segments of the active files is one block. The UNIX files containing the active files consist of two parts. The first part is a fixed number of blocks at the beginning of the file (currently 2) termed the file header. The second part extends to the end of the file and contains the pages of the active file. The rl ace ~ ment of the pages and the number of words used in each page is determined from a doubly linked list "11 1st" In the file header. The physical location of each element in the list determines the correspond- ing block in the UNIX file. The placement of the pages or blocks In the active file is given by the orderinp of the elements in the list. The first element in the list, element 0, is used to head the list of pages contained in the file. In the course of operation on a file, blocks or pages are occasionally freed. Since the UNIX file system lias no provision for returning blocks, the link list element of a freed block is inserted at the beginning of a free block list. The pointer to the first element in this list is "freelist" in the file header. Ini- tially, all of the elements in the list are linked in the free list. V.Tienever a new page is required by the active file, the first pap.e in the free list is used. Also contained in the file head are pointers into the "current" structures in the file. These pointers, "bp", "en", and "tp", contain the displacement in words from the start of the file to the current block, current entry, and current text line respectively. These point- ers are transparent to the GI>fL language and are used internally for efficient seeking to the current structures. The flag word "pokflgs" also in the header indicates whether or not the displacement in each pointer is valid. As stated, an active file can be as large as 65K words. If a file of this length were compact, which is to say if it had no unused words per page, then the file would fill 256 pages. However, the paging scheme is designed for non-compact storage of files and for this reason, a maximum of "TOTBLKS" pages can be used to store the active file. The routine "compress" is used whenever the number of blocks approaches the 35 limit of "TOTBLKS". The routine compacts the active file into a minimum number of blocks and ad-justs the link lists accordingly. When an active file is in core, it is in a structure referred to as "actfilh". The number of files which can be in core is determined by "NUMAFIC". At present two active files can be in core. The active file structure "actfilh" can be divided into three parts. The first section contains the active file header which includes the variables from "fleng" through "Hist". The second section, "rafbuf" is a 768 word ar- ray used to buffer segments of the active file. Whenever a location in an active file is referenced, the page containing the location, if not already present in this buffer, is' read into it fron disk. The third section of the active file structure is the collection of variables relating to the active file as it is in core. The variable "lastref" is utilized when a new file must be brought into core. The structure which is to contain the new file is the one which has not been referenced in the longest period. By comparing the differences of the current access number in "currefnum" and the values in "lastref", the structure satisfying this criterion is determined. The two variables "afhrtodf lg" and "locmodflg" indicate modification of either the file header or the file segment contained in "rafbuf". The remaining varia- bles in the third section, "fp2", "dispfpl", "dispfp2", "sblock", and "eblock" relate to the portion of the file contained in the buffer "rafbuf". The portion of the file is always front justified in the buf- fer and if more than one page is in core the data is in sequence. The variable "dispfpl" is the displacement from the start of the active file to the first word of the segment in core. "dispfp2" contains the displacement of the last word in core plus one. T'ages appended to the se^nent art- read into the I uffer at "fp2" which poi the last word in the •. The variables "sbb limit the strlnp of pages read into core "eblocl:" the m last page i-n core while "sbloe!'" refers to ti i si one In core. Pccall tliat element zero in tl>e Linl List Is u?.- head of the 1 if; t and dons not correspond Lo an actual '■.-■• . T f the first page of the file is in core, "abloc!;" contains t preceding page which ie element zero, tlie head of I . hence the scheme works out nicely because there arp no speci. -1 ! cases involved in moving pointers about the list. The strategy for reading and writing pages into core is as fol- lows* If the segment in the buffer has been nod if led and therefore, must be written to disk, the pages after "si loci" up to and including "eb]ocb" are prepended to the free pare list. Then commencing at t start of the servient, a page is allocate! fror the free list and data from the segment is written to the page. The process is repeated Boring down through core and allocating new pages until all data In the. segment has been saved en disk, L'otice that if less pages on lis) were required for the segment than were between "si loch" and "elded", the surplus pages are in the free linl list since the pages were trans fered to the free list before page allocation began. If a wore at a given displace- ment is references and the displacement lies before the segment (i.e., d.isp < dispfpl), then if the section in core has been modified, it is written to disk. The link list is traversed backwards from "sblock" to find the page which contains the desired displacement. The page is then read into core and the variables "dispfpl", "dispfp2", etc. are adjusted accordingly. A the desired displacement lies at or after the segment 37 in core, the link list is traversed forevard from "eblock" to find the page containing the displacement. If the paces from "eblock" through this page can fit in the buffer, then the pages are appended in "rafbuf" and the variables "eblock", "dispfp2", and "fp2" are adjusted. If the pages cannot be accommodated, the section in core, if modified, is writ- ten to disk and the new page is read into core. The strategy for inserting and deleting space in an active file is geared toward mimimizing disk 10. The first word following the space to be inserted or deleted is established in core. In almost all cases space can be inserted or deleted simply by perturbing the segment in core and possibly the page lengths in the link list. Deleting large amounts of space may result in the transfer of pages into the free list. The only instance where disk 10 need be performed is when the amount of space to insert is greater than the unused buffer space. To state the process simply, the data following the location of the inserted space is written to disk in one or more pages. If still more space is necessary, pages are inserted in the link list until the sum of the space in the buffer plus the inserted space in the pages on disk equals the required total. The algorithm is designed to maximize the amount of space that will be in core at the conclusion and minimize the number of inserted pages. For example, suppose "rafbuf" contains a segment 578 words long as in figure 9a and 400 words are to be inserted before the word at displacement 1488 in the file. A new page is allocated and inserted im- mediately after "eblock" in the link list. The 90 words in the buffer following the inserted space and 130 preceding "garbage" words are writ- ten to the newly inserted page (figure 9b). The "garbage" words are in fact part of the file but have no consequence on disk. The length of EBLCCK RAFBUF —— 7—— — i-SiS?i!:?SS : 768 INSERT BEFORE THIS POINT fi'Mire "n, EB ""*■ — "V""" 1 LOCK * INSERTED SPACE RAFBUF 1 .1 l.f .VAVtViViYri'hl.l.'.Vi NSERTED SPACE 270 figure 9b. 39 the new page is set to 210 in the link list element corresponding to the page and the variables "fp2" and "dispfp2" are adjusted to the end of the buffer. 5.1.2 Input Handling The machine WAIT instruction suspends execution and waits for input from any of the logical devices such as the joy stick, timer, or keyboard. UNIX, however, does not have a standard system call which in- dicates that input is pending. The only test for input is to issue a read for a specific device. Unfortunately, the read does not return un- til the number of requested bytes has been read. The solution to the problem stems from the forking and waiting capabilities of UNIX programs. Briefly, the system "fork" call splits execution into the current program or "parent process" and a new program termed the "child process". The child process is a copy of the parent program and inherits the ability to access all previously opened files. Another system call, "wait", suspends execution until one of the child processes ends execution, or in UNIX terms "dies". The hypothetical machine FAIT mechanism is implemented by having the child processes read the physical devices; save the input in the communication file "gimlin- put"; and finally die using the "exit" system call. When the parent process encounters a CIML wait instruction, it calls the system "wait" routine. Control returns to the parent when one of the child processes has died indicating that some type of input has been received. The log- ical device number of the input is passed to the parent process in the high order byte of the exit status of the child process. Each physical device excluding the timer is associated with one block in the file "giml Input". All comnuni ca t Jon to the parent from a child process is entered in the associated blocV. 'r <— <~ip]e, the user's console is associated with the first block in the file. Input in the form of text lines and 1oy stick hits are nlaced in the block which can then be read by the parent process when the input is to be received. Once input for a particular device has been received, a new child proc- ess Is forked which re-Issues a read for the particular device. The timer is handled in a somewhat different maner. A child process is forked off when the GIML instruction SF.TT'IER is encountered instead of when the input is received. 5 . 2 CAS ~ r,IML Assembler GAS is an assembler for the GIML programming language. The as- sembler is coded in the C programming language and executes under the Bell Laboratory time-sharing system UNIX. The table driven assembler features comprehensive diagnostics, efficient one pass scanning, automat- ic subroutine parameter linkage, stack level monitoring, automatic gen- eration of loads for constants and an optional listing. The design ob- jective of the assembler has been to maximize symbolic representation and free the programmer from the bookkeeping normally associated with a stack machine. 5.2.1 Forward References GAS is a one pass assembler and as such examines the source code only once from start to finish. Stack variables must be defined prior to use and pose little difficulty. Labels and procedures on the other hand can be referenced before they are defined and require special 41 provisions. At initialization the assembler creates the file "gas.ltmp" which is used to list all forward references to labels and procedures. Each reference is stored as a triplet. The first word contains the ad- dress of the label or procedure in the object file. The second contains a pointer to the symbol table entry of the label or procedure (A symbol table entry is created for either symbol at the first encounter of the identifier in the source code). The third word contains a one or a two depending on the type of address reference, A one indicates an eight bit relative offset while a two indicates a sixteen bit absolute ad- dress. At the conclusion of pass one the forward address reference list is traversed from the beginning filling in the appropriate address fields in the object file. If the label or procedure is never defined in the course of a program, an error message is produced giving the ad- dress of the reference and the indentifier name. The eight bit relative address can reference up to 127 locations forward. If any eight bit ref- erence is found to be beyond this range, a suitable error message is produced. 5.2.2 Symbol Table The symbol table is used to store all C.IML Instructions, assem- bler directives in the form of symbols, stack variables, labels, and procedure identifiers. The information stored in the symbol table varies slightly from type to type. The invarient elements in each sym- bol table entry are: char name [10] int type int *front int *back int hashv int chain The variable "name" contains the character string representation of t symbol. The name is padded with a zero and only the fir6t nine- charac- ters are stored in the table. The "type" variable contains the symbol table type. The eight possible types are MNEMONIC (instruction mnemon- ic), GLOBLSTKOP (global stack variable), LOCALSTKOP (local stack varia- ble), PARMSTKOP (formal parameter), PROC_DEF (defined procedure identi- fier), PROCJ.'DFF (undefined procedure identifier), LAB_ r ;FF (defined label), and LABJ'DF.r (undefined label). The symbol table is based on a hashing scheme which produces a seven bit integer from the name. The integer is used to index into an array of pointers termed "buckets" which point to linked lists of symbol table entries. All entries which hash to a particular index are linked in these doubly linked lists using the pointer variables "front" and "back". The "back" pointer of the first entry in each list and the "front" pointer of the last entry in each list are zero. "hashv" con- tains the hash value associated with the entry. The hash value is necessary when deleting the last entry in a list because the hash table array entry or bucket must be zeroed to indicate an empty list. The "chain" variable is used to link all variables which are to be removed from the symbol table at the end of the current procedure. Local stack variables, formal parameters, and labels are local to a procedure. By creating an entry with the attribute "LOCALSCOPF", the symbol table en- try is linked with all other local variables. Mien a procedure declara- tion is encountered, all entries in the local scope chain are removed fron the hash table lists. The "LOCALSCOPE" stack variable entries are returned to the entry list; however, the entries for labels are simply left unattached. The symbol table entries for labels are required A3 during the forward reference pass. Recall that one of the three varia- bles in the forward address entry contains a pointer to the symbol table entry. The symbol table entries for the permanent symbols, those with the type MNEMONIC, employ three variables in addition to the common ones already discussed. The three variables "s_val", "s_deltastk", and "s_class" are initialized from the permanent symbol file "/usr/giml/instr. tab" at the commencement of the assembler. The varia- bles contain the instruction opcode, the effect of the instruction on the stack, and the parse class. Currently, the instructions and assem- bler directives are divided into twenty-three parse classes. A few of the GIML instructions comprise the entire class such as the WAIT in- struction. A new instruction can be added to the assembler simply by adding the mnemonic, opcode, parse class, and stack level change. If the new instruction differs in syntax from all existing instructions, a new parse class must be created and a corresponding syntax analyzer ad- ded to the "encode" routine. The symbol table entries for stack variables employ only one ad- ditional variable, "s_val", which contains the stack level associated with the identifier. The "type" variable in the entry contains the stack variable type which is either "CLOBALSTKOP", "LOCALSTKOP", or "PARSTKOP" . The symbol table entries for labels use three additional varia- bles "l_val", "l_stklev", and "l_lstfound". At the first instance of a label in the source, either as a label prefix or as a reference, an en- try is created with "1 stklev" containing the current value of the stack level and "l_lstfound" containing the current program address. If the label is encountered as a stntenent prefix (i.e., with a colon at the end of the identifier), the entry Is assigned the type "LAB DBF* and "l_val" is set to the current program address. Alternatively, the entry is assigned the type "I^.B_UDr.F". Synbol table entries for procedure identifiers use only one ad- ditional variable "l_val" which contains the address of the procedure. At the first instance of a procedure identifier in the source, an entry is created with the "OLOBALSCOPr" attribute. The "type" variable is as- signed "PROC_DEF" if the identifier is encountered in a procedure dec- laration. 5.2.3 Synbol Table *Uin Tine Data The macro "NENTRIES" determines the maximum number of entries in the symbol table. At present "NENTRIES" is 500. The symbol table must be large enough to contain all permanent symbols (about 1^5), all labels and procedures, all global symbols, and a varying number of local stack variables. The hashing scheme is independent of the sparseness of the symbol table so that increasing the symbol table size will not affect execution speed. The assembler has been equiped with the "-data" option which produces a summary of the symbol table run time data. A typical large program (over 3000 lines) produced the following data: Maximum number of entries: 385 Max hash table array usage: 109/123 Average number of compares/ lookups: 1.605 The results indicate that the current hash function and symbol table size of 500 are quite good for this typical program. If the average number of compares per lookup becomes much greater, say 2.5, I suggest 45 that the hash function be modified to return eight bits and the number of hash table buckets be extended from the current 128 to 256. 5.2.4 Perspectives for Development Full macro capabilities have not been realized in the assembler. The original intent was to use the macro preprocessor available in UNIX. The preprocessor is usable although, it has a very unfavorable visual impact on the listing. A macro processor could be built into the scan- ning section of the assembler which would have minimal side effects on the remainder of the assembler. 46 LIFT OF R] [1] Ratadorf, ". J, "FLINC— a ^ORTRAM Language for Interact • a- phics", Numerical and Computer Methods In Civil Lngl nee ring , Acadcnlc Press, 'lev Yorl , pp. 513-542, 1071. [2] Bergman, F. "RCRAF2: A real-tine graphics language with nodular objects and Implicit dynamics, " Proc . flCCRAP ' 76, funner, 1976, [3] Roullicr, P., Cros J,, Jancenc P., Lenaire A. "META.VISU, A General Purpose Graphic System," Proceedings of the ITIP ' 'orl.ln ^ Conference on Graphic Languages , pp. 244-267, 1972. [A] Kasik, D. J. "Controlling User Interaction," Proc . FIGGRAPli '76, 10, //2, pp. 109-U5, 1976. [5] Martin, J. DESIGN OF MAN COMPUTER DIALOGUES, Prentice Fall Inc., Hew Jersey, 1973. [6] Miller, R. B, "Response Time in Man Computer Conversational Tran- sactions," AT£IPS_ C^nj[£renc£ ProjccedJjTj^, Fall 1963 , vol. 2, Thomp- son Rook Company, Washington D,C. f pp. 267-277, 196R, [7] Newman, V T . M. "A High Revel Programming System for ?e:note Tine- shared Graphics Terminal," Pertinent Concepts in Computer Graphics , Univeristy of Illinois Press, Urbana, Illinois, pp. 200-223, 1969. [8] Newman, W. H, "Display Procedures," Comm. ACM , 14. #10, pp. 651-660, 1971. 47 Instruction Synopsis Appendix A Stack Instructions: load load stacl' variable on top of stack loadi load inmcdiate (load constant on top of stack) move(p) move top of stack Into stack variable (and poo stack; or bitwise or and bitwise and add two's complement add cmp compare and push a -1 , or 1 ashift arithmetic shift cshift circular shift neg two's complement nepation com bitwise complement pop pop levels from stack push push lovels onto stack Control Transfer Instructions: br(p) uncond i beq(p) brand) bne(p) branch bge(p) branch bgt(p) branch ble(p) branch blt(p) branch imp uncondi jmptble j ump in ibrz increme dbrz decreme testbr test an tional branch (and nop stack) if equal to zero (an^ nop stack) not equal to zero (and pop stack) greater than or equal to zero (and pop stack) preater than zero (and pop stack) less than or equal to zero (and pop stacl.) less than zero (and pop stack) tional /jump (anywhere in current procedure) directy throuph an address table nt and branch on zero nt and branch on zero d branch if equal Text P.uffer Instructions: tbappc append character to text buffer tbanpt append text string to text buffer tbinsc insert character in text buffer tbinst insert text string in text buffer tbdelc delete character in text buffer tbdelt delete text in text buffer tbchnpc change character in text buffer tbpshc push character in text buffer onto stack. tbemn compare text string with string in text buffer tsearch search text buffer for a character string tbcnvo convert value to an octal character representation tbcnvd convert value to a decimal character representation tbinit initialize text buffer to a null string tbmpl move text pointer pi tbmp2 move text pointer p2 tbldpl load value of text pointer pi on stack tbldp2 load value of text pointer p2 on stack 49 thldln load number of characters in text buffer on stack tbstpl set value of text pointer pi tbstp2 set value of text pointer p2 File Management Instructions: fload load file with given name into current active file fsave save active file under given nane fdel delete file with given nane setfn make active file current setbn make block current seten make entry current settln make text line current Idfn load current active file number ldbn load current block number lden load current entry number ldtln load current text line number ldlsten load last entry number ldlsttn load last text line number initf initialize active file to empty initb initialize block delb delete current block appe append entry to current block inse insert an entry before current entry dele delete current entry apptl append text line to current entry instl insert text line before current text line chngl change current text line dell delete current text line setdy set dy displacement of block setdx set dx displacement of block lddy load dy displacement of block lddx load dx displacemente of block setxyt set xy coordinates of text in entry ldxyt load xy coordinates of text in entry stq store xy quad word in current entry stw store information word in current entry ldq load xy quad word from current entry Idw load information word from current entry display Instructions: dispf display current active file dispb display current block dispe display current entry disptl display current text line dispq display xy quad flisptxt display text erase erase screen Procedure Invocation and Return Instructions: calli call internal (procedure within current program) calle call external (procedure outside of current program) return return from a procedure fcreen Coordinate Related Instructions: poseurs load position registers for console text input Idjsn load joy stick function button number setgrd partition the screen into numbered r»rid areas tstgrd calculated grid number of coordinates fror current grid tscanxy scan current entry for text containing coordinates ldcn load character number of coordinates from tscanxy 10 Related Instructions: wait wait setimer arm revtimer rece revcontx rece revconjs rece sndcsotx send sndcsof i send revesotx rece revesof i rece revesoip rece snd732tx send snd732fi send rcv732tx rece rcv732fi rece rcv732ip rece for input timer interrupt ive tiir.er input (interrupt) ive text line input from console ive -joy stick input from console text line to IEM360 file to IB»I360 ive text line from I3M360 ive file from IBM360 ive interpreter program from IB?-f360 text line to Interdata 7/32 file to Interdata 7/32 ive text line input from Interdata 7/32 ive file input from Interdata 7/32 ive interpreter program from Interdata 7/32 Debugging Instructions: traceon turn program trace facility on traceoff turn program trace facility off dumpaf dump current active file dumpcv dump console vector containing both stacks, pc, sp, etc. 51 Assenbler Directives: procedure procedure declaration dclloc local variable declaration and initialization id = local variable equate dclglob global variable declaration allocglobs allocate space for global variables . = set stack level pseudo op Instruction Opcodes and Assenbler Formats Apnendix B 53 The following is a summary of the OIML instruction set. Opcodes are listed in octal. The initialization file for the GAS assembler can be formed from this table by removing lines containing the second occurance of a mnemonic and deleting the last two columns and head- ings. Key to symbols: s stack level expression if integer (can be signed) 1 label p procedure name a formal parameter identifier dev device mnemonic "text" any text string tl length of text (if of characters + 1) ope mnemon stack parse instr assembler change class length fornat 004 load +1 25 Z load s 006 loadi +1 2 loadi if 007 loadi +1 3 loadi ii 010 rriove 2 2 move s Oil movep -1 2 2 movep s 012 or n 2 or s 013 or -1 2 1 or 014 and n 2 and s 015 and -1 2 1 and 016 add 2 2 add s 017 add -1 2 1 add 020 emp +1 2 2 emp s 021 emp 2 1 emp 022 ibrz 4 4 ibrz s, 1 023 dbrz 4 4 dbrz s, 1 024 ashif t 3 2 ashift if 025 ashift -1 3 1 ashift 026 cshif t 3 cshif t It It 027 cshif t -1 3 1 cshift 030 pop -if Q 2 pop if 032 push if 9 2 push u 034 tbappt 5 1+tl tbappt "text" 035 tbappt 5 1 tbappt 036 tbinst 5 1-1- Cl tbinst "text" 037 tbinst 5 1 tbinst 040 tbemp +1 5 1+tl tbemp "text" 041 tbemp +1 5 1 tbemp 042 tbmpl 3 2 tbmpl if 043 tbmpl -1 3 1 tbmpl 044 tbmp2 3 2 tbmp2 if ope mnemon stack parse lnstr assemb! Ler change class length ia t 045 tbmp2 -1 3 1 tbmp2 046 tsearch 12 3+tl tsearch "text", 1 047 tsearch 12 3 tsearch 050 tscanxy 24 3 tscanxy 054 br 20 2 br 055 brp -1 20 2 brp 056 beq 2 beq 057 beqp -1 2 beq o60 bne 2 bne 061 bnep -1 2 bnep 062 bp,e 2 bge 063 bgep -1 2 bgep 064 bgt 2 b;-,t 065 bgtp -1 2 bgtp 066 ble 2 ble 067 blep -] 2 blep 070 bit 2 bit 071 bltp -1 2 bltp 072 ,1™P 3 Jmp 074 jmptble -1 17 2+2*n jmptble 11,12, ...,ln 076 testbr -1 11 4 testbr *, 1 100 wait +1 10 4+n/8 wait devl,dev2 ^s(l,4,..,n) 102 traceof f 1 traceof i 103 traceon 1 traceon 104 dumpaf 1 rhippaf 106 dumpcv 1 dumpcv 112 setgrd 13 3+2* (m+n) setgrd x(xl ,x2, . .xn) y(yl,...ym) 114 calll -n 14 4 calli p(al,a2, . . . ,an) 116 calle -n 15 4+tl calle "text"(al,a2,...ar), 1 117 calle -n 15 4 calle (al,a2, . . .an) , 1 120 return 21 1 return 122 stq -1 8 2 stq t 123 stq -2 8 1 stq 124 stw -1 8 2 stw fi 125 stw _o 3 1 stw 126 ldq +1 8 2 ldq § 127 ldq 3 1 ldq 130 ldw +1 8 2 ldw // 131 ldw 8 1 ldw 134 neg 1 1 neg 136 com 1 1 com 140 tbinit 1 1 tbinit 142 tbpshc +1 1 1 tbpshc 144 tbinsc -1 1 1 tbinsc 146 tbdelc 1 1 tbdelc 150 tbehnge -1 1 1 tbehnge ope mnemon stack parse instr assembler change class length format 55 152 tbappc +] 1 1 154 tbdelt 1 1 156 tbcnvo -1 1 1 160 tbcnvd -1 1 1 162 tbldpl +1 1 1 164 tbldp2 +1 1 1 166 tbldln +1 1 1 170 tbstpl -1 1 1 172 tbstp2 -1 1 1 176 setfn -1 1 1 200 ldfn +1 1 1 202 initf -1 1 1 204 setbn -] 1 1 206 ldbn +1 1 1 210 initb -3 1 1 212 delb 1 1 214 lddy +1 1 1 216 lddx +1 1 1 220 setdy -1 1 1 222 setdx -1 1 1 224 seten -1 1 1 226 lden +1 1 1 230 ldlsten +1 1 1 232 appe 1 1 234 Inse 1 1 236 dele 1 1 240 settln -1 1 1 242 Id tin +1 1 1 244 ldlsttn +1 1 1 246 apptl 1 1 250 instl 1 1 252 dell 1 1 254 chngl 1 1 256 ldxyt +2 1 1 260 setxyt -2 1 1 262 Id ] sn +1 1 1 264 ldcn +1 1 1 266 tstgrd +1 1 1 276 poseurs _2 1 1 300 dispf 1 1 302 dispb 1 1 304 dispe 1 1 306 dlspq -1 1 1 310 disptl 1 1 312 disptxt -2 5 l+t3 313 disptxt -2 5 1 314 erase 1 1 320 fload 23 3 tbappc tbdelt tbcnvo tbcnvd tbldpl tbld P 2 tbldln tbstpl tbstp2 setfn ldfn Initf setbn ldbn Initb delb lddy lddx setdy setdx seten lden Idlsen appe inse dele settln Id tin ldlsttn apptl instl dell chngl ldxyt setxyt ldjsn ldcn tstgrd poseurs dispf dispb dispe dispq disptl disptxt disptxt erase fload 'text' ope mnenon stack parse change class 322 f save 324 fdel 326 flush 330 setlmer -1 332 revtimer 334 revcontx 336 revconjs +2 340 sndcsotx 342 sndcsof 1 344 revesotx 346 revesof i 350 revesoip 352 snd732tx 354 snd732fi 356 rcv732tx 360 rcv732fi 362 rcv732ip 364 sndplltx 366 sndpllfi 370 rcvplltx 372 rcvpllf i 374 rcvpllip nstr ength assernbl er format f save fdel flush setlmer rcvtlmer revcontx revconj s sndcsotx sndcsof J revesotx revesof i rcvcsolp snd732tx snd732fi rcv732tx rcv732fi rcv7321p sndplltx sndpllfi rcvplltx rcvpllf i rcvpllip , m AEC-427 U.S. ATOMIC ENERGY COMMISSION I 6 /. 6 ?!.. UNIVERSITY-TYPE CONTRACTOR'S RECOMMENDATION FOR DISPOSITION OF SCIENTIFIC AND TECHNICAL DOCUMENT ( See Instructions on Reverse Side ) ,ECM 3201 AEC REPORT NO. COO-2383-0037 2. TITLE GIMLI AND GIML--A MACHINE AND PROGRAMMING LANGUAGE FOR LOW COST INTERACTIVE GRAPHICAL SYSTEMS TYPE OF DOCUMENT (Check one): [x] a. Scientific and technical report |~l b. Conference paper not to be published in a journal: Title of conference Date of conference Exact location of conference. Sponsoring organization □ c. Other (Specify) I. RECOMMENDED ANNOUNCEMENT AND DISTRIBUTION (Check one): lyl a. AEC's normal announcement and distribution procedures may be followed. ~2 b. Make available only within AEC and to AEC contractors and other U.S. Government agencies and their contractors. "2 c. Make no announcement or distribution. . REASON FOR RECOMMENDED RESTRICTIONS: i. SUBMITTED BY: NAME AND POSITION (Please print or type) C. W. Gear Professor and Principal Investigator Organization Department of Computer Science University of Illinois at Urbana-Champaign Urbana, IL 61801 Signature ^C&«jft-* Date April 1977 FOR AEC USE ONLY AEC CONTRACT ADMINISTRATOR'S COMMENTS, IF ANY, ON ABOVE ANNOUNCEMENT AND DISTRIBUTION RECOMMENDATION: PATENT CLEARANCE: O a. AEC patent clearance has been granted by responsible AEC patent group. LJ b. Report has been sent to responsible AEC patent group for clearance. [~l c. Patent clearance not required. "biliographic data SEET ' 1. Report No. UIUCDCS-R-77-856 f°itle and Subtitle GIMLI AND GIML A MACHINE AND PROGRAMMING LANGUAGE FOR LOW COST INTERACTIVE GRAPHICAL SYSTEMS 3. Recipient's Accession No. 5. Report Date April 1977 7Author(s) Neal M. Hennegan 8- Performing Organization Rept. No - UIUCDCS-R-77-856 performing Organization Name and Address Department of Computer Science University of Illinois Urbana, IL 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. US ERDA/EY-76-S-02-2383 1 Sponsoring Organization Name and Address Energy Research and Development Administration 9800 South Cass Avenue Argonne, IL 60439 13. Type of Report & Period Covered Thesis 14. 1 Supplementary Notes ) Abstracts The design of interactive graphics packages has proven to be a difficult and lengthy process. This paper describes in detail the programming language GIML which has been designed to facilitate the implementation of interactive graphics systems, and the program GIMLI, a pseudo machine for the language. Interaction can be thought of as state transitions in which the type and source of the input determine the next state and corresponding action. GIML reflects this process in its structure and most important, reduces the number of transitions that need be explicitly defined by incorporating the input response into the procedure invocation structure. Key Words and Document Analysis. 17o. Descriptors interactive graphics programming language scoping of input response interpreter b. Identifiers/Open-Ended Terms 'e. COSATI Field/Group I. Availability Statement unlimited 19. Security Class (This Report) UNCLASSIFIED curitv Class (Thi 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 61 22. Price 5RM NTIS-35 ( 10-70) USCOMM-DC 40329-P71 h M 1 7 m mMtMNUMHOHMOM