GRAAL(ID:7060/gra030)Graphic extension to FortranBasili, Maryland, 1972 Places People: Related languages
References: Introduction For the implementation of a graph algorithm on a computer, standard algorithmic languages, such as FORTRAN or ALGOL, are, in general, rather unsuitable. In fact, they are neither well-adapted to expressing basic graph operations, nor to describing and manipulating most of the data structures upon which these operations are defined. Although list processing languages provide for a more appropriate data structure,they tend to hide the graph theoretical nature of the algorithms besides leading to slow execution and large demands for storage. This points to the need for the development of special-purpose languages which facilitate the programming as well as the publication of graph algorithms. In this article we propose such a language-named GRAAL (GRAph Algorithmic Language)-for use in the solution of graph problems of the type primarily arising in applications. These problems involve a wide variety of graphs of different types and complexity; and one of the objectives in the design of GRAAL was to allow for this range of possibilities with as little degradation as possible in the efficient implementation and execution of an algorithm designed for a specific type of problem. Our second objective relates to the need for a language which facilitates the design and communication of graph algorithms independent of the computer. In line with this, we aimed at ensuring a concise and clear description of such algorithms in terms of data objects and operations natural to graph theory, that is, without introducing too many instructions required mainly by programming considerations. In order to meet these objectives, GRAAL was based on a set algebraic model of graph theory which allows for considerable flexibility in the selection of the storage representation for different graph structures. The use of sets in graph algorithms is, of course, entirely natural, if only to express such concepts as the "set of all arcs incident with s node". However, in the development of a set oriented data structure for graphs one soon faces complications with ordered pairs of elements as they arise, for instance, in the usual definition of arcs as node pairs. Childs [2], [3] has described a rather general approach to set theoretic data structures. For the design of GRAAL we proceeded more simply by using a model of graph theory in which the basic data objects are the elements of the power sets of the node and arc set. Algebraic structures are imposed on these power sets and the basic graph operators defining the structure of the graph represent morphisms between these algebraic structures. GRAAL is a modular language in the sense that the user can specify which basic graph operators are available for any graph. This provides for the possibility of using various different storage representations for a graph structure in line with the specific nature of the problem at hand. In view of its set theoretic foundation, GRAAL incorporates sets as a new data type on the same level as integer, real, or Boolean variables. In order to allow for an effective implementation of the standard set operations, sets are assumed to contain only distinct elements which are ordered by an internal key. This key constitutes the unique internal identification for each basic element and each of these elements can in turn be used in any graph as either a node or an arc. In addition to the data type "set" a data structure "list" has also been provided in GRAAL to allow stacking. At present GRAAL is defined as an extension of the revised ALGOL 60 language. However, the language itself is relatively independent of ALGOL and can be redefined in terms of other algorithmic languages; in fact, a FORTRAN-based version is presently being developed. During the past years, various graph algorithmic languages have been described in the literature. One of the earliest efforts along this line appears to have been a language of Tabory which was based on FORTRAN I1 and FLPL (FORTRAN-compiled List Processing Language). More recently, Friedman et al. (see also Friedman as well as Pratt and Friedman) developed an extension of LISP 1.5, called GRASPE 1.5, to allow graph processing on a list processing system. Another list-processing oriented language, HINT, has been described by Hart. The GTPL language of Read et al. (see also Read) is a system of FORTRAN II subroutines designed primarily for use in conjunction with theoretical studies of graphs. The graph language ALLA of Wolfberg, is a part of an interactive graphics system and allows the solution of graph problems with the aid of a display unit. As an aid in his work on the efficiency of graph algorithms, Chase developed a graph algorithmic software package, GASP, consisting of a library of PL/l procedures and run-time macros. Finally, we mention Crespi-Reghizzi and Morpurgo, who defined their graph language, GEA, as an extension of ALGOL 60. Undoubtedly, there are other similar efforts not known to us. Also, our list does not include languages which operate only on special types of graphs, as, for instance, the TREETRAN system of Pfaltz for the manipulation of rooted trees. in BIT 12, 1971. view details in BIT 12, 1971. view details Extract: Language Overview 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 Extract: Introduction Introduction Designing a high-level programming language is at best a difficult task. The designer must keep the entire design in mind at the top level in order to decide what the various components of the language should be, what they should look like, and what effect they have upon one another. And if he should settle on a design, and then change some aspect of it, he must be concerned with the effect this would have on the rest of the language. These problems are made more difficult if any of the features of the language are 'new' or have never been used in combination with one another. Unfortunately, as with most new and large projects, there is not much guidance available to the designer. There is little information in the literature on what approach to take. Experience with other language designs is helpful but where does one start? What is really needed is a set of tools to give the designer as much control over the project as possible. This paper is an attempt at systematizing language design based in part on a design and implementation experience with GRAAL [I-31, a high-level programming language for use in the solution of graph problems primarily arising in applications. A sequence of hierarchical semantic models is recommended for designing the language and its compiler; and the approach is demonstrated by application to the set and graph features of GRAAL. This sequence of hierarchical semantic models, specified in the hierarchical graph language HGL, is in effect a sequence of very high-level machines, each of which is a refinement of its predecessor, with the data and control structures for the new machine being more highly specified. This permits language design to be approached in a topdown manner. The next section contains a description of the approach. Sections 3, 5 and 6 describe the application of the approach to GRAAL, and Section 4 contains an informal description of the HGL semantic model used in the process. in Computer Languages 1(3) September 1976 view details in Graphen-Sprachen und Algorithmen auf Graphen, Applied Computer Science 1, Carl Hanser Verlag, 1976 view details |