VERS(ID:3969/ver003)Set-based algorithmic languageSet-based algorithmic language, designed to make the use of V-graphs in programming straightforward. Described as being a system of which L6 is a simplest case. Lumped with SETL and MADCAP in MIT review Also significant in that it was the first system to make use of Earley's own parser, which went on to become a highly important feature of many compilers Places
People: Related languages
References: DOI Extract: Programming Languages and an Implementation Facility Programming Languages and an Implementation Facility We have presented a notion of the semantics of data structures. We would now like to explore the possibility of using this idea as the basis for a programming language. (We are, in fact, doing this with a language called VERS.) The simplest approach is just to embed the V-graph primitives in a language, extending them with some kind of control structure, subroutines, etc., that one finds in any programming language. But how does one refer to a V-graph in such a language, and what happens to such standard notions as those of variable and assignment statement? The important observation to make along these lines is that there are basically two categories of objects in a programming language--a fixed number of "static" objects whose names can be written in a program, and an arbitrary number of "dynamic" objects which are created by the program at run-time and may be referenced only through the static objects. Thus in VERS there are static and dynamic varieties of nodes, links, and atoms. Static nodes are headers for data structures whose identity cannot be changed by the program. (The symbol table header is an example of this.) Dynamic nodes are created by the CREATE primitive and are parts of data structures which can be altered (such as stack element nodes). They may be referenced only through links. Static links are links which do not come from nodes, but have an existence of their own. These would be used to represent the concept of a variable in an ordinary language. The links emanating from nodes are dynamic and represent access paths in the data structure. Similarly, a static atom is a constant, and a dynamic atom is the value of a variable or a value stored in a data structure. If we include transformations in VERS, then they can be used to specify primitive operations on the data structures and also as data structure descriptions from which information may be deduced by a compiler. Our ultimate aim is that a programmer would express his algorithm in VERS using V-graphs and being as unconcerned with implementation as he likes. Then the compiler would process his data structure descriptions, determine a good implementation, and carry it out. However, we are not at the point where this is feasible. We do not yet understand enough about alternative implementations of V-graphs or the process of specifying an implementation or the mathematical properties of V-graphs. Therefore, in order to gain some experience with these things and also so that such a language may be programmer may describe the implementation of a data structure whose semantics is expressed by V-graphs. Higher level languages have for a long time given us the ability to write programs in a way which avoids some of the extraneous details and bookkeeping which must go on in the computer. In the process of doing away with the bookkeeping, however, most languages take away from the programmer some control over implementation which he may need for efficiency. In fact, because of this, low level systems-programming languages have developed [12-15] in order to restore some of this control (especially over data structures) without reverting to machine language. However, these languages usually lack much of the power of higher level languages. Our concept of an implementation facility is an attempt to provide the advantages of both. A programmer first writes his algorithm in VERS, obtaining the advantages of V-graphs and a higher level language. He can debug the algorithm by using a general default implementation which is good for any V-graph, supplied by the VERS compiler. He may then, if he wants, insert declarations and/or code into his program to specify how the data structures are to be implemented. Ideally, he may go into as much detail as he needs to achieve the efficiency he wants. He may experiment with several implementations in order to get the best one for his needs, this being feasible because it does not mean rewriting the basic code of the program as it would ordinarily. He may even ignore implementation entirely if the program is already good enough for his needs. This idea has been used successfully in a very limited way in the field declaration facility of L6 [11], which is a special case of our system. It has been proposed on a larger scale by Balzer [16], but not implemented. In addition, although we agree with his concept of an implementation facility, we much prefer V-graphs to his data structures (hierarchical ordered sets). The basic idea of the implementation facility is that one specifies the implementation of a high level V-graph in terms of lower level V-graphs which more closely (or exactly) reflect the structure of the data in the machine. In the most general case, this means that for each node-type and for each possible kind of link from that node-type, the programmer writes an algorithm in VERS to implement each of the primitives which work on that node-type and link. Thus the "primitives" are no longer primitives but are instead subroutines (or macros) for the next lower level of implementation. At the lowest level, each node, link, and atom in the V-graph corresponds exactly to some allocatable resource in the machine. For current machines, we have decided that a node should correspond to a bead [23] (a contiguous block of words in memory), each of its links should correspond to a field of bits within this block, and each atom should correspond to a pattern of bits. At this level, the primitives do not need to be recoded. Instead the programmer just declares the size of the bead for the node and the locations of the fields for the links, much as in L6[12]. in [ACM] CACM 14(10) October 1971 view details in [ACM] CACM 15(12) 1972 view details There are three kinds of V-graph objects: nodes, links, and atoms. These objects serve to assign structure to a set of data items and to define access paths to the items. A set of primitives for manipulating V-graphs is suggested, and examples of their use on different data structures are given. The notion of a transformation on V-graphs is defined; it is seen that a data structure consists of a set of initial V graphs and a set of transformations. Thus, a description of a stack includes the V-graph representation for an empty stack and transformations for pushing and popping stack items. An implementation facility is described, which could be a part of a programming language based on V-graphs. The basic idea is that the programmer would describe the implementation of a highlevel V- graph in terms of lower level V-graphs; at the looniest level, V-graph objects would correspond to some allocatable machine resource. A mathematical formalism for V-graphs is presented, and some questions about general classes of data structures are listed. The author notes several shortcomings haying to do with V-graph representation of array-like structures, and suggests extensions which might solve them. in ACM Computing Reviews 13(02) February 1972 view details in ACM Computing Reviews 13(02) February 1972 view details Extract: VERS Earley (1973) proposes four data structures which are very similar to those used in SETL and MADCAP: - Tuples (fixed collections of heterogeneous objects which can be accessed by name) - Sets (unordered non-repeating collections of objects) - Relations (sets of tuples) - Sequences (ordered collections of objects) Earley's major point is that these structures allow a relational level of description in which data structures may be described in terms of essential relationships between the data items, ignoring the particular access paths between them. This prescription clearly states one of our principles of nonprocedural programming. in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details in Proceedings of the International Conference on Reliable software Los Angeles, California 1975 view details |