Set-based algorithmic language 

Set-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

Related languages
DPL => VERS   Influence
L6 => VERS   Superset
Mem-theory => VERS   Influence
VERS => CLU   Influence
VERS => VERS2   Evolution of

  • Earley, J. "VERS - An extensible language with an implementation facility" Computer Science Dept U. of California, Berkeley, 1969. view details
  • Earley, J. and Caizergues, P. VERS Manual. Comput. Sci. Dep., U. of California, Berkeley, 1971. view details
  • Earley, Jay "Toward an understanding of data structures" view details Abstract: This paper presents a notation and formalism for describing the semantics of data structures. This is based on directed graphs with named edges and transformations on these graphs. In addition, and implementation facility is described which could be part of a programming language, which allows a programmer who has expressed the semantics of an algorithm in terms of the graphs to then specify the implementation of some of his data structures in order to gain efficiency.
    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
  • Earley, Jay and Caizergues, Paul "A method for incrementally compiling languages with nested statement structure" pp1040-1044 view details Abstract: A method of incremental compilation is presented which applies especially to programming languages in which statements can be nested (such as Algol and PL/I). The method permits editing of the source language using a general purpose text editor, and incremental processing of changes without frequent recompilation of entire routines. The essential points of the method are: (1) the syntax of the language is restricted insofar as which constructs may occur on lines; (2) an internal data structure (called the skeleton) is maintained to represent the statement structure; (3) the recompilation is partially batched in the sense that recompilation of modified lines does not occur until the last of a set of editing commands has been received; and (4) the parsing and compilation are factored into two parts, that done on individual lines and that done globally to handle the relationships between the lines. DOI
          in [ACM] CACM 15(12) 1972 view details
  • Leinius, R. P. review of Early 1971 view details Abstract: This paper presents a system for describing the semantics of data structures. The central idea is that the semantics of data structures may be represented by directed graphs vith named edges (V-graphs).

    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
  • Earley, J. "Relational level data structures for programming languages", Acta Informatica, V. 2 (1973), p. 293-309. view details
          in ACM Computing Reviews 13(02) February 1972 view details
  • Leavenworth, Burt M.; Sammet, Jean E. "An overview of nonprocedural languages" pp1-12 view details Abstract: This paper attempts to describe some of the basic characteristics and issues involving the class of programming languages commonly referred to as ?nonprocedural? or ?very high level?. The paper discusses major issues such as terminology, relativeness, and arbitrary sequencing. Five features of nonprocedural languages are described, and a number of specific languages are discussed briefly. A short history of the subject is included.
    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
  • Liskov, Barbara and Zilles, Stephen "Specification techniques for data abstractions" pp72-87 view details Abstract: The main purposes in writing this paper are to discuss the importance of formal specifications and to survey a number of promising specification techniques. The role of formal specifications both in proofs of program correctness, and in programming methodologies leading to programs which are correct by construction, is explained. Some criteria are established for evaluating the practical potential of specification techniques. The importance of providing specifications at the right level of abstraction is discussed, and a particularly interesting class of specification techniques, those used to construct specifications of data abstractions, is identified. A number of specification techniques for describing data abstractions are surveyed and evaluated with respect to the criteria. Finally, directions for future research are indicated
          in Proceedings of the International Conference on Reliable software Los Angeles, California 1975 view details