Publications

We present a graph-based model of a generic type system for an OO language. The type system supports the features of recursive types, generics and interfaces, which are commonly found in modern OO languages such as Java. In the classical graph theory, we define type graphs, instantiation graphs and conjunction graphs that naturally illustrate the relations among types, generics and interfaces within complex OO programs. The model employs a combination of nominal and anonymous nodes to represent respectively types that are identified by names and structures, and defines graph-based relations and operations on types including equivalence, subtyping, conjunction and instantiation. Algorithms based on the graph structures are designed for the implementation of the type system. We believe that this type system is important for the development of a graphbased logical foundation of a formal method for verification of and reasoning about OO programs.

Graph transformation techniques, and the Double-Pushout approach in particular, have been successfully applied in the modeling of concurrent systems. In this area, a research thread has addressed the definition of concurrent semantics for process calculi. In this paper, we show how graph transformation can cope with advanced features of service-oriented process calculi, such as several logical notions of scoping (like sessions and pipelines) together with the interplay between linking and containment. This is illustrated by encoding CaSPiS, a recently proposed process calculus with such sophisticated features. We show how to represent the congruence and reduction relations between CaSPiS processes by exploiting concurrent graph transformations over hierarchical graphs.

Theories of graphs and graph transformations form an important part of the mathematical foundations of computing, and have been applied in a wide range of areas from the design and analysis of algorithms to the formalization of various computer systems and programs. In this thesis, we study how graphs and graph transformations can be used to model the static structure and dynamic behavior of object-orientated and service-oriented systems.

Our work is mainly motivated by the difficulty in understanding and reasoning about object-orientated and service-oriented programs, which have more sophisticated features compared with traditional procedural programs. We show that the use of graphs and graph transformations provides both an intuitive visualization and a formal representation of object-orientated and service-oriented programs with these features, improving people’s understanding of the execution states and behaviors of these programs.

We provide a graph-based type system, operational semantics and refinement calculus for an object-oriented language. In this framework, we define class structures and execution states of oo programs as directed and labeled graphs, called class graphs and state graphs, respectively. The type system checks whether a program is well-typed based on its class graph, while the operational semantics defines each step of program execution as a simple graph transformations between state graphs. We show the operational semantics is type-safe in that the execution of a well-typed program does not “go wrong”. Based on the operational semantics, we study the notion of structure refinement of oo programs as graph transformations between their class graphs. We provide a few groups of refinement rules for various purposes such as class expansion and polymorphism elimination and prove their soundness and relative completeness.

We also propose a graph-based representation of service-oriented systems specified in a service-oriented process calculus. In this framework, we define states of service-oriented systems as hierarchical graphs that naturally capture the hierarchical nature of service structures. For this, we exploit a suitable graph algebra and set up a hierarchical graph model, in which graph transformations are studied following the well-known Double-Pushout approach. Based on this model, we provide a graph transformation system with a few sets of graph transformation rules for various purposes such as process copy and process reduction. We prove that the graph transformation system is sound and complete with respect to the reduction semantics of the calculus.

We present a graph-based model of a generic type system for an oo language. The type system supports the features of recursive types, generics and interfaces, which are commonly found in modern oo languages such as Java. In the classical graph theory, we define type graphs, instantiation graphs and conjunction graphs that naturally illustrate the relations among types, generics and interfaces within complex oo programs. The model employs a combination of onymous and anonymous nodes to represent respectively types that are identified as names and structures, and defines graph-based relations and operations on types including subtyping, equivalence, conjunction and instantiation. Algorithms based on the graph structures are designed for the implementation of the type system. We believe that this type system is important for the development of a graph-based logical foundation of a formal method for verification of and reasoning about oo programs.

Graph transformation techniques, and the Double-Pushout (DPO) approach in particular, have been successfully applied in the modeling of concurrent systems. In this area, a research thread has addressed the definition of concurrent semantics for process calculi. In this report, we provide a theory of graph transformations for service programming with sessions and pipelines. The theory shows how graph transformation can cope with advanced features of service-oriented computing, such as several logical notions of scoping (like sessions and pipelines) together with the interplay between linking and containment. This is illustrated by encoding CaSPiS, a recently proposed process calculus with such sophisticated features. We first exploit a graph algebra and set up a graph model that supports DPO graph transformations. Then, we show how to represent CaSPiS processes as hierarchical graphs in the graph model and their behaviors as transformation rules over these graphs. Finally, we provide the soundness and completeness results of these rules with respect to the reduction semantics of CaSPiS.

Graph transformation techniques, and the Double-Pushout approach in particular, have been particularly successful in the modeling of concurrent systems. In this area, a research thread has addressed the definition of concurrent semantics for process calculi. In this paper, we show how graph transformation can cope with advanced features of service-oriented process calculi, such as several logical notions of scoping (sessions, pipelines), pattern matching together with the interplay between linking and containment. This is illustrated by encoding CaSPiS, a recently proposed process calculus with such sophisticated features. We show how to handle congruence rules and reduction rules using a suitable notion of hierarchical graphs. The main result proves soundness and completeness of the encoding with respect to congruence.

 An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class declarations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams as directed labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such a structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement, as an extension to the classical theory of data refinement, in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation. 

An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class declarations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams asdirected labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such a structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement, as an extension to the classical theory of data refinement, in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation. 

We present a mathematical model of class graphs, object graphs and state graphs which naturally capture the essential oo features. A small-step operational semantics of oo programs is defined in the style of classical structural operational semantics, in which an execution step of a command is defined as a transition from one state graph to another obtained by simple operations on graphs. To validate this semantics, we give it an implementation in Java. This implementation can also be used for simulation and validation of oo programs, with the visualization of state graph transitions during the execution. A distinct feature of this semantics is location or address independent. Properties of objects and oo programs can be described as properties of graphs in terms of relations of navigation paths (or attribute strings).

 We present a graph-based model of a type system and an operational semantics for an object-oriented programming language. In this model, we define class graphs, object graphs and state graphs that naturally capture the essential oo features. The type system checks whether an expression, a command or a program is type-correct, based on its class graph and type context, which is a graph too. The operational semantics is a small-step one defined in the style of classical structural operational semantics, in which an execution step of a command is defined as a transition from one state graph to another obtained by simple operations on graphs. Both the type system and the semantics are fully implemented. On the one hand, working out the implementation has helped us to understand the semantics to make sure our definition is correct. On the other hand, the implementation will be used as the basis for our future development of simulation and validation techniques for oo programs, with the visualization of stage graph transitions during the execution. The motivation of this work is the development of techniques for reasoning about properties of oo programs stated in a logic of graphs. We show the promises and feasibility of this by formulating a range of assertions about objects.

In UML, the general structure of objects, their attributes and relations are modeled as a class graph, and an instance of a class graph is defined as an object graph. The class graph of a system determines the general properties of objects and how objects collaborate in realizing a use case. In this paper, we define class graphs and their object graphs as directed labelled graphs, and investigate in a graph theoretical approach what changes in the object structure maintain the capability of providing services. We define the general notion of structure refinements. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is the resulting class graph should be able to provide at least as well as the original graph. We give a small set of structure refinement rules that is proved to be sound and complete for a kind of structure refinement.

 An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class decorations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams as directed labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such as structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation. Keywords: Class graph, Object graph, Graph transformation, Normal form, Object-orientation, Structure refinement.

 Being a successful technique in software practice, Object Orientation (OO) is a hot topic in academic research fields. Among many formalisms, rCOS, a refinement calculus of object-oriented systems based on Unifying Theories of Programming (UTP), has been proven a promising one in the sense of its applications to incremental software constructions, the formal use of UML, etc. However, equipped with a semantics reasoning on both static and dynamic properties, rCOS is not designed for static checking. We believe introducing static checking will extend the power of rCOS. In this paper, we develop a type system for rCOS and prove some type safety theorems. To make the theoretical results of this paper convincible and easy to be understood, we follow the traditional approaches of type systems construction. That is, we use an operational semantics as the basic explanation of rCOS language in spite of the fact that rCOS is originally developed in a denotational framework.

 Abstract: In UML, the general structure of objects, their attributes and relations are modeled as a class graph, and an instance of a class graph is defined as an object graph. The class graph of a system determines the general properties of objects and how objects collaborate in realizing a use case. In this paper, we define class graphs and their object graphs as directed labelled graphs, and investigate in a graph theoretical approach what changes in the object structure maintain the capability of providing services. We define the general notion of structure refinements. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is the resulting class graph should be able to provide at least as well as the original graph. We give a small set of structure refinement rules that is proved to be sound and complete for a kind of structure refinement. Keywords: Object systems, class graphs, object graphs, labelled graphs, graph transformations, refinement

Being a successful technique in software practice, object orientation (OO) is a hot topic in academic research fields. Among many formalisms, rCOS, a refinement calculus of object-oriented systems based on unifying theories of programming (UTP), has been proven a promising one in the sense of its applications to incremental software constructions, the formal use of UML, etc. However, equipped with a semantics reasoning on both static and dynamic properties, rCOS is not designed for static checking. We believe introducing static checking will extend the power of rCOS. In this paper, we develop a type system for rCOS and prove some type safety theorems. To make the theoretical results of this paper convincible and easy to be understood, we follow the traditional approaches of type systems construction. That is, we use an operational semantics as the basic explanation of rCOS language in spite of the fact that rCOS is originally developed in a denotational framework.