Complex systems are naturally understood as combinations of their distinguishing characteristics or \definit{features}. Distinct features differentiate between variations of configurable systems and also identify the novelties of extensions. The implementation of a conceptual feature is often scattered throughout an artifact, forcing designers to understand the entire artifact in order to reason about the behavior of a single feature. It is particularly challenging to independently develop novel extensions to complex systems as a result. This dissertation shows how to modularly reason about the implementation of conceptual features in both the formalizations of programming languages and object-oriented software product lines. In both domains, modular verification of features can be leveraged to reason about the behavior of artifacts in which they are included: fully mechanized metatheory proofs for programming languages can be synthesized from independently developed proofs, and programs built from well-formed feature modules are guaranteed to be well-formed without needing to be typechecked. Modular reasoning about individual features can furthermore be used to efficiently reason about families of languages and programs which share a common set of features. / text

This thesis presents a component-based approach to proving the correctness of programs involving pointers. Unlike previous work, our component-based approach supports modular reasoning, which is essential to the scalability of systems. Specifically, we specify the behavior of a graph-marking algorithm known as the Schorr-Waite algorithm, implement it using a component that captures the behavior and performance benefits of pointers, and prove that the implementation is correct with respect to the specification. We use the Resolve language in our example, which is an integrated programming and specification language that supports modular reasoning. The behavior of the algorithm is fully specified using custom definitions, pre- and post-conditions, and a complex loop invariant. Additional operations for the Resolve pointer component are introduced that preserve the accessibility of a system. These operations are used in the implementation of the algorithm. They simplify the proof of correctness and make the code shorter. / Master of Science

Aspect-oriented programming (AOP) aims to enhance modularity and reusability in software systems by offering an abstraction mechanism to deal with crosscutting concerns. But, in most general-purpose aspect languages aspects have almost unrestricted power, eventually conflicting with these goals. This work presents Effective Aspects: a novel approach to embed the pointcut/advice model of AOP in a statically-typed functional programming language like Haskell; along two main contributions. First, we define a monadic embedding of the full pointcut/advicemodel of AOP. Type soundness is guaranteed by exploiting the underlying type system, in particular phantom types and a new anti-unification type class. In this model aspects are first-class, can be deployed dynamically, and the pointcut language is extensible, therefore combining the flexibility of dynamically-typed aspect languages with the guarantees of a static type system. Monads enable us to directly reason about computational effects both in aspects and base programs using traditional monadic techniques. Using this we extend the notion of Open Modules with effects, and also with protected pointcut interfaces to external advising. These restrictions are enforced statically using the type system. Also, we adapt the techniques of EffectiveAdvice to reason about and enforce control flow properties as well as to control effect interference. We show that the parametricity-based approach to effect interference falls short in the presence of multiple aspects and propose a different approach using monad views, a novel technique for handling the monad stack, developed by Schrijvers and Oliveira. Then, we exploit the properties of our model to enable the modular construction of new semantics for aspect scoping and weaving. Our second contribution builds upon a powerful model to reason about mixin-based composition of effectful components and their interference, based on equational reasoning, parametricity, and algebraic laws about monadic effects. Our contribution is to show how to reason about interference in the presence of unrestricted quantification through pointcuts. We show that global reasoning can be compositional, which is key for the scalability of the approach in the face of large and evolving systems. We prove a general equivalence theorem that is based on a few conditions that can be established, reused, and adapted separately as the system evolves. The theorem is defined for an abstract monadic AOP model; we illustrate its use with a simple version of the model just described. This work brings type-based reasoning about effects for the first time in the pointcut/advice model, in a framework that is expressive, extensible and well-suited for development of robust aspect-oriented systems as well as a research tool for new aspect semantics.

La programmation orientée aspect (AOP) vise à améliorer la modularité et la réutilisation des couches logiciels en proposant un mécanisme d’abstraction pour faire face aux préoccupations transversales. Cependant, dans la plupart des langages d’aspects généralistes, les aspects ont un pouvoir presque illimité, rentrant éventuellement en conflit avec ces objectifs. Dans ce travail, nous présentons Effective Aspects : une nouvelle approche pour incorporer le modèle pointcut/advice de l’AOP dans un langage de programmation fonctionnel statiquement typé comme Haskell. Notre travail comprend deux contributions principales. Premièrement, nous définissons un plongement monadique du modèle pointcut/advice complet de l’AOP. La correction du typage est garantie par l’exploitation du système de type sous-jacent, en particulier les types fantômes et une nouvelle classe de type pour faire de l’anti-unification de types. Dans ce modèle, les aspects sont de première classe, peuvent être déployés de façon dynamique, et le langage de pointcuts est extensible, combinant donc la flexibilité des langages d’aspect typés dynamiquement avec les garanties d’un système de type statique. Les monades nous permettent de raisonner directement sur les effets du calcul à la fois dans les aspects et les programmes de base en utilisant des techniques monadiques traditionnelle. Avec ce système, nous étendons la notion de “open modules” avec des effets, et aussi avec les interfaces de pointcut protégés à l’extérieur d’un advice. Ces restrictions sont appliquées statiquement par le système de type. Aussi, nous adaptons les techniques de EffectiveAdvice afin de raisonner sur des propriétés du flot de contrôle. En outre, nous montrons comment contrôler l’interférence des effets en utilisant l’approche fondée sur la paramétricité de EffectiveAdvice. Nous montrons que cette approche n’est pas satisfaisante en présence de multiples aspects et proposons une approche différente en utilisant des vues monadiques, une nouvelle technique pour le traitement de la pile monadique, développée par Schrijvers et Oliveira. Ensuite, nous exploitons les propriétés de notre modèle pour permettre la construction modulaire de nouvelles sémantiques pour la portée d’aspects et le tissage. Notre deuxième contribution s’appuie sur un modèle puissant pour raisonner sur la composition de mixins avec effets et leur interférence, fondée sur un raisonnement équationnelle, paramétrique, et les lois algébriques sur les effets monadiques. Notre contribution est de montrer comment raisonner sur l’interférence en présence de quantification sans restriction pour les pointcuts. Nous montrons que le raisonnement global peut être compositionnelle, ce qui est essentiel pour le passage à l’échelle de l’approche face aux évolutions de grands systèmes. / Aspect-oriented programming (AOP) aims to enhance modularity and reusability in software systems by offering an abstraction mechanism to deal with crosscutting concerns. But, in most general-purpose aspect languages aspects have almost unrestricted power, eventually conflicting with these goals. This work presents Effective Aspects: a novel approach to embed the pointcut/advice model of AOP in a statically-typed functional programming language like Haskell; along two main contributions. First, we define a monadic embedding of the full pointcut/advicemodel of AOP. Type soundness is guaranteed by exploiting the underlying type system, in particular phantom types and a new anti-unification type class. In this model aspects are first-class, can be deployed dynamically, and the pointcut language is extensible, therefore combining the flexibility of dynamically-typed aspect languages with the guarantees of a static type system. Monads enable us to directly reason about computational effects both in aspects and base programs using traditional monadic techniques. Using this we extend the notion of Open Modules with effects, and also with protected pointcut interfaces to external advising. These restrictions are enforced statically using the type system. Also, we adapt the techniques of EffectiveAdvice to reason about and enforce control flow properties as well as to control effect interference. We show that the parametricity-based approach to effect interference falls short in the presence of multiple aspects and propose a different approach using monad views, a novel technique for handling the monad stack, developed by Schrijvers and Oliveira. Then, we exploit the properties of our model to enable the modular construction of new semantics for aspect scoping and weaving. Our second contribution builds upon a powerful model to reason about mixin-based composition of effectful components and their interference, based on equational reasoning, parametricity, and algebraic laws about monadic effects. Our contribution is to show how to reason about interference in the presence of unrestricted quantification through pointcuts. We show that global reasoning can be compositional, which is key for the scalability of the approach in the face of large and evolving systems. We prove a general equivalence theorem that is based on a few conditions that can be established, reused, and adapted separately as the system evolves. The theorem is defined for an abstract monadic AOP model; we illustrate its use with a simple version of the model just described. This work brings type-based reasoning about effects for the first time in the pointcut/advice model, in a framework that is expressive, extensible and well-suited for development of robust aspect-oriented systems as well as a research tool for new aspect semantics.

Un objectif principal du génie logiciel est de pouvoir produire des logiciels complexes, de grande taille et fiables en un temps raisonnable. La technologie orientée objet (OO) a fourni de bons concepts et des techniques de modélisation et de programmation qui ont permis de développer des applications complexes tant dans le monde académique que dans le monde industriel. Cette expérience a cependant permis de découvrir les faiblesses du paradigme objet (par exemples, la dispersion de code et le problème de traçabilité). La programmation orientée aspect (OA) apporte une solution simple aux limitations de la programmation OO, telle que le problème des préoccupations transversales. Ces préoccupations transversales se traduisent par la dispersion du même code dans plusieurs modules du système ou l’emmêlement de plusieurs morceaux de code dans un même module. Cette nouvelle méthode de programmer permet d’implémenter chaque problématique indépendamment des autres, puis de les assembler selon des règles bien définies. La programmation OA promet donc une meilleure productivité, une meilleure réutilisation du code et une meilleure adaptation du code aux changements. Très vite, cette nouvelle façon de faire s’est vue s’étendre sur tout le processus de développement de logiciel en ayant pour but de préserver la modularité et la traçabilité, qui sont deux propriétés importantes des logiciels de bonne qualité. Cependant, la technologie OA présente de nombreux défis. Le raisonnement, la spécification, et la vérification des programmes OA présentent des difficultés d’autant plus que ces programmes évoluent dans le temps. Par conséquent, le raisonnement modulaire de ces programmes est requis sinon ils nécessiteraient d’être réexaminés au complet chaque fois qu’un composant est changé ou ajouté. Il est cependant bien connu dans la littérature que le raisonnement modulaire sur les programmes OA est difficile vu que les aspects appliqués changent souvent le comportement de leurs composantes de base [47]. Ces mêmes difficultés sont présentes au niveau des phases de spécification et de vérification du processus de développement des logiciels. Au meilleur de nos connaissances, la spécification modulaire et la vérification modulaire sont faiblement couvertes et constituent un champ de recherche très intéressant. De même, les interactions entre aspects est un sérieux problème dans la communauté des aspects. Pour faire face à ces problèmes, nous avons choisi d’utiliser la théorie des catégories et les techniques des spécifications algébriques. Pour apporter une solution aux problèmes ci-dessus cités, nous avons utilisé les travaux de Wiels [110] et d’autres contributions telles que celles décrites dans le livre [25]. Nous supposons que le système en développement est déjà décomposé en aspects et classes. La première contribution de notre thèse est l’extension des techniques des spécifications algébriques à la notion d’aspect. Deuxièmement, nous avons défini une logique, LA , qui est utilisée dans le corps des spécifications pour décrire le comportement de ces composantes. La troisième contribution consiste en la définition de l’opérateur de tissage qui correspond à la relation d’interconnexion entre les modules d’aspect et les modules de classe. La quatrième contribution concerne le développement d’un mécanisme de prévention qui permet de prévenir les interactions indésirables dans les systèmes orientés aspect. / One of the main goals of software engineering is to enable the construction of large, complex and reliable software in timely fashion. Object-oriented (OO) technology has provided modeling and programming principles and techniques that allow developing complex software systems both in academic and industrial areas. In return, experience gained in OO system development has allowed discovering some limitations of object technology (e.g., code scattering and poor traceability problems). Aspect Oriented (AO) Technology is a post-object-oriented technology emerged to overcome limitations of Object Oriented (OO) Technology, such as the crosscutting concern problem. Crosscutting concerns are scattered and tangled concerns. Major goals of Aspect Oriented Programming (AOP) include improving modularity, cohesion, and overall software quality. Aspect Oriented Programming results in the evolution of programming activities to fullblown software engineering processes, to preserve modularity and traceability, which are two important properties of high-quality software. Yet, there are also many challenges in AO Technology. Reasoning, specification, and verification of AO programs present unique challenges especially as such programs evolve over time. Consequently, modular reasoning of such programs is highly attractive as it enables tractable evolution, otherwise necessitating that the entire program be reexamined each time a component is changed or is added. It is well known in the literature, however, that modular reasoning about AO programs is difficult due to the fact that the aspects applied often alter the behavior of the base components [47]. The same modular reasoning difficulties are also present in the specification and verification phases of software development process. To the best of our knowledge, AO modular specification and verification is a weakly covered subject and constitutes an interesting open research field. Also, aspect interaction is a major concern in the aspect-oriented community. To deal with these problems, we choose to use category theory and algebraic specification techniques. To achieve the above thesis goals, we use the work of Wiels [110] and other contributions such as the one described in [25]. We assume at the beginning that the system under development is already decomposed into aspect and class components. The first contribution of our thesis is the extension of the algebraic specification technique to the notion of aspect. Secondly, we define a logic, LA that is used in specification bodies to describe the behavior of these components. The third contribution concerns the defini tion of the weaving operator corresponding to the weaving interconnection relationship between aspect modules and class modules. The fourth contribution consists of the design of a prevention policy that is used to prevent or avoid undesirable aspect interactions in aspect-oriented systems.

Un objectif principal du génie logiciel est de pouvoir produire des logiciels complexes, de grande taille et fiables en un temps raisonnable. La technologie orientée objet (OO) a fourni de bons concepts et des techniques de modélisation et de programmation qui ont permis de développer des applications complexes tant dans le monde académique que dans le monde industriel. Cette expérience a cependant permis de découvrir les faiblesses du paradigme objet (par exemples, la dispersion de code et le problème de traçabilité). La programmation orientée aspect (OA) apporte une solution simple aux limitations de la programmation OO, telle que le problème des préoccupations transversales. Ces préoccupations transversales se traduisent par la dispersion du même code dans plusieurs modules du système ou l’emmêlement de plusieurs morceaux de code dans un même module. Cette nouvelle méthode de programmer permet d’implémenter chaque problématique indépendamment des autres, puis de les assembler selon des règles bien définies. La programmation OA promet donc une meilleure productivité, une meilleure réutilisation du code et une meilleure adaptation du code aux changements. Très vite, cette nouvelle façon de faire s’est vue s’étendre sur tout le processus de développement de logiciel en ayant pour but de préserver la modularité et la traçabilité, qui sont deux propriétés importantes des logiciels de bonne qualité. Cependant, la technologie OA présente de nombreux défis. Le raisonnement, la spécification, et la vérification des programmes OA présentent des difficultés d’autant plus que ces programmes évoluent dans le temps. Par conséquent, le raisonnement modulaire de ces programmes est requis sinon ils nécessiteraient d’être réexaminés au complet chaque fois qu’un composant est changé ou ajouté. Il est cependant bien connu dans la littérature que le raisonnement modulaire sur les programmes OA est difficile vu que les aspects appliqués changent souvent le comportement de leurs composantes de base [47]. Ces mêmes difficultés sont présentes au niveau des phases de spécification et de vérification du processus de développement des logiciels. Au meilleur de nos connaissances, la spécification modulaire et la vérification modulaire sont faiblement couvertes et constituent un champ de recherche très intéressant. De même, les interactions entre aspects est un sérieux problème dans la communauté des aspects. Pour faire face à ces problèmes, nous avons choisi d’utiliser la théorie des catégories et les techniques des spécifications algébriques. Pour apporter une solution aux problèmes ci-dessus cités, nous avons utilisé les travaux de Wiels [110] et d’autres contributions telles que celles décrites dans le livre [25]. Nous supposons que le système en développement est déjà décomposé en aspects et classes. La première contribution de notre thèse est l’extension des techniques des spécifications algébriques à la notion d’aspect. Deuxièmement, nous avons défini une logique, LA , qui est utilisée dans le corps des spécifications pour décrire le comportement de ces composantes. La troisième contribution consiste en la définition de l’opérateur de tissage qui correspond à la relation d’interconnexion entre les modules d’aspect et les modules de classe. La quatrième contribution concerne le développement d’un mécanisme de prévention qui permet de prévenir les interactions indésirables dans les systèmes orientés aspect. / One of the main goals of software engineering is to enable the construction of large, complex and reliable software in timely fashion. Object-oriented (OO) technology has provided modeling and programming principles and techniques that allow developing complex software systems both in academic and industrial areas. In return, experience gained in OO system development has allowed discovering some limitations of object technology (e.g., code scattering and poor traceability problems). Aspect Oriented (AO) Technology is a post-object-oriented technology emerged to overcome limitations of Object Oriented (OO) Technology, such as the crosscutting concern problem. Crosscutting concerns are scattered and tangled concerns. Major goals of Aspect Oriented Programming (AOP) include improving modularity, cohesion, and overall software quality. Aspect Oriented Programming results in the evolution of programming activities to fullblown software engineering processes, to preserve modularity and traceability, which are two important properties of high-quality software. Yet, there are also many challenges in AO Technology. Reasoning, specification, and verification of AO programs present unique challenges especially as such programs evolve over time. Consequently, modular reasoning of such programs is highly attractive as it enables tractable evolution, otherwise necessitating that the entire program be reexamined each time a component is changed or is added. It is well known in the literature, however, that modular reasoning about AO programs is difficult due to the fact that the aspects applied often alter the behavior of the base components [47]. The same modular reasoning difficulties are also present in the specification and verification phases of software development process. To the best of our knowledge, AO modular specification and verification is a weakly covered subject and constitutes an interesting open research field. Also, aspect interaction is a major concern in the aspect-oriented community. To deal with these problems, we choose to use category theory and algebraic specification techniques. To achieve the above thesis goals, we use the work of Wiels [110] and other contributions such as the one described in [25]. We assume at the beginning that the system under development is already decomposed into aspect and class components. The first contribution of our thesis is the extension of the algebraic specification technique to the notion of aspect. Secondly, we define a logic, LA that is used in specification bodies to describe the behavior of these components. The third contribution concerns the defini tion of the weaving operator corresponding to the weaving interconnection relationship between aspect modules and class modules. The fourth contribution consists of the design of a prevention policy that is used to prevent or avoid undesirable aspect interactions in aspect-oriented systems.