Facts

• Title: Foundations of an adaptable container library.
• Field of study: Computer Science (danish: Datalogi).
• Awarded degree: cand.scient. i Datalogi (Latin: candidatus scientiarum, English: Master of Science (M.Sc.) in Computer Science).
• Degree-awarding institution: University of Copenhagen, Department of Computer Science (DIKU).
• Credit / Size: 37,5 ECTS.

People

• Examiner: Torben Æ. Mogensen Associate Professor (Lektor), Ph.D. (DIKU).
• External examiner: Peter Sestoft Professor, Ph.D. (IT University of Copenhagen).
• Supervisor: Jyrki Katajainen Associate Professor (Lektor), Ph.D. (DIKU).

Dates

• Deadline: November 6, 2009.
• Defence time and place: December 17, 2009 at 09:00-10:00 in S125 (Universitetsparken 1, 2100 København Ø).

Download

• The thesis in PDF and PS.GZ.
• The code discussed in the thesis as a ZIP file.
• Errata in PDF.
• The presentation from the oral defence in Danish in PDF.
• The code and the thesis are also available at the dedicated webpage at PE-lab's homepage.

News

• December 17, 2009: Probably the last post on this page. The defence went really well today, and my thesis was awarded the highest grade in the danish grading system (12). I am finally cand.scient (M.Sc.). Thanks must go to the people who attended the defence today; they made my day special.
• December 9, 2009: The defence has now been officially announced.
• November 30, 2009: Added defence time and place and added a link to the PE-lab homepage for my thesis.
• November 6, 2009: After just one hour of sleep I went to Copenhagen this morning to hand in the thesis. Nothing really went wrong. I spend the night doing one more proof reading of the thesis, and I did also manage to create a zip file with all the code relevant for the thesis. I talked briefly to my supervisor which told that the defence will be held in about 6 weeks, since the external examiner (censor) is abroad. I have still a lot to do, including finishing the revised version of the infrastructure paper and extending the Copenhagen LEDA implementation. I hope that we can announce the time and date for the defence really soon.
• October 22, 2009: Just about one month since I've updated this page. Since the last update, I've been polishing the introduction and the usability report. We (me and Jyrki) decided to include an earlier version of the infrastructure paper (first paper in the listing below) in the thesis. Therefore the thesis is actually ready right now, but I still need to do some more polishing (to satisfy my own requirements) of the text, before I hand it in. I expect to post the first draft in about a week on this page, so stay tuned. Notice, that I've changed the title, mainly because the old title did only cover the two first parts of the text.
• September 23, 2009: I've now finished writing my usability report, so basically I just need to rewrite the introduction and finish the infrastructure paper. It's kinda sad in a good way, that this journey (my graduate study) has now (maybe) come to the end. "The chase is better than the catch".
• September 06, 2009: We are about to start our rewrite of the infrastructure paper. We need several corrections in order to submit it for publication. I am currently working in parallel to finish my usability report. I have all text, I just need to polish it.
• September 03, 2009: I just got back from the conference. My presentation went very well; the slides from the presentation are available here. The conference and the workshop were really inspiring and I have got several ideas for future work.
• August 16, 2009: I have worked all weekend on my usability report. I really hope I can finish it before the presentation of our vector paper, since the language extension of named template arguments is included in my presentation. Hopefully, it will soon be published at the CPH STL homepage.
• August 8, 2009: Page uploaded, I am quite busy preparing my presentation of the vector paper at the ACM SIGPLAN Workshop on Generic Programming. The paper will be presented the 30th of August at the workshop in Edinburgh, UK. Hopefully I will get some feedback which could give pointers to future research.

Contents

My Master's Thesis is the result of the redesign of the CPH STL. It primarily consists of three papers; two papers are written jointly with my supervisor Jyrki Katajainen.

The papers are:

1. Jyrki Katajainen and Bo Simonsen: Applying design patterns to specify the architecture of a generic program library (2008).

   Abstract: The standard template library (STL), now part of the C++ standard library, ships with every standard-compliant C++ compiler. In this paper, we apply design patterns to specify the structure of the CPH STL, which is a special edition of the STL developed at the University of Copenhagen. Three design patterns have had significant influence on the structure of the library: bridge, strategy, and iterator. With the use of design patterns we obtain a high-quality design with many desirable characteristics including simplicity, ease of maintenance, loose coupling, extensibility, and reusability. Because of a high degree of parameterization, the usability of components becomes a central issue and we propose a solution that may be of independent interest for developers of other template libraries.

   Keywords: Generic programming, design patterns, program libraries.

2. Jyrki Katajainen and Bo Simonsen: Adaptable component frameworks: Using vector from the C++ standard library as an example, Proceedings of the 2009 ACM SIGPLAN Workshop on Generic Programming, ACM (2009), 13-24. [PDF] [PS] [DOI]

   Abstract: The CPH STL is a special edition of the STL, the containers and algorithms part of the C++ standard library. The specification of the generic components of the STL is given in the C++ standard. Any implementation of the STL, e.g. the one that ships with your standard-compliant C++ compiler, should provide at least one realization for each container that has the specified characteristics with respect to performance and safety. In the CPH STL project, our goal is to provide several alternative realizations for each STL container. For example, for associative containers we can provide almost any kind of balanced search tree. Also, we do provide safe and compact versions of each container. To ease the maintenance of this large collection of implementations, we have developed component frameworks for the STL containers. In this paper, we describe the design and implementation of a component framework for vector, which is undoubtedly the most used container of the C++ standard library. In particular, we specify the details of a vector implementation that is safe with respect to referential integrity and strong exception safety. Additionally, we report the experiences and lessons learnt from the development of component frameworks which we hope to be of benefit to persons engaged in the design and implementation of generic software libraries.

   General terms: Algorithms, Design, Experimentation, Languages, Performance.

   Keywords: Generic Programming, C++ Standard Library, STL, Robustness, Efficiency.

3. Bo Simonsen: Towards better usability of component frameworks, CPH STL report 2009-6, Department of Computer Science, University of Copenhagen (2009). [PDF] [PS]

   Abstract: The CPH STL is an enhanced version of the STL. During the development of the CPH STL we focused on the container part of the STL. Our goal is to provide several versions of individual STL containers, each providing different trade-offs and desired properties. We found that maintaining complete implementations of all variants would become a hazard for the future development of the library. Therefore, we designed component frameworks, where the concepts of the containers are factorized into smaller parts and most of them can vary independently. Component frameworks give the user an enormous flexibility which allows he or she to specify the desirable trade-offs and properties. We observed that flexibility and usability are hard to reconcile because of limitations in the C++ programming language. In this work we will study the usability problems, caused by these limitations, and we will also provide solutions for these problems. The key problems are that the user has to write a large declaration for using a container, and a component mismatch is likely to occur, i.e. the user gives incompatible components to the framework. Such a component mismatch results in unreadable error messages and the actual errors can be hard to correct. We solved the problem of large declarations by extending C++ with named template arguments and we applied C++ metaprogramming techniques to solve the problem of component mismatches. We believe that the solutions to the problems described in this work are relevant beyond the CPH STL.

   Keywords: component frameworks, C++ language features, C++0x, named template arguments, template argument propagation, component mismatch.