LEAP(ID:427/lea004)Language for the Expression of Associative ProceduresLanguage for the Expression of Associative Procedures. ALGOL-based formalism for sets and associative retrieval, for TX-2. Became part of SAIL. Featured the triple, excellent structure for matching Dog.Owner = Bill... Structures: Related languages
References: an existing ALGOL system. This report consists of three sections: Sec. 1 describes the high-level programming language for the overall system; Sec. II outlines the scheme for representing an associative information base: and Sec. III summarizes the processing routines for associative retrieval requests. 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 Morrell, A. J. H. (Ed.): Information Processing 68, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968 view details in Kaneff, S. (ed) Picture Language Machines: Proceedings of a Conference held at the Australian National University, Canberra on 24-28 February, 1969 view details in [ACM] CACM 12(08) (Aug 1969) view details in Donald E. Walker, Lewis M. Norton (Eds.): Proceedings of the 1st International Joint Conference on Artificial Intelligence IJCAI-69, Washington, DC, May 1969. William Kaufmann, 1969 view details in [ACM] Proceedings on the ACM SIGFIDET Workshop on Data Description, Access, and Control, San Diego, California (November 1971) view details in Computers & Automation 21(6B), 30 Aug 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 Institution: Stanford University, Department of Computer Science Title: SAIL user manual. Author: VanLehn, Kurt A. Date: July 1973 Abstract: SAIL is a high-level programming language for the PDP-10 computer. It includes an extended ALGOL 60 compiler and a companion set of execution-time routines. In addition to ALGOL, the language features: (1) flexible linking to hand-coded machine language algorithms, (2) complete access to the PDP-10 I/O facilities, (3) a complete system of compile-time arithmetic and logic as well as a flexible macro system, (4) user modifiable error handling, (5) backtracking, and (6) interrupt facilities. Furthermore, a subset of the SAIL language, called LEAP, provides facilities for (1) sets and lists, (2) an associative data structure, (3) independent processes, and (4) procedure variables. The LEAP subset of SAIL is an extension of the LEAP language, which was designed by J. Feldman and P. Rovner, and implemented on Lincoln Laboratory's TX-2 (see [Feldman & Rovner, "An Algol-Based Associative Language," Communications of the ACM, v.12, no. 8 (Aug. 1969), pp.439-449]). The extensions to LEAP are partially described in "Recent Developments is SAIL" (see [Feldman et al., Proceedings of the AFIPS Fall Joint Computer Conference, 1972, pp. 1193-1202]). This manual describes the SAIL language and the execution-time routines for the typical SAIL user: a non-novice programmer with some knowledge of ALGOL. It lies somewhere between being a tutorial and a reference manual. in ACM Computing Reviews 15(04) April 1974 view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details Extract: Languages for creating and manipulating data structures 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 Institution: Stanford University, Department of Computer Science Title: SAIL Author: Reiser, John F. Date: August 1976 Abstract: Sail is a high-level programming language for the PDP-10 computer. It includes an extended ALGOL 60 compiler and a companion set of execution-time routines. In addition to ALGOL, the language features: (1) flexible linking to hand-coded machine language algorithms, (2) complete access to the PDP-10 I/O facilities, (3) a complete system of compile-time arithmetic and logic as well as a flexible macro system, (4) a high-level debugger, (5) records and references, (6) sets and lists, (7) an associative data structure, (8) independent processes, (9) procedure variables, (10) user modifiable error handling, (11) backtracking, and (12) interrupt facilities. This manual describes the Sail language and the execution-time routines for the typical Sail user: a non-novice programmer with some knowledge of ALGOL. It lies somewhere between being a tutorial and a reference manual. pdf Extract: History HISTORY OF THE LANGUAGE The GOGOL III compiler, developed principally by Dan Swinehart at the Stanford Artificial Intelligence Project, was the basis for the non-LEAP portions of SAIL. Robert Sproull joined Swinehart in incorporating the features of LEAP The first version of the language was released in November, 1969. SAIL's intermediate development was the responsibility of Russell Taylor, Jim Low, and Hanan Samet, who introduced processes, procedure variables, interrupts, contexts, matching procedures, a new macro system, and other features. Most recently John Reiser, Robert Smith, and Russell Taylor maintained and extended SAIL. They added a high-level debugger, conversion to TENEX, a print statement, and records and references. 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 |