A graph grammar approach to concurrent programming
Goering, Steven Kent
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20654
Description
Title
A graph grammar approach to concurrent programming
Author(s)
Goering, Steven Kent
Issue Date
1990
Doctoral Committee Chair(s)
Kaplan, Simon M.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Language, Linguistics
Computer Science
Language
eng
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
