Interpretive Overhead and Optimal Specialisation. Or: Life without the Pending List (Workshop Version)

A self-interpreter and a program specialiser with the following characteristics are developed for a simple imperative language: 1) The self-interpreter runs with program-independent interpretive overhead; 2) the specialiser achieves optimal specialisation, that is, it eliminates all interpretation overhead; 3) the specialiser has been run on a variety of small and large programs, including specialising the selfinterpreter to itself; 4) all specialiser parts except for loop unfolding have been proven to terminate.

We achieve the above by using a structured language with separated control and data flow, containing loops but without while. The specialiser uses two-level binding-time annotations in a new way: source annotations are used to ensure correctness of specialised programs. A novelty: the specialiser has no need for a pending list, and does no call graph analysis of the residual program. A source-to-source normalisation phase does program transformations to avoid situations where the specialiser would need to specialise code based on an unknown state. A pruning phase e ciently achieves the e ect of Romanenko's arity raising.