L6(ID:227/l::002)Laboratories Low-Level Linked List LanguageBell Telephone Laboratories Low-Level Linked List Language. Ken Knowlton, 1963-5. Typeless list processing language. Base data structure was the bug, which was a varying base list structure. Many interesting features, not least of which was the incorporation of names by coalescing their functions. Higman (2nd ed 1977): "The syntactic nature of a line is an intersting first step towards thinking of program structure by encouraging the grouping of machine instructions into compound operations. (This can be done in any assembly code that allows a semicolon, for example, to double as a new line semantically, but few programmers have the motivation to exploit it; L-six encourages it.)" Goto (who used ot get upset that Dijkstra considered him harmful) implemented a version on a FACOM in 1968 at Tokyo university Places Structures: Related languages
References: in [ACM] CACM 8(10) Oct 1965 view details in [ACM] CACM 8(10) Oct 1965 view details in [ACM] CACM 9(08) August 1966 view details Automatic picture processing by a computer has many and varied aspects, such as the analysis and measurement of pictorial patterns, the construction of picture sequences, the recognition of character shapes, the development of perspective figures, and so forth. For these applications various programming systems were developed. In this paper one such system called BUGSYS is described, which is based on and evolved from the previous programming systems of Knowlton and of the authors. BUGSYS is a picture processing and measuring system t h a t depends upon a pictorial input to the computer's memory. For the picture input the FIDAC (Film Input to Digital Automatic Computer) scanning instrument has been used. FIDAC can sample 350,000 spots (700 × 500 raster) of a picture in eight grey levels (3 bits per spot), and record these directly in the core memory of an IBM 7094 computer within 0.3 seconds online and in real time. As soon as the picture has been recorded in the computer's memory, the picture processing by BUGSYS is carried out. BUGSYS can be used for many types of applications. In particular, the authors have used the system for the analysis of photomicrographs of neuron dendrites and for the processing of Schlieren photographs taken for molecular weight determination when using ultracentrifuges. From a processing point of view, the problem is to make measurements on a curve. Since the lines are thick, the measurements must be made from points in the middle of the lines. Thus, for example, in Figure 2 the middle of segment A - A ' defines the line X = 0, and the middle of segment B - B ' defines the line Y = 0. Hence a point on the curve, say the middle of the segment C-C', will have the X- and Y-coordinates illustrated. Many hours are presently required to make the measurements accurately by manual means, whereas the automatic computer analysis using BUGSYS can accomplish the same task within a fraction of a second for an entire photograph. Extract: The System The System The main concept of the system is the use of a collection of programmable pointers, which are visualized as a family of "bugs" (whence is derived the title of this paper). A bug can be initiated or PLACEd, and once initiated, a bug can be MOVEd. In addition a bug can change the grey-level value of the spot on which it may be located and it can lay down a so-called STICK across a <thick> line in the picture as an aid to locating the middle of the line. This system has other macros which enable a bug to test the grey level value of the spot on which it is located and which enables some program manipulation. For each bug initialized by means of the macro PLACE, there is associated a list which gives the X- and Y-coordinates of the current position of that bug, the equivalent core location, the spot position (0-11) within this location (there are 3 bits per spot or 12 spots per IBM 7094 computer word) and the grey-level value of the current position of the bug. For example, if the bug named "ZIPPY" were in the position indicated by the circle, then the list for ZIPPY would contain the following:
As a bug is moved about the picture by a program, the list for the bug is kept current. In fact, in essence, the list is the bug. We now proceed to describe some of the statements of the BUGSYS language and then follow with an illustrative program written in the language. PLACE The PLACE statement initiates or sets up a bug by assigning a name and initial coordinates to it. The syntax is:
BUGS The BUGS statement allocates five storage locations to each bug named:
MOVE The MOVE statements move the bug a specified distance <i.e. number of spots> in either the x or the y directions, i.e. horizontally or vertically. The syntax is:
The effect of the execution of "MOVE bugname,RIGHT, distance" is to move the bug to a new location having the same y-coordinate but a new x-coordinate as follows: <new x-coordinate> = <present x-coordinate> + <distance> "MOVE bugname,LEFT,distance" is similar, but distance is subtracted from the present x-coordinate. The list corresponding to <bugname> is adjusted for the new value accordingly, of course. This statement includes a two-way branch, for provision must be made to be sure that the bug will not be MOVEd out of the picture. Hence, if the bug would be moved out of the picture, then it is not moved at all, and the next sequential statement is taken as the next executed statement. Otherwise <i.e., if the bug would still be in the picture after the move> the bug is MOVEd and the next sequential statement is skipped. GO TO For facilitating the two-way branch, a GO TO statement is included in the system, with syntax as follows:
TEST A series of statements are included in the system that TEST the grey-level value of the picture at the location of the bug. The syntax of three of them is as follows:
For "TEST bugname,EQUAL,grey cutoff," if the grey level value of the picture at the location of the bug is not equal to <grey cutoff>, then the next sequential statement is executed; otherwise <i.e., if the picture value is equal to the cutoff value> the next sequential statement is skipped. For "TEST bugname, GREATR, grey cutoff," if the picture value is less than or equal to the cutoff value, then the next sequential statement is executed; otherwise <i.e., if the picture value is greater than the grey cutoff value> the next sequential statement is skipped. CHANGE A bug's grey-level value may be changed with the macro CHANGE:
The grey cutoff, 7, is reserved as a control in order that the bug can leave sevens or "footprints" on the picture. This is an aid when checking out a BUGSYS program. The number, 7, can cause any user'specified symbol to be printed. STICK Statements that are particularly useful for "thick line" analysis are the STICKs. If a bug wishes to walk along the middle of a "thick line," these statements will readjust the bug location to the "middle" of the thick line. For example, suppose that the "thick line" is characterized by grey levels of 4 or greater, and that the present location <encircled> is not in the middle of the "thick line" <see Figure 3>. To adjust the bug's position, a horizontal stick is laid down to the right and to the left of the bug, but not extending past the "thick line." Then the bug is placed in the center of the stick <boxed> which is the desired position at the middle of the thick line. The syntax of the STICK statements is as follows:
Here the thick line will be characterized by grey-level values equal to or greater than the <grey cutoff> value specified in the statement. The value of <maximum length> is the upper allowable limit of the length of the stick (i.e., "width" of the "thick line") above which an alternative branch in the program can be chosen. In fact, the STICK instructions are three-way branch statements as follows: if the stick extends out of the picture, i.e., touches the picture edge, then the next sequential statement is executed; if the stick length exceeds the maximum length, then the next sequential statement is skipped and the second following statement is executed; otherwise (i.e., in the "normal" case) the bug is moved to the middle of the stick and the third following statement is executed next. in [ACM] CACM 9(02) February 1966 view details This paper is a description of Bell Telephone Laboratories' Low-Level Linked List Language. As its name suggests, it is another programming language which has been devised to permit easy handling of lists. It naturally contains many of the features of other list processors. In order to gain speed and make more efficient use of memory, it has been written so that the user is "much closer to machine code." The program is in use at Bell Laboratories for a variety of tasks and apparently is quite successful. H. H. Goldstine, White Plains, N. Y. in ACM Computing Reviews 8(02) March-April 1967 view details A basic package for constructing and manipulating lists and rings is L6. (Bell Labs Low Level Linked List Language). The main features are as follows: Blocks of various sizes are allocated by the free storage system. A "component" feature is provided, whereby a specified field (plus offset) may be named with any one of the letters or the digits A-Z, 0-9. If these fields contain pointers, then by concatenating the identifiers of these pointers one can have an (indirect) reference to another field; i.e., if A points to B which points to C which points to D, the identifier for D with respect to A is ABCD. This notation has been adopted for PL/1, in a modified form. In L6, 26 base registers are provided, called bugs (as they may be thought of as hopping around the structure pointing to various items). An indirect multiple reference is usually with respect to a particular base register. These act as basic program identifiers, and others can then be built by concatenation of field names. A very full set of arithmetic, logical and Boolean operations is provided together with such system operations as the setting up and use of built-in pushdown lists. As would be expected of a list processing language, subroutines may be recursive. L6 is written in MACRO-FAP; it would seem to be a very useful and flexible tool for building ring implemented data structure packages. in Proceedings A.C.M. National Meeting, 1967 view details in Computers & Automation 16(6) June 1967 view details External link: Online Extract: Use of names USE OF NAMES The distinction between a name and the value is one of the first hurdles one crosses on proceeding beyond FORTRAN in computer programming. The necessity for FORTRAN programmers to learn it is fast disappearing, if it has not already gone. Nevertheless, this distinction is of fundamental importance to the systems programmer. Strictly speaking, a name is a symbol together with all its attributes. These attributes may include such things as mode (floating point, integer, etc. ), storage length in words or bytes, address within the computer assigned to this symbol, as well as many others. The value ascribed to this symbol is an attribute usually only defined at the time of execution. Oddly enough, by the time of execution most of the other attributes of the symbol (including. the symbol itself) have been discarded. All that remains is its current value and its address. In the following sections when we use the term name, we will usually be referring only to the address for the symbol, having discarded most of the rest of the attributes at compile time. This restriction is not fundamental, however, since it is merely a matter of choice which attributes should be fixed and interpreted at compile time, and which should be left free until execution time. In particular, in function calls, MAD passes parameters by name, name in this case including the address associated with the symbol and the structuring information (to be described below). As a result of the compilation process, each symbol within the source program is mapped into an address and a relocation factor. We can think of this symbol as marking the position within some memory space which will be related to a real computer memory at some later time, For example, MAD programs produce symbols which are relocatable within the program, within a reserved area of core called PROGRAM COMMON, and within another area of core called ERASABLE. Similarly FORTRAN programs produce symbols within the program, within COMMON, or within one of the areas called labeled COMMON. The absolute location of each of these areas is undetermined at compile time as is the relative displacement of one area with respect to another. The only quantity which is determined at compile time is the relative displacement of one symbol with respect to another of the same relocation type. The usual method of relating these symbols to absolute memory locations is by means of a relocatable loader, which also has the task of performing interprogram linkages when more than one program segment is required for execution. At the time of loading each symbol becomes associated with a definite computer address. It is possible, however, to defer the A Compiler Language for Data Structures 389 determination of this definite address to an even later time. Using techniques known as dynamic memory allocation, a running program can determine the absolute origin of a certain storage region and use the symbol value as an offset into this region. Doing this means that a given symbol may refer to more than one machine address during the course of execution of a program. It also means that at the time of execution, one requires a means of indicating the memory origin of the storage area. To construct a list-processing system, a language must be able to compute the names which it employs within a running program. This ability allows us to represent a graph within the list structure and to alter dynamically the connectedness of the graph within the computer. As we have noted, MAD (and FORTRAN) have the ability to use run-time computed names through the medium of the subscript. This construction is limited in its utility, however, and its use for complex problems can be awkward if not downright unmanageable. What is needed as an addition to language facilities is the ability to calculate more conveniently names within the running programs. The definition of "conveniently," however, must rely on experience and some intuition, and it will always be tempered with the realization that "what is one man's meat is another man's poison." The type of operation envisaged was first based on the primitive functions of SLIP; 6 this was later abandoned and a scheme which was modeled on the facilities of L6 was developed. Extract: List-Processing Facilities List-Processing Facilities The first set of language extensions are designed to make it possible to program list-processing systems directly in MAD. The SLIP system 6 will be used in what follows as an example of a system which could be programmed in this language, but the facilities do not in themselves depend on SLIP. L6 2 was used as a model for type of facilities desired, although in some respects there is a resemblance to the APL system V as well as to PL/I. Two new operand modes have been created to afford the list-processing facilities desired: REFERENCE and DYNAMIC RECORD. A REFERENCE variable is a MAD-language variable whose value is a machine pointer to some other entity. REFERENCE variables may be combined with certain operators (to be described below) to form expressions of REFERENCE mode. The value of such expressions is a language name and as such may appear on the left side of assignment statements: REFERENCE expressions acquire utility when we must refer within a program to constructs whose names must be calculated at run time. Such objects are normally found within declarations called DYNAMIC RECORD. A variable is of mode DYNAMIC RECORD when it is used as a name for heterogeneous grouping of variables of other modes for which space is to be assigned by a dynamic-allocation routine at run time. This grouping may be such that several variables share parts of one computer word. An example from SLIP should serve to clarify the nature of DYNAMIC RECORD declarations. A SLIP cell normally contains four parts occupying two computer words. There are two pointers, LNKL and LNKR, linking the cell to its predecessor and its successor, an identification field, ID, which can assume the values from 0 to 3, and an entire word named DATUM normally used to store the information on the list. Extract: Other Extensions To The Mad Syntax Other Extensions To The Mad Syntax The MAD language offers a powerful facility to programmers to tailor their compiler to fit their application, viz., the MAD operator-definition facility. Using this part of the MAD compiler, the programmer (or programming staff) can extend the compiler by introducing new operators and new operand mode definitions into the language. In the formulation of any graphical language, the MAD operator-definition facility should play a large role. The syntax extensions we are describing in this paper are those which cannot be encompassed within the operator-definition facility. The list-processing facilities described in the last section resulted from the examination of the L6 syntax, and the identification of these elements which were beyond the scope of the operator-definition ability. The rest we leave for development at the MAD programming level. In a similar fashion, we have tried to identify those elements of graphical language which were beyond the scope of the MAD syntax for their possible incorporation into the compiler. The one example of a graphic language which encompasses most of the desirable elements is the LEAP language of Feldman and Rovner. 1 This language is an ALGOL-type language which includes elements of set operations as well as Feldman's own method of representing graphical relations. LEAP is predicated on a highly elaborate but efficient method of data storage involving hash coding, but the details" of the implementation do not concern us here. It What does concern us, however, is the language syntax, insofar as it is incompatible with a MAD representation. Of all the elements of the LEAP language, the only construct which represents any serious difficulty in implementation within the MAD operator-definition framework is that of the local variable. A local variable is one which has an undetermined value before the execution of a given statement (or block within ALGOL), but after the first occurrence of the variable within the statement, its value is constrained to be that which it was in the first occurrence. Upon close examination of this construct, we notice that it is always associated with an implied or overt iteration over some set of permissible values. Consider one well-known language which contains local variables, SNOBOL. The local-variables concept is present within SNOBOL as is evidenced in the statement LIST *A* ', ' *B* ', ' A--A ', 'B This statement directs us to search the string named LIST for the following pattern, an arbitrary string, call it A, followed by a literal comma followed by an arbitrary string, call it B, followed by a literal comma, followed by the field A repeated. A in this example serves as a local variable. In the first occurrence of A, its value is free, to be determined by the search. In its second occurrence, A is constrained to have the same value which it had in its first occurrence. This statement, however, has an implied iteration contained within it. In order to perform the pattern match, A is associated with certain substrings of the string LIST according to a preset algorithm. In the LEAP language, also, the use of locals is constrained to be within iterations, specifically iterations over the elements of some set. The role of a local, therefore, is that of a variable of iteration in that the iteration is a specification of a set of values which the variable should take on successively to the satisfaction of some condition. To accommodate such a construct in MAD we must be able to perform operations which result in the sequencing of some element over the available elements of a set and to let this operation control an iteration. The first part of this requirement can be most easily satisfied within the MAD operator-definition facility. Consider, for example, the operator .MEMBER. X .MEMBER. S could, by suitable definition, result in the sequencing of X through all the possible values of the set S, performing the sequencing every time the operator is executed. The necessity of iterating over this construction, however, requires a change in our iteration statement. In what follows we use the abbreviations < sid > := <.simple iteration description > < e > : = := With this notation, the MAD iteration statement has the form THROUGH where We have modified the syntax of the iteration statement as follows: THROUGH where and < sid> := The first extension allows us to incorporate several iterations within the same statement which are automatically nested from left to right. In addition, the iteration may contain a WHENEVER clause which determines whether the scope of the iteration is to be executed for that particular iteration. The extension of the simple iteration description allows us to include sequencing operations instead of assignments as the controlling elements of the iterations. These features are all exemplified in the iteration THROUGH A, FOR I ---- 1, l, I.G. SIZE.(S), X. MEMBER. S, WHENEVER X .NE. Y(I) A This statement provides a double-nested iteration, the outer iteration being over the value of I, and the inner iteration being over the value of X. The phrase X.MEMBER.S is assumed to be a defined operator which sequences X over all possible members of the set S. The result of this operation is (Boolean) false as long as the sequencing proceeds, and is true when the set S is exhausted. The conditional phrase X.NE. Y(I) does not terminate the iteration but merely provides that the scope of the iteration shall not be performed whenever the condition is not satisfied. We must emphasize that the operator .MEMBER. has not been defined within our compiler; the statement only serves to illustrate the modifications of the iteration statement syntax. The implementation of .MEMBER. and the formulation of the behavior of variables like S which represent sets is left completely open, to be defined by some operator-definition package for a given application. in Proceedings of the 23rd ACM national conference January 1968 view details in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details This paper describes the implementation on the London University Atlas computer of the Bell Telephone Laboratories low level linked list language L6. A syntactical definition of L6 is given in terms of BCL, a general purpose programming language with special emphasis on data structure. The description of the implementation in BCL includes details of the general field handling routines. External link: CompJournal online Extract: About BCL BCL is a general purpose data processing language with special emphasis on data structures. The version of BCL used in this report is that defined by the Atlas BCL compiler dated August 1968 (Hendry and Mohan, 1968). At the time of writing, functions and 'groups' of commands with parameters have not been generally implemented in BCL but a small subset of parameters has been added by the author to provide a working list-processing system for teaching purposes. The LISP function CONS and the predicates EQ, NULL and ATOM are defined in BCL, CAR and CDR are represented by HEAD and TAIL and the complete program in Table 1 shows how recursive functions, such as MEMBER, UNION and INTERSECTION, may be defined. The use of these functions demonstrates the high-level aspects of the system. At the other extreme, instructions written in the basic language of the machine concerned may be written anywhere in a BCL program, thus giving the flexibility of low-level list-processing languages such as L6 (Knowlton, 1966) with the possibility of manipulating bit patterns. The user may define list-cells or data blocks of several different sizes and from them build multi-linked structures by planting links in various fields of the list-cells. The system is particularly useful for teaching list-processing techniques as the student is able to get near to its innermost workings. He may extend it or even define and build his own system Extract: Review in Computer reviews by Yarbrough HOUSDEN, R. J. W. 18,880 A note on list-processing in BCL. Computer J. 12, 4 (Nov. 1969), 332-341. This paper describes a simple list-processing system which is based on BCL, a general purpose language with special emphasis on data structures. The basic LISP functions are defined in BCL and examples given of recursive functions. A program to input and differentiate polynomial expressions is described. The system has been used for teaching list-processing techniques to AI.Sc. students and has the advantage that the user can get close to its innermost workings. Nodes of several different sizes may be set up and used to build multilinked structures by planting in various fields pointers to other nodes. The appearance of this paper in the Computer Journal is perplexing: somehow the editors seem to have put the cart before the horse. If the author's bibliography is complete -- his paper is otherwise well put together -- then BCL (British Computing Language?) is properly defined only in a relatively inaccessible "parent" document, [1] The current paper would, if it appeared as an appendix to [1], be an outstanding contribution, as in that context it would be a well-written, stimulating exposition of the power and utility of BCL. Appearing by itself in the Computer Journal it cannot stand on its own merits: it says nothing new about list processing or its applications, except in the context of BCL. Perhaps it is this reviewer's ignorance of other prior publications about BCL which is at fault. If not, then an abridgement of [1] would be far more appropriate for publication in the Computer Journal. L. D. Yarbrough, Lexington, Mass. REFERENCES [1] Hendry, D. F. AND Mohan, B. "A BCL Manual", Internal Report No. ICSI 103, Univ. of London Inst. of Computer Science 1968 in The Computer Journal 12(4) 1969 view details This paper describes a simple list-processing system which is based on BCL, a general purpose language with special emphasis on data structures. The basic LISP functions are defined in BCL and examples given of recursive functions. A program to input and differentiate polynomial expression is described. The system has been used for teaching list-processing techniques to M.Sc. students and has the advantage that the user can get close to its innermost workings. Nodes of several different sizes may be set up and used to build multilinked structures by planting in various fields pointers to other nodes. External link: CompJournal Online Extract: Review in COpmuter Reviews by Goldstine HOUSDEN, R. J. W. (Univ. London, Inst. Computer Science, London, England) The definition and implementation of LSIX in BCL. Copter J. 12, 1 (Feb. 1969), 15-23. In this paper the author describes how the Institute of Computer Science at the University of London has implemented the Bell Laboratories list-processing language L6. The implementation is in terms of BLC, ". . . a general-purpose programming language with special emphasis on data structures...." An example is given in the form of a complete program that has been run. H. H. Goldstine, White Plains, N. Y. in The Computer Journal 12(1) 1969 view details in The Computer Journal 12(1) 1969 view details in The Computer Journal 12(1) 1969 view details in The Computer Journal 12(1) 1969 view details in Computers & Automation 21(6B), 30 Aug 1972 view details E. Goto, et al of University of Tokyo discussed an implementation on FACOM 230-25/35 of L6 (a list processing language) and its several extensions in the 1970 National Conference of IPSJ. Prior to this, L6 was implemented on HIPAC-103 by K. Takahashi, et al of Institute of Statistical Mathematics, and later its large extension was implemented on TOSBAC 3400. in First USA-Japan Computer Conference Proceedings, Tokyo, 1972. view details in ACM Computing Reviews 15(04) April 1974 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 ACM Computing Reviews 15(04) April 1974 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 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 |