The Centre for Efficiency-Oriented Languages (CEOL), created at UCC with intial funding from Science Foundation Ireland, focuses on bridging Semantics and Complexity and Improved Software Timing. Currently the centre has 11 members and has a collaboration project with Sun Microsystems Labs.
We present ACETT, the Average Case Execution Time Tool, as the first language which is compositional with respect to a non-trivial time measure. This provides a key step for the IFIP2000 research challenge to bridge (Denotational) Semantics and Complexity. The average time of ACETT programs can be expressed in a compositional way as linear (or more precisely: affine) combinations of the average times of their basic components.
Thus far no single unifying theory is available to support average time analysis and algorithms are analyzed on a case-by-case basis. ACETT allows for a uniform approach to average-time analysis. The new approach is directly inspired by the traditional semantic notion of compositionality and ACETT programs are shown to be Random-Structure preserving. As an application of the language we show how to reprogram Heapsort in ACETT. This leads to the first Randomness preserving variant of the algorithm, solving an open problem stated by Knuth and Edelkamp, with wider repercussions for Automated Average Case Analysis.
We show how this work goes well beyond the state of the art in three main stream areas in Computer Science: Automated Average Case Analysis, Real-Time Languages and Random Structures.