Efficient implementation of an algebraic specification language

Abstract

We consider the implementation of SRDL, a small algebraic specification language with particular emphasis on structural recursion which is for abstract data types the analogue of primitive recursion. We demonstrate how the regular behaviour of structural recursion can be exploited for generating better code. Technically, this is achieved by generalizing loop iteration on integers to bottom-up iteration on trees. Here, it is possible to replace the function stack of activation records by simpler control stacks. On the machine level, this tree walk is performed by a generalization of the Schorr-Waite algorithm to n-ary trees, causing only a small overhead in execution time but no additional memory requirements. The resulting code is faster and requires less storage than usual call by value code.