The Choice Calculus
For Variation Maintenance

Project Description

Managing variation is an important problem in software engineering that takes different forms, ranging from version control and configuration management to software product lines. Our current work in this area focuses on the choice calculus, a fundamental representation for software variation that can serve as a common language of discourse for variation research, filling a role similar to lambda calculus in programming language research.

About the Choice Calculus

At the core of the choice calculus are choices, which represent different alternatives that can be selected. Choices are annotated by names, which group choices into dimensions. Dimensions provide a structuring and scoping mechanism for choices. Moreover, each dimension introduces the number of alternatives each choice in it must have and tags for selecting those alternatives. The semantics of the choice calculus is defined via repeated elimination of dimensions and their associated choices through the selection of a tag defined by that dimension.

The choice calculus obeys a rich set of laws that give rise to a number of normal forms and allow the flexible restructuring of variation representations to adjust to the needs of different applications.

Among the potential applications of the choice calculus are feature modeling, change pattern detection, property preservation, and the development of change IDEs. We have also successfully applied the choice calculus in the development of type systems for variational languages and in the design of type systems that produce better type error messages.

Selected Publications

Guided Type Debugging, Sheng Chen and Martin Erwig
Int. Symp. on Functional and Logic Programming, LNCS 8475, 35-51, 2014

Counter-Factual Typing for Debugging Type Errors, Sheng Chen and Martin Erwig
ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, 583-594, 2014

Early Detection of Type Errors in C++ Templates, Sheng Chen and Martin Erwig
ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, 133-144, 2014

Extending Type Inference to Variational Programs, Sheng Chen, Martin Erwig, and Eric Walkingshaw
ACM Transactions on Programming Languages and Systems, Vol. 36, No. 1, 1:1--1:54, 2014

An Abstract Representation of Variational Graphs, Martin Erwig, Eric Walkingshaw, and Sheng Chen
ACM Int. Workshop on Feature-Oriented Software Development, 25-32, 2013

The Choice Calculus: A Formal Language of Variation, Eric Walkingshaw
Doctoral Thesis, Oregon State University, 2013

Adding Configuration to the Choice Calculus, Martin Erwig, Klaus Ostermann, Tillmann Rendel, and Eric Walkingshaw
ACM Int. Workshop on Variability Modelling of Software-Intensive Systems, 13:1-13:8, 2013

Variation Programming with the Choice Calculus, Martin Erwig and Eric Walkingshaw
Generative and Transformational Techniques in Software Engineering, LNCS 7680, 55-100, 2013

An Error-Tolerant Type System for Variational Lambda Calculus, Sheng Chen, Martin Erwig, and Eric Walkingshaw
ACM SIGPLAN Int. Conf. on Functional Programming, 29-40, 2012

A Calculus for Modeling and Implementing Variation, Eric Walkingshaw and Martin Erwig
ACM SIGPLAN Conf. on Generative Programming and Component Engineering, 132-140, 2012

The Choice Calculus: A Representation for Software Variation, Martin Erwig and Eric Walkingshaw
ACM Transactions on Software Engineering and Methodology, Vol. 21, No. 1, 2011, 6:1- 6:27

#ifdef Confirmed Harmful: Promoting Understandable Software Variation, Duc Le, Eric Walkingshaw, and Martin Erwig
IEEE Int. Symp. on Visual Languages and Human-Centric Computing, 143-150, 2011

Optimizing the Product Derivation Process, Sheng Chen and Martin Erwig
IEEE Int. Software Product Line Conference, 35-44, 2011

Program Fields for Continuous Software, Martin Erwig and Eric Walkingshaw
ACM SIGSOFT Workshop on the Future of Software Engineering Research, 105-108, 2010

A Language for Software Variation, Martin Erwig
ACM SIGPLAN Conf. on Generative Programming and Component Engineering, 3-12, 2010

Variation Programming

Here is the version of the Haskell DSEL for variation programming used in my tutorial given at the 2011 GTTSE summer school.
You need a recent version of the GHC Haskell compiler, or even better the Haskell Platform, to use the code.

How to use the program: Download the zip file, and unzip it. This will create a directory GTTSE. Change to that directory and load one of the example files into ghci by executing, for example, ghci Examples/List.hs.


This project is supported by the Air Force Office of Scientific Research under the grant FA9550-09-1-0229 and by the National Science Foundation under the grants CCF-0917092, CCF-1219165, and IIS-1314384.
last change: April 19, 2014 Martin Erwig