The Prague Stringology Conference 2005

Juha Kärkkäinen

Alphabets in Generic Programming

We initiate the design of a software library of algorithms and data structures on strings. The design is based on generic programming, which aims for a single implementation of an abstract algorithm that works in every situation, particularly with any kind of string or sequence, without any disadvantage to a more specific implementation. The design requires a deep understanding of both different algorithms and various types of strings. In this paper, we address one aspect of strings, the alphabet. The main contribution is a novel definition of the concept of an alphabet in a program. The key feature is the recognition of two levels, the level of abstract algorithms and the level of concrete programs, and the establishment of a connection between the levels. Based on the definition, we provide a sketch of a design for alphabet traits, a crucial abstraction layer between algorithms and strings.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF