WG211/M12Sloane

Domain-specific algorithm analysis by Tony Sloane

Analysis of the run-time complexity of an algorithm begins by abstracting the time taken by basic operations. We then consider how many times each basic operation will be performed in terms of some measure of problem size. The result is a formula that estimates run-time in terms of the basic operation times and the problem size. Space usage can be analysed in a similar way.

This talk will present some preliminary work that applies this method to the analysis of domain-specific algorithms. Our goal is to provide a way for algorithms expressed in domain-specific languages to be compared. We show that the abstraction of basic operations is mostly pre-determined by the domain and therefore does not have to be done anew for each algorithm. The analysis of repetition depends on some properties of domain-specific data and the high- level operations that are performed on that data.

The main example is a comparison between approaches to name analysis in programming languages as expressed by an attribute grammar domain-specific language. We aim to get a clear view of the differences between an approach that propagates an environment around a syntax tree and one that uses reference attributes to represent naming information by its declarations.