## Paper: Order-Sorted Algebra solves the Constructor-Selector, Multiple (at LICS 1987)

**Joseph A. Goguen José Meseguer**

### Abstract

Structured data are generally composed from constituent parts
by *constructors* and decomposed by *selectors*. We prove that the
usual many-sorted algebra approach to abstract data types *cannot* capture
this simple intuition in a satisfactory way. We also show that order-sorted
algebra *does* solve this problem, and many others concerning ill-defined
and erroneous expressions, in a simple and natural way. In particular, we show
how order-sorted algebra supports an elegant solution to the problems of
multiple representations and coercions. The essence of order-sorted algebra is
that sorts have *subsorts*, whose semantic interpretation is the
*subset* relation on the carriers of algebras.

### BibTeX

@InProceedings{GoguenMeseguer-OrderSortedAlgebras, author = {Joseph A. Goguen and José Meseguer}, title = {Order-Sorted Algebra solves the Constructor-Selector, Multiple}, booktitle = {Proceedings of the Second Annual IEEE Symposium on Logic in Computer Science (LICS 1987)}, year = {1987}, month = {June}, pages = {18--29}, location = {Ithaca, NY, USA}, publisher = {IEEE Computer Society Press} }