Trustworthy Systems

Towards a representation theorem for coloring algebra

Authors

Peter Hoefner

NICTA

UNSW

Abstract

Coloring algebra (CA) captures common ideas of feature oriented programming (FOP), a general programming paradigm that provides formalisms, methods, languages, and tools for building maintainable, customisable, as well as extensible software. FOP has widespread applications from network protocols and data structures to software product lines. It arose from the idea of level-based designs, i.e., the idea that each program (design) can be successively built up by adding more and more levels (features). Later, this idea was generalised to the abstract concept of features. The algebra itself is based on rings and offers simple and concise axioms for feature composition and feature interaction. From these two operations algebraic laws describing products, product lines and other concepts of FOP can be derived.

The talk will start with a brief introduction to coloring algebra. In particular I will discuss the interplay between feature composition and interaction. I will also present different models and discuss their relationship to and applicability for feature oriented programming.

The examples will show that the choice for defining feature composition is limited. In fact, I will prove that the composition operator is always isomorphic to symmetric-difference in a set-theoretic model. The proof can easily be derived from Kronecker Basis Theorem. By this result we have “half” a representation theorem for CA. A detailed understanding of feature interaction is missing for the characterisation and the proof of a full representation theorem. Therefore, I will conclude the talk with some observations and conjectures on the structure of coloring algebra, which hopefully helps to come up with a full representation theorem.

BibTeX Entry

  @misc{Hoefner_12,
    author           = {H\"ofner, Peter},
    booktitle        = {Workshop on Lattices and Relations},
    keywords         = {fosd},
    month            = aug,
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/6567.pdf},
    title            = {Towards a Representation Theorem for Coloring Algebra},
    year             = {2012}
  }

Download