Hybrid implementations of algebraic specifications

The problem of insufficient execution speed of implementations of algebraic specifications is approached by presenting a formal framework in which implementations based on term rewriting [3] can be combined transparently with implementations based on conventional programming languages. This hybrid method can be used for the implementation of parameterized datatypes, where the formal parameter may have a formal signature and where the actual parameter may be implemented in either fashion. The hybrid method permits later addition of equations over datatypes implemented in this fashion, and allows for non-canonical terms to have an ‘internal representation’. The correctness of the hybrid method can be established (it is completely covered in [6]). An extended example is shown. Measurements done on a prototype suggest a gain of a factor five in execution speed.