What email address or phone number would you like to use to sign in to Docs.com?
If you already have an account that you use with Office or other Microsoft services, enter it here.
Or sign in with:
Signing in allows you to download and like content, and it provides the authors analytical data about your interactions with their content.
Embed code for: Analysis of meta-programs: An example
Select a size
1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 International Journal of Software Engineering1 and Knowledge Engineering Vol. 16, No. 1 (2006) 1–253 c
World Scientiﬁc Publishing Company ANALYSIS OF META-PROGRAMS: AN EXAMPLE5 STAN JARZABEK∗,‡, HONGYU ZHANG†,§, SHEN RU∗, VU TUNG LAM∗ and SUN ZHENXIN∗7 ∗School of Computing, National University of Singapore, Lower Kent Ridge Road, Singapore 1175439 †School of Computer Science and Information Technology, RMIT University, Melbourne 3001, Australia11 ‡firstname.lastname@example.org §email@example.com Meta-programs are generic, incomplete, adaptable programs that are instantiated at con- struction time to meet speciﬁc requirements. Templates and generative techniques are15 examples of meta-programming techniques. Understanding of meta-programs is more dif- ﬁcult than understanding of concrete, executable programs. Static and dynamic analysis17 methods have been applied to ease understanding of programs — can similar methods be used for meta-programs? In our projects, we build meta-programs with a meta-19 programming technique called XVCL. Meta-programs in XVCL are organized into a hierarchy of meta-components from which the XVCL processor generates concrete, exe-21 cutable programs that meet speciﬁc requirements. We developed an automated system that analyzes XVCL meta-programs, and presents developers with information that23 helps them work with meta-programs more eﬀectively. Our system conducts both static and dynamic analysis of a meta-program. An integral part of our solution is a query25 language, FQL in which we formulate questions about meta-program properties. An FQL query processor automatically answers a class of queries. The analysis method de-27 scribed in the paper is speciﬁc to XVCL. However, the principle of our approach can be applied to other meta-programming systems. We believe readers interested in meta-29 programming in general will ﬁnd some of the lessons from our experiment interesting and useful.31 Keywords: Meta-programs; program understanding; program analysis; program queries; debugging.33 1. Introduction Meta-programs are generic, incomplete, adaptable programs. Custom programs,35 derived from a meta-program, may diﬀer in requirements, design decisions, plat- forms, etc. Programs instrumented with macros [1,2], transformational systems and37 generative techniques  are examples of meta-programming techniques.a aStatic meta-programming systems transform a program before compilation and load time . Other forms of meta-programming modify programs during execution (e.g., using reﬂection). In this paper, we are concerned with static meta-programming only. 1 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 2 S. Jarzabek et al. In our projects, we build meta-programs with XVCL (XML-based Variant Con-1 ﬁguration Language) [4,5]. XVCL is a public domain meta-language, method and tool for enhanced maintainability and reusability. In addition to unrestrictive pa-3 rameterization and a range of mechanisms to handle changes, XVCL supports meta- level partitioning of programs into generic, adaptable meta-components called x-5 frames. x-frames are inter-related and organized into a hierarchical structure called an x-framework. An x-framework is a meta-program from which the XVCL Pro-7 cessor generates concrete, executable programs that meet speciﬁc requirements. In that sense, an XVCL meta-program may be considered an implementation of the9 product line architecture concept . Meta-programming systems have the potential to enhance conventional pro-11 gramming techniques, helping programmers to write more generic, adaptable, and changeable programs. The reader can ﬁnd a discussion of meta-programming sys-13 tems (e.g., meta-programming with C++ templates) with many examples of their application in software engineering in . Application of XVCL to meet software15 engineering goals is described in [7,8,9] and further sources can be found at our web site .17 Flexible manipulation of programs and genericity, central in software reuse, are the strength of meta-programming. However, meta-programming techniques19 come at a price: High maintenance cost is a living proof that understanding of concrete programs is already complex enough. A meta-program — being a generic21 representation of a class of programs — is bound to be more diﬃcult to describe and understand than a concrete program. We believe that methods and tools for23 understanding and debugging of meta-programs are essential for wider acceptance of meta-programming as an eﬀective approach to software development. We believe25 that lack of such methods and tools is one of the factors that does not allow us to fully exploit the potentials of meta-programming techniques in software engineering27 context. Static and dynamic analysis methods have been applied to ease understand-29 ing and maintenance of programs: Could similar methods aid in understanding of meta-programs? Given the lack of fundamentals unifying a wide variety of meta-31 programming techniques, and relative immaturity of meta-programming concepts, it is diﬃcult to address this question in general.33 In our earlier work, we developed a Program Query Language (PQL)  for static analysis of conventional programs (e.g., written in COBOL or Java). The aim35 of PQL system was to acquire information about properties of programs that could be automatically computed in the course of static program analysis. This informa-37 tion was then presented to a programmer, in order to help him/her understand high-level properties of programs, related to various maintenance tasks. In PQL, a39 programmer expressed queries in terms of conceptual models of program design in- formation. The information required to answer program queries was computed by a41 front-end and stored in a Program Knowledge Base (PKB). A PQL query evaluator 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 3 could automatically answer queries consulting the PKB for relevant information.1 In this paper, we applied PQL concepts to aid in understanding of x-frameworks, i.e., meta-programs written in XVCL. We developed an automated system that3 analyzes an x-framework, and presents developers with information that helps them work with an x-framework in a more eﬀective way. Our system conducts both static5 and dynamic analysis of an x-framework. An integral part of our solution is an x- framework query language, called FQL, in which we can formulate questions about7 x-framework properties. An FQL query processor automatically answers queries. We believe information that can be acquired in a question-answer session can help9 developers understand higher-level x-framework properties. FQL queries are meant to bridge the gap between detailed information that can be directly observed at the11 x-framework level, and higher-level properties of an x-framework that are directly related to various tasks developers need to accomplish when enhancing or reusing13 an x-framework. The design of FQL follows the approach of PQL : We start by building15 models describing conceptual entities of XVCL (such as an x-frame, a meta-variable or an XVCL command) and the relationships among those entities that matter to17 developers working with x-frameworks. FQL is a PQL-like language that allows us to formulate questions about x-frameworks in terms of those models.19 An important ﬁnding from our study is that static program analysis techniques alone have limited value for understanding of meta-programs. Interesting and useful21 queries require partial processing (that is instantiation) of a meta-program. There- fore, we incorporated elements of dynamic analysis into our x-framework analysis23 system. The details of the analysis method described in the paper are speciﬁc to XVCL.25 However, the principle of our approach can be applied to other meta-programming systems. We believe readers interested in meta-programming in general will ﬁnd27 some of the lessons from our experiment interesting and useful. 2. Background and Related Work29 Genericity and changeability are two important program qualities that underlie ef- fective reuse and maintenance. Developers address these qualities with a range of31 programming language features and design techniques such as inheritance, gener- ics , information hiding , design patterns , architectural approaches 33 or mechanisms supported by component platforms (such as J2EETM or .NETTM). However, often it becomes diﬃcult to achieve genericity and changeability with con-35 ventional methods, without compromising other design goals that developers must meet [7,8]. Meta-level mechanisms oﬀer parameterization (and sometimes genera-37 tion) capabilities that are not constrained by an underlying programming language or component platform. When generic design becomes diﬃcult with conventional39 methods, meta-level techniques may oﬀer a workable solution [8,14]. Macros (e.g., C preprocessor CPP  or m4 ) are the oldest form of meta-41 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 4 S. Jarzabek et al. programming. Most of the macro systems are merely implementation level mecha-1 nisms for managing changes (or variability in the context of reuse ). Failing to address change at analysis and design levels , macros never evolved towards3 full-ﬂedged “design for change” methods . Programs instrumented with macros tend to be diﬃcult to understand and test . Among the most important deﬁ-5 ciencies of macros, is weak parameterization and lack of a meta-level decomposition mechanism. Lack of proper rules for parameter propagation (and overriding) across7 program units does not allow programmers to formally link and control chains of inter-related program transformations. Despite these problems and new powerful9 features of modern programming languages, macros are still often used by program- mers . It was generally believed that functions, and later classes and components,11 were more promising than macros for reuse. In fact, it has never been an either-or situation, as meta-level processing (of which macros are a simple example) addresses13 diﬀerent engineering goals than functions/classes/components: The prime goal of functions/classes/components is to deﬁne executable units of a program runtime15 architecture. Frame technology  is an example of a fully developed and highly success-17 ful meta-programming system which originated from the concepts of macros, but then evolved into a comprehensive mechanism for managing changes over years of19 software evolution and to facilitate systematic reuse. Frame technology has been extensively applied in industry to manage variants and evolve multi-million-line,21 COBOL-based, information systems. While designing a frame architecture is not trivial, subsequent complexity reductions and productivity gains are substantial.23 These gains are due to the ﬂexibility of the resulting architectures and their evolv- ability over time.25 A potential role of generative techniques (meta-programming, in particular) in solving software engineering goals have been described in . The authors also27 indicated problems with understanding and debugging meta-programs as an im- portant factor that limits engineering beneﬁts and hinders wide adoption of such29 techniques. Static and dynamic analysis methods have been applied to ease un- derstanding of programs  but application of such methods to meta-programs31 has not been explored yet. Among existing approaches, only m4  oﬀers some meta-level debugging features.33 3. An Overview of XVCL 3.1. What is XVCL?35 XVCL [18,5] that works with any other software technology and adds value to it in terms of enhanced genericity and changeability. First, we develop a program37 with one of the programming languages and with conventional design techniques, to achieve proper program modularization and required runtime properties such as39 performance or reliability. Then, we apply XVCL on top of a program to facilitate change and/or to inject extra levels of genericity into it.41 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 5 Composition & Adaptation XVCL Processor SPC A custom system Specification of a custom system Component 1 Component 2 Component n x-frame x-frame x-frame x-frame x-frame x-frame ... An x-framework: generic, adaptable, reusable meta- component architecture Fig. 1. XVCL at work. XVCL partitions a program into meta-components. XVCL meta-components are1 called x-frames. Meta-level partitioning is independent of (therefore, does not con- ﬂict with) decomposition into program modules (e.g., classes, functions, higher-level3 components and sub-systems). x-frames form a hierarchically structured architec- ture, called an x-framework, and are instrumented with XVCL commands (Fig. 1).5 Decomposition along x-frame boundaries, hierarchical organization of x-frames and unrestrictive parameterization of x-frames with XVCL commands are the main7 XVCL mechanisms to facilitate changeability and genericity. An x-framework is carefully designed into layers to enhance reuse. It is also “normalized” to unify re-9 curring patterns of program similarities which reduces conceptual complexity of a program as perceived by a programmer.11 XVCL uses “composition with adaptation” rules to generate a speciﬁc program from an x-framework. Rules of XVCL are simple but suﬃcient to manage a wide13 range of program variants at analysis, design and code levels, from a compact base of meta-components.15 XVCL is based on frame concepts. Being a modern and versatile version of Bassett’s frames , the underlying principles of the XVCL have been thoroughly17 tested in practice. Unlike original frames, XVCL blends with contemporary pro- gramming paradigms and complements other design techniques.19 3.2. How does XVCL work? XVCL works on the principle of constructing custom systems by composing generic,21 reusable x-frames, after possible adaptations. Any location or structure in an x-frame can be a designated variation point, available for adaptation by ancestor23 x-frames. This “composition with adaptation” process turns x-frames into concrete components of the custom system we wish to build. Program generation rules are25 100% transparent to a programmer, who can ﬁne-tune and re-generate code with- out losing prior customizations. x-frames can evolve as needed without ever forcing27 retroﬁts. Usually, from a small number of x-frames we can generate many concrete 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 6 S. Jarzabek et al. x-frame C adapts D and F. Fig. 2. An example of an x-framework and SPC. components that diﬀer in various characteristics such as functional requirements or1 design decisions. An x-frame is an XML  ﬁle with components’ code or architectural elements3 (such as groups of components or interfaces), instrumented with XVCL commands for ease of change and evolution. XVCL commands, designed as XML tags, allow5 the composition of the x-frames, selection of pre-deﬁned options based on certain conditions, etc. Meta-variables and expressions provide a parameterization mech-7 anism. Values of meta-variables are propagated across x-frames and meta-variable scoping rules enhance genericity and reuse.9 Customization of an x-framework is supported by the XVCL Processor. The XVCL Processor traverses an x-framework, interprets XVCL commands embedded11 in visited x-frames, and emits a custom program into one or more ﬁles. In our exam- ple, the output is emitted to a single ﬁle. The Processor’s traversal order is dictated13 by <adapt> commands embedded in x-frames. The <adapt> command tells the Processor to customize and include the speciﬁed x-frame. This customization pro-15 cess of the x-framework is directed by instructions contained in the speciﬁcation x-frame, called SPC for short.17 We shall now illustrate the customization process. In the example of Fig. 2, x-frame A is SPC and x-frames B, C, D and E form the x-framework:19 • x-frame A adapts x-frames B and C, • x-frame B adapts D and E,21 • x-frame C adapts D and F. The faded text starting with capital letters (e.g., AAA, BBB, etc.) in boxes of23 Fig. 2 represents any program code contained in the respective x-frame. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 7 Fig. 3. An example of x-framework processing. Figure 3 shows the traversal path of the XVCL Processor for the example shown1 in Fig. 2. The Processor starts with the top-most x-frame, in our case it is an x- frame A. The Processor reads the contents of x-frame A from the top to the bottom,3 emitting any program code and interpreting any XVCL commands encountered on the way. Having emitted “AAA before”, the Processor encounters command <adapt5 x-frame = “B”>, suspends processing of x-frame A, and starts reading x-frame B. Having emitted “BBB before”, the Processor encounters command <adapt x-frame7 = “D”>, suspends processing of x-frame B, and starts reading x-frame D. Once the processing of a given x-frame is completed, the Processor returns to interpret the9 parent x-frame, from the point where the processing was suspended. The complete result of processing the x-framework of Fig. 2 is shown on the11 right-hand side of Fig. 3. What we did not show in the above example, is that <adapt> command may also specify customization commands. In such a case, the13 speciﬁed x-frame is customized before it is processed. We shall discuss this in more detail below.15 3.3. Essential XVCL commands We shall now describe a subset of XVCL that is suﬃcient for the purpose of this17 paper. We refer the reader to XVCL web site  for complete description of XVCL. <x-frame> command:19 <x-frame name = “name”> x-frame body: mixture of code and XVCL commands21 </x-frame> 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 8 S. Jarzabek et al. An x-frame body contains the program code instrumented for ease of changing1 with XVCL commands. Attribute name deﬁnes the name of x-frame. <adapt> command:3 <adapt x-frame =“name”> adapt-body: mixture of <insert>, <insert-before>, <insert-after>5 commands </adapt>7 (or) <adapt x-frame =“name”/>9 The <adapt> command instructs the processor to: • adapt the x-frame deﬁned in “x-frame” attribute and apply the commands listed11 in the adapt-body, • include the adapted x-frame into the current x-frame,13 • resume processing of the current x-frame. The x-frame name may be a character string specifying the name of a concrete15 x-frame (e.g., “A”) or a reference to a meta-variable whose value speciﬁes x-frame name. Meta-variable reference has a form “@V” (explained later in more details).17 The adapt-body may contain a mixture of <insert>, <insert-before> and <insert-after> command. Customization commands may aﬀect any x-frame19 reached in a sequence of <adapt> commands from a given one. For exam- ple, in x-framework of Fig. 1, customization commands speciﬁed in an <adapt21 x-frame=“editor”> may refer not only to x-frame editor, but also to x-frames menu and toolbar.23 <break> command: <break name = “break-name”>25 break-body </break>27 The <break> command marks a point at which an x-frame can be adapted by29 ancestor x-frames. The break-body deﬁnes the default code that may be replaced or extended by <insert>, <insert-before> and <insert-after> commands matching31 a given <break>. This matching is done by the break-name which is deﬁned as either character string or meta-variable reference.33 <insert> command: <insert break =“break-name”>35 insert-body </insert>37 The <insert> command replaces the break-body of matching <break> com-39 mands with insert-body. The matching <break> commands are found below 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 9 <insert> in the same x-frame and in all its descendents. The <insert-before>1 command inserts the insert-body before the matching <break> commands. The <insert-after> command inserts the insert-body after the matching <break>3 commands. The insert-body may contain a mixture of code and XVCL commands.5 <set> command: <set var = “var-name” value =“value”/>7 The <set> command is used to deﬁne a single-value meta-variable. The <set>9 command assigns a value deﬁned in value attribute to single-value meta-variable var-name deﬁned in var attribute. Value is either a string or a reference to a11 meta-variable. 13 <set-multi> command: <set-multi var =“var-name” value =“value1, value2, ...”/>15 The <set-multi> command is used to deﬁne a multi-value meta-variable. The17 <set-multi> command assigns multiple values (value1,value2,...) deﬁne in “value” attribute to a multi-value meta-variable name var-name deﬁne in var attribute.19 <value-of > command 21 <value-of expr =“variable-ref”/> 23 The value of the “variable-ref ” is evaluated and the result is inserted in place of the <value-of> command. Meta-variable reference can be direct or indirect25 such as: “@v” — value of meta-variable v (direct reference)27 “@@v” — value-of(value-of (v)) (indirect reference) “@...@v” — multi-level indirect reference29 Meta-variable scoping rules:31 Meta-variable scoping rules are the same for both single-value and multi-value33 meta-variables. While many x-frames may include <set> commands for the same meta-variable, only <set> commands from one x-frame take eﬀect during each run35 of XVCL processor through x-frames. The <set> command(s) in the ancestor x- frame takes precedence over <set> commands in its descendent x-frames. That is,37 once x-frame X sets the value of meta-variable v, <set> commands that deﬁne the same meta-variable v in descendent x-frames (if any) visited by the processor will39 not take eﬀect. However, the subsequent <set> commands in x-frame X can reset the value of meta-variable v. Meta-variable v becomes undeﬁned as soon as the41 processor returns the processing to the parent x-frame that adapts x-frame X. Meta-variables become undeﬁned as soon as the processing level rises above the43 x-frame that eﬀectively set meta-variable values. This makes it possible for other 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 10 S. Jarzabek et al. x-frames to set and use the same meta-variablesand prevents the interference among1 meta-variables used in two diﬀerent sub-trees in the x-frame hierarchy. The above scoping rule has important implication on reuse. Lower level x-3 frames must be generic so that they can be reused in many systems. Such x- frames deﬁne default values of meta-variables in their respective <set> commands.5 However, ancestor x-frames often need to adapt lower level x-frames for reuse in diﬀerent contexts. Some of the adaptations are done by setting values of meta-7 variables. Therefore, ancestor x-frames must have a power to override defaults de- ﬁned in lower level x-frames. Meta-variable scoping rules in XVCL reﬂect the above9 thinking. Deﬁnition of <select> command11 <select option =“var-name”> select-body: may contain options listed below13 </select> select-body:15 <option-undeﬁned> (optional) option-body17 </option-undeﬁned> <option value = “value”> (0 or more)19 option-body </option>21 <otherwise> (optional) option-body23 </otherwise> 25 The <select> command selects from a set of options based on meta-variable “var-name” as follows: 27 <option-undeﬁned> is processed, if the meta-variable “var-name” is29 undeﬁned, <option> is processed, if value of “var-name” matches <option>’s “value”,31 <otherwise> is processed, if none of the <option>’s “value” is matched. The option-body may contain a mixture of textual content and XVCL commands. 33 Deﬁnition of <while> command: <while using-items-in=“multi-var”>35 while-body </while>37 The <while> command iterates over while-body using the values of multi-var39 deﬁned in using-items-in attribute. The ith iteration uses ith value of the multi- valued meta-variable “multi-var”. Inside the while-body, multi-var with the ith41 value can be used as single-value meta-variable. The while-body may contain a mixture of code and XVCL commands.43 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 11 Description of how we use XVCL to design generic systems would occupy a1 large part of this paper and would repeat what we have already described in other papers. We refer the reader to the examples of a generic editor  and generic3 design of a buﬀer class library . Any of those two studies explains the concepts with enough details to get an understanding of how XVCL meta-level constructs5 work in practice. The reader can also ﬁnd full documentation (including code) for the two studies at our web site ).7 4. Understanding an x-Framework Using XVCL mechanisms described in the last section, we create meta-level struc-9 tures on top of conventional programs. Here, we are concerned with understanding the properties of meta-level structures rather than properties of actual programs.11 An x-framework is analyzed for understanding when it is developed, evolved and reused. In any of those situations, we must understand the internal structure13 of selected x-frames, as well relationships among x-frames. Here are some examples of scenarios in which we need to understand an x-framework and the information15 that can be useful to accomplish those scenarios: Scenario 1: Adding a new x-frame X into an x-framework during x-framework de-17 velopment or evolution. Information relevant to Scenario 1: 19 1. Which x-frames can potentially adapt (reuse) x-frame X, directly or indirectly?21 2. Which x-frames can be adapted from x-frame X, directly or indirectly? 3. In what ways is an x-frame X related to other x-frames? For example:23 (a) Which meta-variables set in other x-frames are referred to in x-frame X? (b) Which meta-variables set in x-frame X are referred to in other x-frames?25 4. How general x-frame X should be? Which XVCL commands and meta-variables allow us to realize diﬀerent types of variability in x-frame X?27 Scenario 2: Modifying an x-frame X. Information relevant to Scenario 2: 29 5. What is the impact of modifying x-frame X on x-frames adapted from it?31 6. What is the impact of modifying x-frame X on x-frames that adapt it? 7. Suppose we modify <set> command that assigns value to a meta-variable x —33 which references to x can be aﬀected? 8. Suppose we modify <select> command — which commands assign value to a35 meta-variable that controls a given <select>? Scenario 3: Reusing an x-frame X37 Information relevant to Scenario 3: 39 9. What are the possible ways to customize x-frame X for reuse? 10. What are the roles of meta-variables that are set or referred to in x-frame X?41 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 12 S. Jarzabek et al. 11. Which variabilities are addressed in x-frame X and which XVCL commands1 realize these variabilities? Scenario 4: Analyzing reuse statistics3 Information relevant to Scenario 4: 5 12. The number of x-frames that can be adapted in an x-framework. 13. The number of x-frames that can be adapted for a given SPC (that is, for a7 speciﬁc run of the XVCL Processor over the x-framework). 14. How many times has a given x-frame been adapted for a given set of SPCs?9 We discussed only a small sample of high-level properties of x-frameworks that must be understood in various x-framework usage scenarios. Some of those11 properties can be directly inferred from an x-framework. But to check other properties — information available from an x-framework must be complemented13 by the information from external sources such as documentation or expert knowledge.15 In the following sections, we describe an x-framework analysis system that collects information in the course of both static and dynamic analysis of an17 x-framework. By querying this information, developers can easier check x-framework properties such as we discussed above.19 5. An Approach to Automating x-Framework Analysis The rationale for our approach is that much of the information related to high-level21 x-framework properties can be derived from the x-framework. This information can be further transformed and ﬁltered to provide a useful help for developers in23 understanding an x-framework. We applied concepts from the earlier project on static program analysis  and arrived at our automated x-framework analysis25 system as follows: 1. We created a conceptual meta-level information model that can be directly com-27 puted by automatic static and dynamic analysis of an x-framework. 2. We formulated queries related to x-framework properties. These queries could29 be automatically answered based on the meta-level information model. 3. We designed an x-frame query language, FQL for short, to specify information (in31 the form of queries) that could help us infer high-level x-framework properties, such as those discussed in the last section.33 4. We deﬁned an x-Framework Knowledge Base (FKB), a repository to store the x-framework information according to a schema deﬁned by the conceptual meta-35 level information model. 5. We designed a front-end to conduct static and dynamic analysis of the x-37 framework and to load the information into the FKB. 6. We implemented an interpreter to evaluate queries written in FQL, and display39 the results. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 13 Here, we give examples of queries that FQL is meant to express and our automated1 analysis system is meant to answer: 3 1. Select all the <adapt> commands from all x-frames. 2. Select meta-variables that are modiﬁed in x-frame X.5 3. Select x-frames that modify value of meta-variable V. 4. Select x-frames that adapt x-frame X.7 5. Select XVCL select structures that adapt x-frame X. 6. Select x-frames adapted directly or indirectly from XVCL command at line 109 in x-frame X. 7. Select x-frames containing break point named BP.11 8. Select x-frames that adapt x-frame X with modiﬁcation at break point BP. 9. Select x-frames that set meta-variable v before adapting x-frame X.13 10. Select x-frames that use meta-variable v in some <adapt> command. 11. Select x-frames that are adapted directly or indirectly from x-frame X and15 modify meta-variable V, and make selection (in XVCL <select> command) based on meta-variable v.17 Clearly, the answers to the above queries can only partially contribute to check- ing high-level properties discussed in the last section. However, answering even19 simple queries for large x-frameworks is diﬃcult and error-prone, as one has to in- spect multiple x-frames and emulate XVCL processing to ﬁnd the result. Therefore,21 we designed an automated system to support query answering. 6. A Conceptual Meta-Level Information Model for x-Frameworks23 We use class diagrams to describe our models. Figure 4 depicts major XVCL com- mands and their important attributes.25 and their important attributes. x-frame +x-frameName break +breakName adapt +x-frameName insert +breakName +type: rep, after, before command +line# set +varName while +multi-var-list select +varName option +type : undef, def, etc. line numbers (line#) are for the purpose of reference in queries set-single +single-value set-multi +value-list value-of +variable ref Fig. 4. XVCL command model. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 14 S. Jarzabek et al. The following relationships among XVCL commands are of interest for querying1 purpose: Relationship Follows (Fig. 5) depicts the sequential order of commands in3 an x-frame. Relationship Follows* is a transitive closure of Follows. Relationship Contains models direct nesting among commands. Relationship Contains* models5 direct or indirect nesting among commands. indirect nesting among commands. command +line# Follows Follows* command +line# command +line# Contains Contains* Fig. 5. XVCL command structure model. Relationship Adapts (x, y) (Fig. 6) holds if x-frame x adapts x-frame y in7 a processing context under consideration. Notice that x-frame x may contain a command <adapt x-frame ="y"> but still this command may not be executed.9 Relationship Adapts* is a transitive closure of Adapt. Relationships Next and Next* model processing control ﬂow processing among any XVCL commands: Next (c, d)11 holds if commands c and d are in the same x-frame and command d is executed after command c. Relationship Next* (c, d) holds if command d is executed after13 command c, independently of whether commands c and d are in the same or in diﬀerent x-frames. x-frame +x-frameName x-frame +x-frameName Adapts Adapts * command +line# command +line# Next Next * Fig. 6. Command processing order model. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 15 command +line# variable +varName command +line# variable +varName Modifies Modifies * Uses Uses * Fig. 7. XVCL meta-variable usage model. Relationship Modiﬁes (x, v) (Fig. 7) holds if command x directly sets the value1 of meta-variable v. Relationship Modiﬁes* (x, v) holds if Modiﬁes (x, v) or there exist y such that Adapts* (x, y) and Modiﬁes (y, v). Relationships Uses and Uses*3 are deﬁned in a similar way. Relationships Aﬀects and Aﬀects* (Fig. 8) model data ﬂow among meta-variable5 deﬁnition and reference points. Relationship Aﬀects (s, ref) holds if value of meta- variable v assigned in <set> command s can be actually used in reference to this7 meta-variable ref. Relationship Aﬀects* (s, ref) holds if there is a chain of meta- variable deﬁnitions and references, starting at <set> command s and ending at9 meta-variable reference ref, such that s aﬀects (directly or indirectly) ref. set +varName var-ref Affects Affects* Fig. 8. Data ﬂow model. 7. Querying x-Frameworks in FQL11 FQL queries are expressed in terms of x-frame information model described in the previous section. In queries, the reader will see references to model entities (such13 as command, x-frame, adapt, etc.), attributes (such as x-frame.x-frameName or variable.varName) and entity relationships (such as Adapts (x-frame, x-frame)).15 Evaluation of a query yields a list of speciﬁc instances of model entities that match the query, for example, x-frame named “X”, XVCL command found at line number17 35 or meta-variable named “V”. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 16 S. Jarzabek et al. In a query, after keyword Select, we list model entities we are interested to1 ﬁnd or keyword BOOLEAN, in case the result is true or false. We further constrain the results by writing (optional) conditions that the results should satisfy. These3 conditions include from, with, and such that clauses. In FQL, all the keywords are in bold font.5 We ﬁrst explain queries in the simplest form, with Select not constrained by any conditions:7 Select x-frame Meaning: this query returns as a result all the x-frames in the x-framework.9 Select x-frame.x-frameName Meaning: returns as a result names of all x-frames in the x-framework11 Select <adapt, select> Meaning: query result may be a tuple. Here the result will contain all possible13 combinations of all the <adapt> and <select> commands. 15 The above query examples did not include any conditions. However, in most situations, we wish to select only speciﬁc elements, for example, <set> commands17 that modify a certain meta-variable. We specify properties of elements to be se- lected in conditions that follow Select. Conditions are expressed in terms of:19 (a) entity attribute values and constants (with clause), (b) participation of entities in relationships (such that clause).21 In addition, if we wish to restrict the scope of searching to speciﬁc x-frames, we23 can do so by listing names of those x-frames in the from clause. All clauses are optional Clauses such that and with may occur many times in the same query.25 There is an implicit and operator between clauses — that means a query result must satisfy the conditions speciﬁed in all the clauses.27 Declarations introduce synonyms that refer to model entities. Synonyms can be used in the remaining part of the query to mean a corresponding entity. So we can29 write: x-frame x;31 Select x such that Modiﬁes (x, “V”) — here we introduce synonym x for x-frame and constraint the result with condition. 33 A typical query has the following format: Select ... from ... such that ...35 with ... 37 Below, we show query examples: Q1. Select all the adapt commands from all x-frames39 Select adapt Q2. Select all the <adapt> commands from x-frame “CAD”41 x-frame x; adapt a; Select adapt from x with x.x-frameName=“CAD”43 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 17 or simply: Select a from “CAD” 1 Q3. Select all the <insert> commands directly nested within <adapt> commands Select insert such that Contains (adapt, insert) 3 Q4. Select meta-variables whose values are modiﬁed in x-frame X and used in x- frame Y variable v; x-frame x, y;5 Select v such that Modiﬁes (x, v) and Uses (y, v) with x.x-frameName = “X” and y.x-frameName = “Y” 7 Q5. Select x-frames that modify value of meta-variable “COLOR” Select x-frame such that Modiﬁes (x-frame, “COLOR”) 9 Q6. Select x-frames that adapt x-frame X directly or indirectly Select x-frame such that Adapts* (x-frame, “X”) 11 Q7. Select all references to meta-variable v aﬀected by <set> command at line number 20 in x-frame “CAD”13 var-ref ref; Select ref from “CAD” such that Aﬀects (“CAD”.20, ref)15 8. An x-Framework Analysis System As XVCL is based on XML , XML query languages such as XQL , XPath 17 or XQuery  can be used to answer certain queries. We started prototyping FQL query evaluator using an XML query language XQL  and a public domain XML19 parser, JAXP from Sun Inc. . We used JAXP parser for parsing XVCL ﬁles and extracting information about x-framework. The extracted information included the21 x-frame structure, adaptation hierarchy of x-frames, breakpoint settings, etc. We stored the extracted information in the XML format. We translated queries written23 in FQL into equivalent queries written in XQL and then used the XQL query en- gine to evaluate queries. In this prototype solution, we could address only queries25 that could be answered by simple search for XML tags representing XVCL com- mands. However, answering any non-trivial FQL query involves more than that.27 Some queries need information about relationships among diﬀerent types of XVCL commands (e.g., as modeled by relationships Follows and Contains). But most im-29 portantly, many useful queries cannot be answered based on information computed in the course of static analysis of an x-framework, but require processing of an31 x-framework. Consider the following simple query: 33 Select x-frame such that Adapts (x-frame, “X”) 35 To answer this query, it is not enough to search for x-frames containing command37 <adapt x-frame = “X”/>. We must also consider commands <adapt x-frame = “@V”/> and check possible values of meta-variable V. For this, we have to interpret39 the x-framework. Meta-variables are heavily used to parameterize x-frameworks: x-frame names in <adapt> or break names in <insert> are most often expressed41 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 18 S. Jarzabek et al. in terms of meta-variable references. Also, <value-of> is commonly used to repre-1 sent class and method names in generic way. Such parameterization is an important technique to achieve reuse. Since XML query languages could not address the above3 situations, we decided to implement our own x-framework analyzer that conducted both static and dynamic analysis of an x-framework. Our aim was to answer accu-5 rately any query written in FQL in terms of models described in Sec. 6. In our previous project, we designed a Program Query Language, PQL for short,7 for analysis of static properties of programs written in conventional programming languages . We implemented a generic PQL query evaluator to facilitate reuse9 of evaluator’s components across various source languages. We achieved language- independence by parameterizing the query evaluator with conceptual models of11 program information such as that described in Sec. 6. To implement a query eval- uator for a new source language, we must implement a parser that analyzes source13 programs, computes program information according to the models, and stores it in a meaningful form in the Program Knowledge Bases (PKB). The PQL query eval-15 uator is driven by tables that store the conceptual model schema, so that changes of the conceptual model do not aﬀect most of the evaluator’s components.17 The above model-based design of PQL allowed us to easily adapt the generic PQL query evaluator to work with FQL, a query language for x-frameworks.19 Figure 9 shows the main components of our x-framework analysis system: An x-Framework Knowledge Base (FKB) stores all the information used for query21 evaluation, computed by both Static Analyzer (SA) and Dynamic Analyzer (DA). The SA parses an x-framework and stores the information explicitly represented23 FKB SA Static Analyzer DA Dynamic Analyzer XVCL Processor x-framework SPC QE Query Evaluator query query result Fig. 9. An overview of the x-framework analysis system. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 19 by XVCL commands embedded in x-frames. The DA processes the x-framework1 — that is why it must be fed with an SPC, in addition to the x-framework. SPC deﬁnes values for meta-variables and other settings that enable processing of the x-3 framework. It was natural to build DA on top of the XVCL Processor. Our XVCL Processor is implemented in JavaTM using a public domain XML parser, JAXP5 from Sun. To build the DA, we instrumented the XVCL Processor with extra code to7 collect x-frameworkinformation, accordingto conceptual models described in Sec. 6. We attached events to XVCL commands and implemented listener interfaces to9 handle such events. At the time of processing, all the relevant meta-variables already have speciﬁc values assigned to them, therefore the queries that require dynamic11 processing of an x-framework can be answered. Once SA and DA have completed an x-framework analysis, all the information13 required to answer queries has already been stored in the FKB. A programmer can now enter a query. The Query Evaluator (QE) ﬁrst validates the query, checking if15 all the references to XVCL commands, their attributes and relationships conform to the conceptual meta-level information model. Then, the QE evaluates the query,17 fetching the information from the FKB via APIs. Eﬃcient query evaluation is an important concern in the design of the FKB.19 We experimented with the following four implementation options for the FKB: 1. Data structures such as tables, graphs and trees, stored in memory and/or ﬁles.21 The analyzers SA and DA used API to feed information about an x-framework during analysis, and to access it for query evaluation. These APIs provided23 abstraction over the physical representation of data structures which allowed us to easily change the representations for better performance or to simplify query25 evaluation. 2. Mainstream database servers MySQLTM 4.1 and MS SQLTM Server 2000 SP3.27 We deﬁned FKB schema in an improved 3NF form to reduce redundancy. The in- formation collected during analysis of an x-framework was inserted into database29 with optimized SQL statements. Our Query Evaluator translated FQL queries into SQL for evaluation by the database query engine.31 3. A ﬁle-based relational database Microsoft Access 2003TM, with FKB schema and SQL used in the same way as above.33 4. In-memory relational database HSQLDB , an open source in-memory rela- tional database written in Java. HSQLDB runs totally inside memory, eliminat-35 ing the need for frequent, time-consuming disk access operations. We conducted experiments with the above media on the same hardware plat-37 form and with various data sets (that is, x-frameworks and queries). HSQLDB performance was the best in most cases, except for trivial-size data sets. HSQLDB39 provides a lightweight Java SQL Engine that accommodates entire data in mem- ory, to minimize disc access during query evaluation. However, the HSQLDB has41 upper bound for database size (400 Mb for version 1.7.3). As FKB size is typically 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 20 S. Jarzabek et al. x-framework size Number of XVCL commands Time to build FKB (in seconds) Small 238 1.434 Medium 1,108 2.656 Large 3,720 13.359 Fig. 10. Time to build FKB for three x-frameworks. 0 0.5 1 1.5 2 2.5 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Seconds Small Medium Large Fig. 11. Query evaluation time for three x-frameworks. between few KB and 20 MB, this limitation was acceptable to us and we selected1 HSQLDB as a medium for the FKB in our project. We evaluated the performance of our Query Evaluator for HSQLDB implemen-3 tation of FKB on a Pentium IV 2.6 GHz, 1 GB RAM, Windows XP SP2 platform. We measured time to conduct static and dynamic analysis of x-frameworks, and to5 build FKBs. In Fig. 10, we show the elapsed time to build FKB for small, medium and large x-frameworks. As the analysis time depends mostly on the number of7 XVCL commands to be processed, we characterized the size of an x-framework in terms of the number of XVCL commands contained in the x-frames rather than9 in terms of lines of code. Figure 11 shows the elapsed time to evaluate the eight queries (given in Appendix B) for FKBs built for each of the three x-frameworks.11 Both FKB build time and query processing time radically increase as the size of an x-frameworkgrows. Query processing time has also to do with the complexity of a13 query and special characteristicsof an x-framework(such as the number of <adapt> commands with many <insert> commands). We found the performance acceptable15 and in this implementation we did not perform any specialized optimizations during FQL-to-SQL translation, relying on the SQL engine to optimize queries.17 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 21 9. Conclusions1 Meta-programs are generic, incomplete, adaptable programs. Flexible manipulation of programs and genericity, central in software reuse, are the strength of meta-3 programming. But a meta-program — being a generic representation of a class of programs — is bound to be more diﬃcult to describe and understand than5 a concrete program. In this paper, we addressed the problem of analysis of meta- programs for understanding, focusing on a speciﬁc meta-programming system called7 XVCL. First, we considered static program analysis methods, developed in analysis of conventional programs. Having found some limitations of such methods in the9 context of analysis of meta-programs, we also considered dynamic analysis methods. We developed an automated system that analyzes an x-framework (i.e., a meta-11 program in XVCL), and presents developers with information that helps them work with an x-framework in a more eﬀective way. Our system conducts both static13 and dynamic analysis of an x-framework. An integral part of our solution is an x- framework query language, called FQL, in which we can formulate questions about15 x-frameworkproperties. An FQL query processorautomatically answersqueries. We designed FQL based on our earlier work on PQL, a query language for conventional17 programs . In the paper, we described FQL as well as the design of our x- framework analysis system.19 We believe information that can be acquired in a question-answer session can help developers understand higher-level x-framework properties. FQL queries are21 meant to bridge the gap between detailed information that can be directly observed at the x-framework level, and higher-level properties of an x-framework that are23 directly related to various tasks developers need accomplish when enhancing or reusing an x-framework. We developed requirements for a class of queries to be25 supported by FQL based on our own work with XVCL and inputs from our partners who applied similar systems on the large, industrial scale . However, we cannot27 yet provide an extensive empirical evidence of how well our analysis tool can support challenging tasks of x-framework development, evolution and reuse. Our tool is29 still immature and can be used only in our internal projects. While our initial experiences are positive, we are also aware of many ways in which we can improve31 our system. Our immediate goal is to integrate the x-framework analysis system into a Smart33 Graphical Editor (SGE), an x-framework visualization tool developed in our lab. The intention is to display query results using SGE’s advanced presentation fea-35 tures, and also to allow developers to seamlessly ask questions about an x-framework while browsing it in SGE windows. Further, we plan to integrate FQL into the37 XVCL debugger. All these tools will be components of an XVCL Workbench, an IDE for XVCL meta-programming, being developed in our lab. We also plan to39 incorporate specialized optimizations during FQL-to-SQL translation to reduce the time to evaluate complex queries for large x-frameworks. As a long-term plan, we41 would like to discover higher-level conceptual models of x-frameworks that would 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 22 S. Jarzabek et al. allow us to better link automatically computed information to typical scenarios for1 x-framework development, evolution and reuse. We believe meta-programming techniques have much potential to improve soft-3 ware development practice. Problems of designing generic, adaptable, easy to main- tain and reuse programs are diﬃcult to address with conventional programming5 approaches. Some of these problems can be tackled easier at the meta-level, where we are not restricted by the rules of the implementation language. While extending7 programs in useful ways, meta-level structures remain fully integrated with the base code. Such solutions are easier to adopt in the industrial practice than powerful ab-9 stractions that are disconnected from code. We believe that methods and tools for understanding and debugging of meta-programs are essential for wider acceptance11 of meta-programming as an eﬀective approach to software development. Acknowledgments13 This work was supported by NUS Research Grant R-252-000-211-112. References15 1. CPP GNU C preprocessor manual, http://gcc.gnu.org/onlinedocs/cpp/ 2. M4 http://www.gnu.org/software/m4/manual/m4.html17 3. K. Czarnecki and U. Eisenecker, Generative Programming: Methods, Tools, and Applications, Addison-Wesley, Reading, MA, 2000.19 4. T. W. Wong, S. Jarzabek, M. S. Soe, R. Shen and H. Zhang, XML Implementation of frame processor, in Proc. Symposium on Software Reusability, SSR’01, Toronto,21 Canada, May 2001, pp. 164–172. 5. XVCL (XML-based Variant Conﬁguration Language) method and tool for managing23 software changes during evolution and reuse, http://fxvcl.sourceforge.net, 2005. 6. P. Clements and L. Northrop, Software Product Lines: Practices and Patterns,25 Addison-Wesley, 2002. 7. H. A. Basit, D. C. Rajapakse and S. Jarzabek, Beyond templates: A study of clones27 in the STL and some general implications, in Proc. Int. Conf. Software Engineering, ICSE’05, St. Louis, MI, May 2005, pp. 451–445.29 8. S. Jarzabek and L. Shubiao, Eliminating redundancies with a “composition with adap- tation” meta-programming technique, in Proc. ESEC-FSE’03, European Software En-31 gineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering, ACM Press, pp. 237–246.33 9. U. Pettersson and S. Jarzabek, Industrial experience with building a web portal prod- uct line using a lightweight, reactive approach, accepted for ESEC-FSE’05, European35 Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering, ACM Press, Lisbon, 2005.37 10. S. Jarzabek, Design of ﬂexible static program analyzers with PQL, IEEE Trans. on Software Engineering, March 1998, pp. 197–215.39 11. R. Garcia et al., A comparative study of language support for generic programming, in Proc. 18th ACM SIGPLAN Conf. on Object-oriented Programming, Systems, Lan-41 guages, and Applications, 2003, pp. 115–134. 12. D. Parnas, On the criteria to be used in decomposing software into modules, Com-43 munications of the ACM 15(12) (1972) 1053–1058. 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 23 13. E. Gamma, R. Helm, R. Johnson and J. Vlissides, Design Patterns — Elements of1 Reusable Object-Oriented Software, Addison-Wesley, 1995. 14. C. Marcos, M. Campo and A. Pirotte, Rectifying design patterns as meta-level3 constructs, Electronic Journal of SADIO 2(1) (1999) 17–29. 15. A. Karhinen, A. Ran and T. Tallgren, Conﬁguring designs for reuse, in Proc. Int.5 Conf. Software Engineering, ICSE ’97, Boston, MA, pp. 701–710. 16. P. Bassett, Framing Software Reuse — Lessons from Real World, Yourdon Press,7 Prentice Hall, 1997. 17. M. Ernst, G. Badros and D. Notkin, An empirical analysis of C preprocessor use,9 IEEE Trans. on Software Engineering, December 2002, pp. 1146–1170. 18. S. Jarzabek, P. Basset, H. Zhang and W. Zhang, XVCL: XML-based variant conﬁg-11 uration language, in Proc. Int. Conf. on Software Engineering, ICSE ’03, May 2003, Portland, pp. 810–811.13 19. XML Extensible Markup Language http://java.sun.com/xml/ 20. M. S. Soe, H. Zhang and S. Jarzabek, XVCL: A tutorial, in Proc. 14th Int. Conf.15 on Software Engineering and Knowledge Engineering, SEKE ’02, ACM Press, Italy, 2002, pp. 341–349.17 21. XQL XML Query Language http://www.w3.org/TandS/QL/QL98/pp/xql.html 22. XPath XML Path Language http://www.w3.org/TR/xpath19 23. XQuery, http://www.w3.org/TR/xquery 24. Sun Microsystems. SUN Java Technology and XML. http://java.sun.com/xml/21 25. HSQLDB http://www.hsqldb.org/ Appendix A. FQL Grammar23 Meta symbols: [a] — optional (0 or 1 occurrences of a)25 a* — repetition 0 or more times of a a+ — repetition 1 or more times of a27 Lexical rules:29 LETTER : A-Z | a-z — capital or small letter DIGIT : 0-931 IDENT : LETTER (LETTER | DIGIT | ‘-’ | ‘ ’)* INTEGER ::= DIGIT+33 STRING ::= ‘ ”’ (LETTER | DIGIT)* ‘ ”’ CONST ::= STRING | INTEGER35 Auxiliary grammar rules:37 tuple ::= elem | ‘<’ elem (‘,’ elem )* ‘>’ elem ::= synonym | attrRef39 synonym, attrName: IDENT entRef ::= synonym | ‘ ’ | STRING | lineRef41 lineRef ::= INTEGER | STRING.INTEGER | synonym.INTEGER 43 Comment on line numbers: entRef are references to XVCL entities deﬁned in models. The entRef’s appear as relationship arguments in conditions in such that45 clauses. Whenever it makes sense (according to models) and does not lead to 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 24 S. Jarzabek et al. ambiguities, line number (lineRef) can be used as arguments of relationships to1 denote a corresponding x-structure. Examples:3 “CAD”.10 means line# 10 in x-frame named CAD xf.10 means line# 10 in x-frame denoted by synonym xf5 Grammar rules:7 select-cl ::= declaration* Select result [from-cl] (with-cl | suchthat-cl | pattern-cl)* declaration ::= IDENT synonym (‘,’ synonym)* ‘;’9 result ::= tuple | ‘BOOLEAN’ from-cl ::= from x-frame-list [down]11 x-frame-list ::= x-frame-ref [‘,’ x-frame-ref] x-frame-ref ::= STRING | synonym13 synonym-list ::= synonym [‘,’ synonym] 15 Comment on from clause: from clause speciﬁes x-frames to be searched. x-frames are referenced (x-frame-ref) by name (STRING) or by synonym of type x-frame.17 The from clause can be further qualiﬁed by down. Qualiﬁer down means we should start searching at a given x-frame and then search all the x-frames down19 from there (along the adapt link) in the x-framework with-cl ::= with attrCond21 suchthat-cl ::= such that relCond attrCond ::= attrCompare (‘and’ attrCompare)*23 attrCompare ::= attrRef COMP-OPER ref COMP-OPER ::= ‘=’ | ‘<’ | ‘>’ | ‘6=’25 attrRef ::= synonym ‘.’ attrName ref ::= CONST | attrRef27 relCond ::= relRef (‘and’ relRef)* relRef ::= all the relationships in the XVCL models29 Appendix B. Queries Used for Performance Evaluation 1. Select all the adapt commands from all x-frames31 adapt a; Select a33 2. Select all the <insert> commands directly nested within <adapt> commands insert i; adapt a;35 Select i such that Contains (a,i) 3. Select variables whose values are modiﬁed in x-frame X37 variable v; x-frame x, command c; Select v such that Modiﬁes (c,v) and Contains (x,c) with x.name=‘X’39 4. Select x-frames that modify value of variable COLOR x-frame x; variable v; command c;41 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 25 Select x such that Modiﬁes (c,v) and Contains (x,c) with v.name=‘COLOR’1 5. Select x-frames that adapt x-frame X x-frame x1; x-frame x2;3 Select x1 such that Adapts (x1,x2) with x2.name=‘X’ 6. Select x-frames adapted directly or indirectly from XVCL command at line 105 in x-frame X x-frame x1; x-frame x2; command c;7 Select x1 such that Adapts* (c,x1) with c.line no=10 such that Contains (x2,c) with x2.name=‘X’9 7. Select x-frames containing a break point B break b; x-frame x;11 Select x such that Contains (x,b) 8. Select x-frames that set variable v before adapting x-frame X13 x-frame x1; variable v; x-frame x2; set s; adapt a; Select x1 such that Contains (x1,s) and Modiﬁes (s,v) and Contains (x1,a)15 and Adapts (a,x2) with x2.name=‘X’ such that Follows (a,s) 1.13 19. XML Extensible Markup Language http://java.sun.com/xml/ 20. M. S. Soe, H. Zhang and S. Jarzabek, XVCL: A tutorial, in Proc. 14th Int. Conf.15 on Software Engineering and Knowledge Engineering, SEKE ’02, ACM Press, Italy, 2002, pp. 341–349.17 21. XQL XML Query Language http://www.w3.org/TandS/QL/QL98/pp/xql.html 22. XPath XML Path Language http://www.w3.org/TR/xpath19 23. XQuery, http://www.w3.org/TR/xquery 24. Sun Microsystems. SUN Java Technology and XML. http://java.sun.com/xml/21 25. HSQLDB http://www.hsqldb.org/ Appendix A. FQL Grammar23 Meta symbols: [a] — optional (0 or 1 occurrences of a)25 a* — repetition 0 or more times of a a+ — repetition 1 or more times of a27 Lexical rules:29 LETTER : A-Z | a-z — capital or small letter DIGIT : 0-931 IDENT : LETTER (LETTER | DIGIT | ‘-’ | ‘ ’)* INTEGER ::= DIGIT+33 STRING ::= ‘ ”’ (LETTER | DIGIT)* ‘ ”’ CONST ::= STRING | INTEGER35 Auxiliary grammar rules:37 tuple ::= elem | ‘<’ elem (‘,’ elem )* ‘>’ elem ::= synonym | attrRef39 synonym, attrName: IDENT entRef ::= synonym | ‘ ’ | STRING | lineRef41 lineRef ::= INTEGER | STRING.INTEGER | synonym.INTEGER 43 Comment on line numbers: entRef are references to XVCL entities deﬁned in models. The entRef’s appear as relationship arguments in conditions in such that45 clauses. Whenever it makes sense (according to models) and does not lead to 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 24 S. Jarzabek et al. ambiguities, line number (lineRef) can be used as arguments of relationships to1 denote a corresponding x-structure. Examples:3 “CAD”.10 means line# 10 in x-frame named CAD xf.10 means line# 10 in x-frame denoted by synonym xf5 Grammar rules:7 select-cl ::= declaration* Select result [from-cl] (with-cl | suchthat-cl | pattern-cl)* declaration ::= IDENT synonym (‘,’ synonym)* ‘;’9 result ::= tuple | ‘BOOLEAN’ from-cl ::= from x-frame-list [down]11 x-frame-list ::= x-frame-ref [‘,’ x-frame-ref] x-frame-ref ::= STRING | synonym13 synonym-list ::= synonym [‘,’ synonym] 15 Comment on from clause: from clause speciﬁes x-frames to be searched. x-frames are referenced (x-frame-ref) by name (STRING) or by synonym of type x-frame.17 The from clause can be further qualiﬁed by down. Qualiﬁer down means we should start searching at a given x-frame and then search all the x-frames down19 from there (along the adapt link) in the x-framework with-cl ::= with attrCond21 suchthat-cl ::= such that relCond attrCond ::= attrCompare (‘and’ attrCompare)*23 attrCompare ::= attrRef COMP-OPER ref COMP-OPER ::= ‘=’ | ‘<’ | ‘>’ | ‘6=’25 attrRef ::= synonym ‘.’ attrName ref ::= CONST | attrRef27 relCond ::= relRef (‘and’ relRef)* relRef ::= all the relationships in the XVCL models29 Appendix B. Queries Used for Performance Evaluation 1. Select all the adapt commands from all x-frames31 adapt a; Select a33 2. Select all the <insert> commands directly nested within <adapt> commands insert i; adapt a;35 Select i such that Contains (a,i) 3. Select variables whose values are modiﬁed in x-frame X37 variable v; x-frame x, command c; Select v such that Modiﬁes (c,v) and Contains (x,c) with x.name=‘X’39 4. Select x-frames that modify value of variable COLOR x-frame x; variable v; command c;41 1st Reading February 8, 2006 16:49 WSPC/117-ijseke 00268 Analysis of Meta-Programs: An Example 25 Select x such that Modiﬁes (c,v) and Contains (x,c) with v.name=‘COLOR’1 5. Select x-frames that adapt x-frame X x-frame x1; x-frame x2;3 Select x1 such that Adapts (x1,x2) with x2.name=‘X’ 6. Select x-frames adapted directly or indirectly from XVCL command