Feature models are a wide-spread approach used for expressing variability in software product lines. Answer set programming (ASP) is nowadays an increasingly popular approach to configuration knowledge representation. In this paper, we study the similarities between feature modeling and configuration knowledge representation with ASP. We define the feature configuration problem utilizing ASP, and show two different ways using an example of translating the basic feature modeling concepts embodied in the graphical feature models into ASP programs. This way we want to emphasize the role of ASP as a means to tackle the feature configuration problem.
Features and feature models [
Software product line variability, and consequently, feature
models, can grow large and complex. Due to the combinatorial explosion,
analyzing feature models and finding a valid feature configuration is
infeasible to do manually with large-scale feature models [
In the field of mechanical and physical products, configuration has
a long and successful history as a basis for mass-customization, see,
e.g., [
As a supporting tooling, Answer Set Programming (ASP) is an
increasingly important formalism for the representation of
configuration models. Configuration is one of the first applications of ASP
solving; the requirements of configuration problems were taken into
account already in the development of the early ASP tool Smodels
[
The two disciplines of software product lines and configurable
products have similar goals and challenges in the variability
management [
RQ1: How can the feature configuration problem be stated through ASP? RQ2: What are the different ways to represent a feature model diagram as an ASP program? RQ3: What are the synergies in the variability management between feature modeling and product configuration?
Figure 1 illustrates the strategy that this paper utilizes to answer the research problem and questions. In particular, it shows how the graphical feature diagrams are represented with textual languages, and these textual languages are then automatically translated to ASP programs. Since the same graphical feature model can be represented both with the textual feature modeling language (Kumbang) as well as with the product configuration language (PCML), it is possible to compare and identify conceptual similarities and differences between software variability management and product configuration. Moreover, the figure illustrates the strategy of utilizing intermediate level languages: this omits the need to manually write ASP programs directly, and consequently, any inherent cognitive difficulties.
The contributions of this paper are the following. Firstly, we adapt
the existing work [
The remainder of this paper is organized as follows. Section 2 lays out the background as a previous work. Section 3 defines the feature configuration task and problem with ASP. Section 4 shows how graphical feature models can be represented as ASP programs by translating them through a textual feature modeling language called Kumbang (cf. Figure 1). Section 5 demonstrates that the same graphical feature model can be represented by Product Configuration Modeling Language (PCML) and its translation to ASP. Section 6 discusses the similarities of the software variability and traditional product configuration. Section 7 concludes. 2 2.1
A feature in a feature model can be seen as a characteristic of a
system that is visible to the end-user [
Given a set of features, a feature model represents the variability
and relations of those features. A feature model is represented as a
hierarchically arranged set of features that consists of relations between
a parent (or compound) feature and its child features (or subfeatures)
and cross-hierarchy constraints [
At least four basic relations between parent and child features can
be identified [
Additionally, there can be cross-hierarchy constraints. For example, features GPS and Basic are mutually exclusive, which means they cannot be in the same product, whereas feature High resolution must always be included in a product that contains feature Camera. These constraints are presented as annotations in Figure 2.
Various feature models and extensions to basic feature models
have been proposed, as discussed in [
Firstly, there can be feature models with attributes [
Secondly, there can be feature models with cardinality [
The usage of feature models varies from an informal
documentation or visualization to more rigorous usages enabling even
automated analysis. Respectively, the research has matured from the early
notations [
As summarized in [
ASP makes it possible to express the problem as a theory
consisting of logic program rules with clear declarative semantics, and the
stable models, i.e., the answer sets of the theory correspond to the
solutions to the problem [
Programs that follow the Answer Set Programming paradigm are
a generalization of normal logic programs. A generalized and
unified syntax of ASP programs called ASP-Core-2 has been defined
[
There are a number of ASP solvers available, see [
The authors of this paper have applied weight constraint rule
language (WCRL) that is almost a genuine subset of ASP-Core-2. The
languages ASP-Core-2 and WCRL are compatible enough so that the
concrete WCRL logic programs generated by our tools are valid
input to systems based on ASP-Core-2. This was verified with Clingo
version 4.3, available from [
In the following, we describe the basic concepts of weight
constraint rules focusing on the concepts needed in the rest of the paper.
Instead of explaining the concepts utilizing a running example, these
concepts are exemplified for Kumbang in Section 4 and for PCML in
Section 5. For further details and examples, please see [
Cardinality constraints are used as the primary basic building blocks of the product configuration rules. Cardinality constraints are of the form
lfa1; : : : ; an; not b1; : : : ; not bmgu where l and u are the lower and upper bounds of the constraint. Basic atoms are the smallest lexical units, for example a, or b. A literal is an atom b or a not-atom not b. A cardinality constraint is satisfied by a set of atoms S if the number of those literals in fa1; : : : ; an; not b1; : : : ; bmg that are satisfied by S is between the bounds l and u.
A constraint rule is an expression of the form
C0 :- C1; : : : ; Cn where the body of the rule consists of a number of cardinality constraints Ci, and the head C0 cannot contain negated atoms. A program P is then a set of constraint rules.
For product configuration, the following rules are often useful. Firstly, in choice rules the number of satisfied atoms in the head must be between l and u:
lfa1; : : : ; angu :- C1; : : : ; Cn Secondly, a rule with an empty head yields an integrity constraint :- C1; : : : ; Cn, that is, an unsatisfiable constraint that allows specifying inconsistent situations where finding the answer is not possible. Finally, a rule with an empty body is called a fact. For example, a fact C0 states that C0 is always true.
Given a set of atoms S, a rule C0 :- C1; : : : ; Cn is satisfied iff S satisfies C0 whenever S satisfies each of C1; : : : ; Cn. A program P is satisfied by S if each rule in P is satisfied by S. A stable model or answer set of a weight constraint rule program is defined as a set of atoms that 1) satisfies the program (is a classical model of the program) and 2) every atom in a stable model is justified (grounded) by the rules in the program. For example, consider the logical formula b ^ (b ^ :c ! a) that has three (classical) models fb; cg, fa; bg and fa; b; cg. The answer set program
b: a :- b; not c:
has one stable model fa; bg. For the formalization of this definition,
refer to [
Variable-free ground weight constraint rules discussed up to now become more practical by allowing the use of variables, function symbols, and predicates. A rule with variables is treated as a short hand for all its ground instantiations with respect to the Herbrand universe of the program. Decidability is retained by allowing only domain-restricted rules. Ignoring the details, each variable in a rule must appear in a domain predicate which occurs positively in the body of the rule. For example, p(X) :- q(X) over constants fa; b; cg is an abbreviation of
p(a) :- q(a); p(b) :- q(b); p(c) :- q(c)
Given predicates and domains, rules with the so called conditional literals are frequently applied in product configuration. For example, a fact with predicate chair and domain predicate member states that every board must have exactly one chair that must also be a member: 1 fchair(X) : member(X)g 1: 3
Research question RQ1 identified the need to address the feature
configuration problem with ASP. In order to utilize ASP and existing
solvers (see Section 2.2), one needs to define the basic concepts of the
feature configuration problem. Figure 4 defines the feature
configuration problem. Here, we adapt the definition of [
Definition of the feature configuration task. Given CM a feature configuration model CM translated to a set of rules, GF a set of ground facts representing the types in CM and unique identifiers for the instances of types, and R a set of rules R representing requirements, is there a feature configuration C, that is, a stable model of CM [ S, such that C satisfies R?
Firstly, a feature configuration model CM in Figure 4 specifies the entities, such as features; their properties, such as feature attributes; and composition structure, i.e. the feature tree structure; and the rules how the entities and their properties can be combined in a proper manner for a valid product. More informally, a feature configuration model represents the variability in the product line. For example, the feature model in Figure 2 is represented as one configuration model CM .
Within the definition in Figure 4, a distinction is made between types in a configuration model and instances in a configuration. Types in a configuration model define the properties of their individuals that can appear in a configuration. For example, in Figure 2, feature type storage defines the different attributes and their values, whereas feature instance storage in the actual product has a specific value for the size, for example 16 GB.
Ground facts GF in Figure 4 describe the possible feature instances and the attribute values of instances that can exist in a feature configuration. For example, for the feature Storage in Figure 2, a ground fact featStorage(i). indicates that feature instance with a unique identifier i is of feature type Storage. Additionally, a ground fact hasattr(i,attrsizeGB,16). tells that this instance has a specific attribute value assignment to indicate 16GB storage.
The set of rules R define requirements thus having a different status from the rules in the configuration model: these requirements represent the requirements that a specific product instance must satisfy. In a valid product configuration, the requirements must be satisfied by a configuration but cannot justify any elements in it. For a feature configuration problem, the requirements are stated as features that must be present in the configuration, or as attribute values that these features have. For example, for Figure 2, one requirement could be stated as hasattr(i,attrsizeGB,16)., meaning that there must be 16 GB storage in the product.
A feature configuration C consists of a set of positive and negative atoms. Positive atoms represent the feature instances and attribute values that are in the configuration. Due to the characteristics of ASP and stable models discussed in Section 2.2, the feature instances and attribute values in the configuration C, that is, the positive atoms in C, both satisfy the configuration model and its requirements, and are justified by them. For example, among the atoms that would be in the feature configuration for Figure 2, an atom in(i) indicates the inclusion of feature Storage. Further, if the storage is set to 16GB, an atom hasattr(i,attrsizeGB,16) is true, while atoms representing other attribute values, such as hasattr(i,attrsizeGB,32), are false.
Consequently, the feature configuration C in the definition above is both consistent and complete. Informally, a consistent feature configuration is such that no rules of the configuration model are violated. A complete feature configuration is such that all the necessary selections have been made.
An ASP solver can be used to find consistent and complete configurations that meet a set of given requirements, given that such configurations exist. Therefore, the configuration problem definition above and its ASP solution can be used to support both domain and application engineering activities. At the domain engineering level, it can be checked whether the given feature configuration model CM doesn’t have any consistent and complete configurations, which implies a self-contradictory model. At the application engineering level, the configuration task can support the finding of consistent and complete configurations, potentially even specifying the requirements R in an iterative manner.
For supporting the user in the configuration task, deducing the consequences of requirements is based on computing an approximation of the set of configurations satisfying the requirements that are valid but not necessarily all consequences are found. Intuitively, the consequences contain a set of facts that must hold for the configurations satisfying the requirements, a set of facts that cannot be true for the given requirements, and a set of unknown facts.
From the practical point of view, a product line engineer needs to capture the product line features and their commonality and variability into a configuration model CM . There are two options for this representation. The first option is to represent the informal feature model, for example, the visual notation in Figure 2, directly as an ASP program. However, this kind of a modeling task requires skills in logic programming, which may not be the case with an average product line engineer. The second option is to capture the feature model with a machine-processable, but human-readable textual language that utilizes directly the concepts known to a product line engineer, and then automatically translate the resulting middle-level model to an ASP program. This translation to ASP also gives the semantics to the middle-level representation language, as well as enables the use of existing ASP solvers for the configuration task. As is illustrated in Figure 1, this paper takes the latter approach.
In the following, we discuss how feature models can be represented as ASP programs, and consequently, how to represent the configuration model CM . 4
Section 3 presented the feature configuration problem utilizing ASP
programs and identified the need to represent a given feature model
as an ASP program. In the following, we show how the graphical
feature model in Figure 2 and the basic feature modeling concepts
can be represented as ASP programs. This is done in two phases,
as illustrated in Figure 1: firstly, Section 4.1 shows how the feature
model is represented as a textual model in Kumbang, and thereafter
Section 4.2 shows how the textual model in Kumbang is translated to
WCRL automatically with the Kumbang tool set [
In order to enable the feature configuration with ASP, the feature
model in Figure 2 needs to be represented in a form that is both
understandable to a product line engineer, and can be unambiguously
translated to an ASP program. For this purpose, we utilize
Kumbang language [
root feature MobilePhone feature type MobilePhone { contains
Calls calls;
GPS gps[
Storage storage;
sitional relations between features, such as mandatory, optional, and
alternative. As illustrated in Figure 3, the multitude of these
relations can be expressed with one relation: cardinality. In order to
define such relations in the configuration model, the cardinality needs
a placeholder in the textual notation: such a placeholder in Kumbang
is called a part definition. For example, the part definition Media
media[
Thirdly, the compositional structure of the features must be defined. For each part definition, a rule with the following format is added: nfhaspart(X1; X2; P ) : ppart(X1; X2; P; I)gm :- F (X1); in(X1): where F and P are replaced with feature and part names, and n; m replaced with the lower and upper bounds of the cardinality. Predicate haspart is used to indicate that a feature instance is instantiated as a part in the configuration, whereas predicate ppart is merely stating the possible parts. Together, these predicates justify the inclusion of a feature instance through composition:
in(X2) :- haspart(X1; X2; N ); ppart(X1; X2; N; I): Fourthly, attribute definitions are captured with the following rule: 1fhasattr(X; Ad; V ) : Av(V )g1 :- in(X); F (X): where Ad is replaced with the name of the attribute definition, Av with the name of the attribute value type, and F with the name of the defining feature type.
Finally, the configuration model must also define the identifiers for each feature instance. This enables, for example, to state requirements R about the features that must be present in the configuration (see Figure 4). In Figure 6, the feature instances are given identifiers by enumerating all possible instances in the configuration, for example, fact featMobilePhone(i0). gives identifier i0 to feature MobilePhone. Additionally, the identifiers are used to state the possible compositional relations between the instances with the predicate ppart. Using these identifiers, it is possible to state the requirements about the feature instances that must be in the configuration, for example, in(i8). requires that feature Camera must be present in the configuration.
through Product Configuration modeling
In this Section, the example feature model of Figure 2 is represented with a configuration modeling language designed to model the variability of physical products. We also exemplify the corresponding ASP presentation. 5.1
For illustrating the application of a configuration modeling language,
we apply PCML, Product Configuration Modeling Language [
The main concepts of PCML are feature types, their compositional structure, attributes, and constraints. Feature types define the subfeatures (parts) and attributes of their individuals that can appear in a configuration. In a configuration, subfeatures (parts) of a feature individual are realized with feature individuals. The realizing feature individual(s) “fill the role” created by the subfeature definition. If the cardinality includes 0, an empty realization is possible. A configuration is a non-empty tree of feature individuals and individuals representing attribute values. In addition, the compositional structure is explicitly presented.
The main modeling mechanism of this example is the compositional structure. Feature type Mobile Phone t in 7 serves as the root of the compositional structure ’configuration type’, see Figure 7. An individual of the type serves as the root of the configuration.
Feature type Mobile Phone t defines it’s compositional structure through a set of subfeature definitions. A subfeature definition specifies a subfeature name, a non-empty set of possible subfeature types (allowed types for brevity) and a cardinality indicating the valid number of subfeatures. Note that the example of Figure 7 applies a naming convention where the names of feature types end with t and names of subfeatures (parts) with p.
A mandatory subfeature is represented by specifying cardinality 1 and by specifying exactly one allowed type. An example is the mandatory feature Calls p. An optional subfeature is modeled with a subfeature definition whose cardinality is 0 to 1, e.g. the feature GPS p. Alternative features are modeled with cardinality 1 and more than one allowed type. E.g., feature Screen p. Or-subfeatures are not directly supported by PCML, because with large cardinalities individuals of the same type would be allowed. Therefore for modeling Media t, further subfeatures were defined and a constraint added that enforces the presence of at least one subfeature.
The only attribute of the example is Storage t defining an enumerated integer attribute Size GB. 5.2
% if an individual C2 is as part of C1 -> in(C2) in(C2) :- pa(C1,T,C2,Pn), ppa(T,C1,C2,Pn). % exclusive parthood: same individual cannot % be a part of several whole individuals :- 2{pa(C1,T,C2,Pn):ppa(T,C1,C2,Pn)}, compT_Feature(C2). %transitivity of is-a hierachy isa(X,Z):- isa(X,Y), isa (Y,Z),
compTDom(X), compTDom(Y), compTDom(Z). % reflexivity of is-a isa(X,X):- compTDom(X). %Example types % Screen_t is a component type and a subtype of ’Feature’ compTDom(compT_Feature). %Screen types are direct subtypes of ’Feature’ compTDom(compT_Basic_t). compT_Feature(C) :- compT_Basic_t(C). isa(compT_Basic_t,compT_Feature). compTDom(compT_Colour_t). compT_Feature(C) :- compT_Colour_t(C). isa(compT_Colour_t,compT_Feature). compTDom(compT_High_resolution_t). compT_Feature(C) :- compT_High_resolution_t(C). isa(compT_High_resolution_t,compT_Feature). % Storage_t compTDom(compT_StoraStorage_t). compT_Feature(C) :- compT_Storage_t(C). isa(compT_Storage_t,compT_Feature). % attribute Size_GB of Storage_t 1{prop_Storage_t_Size_GB(X,compT_Storage_t,Y):prSpec(Y)}1 :- in(X),compT_Storage_t(X). prSpec(8). prSpec(16). prSpec(32). prSpec(64). %part name Screen_p pan(part_Screen_p). %cardinality 1 1{pa(C1,compT_Mobile_Phone_t,C2,part_Screen_p): ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p)}1 :in(C1),compT_Mobile_Phone_t(C1). % assignment of possible part individuals of allowed % types for part screen_p with helper predicate for. % The automated translation makes such an allocation % for symmetry breaking, which this example % does not need ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p) :compT_Mobile_Phone_t(C1),compT_Basic_t(C2), for(compT_Mobile_Phone_t,C1,C2,part_Screen_p). ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p) :compT_Mobile_Phone_t(C1),compT_Colour_t(C2), for(compT_Mobile_Phone_t,C1,C2,part_Screen_p). ppa(compT_Mobile_Phone_t,C1,C2,part_Screen_p) :compT_Mobile_Phone_t(C1),compT_High_resolution_t(C2), for(compT_Mobile_Phone_t,C1,C2,part_Screen_p). % Constraint compilation omitted for brevity. % it is performed by subexpression.
In this paper, we showed two ways to represent feature models as
ASP programs by utilizing existing textual modeling languages
designed for feature modeling and product configuration modeling. The
use of an intermediate, textual language between the graphical
feature models and logic programs is not that common: it seems
typical that graphical feature diagrams are directly translated, e.g., to
propositional logic [
The benefit of using such intermediate languages and models is that they may be more approachable to product line engineers: they utilize modeling concepts that more or less directly correspond to the concepts used to represent software variability. Such intermediate languages can serve a multitude of purposes: they can be represented graphically and modelled with the aid of graphical tools; they can be created or edited directly if need arises; and they can be automatically translated to ASP programs.
Another option would have been to directly represent or encode the entities and relations in feature models as ASP programs. The benefit of writing directly ASP programs is that the resulting ASP programs most probably are more compact and directly humanreadable. The drawback is that logic programming even in the form of ASP programs might be challenging for a product line engineer not trained in computational logic programming.
For simplicity, our representation in this paper covered some basic concepts of feature models. Nevertheless, the languages discussed in Sections 4 and 5 cover much richer sets of modeling constructs. For example, the capability to represent feature inheritance was not utilized in the examples. Similarly, the literature contains numerous proposed extensions of feature models. Some of them are included in our conceptualizations and corresponding tools (e.g. attributes, cardinalities) while some are not. In any case, a detailed discussion about the needed modeling concepts is a future work item.
By mapping the feature modeling notation to both Kumbang and PCML, we demonstrated that both approaches, one tailored for feature modeling and one for product configuration, can be utilized for modeling software variability. A specific addition to the traditional feature modeling concepts done in this paper is to differentiate between feature instances and feature types. This dichotomy, however, parallels with domain and application engineering in software product families and is, therefore, quite natural for software variability although it has not been applied explicitly in feature modeling.
The product configuration community has applied configuration modeling and configuration techniques in full scale production use for decades. It may be that some modeling constructs and approaches related to managing variability could be carried over to describe and analyze feature models. In such a case, existing analyses and respective tools could be readily utilized.
However, the derivation of product lines is not just about configuration: feature models are applicable to a wide range of settings, not just to configurable software product lines. Because of this, the tools intended for product configuration do not necessarily support all the relevant activities in the application engineering phase of software product lines.
In general, due to the availability of a variety of different
efficient ASP solvers, it seems beneficial to represent feature models
as ASP programs. Despite the fact that the theoretical computational
complexity inherent in the feature configuration problem is NP-hard,
the current ASP solvers are efficient in calculating the stable models
even for programs that represent real-life feature models. We believe
that it is more important to find and utilize real problems in testing
scalability instead of generated random problems. Consequently, we
have configured real problems interactively, without no noticeable
delay: see the configuration model with slightly less than 500
variation points [
This study shows how feature models can be represented as ASP programs by means of two different mappings of a graphical feature diagram through intermediate languages. The representation of feature models as ASP programs enables utilizing existing inference engines that are efficient for practical problems. Moreover, the mapping shows significant similarities between feature modeling and product configuration, in particular demonstrating how a feature model diagram can be presented using a product configuration language. This is one concrete step towards better unification between these two similar disciplines of research.
We acknowledge the financial support of TEKES as part of the Need 4 Speed (N4S) program of DIGILE and the Austrian Research Promotion Agency (Casa Vecchia, 825889).