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

The many-sorted algebra approach to abstract data types has difficulties in handling erroneous expressions, such as dividing by zero, taking the top of an empty stack, etc. Another problem is data representation in more than one way and conversion (coercion) between different representations. Those problems may be solved using the approach of order-sorted algebra, originally introduced by the authors [Theor. Comput. Sci. 105, 217-273 (1992; Zbl 0778.68056)]. The essence of order- sorted algebra is that sorts have suborts, semantically interpreted as subsets among the carriers of an algebra. It is shown how this algebra generalizes the usual many-sorted algebra and how it permits an elegant solution to the constructor-selector problem, which cannot be satisfactory solved in many-sorted algebra. The theoretical considerations are illustrated by examples using a syntax based on the OBJ language.