A graph grammar approach to concurrent programming

We propose the use of graph grammars as a theory to organize programming of highly-concurrent systems. To understand the interactions among components of a concurrent system it is useful to visualize the system as dynamically changing graphs where the nodes represent concurrent components and the edges represent (the possibility of) interactions among them. Graph grammars are effective tools for translating this intuitive understanding of system behavior into formal specifications and executable concurrent programs.We claim that the use of hybrid graphical/textual languages is an important way to effectively specify and clearly understand the dynamic behavior of concurrent systems. This is because the problem is divided into two parts, the graphical part of understanding object relationships and the textual part of understanding internal object behavior. We develop theory necessary to support this division of labor. Problems that are addressed include: modifying and using existing graph grammar theory to get a formal way to express and to reason graphically about the dynamic behavior of concurrent programs, fitting both text and graphics into a unified semantic framework and building real hybrid graphical/textual languages using the theory introduced.In order to ground our ideas in the context of graph grammar research, we propose an algebraic model, $\Delta$-G scRAMMARS, and give it a semantics. $\Delta$-G scRAMMARS are reflective, concurrent and fair in production application, and incorporate a notion of Kleene star-like graph rewriting. The result is a powerful, but low-level paradigm for defining graph languages.Existing semantics that try to take both textual and graphical elements into account are text-based. In contrast, we show how graphically-based semantics can be given using $\Delta$-G scRAMMARS, and justify why this is useful. Such $\Delta$-semantics provides a coherent framework to consider both text and graphics.Finally, using $\Delta$-semantics we give the definition of a higher-level programming language. The higher-level language includes facilities for graph rewriting, message passing (synchronous and asynchronous) and imperative style programming. The methods for defining and using these facilities that mix graphical and textual concepts are supported by the graph grammar and graphical semantics base that has been developed.A tutorial introduction to graph grammars is also included.U of I OnlyETDs are only available to UIUC Users without author permissio