ALLA(ID:7064/all007)Graph-theoretical language by Wolfberg, "part of an interactive graphics system and allows the solution of graph problems with the aid of a display unit" References: Language Overview The first pass in the design consisted of a general specification of the language primitives. It was decided that strictly set theoretic development of graph theory would allow for considerable flexibility in the selection of storage representations for different graph structures (see [5] for a motivation of this decision). Therefore two primitives that were included in the language were sets and graphs. Sets, however, were placed in GRAAL mainly for the purpose of defining graphs and their specific design was motivated by this. Their introduction into the language generated the need for several set operations. These include the standard set union (U), intersection (A), difference (-) , and symmetric sum (A). There is a subset operator which constructs the subset of all elements of a set that satisfy a specified boolean relation. Tnere are some comn relational operators such as =, f, and5 which return the value true if t ~ o sets are equal, not equal or one is a subset of the other, respectively, and the value false otherwise. There are a variety of graph structures available in GRAAL distinguished by the family of graph operators provided for constructlng and traversing each specific structure. The present graph dsfinitions include a directed pseudograph, an undirected pseudograph, a directected graph in node form and an undirected graph in node form. We use the generic term "graph" for all of these. The graph construction operators consist of an operator which would attach a node, arc, node and arc or two nodes and their connecting arc to a graph, and a detach operator which would remove a set of nodes for arcs from a graph. Both of these operators return graphs as a result. There are two graph operators, nodes and arcs, which return the set of all nodes and the set of all arcs in a graph, respectively. The graph connectivity operators take as an argument a set expression which designates either a set of nodes or of arcs of the specified graph. The various possible operators presently included in the language are the incidence operator inc, the positive and negative incidence operators pinc and ninc, the star operator star, the positive and negative star operators pstar and nstar, the bound operator bd, the positive and negative boundary operators pbd and nbd, the coboudary operator cob, the positive and negative coboundary operators pcb and ncb, the adjacency operator a, and the positive and negative adjacency operators padi and adi. Each one of these operators is associated specific types of graphs. The data structures decided upon for the language were arrays and lists. It was felt that these two structures could handle the static and dynamic storage needs of the type of problems attacked by the language. The control structure decided upon was the stardard algebraic language control structure since the purpose of the language was for writing readable and easily expressed algorithms. In fact, it was felt that the language should be embedded in a standard algebraic language format which includes the normal integer and real variables and integer and real arithmetic. This defines the basic outline of language features. Almost all, except for the set and graph constructs, are common to a large number of stardard programing largauages, such as ALGOL or FORTRAN. In fact, GRAAL was originally designed as an extension to ALGOL and a first implementation of the language was done as an extension to an existing FORTRAN compiler on the UNIVAC 1108. What is needed is a closer look at the definition of sets and graphs. The first questions are what is a set in the context defined here, and whit does lt consist of? That is, where do sets fit into the definition of an algebraic programming language and what are reasonable ways of defining them for their use in the definition of graphs? There are several other programing languages that include sets among their constructs. SETL and SETTEL are both languages which were designed for writing general set-theoretic algoritiuns. In SETL a set is basically considered as an unstructured data structure whose elements may be a variety of objects such as integers or even other sets. In SETTEL a set is defined over some user'specified miverse which might be the integers or integers and reals, etc. MADCAP, a language which was primarily defined for combinatorial computing, treats sets as subsets of the natural numbers. There are also several other languages that have set constructs of some form or other. For GRAAL it was decided at the beginning that a set would be a data type rather than a structure. The basic philosophy that guided this decision was that the data types of a language represented the basic set of primitives of the language. That is, they represent those data elements and their respective operators which are used at the basic level of the algorithms written in that language. Thus it was agreed that sets and the set operations were part of the basic primitive notions of GRAAL. This is not a new approach, although it appears to be with respect to sets. It attempts to separate the concepts of data types and data structures into disjoint categories in a particular language, depending upon the applications addressed by that language. Data types are the primitive data elements of the application area and represent the lowest level upon which the algorithm is based. For example, in the standard algebraic languages, FORTRAN and ALGOL, integer and real are the basic data types since they are the basic units of data used by algorithms in the languages. These data types may be thought of as unstructured data types because their structure (which is usually defined by the machine wordsize) is fixed. There are basic data types which do have a more variable, machine-defined structure. Strings in SNOBOL, for example, are a structured data type. In fact, there is a very close analogy between strings in SNOBOL and sets in GRAAL. They both have a definite structure whose internal definition is hidden from the user and immaterial to him. They consist of subelements, which are characters for strings and elements for sets. They have operators acting upon them which allow the user to access any subgroup of the elements as well as operations between them, such as concatenation for strings or union for sets. They may be stored in structures, such as arrays, whose structural design is more visible to the user because he uses the array strictly as a storage mechanism for his primitive data types. Granted that a set is a data type rather than a data structure, what is a reasonable definition of its members? They are elements, usually representing nodes or arcs, which are members of some universe of elements, just as the subelements of a string are characters which are members of some universe of characters. The difference is that the maximum size of the universe of characters is usually thought of as fixed while the universe of elements must be highly dynamic. In order to define a new element, it must be dynamically created from this universe of elements. Each element may have associated with it any number of typed properties. This permits the elements of a set or the nodes and arcs of a graph to have any number of integer, real, or string values associated with them. We my now ask a similar question about a graph. What is a graph and what is it composed of? The answer to this question is similar to the answer to the previous one. For the same reasons a graph is really a structured data type, which is composed of undeclared data elements which play the roles of nodes or arcs and are interrelated to define the particular graph structure. Extract: Model of Sets and Graphs Model of Sets and Graphs Now that some of the basic informal GRAAL design has been given, we are ready to present a high-level informal model of these concepts. The operational semantic modeling language used is an informal version of the hierarchical language HGL. Essentially HCL is a definitional facility for specifying models which may be used to describe the semantics of programing languages. The basic HGL primitives consist of (1) a set of nodes each with an associated structured value, atomic value, and a set of attributes, and (2) a set of primitive transition functions that can change the structure, atom, or an attribute associated with a node and can define and delete nodes. More specifically, each node n in HGL nay be thought of as a high-level memory cell representing a unit of information about the language. The atomic value associated with the node v(n) usually represents some nonstructured program or data element. The structured value associated with a node h(n) usually represents some language component which must be structured and whose structure is of interest. The attributes associated with a node, a(n,attribute), usually represent characteristics or properties of the unit of information contained in a node. These attributes can be thought of as a symbol table which might contain the compile time properties known about that unit of information. Extract: Conclusion For the sake of completeness, a brief discussion of a possible internal data strusturing of the universe, sets and graphs will now be given. A natural data structure for the universe of elements would be dynamic array-like structure which would permit an easy and quick ordering and accessing scheme for the elements. This can be done by using the index of the elentent in the array as its unique (integer) name. This would lead to a relatively efficient implementation of the universe and of sets. Sets could be implemented using a list type data structure because of their dynamically varying size. These lists can be ordered, however, according to the unique integer name associated with each element in the universe. This intrinsic ordering permits a great improvement in the efficiency of the set operations. Properties, like sets, should also be defined by a list stricture since there are a variable number of properties associated with each element. This tends to be efficient with respect to space but inefficient with respect to accessing speed. Graphs are essentially defined through the properties of their nodes and arcs. However the individual elements of a particular graph can be chained together across their respective property lists. For a complete description of a particular implementation, see[4]. in Proceedings of the 1974 ACM Annual Conference San Diego, November, 1974 view details |