Wilhelm-Schickard-Institut fur Informatik

The generic programming paradigm has received considerable at-tention since the publication of the C STL library [20]. The specication of capabilities, which a programming language must provide to support generic programming, has been examined in detail in [26] and [31]. Especially in the area of computer algebra, these requirements are extensive, because of the structural complexity of the types and algorithms and the need for precision in declarations. In this essay we propose a general approach to the design and im-plementation of a type system. We then discuss how programming lan-guage constructs can be described by means of the calculus, including overload resolution, higher-order functions and type constructors with contravariant argument positions together with automatic instantia