OBJ-P: The polymorphic extension of OBJ-3

OBJ-3 is a functional programming language with first-order function types. It has two special features: overloading of function symbols and the possibility to define an ordering on the sorts. This ordering is induced by set inclusion on the carrier sets. Therefore, we speak of set inclusion subtyping. The algebraic semantics of OBJ-3 is based on the theory of order-sorted algebras. OBJ-3 also allows parameterized programming. However, the concepts of higher-order functions and parametric polymorphism are only emulated by parameters of OBJ-3 modules. In this thesis, we show how to extend OBJ-3 by parametric polymorphism in an elegant way. We call this extended language OBJ-P. In the second part of the thesis, we introduce a type inference system for OBJ-P and give a corresponding type reconstruction algorithm. For this we have considered the theory of unification, as type reconstruction is reduced to type unification. Finally, we give two large examples. One example shows how the type reconstruction algorithm works. The other one shows the powerful OBJ-P module system in combination with overloading and set inclusion subtyping. (orig.)SIGLEAvailable from TIB Hannover: RR 4367(99-4) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman