Types in Their Prime: Sub-typing of Data in Resource Constrained Environments

Sub-typing of data improves reuse and allows for reasoning at different levels of abstraction; however, it is seldom applied in resource constrained environments. The key reason behind this is the increase in overhead that is caused by including hierarchical information in data types as compared to a flat list. Where hierarchical data typing is used, it is often represented using verbose textual identifiers or numerical encodings that are suboptimal with regards to space. In this paper, we present an encoding function for hierarchically typed information, based on the properties of prime numbers. It provides a compact representation of types, fast subsumption testing even on resource constrained platforms and support for the evolution of the data type hierarchy. We demonstrate the feasibility of our approach on two representative communication models in constrained environments; a publish/subscribe event bus and a RESTful application protocol. We evaluate the performance of our encoding function and show that it has limited overhead compared to a flat list of data types and that this overhead is outweighed by reduced memory and communication overhead once applied.