Parsimony principles for software components and metalanguages

ABSTRACT

Software is a communication system. The usual topic of communication is program behavior, as encoded by programs. Domain-specific libraries are codebooks, domain-specific languages are coding schemes, and so forth. To turn metaphor into method, we adapt tools from information theory - the study of efficient communication - to probe the efficiency with which languages and libraries let us communicate programs. In previous work we developed an information-theoretic analysis of software reuse in problem domains. This new paper uses information theory to analyze tradeoffs in the design of components, generators, and metalanguages. We seek answers to two questions: (1) How can we judge whether a component is over- or under-generalized? Drawing on minimum description length principles, we propose that the best component yields the most succinct representation of the use cases. (2) If we view a programming language as an assemblage of metalanguages, each providing a complementary style of abstraction, how can these metalanguages aid or hinder us in efficiently describing software? We describe a complex triangle of interactions between the power of an abstraction mechanism, the amount of reuse it enables, and the cognitive difficulty of its use.

References

1. D. Abrahams and A. Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. Addison-Wesley, 2004.
2. A. Alexandrescu. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, 2001.
3. B. Barak, R. Shaltiel, and A. Wigderson. Computational analogues of entropy. In S. Arora, K. Jansen, J. D. P. Rolim, and A. Sahai, editors, RANDOM-APPROX, volume 2764 of Lecture Notes in Computer Science, pages 200--215. Springer, 2003.
4. F. J. Barrett and D. L. Cooperrider. Generative metaphor intervention: A new approach for working with systems divided by conflict and caught in defensive perceptiton. The Journal of Applied Behavioral Science, 26(2):219--239, 1990.
5. D. Bert, P. Drabik, R. Echahed, O. Declerfayt, B. Demeuse, P.-Y. Schobbens, and F. Wautier. LPG: A generic, logic and functional programming language. In H. Ganzinger, editor, ESOP'88, 2nd European Symposium on Programming, volume 300 of Lecture Notes in Computer Science, pages 376--377, Nancy, France, 21-24 Mar. 1988. Springer.
6. A. F. Blackwell, C. Britton, A. Cox, T. Green, C. Gurr, G. Kadoda, M. S. Kutar, M. Loomes, C. L. Nehaniv, M. Petre, C. Roast, C. Roes, A. Wong, and R. M. Young. Cognitive dimensions of notations: Design tools for cognitive technology. Lecture Notes in Computer Science, 2117:325--341, 2001.
7. J. Carette. Understanding expression simplification. In ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 72--79, New York, NY, USA, 2004. ACM Press.
8. K. Czarnecki and U. W. Eisenecker. Generative Programming: Methods, Tools, and Applications. Addison-Wesley, 2000.
9. R. Garcia, J. Jarvi, A. Lumsdaine, J. Siek, and J. Willcock. A comparative study of language support for generic programming. In Proceedings of the 18th ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pages 115--134. ACM Press, 2003.
10. J. A. Goguen. Principles of parameterized programming. pages 159--225. ACM Press, New York, NY, USA, 1989.
11. T. R. G. Green. Cognitive dimensions of notations. In Proceedings of the HCI'89 Conference on People and Computers V, Cognitive Ergonomics, pages 443--460, 1989.
12. P. N. Klein. Computing the edit-distance between unrooted ordered trees. In G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci, editors, Proceedings of the 6th Annual European Symposium on Algorithms, ESA'98 (Venice, Italy, August 24-26, 1998), volume 1461 of LNCS, pages 91--102. Springer-Verlag, Berlin, 1998.
13. K. Knight. Unification: A multidisciplinary survey. ACM Computing Surveys, 21(1):93--124, Mar. 1989.
14. B. Liskov, A. Snyder, R. Atkinson, and C. Schaffert.Abstraction mechanisms in CLU. Commun. ACM, 20(8):564--576, 1977.
15. D. R. Musser and A. A. Stepanov. Algorithm-oriented generic libraries. Software: Practice and Experience, 24(7):632--642, July 1994.
16. J. Rissanen. Stochastic Complexity in Statistical Inquiry, volume 15 of Series in Computer Science. World Scientific, 1989.
17. D. Schön. Generative metaphor: A perspective on problem setting in social policy. In A. Ortony, editor, Metaphor and Thought. Cambridge University Press, 1978.
18. M. Shaw, W. A. Wulf, and R. L. London. Abstraction and verification in Alphard: defining and specifying iteration and generators. Commun. ACM, 20(8):553--564, 1977.
19. T. Sheard and J. Hook. Type safe meta-programming. Unpublished manuscript, Oregon Graduate Institute, November 1994.
20. W. Taha and T. Sheard. MetaML and multi-stage programming with explicit annotations. Theoretical Computer Science, 248(1-2):211--242, Oct. 2000.
21. T. L. Veldhuizen. Using C++ template metaprograms. C++ Report, 7(4):36--43, May 1995. Reprinted in C++ Gems, ed. Stanley Lippman.
22. T. L. Veldhuizen. Software libraries and their reuse: Entropy, Kolmogorov complexity, and Zipf's law. In OOPSLA 2005 Workshop on Library-Centric Software Design (LCSD'05), 2005.
23. T. L. Veldhuizen. Tradeoffs in metaprogramming. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Jan. 2006.
24. D. J. Wheeler. The use of sub-routines in programmes. In ACM '52: Proceedings of the 1952 ACM national meeting (Pittsburgh), pages 235--236. ACM Press, 1952.
25. G. V. Wilson. Personal communication. December 2005.
26. K. Zhang and D. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput., 18:1245--1262, 1989.

Index Terms

• Software and its engineering

  • Software creation and management

    • Designing software

    • Software development techniques

      • Reusability

  • Software notations and tools

    • Software libraries and repositories