Home

The Beauty and the Beast: Separating Design from Algorithm

The Beauty and the Beast: Separating Design from Algorithm
application/pdf iconecoop11-preprint.pdf
Related tools & artifacts:
Conference Paper: ECOOP'11, July, 2011

We present an approach that partitions a software system into its algorithmically essential parts and the parts that manifest its design. Our approach is inspired by the notion of an algorithm and its asymptotic complexity. However, we do not propose a metric for measuring asymptotic complexity (efficiency). Instead, we use the one aspect of algorithms that drives up their asymptotic complexity – repetition, in the form of loops and recursions – to determine the algorithmically essential parts of a software system. Those parts of a system that are not algorithmically essential represent aspects of the design. A large fraction of inessential parts is indicative of "overdesign", where a small fraction indicates a lack of modularization. We present a metric, relative essence, to quantify the fraction of the program that is algorithmically essential. We evaluate our approach by studying the algorithmic essence of a large corpus of software system, and by comparing the measured essence to an intuitive view of design "overhead".

@inproceedings{Zaparanuks:2011:BBS:2032497.2032502, author = {Zaparanuks, Dmitrijs and Hauswirth, Matthias}, title = {The beauty and the beast: separating design from algorithm}, booktitle = {Proceedings of the 25th European conference on Object-oriented programming}, series = {ECOOP'11}, year = {2011}, isbn = {978-3-642-22654-0}, location = {Lancaster, UK}, pages = {27--51}, numpages = {25}, url = {http://dl.acm.org/citation.cfm?id=2032497.2032502}, acmid = {2032502}, publisher = {Springer-Verlag}, address = {Berlin, Heidelberg}, }