Higher-order graph rewriting systems

Abstract

Programas sofrem diversas modificações ao longo das etapas de desenvolvimento, implantação e manutenção. A evolução de um software pode ter várias causas: correção de erros, inclusão de novas funcionalidades ou até mesmo, como é o caso de programas orientados a aspecto, transformações estruturais podem fazer parte da semântica do sistema. Apesar de modificações serem comuns, não é tarefa trivial prever como estas afetam o comportamento dos programas, já que os componentes de software normalmente interagem de forma complexa, o que faz com que mesmo pequenas alterações possam introduzir comportamentos indesejados. Transformação de grafos, também conhecida como reescrita de grafos, é um importante paradigma para modelagem e análise de sistemas. Modelos baseados em transformação de grafos, como gramáticas de grafos, permitem uma modelagem ao mesmo tempo intuitiva e com semântica precisa, permitindo a aplicação de técnicas de análise como verificação de modelos e análise de par crítico no estudo do comportamento de sistemas. A teoria por trás de transformação de grafos vem sendo desenvolvida a várias décadas, e atualmente está descrita de uma forma bastante abstrata. Contudo, ainda não possui uma definição natural de reescritas de alta ordem, que facilitaria a definição de evolução de especificações compostas por regras de reescrita de grafo, tais como gramáticas de grafos. Nesta tese são abordadas a modelagem e a análise de sistemas sob modificações programadas no contexto de gramáticas de grafos. A generalização da abordagem de pushout duplo para reescrita de grafos é utilizada como o princípio geral para descrever, simultaneamente, a semântica do sistema e modificações estruturais. Para tal, introduzimos uma noção de reescrita de segunda ordem para modificar a estrutura de regras de transformação de grafos, e usando isso, definimos modelos equipados simultaneamente de regras de primeira e segunda ordem, chamados gramáticas de grafos de segunda ordem. Através destes modelos podemos representar simultaneamente transformações estruturais e execução do sistema, e relacionar formalmente ambos tipos de reescrita. Também propomos novas técnicas para investigar o efeito da modificação de regras sobre a aplicação destas. Finalmente, como um exemplo de aplicação da teoria, caracterizamos construções de sistemas orientados a aspectos através de gramáticas de grafos de segunda ordem, e discutimos como utilizar as novas técnicas para estudar o efeito da combinação aspectual sobre o sistema inicial.

Software systems are not static entities: they usually undergo several changes along their development and maintenance cycles. Software evolution may be required for several reasons, such as the inclusion of new functionalities, the correction of errors or even as part of the system semantics, as it is the case of aspect-oriented systems. However, it is usually not trivial to foresee how structural changes can affect the system behaviour, since system components often interact in very complex ways, and even trivial modifications may introduce new problems. Graph transformation, also known as graph rewriting, has been used throughout the years as an important paradigm for system modelling and analysis. Models based on graph transformation, such as graph grammars, allow an intuitive but formal representation of the system behaviour, allowing the usage of analysis techniques such as model checking and static analysis of rule interaction. The theory behind graph transformation is quite general, and has been studied since the 1970s. However, it still lacks a general notion of higher-order rewriting that would allow a natural definition of model transformations for graph grammars. The lack of general second-order characterization presents difficulties for employing graph grammars as targets of model transformations, and studying how model transformations affect their natural behaviour. In this thesis we address the problem of modelling and analysing systems undergoing programmed modifications in the context of graph grammars. We use the generalization of the double-pushout approach for graph rewriting as a principle for defining simultaneously the system semantics and structural modifications. To achieve this, we introduce a notion of second-order graph rewriting that acts on graph transformation rules. Based on secondorder rewriting we are able to define second-order graph grammars, models equipped with a first-order layer, representing the original system execution, and a second-order layer, representing a model transformation. Using second-order graph grammar we can encode simultaneously model transformations and system execution, allowing us to formally relate them. Moreover, we propose new techniques to investigate the effect of rule modification over their effect on graphs. As an application example, we characterize aspect-oriented constructions for graph grammars, and discuss how to relate the aspect weaving layer with the base system semantics.