CPL - Chalmers Publication Library

Generic Programming with Concepts

Författare och institution:
Marcin Zalewski (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers))
Serie:
1) Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie, ISSN 0346-718X; nr 2857
2) Technical report D - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, ISSN 1653-1787; nr 46
ISBN:
978-91-7385-176-3
Antal sidor:
216
Publikationstyp:
Doktorsavhandling
Förlag:
Chalmers University of Technology
Förlagsort:
Göteborg
Publiceringsår:
2008
Språk:
engelska
Datum för examination:
2008-11-28
Tidpunkt för examination:
13:15
Lokal:
Room EE (in the EDIT building), Rännvägen 6B, Chalmers University
Opponent:
Professor Gregor Snelting, Fakultät für Informatik, Universität Karlsruhe, Germany
Inkluderade delarbeten:
Sammanfattning (abstract):
Generic programming is an indispensable ingredient of modern programming languages. In the C++ programming language, generic programming is implemented by the means of parameterized fragments of code, called templates, in which parameters are constrained by concepts. This thesis consists of seven publications investigating different aspects of generic programming with concepts---formal semantics of the concepts language feature, the mathematical foundations of concepts as a specification tool, change impact analysis of generic libraries, performance-based component composition, and multi-paradigm, multi-language library development.

Formally specifying the semantics of programming languages is a difficult task, one that is taken up rarely due to its complexity. In this thesis we provide a formal semantics of the separate type checking with concepts. We also describe some potential problems we discovered while translating the informal wording into formal rules. A formal semantics, such as ours, makes it easier to discuss language design, to improve the quality of the informal specification, and may serve as a model for compilers and other tools. Concepts as institutions is another view on the semantics of concepts we provide in this thesis. Institutions describe the parts of logics: signatures are the vocabulary, sentences are phrases that can be said given a vocabulary, and models are the subjects of the phrases. The institutions of concepts we provide make concepts into logics; the most basic general institution frames concepts as signatures and concept maps as sentences and models at the same time. The logic view on concepts makes it possible to apply techniques from the field of algebraic specification in the realm of C++ programming.

Generic programming with concepts also requires more practical support: in this thesis we describe a conceptual change impact analysis for generic libraries and a tool for performance-based component composition. Our change impact analysis is applied at the specification level of a generic library, which comprises the underlying concept hierarchy and generic interfaces of library functions and data structures. We apply the analysis to a real and important problem, a proposed change to the iterator concepts hierarchy of the Standard Template Library of C++. Our component composition tool addresses the issue of combining generic components. We provide a tool that learns from experiments and automatically selects the combination of components expected to be the best in a given situation---a case study is provided for our fast Fourier transform library.

Finally, we consider multi-paradigm development of generic libraries. We investigate how the datatype-generic paradigm applies to an imperative language such as C++: we provide a possible solution and outline the important differences between C++ and a functional language that must be taken into account. We also consider similarities between generic programming in Haskell and C++: based on a particular library we provide a translation from Haskell generic interfaces to the corresponding interfaces in C++.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Data- och informationsvetenskap ->
Datavetenskap (datalogi) ->
Datalogi
NATURVETENSKAP ->
Data- och informationsvetenskap ->
Programvaruteknik
Nyckelord:
generic, c++, template, libraries, concepts
Postens nummer:
76351
Posten skapad:
2008-10-27 14:34
Posten ändrad:
2013-09-25 15:19

Visa i Endnote-format