DSPL(ID:7344/dsp004)Display Systems Programming Languagefor Data Structures Programming Language D. Evans, University Pennsylvania, and A. Van Dam, Brown University Related languages
References: in Advances in Computers, Vol. 7, L. Alt and M. Rubinoff (Eds.), Academic Press, New York, 1966 view details in [AFIPS] Proceedings of the 1967 Spring Joint Computer Conference, April 18-20, Atlantic City, N. J. SJCC 30 view details in [AFIPS] Proceedings of the 1967 Spring Joint Computer Conference, April 18-20, Atlantic City, N. J. SJCC 30 view details in Morrell, A. J. H. (Ed.): Information Processing 68, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968 view details Languages for creating and manipulating data structures Languages specially designed for creating and processing list structures have been around for ten years or more: examples are LISP, SNOBOL, IPL and COMIT, to name a few. Ring structures were first used in the SKETCHPAD program [ 100 ] developed by I. E. Sutherland at Massachusetts Institute of Technology. Since then, languages for creating and manipulating ring structures have been developed. CORAL [ 101 ] was the first of these. More recently other languages with greater flexibility and more complex data structuring capability have appeared. Extract: Low Level Languages Low Level Languages Some languages allow the user to program very efficient! but the user has to program closer to machine language to get this benefit. Programs written in these languages run much faster, even one or two orders of magnitude faster, than the same programs written in higher level list processing languag Examples of low level languages are L6 [ 55 ] (K. Knowlton, Bel Telephone Laboratories) and DSPL [ 105 ] (D. Evans, University Pennsylvania, and A. Van Dam, Brown University) and to some extent ASP [ 59 ] (C. A. Lang and J. C. Gray, Cambridge University England). L6 and DSPL data structures are built up from blocks, fields, and pointers, A block is a sequential number of machine words, a field is a sequential number of bits in a word, and pointer is a word address. In DSPL (L6 is similar) a user can create and name blocks and fields (called baseblocks and basefields in this language) and can interconnect them with pointers to form structures. Addresses are formed by concatenating the names of blocks and fields. IJith reference to Figure 7, one can use ABC as an address to start in block A, find a pointer in field B to another block, and then retrieve the contents of field C in that block. If the block contain) field C is labeled D, then address DC also retrieves the contents of field C. Concatenating pointers in this way is often called pointer chasing or field sequencing. A powerful feature of this language is the facility to create templates (blocks or fields) at any place. The template may be located with respect to an existing block or field. An example is shown in Figure 8. In this example a mask is formed for bits 0-15 in word 3 of every block, and block A is specified as a template with respect to (base) blocks BIG and SMALL. Operations must also be included in low level languages make them useful. These include shifting operations, logical operations, fixed point arithmetic, storing of pointers, etc. There must also be a few simple control commands like DO, IF. THEN, GO TO, IF ALL, and others for input and output. DSPL also includes a paging facility. Pages have an identification key and a control header that specifies how a page i structured. There are four other sections to a page: a table of references to items on other pages: a table of references to items on other pages; a table of references to local pages associated with this page: a description of the page when it is made permanent; and a data section. Local pages all pages that are associated with a (main) page and which contain information that is necessary for defining an information structure. A page is temporary while data in it is being created or altered and may be made permanent when the user indicates that it is completely defined. The user has access only to the da l section of a temporary page; the other sections are maintained by the system. When a page is made permanent, it can only be read and cannot be altered. A frequency-of-use and recentness-of-use statistic is us to determine which pages to keep in core or which to write out on disk when more space is required by other pages coming int core. I4hen a page is brought into core, a look-ahead mechanism is used to bring in other pages that may be needed also. This is done by looking through the reference tables of the page j brought in to find what other pages may be required; and if t is room in core for them, they are brought in while the first page is being processed. DSPL is one of the few languages for data structures which are set up for list-type secondary memory has a paging system that is explicitly set data structures. Other languages that use usually use an existing system paging mechanism and would, therefore, be less efficient. Low level languages in general can be used to build any kind of list structure, even hierarchical ring structures, an~ are very efficient; however, the user has to concern himself with all the structuring details. ASP [ 59 ] , which stands for Associated Structure Package, is low level language that uses MACRO calls for creating ring (hierarchical) structures. The language is not at such a low level as L6 or DSPL, but nevertheless, the programmer creates and manipulates structures and data items explicitly and controls the form of the structure. The system has been created for the Titan (Atlas 2) computer, and ASP statements may be Compiled together with programs written in other languages for this computer. Thus it is possible to build a model in ASP and to perform analysis on the data with programs written in other languages - a very desirable feature. Associations between data elements may also be expressed in ASP. This is done by creating an associative ring and connecting together rings from all associated items on this associative ring. The association is then expressed in the header, called a ringstart in ASP, of the associative ring. A data element can have many associations. Using this technique, data relations can be represented in ASP in a similar manner to those which can be represented in LEAP [ 38, 88 ] (see Section 3). Extract: Higher Level Languages Higher Level Languages The reason for developing higher level languages is to free the user from the details concerning the computer and to allow him to concentrate on his problem. The result is that usually a problem may be solved more quickly by using a higher level language, but it is less efficient because it generates more machine code, which uses more storage space and takes longer to run. PL/1 has the facility to create pointers, and therefore list, ring, and tree structures can be constructed with this language. Dodd has added six statements to PL/1 and formed APL [ 31 ] (Associative Programming Language), which is particularly conventient to users who wish to express data associations. The basic elements are called entities, which in turn are described by attributes. Related entities can be grouped into sets and may be referenced through another entity which owns the set, or they may be referenced independently. An entity is a contiguous block of memory locations and contains the following: (a) References (pointers) to subsets belonging to the entity. (b) References to sets to which the entity belongs (called an associative set of reference links). (c) Data attributes. Sets are arranged in the form of rings. Figure 10 shows a typical example where D and E belong to B, while E is a member of subset C, which itself is in set A. APL has many special programmer tools, declarations, sta meets, and control specifications for creating and manipulati data. These are all specified in a higher level language for and the APL structure can be referenced from PL/1 programs, which makes things easier for the user. Therefore, it is not necessarY for the programmer to be aware of details such as r structuring when using the language, and this is a good featu Also all normal PL/1 language facilities are available to the user. A language called LEAP, developed for expressing data re rations in associative structures, has been developed by Feld and Rovner t38, 88 ] . LEAP is an extension of Algol and inclu statements for creating and accessing data by a hash coding technique. Data associations are of the form: or "Attribute of Object is Value" A(0) = V. An example is: father (jack) = jim - where father, jack, and jim are called items. This data is created and stored ty a hi level statement: Make father jack = jim and jack may be put into a set SONS by PUT jack in sons. Data is stored in an A page, an O page, and a V page. Items are treated as integers, and data for an A page, for example, is created by hashing together the A and O values of the triple A(0) = V. The system is symmetrical, and each tri is stored on a page of each type. All occurrences of a parti cular item on an A page are connected together on a ring in t A page; similar rings exist in the O and V pages. Several ki of requests can be made of the system. If the A, O, and V names are all given, the system checks to see if the triple i ~n the store. If any two items are given, they are hashed to gether by the same mechanism that is used to store triples an~ all the third values that satisfy the triple are returned. Thus, if A and O are given, a position on the corresponding , page is found from hashing A and 0. At this position two lis hegin. One is a conflict list for all A,O pairs that hash to this address, and the other is a multiple-hit list for all va V that form triples with this particular A and O pair. All values of V for multiple hits and for the appropriate A,O pair in the case of a conflict are returned. Similarly, if any one item in an A,O, or V position of a triple is specified, then all triples in which this item is used in that position are found, using the rings~4escribed above, and are returned. This system allows arbitrary data associations of the form A(0) = V to be created and stored. Storage and retrieval of data are fast and do not require extensive pointer chasing, except to resolve conflicts and to return multiple hits results. Because of the paging structure, extensive page swapping is also avoided. Twice as much storage [ 38 ] is required to store data in A, O, and V pages, but it is in secondary memory where the extra storage is needed. LEAP has been used in several interactive graphical applications. The language is useful in Darticular applications only if data associations are already in the form A(n) = V or can be expressed in that form. Other developments in associative processing include TRAMP [ 3 ] , which is an interpretive assoc~ative processor, and Symond's associative data structure, which is an extension of PL/1 and which is based directly on Feldman and Rovner's idea of expressing data associations in the form A(0) = V. in Klinger, A.; Fu, K. S.; Kunii, T. L. "Data Structures, Computer Graphics, and Pattern Recognition" (Largely based on IEEE Computer Society conference held in Los Angeles, May 1975) Academic Press, NY 1977 view details |