GENIE(ID:3070/gen012)Algorithmic language for the Rice R1J. Iliffe Rice University 1960 Algolish programming language, with extensibility Ran on the Rice R1, was intended to run on the Basic Language Machine (purpose built) but problems with transistor circuit pins prevented that machine being finished Work taken up again by Iliffe at ICL Stevanage in the UK in 1968 Places Related languages
References: The paper by J. Iliffe on "The Use of the GENIE System in Numerical Calculation" describes a mathematical programming language for the Rice University computer. The GENIE language bears a strong resemblance both to ALGOL and to the ADES language developed several years ago by the reviewer. GENIE has some of the best features of both languages. It also embodies some ideas not possessed by either of these systems or any other system of this kind. Perhaps the most important departure from .\LGOL is the extension of the domain of possible values assigned to the symbols in the language. Whereas in ALGOL values are limited to real, integer and Boolean, GENIE permits as additional domains of values other symbol sets and instruction sets. Thus, the value of the expression P(ll, a) could be a set of single-address machine instructions for performing the addition ~ + v. The claim is also made that analytical processes can be performed as well as numerical processes. Another feature, although not original in GENIE, is worth mentioning. This is the use of a table of codewords for assignment of storage to arrays. The use of codewords rather than the ALGOL array declarations (or the dimension statements in FORTRAN) permits a much more flexible and efficient handling of storage assignments for arrays both in the source language and in the compiler. Extract: Review The paper by R. F. Clippinger titled "FACT -- A Business- Compiler: Description and Comparison with COBOL and Commercial Translator," must be singled out as an example c(-; the kind of paper which a compendium such as this should strive to present. Clippinger's excellent paper does much more than describe the FACT system for the Honeywell 800. Avoiding the dreary style of the instruction manual which one finds in most papers on programming, Clippinger gives a well-reasoned aoJcarefully thought-out discussion of the general aspects of business data processing, shows how FACT treats each major problem area and explains the technical factors which influenced the particuls~ technique chosen. At the same time, he manages to give a good account of the details of FACT by referring to 17 exhibits placed. Extract: Extract regarding GENIE The paper by J. Iliffe on "The Use of the GENIE System in Numerical Calculation" describes a mathematical programming language for the Rice University computer. The GENIE language bears a strong resemblance both to ALGOL and to the ADES language developed several years ago by the reviewer. GENIE has some of the best features of both languages. It also embodies some ideas not possessed by either of these systems or any other system of this kind. Perhaps the most important departure from ALGOL is the extension of the domain of possible values assigned to the symbols in the language. Whereas in ALGOL values are limited to real, integer and Boolean, GENIE permits as additional domains of values other symbol sets and instruction sets. Thus, the value of the expression P(ll, a) could be a set of single-address machine instructions for performing the addition ~ + v. The claim is also made that analytical processes can be performed as well as numerical processes. Another feature, although not original in GENIE, is worth mentioning. This is the use of a table of codewords for assignment of storage to arrays. The use of codewords rather than the ALGOL array declarations (or the dimension statements in FORTRAN) permits a much more flexible and efficient handling of storage assignments for arrays both in the source language and in the compiler. 1. General Introduction The set of codes designed for interpreting formal expressions on the Rice University computer is termed the 'Genie system', or simply 'Genie'. Although most of the concepts employed therein may be applied on any machine of the type used for a decade, it is probably true that intensive exploitation of a given set of orders and logical properties influences the code designer to a greater extent than he is aware, and it is appropriate to make some initial remarks on the properties of the Rice computer, and the circumstances in which the Genie system is used. Design specifications were made in 1958 at a time when no machine was available with a word length suitable for extended numerical calculations; the choice of an instruction code for the machine using a 56-bit word has led to some features which, if not novel, at least do not appear to exist in such a combination on another computer. The machine is binary, and has main memory of 32,767 words, principally in electrostatic storage which is parallel in operation. Access to the memory is shared by four magnetic tape units, a fast line printer and the central processing unit. Primary input is by punched paper tape prepared on an 88-character Flexowriter with 112-line super- and subscript shifts. The principal features which are relevant to the present discussion may be summarized as follows: 1. A location number is 15 bits in length. It represents, in one's complement notation, a numeral in the range (—16,383, +16,383). 2. The machine contains 8 conventional B-registers each of length 15 bits, one of which is the 'control counter' used in sequencing programs. Thus simple routines may be written in absolute code in completely relocatable form. 3. An address consists of 24 bits, divided into groups A,, A, and A, of 1, 8 and 15 bits respectively. A location number is formed from an address in the following manner: (a) The contents of up to 8 B-registers, selected by A,, are added to the number represented by A,. (b) If A, is zero, the 15-bit number resulting from (a) is the required location number. If A, is one, the result of (a) is used to select a word in memory from which a 24-bit address is taken, and the process (a) is repeated, and (b) reapplied. Thus indirect addressing to any depth with B-modification is permissible (Fig..I). 4. An instruction is a 54-bit number containing up to three operands and two orders. An operand is specified either by an address or a truncated location number of 4 bits, which selects one of 16 special fast access (1 psec) registers. Two of the operands may undergo sign modifications selected by the instruction. The location number determined by the address may itseIf be used as an operand, by using an immediate addressing option. An order is either a 15-bit order code or a part of an auxiliary operation which involves certain of the fast registers. In the order code are about 1000 non-trivial orders with perhaps 200 of these in regular use. The auxiliary operations are 64 in number, and include such frequently used orders as B-register incrementing and decrementing (thus including 'jump' orders) and transfers between fast access registers. It is our experience that the present organization combines many advantages of single-and three-address machines, achieving more compact programs than would be expected, even on the basis of the longer word length (Fig. 2). 5. Associated with each word in memory are two tag bits or labels which do not take part in its function as a number or instruction. They are detected separately in the arithmetic and control sections of the machine, and may be interrogated and set to 0 or 1 by conventional orders. Alternatively, they may be interrogated automatically when the machine is in the 'trapping mode' described in the next paragraph. 6. Under normal sequencing conditions, instructions are taken from consecutively numbered memory cells to the control unit for execution, unless a conventional 'transfer of control' takes place as a result of an order. In executing an instruction, two operands are brought to special registers in the arithmetic unit, the designated order is then obeyed, and finally the auxiliary operation is performed. When the machine is in the trapping mode, normal sequencing may be interrupted if certain conditions arise in the control or arithmetic units. The point at which interruption or 'trapping' occurs depends upon the intentions of the coder, but there seem to be three natural points at which the option should be provided: (a) Immediately an instruction enters the control unit. This is useful if any part of the instruction requires an interpretation not provided in the machine hardware. (b) Immediately an operand enters the arithmetic unit. This is useful again if the operand is of some 'non-normal' type, requiring interpretation. (c) Immediately after an order has been executed, in case some particular condition, such as an overflow, has arisen. All three possibilities are provided on the Rice machine. Cases (a) and (6) are normally controlled by tagged instructions and data. Apart from the obvious ability to employ these features in selective interpretive and tracing routines, they are of importance in the control of the Genie codes. In the latter respect a simulated interruption system would begin to lose practical value. Some remarks on experiences in hand coding the machine are appropriate at this point, since they illustrate both the direction and purpose of our efforts in automatic coding. The instructions admit of a compact and meaningful symbolic representation which is used by almost all coders. Using the symbolic assembly program, correct codes can be written reasonably concisely and quickly if no more than a casual regard for optimization is taken. By 'optimization' we mean reaching an acceptable compromise between time and space requirements in a given code, such that a reduction in one cannot be reached without an unacceptable increase in the other. It involves principally the choice of the index registers and fast registers which will be used, taking into account the ability to use truncated operands and orders, and the requirements of subordinated or concatenated pieces of coding in these respects. The detailed optimization of code is an interesting and normally rewarding problem. At the same time, it frequently amounts to a combinatorial problem of such magnitude, even for short codes of 20 or 30 instructions, that the coder is willing to accept a soIution he believes to be near-optima1 rather than devote time to investigating all possibilities. The point to make here is that we consider all coding, hand or automatic, to take part in four stages: (a) A description of an algorithm. (b) An initial equivalence transformation of the algorithm dictated by the properties of the machine and the translation process. (c) A translation from the algorithm description to a sequential machine code. (d) A final equivalence transformation of the machine code based upon certain optimizing criteria. In practice, it is rare to consider these stages separately, but since it is our purpose to assign the last three to a machine, and since each involves an amount of experimentation, it is advantageous to separate them. The present paper is concerned with stages (a) and (c), as far as they affect the user of Genie codes. In fact, some of the descriptive forms permitted in Genie are precisely those convenient for describing experiments on stages (b) and (d), which are the subject of continued investigation. Whilst refined optimizing processes are of considerable technical interest, and probably of future importance, it remains to be seen whether, even on a machine as versatile as the one we are concerned with, they will gain favour over crude but fast methods. However, it does seem possible that a good solution to the combinatorial problem can be attained at stage (d). In the writer's view, the task of designing an automatic coding 'language' for a particular class of problems is for the user of the language, and not the designer of automatic coding systems. In the sense that he, too, has a class of problems that can be described formally, he is a user with prejudices of his own, but in the main he cannot anticipate the tastes of those using other formal languages beyond attempting to provide for as wide a choice of form as possible. Only in this way does it seem possible that an acceptable 'universal' language will develop in any particular branch of mathematics. Although the system may be anchored at one or two corners in safe theoretical grounds, it is supported in the main by its use and abuse: in the present case, the users are chemists, physicists and mathematicians, with a small number of large problems of an experimental numerical nature. If it appears that Genie is designed for coders with some fluency in the symbolic representation of algorithms, then the circumstances of its use may provide an explanation. Extract: Particular Aspects Of Genie Organization 2. Particular Aspects Of Genie Organization Genie is concerned in general with the definition of objects belonging to certain computable domains, and the execution of particular opationr between or upon these objects. Both the objects and the operations are under the control of the coder, but if he can find an acceptable machine realization for them both, then he can call upon the mechanism of Genie to assist in a calculation. Applications of Genie have been made to domains of objects wGch include 'numbers', 'integers', 'names', 'symbols', 'equations', 'formulae', 'truth-values' and 'instructions'; (Each defined in some specialized sense corresponding closely to general usage.) generally, operations on such objects fall into closed groups so that we can talk of a 'language' in which operations between objects in a certain domain, say 'integers' or 'truth-values', take place. It is practical to give a description of such 'languages' in parametric terms, and although in the present paper particular reference is made to the conventional language forms of algebra, it should be understood that most of the constructions illustrated are operand independent in the sense that a given formal representation may be variously interpreted in a number of domains. Formal calculation proceeds by naming objects of interest, and assigning values to such objects either by means of equations (which use names and operations), or, in the case of linguistic objects, by exhibiting specific examples of the objects. The fact that early applications of Genie have been made to linguistic objects should not obscure the more general conception of the system. Two features are characteristic of most coding systems in active use at the present time and may be selected as ones which have been modified in Genie. They are as follows: (A) The pattern of sequential coding imposed by machine conventions in the past decade still dominates algebraic coding languages. The 'instruction' has become a 'statement', but the only advance towards nonsequential description has been to permit the use of formulae and substitution-type equations. (B) The 'translation' process is conceived in terms separate from the 'execution' of a program. In their primitive forms, the deficiencies of both these features have long been recognized, and a number of attempts have been made to use the sequencing implicit in recursive definitions in order to derive more compact descriptions of algorithms. Any text on recursive functions supplies schemata which may form the basis of such descriptions, but an immediate attempt to allow descriptions of a general type falls into difficulties of another sort. Firstly, our machines are finite in both capacity and speed, and the type of program resulting from general recursive definitions may overstrain both these quantities . Secondly, from the point of view of practical description of algorithms, recursive definition is only useful up to a point where rapid visual comprehension is possible: beyond that, it is self-defeating, and a survey of any text on numerical procedures would bear this point out. Most expressions belong to a relatively small class of primitive recursive functions, and complicated algorithms are described by reverting to a sequential presentation of these expressions, although the proportion of these which consist of simple substitutional equalities is probably quite small. One of the objectives of Genie, therefore, is to extend the basic forms of definition which can readily be understood, and simply and efficiently encoded. The precise form of these extensions is not of vital importance, but some examples of those in current use are given in the next Section. An improvement on the second feature (B) is less easy to achieve, although its necessity can be demonstrated by various expedients currently in use to circumvent it. These include 'load-and-go' techniques, the 'subroutine library', 'subroutine package', the 'executive system' and various 'monitoring' systems. To recognize the similarities of all computing processes involves a unification of these ideas, and the removal of one of the main obstacles to efficient automatic coding, in its widest sense. In Genie the separation of processes of various types has been removed by greneralizing the concept of evaluation to include objects with values in any domain of interest, and by precise control of names to make evaluation an automatic process in cases where no ambiguity can arise. At its simplest level, this generalization can be illustrated by a numerical example. Suppose a and 6 have values 2.6 and —1.8 respectively. Then if a formula 'a + V is encountered in the course of constructing code, it will automaticalIy be replaced by the simpler formula '0.8'. Similarly, if w is a given constant number, and sin a given constant function, the formula 'sin (46)' would automatically be replaced by the simpler formula '0.5'. Other consequences are: (i) That a program is executed automatically if it has been defined and all parameters have been given values. (ii) That an executive system of some power is included in the formalism of Genie; machine operation is a continuous process from program to program. (iii) That storage control for vectors and matrices is continually exercised, space for arrays of variable size being taken only for the period of time in which they are used. One of the most difficult problems of automatic coding, yet one to which a sophisticated solution is required when continuous evaluation techniques are used, is that of the identity of names in different parts of a description. A coder frequently divides his problem into segments, each logically independent, but referring to the same operands: in each segment of code, references to 'common' operands must be distinguished from purely internal names. He may use constant numbers and routines of his own definition, he may use routines from a 'library'; he may also use one or more of the languages of Genie; and finally his code may involve analytical manipulations which retain symbolic names. All these requirements put constraints on the way names can be handled internally. A solution is proposed in Genie, which is summarized in Section 4, which links symbol control to a hierarchy of definitions given to the machine. This is probably by no means a final solution, but it is feasible, and corresponds in an approximate way with conventional usage where the latter has any describable meaning. Extract: Conclusion 6. Conclusion It is difficult to compare one system of automatic coding with another: in most instances they differ sufficiently in purpose and economic circumstance to invalidate any possible criteria of comparison. At the same time, the power of symbol manipulative languages (instances of which appear in the present system) supports the view that most apparent differences of form in an algebraic language can almost trivially be rectified and those that remain are accounted for by the tastes of the code designer. Differences of evaluation technique are not of first importance to the user of a system. t Indirectly, however, they will affect him to the extent that he requires flexibility and speed in problem solution. In this respect, the use of a hierarchy of definition sets in Genie is its key feature, leading to the application of the continuous evaluation principle, to the definition of context, and the formalization of automatic operating, debugging and symbolic correction schemes. One of the main objectives in writing Genie is to permit the description of both numerical and analytical processes in the same formal system. It will be recalled that from a formal definition (11) the principal variable can only be evaluated if value assignments have been made to each independent variable. If, by some syntactic device, an evaluation is called for by the coder, the occurrence of a name with unassigned value will result in a failure of the evaluation process at that point (by a 'trap transfer'). This is not necessary, however, if provision is made for the formal manipulation of names within formulae, and there is no theoretical limit to the complexity of such processes which can be accommodated. A more difficult problem is that of placing formal manipulations within an unambiguous context, and our present investigations, although incomplete, indicate that again definition sets may be more suitable tools than programs. in Goodman, Richard (ed) "Annual Review in Automatic Programming" (2) 1961 Pergamon Press, Oxford view details Of the scientific papers probably the most interesting is "The use of the Genie system in numerical calculation," by J. K. Iliffe. "Genie" is a remarkably elegant and powerful programming system developed for the Rice University computer at Houston, Texas. This is the first account to be generally published, and we must hope that it will be followed by further papers describing other features of the system (there is a tantalising mention in the present paper of "applications to linguistic objects"), and of its implementation. in The Computer Bulletin June 1962 view details in The Computer Journal 5(3) October 1962 view details in Wegner, Peter (ed.) "An Introduction to Systems Programming" proceedings of a Symposium held at the LSE 1962 (APIC Series No 2) view details in Wegner, Peter (ed.) "An Introduction to Systems Programming" proceedings of a Symposium held at the LSE 1962 (APIC Series No 2) view details in Wegner, Peter (ed.) "An Introduction to Systems Programming" proceedings of a Symposium held at the LSE 1962 (APIC Series No 2) view details in [ACM] CACM 11(11) November 1968 view details The BLM experiment 'Basic Language Machine' is the name given to an experimental computer built in the research division of International Computers Limited in Stevenage. As the name indicates, the experiment is directed at both the 'hard' and 'soft' aspects of computer design, but more particularly with the way the system appears to its users. It is 'Basic' in the sense that it is not concerned with those refinements which can be achieved entirely by 'soft' translation of commands from one language to another, nor with equivalent hardware transformations which do not affect the machine's logical capabilities. In algebra, the 'base' of a vector space is a set of independent vectors from which all elements can be derived by linear combination of operations; by a rough analogy, the 'base' we have been looking for is a set of objects and operations from which all elements of programming 'space' can be derived. The classic bases of computation, e.g. Turing machine or recursive function theory, are unsuitable in this respect, since they do not take account of the finite nature of machine registers, or of the task of program construction, to name only two important factors. Most computers in use today are based on the von Neumann model of machine organisation, which can be described in terms of a memory consisting of an ordered sequence of words, in which instructions and numbers are stored. A sequencing rule is introduced to describe how control passes from one instruction to the next. The instructions are split into function and address fields, and an addressing rule is used to determine the numbers on which the functions will operate. The definition then proceeds to more detailed definition of each function, including the conditions under which it 'fails', either because the addressing rule can't supply it with operands, or because it can't produce a meaningful result. It is well known that the von Neumann model as it stands is an insufficient basis for programming. This is difficult to 'prove', since most problems can be programmed, with a given function code and sufficient store. What is lacking is the generality of expression which alone makes the effort of writing a program worthwhile. In other words, the idea of words in memory must be replaced by a more general information structure, and the addressing rule must evolve into a more general means of identifying items of information and relating one to another. The conventional approach to this problem through 'high level' languages provides at best a partial solution: it offers the programmer a useful set of working concepts, but it attaches restrictions, in the interest of run-time efficiency, which are not always easy to accept. Moreover, the original program is often so mutilated in the course of translation that there is no hope of changing it during execution, or of checking that the structure is being interpreted consistently. In the BLM we are attempting to provide a 'hard' programming base sufficient to meet operating system and user requirements in the most general way, i.e. by retaining structural information as an essential component of a program, distinct from numbers and instructions, and adapting the function code to operate on it. Such a plan of work obviously calls for much detailed study of current programming practice, trends in component costs, market requirements, and so on. However, the essential features of a Basic Machine are almost as simple as a von Neumann machine; it is the purpose of the next three sections to introduce them at the same level of detail as would be offered in a first lesson on programming, i.e. assuming that the various exceptional conditions which are noted in passing are rare enough to be ignored, though we know from experience that they occur often in the human timescale. In Section 5, we indicate very briefly the various lines of development leading to a properly engineered system, some of which have been outlined in Iliffe (1968), and others are under investigation on the experimental BLM. in The Computer Journal 12(3) 1969 view details in [ACM] CACM 13(05) (May 1970). view details [321 programming languages with indication of the computer manufacturers, on whose machinery the appropriate languages are used to know. Register of the 74 computer companies; Sequence of the programming languages after the number of manufacturing firms, on whose plants the language is implemented; Sequence of the manufacturing firms after the number of used programming languages.] in [ACM] CACM 13(05) (May 1970). view details in Computers & Automation 21(6B), 30 Aug 1972 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in Computers & Automation 21(6B), 30 Aug 1972 view details Resources
|