Order-sorted algebra solves the constructor-selector, multiple representation, and coercion problems

Jose Meseguer, Joseph A. Goguen

Research output: Contribution to journalArticlepeer-review


Structured data are generally composed from constituent parts by constructors and decomposed by selectors. We show 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 partially defined, ill-defined, and erroneous expressions, in a simple and natural way. In particular, we show how order-sorted algebra supports and 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.

Original languageEnglish (US)
Pages (from-to)114-158
Number of pages45
JournalInformation and Computation
Issue number1
StatePublished - Mar 1993
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Order-sorted algebra solves the constructor-selector, multiple representation, and coercion problems'. Together they form a unique fingerprint.

Cite this