SiMoL– A Modeling Language for Simulation and (Re-)Configuration∗ Iulia Nica and Franz Wotawa† Technische Universität Graz, Institute for Software Technology Inffeldgasse 16b/2, Graz, Austria {inica,wotawa}@ist.tugraz.at Abstract the requirements are a solution of the re-configuration prob- lem. Simulation and configuration play an important In order to provide a method for computing solutions for a role in industry. Modeling languages like Mat- given re-configuration problem we need to state the problem lab/Simulink or Modelica, which are often used to in a formal way. Therefore, we require a modeling language model the dependencies between the components for stating systems comprising components and their relation- of physical systems, are less suitable for the area ships. In principle, formal languages like first order logic or of knowledge-based systems. For these languages, constraint languages would be sufficient for this purpose. But the description of knowledge and its connection using such languages usually is not easy and prevents systems to a theorem prover for nonmonotonic reasoning based on such languages to be used in practice. Hence, there (needed for configuration tasks) is, due to technical is a strong need for easy to learn and use modeling languages reasons, almost impossible. In this paper we focus that are expressive enough to state configuration problems. on a language that can be used for both simulation The SiMoL language we introduce in this paper serves this and configuration purposes. SiMoL is an object- purpose. The language itself is from a syntactical point of oriented language that allows representing systems view close to Java. The idea behind SiMoL is to provide a comprising basic and hierarchical components. language that can be used for (restricted) simulation and con- figuration at the same time. SiMoL is an object-oriented language with multiple inher- 1 Introduction itance and allows for stating constraints between variables. Beside the basic data types like integer and boolean, SiMoL The adaptation of technical systems after deployment to en- makes use of component instances. All component instances sure the desired system’s functionality over time is an impor- are statically declared. In this paper we focus on describing tant task and can never be avoided. Reasons for adaptation are the syntax and the semantics of SiMoL. necessary corrections due to faults in system parts, changes in user requirements, or changes of technology among oth- ers. All activities necessary for increasing the lifetime of a 2 Related research system and retaining its usefulness are summarized under the Over time, the AI community has developed a large variety general term maintenance. of configuration tools that fitted the different necessities and In our research we focus on system changes due to changes goals in each practical area, thus creating a strong foundation in requirements. For example, consider a cellular network for newcomers. As preamble to our approach, we shortly re- where the base stations are initially configured to ensure cur- call three configuration systems, that make use of constraint rent and future needs to some extent. Due to changes in programming. the environment, i.e., new apartment buildings constructed in ConBaCon [John and Geske, 1999 ] treats the special case reach of the base station or an increased use of cellular net- of re-configuration, using the conditional propagation of con- works for data communication, the base station or even the lo- straint networks and has its own input language - ConBa- cal topology of the network has to be adapted. This adaption ConL. In [John and Geske, 1999 ], the authors present Con- can more or less be classified as a re-configuration problem BaConL, a ”largely declarative specification language”, by where the current system’s structure, behavior, and the new means of which one can specify the object hierarchy, the requirements are given as input. Changes in the structure and context-independent constraints and the context constraints. behavior of the system in order to cope with the changes in Furthermore, the constraints are divided into Simple Con- straints, Compositional Constraints and Conditional Con- ∗ Authors are listed in alphabetical orde. The work presented in straints. this paper has been supported by the BRIDGE research project Sim- LAVA is another successful automated configurator [Fleis- ulation and configuration of Mobile networks with M2M Applica- chanderl et al., 1998 ], used in the complex domain of tele- tions (SIMOA), which is funded by the FFG. phone switching systems. It makes use of generative con- † Corresponding author. straints and is the successor of COCOS [Stumptner et al., 1994], a knowledge-based, domain independent configura- modeling systems. Figure 1 depicts a small system compris- tion tool. The modeling language is ConTalk, an enhanced ing 4 components, i.e., a power supply (P S), an acceleration version of LCON that follows the Smalltalk notation. A Con- sensor (AS), a GPS sensor (GP S), and a communication de- Talk constraint is a statement which describes a relationship vice (CD). The communication device is used for sending between components ports or between the attributes values. the measured sensor information to a server. The power sup- A powerful configuration system that combines constraint ply is for providing electricity to the connected components. programming(CP) with a description logic(DL) is the ILOG All these components have a behavior and provide function- (J)Configurator [Junker and Mailharro, 2003 ]. The combined ality. CP-DL language, in which the configuration problem is for- For the purpose of specifying functionality we introduce mulated provides, on the one hand, the constraints, needed a function f ct that maps a component to a set of attributes, in the decision process, and on the other hand, the con- which indicate a certain functionality. For our example, we structs of the description logic, able to deal with unknown introduce the attributes ad, gps, comm to state the accelera- universes. When solving the problem, the constructs of de- tion sensor functionality, the gps functionality, and the ability scription logic, which are well-suited to model the configura- for communication respectively. tion specific taxonomic and partonomic relations, are mapped f ct(AS) = {ad} f ct(GP S) = {gps} f ct(CD) = {comm} on constraints and thus the wide range of constraint solving algorithms may be used. We now specify additional constraints of the system. The The other field following constraint formally represents the requirement that of interest for our the power provided by P S must be larger or at least equiva- research has been lent to the sum of the power consumption of the other com- the modeling lan- ponents: power(P S) ≥ power(AS) + power(GP S) + power(CD) Communication guages currently device (CD) used for simula- Moreover, we state that the device has to provide at least tion of technical ad, gps, comm functionality. systems. Mat- f ct(AS) ∪ f ct(GP S) ∪ f ct(CD) ⊇ {ad, gps, comm} 4 Acceleration lab/Simulink Power supply sensor Finally, we have the requirement that the sum of the cost (PS) and Modelica (AS) of each part of the device is not allowed to exceed a certain 5 are the most pre-defined maximum cost. famous ones cost(P S) + cost(AS) + cost(GP S) + cost(CD) ≤ max cost in the area of GPS sensor In configuration we are interested in providing specific im- dynamic systems (GPS) plementations of the components P S, AS, GP S, and CD modeling and such that all requirements are fulfilled and no constraint is simulation. When violated. Hence, what we do now for our running example, working with is to introduce specific instances of the generic components Simulink, the Figure 1: A small sensor systems with different costs and power consumptions. Table 1 sum- user is capable marizes all the used concrete component implementations. of modeling the A valid configuration is now a set of components that ful- desired system in the graphical interface, based on the large fills all constraints. For example, when assuming maximum library of standard components (called blocks). Also making cost of 60, the set {P S 1 , AS2 , GP S1 , CD2 } is a valid con- use of predefined building blocks, Modelica, on the other figuration but {P S 2 , AS2 , GP S1 , CD2 } is not because of vi- side, is an equation-based object-oriented language with olation of the cost constraint. multi-domain modeling capability. Although both of them Throughout this paper we make use of this example and are complex languages, capable of modeling a great variety show how SiMoL can be used for modeling such systems. of components, neither Simulink or Modelica can be used for re-configuration purposes, as the description of knowledge 4 SiMoL definition and its connection to a theorem prover for nonmonotonic reasoning (needed for configuration tasks) is, due to technical In order to define SiMoL we discuss its syntax and seman- reasons, almost impossible. tics as well as its capability to be used for re-configuration Throughout the rest of this paper, we present our model- purposes. ing language - SiMoL. SiMoL can be applied in both simula- tion and re-configuration domains, using the powerful mech- SiMoL syntax: As already mentioned, SiMoL uses a Java- anism of constraint solving and hence being highly scalable like syntax and the common conventions compass most of for complex simulation and re-configuration tasks. the defined tokens: identifiers for any type of component and attribute, integer and boolean literals, separators, arithmetic 3 An example and relational operators (+, −, ∗, /, =, <, >, <=, >=, ! =), In this paper we make use of the following small example to special tokens - comments, reserved words and literals. discuss SiMoL, as well as re-configuration using SiMoL for Additionally, SiMoL offers support for using units of mea- surement, thus creating a more realistic model. 4 www.mathworks.com Another feature of the language, that provides direct con- 5 www.modelica.com trol over the possible values of a component attribute, is the Generic component Instance 1 Instance 2 PS P S1 : costs(P S1 ) = 10, power(P S1 ) = 10 P S2 : costs(P S2 ) = 20, power(P S2 ) = 15 AS AS1 : costs(AS1 ) = 2, power(AS1 ) = 4 AS2 : costs(AS2 ) = 20, power(AS2 ) = 1 GP S GP S1 : costs(GP S1 ) = 6, power(GP S1 ) = 5 CD CD1 : costs(CD1 ) = 10, power(CD1 ) = 10 CD2 : costs(CD2 ) = 20, power(CD2 ) = 4 Table 1: The component instances for our small sensor system component CD{ attribute int power, costs; Now the additional constraints of the system become: constraints{ power(P S) ≥ power(AS) + power(GP S) power={4,6,10} W; +power(CD) + power(M ) costs={10..30}; } } f ct(AS) ∪ f ct(GP S) ∪ f ct(CD) ∪ f ct(M ) ⊇ {ad, gps, comm, mdm} Figure 2: SiMoL: initialization of attributes with integer val- cost(P S) + cost(AS) + cost(GP S) + cost(CD) ued ranges +cost(M ) ≤ max cost The problem appears if the pre-defined maximum cost is initialization of attributes with integer valued ranges, as il- always exceeded, because of the new added component. In lustrated in fig. 4. other words, we can not afford both a modem and a com- Basically, a program written in SiMoL comprises 3 sec- munication device. Therefore, a new component type - a tions: a knowledge base declaration section, which is op- communication device with integrated modem (M DC)- will tional, an import declaration section, which is also optional, solve the case (under the assumption that cost(M DC) ≤ and a component definition section, that is the main construct- cost(CD) + cost(M )). In SiMoL, the M DC definition has ing unit of a SiMoL program and it is mandatory. Gener- the following syntax: ally, each component will posses a set of attributes and will component MDC extends DC,M { introduce constraints in the system. The attributes decla- constraints{ ration is marked by the attribute keyword, whilst the power={4,6} W; relations stated between the component attributes and new- costs={2..30};}} component instance-declaration statements appear enclosed In the constraints section, we may have the following types in the constraints{ . . . } block. By convention, an of statements: empty component definition section is not allowed, i.e., if the constraints block is missing, we have to declare at least one • an empty statement: ;, attribute for the current component. Furthermore, in the case • a component instance declaration: GPS1 gps1; Op- of derived components, the opposite holds: even with no at- tionally, one can also initialize its attributes: GPS1 tributes declared, we may state constraints over the inherited gps1{costs=100}; attributes. For instance: Using this kind of statements, we define the subcompo- component AS{ nent hierarchy in our model, i.e., the partonomy rela- attribute int power, costs; tions. The cardinality of these relations (i.e., the number constraints{ of subcomponents which can be connected to a certain power={4,6} W; costs={2..30}; }} component) is always finite - we cannot have an unlim- component AS1 extends AS{ ited number of components in our model. constraints{ • an arithmetic or/and boolean expression: power=4; ps1.power>=sum([as1,gps2,cd1],power); costs=2;}} • a conditional block: The ability to extend the functionality and behavior of ex- if(sum([ps1,as1,gps1,cd1],costs) isting components is of great importance for the taxonomic <= max cost) structure of a configuration domain. In any object oriented cost=sum([ps1,as1,gps1,cd1],costs); languages, the taxonomy relations are represented through else cost=100; the inheritance mechanism. We designed SiMoL with mul- tiple inheritance. In order to demonstrate the necessity of this • a forall block: feature, let us consider the following scenario. For our small forall(AS1){ power=10 W; costs={1..10};} system described in Section 3, we introduce a new require- ment that refers to a specific signal modulation which can • an exist statement, e.g.: be accomplished by a new component - a modem (M ). The exist(at most(1),GPS1,costs=30);. modem receives the measured sensor information and trans- We also mention the built-in functions min, max, mits the modified signal to the communication device. The sum, product, meant to ease the manipulation of large function f ct from Section 3 will similarly depict for M the sets of component instances. modulation-demodulation functionality : Adopting a clear Java-like syntax, SiMoL is a f ct(M ) = {mdm} functionality-based, declarative language, creating a good environment for simulation, and, at the same time, it Finally, the configuration constraints are divided into com- provides many embedded functionalities specially designed patibility constraints, requirement constraints and resource for configuration purposes. constraint. The first ones specify which value combina- tions are legal for the attributes given in the model and they are modeled in SiMoL through C attr val and Cattr attr Semantics of SiMoL: Because of space reasons we only constraints. The requirement constraints describe a rela- briefly define the semantics of the language SiMoL where we tion between two component attributes ( [Rossi et al., 2006]), rely on mathematical equations. In particular, we map ev- which is best depicted by combining C cond with Cattr val or ery statement to a mathematical equation, and combine these Cattr attr . Moreover, the resource constraints on numerical equations for a component, taking care of component inheri- attributes were intensively addressed throughout this paper. tance and component instances. Consequently, we find the expressive power of the lan- For each component defined in SiMoL we have a set of guage sufficient for modeling the discussed configuration equations that is defined within the constraints { . . . knowledge forms. As also stated in [Rossi et al., 2006], the } block. Moreover, a component also receives equations configuration problem complexity may vary from very sim- from its super components and the instances used in the ple option selection problems to complex cases, but they all component definition. For example, when specifying GPS1 appear as combinations of the specified knowledge forms. gps; in the variable declaration a new instance of GPS1 is generated. All constraints of GPS1 are added to the con- 5 Conclusion straints of the component. The semantics of SiMoL is now In this paper, we have presented SiMoL- a new functional- nothing else than the union of all constraints defined includ- based, declarative modeling language, that serves simulation ing inherited constraints and constraints coming from com- and re-configuration purposes. The novelty of our approach ponent instances. is designing a language that is easy to learn and capable of We discuss the expressiveness of the language by classify- modeling large and complex systems. SiMoL can cope with ing its capabilities with respect to the framework offered in large models and be also efficient with respect to computa- the chapter on configuration from [Rossi et al., 2006]. In the tion time (simulation). Although re-configuration is not fully context of the successful integration of constraint program- implemented for the SiMoL language, several ideas are cur- ming in solving a large variety of configuration problems, the rently analyzed and implemented, such that in the near future author defines several distinguishing constraint models, each a fully working re-configurator can be used for SiMoL mod- corresponding to a specific type of configuration problem. To els. In future research we mainly focus on providing a sound set up the constraint model, the appropriate variables and con- and complete configuration algorithm that takes SiMoL mod- straints are deduced from the given configuration knowledge. els and requirements as input and computes valid configura- The author states that this knowledge may have three differ- tions as output. ent forms: the component catalogs, the component structure and the component constraints. The catalog knowledge, as defined in [Rossi et al., 2006], References is modeled in SiMoL by means of the generic components [Fleischanderl et al., 1998 ] Gerhard Fleischanderl, Ger- (correspondent to the term of technical types in [Rossi et al., hard E. Friedrich, Alois Haselböck, Herwig Schreiner, 2006]) and the concrete components( derived (extended) from and Markus Stumptner. Configuring large systems using generic component/s or from other concrete component/s, in generative constraint satisfaction. In IEEE Intelligent our case, and correspondent to the term of concrete or func- Systems & their applications, pages 59–68, 1998. tional types in [Rossi et al., 2006]). Both generic and concrete [John and Geske, 1999 ] Ulrich John and Ulrich Geske. Re- components have a set of attributes, mapped to variables in configuration of Technical Products Using ConBaCon. In the constraint model. Based on this kind of knowledge, we Proceedings of WS on Configuration at AAAI99, Orlando, build the catalog constraints ( [Rossi et al., 2006]), which are 1999. stated over the set of variables and formulated by means of [Junker and Mailharro, 2003 ] Ulrich Junker and Daniel Cattr val and Cattr attr constraints. Mailharro. The logic of ILOG (J)Configurator: Combin- The structural knowledge of a SiMoL model is determined ing Constraint Programming with a Description Logic. In by the component instances declared in the current model. Proceedings of IJCAI-03 Configuration WS, pages 13–20, In this manner, we generate for our system the set of sub- 2003. components, that are either generic or extended components. The logic behind this mechanism has been previously de- [Rossi et al., 2006] Francesca Rossi, Peter van Beek, and tailed, when presenting the semantics of the language. We Toby Walsh. Handbook of Constraint Programming recall that the SiMoL model is in fact a component, which (Foundations of Artificial Intelligence). Elsevier Science describes the configuration problem. The connection ports Inc., New York, NY, USA, 2006. defined in [Rossi et al., 2006] have no correspondent term in [Stumptner et al., 1994 ] Markus Stumptner, Alois SiMoL yet, but the connection between component instances Haselböck, and Gerhard Friedrich. COCOS - a tool is possible through C attr attr constraints. Also the statement for constraint-based, dynamic configuration. In Proceed- in [Rossi et al., 2006] according to which ”the sets of direct ings of the 10th IEEE Conference on AI Applications subtypes of two types are mutually disjoint” does not hold in (CAIA), San Antonio, March 1994. our approach, because we accept multiple inheritance.