HGL(ID:7063/)Hierarchical graph languageSuperset of GRAAL developed as a semantic means of expressing languages. Used to make a definition for SIMPL-S at University of Maryland People: Related languages
References: in SIGPLAN Notices 8(11) November 1973 Proceedings of the ACM-IEEE symposium on High-level-language computer architecture 1973, College Park, Maryland, United States view details 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 In recent years there has been a phenomenal growth of interest in networks of computers sharing both data and programs. For examnle, Cmdr. Grace Hopper has advocated a hierarchical network of minicomputers to perform the data processing function in which the tasks to be done would be distributed over the network, with only sunmmry or extract information being passed from one level to another. While the hardware exists to build such a network, the software mechanisms to effectively (from both a time and cost viewpoint) control such a network have not yet been developed. At the Computer Science Center of the University of Maryland a distributed operating system, which is independent of the specific number and hardware of the particular con~outers it is running on, is being developed and imDlemented. Supporting this project is the develovment of two linguistic tools: the design and implementation of a systems programming language called SIMPL and the use of formal semantics in the specification of both SIMPL and the distributed operating system. So far, each of these three elements has had a considerable effect on the others. The operating syste~ will be coded in SIMPL. In fact, this language is intended to be used for systems work on both the Center's UNIVAC 1108 and DEC PDP-ii/45. Unlike ALGOL 68, SIMPL itself is not an attenmt to push forward the boundaries of language design. Rather it is an attempt to incorporate what has been learned about programming and algebraic languages since the introduction of FORTRAN in the late 1950's. As a language, SIMPL resembles both BLISS and NUCLEUS. Extract: Reuirements of SIMPL In the design of the language, a number of sometimes conflicting goals had to be resolved. These goals included the following: i. SIMPL was based on the principles of structured programming. Certain features, notably the go to statement, were abolished from the language. 2. The language was to serve as a student progranming language. It must be simple and easy-to-learn and must encourage good progranming habits. 3. The language must be free-format and yet have a simple syntax. Because of student difficulties in learning ALGOL, the obnoxious semicolon was abolished. 4. The language was to be used as a systems proqramming language. It thus includes both bit and shift operators. However, in order to preserve machine-independence, it did not include the capability of addressing registers or of inserting machine language instructions. 5. As a systems language, only features which could be efficiently implemented were allowed. Thus, for example, block structure was not included in SIMPL. 6. The language will be used for the verification of programs. This influenced the design considerably. For examnle, functions may not have side-effects and may not be recursive. 7. Later versions of the language will include an assert statement. Assertions which cannot be verified at compile time will cause run time tests to be inserted when compiled in debugging mode. 8. Automatic traceback and subscript checking are provided in the compiler. various trace statements can be compiled or omitted depending on the trace mode selected. Features of the language include both internal and external procedures, and aritbnetic assignment, if, case, call, while, return, and exit statements. Simple parameters are passed either by value or by reference and arrays are massed by reference. Simple variables and arrays may be declared external. The usual arithmetic operators have been included but only integer arithmetic and one dimensional arrays have been implemented. At the current time two versions of SIMPL are running on the UNIVAC 1108; one produces code for the 1108, while the other for the PDP-11. To minimize the differences between the two implementations, both a reference language and a hardware language have been defined. Extract: The nature of HGL The second major element of this effort is research in the area of semantic models. A language called HGL (Hierarchical Graph Language) has been develoned based on the earlier work on H-graphs due to Pratt (1969) and Basili (1970). HGL is essentially a structured programming model; despite this, it is capable of modeling any programming language feature, including go to statements. In HGL the basic structure is a graph. The contents of a particular node can be either a data item or a graph (possibly the one containing this node). In addition, a graph may have attributes associated with it; an important attribute of graph is its entry node. The basic operators of HGL are the basic graph operators, such as positive adjacency, positive incidence, etc., extended to hierarchical graphs. As a language HGL is functional and LISP-like. The principal advantages of HGL over VDL is that it preserves the natural program topology as a graph and that graph structures are a more natural representation of data structures than the tree structures of VDL. In order to cormoare the two, formal definitions of SIMPL have been produced in both HGL and VDL. Several definitions were produced in HGL and evaluated as implementation strategies. In fact, this should be a major use of a model and of a formal definition. This was one of the major defects of VDL, however; the definition developed depended on a dump mechanism (as in the formal definition of PL/I) even though this was totally inappropriate for a non-block structured language. The best HGL model, on the other hand, relied on a more natural stack definition. The use of HGL in modeling various language constructs has had a major impact on the evolution of SIMPL. For example, the study of various models of block structure in HGL led to the conclusion that block structure is an unnecessarily complicated mechanism to achieve independence of names. Hence, this feature was not included in SIMPL, which relies instead on named procedures. It was felt that the latter was more in keeping with the precepts of structured programming especially with regard to limiting the length of a given routine (as advocated by E. Dijkstra and H. Mills). Another use of HGL will be a proof of correctness of the implementation of SIMPL using the twin model approach as developed by the IBM Vienna group. in Hamlet, R. G. and Zelkowitz, M. V. "SIMPL systems programming on a minicomputer", pp203-206 view details 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 |