Gypsy(ID:8146/)Emidec autocodefor General Interpretive Programming System experimental Autocode for the EMIDEC 2400. Stack-based, recursive and influenced by the lambda calculus Places Related languages
References: This chapter starts with a brief description of the GIPSY (General Interpretive Programming System) system which has been implemented on EMIDEC 2400. GIPSY interprets programs consisting of lists of names of functions. This is followed by an account of a method of describing the combining of operations called a 'construction process'. A tree diagram is used to describe this construction process and rules of evaluation of a construction process which use a stack are introduced. Operations which transform tree diagrams to produce equivalent tree diagrams are discussed. The evaluation of equivalent tree diagrams produce the same result but the time taken or storage required may differ. The restrictions on operations which are allowed in the GIPSY system are relaxed. The generalization allows operations which are included in other operations to address the arguments of an outer operation. Extract: Description of the GIPSY System pt 1 Description of the GIPSY System There are three basic functions built in to the GIPSY system called 'DEFINE l', 'DEFINE 2' and 'INTW'. By using DEFINE 1, a piece of program or a subroutine can be written in machine code, given a descriptive name-and added to the system. The program INTERP accepts a list of names as argument and interprets the names one at a time. Interpreting a name which corresponds to a machine code subroutine causes the associated subroutine to be executed. Control then returns to the interpreter to interpret the next name. The list of names is called GIPSY language. The function DEFINE 2 is used to define new subroutines whose body is written in GIPSY language, e.g. 'AB + C - AC f +'. The specification of the subroutines and the names are left to the user. When a new subroutine is defined, the body of converted subroutine is placed at the end of an area of store called the 'function area'. The name and the address of the body of the subroutine are placed in a 'function table'. The interpreter accepts a name and looks it up in the function table. If the name is found the interpreter passes control to the body of the subroutine. Each machine coded subroutine can be activated in two ways: 1. By a subroutine jump from machine coded programme. 2. By interpreting its name. The function DEFINE 2 is used to define new subroutines whose body is written in GIPSY language. The body is placed in the function area, its name and address are placed in the function table. The function table contains one bit with each name and address pair to tell the interpreter whether the body of the subroutine is in GIPSY language or in machine code. When the interpreter interprets the name of a GIPSY language subroutine the interpretive control number is stored and changed to point to the beginning of the body of the subroutine. Each GIPSY language subroutine can be activated in two ways: 1. By interpreting its name. 2. From machine code of the form 'a special subroutine jump followed by the name'. A register 'C' holds the address of the name which is currently being interpreted and is called the 'interpretive control number'. Extract: Description of the GIPSY System pt 2 So far a description of a basic GIPSY system has been given. A user can start at this stage if he wishes. However, a number of less basic but fairly general functions have been written and will now be described. All names in GIPSY language are names of operations. The names are written in the same order as the operations are to be obeyed. Both the links between subroutines and the variables are stored in a stack. Each operation finds its arguments at the top of the stack and replaces them by its results. Two registers A and P are used as reference pointers to the stack. The register A contains the address of the top member of the stack and is called the 'accumulator pointer'; P contains the address of the last link and is called the parameter pointer. Both machine coded and GIPSY language subroutines are written in a standard way. The first instruction is an 'entry' subroutine. This entry instruction stores the control number or interpretive control number& the stack together with a bit which signifies whether the entry to the subroutine was from machine code or GIPSY language. The value of P is also stored in the stack and P is re-set to point to this new link. The last instruction of a subroutine is an exit order which overwrites the input variables by the output variables, restores the value of P and makes a machine or interpretive jump to the return address. The arguments of a subroutine are brought forward from behind the link to the head of the stack by the functions called GI, G2, G3 etc. There are also functions which transfer an argument back from the head of the stack to a parameter position called TI, T2, T3 etc. Interpretive conditional and unconditional jumps are also standardized. The names 'TEST' 'BEGINS' 'ENDS' are used in that order to separate the list of names into two parts. The names between 'TEST' and 'BEGINS' are interpreted and those between 'BEGINS' and 'ENDS' are skipped if the stack holds the Boolean variable 'true'. If the stack has 'False' as its top member the names after 'BEGINS' are interpreted. When the function 'TEST' finds 'false' in the stack it searches forward to find the 'BEGINS' bracketed with it, any other bracketed 'TESYs and 'BEGINS"s are ignored. When it finds 'true' in the stack, 'TEST' allows interpretation to carry on with the next name. When the function 'BEGINS' is interpreted it skips interpretive control until after its bracketed 'ENDS'. Unconditional jumps are of the form 'JUMP' followed by a number. The position jumped to is made up of the name 'TAG' followed by the same number. The process of interpretation described is very slow because the interpreter searches the function list for each name. Interpretation is speeded up if the interpreter does translation from the name to address and replaces the name by the address on the first interpretation. The first time the interpretive control passes through the names is slow but subsequent interpretations of the same program are faster. The basic input characters go through a slight translation before they are interpreted. Names are put into one machine word, numbers are converted to binary and character strings are fitted into an integral number of computer words. There is a compiling process in the GIPSY system which compiles a subroutine in GIPSY language to a subroutine in machine code. It changes the body of a 'DEFINE 2' item into the body of a 'DEFINE I' item. in Wegner, Peter (ed.) "An Introduction to Systems Programming" proceedings of a Symposium held at the LSE 1962 (APIC Series No 2) view details Introduction Electronic computers are able to work at high speeds only because they are programmed. Analysis of a problem, or a data processing procedure, and the programming of it for a computer in machine code, is a laborious task. In the early machines, users soon appreciated the advantage of having standard programs for assembly and program development, and a library of routines for regular calculations, complex number input and output, and for tracing the course of programs during program development, particularly when unexpected results were given when the program was tried on the machine. Where jobs are to be done regularly, it is still most economical, in the long run, to program them in machine language using such library routines as may be available. But for jobs which have to be done only once, or where it is desirable to try-out part of the job first and then extend the application of the computer, simplified programming systems have been developed. By their means, the computer can be addressed in a form of English, or by direct use of mathematical symbols if these are available in the character set of the teleprinter-punch used for punching the program. These simplified programming systems to which I shall apply the term "Autocodes" (originally named by Brooker at Manchester), together with available libraries of programs, constitute a very significant extension of the machinery which is now available. Besides saving the time spent on programming, these systems reduce the clerical errors of program writing by eliminating many tedious steps and this also reduces the time taken by program development. They also make it easier for the writer (or another person) to amend the program at a later date. In the earlier systems, the simplification entailed a varying loss of operating speed, varying between two and fifteen times as long to do a job on the machine. But a half hour of computer time after a few hours' programming in autocode is a more economic proposition for a one-off job, or trial of a routine job, than several weeks on programming, followed, after several trials, by a successful five-minute run on the computer. The newer programming systems, which involve a preliminary operation to compile a machine code program, will suffer less loss of speed and will become the normal method of programming computers for calculations and dataprocessing work, where the operations are not sufficiently standard to justify the writing of specific or general programs in machine language. Extract: Work at Rothamsted Work at Rothamsted In his valedictory Presidential address to The British Computer Society in London on 26 September 1961, Dr. Frank Yates reviewed the contribution which computers have made and are making in research statistics. It is on the solution of problems involving heavy numerical computation, in pure research, and in engineering design that, in his view, computers have achieved their most striking successes: Dr. Yates went on to point out that even in fields where computational tasks had previously been performed on desk calculators, computers could introduce three new features: (a) Speed, e.g. where further progress depends on knowing results to date. (b) A more thorough job, with better editing of data and more accurate calculations. (c) Relegation of computational methodology to the machine, so that people requiring to do calculations do not have to know the detail of the calculations involved. His paper (Yates, 1962), published in the January issue of The Computer Journal, reviews experience at Rothamsted and the development there of general programs for statistical work and some autocodes at other centres. If a general purpose program is available to include a mathematical procedure or the statistical method which one needs for a piece of analysis, then more people can use the computer. 1 have prepared a schedule of some of the schemes that are now available, or may be expected to be available early in 1962. Those who have access to a computer may find this of interest to follow up whichever line of development is applicable. Extract: Applications in Metal Box Company Applications in Metal Box Company In a paper published in The Computer Journal for April 1961 (Gearing 1961) 1 referred to the use which we, in The Metal Box Company Limited, had made of Pegasus autocode. I reviewed, in some detail, two programs. One of these was an analysis of a market survey for household trays in which interviews were conducted with some 1,100 households, covering 17 general questions and 10 observations of each tray found at the house: these questionnaires were analysed and 17 tables for the internal report were printed direct from the computer output tape. The other program related to part of our work on experimental sales forecasting and is now available in the Pegasus/Sirius interchange scheme (Ferranti, 1960). Our first computer application to quality control was in 1958-59 when we undertook an analysis of variance in connection with a productive operation being camed out by a group of machines in the chain between the sheet of tinplate and the finished open top can. Three factors were involved. The autocode program for Pegasus was thought to be rather slow and a full machine code program was written by Mr. D. Bulcock and is now available in the Pegasus interchange scheme. There are other analyses of variance programs available, notably one by BISRA (Caner and Taylor, 1960) which caters for up to seven factors, but if there are more than seven levels and only three factors involved, our program permits all the levels of data to be used. Nowadays, we would not attempt to write a full machine code program unless the job was going to be frequently done and would require considerable machine time. In the group of machines which we are using, a compiler-program has become available which automatically translates the Pegasus autocode program into Sirius machine orders (Ferranti, 1959 and 1961). In 1960 we were asked to assist in the analysis of data on the variability of some raw material which had been collected from sampled consignments over two years. Several different characteristics of the material had been measured. An autocode program was wntten to analyse each characteristic separately, prmting sample means, ranges, standard dev~ations, and compiling frequency distributions of means and standard deviations. A hierarchic analysis of variance was also given at the end of each characteristic. We were asked to undertake this work on 29 March and the calculations were substantially completed on 12 Aprll. Further calculations and a correlation between two characteristics were made on 3 June and 5 October 1960. Here I would like to stress that although the program was written in autocode, which is normally advocated for one-off jobs, the program is a general one. The progress of the calculations is controlled by ten parameters and the print routine by seven more. Thus one program served for the analysis of all the different characteristics, including some that involved preliminary arithmetic on pairs of observations. The correlation program was written separately but took only two hours to write, using pairs of exlsting data tapes fed in on the two tape readers simultaneously. Extract: Scientific Autocodes Scientific Autocodes The list appended covers a wide range of programs. compilers, autocodes. Among the autocodes which can be taught in a few days and which are already fully operational are : Mercury autocode. Pegasus/Sirius autocode. Ferranti Matrix Interpretive Scheme. Deuce Alphacode. IBM Fortran. Edsac 2 Autocode. Stantec Zebra Simple Code. Elliott 803 autocode. Elliott and other systems based on ALGOL Extract: Commercial Autocodes Commercial Autocodes Those concerned with Commercial Data Processing should have a look at: ICT Rapidwrite-Cobol. Ferranti Nebula. Cleo & Gypsy when available. These may take a couple of weeks to study, because, speaking from experience with Nebula, there are not only procedure descriptions but also file outlines and specifications of format of data and results when dealing with computers having considerable ancillary equipment. The Scientific Autocodes are usually concerned with one medium of inputloutput only, punched tape or punched-cards. Programming a data processing operation in a Commercial Autocode like Nebula becomes a full-time job; but it is easier to train staff in Nebula than a machine code and the autocode compiler will (we hope) take care of housekeeping routines when opening and closing files. We are using young men and women of O level mathematics, who have had experience of controlling our punched card routines, for this work. in The Computer Bulletin March 1962 view details The author then begins a discussion of "construction processes", which are represented by tree diagrams, and describes how several operations are combined into a single new operation. He then discusses how these construction processes are interpreted, using a stack to store the elements. IIe next discusses the provisions for nesting procedures, and how these are implemented using the stack. He introduces an operation called "apply", which allows operations to be used as arguments. Finally, recursive operations are discussed briefly, and some examples are given of methods to improve the efficiency of operations. in ACM Computing Reviews 5(04) July-August 1964 view details |