Thesis (Ph.D.)--Drexel University, 2009. / Includes abstract. Includes bibliographical references (leaves 113-126).

Generics has recently been adopted to many mainstream object oriented languages, such as C# and Java. As a particular design choice, generics in C# and Java use a sub-typing relation to constraint type parameters. Failing to encapsulate type parameters within generic interfaces and inability to encapsulate type constraints as part of an interface definition have been identified as deficiencies in the way this design choice has been implemented in these languages. These deficiencies can lead to verbose and redundant code. In particular, they have been reported to affect the development of highly generic libraries. To address these issues, extending object oriented interfaces and sub-typing with associated types and constraint propagation has been proposed and studied in an idealized small-scale formal setting. This thesis builds on this previous work and provides a design and implementation of the extensions in full C#. We also present a proof of soundness of the Featherweight Generic Java (FGJ) formalism extended with interfaces. This property was assumed in a proof of type safety of associated types and constraint propagation, but no proof for the property was provided.

Reusing code from software libraries can reduce the time and effort to construct software systems and also enable the development of larger systems. However, the benefits that come from the use of software libraries may not be realized due to limitations in the way that traditional software libraries are constructed. Libraries come equipped with application programming interfaces (API) that help enforce the correct use of the abstractions in those libraries. Writing new components and adapting existing ones to conform to library APIs may require substantial amounts of "glue" code that potentially affects software's efficiency, robustness, and ease-of-maintenance. If, as a result, the idea of reusing functionality from a software library is rejected, no benefits of reuse will be realized. This dissertation explores and develops techniques that support the construction of software libraries with abstraction layers that do not impede efficiency. In many situations, glue code can be expected to have very low (or zero) performance overhead. In particular, we describe advances in the design and development of active libraries - software libraries that take an active role in the compilation of the user's code. Common to the presented techniques is that they may "break" a library API (in a controlled manner) to adapt the functionality of the library for a particular use case. The concrete contributions of this dissertation are: a library API that supports iterator selection in the Standard Template Library, allowing generic algorithms to find the most suitable traversal through a container, allowing (in one case) a 30-fold improvement in performance; the development of techniques, idioms, and best practices for concepts and concept maps in C++, allowing the construction of algorithms for one domain entirely in terms of formalisms from a second domain; the construction of generic algorithms for algorithmic differentiation, implemented as an active library in Spad, language of the Open Axiom computer algebra system, allowing algorithmic differentiation to be applied to the appropriate mathematical object and not just concrete data-types; and the description of a static analysis framework to describe the generic programming notion of local specialization within Spad, allowing more sophisticated (value-based) control over algorithm selection and specialization in categories and domains. We will find that active libraries simultaneously increase the expressivity of the underlying language and the performance of software using those libraries.

Production compilers implement optimizing transformation rules for built-in types. What justifies applying these optimizing rules is the axioms that hold for built-in types and the built-in operations supported by these types. Similar axioms also hold for user-defined types and the operations defined on them, and therefore justify a set of optimization rules that may apply to user-defined types. Production compilers, however, do not attempt to construct and apply these optimization rules to user-defined types. Built-in types together the axioms that apply to them are instances of more general algebraic structures. So are user-defined types and their associated axioms. We use the technique of generic programming, a programming paradigm to design efficient, reusable software libraries, to identify the commonality of classes of types, whether built-in or user-defined, convey the semantics of the classes of types to compilers, design scalable and effective program analysis for them, and eventually apply optimizing rules to the operations on them. In generic programming, algorithms and data structures are defined in terms of such algebraic structures. The same definitions are reused for many types, both built-in and user-defined. This dissertation applies generic programming to compiler analyses and transformations. Analyses and transformations are specified for general algebraic structures, and they apply to all types, both built-in and primitive types.

Univ., Diss.--Leipzig, 2004. / Literaturverz. S. [229] - 238.

Dans le cadre du génie logiciel en traitement d'images (TDI), nous nous intéressons à la notion de réutilisabilité des algorithmes. Dans de nombreux outils logiciels, l'implémentation d'un algorithme est souvent dépendante du type des données traitées. Au sens le plus général, les formes que peuvent prendre les images numériques discrètes sont nombreuses (image 2D classiques, volumes 3D, graphes non réguliers, complexes cellulaires, etc.) conduisant à une explosion combinatoire du nombre théorique d'implémentations. La programmation générique (PG) est un cadre adapté au développement d'outils logiciels réutilisables. Nous présentons un paradigme de programmation basé sur la PG conçu pour la création de logiciels scientifiques tels ceux dédiés au TDI. Cette approche concilie réutilisabilité, puissance d'expression, extensibilité et performance. Nous proposons ensuite une architecture logicielle pour le TDI basée sur ce paradigme de programmation, s'appuyant sur une bibliothèque générique de TDI. Les fondations de ce cadre définissent des concepts fondamentaux du TDI, qui permettent l'écriture d'algorithmes réutilisables sur de nombreux types d'images. Nous présentons enfin une stratégie pour construire des outils haut niveau au dessus de cette bibliothèque tels que des ponts vers des langages dynamiques ou des interfaces graphiques. Ce mécanisme est conçu pour préserver la généricité et la performance des outils logiciels sous-jacents, tout en permettant un usage plus simple et plus flexible de ceux-ci / In the context of software engineering for image processing (IP), we consider the notion of reusability of algorithms. In many software tools, an algorithm's implementation often depends on the type of processed data. In a broad definition, discrete digital images may have various forms : classical 2D images, 3D volumes, non-regular graphs, cell complexes, and so on : thus leading to a combinatorial explosion of the theoretical number of implementations. Generic programming (GP) is a framework suited to the development of reusable software tools. We present a programming paradigm based on GP designed for the creation of scientific software such as IP tools. This approach combines the benefits of reusability, expressive power, extensibility, and efficiency. We then propose a software architecture for IP using this programming paradigm based on a generic IP library. The foundations of this framework define essential IP concepts, enabling the development of algorithms compatible with many image types. We finally present a strategy to build high-level tools on top of this library, such as bridges to dynamic languages or graphical user interfaces. This mechanism has been designed to preserve the genericity and efficiency of the underlying software tools, while making them simpler to use and more flexible

Dependently typed programming languages allow the type system to express arbitrary propositions of intuitionistic logic, thanks to the Curry-Howard isomorphism. Taking full advantage of this type system requires defining more types than usual, in order to encode logical correctness criteria into the definitions of datatypes. While an abundance of specialized types helps ensure correctness, it comes at the cost of needing to redefine common functions for each specialized type. This dissertation makes an effort to attack the problem of code reuse in dependently typed languages. Our solution is to write generic functions, which can be applied to any datatype. Such a generic function can be applied to datatypes that are defined at the time the generic function was written, but they can also be applied to any datatype that is defined in the future. Our solution builds upon previous work on generic programming within dependently typed programming. Type theory supports generic programming using a construction known as a universe. A universe can be considered the model of a programming language, such that writing functions over it models writing generic programs in the programming language. Historically, there has been a trade-off between the expressive power of the modeled programming language, and the kinds of generic functions that can be written in it. Our dissertation shows that no such trade-off is necessary, and that we can write future-proof generic functions in a model of a dependently typed programming language with a rich collection of types.

Computation with large-scale heterogeneous data typically requires universal traversal to search for all occurrences of a substructure that matches a possibly complex search pattern, whose context may be different in different places within the data. Both aspects cause difficulty for existing general-purpose programming languages, because these languages are designed for homogeneous data and have problems typing the different substructures in heterogeneous data, and the complex patterns to match with the substructures. Programmers either have to hard-code the structures and search patterns, preventing programs from being reusable and scalable, or have to use low-level untyped programming or programming with special-purpose query languages, opening the door to type mismatches that cause a high risk of program correctness and security problems. This thesis invents the concept of pattern structures, and proposes a general solution to the above problems - a programming technique using pattern structures. In this solution, well-typed pattern structures are defined to represent complex search patterns, and pattern searching over heterogeneous data is programmed with pattern parameters, in a statically-typed language that supports first-class typing of structures and patterns. The resulting programs are statically-typed, highly reusable for different data structures and different patterns, and highly scalable in terms of the complexity of data structures and patterns. Adding new kinds of patterns for an application no longer requires changing the language in use or creating new ones, but is only a programming task. The thesis demonstrates the application of this approach to, and its advantages in, two important examples of computation with heterogeneous data, i.e., XML data processing and Java bytecode analysis. / Thesis (Ph.D, Computing) -- Queen's University, 2007-08-27 09:43:38.888

In the context of software engineering for image processing (IP), we consider the notion of reusability of algorithms. In many software tools, an algorithm's implementation often depends on the type of processed data. In a broad definition, discrete digital images may have various forms : classical 2D images, 3D volumes, non-regular graphs, cell complexes, and so on : thus leading to a combinatorial explosion of the theoretical number of implementations. Generic programming (GP) is a framework suited to the development of reusable software tools. We present a programming paradigm based on GP designed for the creation of scientific software such as IP tools. This approach combines the benefits of reusability, expressive power, extensibility, and efficiency. We then propose a software architecture for IP using this programming paradigm based on a generic IP library. The foundations of this framework define essential IP concepts, enabling the development of algorithms compatible with many image types. We finally present a strategy to build high-level tools on top of this library, such as bridges to dynamic languages or graphical user interfaces. This mechanism has been designed to preserve the genericity and efficiency of the underlying software tools, while making them simpler to use and more flexible

Thesis (Ph.D.)--University of Wollongong, 2005. / Typescript. Includes bibliographical references: p. 333-339.