Datatype−Generic Programming

Abstract

Generic programming aims to increase the flexibility of programming languages, by expanding the possibilities for parametrization — ideally, without also expanding the possibilities for uncaught errors. The term means different things to different people: parametric polymorphism, data abstraction, meta-programming, and so on. We use it to mean polytypism, that is, parametrization by the shape of data structures rather than their contents. To avoid confusion with other uses, we have coined the qualified term datatype-generic programming for this purpose. In these lecture notes, we expand on the definition of datatype-generic programming, and present some examples of datatype-generic programs. We also explore the connection with design patterns in object-oriented programming; in particular, we argue that certain design patterns are just higher-order datatype-generic programs.