Frugal Encoding in Reversible MOQA: A Case Study for Quicksort
Diarmuid Early, Ang Gao, Michel Schellekens · 2012
MOQA is a high-level data structuring language, designed to allow for modular static timing analysis. In essence, MOQA allows the programmer to determine the average running time of a broad class of programmes directly from the code in a (semi-)automated way. The MOQA language has the property of randomness preservation which means that applying any operation to a random structure, results in an output isomorphic to one or more random structures, which is the key to systematic timing. The language, its implementation and the associ- ated timing tool have been reported on in the literature. Randomness preservation is key in ensuring modular timing derivation. A degree of reversibility in turn is a key aspect of ensuring randomness preservation. All operations of the MOQA language can be made reversible with min- imal additional bookkeeping. A challenge in achieving this encoding in a frugal way is to ensure subsets of data can be stored without exces- sive overheads. The paper focuses on illustrating such an encoding for the case of the Quicksort algorithm. Similar encodings are explored to ensure efficient reversibility of all MOQA operations. The paper is self contained, i.e. no prior knowledge of the MOQA language is needed to follow the encoding argument. We show how to efficiently encode the information needed to reverse the split of a list into two sublists. The code for reversible Quicksort is provided and an example illustrates the algorithm's reverse execution.