The Share 709 System: Machine Implementation of Symbolic Programming
E. M. Boehm, Thomas B. Steel · Journal of the ACM · 1959
As emphasized in the preceding paper, a fundamental requirement for effective utilization of high speed computing devices such as the 709 is a man-machine communication link that is at once rapid and unambiguous. Use of symbolic languages with conventional conversion techniques has resulted in reasonable initial specification of computational problems, but excess input handling has made such procedures uneconomical for the tedious corrections incumbent on the best of programmers. Also, checkout is frequently awkward, due to the inability of current systems to permit dynamic requests and responses in a language familiar to the writer. It is an objective of the system design to provide a mechanism for preservation of symbolic language communication between coder and calculator during the entire process of preparing, verifying and executing a program. Decisive in the accomplishment of this aim is recognition of a distinction between the information content of a language and the methods of encoding that language for presentation. Standard routines for translation of symbolic to absolute machine language uniformly result in information loss. This is not the case in the 709 system; only the syntax, not the semantics, are changed. Apart from mnemonic aids, the principal feature of symbolic coding is that referents and their relata maintain the same association when intervening elements are altered in number. A price is paid for this freedom as symbolic languages are uninterpretable by machine circuits without aid. A special program is required—an assembler. The principal disagreeable characteristic of an assembly program is the amount of time it occupies in execution. By attempting to minimize the frequency of reassembly, the programmer is forced to employ two languages in parallel. Logic shows that the only escape from this dilemma is to place some burden of the assembly on that program which loads codes into the machine storage for immediate execution. At once a question arises concerning the propriety of performing even a partial assembly at each machine pass. It is apparent to anyone familiar with historical assembly programs that the major time involved comes not from the internal processing but from the considerable read-in time associated with the usual methods of representing symbolic information. As this information is originally written by a human coder and then reproduced into, say, punched cards, again by a human operator, it is evidently impractical to start the process with binary encoding or some other form of compact expression. It is, however, possible to reduce this original writing to some new form of condensed encoding by computer processing and to use this form exclusively in subsequent operations. With care this can be done and not destroy the desirable features of the original representation. The basic concept in this system is a second encoding schema for the information concerning a program originally described in the symbolic language. This encoding, called the “SQUOZE encoding,” is at variance with the programmers' encoding in several respects. First, it is fundamentally binary, employing only two basic marks, while the programmer enjoys the use of 50. Secondly, the organization of information is quite different in the SQUOZE encoding. All information concerning a particular instruction occurs together in the original expression. This is not the pattern in the SQUOZE encoding. For example, the location symbols associated with the various instructions and storage cells are collected in a single, separate list. This proves to be most desirable for computational purposes when consideration is given to the special role played by such symbols. Finally, and with perhaps the most significance to the casual observer, the SQUOZE encoding is far more conservative of bits than the pseudo-English used by the programmer. It is from this phenomenon that the scheme derives its name, “SQUOZE” being a bastard past participle of the verb “to squeeze.” This condensation, which is on the order of ten to one, does not alter the functions of the system, but it does provide a considerable decrease in the time involved in processing program input, a major criterion for acceptability to those concerned with machine rentals. The critical difference from other systems inherent in the SQUOZE encoding is the retention and reorganization of information concerning symbols. It is this element that makes possible the more desirable modification and checkout procedures. Condensation does nothing more than make this sophistication cheaper and therefore more palatable. While clearly less redundant than the usual mode of expression, the SQUOZE encoding is not based on a minimum redundancy code. There are two reasons for this. In the first place, the construction of a true minimum redundancy code is not possible without precise knowledge of the probabilities of the various elements involved. Such data would be hard to come by for a programming language on an untried machine. Also, in the general case, a minimum redundancy code requires bit by bit examination for decoding. In the 709 this would require more internal processing time than would be saved on input read-in. It is evident that a compromise is necessary. A single example will suffice to illustrate the pattern of exchange between decoding time and input time. When the various macro instructions are adjoined to the actual 709 instructions, the number of operation codes which the loading program must recognize approaches 250. Allowing for later expansion, a principle that has been followed throughout the system, nine bits would be required for an elementary table description of the operation code list. Had this mechanism been adopted, only a single table lookup function would be required in the decoding program for the determination of the operation codes. If the exact frequency ranking of the operation codes were known, assuming a logarithmic distribution as a best example, approximately five and one-half bits would be the mean needed for representation of the operation codes in a minimum redundancy scheme. In this case no table lookup would be performed, but an average of five and one-half bit examinations would be essential. Evaluation of the computing and input times involved shows that the simple scheme enjoys an advantage by a factor approaching two. Additionally, in a machine with a finite high speed storage, attention must be given to the amount of program and table space needed for each procedure. Invariably the logic of present day machines favors the simpler table lookup approach. Certain improvements are possible, however. Although the precise frequencies are unknown, some a priori data are available regarding the relative probabilities for the occurrence of the various operation codes. For example, it is clear that a STORE instruction will occur more often than a REWIND TAPE instruction. By dividing the operation codes into two groups, a gain can be made. This is the procedure actually employed in the SQUOZE encoding. The operation codes representing those 32 instructions expected to be the most frequent are assigned a five bit code, while the remainder are encoded in nine. It is, of course, necessary to adjoin an additional bit to each code in order to provide an indicator for the category into which the code falls. Thus, frequent instructions require six bits for specification of their operation codes while the others demand ten. A mean of seven and one-half bits is estimated for the length of an operation code in the SQUOZE encoding. The decoding procedure for a SQUOZE operation code requires a single bit test and a table lookup. There is a slight advantage in this case over the straight table lookup. Eighteen microseconds per instruction are gained in input time at the expense of sixteen and one-half microseconds of decoding time. Clearly any more elaborate encoding would be less efficient. Talk of fractional microsecond savings may seem like woolgathering, but this time is saved on each occasion of loading an instruction into the machine. With some reasonable assumptions on the ratio of loading time to processing time, this one feature would account for some ten minutes of computer time each year. However, there are perhaps 100 such effects in the entire SQUOZE encoding and a similar number of machines involved. When translated through the rental formula, this represents some 50,000 dollars annually. For ease of discourse, the SQUOZE encoding schema will be discussed in terms of its representation on punched cards, the “SQUOZE deck.” The deck is divided logically into four parts: preface, introduction, dictionary, and text. The preface contains sundry information concerning the layout of the remainder of the deck and is utilized in allocating high speed storage effectively. The introduction contains information about those elements of the symbolic program not bearing directly on the resulting machine language code; such things as comments and data concerning which words were generated by the assembler initially as a result of library call cards and macro instructions. The dictionary is essentially a list of the location symbols encountered in the program, together with a description of the format of the cells these symbols name. The text, finally, contains the specific description of the instructions to be developed into 709 binary words and loaded into the high speed storage of the machine.