Towards a theory of abstract data types: a discussion on problems and tools

This paper aims to show that, in order to capture a quite relevant featu­re such as the recursiveness of abstract data types, Model Theory works better than Category Theory. First, various categorial notions such as "initiality", "finality", mo­ noinitiality", "epifinality", "weak monoinitiality" and "weak epifinality'' are analyzed, from a model theoretic point of view, as regards the "abs­tractness" and the "cardinality" of the models they determine. In parti­cular, countability is seen as a necessary condition to get recursive da­ta types, and it is shown that only "initiality", "monoinitiality", "epi­finality" and "weak epifinality" allow to select countable models. An extensive analysis is then devoted to the problem of the recursiveness of abstract data types: we provide a formal definition of recursiveness and show that it neither collapses, nor it is incompatible with the "abs­tractness" requirement. We also show that none of the above quoted cate­gorial notions captures recursiveness. Finally, we consider our own definition of abstract data type, based on model-theoretic notions; we analyze this definition in the frame of the proposed formalization of recursiveness, and illustrate the sense accord­ing to which it captures recursiveness.