Run Time Type Information in Mercury

The logic/functional language Mercury uses a strong, mostly static type system based on polymorphic many-sorted logic. For efficiency, the Mercury compiler uses type specific representations of terms, and implements polymorphic operations such as unifications via generic code invoked with descriptions of the actual types of the operands. These descriptions, which consist of automatically generated data and code, are the main components of the Mercury runtime type information (RTTI) system. We have used this system to implement several extensions of the Mercury system, including an escape mechanism from static type checking, generic input and output facilities, a debugger, and automatic memoization, and we are in the process of using it for an accurate, native garbage collector. We give detailed information on the implementation and uses of the Mercury RTTI system as well as measurements of the space costs of the system.