Ring Fortran(ID:5846/)Ring-storage package for FortranImplementation of the Coral ring-system in Fortran by Linden Blake et al at the Admiralty Research Laboratory, Teddington, Middlesex Related languages
References: Many modern applications of a computer, particularly in the fields of computer aided engineering design and computer controlled drawing or display, are concerned with collections of objects, each of which has properties represented by some data, arranged in such a way that the association of one object with another is explicit. For example, certain objects may possess some common property or they may possess some hierarchical structure such as a family tree. Data representing such a collection of objects is known as an associative data structure. It is required to represent an associative data structure in a computer store in such a way that it may undergo rearrangement and modification when required and so that the associative relationships may be determined easily when the data structure is entered at any point. An association between two blocks of data in a computer store may be represented by adding to one block of data a word which contains a pointer to the address of a similar word added to the other block of data. By building on this concept multiple associations may be achieved by adding several words to each data block and by using many address pointers to link the blocks together in some orderly fashion. The simplest arrangement that will satisfy the requirements of the previous paragraph is one in which the pointers form rings that may be traversed from one block of data to another, eventually returning to the first, and to designate one position in each ring to be its starting-point. It is convenient, however, to have pointers that enable a ring to be traversed in either direction and also to make it possible to go directly to the start of a ring. The various published implementations of this concept differ in their arrangement and handling of the pointers, in their methods of execution, and in the command languages by which the systems are used. A review of several schemes was published by Gray (1967). All required compiler type programs to translate commands, written in the chosen terminology, into machine code or, in the case of APL (Dodd, 1966) for example, into PLIl statements and subroutine calls. There is as yet no 'standard terminology for describing associative data structures, or operations on them, and some of the published command languages are far from easy to use. The object of the present work was to provide a ring processing software package that permitted the representation of large complex associative data structures which could be operated upon in a manner which was easy to program. There is a tendency, at present, for engineering applications programs to be written in FORTRAN (in the hope that they will run on different computers without having to be re-written) and it seemed to be desirable to provide a set of operations within the framework of a proven high-level language rather than a separate facility. For these reasons our ring processing routines, written in a low-level language, are accessible to a programmer by calls to FORTRAN subroutines. (The package uses small auxiliary routines to connect it to the FORTRAN and it would be easy to enable it to be used with another high-level language, for example, as a set of ALGOL procedures.) This obviates the need for a special compiler to include ring processing operations and permits the programmer to use the jump facilities of FORTRAN to embed the basic ring processing operations in sophisticated program loops if he so desires. The subroutines permit all required operations on the structured data but the detailed organisation of the rings is carried out automatically. The names given to the subroutines are concerned with ring processing operations and the interpretation in terms of the data structure represented depends entirely on the application. The ring processor has been implemented on a KDF9 computer and is designed to fit into the Egdon 3 operating system (Poole, 1968). The system makes use of a four million word disc store and it was desired to use this to store large data structures which could be operated upon by running various programs in the computer. It was decided to hold each element of a ring in one 48-bit word. Although the use of forward, backward and ring start pointers in each element would have been desirable this would have restricted each address pointer to 14 bits and confined the total size of the structured data to less than 16,384 words. It was therefore decided to use 21-bit pointers which allow the data to occupy up to two million words if required. (Each element of a ring contains a forward pointer and either a backward or a ring start pointer as will be described in more detail later.) The data is held on pages in files on the disc store and pages are brought into the core store when required. By this means the ring processing package effectively permits the extension of the addressable memory within a FORTRAN program to about two million words. Extract: Data structure Representation of data structure in computer store The basic item of the representation of an associative data structure comprises a number of contiguous computer words and will be called an entity. Many different types of entity may exist in the same ring structure. A typical entity is shown in Fig. 1. The first word is the entity header and into this is packed information concerning its type, region, number and size. The next few words are elements of rings formed by address pointers as described in the next paragraph. (There is a maximum of seven of these, only six of which are available for general use.) The remaining words of the entity contain data specific to the object represented by that entity; these data may be alpha-numerical, e.g. the name of the object, and/or purely numerical data concerning one or more properties of the object, depending upon the application. The arrangement of a ring is based on that of the CORAL language which was developed at the M.I.T. Lincoln Laboratory (Sutherland, 1966). This allows 1 Entity header 1 Associative element in type ring Associative element 1 Associative element 2 I Ring start element I 1 Ring start element 1 I Data word I I Data word 1 I Data word I Fig. 1. Typical entity rapid tracing through the ring in a forward direction and permits tracing backwards or to the start of a ring with little extra effort. In our implementation each element of a ring is formed in one 48-bit word of KDF9 store and consists of four parts. Three bits identify the type of element, three bits form a number specifying its position in the entity and the remainder of the word contains two parts of 21 bits each. One of these parts holds the page and relative address of the next element in the ring. One element is the start of the ring and is called a ring start element; all other elements are subordinate to it and are called associative elements. In the ring start element the second 21 bits records the number of elements in the ring. In the associative elements the second 21 bits hold a page and relative address which points either to the ring start element or is used as a backward pointer. A backward pointer always points to an element with a back pointer and rings are formed with start pointers and back pointers alternating as shown in Fig. 2. The less useful pointers are thus stored in half the space but this involves only a small sacrifice of operation time. Ring start element Start pointers t - Back pointers Fig. 2. Arrangement of ring The association between two entities is achieved by choosing the associative element, at a given position in one of the entities, and putting it into the ring starting at a given position in the other entity. A third entity may be associated with these two by putting one of its associative elements into the same ring and further entities may be added in the same way. When it is desired to put one associative element of an entity into the rings starting in two or more other entities a problem arises because an associative element has only sufficient room for the pointers of one ring. This problem is handled automatically by the program by letting it join rings together by means of a device called a knot. (These were called nubs in CORAL.) A knot is a two-word block of store each word of which is an element of a ring. When an associative element of an entity is to be put into two rings it becomes the start element of an auxiliary ring of two associative elements, one in each of two knots. The other two elements of the two knots become associative elements in the two rings of which the entity is to become a member. If it is desired to place the entity in a further ring the number of knots is increased by one, and so on. Thus the effect of the auxiliary ring is to provide an extension of one 42 Linden F. Blake, et al. associative element of an entity when (and only when) required. It is best thought of in this way so that the original associative element in the entity may be regarded as one associative element tied to more than one ring. A ring without knots will be referred to as a simple ring and one with knots will be called a complex ring. The creation, organisation and deletion of knots is handled entirely by the processing package and need not concern the applications programmer. A small associative data structure is shown in Fig. 3 and illustrates the use of knots to join rings. Entities A, B, C and D, are in a simple ring having its starting element in entity I. Entity 1 is in one ring starting in entity A. Entity 2 is in two rings starting in entities A and B. Entity 3 is in three rings starting in entities B, C and D. The associations represented in Fig. 3 are completely general and depend upon the meaning given to the data structure in a particular application. For example, in part of an information system entity I might represent a particular subject, entities A, B, C and D papers on that subject (with titles and sources held as data) and entities 1, 2 and 3 the authors of the papers (with their names held as data). The limitation on the number of ring elements in an entity may appear to imply a limitation on the number of rings that can have their ring starts in a given entity, but this is not so in practice. For most applications this limitation will not be a restriction. If it is, however, the difficulty may be overcome by defining an entity with up to five ring start elements and by putting one or more of these entities into a ring starting in the original entity thus effectively extending indefinitely the number of ring starts there. If the latter is to have a large number of associations (as is implied) it may be convenient to include in the extra entities some words of data for identification or they may be identified solely by their positions round the ring starting in the original entity. in The Computer Journal 13(1) January 1970 view details |