Software Reuse: Advances in Software Reusability: 6th International Conference ICSR-6, Vienna, Austria, June 27-29, 2000. Proceedings

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen

1844

Springer Berlin Heidelberg New York Barcelona Hong Kong London

Milan Paris Singapore Tokyo

William B. Frakes (Ed.)

Software Reuse: Advances in Software Reusability 6th International Conference, ICSR-6 Vienna, Austria, June 27-29,2000 Proceedings

Springer

Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editor William B. Frakes Virginia Tech, Computer Science Department 7054 Haycock Road, Falls Church, VA 22043-231 1, USA E-mail: wfrakes @ vt.edu Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Software reuse: advances in software reusability : 6th international conference ;proceedings I ICSR-6, Vienna, Austria, June 27 - 29, 2000. William B. Frakes (ed.). - Berlin ; Heidelberg ;New York ; Barcelona ;Hong Kong ;London ; Milan ; Paris ; Singapore ;Tokyo : Springer, 2000 (Lecture notes in computer science ; Vol. 1844) ISBN 3-540-67696-1

CR Subject Classification (1998): D.2, K.6, D.l, J.l ISSN 0302-9743 ISBN 3-540-67696- 1 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations,recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9,1965, in its current version, and permission for use must always be obtained from Springer-Verlag.Violations are liable for prosecution under the German Copyright Law. Springer-Verlag is a company in the BertelsmannSpringer publishing group. 8 Springer-Verlag Berlin Heidelberg Zoo0 Printed in Germany Qpesetting: Camera-ready by author, data conversion by DA-TeX Gerd Blumenstein Pnnted on acid-free paper SPIN:10722052 06/3142 5432 10

Message from the Program Chair People like to make predictions about software reuse. Some of us have predicted that systematic reuse via domain engineering will produce a paradigm shift in software engineering. Others have predicted that reuse will be universally accepted as good practice, and therefore die as a research discipline. While significant progress has been made in systematic reuse, the paradigm shift is not yet complete, nor has reuse research died. What has happened in the past few years in that the concerns of the reuse research community have fragmented into many subareas. These include componentry, product line architectures, design patterns, functional languages, economics, and object oriented methods. The ICSR6 program reflects this diversity. This fragmentation means that it is ever harder to keep up with developments in reuse. To address this problem, the ICSR6 program contains several summary talks on various areas of reuse research. There is also diversity in the origins of the papers: There are contributions from Europe, North and South America, Asia, and Australia. ICSR6 has many new contributors and committee members, along with many long time contributors. The many kinds of diversity should make for an interesting and productive conference. Enjoy ICSR6 in Vienna.

June, 2000

Bill Frakes

Message from the General Chair

The International Conference in Software Reuse has always had a special relationship with Europe, dating back to its modest beginnings as a workshop in 1991 in Germany. During this first edition, and again in its second edition in Italy two years later, the workshop matured and acquired a critical mass of visibility in the software engineering community. These formative experiences in Europe permitted the workshop to reincarnate itself as a full-fledged conference in a number of locations in North and South America in the decade that followed. Now, nearly ten years after that first workshop, we are pleased to welcome ICSR back to Europe for the first time since its transformation into the world’s premier conference on software reuse, to Vienna, at the very center of Europe. The past decade has seen many concepts first articulated by that small group of original participants, such as component-oriented development, pass into the general vocabulary. Yet as satisfying as it is for us to see the validation of reuse as the dominant software development paradigm today, much remains to be done. Product line architectures are only beginning to reach their full potential. Systematic reuse processes are only beginning to be codified and implemented. The full impact of reuse on the economics of enterprise information technology is only now beginning to be analyzed. No other conference can address these issues as directly as ICSR. ICSR owes an immense debt of gratitude to ARCS, the Austrian Research Centers, whose extraordinary generosity has literally made this conference possible. Special thanks for this opportunity are due to my longtime colleague Professor G¨ unter Koch, a prominent champion of European software engineering for the past twenty years, and now a leading figure in the transformation of ARCS from its traditional role in support of government research into a dynamic participant in the commercial IT industry. As part of that transformation, ARCS has made a deep commitment to the very technologies that are the subject of our conference. The Executive Committee thanks all of the volunteers who have contributed their efforts to the organization of this conference. Most of all, however, our sincerest thanks are reserved for Dr. Dieter Donhoffer of ARCS, whose seemingly inexhaustible supply of energy and resourcefulness has created an event that will not only be a useful contribution to the software engineering community but a memorable one for its participants as well.

June, 2000

John Favaro

Committees

General Chair John Favaro Program Chair William B. Frakes Tutorial Co-chairs Patricia Collins Kyo Kang Corporate Support Co-chairs Juan Llorens Mike Mannion

Publicity Co-chairs Roland T. Mittermeir Giancarlo Succi Exhibitions/Demos Co-chairs Sidney Bailin Dieter Donhoffer Local Arrangements Chair Registrations Chair Finance Chair Dieter Donhoffer

Program Committee O. Alonso (USA) D. Batory (USA) S. Bailin (USA) I. Baxter (USA) T. Biggerstaff (USA) C. Boldyreff (UK) J. Bosch (SWEDEN) S. Castano (ITALY) S. Cohen (USA) P. Collins (USA) J. Cybulski (Australia) K. Czarnecki (Germany) P. Devanbu (USA) J. Favaro (Italy) C. Fox (USA) B. Frakes (USA) (Chair) S. Fraser (Canada) H. Gall (Austria) H. Gommaa (USA) M. Griss (USA) E. Guerrieri (USA) S. Isoda (Japan)

K. Kang (Korea) P. Koltun (USA) G. Kovacs (Hungary) J. Kuusela (Finland) M. Lacroix (Belgium) J. Lerch (USA) J. Leite (Brazil) C. Lillie (USA) J. Llorens (Spain) M. Mannion (UK) Y. Maarek (Israel) M. Matsumoto (Japan) Y. Matsumoto (Japan) R. Mittermeir (Austria) M. Morisio (USA) J. Neighbors (USA) H. Obbink (Austria) R. Prieto-Diaz (USA) S. Robertson (UK) G. Succi (Canada) S. Wartik (USA) B. Weide (USA)

VIII

Committees

Organizing Committee D. Donhoffer (Chair) G. Holzer

M. Strasser

E. Voehringer G. Zoffmann

Sixth International Conference on Software Reuse ICSR6 Vienna, Austria June 27-29, 2000 Sponsored by Austrian Federal Ministery for Traffic, Innovation, and Technology Austrian Computer Society Deloitte &Touche DTInf Desarrollos para las Tecnolog´ıas de la Informaci´ on Fraunhofer Institute for Experimental Software Engineering Intecs Sistemi Sodalia TCP Sistemas e Ingenier´ıa University of Madrid Organized and supported by

Table of Contents

Generative Reuse and Formal Domain Languages A New Control Structure for Transformation-Based Generators . . . . . . . . . . . . . 1 Ted J. Biggerstaff Palette: A Reuse-Oriented Specification Language for Real-Time Systems . . 20 Binoy Ravindran and Stephen Edwards From Application Domains to Executable Domains: Achieving Reuse with a Domain Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Ulf Bergmann and Julio Cesar Sampaio do Prado Leite Reuse of Knowledge at an Appropriate Level of Abstraction Case Studies Using Specware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Keith E. Williamso, Michael J. Healy and Richard A. Barker

Object Oriented Methods 1 Building Customizable Frameworks for the Telecommunications Domain: A Comparison of Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Giovanni Cortese, Marco Braga and Sandro Borioni Object Oriented Analysis and Modeling for Families of Systems with UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Hassan Gomaa Framework-Based Applications: From Incremental Development to Incremental Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Neelam Soundarajan and Stephen Fridella

Product Line Architectures Achieving Extensibility Through Product-Lines and Domain-Specific Languages: A Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Don Batory, Clay Johnson, Bob MacDonald and Dale von Heeder Implementing Product-Line Features with Component Reuse . . . . . . . . . . . . . .137 Martin L. Griss Representing Requirements on Generic Software in an Application Family Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Mike Mannion, Oliver Lewis, Hermann Kaindl, Gianluca Montroni and Joe Wheadon

X

Table of Contents

Implementation Issues in Product Line Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 Klaus Schmid and Cristina Gacek

Requirements Reuse and Business Modeling Requirements Classification and Reuse: Crossing Domain Boundaries . . . . . 190 Jacob L. Cybulski and Karl Reed Reuse Measurement in the ERP Requirements Engineering Process . . . . . . . 211 Maya Daneva Business Modeling and Component Mining Based on Rough Set Theory . . 231 Yoshiyuki Shinkawa and Masao J. Matsumoto

Components and Libraries Visualization of Reusable Software Assets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 Omar Alonso and William B. Frakes Reasoning about Software-Component Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 266 Murali Sitaraman, Steven Atkinson, Gregory Kulczycki, Bruce W. Weide, Timothy J. Long, Paolo Bucci, Wayne Heym and Scott Pike and Joseph E. Hollingsworth Use and Identification of Components in Component-Based Software Development Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Marko Forsell, Veikko Halttunen and Jarmo Ahonen Promoting Reuse with Active Reuse Repository Systems . . . . . . . . . . . . . . . . . . 302 Yunwen Ye and Gerhard Fischer

Design Patterns A Method to Recover Design Patterns Using Software Product Metrics . . . 318 Hyoseob Kim and Cornelia Boldyreff Object Oriented Design Expertise Reuse: An Approach Based on Heuristics, Design Patterns and Anti-Patterns . . . . 336 Alexandre L. Correa, Cl´ audia M. L. Werner and Gerson Zaverucha Patterns Leveraging Analysis Reuse of Business Processes . . . . . . . . . . . . . . . . .353 Marco Paludo, Robert Burnett and Edgard Jamhour Constructional Design Patterns as Reusable Components . . . . . . . . . . . . . . . . . 369 Sherif Yacoub, Hany H. Ammar and Ali Mili

Table of Contents

XI

Object Oriented Methods 2 A Two-Dimensional Composition Framework to Support Software Adaptability and Reuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 Constantinos A. Constantinides, Atef Bader and Tzilla Elrad Structuring Mechanisms for an Object-Oriented Formal Specification Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 M´ arcio Corn´elio and Paulo Borba Software Reuse in an Object Oriented Framework: Distinguishing Types from Implementations and Objects from Attributes . . . . . . . . . . . . . . . . . . . . . . . 420 J. Leslie Keedy, K. Espenlaub, G. Menger, A. Schmolitzky and M. Evered Compatibility Elements in System Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 Giancarlo Succi, Paolo Predonzani and Tullio Vernazza Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .449

A New Control Structure for Transformation-Based Generators Ted J. Biggerstaff [email protected]

Abstract. A serious problem of most transformation-based generators is that they are trying to achieve three mutually antagonistic goals simultaneously: 1) deeply factored operators and operands to gain the combinatorial programming leverage provided by composition, 2) high performance code in the generated program, and 3) small (i.e., practical) generation search spaces. The hypothesis of this paper is that current generator control structures are inadequate and a new control structure is required. To explore architectural variations needed to address this quandary, I have implemented a generator in Common LISP. It is called the Anticipatory Optimization Generator (AOG1) because it allows programmers to anticipate optimization opportunities and to prepare an abstract, distributed plan that attempts to achieve them. The AOG system introduces a new control structure that allows differing kinds of knowledge (e.g., optimization knowledge) to be anticipated, placed where it will be needed, and triggered when the time is right for its use.

1

Problems

A serious problem of most transformation-based generators is that they are trying to achieve three mutually antagonistic goals simultaneously: 1) deeply factored operators and operands to gain the combinatorial programming leverage provided by composition, 2) high performance code in the generated program, and 3) small (i.e., practical) generation search spaces. This paper will make the argument that this quandary is due in large measure to the control structure characteristics of large global soups of pattern-directed transformations. While pattern-directed transformations make the specification of the transformations easy, they also explode the search space when one is trying to produce highly optimized code from deeply factored operators and operands. Since giving up the deep factoring also gives up the combinatorial programming leverage provided by the composition, that is not a good trade off. There are other problems in addition to the search space explosion. Pattern-directed transforms provide relatively few tools for grouping sets of transformations, coordinating their operation, and associating them with a large grain purpose that transcends the fine grain structural aspects of the target program. For example, there are few and crude tools to express the idea that some subset of tightly related, cooperating transformations is designed for the narrow purpose of creating, placing and merging loops in the target program. 1

Much of this work was done at Microsoft Research and the author gratefully acknowledges the support of Microsoft.

W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 1-19, 2000.  Springer-Verlag Berlin Heidelberg 2000

2

Ted J. Biggerstaff

Along a similar vein, it is difficult to generate target code optimized for differing machine architectures from a single canonical specification. For example, one would like to be able to generate code optimized for a non-SIMD architecture and with the flip of a switch generate code optimized for a SIMD architecture. With conventional systems this is difficult. There is no way currently to record knowledge about the reusable components that may lead to optimization opportunities during the generation process. For example, the writer of a reusable component may know that a property of his component ensures that part of its code can be hoisted above a loop that will be generated to host the component. Conventional transformation systems allow no easy way to express and then later exploit such information. Similary, most conventional transformation systems provide no mechanism to record knowledge of future optimization opportunities that become known in the course of executing early transformations. Further, there is no way to condition such optimization opportunities upon optimization events (e.g., a substitution of a particular structure) or expected properties of the generated code (e.g., the requirement that an expression must have been simplified to a constant). Finally, there is no way to intermix (abstractly) planned optimization operations with opportunistic optimization operations that cannot be planned because the opportunities for these optimizations arise unpredictably as a consequence earlier transformations manipulating the target program code. We will introduce a new kind of transformation and a new control structure (called a tag-directed control structure) that can overcome much of the search space explosion problem and also can address these other problems. Let us review convention transformation architectures, contrast the new architecture with respect to these conventional systems and then examine how this new architecture addresses these problems.

2

The New Control Structure

2.1

Overview

Conventional Transformation Systems. Conventionally, generic transformation systems store knowledge as a single global soup of transformations represented as rules of the form syntactic pattern ⇒ reformulated structure The left hand side of the rule recognizes the syntactic form and binds matching elements of the program being transformed to transformation variables (e.g., ?operator) in the pattern. If that is successful, then the right hand side of the rule (instantiated with the variable bindings) replaces the matched portion of the program. Operationally, rules are chosen (i.e., triggered) based largely on the syntactic pattern of the left hand side, which may include type constraints as well as purely syntactic patterns. Rules may include some set of additional constraints (often called enabling conditions) that must be true before the rule can be triggered. However, all of this is not entirely sufficient since pure declarative forms are often inadequate to express

A New Control Structure for Transformation-Based Generators

3

complex procedural transformations. Therefore, the rules of some systems also allow for arbitrary computations to occur during the execution of the rules. The operational form of the program being transformed may be text or, more typically in modern systems, an Abstract Syntax Tree (AST). In summary, the major control structure of generic transformation systems is based largely on the pattern of the program portion being transformed. Hence, we call such systems pattern-directed. Draco. Some transformation systems add control variations to enhance efficiency. For example, Draco [10] separates its rules into two kinds: 1) refinement rules, and 2) optimization rules. Refinement rules add detail by inlining definitions. Optimization rules reorganize those details for better performance. Further, the refinement rules are grouped into subsets that induce a set of translation “stages” by virtue of the fact that each group translates from some higher level domain specific language (e.g., the language of the relational algebra) into one or more lower level domain specific languages (i.e., ones that are closer to conventional programming languages, such as a tuple language). After each such refinement stage, optimization rules are applied to reorganize the current expression of the program into a more optimum form within the current domain specific language. The final output is a form of the program expressed in a conventional programming language such as C. While such generators usually produce programs with adequate performance and do so within an acceptable period of time, in some domains, the search space of the optimization phases tends to explode. Tag-Directed. A key insight of AOG (i.e., the use of tags to identify and trigger optimizing transformations) arose from an analysis of several transformation-based derivations of graphics functions. The derivations were quite long with a series of carefully chosen and carefully ordered transformations that prepared the program for the application of key optimizing transforms. The need to choose exactly the right transform at exactly the right point over and over again seemed like a long series of miracles that implied a huge underlying search space. Further, I noticed that the choice of the various transformations depended only weakly on the patterns in the program. Rather they depended on other kinds of knowledge and relationships. Some of this was knowledge specific to the reusable components and could be attached to the components at the time of their creation. Other knowledge arose in the course of transformation operation (e.g., the creation of a data flow introduced by a preparatory transformation). Tags serve to capture such knowledge and thereby they became a key element of the AOG control structure. Such use of tags motivates the moniker of tagdirected transformations for those optimizing transformations that are triggered largely because of the tags attached to the AST. In triggering these optimizing transformations, patterns play a lesser role. Event Triggering. The transformation name in a tag indicates what transformation to fire but not when. Thus, the tag control structure includes the idea of local and global events associated with the tag structure that indicate when to fire the transformations. Global events, which apply to the whole subtree being operated on, provide a way to induce a set of optimization stages. Each stage has a general optimization purpose, which assures certain global properties are true upon completion of the stage. For example, all loop merging is complete before commencing the stage that triggers certain kinds of code hoisting outside of loops. Local events, on the other hand, are events specific to an AST subtree such as its

4

Ted J. Biggerstaff

movement or substitution. Local events occur in the course of some other transformation’s operation. Local events allow opportunistic transformations to be interleaved among the transformations triggered during a stage. Components. Another control structure innovation is to represent passive and active components by different mechanisms. Passive components (just called components) are those for which one can write a concrete, static definition. These comprise the library reusable piece parts from which the target program will be built and they are represented in an Object Oriented hierarchy. For example, one of the data types specific to the graphics domain language that I use is a Neighborhood, which is a subset of pixels in a larger image centered on some specific pixel within that larger image. Specific instances of neighborhoods are defined via functional methods that compute: 1) the indexes of neighborhood pixels in terms of the image’s indexes (Row and Col), 2) a set of convolution weights associated with individual pixel positions within the neighborhood (W), and 3) the range of the relative offsets from the centering pixel (PRange, QRange). These methods, like conventional refinement rules, will be inlined and thereby will form portions of the target program. The operator components (e.g., the convolution operator ⊕) are defined in the operator subtree of this OO hierarchy and act like multi-methods whose definition is determined by the type signature of the operator expression. For example, “(⊕ ⊕ array [iterator, iterator], neighborhood)” is a signature that designates a method of ⊕ with a static, inline-able definition which will become the inner loop of a convolution. Transformations. The transformations are the active components and are represented as executable functions rather than isolated declarative rules. This allows them to handle high degrees of AST variation; compute complex enabling conditions; and recognize why enabling conditions are failing and take actions to fix them (e.g., by directly calling another transformation). Representing such transformations as conventional rules would require splitting them up into a number of individual transformations which would thereby explode the generator search space. Larger grain transformations that are implemented as programmable functions prevent this explosion. Kinds of Transformations. AOG transformations come in two flavors – patterndirected and tag-directed. Pattern-directed transformations are used for program refinement stages and tag-directed are used for optimization stages. Pattern-directed transformations are organized into the OO hierarchy to help reduce the number of candidate transformations at each point in the AST. That is to say, the OO hierarchy captures a key element of the pattern – the type of the subtree being processed, which saves looking at a large number of transformations that might syntactically match but semantically fail. Partial Evaluation. Like mathematical equations, reformulations of program parts require frequent simplication. If simplifications are represented as isolated transformations in a global soup of transformations, they explode the search space because they can be applied at many points, most of which are inappropriate. Therefore, AOG contains a partial evaluator that is called for each new AST subtree to perform that simplication. A partial evaluator is a specialized agent that simplifies expressions without exploding the search space. Now let us examine these ideas in the context of an example.

A New Control Structure for Transformation-Based Generators

2.2

5

Related Interdependent Knowledge

Sometimes a priori knowledge about the interdependence of several aspects of a problem implies a future optimization opportunity and using this knowledge in course of generation can reduce the generator’s search space. For example, a component writer may know that in a particular architectural context (e.g., a CPU without parallel processing instructions) a specific optimization will be enabled within a component and will be desirable at a particular stage of generation. How should such knowledge be captured? Where should it be kept? And how should the optimization be triggered? Let us look at a concrete example of this situation. Suppose that the component writer is creating a description of a pixel neighborhood (call it s) within a graphics image and that description will be used in the context of graphics operators such as the convolution2 operator. This neighborhood description comprises a set of methods of s that describe the size and shape of the neighborhood, the weights associated with each relative position in the neighborhood, how to compute the relative positions in terms of the [i,j] pixel of the image upon which the neighborhood is centered, and any special case processing such as the special case test for the neighborhood hanging off the edge of the image. Let us consider the method that defines the weights for a particular neighborhood s. If any part of the neighborhood is hanging off the edge of the image, the weight will be defined as 0. Otherwise, the weights will be defined by the matrix:

Q4 647 8 −1 0 1 − 1  − 1 0 1   P  0 − 2 〈 0〉 2    1  − 1 0 1    where p and q define the pixel offset from image pixel upon which the neighborhood is centered. The diamond bracketed entry indicates the center of the neighborhood. Then the definition of the weight method w for pixel [p,q] in the neighborhood s is defined by the following pseudo-code, where s is centered on the [i,j] pixel of an m x n image: w.s(i,j,m,n,p,q) ⇒ {if ((i==0) || (j==0) || (i==(m - 1)) || (j==(n - 1))) then 0; else {if ((p!=0) && (q!=0)) then q; else {if ((p==0) && (q!=0)) then (2 * q); else 0 }}}

2

A convolution is a graphics operator that computes an output image b from an input image a by operating on each neighborhood around each pixel a[i,j] to produce the corresponding b[i,j] pixel. Specifically, the operation is a sum of products of each of the pixels in the neighborhood around a[i,j] times the weight value defined for that pixel in the neighborhood.

6

Ted J. Biggerstaff

What does the component writer know about this component that might be helpful in the course of code generation? He knows that the eventual use of the weight calculation will be in the context of some image operator (e.g., a convolution). Further, that context will comprise a 2D loop iterating over the neighborhood that will be nested within another 2D loop iterating over the whole image. Further, the component writer knows that the special case test is not dependent on the neighborhood loop and, therefore, the test can be hoisted outside of the neighborhood loop. Or equivalently, the loop can be distributed over the if statement producing an instance of the loop in both the then and else clauses. Since the specific instance of the image operation has not been chosen and these loops have not yet been generated, the component writer cannot execute the potential transformation yet. The component writer can only use the abstract knowledge that defines, in general terms, the eventual solution envelope. What he would like to do is to associate a piece of information with the if statement that would indicate the transformation to be invoked and some indication of when it should be invoked. AOG provides a mechanism for accomplishing this by allowing the component writer to attach a tag (to be used by the generator) to the if statement. In this case, the tag has the form: (_On SubstitutionOfMe (_PromoteConditionAboveLoop ?p ?q)) This tag is like an interrupt that is triggered when the if statement gets substituted in some context, i.e., when a local substitution event happens to the if statement. When triggered, the tag will cause the _PromoteConditionAboveLoop transform to be called with the name of the target loop control variables (i.e., the values p and q, which will be bound to the generator variables ?p and ?q) as parameters. The transform will find the loops controlled by the values of p and q, check the enabling conditions, and if enabled, perform the distribution of the loop over the if statement. Thus, _PromoteConditionAboveLoop will transform a form like {Σ Σp,q

(p ∈ [-1:1] ) (q ∈ [-1:1] ) : { if(i==0 || j==0 || i==m-1 || j==n-1) /* Off edge */ then <special case processing>; else }}

into a form like { if(i==0 || j==0 || i==m-1 || j==n-1) /* Off edge */ then {Σ Σp,q (p ∈ [-1:1] ) (q ∈ [-1:1] ): <special case processing>} else {Σ Σp,q (p ∈ [-1:1] ) (q ∈ [-1:1] ): } } Thus, with these ideas, we have introduced a new kind of transformation, which we will call a tag-directed transformation. Such transformations are triggered by events, in contrast to conventional pattern-directed transformations that are triggered largely

A New Control Structure for Transformation-Based Generators

7

by patterns in the AST (Abstract Syntax Tree). Another difference from patterndirected transformations is that tag-directed transformations and their host tags can capture knowledge that is not easily derivable from the AST patterns or operator/operand semantics. Such knowledge would require some deep inference, some sense of the optimization opportunities particular to the evolving program or some knowledge that is fleetingly available in the course of transformation execution. For example, the tag-directed example we examined takes advantage of several interrelated knowledge nuggets that have little to do with the structure of the AST: 1) the knowledge of the case structure of the reusable component s where the general purpose of the branching is known (i.e., one branch is a special case), 2) the knowledge that the reusable component will be used in the context of neighborhood loops whose general purpose is known a priori, 3) the knowledge that the if condition within the component is independent of the anticipated neighborhood loops, 4) the optimization knowledge that executing an if test outside of the loop instead of within the loop is more computationally efficient, and 5) the generation knowledge that attaching an interrupt-like tag (incorporating all of this special knowledge) to the reusable component will produce search space reduction advantages by eliminating the search for which transform to fire, where to apply it in the AST, and when to fire it. The key objective of tag-directed transformations is to reduce the generator search space explosion that arises when each transformation is just one of many in a global soup of transformations. By using all of this knowledge together, we can eliminate much of the branching in the search space (i.e., eliminate all of the alternative transformations that might apply at a given point in the generation) because tags supply all of the information needed to make the choice of transformation. They determine: 1) which transformation is called (i.e., it is explicitly named in the tag), 2) when it is called (i.e., when the named event occurs), and 3) where in the AST to apply the transform (i.e., it is applied to the structure to which the tag is attached). 2.3

The Likelihood of Optimization Opportunities

Not all knowledge that one might want to use is deterministic. Often, there is just the likelihood that some optimization friendly condition may occur as a result of code manipulation. This knowledge too is valuable in keeping the search space from exploding while simultaneously achieving important generation goals such as eliminating redundant code. An example of this situation is illustrated by the expression for Sobel edge detection in bitmapped images. DSDeclare image a, b :form ( array m n) :of bwpixel; b = [ (a ⊕ s)2 + (a ⊕ sp)2]1/2 ;

8

Ted J. Biggerstaff

where a and b are (m X n) grayscale images and ⊕ is a convolution operator that applies the template matrices s and sp to each pixel a[i,j] and its surrounding neighborhood in the image a to compute the corresponding pixel b[i,j] of b. s (whose w method was defined earlier) and sp are OO abstractions that define the specifics of the pixel neighborhoods. It is possible and indeed, even likely that the special case processing seen in the w method of s will be repeated in the w method of sp. If so, it would be desirable to share the condition test code if possible by applying the _MergeCommonCondition transformation: { if ?a then ?b else ?c; if ?a then ?d else ?e } => if ?a then {?b; ?d} else {?c ; ?e} where the ?x syntax represents generator variables that will be bound to subtrees of the AST. In the above example, ?a will be bound to the common special case condition code that tests for the neighborhood hanging partially off the edge of the image. Because the component writer anticipates this possibility, he would like to hang a tag on the if statement in the w definitions of s and sp that will cause the _MergeCommonCondition transformation to be called. If the condition code is common and all other enabling conditions are met, it will perform the transformation. However, this raises a question. What event should this transformation be triggered on? Local events like substitution of the subtree would be a bad choice because there is no easy way to assure ordering of the strategic computational goals of the overall optimization process. For example, we want all code sharing across domain specific subexpressions (i.e., global code manipulations) to be completed before any in-place optimizations (i.e., mostly local manipulations) begin. The approach used by AOG is to separate the strategic processing into phases that each have a general purpose such as 1. 2. 3. 4.

inlining definitions (e.g., substituting the method definition of w.s), sharing code across expressions (e.g., sharing common test conditions), performing in-place optimizations (e.g., unrolling loops), and performing clean up optimizations (e.g., eliminating common subexpressions).

These phases behave like an abstract algorithm where the details of the algorithmic steps come from the transformations mentioned in the tags attached to the components. The start of each stage is signaled by the generator posting a global event that will cause all tags waiting on that event to be scheduled for execution. This is how _MergeCommonCondition gets called to share the condition test code common to w.s and w.sp. It is scheduled when the global event signalling the start of the cross expression code sharing is posted by AOG. So, here we have a new control structure construct that allows a useful separation of concerns. The generator writer provides the broad general optimization strategy by defining stages, each with a narrow optimization goal. The component writer at library creation time (or a transformation during generator execution) adds tags that supply the details of the steps. This means that the generator writer does not have to account for all the possible combinations of purposes, sequences, enabling conditions, etc. He only has to create one (or more) abstract algorithms (i.e., define a set of stages) that are suitable for the classes of optimization that might occur. Similarly, the

A New Control Structure for Transformation-Based Generators

9

component writer (or transformation writer in the case where the tags are dynamically added to the AST) can add tags that take advantage of every bit of knowledge about the components, even possibilities that may or may not arise in any specific case. This kind of separation of concerns avoids much of the search space explosion that occurs when all of the strategic goals, component-specific details, and their interdependencies reside in one central entity such as the generator’s algorithm or in a global soup of transformations. The view that tag-directed transforms are like interrupts is an apt simile because they mimic both the kind of design separation seen in interrupt-driven systems as well as the kind of operational behavior exhibited by interrupt-driven systems. 1.4

Simplification Opportunities

Not all optimizations fit the tag-directed model. There are many opportunities for simplification by partial evaluation. In fact, any newly formed AST subtree is a candidate for such simplification and each transformation that formulates new subtrees immediately calls the partial evaluator to see if the subtrees can be simplified. For example, during the in-place optimization phase, one of the neighborhood loops is unrolled by a tag-directed transformation. The pseudo-code of the internal form of the loop looks like: {_sum (p q) (_suchthat (_member p (_range -1 1)) (_member q (_range -1 1))) {if ((p!=0) && (q!=0)) then (a[(i + p),(j + q)]*p); else {if ((p!=0) && (q==0)) then (a[(i + p),(j + q)]*(2*p)); else 0;}}} where the _sum operator indicates a summation loop and the _suchthat clause indicates that p and q range from –1 to +1. This produces two levels of loop unwrapping. In the course of the first level of unwrapping (i.e., the loop over p), one of the terms (i.e., the one for (p==1) ) has the intermediate form: {_sum (q) (_suchthat (_member q (_range -1 1))) {if (q!=0) then a[(i+1),(j+q)] ; else {if (q==0) then (a[(i+1),(j+q)]*2); else 0;}}} When the remaining loop over q is subsequently unrolled, we get the expression ({if (-1!=0) then a[(i+1),(j-1)] ; else {if (-1==0) then (a[(i+1),(j-1)]*2); else 0;}} + {if (0!=0) then a[(i+1),(j+0)]; else {if (0 == 0) then (a[(i+1),(j+0)]*2);

10

Ted J. Biggerstaff

else 0;}} + {if (1!=0) then a[(i+1),(j+1)] ; else {if (1 == 0) then (a[(i+1),(j+1)]*2); else 0;}}) The unroll transform calls the partial evaluator on this expression which produces the final result for this subloop: (a[(i+1),(j-1)] + (a[(i+1),j]*2) + a[(i+1),(j+1)]) In the same way, the other derived, nested loops produce zero or more analogous expressions for a total of six terms for the original loop over p and q. Partial evaluation is critical because it allows future transformations to execute. Without it, many future transformations would fail to execute simply because of the complexity of detecting their enabling conditions or the complexity of manipulating un-simplified code. Partial evaluation is the most executed transformation. For the Sobel edge detection expression, 44 out of a total of 92 transformations required to generate code are partial evaluation. 1.5

Architectural Knowledge

No aspect can have a larger effect on the final form of the generated code than the architecture of the CPU. Consider the two different sets of code produced by AOG for a CPU without parallel instructions and one with parallel instructions (i.e., the MMX instructions of the PentiumTM processor). For a single CPU Pentium machine without MMX instructions (which are SIMD instructions that perform some arithmetic in parallel), the AO generator will produce code that looks like for (i=0; i < m; i++) /* Version 1 */ {im1=i-1; ip1= i+1; for (j=0; j < n; j++) { if(i==0 || j==0 || i==m-1 || j==n-1) then b[i, j] = 0; /* Off edge */ else {jm1= j-1; jp1 = j+1; t1 = a[im1,jm1]*(-1)+a[im1,j]*(-2) + a[im1,jp1]*(-1)+a[ip1,jm1]*1 + a[ip1,j]*2+a[ip1,jp1]*1; t2 = a[im1,jm1]*(-1)+a[i,jm1]*(-2) + a[ip1,jm1]*(-1)+a[im1,jp1]*1 + a[i,jp1]*2+a[ip1,jp1]*1; b[i,j] = sqrt(t1*t1 + t2*t2 )}}} This result requires 92 large grain transformations and is produced in a few tens of seconds on a 400 MHz Pentium. In contrast, if the machine architecture is specified to be MMX, the resultant code is quite different:

A New Control Structure for Transformation-Based Generators

11

{int s[(-1:1), (-1:1)]={{-1, 0, 1}, {-2, 0 , 2}, {-1, 0, 1}};/* Version 2 */ int sp [(-1:1), (-1:1)]={{-1, -2, -1}, {0, 0, 0}, {1, 2, 1}}; for (j=0; j
3

MMX instructions use registers containing an even number of operands to be operated on in parallel. Thus, pmadd3 is just a special case of pmadd4((a0, a1, a2, a3), (c0, c1, c2, c3)) with a zero padded fourth operand in each of the registers a and c. pmadd4 is defined as (a0*c0+a1*c1, a2*c2+a3*c3). Thus, pmadd3 ((a0, a1, a2) , (c0, c1, c2)) is actually the special case pmadd4 ((a0, a1, a2, 0) , (c0, c1, c2, 0)).

12

Ted J. Biggerstaff

if (?MMX == ‘MMX) then <MMXDefinition> else ; Given a global generator variable (say ?MMX) bound to a value indicating the target architecture, partial evaluation of the reusable components will result in differently tagged definitions for each architectural variation. Thus, after this partial evaluation, the weight method of s for the MMX architecture will have some additional tags that are MMX specific. In order to exploit MMX instructions, the generated code needs to have a couple of important architectural properties. The weights need to be formed into a vector to exploit the vector processing of the MMX instructions. Ideally, this should happen at generation time but failing that, it could happen at target program execution time by computing all weights first and then using the resulting vector to compute the convolution. The second important architectural property is a branch free expression of the convolution computation so that the vector processing instructions will not be interrupted by branch instructions. Let’s us sketch how these properties are achieved. We will start with getting s and sp into vector form. This is accomplished by attaching the tag (_On SubstitutionOfMe

(_MapToArray))

to the non-special case branch of w.s and w.sp. For w.s, this branch would be the expression {if ((p!=0) && (q!=0)) then q; else {if ((p==0) && (q!=0)) then (2*q); else 0 }} When triggered, _MapToArray replaces this expression with a reference to a vector s[p,q] which it then sets about creating. First, it formulates the data declaration int s[(pRange.s), (qRange.s)]= {∀ ∀p,q (p ∈ pRange.s ) (q ∈ qRange.s ) : {if ((p!=0) && (q!=0)) then q; else {if ((p== 0)&&(q!=0)) then (2*q); else 0 }}} which after substitution of the definitions of pRange.s and qRange.s followed by partial evaluation, becomes int s[(-1:1),(-1:1)]={{-1, 0, 1},{-2, 0 , 2}, {-1, 0, 1}} The next job is to get rid of the branching in the loop body. This is handled by the attached tag4 (_On CFWrapUpEnd(0) ( _SplitLoopOnCases)) 4

CFWrapUpEnd is the event signalling the clean up optimization phase and the zero parameter on the event indicates that it should be scheduled before any other transforms in that phase that have larger parameters.

A New Control Structure for Transformation-Based Generators

13

to the top level if statement in w.s. This will effect the incorporation of each of the cases of the condition test ((i==0) || (j==0) || (i==(m - 1)) || (j==(n - 1))) into a different loop, thereby producing the five loops in the MMX code shown earlier. _MapToArray checks the enabling conditions, deconstructs both the loop control information and the branching test, and reformulates the single loop structure into {∀ ∀i,j ((i ∈[0:(m-1)]) && (j ∈[0:(n-1)]) && (i==0)): b[i,j] = 0 } {∀ ∀i,j ((i ∈[0:(m-1)]) && (j ∈[0:(n-1)]) && (j==0)): b[i,j] = 0 } {∀ ∀i,j ((i ∈[0:(m-1)]) && (j ∈[0:(n-1)]) && (i==(m-1)): b[i,j] = 0 } {∀ ∀i,j ((i ∈[0:(m-1)]) && (j ∈[0:(n-1)]) && (j==(n-1)): b[i,j] = 0 } {∀ ∀i,j ((i ∈[0:(m-1)]) && (j ∈[0:(n-1)]) && (i!=0) && (j!= 0) && (i!=(m - 1)) && (j!=(n - 1))): … non-special process…} To simplify the control expressions, _MapToArray invokes some lightweight inference and uses AOG’s built-in schema language to perform that inference. (See 6 for more details of the schema language and this inference operation.) It uses a set of rules that recognize an iteration pattern and thereby, determine how to simplify the loop control and the loop body. For example, suppose that the control variable i is really a fixed constant (e.g., (i ∈[0:(m-1)]) && i==0)). This would engender elimination of the control variable i from the loop control and substitution of 0 everywhere i appears in the loop body. Other rules recognize patterns such as those that require clipping the upper and/or lower limits of the control range, which is how the non-special processing loop control is generated. There is still more massaging to do. At this point, the non-special processing loop body looks like {t1= {Σ Σp,q (p∈ ∈[-1:1])(q∈ ∈[-1:1]):a[(i+p),(j+q)]*s[p,q]} t2= {Σ Σp,q (p∈ ∈[-1:1])(q∈ ∈[-1:1]):a[(i+p),(j+q)]*sp[p,q]} b[i,j] = sqrt(t1*t1 + t2*t2);} The loops over p and q (i.e., {Σ Σp,q: … } ) arose from the definition of the convolution operator, which was defined by the “(⊕ ⊕ array [iterator, iterator], neighborhood)” method of the ⊕ operator (a[i,j] ⊕ s) ⇒ {Σ Σp,q (p∈ ∈ pRange.s) (q∈ ∈qRange.s ): {a[row.s(i,j, m, n, p,q),col.s(i,j, m,n,p,q)] * w.s(i,j,m,n,p,q) }} and which has a tag of the form

14

Ted J. Biggerstaff

(_ON CFWrapUpEnd(1)

(_MMXLoop))

attached to its loop. Because the tag was preserved during definition inlining, this tag is now attached to both of the loops over p and q since they are derived from the definition of the convolution operator. The _MMXLoop transformation will massage these loop controls and loop bodies into the form shown in the final MMX pseudocode shown earlier. 1.6

Creation, Placement, and Merging of Loops

The interrupt style control structure of tag-directed transformations is not ideal for all generator operations. There is still a role for pattern-directed transformations for some refinement-like operations. Even so, a large global soup of pattern-directed transformations is not optimal from a search-space point of view so we will adapt that model to the job required by AOG. The pattern-directed processing (which precedes the tag-directed processing) performs loop introduction, placement and merging. In the course of that, it may also perform some opportunistic optimizations (e.g., reduction in strength of the square operator). At the end of the pattern-directed processing, the example has the following form expressed in a C-ish pseudo-code. for (i=0; i < m; i++) {for (j=0; j < n; j++) {t1 = (a[i,j] ⊕ s); t2 = (a[i,j] ⊕ sp); b[i,j] = sqrt(t1*t1 +

t2*t2)

}}

Like APL, AOG operators use implicit looping. This simplifies the specification code in that most domain operations can be written as loop-free expressions of operators and operands. It also makes manipulation of the code much simpler than if the programmer where allowed to program arbitrary loops. However, it makes AOG’s job harder in that it must generate the loops and figure out how to eliminate redundant looping operations. It does this by executing an abstract algorithm comprising three phases. 1) Walk down the expression tree reducing operators and adding tag information that describes the implicit looping, 2) Walk back up the tree moving and merging the looping information to eliminate redundant loops, and 1) Walk over the tree again generating loop code, adding tags needed by the tagdirected phase, and executing opportunistic optimizations (e.g., the reduction in 2 strength optimization of the expressions (a[i,j]⊕ ⊕s) and 2 (a[i,j] ⊕sp) ). ⊕ Like the tag-directed phases, the details of the abstract algorithm operations are contained in the code of the transformations. However, the control structure inherent to loop creation and placement does not lend itself to the interrupt-like design of the tag-directed transformations. As the looping data is moved up the expression tree, the rules by which it is transformed and merged are largely determined by the patterns

A New Control Structure for Transformation-Based Generators

15

and semantics of the operators and operands in the tree. This suggests that patterndirected transformations would provide a more suitable control structure. However, a large global soup of pattern-directed transformations tends to explode the search space because too much computation is required to discover which transformations to fire. Since the transformation of the looping information is naturally organized as case-based logic dependent almost exclusively on the semantics of the operators and operands, a small set of candidate transformations is immediately obvious from the operator and operand types in the AST. Thus, the most natural organization for the transformations is to attach them to the domain specific operator and operand classes in the inheritance hierarchy (and group them by phase). This significantly reduces the search space. Operationally, the loop placement control simply walks over the expression tree and executes any phase-specific transformations attached to the operator and operand definitions. The pattern-directed phases of AOG are described in detail elsewhere [4]. 1.7

Summary

In summary, the new control structure is designed to reduce the generator’s search space as much as possible while still allowing deep factorization of reusable componentry and high degrees of optimization of the target code. There are two major phases (i.e., pattern-directed refinement and tag-directed optimization) and the control constructs of each are optimized for the goals of the underlying phases. Each major phase is subdivided into minor phases, each of which has a narrowly specific generation goal. The pattern-directed control structures are designed to optimize the generation, placement, and merging of looping constructs. Because the operator and operand types naturally separate the relevant transformations into small groups, the inheritance hierarchy is used as an index to these small groups. The transformations are further grouped by minor phase, which further diminishes the number of choices at any point. By these techniques, the generator’s search space is significantly reduced because there are usually only a handful of transformations to check at any point in the AST. This organization thwarts most of the search space explosion induced by a generator architecture that relies on global sets of transforms using pattern-directed triggering. The minor phases behave like an abstract algorithm (i.e., a strategy) with the pattern-directed transformations supplying the tactical details. This separation of the strategic from the tactical makes the addition of new operator and operand types quite easy. Optimization is a process of reorganizing the code to accommodate the architectural properties of the CPU. Such code movement requires a different control structure – a tag-directed control structure -- to minimize its search space. Like the pattern-directed control structure used to generate and optimize loops, the tag-directed control structure also separates the strategic from the tactical. The strategic elements are defined by a set of minor phases with very specific computational goals. However, the tag-directed mechanism differs from the pattern-directed in its interrupt-like triggering mechanism and in its organization. The search space reduction with tagdirected transformations is wrought by

16

Ted J. Biggerstaff

• Locating the tag at the point of application in the reusable components, • Naming the specific transformation so that no search is required to determine which transformation should be applied at a given point in time, • Using as much a priori knowledge (e.g., domain specific knowledge) as possible to further narrow the computational purpose and therefore, the search space, and • Using an arbitrarily rich model of local and global events to trigger the transformations named in the tags. Fundamentally, the tag-directed process is a scheduler that keeps a queue of events that have triggered tags. It simply runs until the event queue is empty. Each minor phase is initiated by the posting of a global event naming the phase. When there are no more phases and the queue is empty, tag-directed processing terminates. This control structure relies on the transformations 1. To post local events (e.g., substitution, migration, simplification), 2. To handle their own enabling condition checking and to directly call other transformations to fix up enabling conditions that do not quite meet their specifications, and 3. To call the partial evaluator for each new subtree that is constructed in the AST.

2

Contributions

AOG makes several contributions. • It uses tag-directed transformations to exploit knowledge and operations that are ill suited to pattern-directed transformations. • It stages transformation phases so that each is organized to achieve a narrowly defined translation or optimization purpose. • It provides event-driven tags that allow for opportunistic optimizations as well as for interdependent, anticipated optimizations that can be organized into stages to assure consistency. • It reasons over the domain specific operators and operands early in the translation process to produce tags that can thereby take advantage of that domain specific knowledge later in the optimization process when, conventionally, all of the domain specific knowledge would have been translated away. • It localizes pattern-directed transforms and component definitions to specific abstractions within an inheritance hierarchy thereby reducing the opportunity for them to explode the search space by being applied in inappropriate situations. • It uses a schema language to insulate the transformations from the physical details and variations in the AST.

3

Related Research

This work bears the strongest relation to Neighbors work. [10] The main differences are 1) the fact that the AOG pattern-directed transformations are organized into an inheritance hierarchy which guides the choice of which

A New Control Structure for Transformation-Based Generators

17

transformations to try, and 2) the use of the tag-directed approach for program optimization. Neighbors uses pattern-directed transformations during his optimization. The work bears a strong relationship to Kiczales' Aspect Oriented programming at least in terms of its objectives but the optimization machinery appears to be quite different. [9] Kiczales' optimization mechanism seems not to be distributed over the AST and the optimization algorithms do not appear to be manipulated by the transformations. In contrast, the AOG’s tags are distributed over the program and they undergo transformations as the generator reasons about the domain, the program, and the optimization tags. This work is largely orthogonal but complementary to the work of Batory. [1] Batory optimizes his type equations to choose the optimum components from which to assemble classes and methods. AOG inlines and interweaves the bodies of methods invoked by compositions of method calls (i.e., expressions). Thus, Batory’s generation focus is at the class level and AOG’s is at the instance level. For details of the relationship see [6]. AOG and Doug Smith's work are similar in that they make heavy use of domain specific information in the course of generation. [11] They differ in the machinery used. Smith's work relies more heavily on inference machinery than does AOG. The reasoning that AOG does is narrowly purposeful and is a somewhat rare event (e.g., the transformation that splits the loop in the MMX example above does highly specialized reasoning about loop limits). However, partial evaluation (a form of inference) is heavily used in AOG, which is how three level if-then-else expressions (which are interweavings of the definitions of W, Row, Col and ConvolutionOp) get reduced to expressions like "a[im1,j]*(-2)". The organization of the transformations into goal driven stages is similar to Boyle’s TAMPR [7]. However, Boyle does not use tags. The schema language is most similar to the work of Wile [14, 15] and Crew [8]. Popart leans more toward an architecture driven by compiling and parsing notions. As such, it is influenced less by logic programming. On the other hand, ASTLOG is more similar to the AOG schema language in that it is heavily influenced by logic programming. However, ASTLOG’s architecture is driven by program analysis objectives and is not really designed for dynamic change and manipulation of the AST. It assumes that its target is a set of link files produced by a compile and link operation, thereby producing a batch-oriented model of AST manipulation. Such a model is not well suited to dynamic manipulation and change of the AST under the control of a transformation-based generator. There are a variety of other connections that are beyond the space limitations of the paper. For example, there are relations to metaprogramming [14], logic programming based generation, formal synthesis systems (e.g., Specware) [12], deforestation [13], transformation replay [2] and other procedural transformation systems (e.g., Refine). The differences are greater or lesser across this group and broad generalization is hard. However, the most obvious general differences between AOG and most of these systems is AOG’s use of transformations that operate in the optimization problem domain and are triggered based on optimization-specific events. Additionally, the AOG control structure is unusual. The overall optimization process behaves like an abstract algorithm where the algorithmic steps are stages and where the details of the

18

Ted J. Biggerstaff

steps (i.e., what operations are performed, what part of the AST they affect, and when they get called) are determined by tags on the AST itself. In addition, the event driven transforms behave like interrupts that allow for operations whose invocation details cannot be planned in advance and whose effect is largely simplification.

4

Conclusions

AOG is being developed to study of the effects of architectural variations of generators on programming leverage, variability, performance, and search space size. While still early, it has demonstrated that some operators and types can be deeply factored to allow highly varied re-compositions while simultaneously allowing the generation of high performance code without huge search spaces.

References 1.

Batory, Don, Singhal, Vivek, Sirkin, Marty, and Thomas, Jeff: Scalable Software Libraries. Symposium on the Foundations of Software Engineering. Los Angeles, California (1993) 2. Baxter, I. D.: Design Maintenance Systems. Communications of the ACM, Vol. 55, No. 4, (1992) 73-89 3. Biggerstaff, Ted J.: Fixing Some Transformation Problems. Automated Software Engineering Conference, Cocoa Beach, Florida (1999) 4. Biggerstaff, Ted J.: Anticipatory Optimization in Domain Specific Translation. International Conference on Software Reuse, Victoria, B. C., Canada (1998) 124-133 5. Biggerstaff, Ted J.: Composite Folding in Anticipatory Optimization. Microsoft Research Technical Report MSR-TR-98-22 (1998) 6. Biggerstaff, Ted J.: Pattern Matching for Program Generation: A User Manual. Microsoft Research Technical Report MSR-TR-98-55 (1998) 7. Boyle, James M.: Abstract Programming and Program Transformation—An Approach to Reusing Programs. In: Biggerstaff, Ted and Perlis, Alan (eds.): Software Reusability, Addison-Wesley/ACM Press (1989) 361-413 8. Crew, R. F.: ASTLOG: A Language for Examining Abstract Syntax Trees. Proceedings of the USENIX Conference on Domain-Specific Languages, Santa Barbara, California (1997) 9. Kiczales, Gregor, Lamping, John, Mendhekar, Anurag, Maede, Chris, Lopes, Cristina, Loingtier, Jean-Marc and Irwin, John: Aspect Oriented Programming. Tech. Report SPL97-08 P9710042, Xerox PARC (1997) 10. Neighbors, James M.: Draco: A Method for Engineering Reusable Software Systems. In: Biggerstaff, Ted and Perlis, Alan (eds.): Software Reusability, Addison-Wesley/ACM Press (1989) 295-319 11. Smith, Douglas R.: KIDS-A Knowledge-Based Software Development System. In: Lowry, M. & McCartney, R., (eds.): Automating Software Design, AAAI/MIT Press (1991) 483-514 12. Srinivas, Y. V.: Refinement of Parameterized Algebraic Specifications. In: Bird, R. and Meertens, L. (eds.): Proceedings of a Workshop on Algorithmic Languages and Calculii. Alsac FR. Chapman and Hill. (1997) 164-186

A New Control Structure for Transformation-Based Generators

19

13. Wadler, Philip: Deforestation: Transforming Programs to Eliminate Trees. Journal of Theoretical Computer Science, Vol. 73 (1990) 231-248 14. Wile, David S.: Popart: Producer of Parsers and Related Tools. USC/Information Sciences Institute Technical Report, Marina del Rey, California (1994) (http:// www.isi.edu/software-sciences/wile/Popart/ popart.html) 15. Wile, David S.: Toward a Calculus for Abstract Syntax Trees. In: Bird, R. and Meertens, L. (eds.): Proceedings of a Workshop on Algorithmic Languages and Calculii. Alsac FR. Chapman and Hill (1997) 324-352

Palette: A Reuse-Oriented Specification Language for Real-Time Systems Binoy Ravindran1 and Stephen Edwards2 1

The Bradley Dept. of Electrical & Computer Engineering, Virginia Tech Blacksburg, VA 24061–0111 Phone: 540--231--3777, Fax: 540--231--3362 [email protected] 2 Department of Computer Science, Virginia Tech Blacksburg, VA 24061–0106 Phone: 540--231--5723, Fax: 540--231--6075 [email protected]

Abstract. We present Palette, a reusable specification language for realtime control systems. Palette is a meta-language that is programming language independent and has generic, reusable functional abstractions that can be customized to construct a real-time system in a given context. The abstractions allow modeling of the interactions of the system with its physical environment, including the specification of data and event stream properties, and allow expression of quality of service (QoS) requirements such as timeliness and survivability. Palette supports mechanisms that allow construction of new abstractions from existing ones. The set of reusable, domain specific abstractions provided by the language thus serves as an implementation vehicle for constructing new real-time control systems—promoting reuse-in-the-large—or enhance existing systems within the domain by reusing individual components—promoting reuse-in-the-small. Further, the abstractions of the language support underlying mechanisms for ensuring QoS requirements are achieved. This promotes reuse of QoS management solutions, techniques, and infrastructures. Keywords: software reuse, domain-specific architectures, real-time systems, computer-based control systems, command and control, middleware

1

Introduction

Real-time control systems, including those supporting command and control tasks, often tax the abilities of software engineers and developers. The requirements for such systems often combine complex behavioral expectations with realtime deadlines, while simultaneously imposing non-functional requirements for quality, reliability, and graceful degradation when operating limits are exceeded. At the same time, formal specification techniques aimed at general purpose computing tasks lack the ability to capture such requirements. W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 20–40, 2000. c Springer-Verlag Berlin Heidelberg 2000


Palette: A Reuse-Oriented Specification Language for Real-Time Systems

21

To address this problem, we present Palette, a specification language designed to allow the description of real-time system properties and quality of service (QoS) requirements. Palette builds on previous work in behavioral specification and in providing language support for reuse practices, while adding new capabilities that specifically address the needs of the real-time control systems domain. The result is a domain-specific specification language that provides built-in support for key domain-specific abstractions. Systems specified using Palette may be realized in any programming language, and the specification information can also be used by QoS management middleware to ensure conformance to certain non-functional requirements. The remainder of the paper is organized as follows: Section 2 describes the domain of interest and presents a generic model of real-time control systems. The model is used to reason about real-time control systems, their important functions, and their non-functional requirements such as timeliness and survivability. Next, Section 3 presents Palette, including both the core abstractions of the language and intermediate representations that are constructed from the language specifications. Section 4 presents an application of Palette: interfacing with a resource management middleware system. We compare the features of Palette with that of related efforts in Section 5 and summarize conclusions in Section 6.

2

Background

Palette is targeted at the unique problems associated with specifying real-time control systems. In this section, we describe the general nature of such systems and present a simple model of real-time control systems that serves as a basis for discussing the features of Palette. 2.1

Real-Time Command and Control

A computer-based, real-time, command and control (C2) system performs actions in response to conditions detected in its environment. Such a system typically consists of sensors that monitor external conditions, software that filters, correlates and evaluates the sensor data, and actuators that affect the environment. Events detected by the evaluation component of a control system initiate planning activities that lead to responses via actuators, as well as monitoring activities that guide the actions to successful completion. The processing performed by a control system depends on the environment in several ways. The load of the sensing function at any point in time depends on the number of environmental elements detected by the sensors. The loads of the initiation and monitoring functions depend on the rate at which environmental events occur. Thus, the characteristics of a control system’s environment are important engineering considerations. The environmental events interacting with a real-time control system can be characterized as deterministic, stochastic, or dynamic. A deterministic environment is one in which properties of the data stream that is collected by

22

Binoy Ravindran and Stephen Edwards

the system is completely predictable. As a result, the rate at which events that cause initiation of actions by the system are generated—both internally and externally—is also completely predictable. Real-time systems may also function in stochastic environments where the data and event stream characteristics may follow statistical distribution patterns. Stream properties of such environments can be determined using probability distribution functions. Control systems may also operate in dynamic environments where the data and event stream characteristics cannot be characterized either deterministically or stochastically. In addition, real-time C2 systems are typically subject to non-functional requirements, including timeliness and survivability constraints. Timeliness requirements include simple deadlines that are expressed on the duration of a single execution cycle of functions and super-period deadlines that are expressed on collections of cycles. Survivability requirements define redundancy levels of application software; survivability schemes for meeting such requirements might include load sharing, use of stateless components, peer replicas and primarysecondary replicas, and hardware clusters that exhibit fault-tolerant properties. The application software and devices such as sensors and actuators that constitute the control system vary from application to application. Systems may be uniprocessor-based or may be distributed across processors and networks. Some applications may be capable of exploiting concurrency by dynamically adding, replicating, or removing subsystems to accommodate workload changes. Dynamic load balancing strategies can be important for meeting timeliness requirements under changing workloads, while also providing a natural scaling plan as environmental events become more numerous and more frequent. Finally, applications may be developed by multiple teams, possibly using multiple programming paradigms and programming languages. Real-time system engineers often must produce computer-based control systems that have stringent timeliness and survivability requirements. Designing the system using techniques that allow the system to achieve the desired nonfunctional requirements is a crucial part of the engineering process. Unfortunately, “reinventing the wheel” is pervasive in this arena. This is due to the absence of mechanisms that allow the construction of new systems from existing ones, as well as design approaches that “glue” techniques that achieve the nonfunctional requirements of the system onto existing designs in an ad hoc manner. Hence, there is a pressing need for a mechanism—an architectural framework— that is a vehicle for constructing real-time systems by reusing implementations that exist within the domain, and one that facilitates achieving its non-functional requirements. 2.2

A General Model of Real-Time Control Systems

Figure 1 shows a generic real-time control system. The control system consists of functions that perform assessment of the environment, initiation of actions, and monitoring and guidance of the actions to their successful completion. The interrelationship of the functions with the environment and the intra-relationship of the functions among themselves are illustrated in Figure 1.

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

23

data stream

data stream

Sensor

Sensor

data

Operating Environment

Assessment task

action

Real-Time System event

Initiation task

Actuator

event

data

Guidance task

Actuator

control of action

Fig. 1. A Generic Real-Time Control System

Assessment entails repeatedly collecting data from the environment through hardware sensing devices. The data is filtered, correlated, classified, and then used to determine the necessity for action by the system. The assessment function has a continuous (or periodic) behavior since the data collection and assessment are performed repeatedly throughout the operational life of the system. Typically, there is a temporal bound associated with the completion of each execution cycle of the function, i.e., a bound on the time taken to review each of the elements of the data stream once. When an action is necessary, the assessment function generates an event that activates the initiation function. The initiation function determines the action that needs to be taken and causes actuators to perform the action. Since the function executes in response to an event that may occur at any time, the initiation function has a transient behavior. The initiation function has, typically, a maximum latency requirement on its execution time, i.e., a latency requirement on the time to process a single event. Once an action is initiated, the guidance function is notified. The guidance function uses sensors to collect data, monitor initiated actions, and guide the actuators to successful completion of the actions. Since the guidance function can begin or terminate at any time, the function is transient. Further, the function behaves like an assessment function once it is active, executing in a continuous manner. Hence, the guidance function has a quasi-continuous behavior. Observe that each (transient) activation of the function consists of a set of execution cycles. Guidance functions typically have two temporal bounds: (1) completion time for one cycle and (2) de-activation time (i.e., an activation

24

Binoy Ravindran and Stephen Edwards

deadline). Typically, it is more critical to perform the required processing before the activation deadline than it is to meet the completion time for each cycle. After a careful study of the domain of real-time C2 systems, we have observed that the resource needs of the system functions—characterized in terms of their execution times—are significantly influenced by the size of the data and the event streams [42]. Size of the data stream refers to the number of data items that the assessment and guidance functions have to process during a single cycle, and size of the event stream refers to the arrival rate of events that trigger the execution of the initiation and guidance functions. We classify the operating environment of real-time control systems as deterministic, stochastic, or dynamic, based on the characterization of data and event stream properties. Deterministic systems are those where stream properties can be defined statically in terms of single discrete values. Stochastic systems are those where the stream properties can be modeled using probability distribution functions. Dynamic systems are those where an a-priori characterization of the stream properties is impossible [42]. The generic model of real-time control systems presented here does not capture their distributed nature, however. Often, both voluntary and involuntary forces push such a system to be physically distributed. The most common involuntary motivation for distribution is that the assets of the application (e.g., the different processing stages of a manufacturing plant, radars and missile launching devices of a combat system, the ships and aircraft of a battle group) are inherently dispersed [5]. Furthermore, response time requirements of individual components in such systems often cannot be met with a centralized computing facility. A primary voluntary reason for physical distribution is survivability, in the sense of continued availability with degradation of functionality or performance. Often, it may be more cost-effective to distribute a combat system than it is to implement a centralized system that becomes a single point of failure. Thus, each of the assessment, initiation, and guidance functions of the control system can consist of sensors, actuators, and a collection of application programs that use computing resources that are geographically distributed. The constituent sensor, actuator, and application program elements of the functions may cooperate and perform the respective assessment, initiation, and guidance functions. Survivability requirements of the system typically include recovery of the system from operational failure of resources, thus providing continuous availability of the functions performed by the system. Survivability is usually achieved by replication of system functions, resulting in primary and secondary copies that use hardware resources that belong to different hardware clusters that exhibit fault-tolerant properties. Detection of failures of primary copies, selection of new primaries, and switch-over to new primaries are functions that must be performed by survivability strategies.

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

3

25

Palette: A Reusable Specification Language for Real-Time C2 Systems

In response to the need for an architecture that allows for the construction of real-time systems by reusing existing components as well reusing techniques that achieve their timeliness and survivability requirements, we present Palette, a reusable specification language for real-time systems. Palette allows for specifying, reasoning about, and constructing real-time systems. The language provides generic, reusable abstractions to describe functions that computer-based, realtime control systems perform, and on which requirements such as timeliness and survivability are usually expressed. In this section, we present the core abstractions of Palette through an example specification and describe a language independent intermediate representation (IR) that can be constructed from its abstractions. Palette is based on an analysis of the real-time C2 systems domain [39]. This prior work includes a study of computer-based, C2 systems that operate in dynamic and hostile environments, their timeliness and survivability requirements, a strategic plan for the emerging generation of such systems, and future technology directions. The work has resulted in a domain model—the path-based paradigm—that captures the essential commonalities and differences among C2 systems in terms of features, capabilities, functions, and requirements [29]. Further, this prior work has also resulted in a specification language— the DeSiDeRaT a (Dynamic, Scalable, Dependable, Real-Time system) specification language—which allows one to specify and reason about distributed real-time systems that operate in dynamic environments [38]. However, the DeSiDeRaT a language does not provide any generic abstractions, or allow customization of abstractions to create new systems from existing ones to promote reusability. Palette is a programming language independent meta-language that supports the description of the non-functional requirements of real-time control systems. These requirements are defined in terms of end-to-end paths through application programs and devices such as sensors and actuators. Paths are convenient functional abstractions for expressing end-to-end QoS objectives in this domain. For example, each of the assessment, initiation, and guidance functions of real-time control systems discussed in Section 2.2 can be implemented as a collection of devices and application programs that cooperate and perform the assessment, initiation, and guidance functions, respectively. Thus, the three functions can constitute three paths in the system. Real-time and survivability requirements of the functions can therefore be expressed as end-to-end QoS requirements on the respective paths. Palette supports two types of paths based on their temporal properties: periodic paths and transient paths. A periodic path executes in a repetitive manner throughout the life of the system, while a transient path executes sporadically and has an ephemeral life. Hybrid transient-periodic paths that have periodic behavior over a transient lifetime can be constructed from periodic and transient paths through inheritance. Abstractions for describing environmentally

26

Binoy Ravindran and Stephen Edwards

dependent properties of paths, such as data and event stream characteristics, are also available. Palette provides constructs for expressing timeliness requirements such as simple deadlines and super-period deadlines (that apply to transientperiodic computations). Abstractions for describing survivability requirements of paths, such as scalability and fault-tolerance, are also supported. Thus, paths that are generic functional abstractions can be instantiated with their stream, QoS (timeliness and survivability), and scalability properties to define and construct a particular real-time system. 3.1

Reusable Abstractions in Palette

To illustrate the generic, reusable abstractions of Palette, we present a sample specification for a real-time control system. For brevity, we only illustrate the specification of a subsystem and it’s QoS objectives. We focus on the core language abstractions that describe the application software within a single subsystem. We present the specifications in a bottom-up manner, defining the basic, low-level atomic instances first, and later describing instances that are composed with the low-level atomic instances.

Application FM { Survivable YES; Scalable Application Filter { Survivable YES; Scalable Application EDM { Survivable YES; Scalable Application ED { Survivable YES; Scalable Device SensorAD, ActuatorAD;

NO;

Combining NO; Splitting EQUAL; }

YES; Combining NO; Splitting NO; NO;

}

Combining NO; Splitting EQUAL; }

YES; Combining NO; Splitting NO;

}

Elements {(SensorAD, FM) (FM, Filter) (Filter, EDM) (EDM, ED)} SensingPathElements;

Fig. 2. Defining components of a path

Figure 2 shows the definition of component elements for a path in a real-time system. Component elements of a path include application programs and devices such as sensors and actuators. Application programs and devices are described using the Application and Device abstractions, respectively. Specification of an application program involves defining boolean properties that indicate whether the application (1) can be replicated for survivability (Survivable) and (2) can support scalability (Scalable). An application is said to be survivable if it can be replicated and the replicas can be maintained in hardware clusters that exhibit different failure properties such as low probabilities for the simultaneous failure of the clusters. An application is said to be scalable if it can be replicated

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

27

to adapt to changes in data and event stream sizes. Note that a survivable application may or may not be scalable and a scalable application may or may not be managed for ensuring survivability. An application may combine its input stream, which may be received from difference predecessor applications and devices, and split its output stream for distribution to different successor applications and devices, as specified by the Combining and Splitting properties. Application attributes also include all information that is necessary to startup and shutdown the application (not described here). Path elements and their interconnectivities are described using the Elements abstraction, which allows the creation of an instance of elements that constitutes a path. Instantiation involves describing the application programs and devices that constitute the path as a sequence of ordered application and device name pairs within parentheses. The order defines the flow of data between elements.

RealTimeQoS { SimpleDeadline 4; InterProcessingTime 7; Throughput 200; MaxSlack 80, MinSlack 20, MonitorWindowSize 20, Violations 15 } SensingPathRTQoS; SurvivabilityQoS { Survivable YES, MinCopies 3, Scheme LoadSharingReplicas } SensingPathSuQoS; QoS {SensingPathRTQoS, SensingPathSuQoS} SensingPathQoS;

Fig. 3. Defining QoS requirements of a path Figure 3 shows the definition of QoS requirements for a path. Real-time and survivability QoS are defined using RealTimeQoS and SurvivabilityQoS, respectively. Instances of such QoS definitions are then used to construct an instance of the QoS abstraction through parameterization. The RealTimeQoS abstraction captures the real-time QoS requirements for a path. A real-time QoS specification includes timing constraints: simple deadlines, inter-processing times, throughputs, and super-period deadlines. A simple deadline is defined as the maximum end-to-end path latency during one cycle of a continuous or quasi-continuous path, or during an activation of a transient path. Inter-processing time is defined as the maximum time that is allowed between the processing of a particular data element of a continuous or quasi-continuous path’s data stream in successive cycles. The throughput requirement is defined as the minimum number of data items that a continuous or quasi-continuous path must process during a unit period of time. A super-period deadline is de-

28

Binoy Ravindran and Stephen Edwards

fined as the maximum allowed latency for all cycles of a quasi-continuous path during a single activation. A super-period deadline (not shown in Figure 3) is specified as the name of a dynamically linked library procedure that is called dynamically to determine the estimated super-period deadline. The real-time QoS specification also includes items that relate to the dynamic monitoring of the constraint. These include a minimum and maximum slack value that must be maintained on the constraint at run-time, the size of a moving window of measured samples that should be observed, and the maximum tolerable number of violations within the window. The SurvivabilityQoS abstraction allows the creation of an instance of the survivability QoS requirements for a path. Survivability QoS specification includes a boolean property that indicates whether the path should be managed to ensure survivability, the minimum required level of redundancy, and the survivability strategy. Observe that replicating a path entails replicating all of the application programs that constitute the path. An instance of the SurvivabilityQoS abstraction together with a RealTimeQoS abstraction forms an instance of the QoS abstraction.

Stream {data, deterministic, 40} SensingStream; Stream {event, dynamic} InitiationStream; Stream {(data, stochastic, "exponential 0.5"), (event, dynamic)} GuidanceStream;

Fig. 4. Defining stream properties of paths

Figure 4 shows the instantiations of streams for three paths of a real-time system. Stream is a generic abstraction that can be used to construct stream instances of paths through specialization to describe data and event stream properties. The instantiation involves specifying the stream type (data or event) and characterizing its size or rate as deterministic, stochastic, or dynamic. The data stream size or event arrival rate of a deterministic stream is a constant (scalar or an interval). A stochastic stream has a data stream size or an event arrival rate that is characterized by a probability distribution function. The distribution is described as a string containing the name of a distribution and its parameters, or is described as the name of a data file containing a data set that characterizes the stream’s behavior (not shown in Figure 4). The data stream size or event arrival rate of a dynamic stream is not described in the specification, since it must be computed at run-time. Figure 5 defines three paths in a real-time system. Path is a generic abstraction that can be customized to represent the functions of a real-time control system. The parameters that can be used to specialize a path abstraction include stream properties, behavior types, priorities, importance, constituent elements, and QoS requirements. Observe that the instances that were constructed earlier to define stream characteristics, constituent elements, and QoS requirements—

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

29

using the respective abstractions—are used in the instantiation of paths. This allows the separation of definition of paths from that of their attributes, and the instances that define the attributes can be reused in multiple path definitions. The Behavior attribute defines the execution behavior of the path. The execution behavior of a path is continuous, transient, or quasi-continuous. The Priority of a path defines the statically known relative priority of the path. The Importance attribute, on the other hand, is a dynamically evaluated property that determines the significance of the path as a function of time. The attribute (a string) is interpreted as the name of a dynamically linked library procedure that must be passed arguments that include the priority and the current time, and returns an integer value representing the importance of the path.

Path { Stream SensingStream, Behavior Continuous, Priority 2, Importance "CalcImportSensing", Elements SensingPathElements, QoS SensingPathQoS } SensingPath; Path { Stream InitiationStream, Behavior Transient, Priority 3, Importance "CalcImportInitiation", Elements InitiationPathElements, QoS InitiationPathQoS } InitiationPath; Path { Stream GuidanceStream, Behavior (SensingPath.Behavior,InitiationPath.Behavior), Priority 4, Importance "CalcImportGuidance", Elements GuidancePathElements, QoS GuidancePathQoS } GuidancePath;

Fig. 5. Instantiation of paths Figure 5 also illustrates how a path with hybrid behavior can be defined. The behaviors of SensingPath and InitiationPath—that are continuous and transient, respectively—are used to define the hybrid transient-periodic behavior of the GuidancePath. 3.2

Programming Language-Independent Intermediate Representations

To reason about real-time systems and construct techniques for ensuring the QoS requirements described using Palette, intermediate representations (or IRs) can

30

Binoy Ravindran and Stephen Edwards

be constructed from the specifications. A static IR that can be easily constructed by a compiler is presented in Section 3.3. The static IR can be augmented with dynamically measured system performance characteristics to produce a dynamic IR. The dynamic IR characterizes the state of the system (e.g., utilization levels of resources) and can be used by system software (e.g., middleware) to reason about the system and available resources, allocate resources, and manage QoS. The dynamic IR is presented in Section 3.4. It is important to note that the static and dynamic attributes of the system captured in the IRs are those (and only those) that are useful for reasoning about the system and, more importantly, that facilitate mechanisms for ensuring the QoS requirements are met. Thus, our selection of attributes in the IRs is directly based on what is necessary and useful from the standpoint of QoS management. 3.3

Static Intermediate Representations

A software subsystem, SS, consists of a set of applications SS.A = {a1 , a2 , · · ·}, a set of devices (sensors and actuators) SS.D = {d1 , d2 , · · ·}, a communication graph for applications and devices G(SS) ∈ Γ ((SS.D ∪ SS.A) × (SS.D ∪ SS.A)), and a set of paths P = {P1 , P2 , P3 , · · ·}, where Γ denotes a power set. Each path Pi is represented as a type τ (Pi ) ∈ {c, qc, t} (where c, qc and t denote continuous, quasi-continuous, and transient, respectively), a set of applications Pi .A = {ai,1 , ai,2 , · · ·} (where Pi .A ⊆ SS.A), a set of devices Pi .D = {di,1 , di,2 , · · ·} (where Pi .D ⊆ SS.D), a communication graph G(Pi ) ∈ Γ ((Pi .D ∪ Pi .A) × (Pi .D ∪ Pi .A)) (where G(Pi ) ⊆ G(SS)), a data stream Pi .DS and an event stream Pi .ES. Pi .DS is defined only if τ (Pi ) ∈ {c, qc} and Pi .ES is defined only if τ (Pi ) ∈ {t, qc}. Each path may also have real-time QoS requirements such as a required latency of λREQ (Pi ) time units, a required throughput of θREQ (Pi ) data stream elements/time, and a required data inter-processing time of δREQ (Pi ) time units. To mask momentary spikes during QoS monitoring, we define a sampling window and a maximum acceptable number of QoS violations within the window. Similar definitions apply to each QoS parameter. For example, ω(λREQ (Pi )) is the sampling window size for latency and υ(λREQ (Pi )) is the maximum allowable number of QoS violations within ω(λREQ (Pi )). The IR also defines the desired slack interval for each QoS parameter. For the latency requirement, the minimum and maximum slack requirements of a path Pi , denoted as ψmin (λREQ (Pi )) and ψmax (λREQ (Pi )) percentages, reλ (Pi )−λOBS (Pi ,c) spectively, is defined such that ψmin (λREQ (Pi )) ≤ REQ λREQ × 100 ≤ (Pi ) ψmax (λREQ (Pi )) should always hold. The characteristics of data and event streams are also represented. The type of Pi ’s data stream is defined as τ (Pi .DS) ∈ {de, st, dy}, where de denotes deterministic, st denotes stochastic, and dy denotes dynamic. The size characteristics of Pi ’s data stream are denoted as σ(Pi .DS) which is a scalar or interval constant if τ (Pi .DS) = de, a distribution if τ (Pi .DS) = st, and undefined if τ (Pi .DS) = dy. Similarly, for an event stream, τ (Pi .ES) ∈ {de, st, dy} defines

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

31

its type, and ρ(Pi .ES) defines its event arrival rate. The event stream representation also includes a function, phi(Pi .ES), that determines the expected time of a deactivation event. Application features that are represented include the following: SCALE(ai,j ) is a boolean flag that indicates whether application ai,j can be replicated to adapt to changes in data and event stream sizes. COM BIN IN G(ai,j ) is a boolean flag that defines whether application ai,j combines the inputs from its successors before forwarding. SP LIT T IN G(ai,j ) ∈ {none, equal, non-equal} describes whether or not an application splits it outputs among its successors, and if it splits its outputs equally among its successors. 3.4

Dynamic Intermediate Representations

The dynamic features of the system that are represented include the size of data and event streams, the mapping of software to computation and communication hardware, and the number of replicas of each application. In modeling dynamic system properties, execution cycles of paths are used as reference points. For brevity, we omit abstractions representing dynamic performance metrics of hardware resources such as utilization levels. Details can be found in [40]. The set of replicas of application ai,j during cycle c of path Pi is defined as REP LICAS(ai,j , c) = ai,j,1 , ai,j,2 , · · ·. The host to which application ai,j,k is assigned during cycle c of Pi is defined as HOST (ai,j,k , c, Pi ), and the communication path (set of network links) used during cycle c of Pi for messages between applications ai,j,x and ai,j,y is represented as COM M P AT H(ai,j,x , ai,j,y , c, Pi ). The set Pi .DS(c) = Pi .DS(c)1 , Pi .DS(c)2 , · · · represents the set of elements in the data stream Pi .DS during cycle c of path Pi . The set Pi .DS(c, ai,j ) = Pi .DS(c, ai,j )1 , Pi .DS(c, ai,j )2 , · · · denotes the set of elements in the data stream processed by the application ai , j of path Pi during cycle c. The processing of elements of a data stream may be divided among replicas of an application to exploit concurrency as a means of decreasing the execution latency of a path. In successive stages of a path that has non-combining applications (i.e., applications that, after processing the data, simply divide the data among their successors), data will arrive in batches to applications. Hence, each application may process several batches of data during a single cycle. The set Pi .DS(c, ai,j , k) = Pi .DS(c, ai,j , k)1 , Pi .DS(c, ai,j , k)2 , · · · defines the set of data stream elements contained in the k th data stream batch processed by application ai,j of path Pi during cycle c. The total number of data batches processed by an application ai of path Pi during cycle c is defined as T otalBatches(ai , Pi , c) =
where ∀k:ak ∈MaxN odeRoute(Root(Pi ),ai ),Pi M AX(REP LICAS(ai , c) ∪ 1), M axN odeRoute(ai,j , ai,k , Pi ) =< a0 , a1 , a2 , · · · an > such that (1) ((ak−1 , ak ) ∈ Γ (Pi ), ∀k : 1 ≤ k ≤ n) and (2) (ai,j = a0 ∧ ai,k = an ) holds. Further, ROOT (Pi ) defines the root node of path Pi i.e., the only node of the path that does not have an incoming edge from any other nodes of the path.

32

Binoy Ravindran and Stephen Edwards

System Spec.

Specification of system characteristics in system description language

Compiler

Static IR Real-Time C2 System Application

dynamically measured performance data

Run-Time System

Dynamic IR

QoS management actions

Staic information of the system such as software and hardware compositions, stream properties and QoS requirements

Platform-independent resource abstractions

QoS Management Middleware

Fig. 6. Language interface with QoS techniques

4

Application of the Specification Language

To illustrate the use of the specification language and the intermediate representations, we describe QoS management techniques that deliver the desired QoS of real-time control systems. The techniques use the IRs that are constructed from the language specifications and augmented with dynamically instrumented performance data. The interface of the language implementation—compiler and run-time system—with QoS management middleware is illustrated in Figure 6. As part of our prior work, we have implemented the QoS management middleware. Details of the middleware can be found in [30]. The steps involved in the QoS management process are as follows: The realtime system components are monitored by the middleware for conformance to specified QoS requirements. QoS violations such as path latencies exceeding their slack values on deadlines are reported to diagnosis functions of the middleware

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

33

that identify the causes of poor QoS. Further analysis by the middleware identifies possible reallocation actions to improve the QoS, and selects the “best” set of these possible actions (e.g., identifying the optimal or sub-optimal bottleneck application program of the path to replicate). Resource allocation is performed by the middleware to determine the optimal or sub-optimal way to execute the selected actions (e.g., determining the optimal or sub-optimal host to execute an application replica). These QoS management steps are summarized in the following subsections. For brevity, we focus here on managing slack values on simple deadlines for periodic, continuous functions such as assessment. More complete details of the middleware algorithms, their implementation, and performance validation are available [28]. A complete implementation of the middleware is currently in the process of commercialization. 4.1

QoS Monitoring

Any algorithm that performs run-time QoS monitoring consumes resources and incurs overhead. We have implemented the middleware algorithms described here and have experimentally measured the run-time overhead [28]. The observed increase in path latency due to monitoring and management was less than 4% with very tight standard deviations for a number of experimental scenarios. Monitoring of real-time QoS involves collection of time stamped events that are sent from the application programs, and synthesis of the events into pathlevel QoS metrics. A time stamped event tag from an application includes the start and end times of processing the data elements and data batches by the application. The start and end times of processing data elements and data batches are defined as follows: s(Pi .DS(c, ai,j )k ) and e(Pi .DS(c, ai,j )k ) define the start time and end time of processing the k th data stream element by application ai,j during path cycle c. s(Pi .DS(c, ai,j , k)) and e(Pi .DS(c, ai,j , k)) define the start time and end time of processing the k th data stream batch by application ai,j during path cycle c. From these basic events, the observed real-time QoS metrics of path latency, throughput, and data inter-processing time are defined as follows: The observed latency of path Pi during cycle c is the maximum of the set of latencies that are incurred in processing each of the data batches. It is defined as λOBS (Pi , c) = M AX(e(Pi .DS(c, ai,m , j))−s(Pi .DS(c, Root(Pi ), 1))), ∀j : 1 ≤ j ≤ T otalBatches(Sink(Pi), c), ∀ai,m ∈ Replicas(Sink(Pi)), where Sink(Pi ) defines the sink node of path Pi i.e., the only node of the path that does not have an outgoing edge to any other nodes of the path. The observed throughi .DS(c)| put of path Pi during cycle c is defined as θOBS (Pi , c) = λ|POBS (Pi ,c) . The observed data-inter-processing time of path Pi during cycle c is δOBS (Pi , c) = f (s(Pi .DS(c, ai,j )k ) − s(Pi .DS(c − 1, ai,j )k )), ∀k, ∀ai,j , and for c > 1, where f (.) is an averaging function over all the inter-processing times. Analyzing a time series of real-time QoS metrics enables detection of QoS violations. Examples of QoS violations include the latency of the path exceeding its minimum slack value for a simple deadline (called a path overload ) or the latency of the path decreasing below its maximum slack value for a simple

34

Binoy Ravindran and Stephen Edwards

deadline (called a path underload ). An overload of a path occurs in any cycle c when the observed path latency violates the required latency in at least υ(λREQ (Pi )) out of the previous ω(λREQ (Pi )) cycles. That is, υ(λREQ (Pi )) ≤ λ (Pi )−λOBS (Pi ,d) < ψmin (λREQ (Pi )). Similarly, |{d : c − d < ω(λREQ (Pi )) ∧ REQ λREQ (Pi )×100 an underload of a path occurs in any cycle c when υ(λREQ (Pi )) ≤ |{d : c − d < λ (Pi )−λOBS (Pi ,d) ω(λREQ (Pi )) ∧ REQ > ψmax (λREQ (Pi )). λREQ (Pi )×100 4.2

QoS Diagnosis

When an end-to-end, path-level QoS violation such as a path overload or path underload occurs, QoS diagnosis is performed to determine the cause(s) of the violation. Here, we focus on QoS diagnosis for a path overload. The objective of diagnosis is to identify applications or replicas that are experiencing significant slowdown. The illustration here presents a technique to perform path local diagnosis, which considers only the applications in a path exhibiting poor QoS. The local QoS diagnosis technique compares current performance of an application to its best performance in the same application-to-host mapping and at the same data stream size. An application ai,j of path Pi is said to be unhealthy during a cycle c if there exists another cycle d such that the processing latencies are significantly worse for the data batches processed by ai,j during cycle c than the processing latencies for the batches processed by ai,j during cycle d, for the same data stream size and host resource. Further, during cycle d, ai,j exhibited its least latency over all cycles. That is, the application ai,j is said to be unhealthy if ∃d : (d < c) ∧ (HOST (ai,j , c, Pi ) = HOST (ai,j , d, Pi )) ∧ (|Pi .DS(c, ai,j )| = |Pi .DS(d, ai,j )|) ∧ (∀f : f < c ∧ HOST (ai,j , c, Pi ) = HOST (ai,j , f, Pi )∧ |Pi .DS(c, ai,j )| = |Pi .DS(f, ai,j )| ∧ λOBS (Pi , f ) > λOBS (Pi , d)∧ (λOBS (Pi , d) < λOBS (Pi , c) − 4), where 4 defines the minimal difference between cycle latencies that is considered significant. 4.3

Identifying Recovery Actions

QoS diagnosis functions produce a set of unhealthy applications as its output. The unhealthy applications are analyzed to identify recovery actions that will improve the QoS of the path. The first step of the analysis is to determine whether the data stream size of an unhealthy application has significantly increased in the recent past. This is determined from the abstraction in the dynamic IR that describes the data stream size processed by an application within the past α cycles, where α defines the size of a window of recent cycles. The data stream size of an application ai,j is said to have increased by at least a significant amount δ, when ∃d : c > d ∧ c − d < α ∧ (|Pi .DS(c, ai,j )| > |Pi .DS(d, ai,j )| + δ). The data stream analysis is used to determine the appropriate recovery action for an unhealthy application. An unhealthy application a is replicated when its data stream size has increased recently by a significant amount. An unhealthy application a is migrated from its current host when its data stream size has not increased recently but the load of its host resource has increased significantly.

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

35

We define the set A = {act1 , act2 , · · ·} as the set of actions selected, where acti is a pair (a, action) that denotes the action that is recommended for application a. Actions that address the same cause of poor path QoS are grouped together. A group of related actions is a set gi (., .) = {(a, action − a), (b, action − b), · · ·}. All actions that migrate applications (or replicas) from a particular host are grouped together, since any one of those actions will reduce the contention experienced by applications on the host. The group of all actions that migrate applications from a host hk to recover from poor QoS detected in cycle c is identified as gm (hk , c) = {acti = (ai , action) : action = ‘migrate’ ∧ HOST (ai , c, Pi ) = hk }. Actions that involve replication of a particular application ai is also grouped together, since the addition of another replica of ai will cause a redistribution of load processed by the existing replicas of ai . The group of all actions that involve replication of an application ai,j can be identified as follows: gr(ai,j , c) = {acti = (ai,j,k , action) : action = ‘replicate’ ∧ ai,j,k = REP LICAS(ai,j , c)}. 4.4

Resource Allocation

Once the recovery actions to improve QoS are determined, the next step is to allocate hardware resources—CPUs and networks—to actions. We summarize a heuristic algorithm that uses the dynamic IR to determine the hardware resources for the use of the replica of an application program or a migrant application program. Details of the algorithm can be found in [30]. The technique uses a fitness function that considers both host and network load indices. The algorithm uses trend values of load indices of hosts and networks over a (moving) set of sample values that is instrumented and represented in the dynamic IR. The trend values are determined as the slope of regression lines that plot the load index values as a function of time. A fitness value is determined for each of the hosts by the algorithm. The fitness value of a host is computed as a function of the load index value of the host, the load index value of the host network that has the least load among all networks of the host, a host weight, a network weight, a host load index weight, and a network load index weight. The host for an application replica or migrant application is determined as the host that has the minimum fitness value among all the eligible hosts of the application. Once the recovery actions and hardware resources are determined, they are enacted on the application to improve the delivered QoS.

5

Related Efforts

Palette is significantly different from other real-time languages, which can be divided into two groups: application development languages, and specification languages (or formalisms) used to describe timing constraints at the application or system level. Examples of application programming languages are Tomal [20], Pearl [24], Real-Time Euclid [21], RTC++ [16], Real-Time Concurrent C [7], Dicon [22], Chaos [3], Flex [23], TCEL [8], Ada95 [1], MPL [27], and CaRTSpec [41]. These languages include a wide variety of features that allow the

36

Binoy Ravindran and Stephen Edwards

compiler (and possibly the run-time system) to check assertions or even to transform code to ensure adherence to timing constraints. Specification languages or metalanguages, such as ACSR [4], GCSR [2,32], and RTL [17], formalize the expression of different types of timing constraints and in some cases allow proofs of program properties based on these constraints. In some cases, such as RTL, these features have been folded into an application development language [9]. Palette is a specification metalanguage that is independent of any particular application language. Rather than providing real-time support within a particular application language, it provides support for expressing timing constraints for families of application programs written in a wide variety of programming languages. Unlike previous work in which timing constraints are described at a relatively small granularity, such as at the individual task level, Palette allows timing constraints to be expressed at a larger granularity, i.e., to span multiple programs. Real-time languages also differ in the way they characterize a system’s interactions with its environment. Prior work has typically assumed that the effects of the environment on the system can be modeled deterministically. Palette expands this to include systems that interact with environments that are deterministic, stochastic, and dynamic. This is accomplished by modeling interactions through data and event streams that may have stochastic or dynamic properties. In order to handle dynamic environments, it is useful if the language includes features that can be related to dynamic mechanisms for monitoring, diagnosis and recovery [18,15,31,33]. Language support for run-time monitoring of real-time programs has been addressed in [9], [19], Real-Time Euclid [21], and Ada95 [1]. However, this prior work provides limited support for diagnosis and recovery actions. Palette extends the language features pertaining to diagnosis of timing problems, and to the migration or replication of software components to handle higher data stream or event stream loads (scalability). Previous real-time languages allow the description of behaviors that are purely periodic or aperiodic. Palette extends language support to describe hybrid behaviors such as the transient-periodic behaviors [35]. It also allow for dynamic multi-dimensional timing constraints—deadlines that are expressed on an aggregation of execution cycles of functions—that to our knowledge, cannot be described in any existing real-time language. Fault-tolerance is an issue that has not yet been addressed in many real-time languages. This is an important QoS objective of systems that operate in hostile environments, however. Palette addresses fault-tolerance by providing abstractions to describe minimum redundancy levels of software components, faulttolerance strategies, and hardware clusters that exhibit group failure modes. With respect to other specification approaches designed for supporting reuse, Palette builds on the parameterized programming approach to software composition. This approach was originally introduced by Goguen with OBJ [12,13], and has been successfully used in a number of other programming languages and specification languages, such as LILEANNA [36], Ada [14], Ada95 [10], Standard ML [26], and RESOLVE [34]. While each of these languages contains some lin-

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

37

guistic features supporting software reuse or parameterized programming, none are appropriate for use in specifying real-time systems and their QoS constraints in a programming language independent fashion. Palette also builds on some work with object-oriented languages, such as Eiffel [25], FOOPS [11], Ada95, and RESOLVE, that combine reuse-oriented language mechanisms with objectoriented features such as inheritance and dynamic binding. None of these languages combine the features necessary to support the three elements of design for reuse, object-oriented design, and real-time QoS specification, however. Further, no other language research effort has aimed to develop a set of reusable, parameterized abstractions that characterize the core behaviors shared by applications in the real-time control systems domain.

6

Conclusions

We have presented a domain specific specification language for the domain of real-time control systems. The core reusable abstraction of the language is the notion of a path—a functional abstraction that can be customized with environmental attributes including properties of data and event streams. The path abstraction is used to define the composition of control system functions in terms of application programs and devices, and to express their non-functional performance objectives. Further, the intermediate representations that are constructed from the language specifications can be used by path-based QoS management techniques. This promotes reuse of underlying techniques (e.g., QoS management strategies), since such techniques are tied to the reusable abstractions of the language itself. We have built a prototype compiler and a run-time system for the DeSiDeRaTa specification language. The language was used to specify the Anti-Air Warfare surface combatant system of the U.S. Navy and to ensure that its QoS requirements were met through the use of a resource management middleware system. Furthermore, experimental characterizations of the middleware illustrated its effectiveness in ensuring the desired QoS requirements. The language and the middleware technology has been transitioned to the Navy [37,6]. Ongoing efforts include using Palette to construct the emerging generation of real-time surface combatants of the Navy by reusing existing components as well as QoS management strategies.

References 1. International Standard ANSI/ISO/IEC-8652:1995. Ada 95 Reference Manual. Intermetrics, Inc., January 1995. 35, 36 2. H. B-Abdallah, I. Lee, and J-Y. Choi. A graphical language with formal semantics for the specification and analysis of real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, pages 276–286, December 1995. 36 3. T. Bihari and P. Gopinath. Object-oriented real-time systems. IEEE Computer, 25(12):25–32, December 1992. 35

38

Binoy Ravindran and Stephen Edwards

4. J-Y. Choi, I. Lee, and H-L. Xie. The specification and schedulability analysis of real-time systems using ACSR. In Proceedings of the IEEE Real-Time Systems Symposium, pages 266–275, December 1995. 36 5. R.K Clark, E.D. Jensen, and F.D. Reynolds. An architectural overview of the Alpha real-time distributed kernel. In Proceedings of the USENIX Workshop on Microkernel and Other Kernel Architectures, Seattle, April 1992. 24 6. Quorum. Available at http://www.darpa.mil/ito/research/quorum/index.html, 1999. 37 7. N. Gehani and K. Ramamritham. Real-time concurrent C: A language for programming dynamic real-time systems. Journal of Real-Time Systems, 3(4):377– 405, December 1991. 35 8. R. Gerber and S. Hong. Semantics-based compiler transformations for enhanced schedulability. In Proceedings of the IEEE Real-Time Systems Symposium, pages 232–242, December 1993. 35 9. M. Gergeleit, J. Kaiser, and H. Streich. Checking timing constraints in distributed object-oriented programs. In Proceedings of the Object-Oriented Real-Time Systems (OORTS) Workshop, October 1995. Seventh IEEE Symposium on Parallel and Distributed Processing (SPDP). 36 10. D. S. Gibson. An introduction to RESOLVE/Ada95. Technical Report OSUCISRC-4/97-TR23, The Ohio State University, April 1997. 36 11. J. A. Goguen and J. Meseguer. Extensions and foundations of object-oriented programming. SIGPLAN Notices, 21(10):153–162, October 1986. 37 12. J. A. Goguen, J. Meseguer, and D. Plaisted. Programming with parameterized abstract objects in OBJ. In D. Ferrari, M. Bolognani, and J. Goguen, editors, Theory and Practice of Software Technology, pages 163–193. North-Holland, Amsterdam, The Netherlands, 1983. 36 13. Joseph A. Goguen. Principles of parameterized programming. In Ted J. Biggerstaff and Alan J. Perlis, editors, Software Reusability, Volume I: Concepts and Models, pages 159–225. ACM Press, New York, NY, 1989. 36 14. Joseph Hollingsworth. Software Component Design-for-Reuse: A Language Independent Discipline Applied to Ada. PhD thesis, Dept. of Computer and Information Science, The Ohio State University, Columbus, OH, 1992. 36 15. D. Hull, A. Shankar, K. Nahrstedt, and J. W. S. Liu. An end-to-end QoS model and management architecture. In Proceedings of the IEEE Workshop on Middleware for Distributed Real-Time Systems and Services, pages 82–89, December 1997. The 18th IEEE Real-Time Systems Symposium. 36 16. Y. Ishikawa, H. Tokuda, and C. M. Mercer. An object-oriented real-time programming language. IEEE Computer, 25(10):66–73, October 1992. 35 17. F. Jahanian and A. K.-L. Mok. Safety analysis of timing properties in real-time systems. IEEE Transactions on Software Engineering, 12(9):890–904, 1986. 36 18. F. Jahanian, R. Rajkumar, and S. Raju. Run-time monitoring of timing constraints in distributed real-time systems. Journal of Real-Time Systems, 1994. 36 19. K. B. Kenny and K. J. Lin. Building flexible real-time systems using the Flex language. IEEE Computer, pages 70–78, May 1991. 36 20. R. B. Kieburtz and J. L. Hennessy. TOMAL—a high-level programming language for microprocessor process control applications. ACM SIGPLAN Notices, pages 127–134, April 1976. 35 21. E. Kligerman and A. D. Stoyenko. Real-Time Euclid: A language for reliable real-time systems. IEEE Transactions on Software Engineering, 12(9):941–949, September 1986. 35, 36

Palette: A Reuse-Oriented Specification Language for Real-Time Systems

39

22. I. Lee and V. Gehlot. Language constructs for distributed real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, December 1985. 35 23. K. J. Lin and S. Natarajan. Expressing and maintaining timing constraints in FLEX. In Proceedings of the 9th IEEE Real-Time Systems Symposium, pages 96– 105, December 1988. 35 24. T. Martin. Real-time programming language PEARL—concept and characteristics. In Proceedings of the IEEE Computer Society Second International Computer Software and Applications Conference (COMPSAC), pages 301–306, 1978. 35 25. Bertrand Meyer. Object-Oriented Software Construction, 2nd Ed. Prentice Hall, New York, NY, 1997. 37 26. Robin Milner, Mads Tofte, and Robert Harper. The Definition of Standard ML. MIT Press, Cambridge, MA, 1990. 36 27. V. M. Nirkhe, S. K. Tripathi, and A. K. Agrawala. Language support for the maruti real-time system. In Proceedings of the 11th IEEE Real-Time Systems Symposium, pages 257–266, 1990. 35 28. B. Ravindran. Modeling and Analysis of Complex, Dynamic Real-Time Systems. PhD thesis, The University of Texas at Arlington, August 1998. 33 29. B. Ravindran, L. R. Welch, and C. Kelling. Building distributed, scalable, dependable real-time systems. In Proceedings of the Tenth IEEE International Conference on Engineering of Computer Based Systems, pages 452–459, March 1997. 25 30. B. Ravindran, L. R. Welch, and B. Shirazi. Resource management middleware for dynamic, dependable real-time systems. Journal of Real-Time Systems, to appear 1999. 32, 35 31. D. Rosu, K. Schwan, S. Yalamanchili, and R. Jha. On adaptive resource allocation for complex real-time applications. In Proceedings of the 18th IEEE Real-Time Systems Symposium, pages 320–329, December 1997. 36 32. A. Shaw. Reasoning about time in higher-level language software. IEEE Transactions on Software Engineering, 15(7):875–889, July 1989. 36 33. K. G. Shin and C.-J. Hou. Design and evaluation of effective load sharing in distributed real-time systems. IEEE Transactions on Parallel and Distributed Systems, 5(7):704–719, July 1994. 36 34. M. Sitaraman and eds. Bruce W. Weide. Special feature: Component-based software using RESOLVE. ACM SIGSOFT Software Engineering Notes, 19(4):21–67, October 1994. 36 35. S. Sommer and J. Potter. Operating system extensions for dynamic real-time applications. In Proceedings of the IEEE Real-Time Systems Symposium, pages 45–50, December 1996. 36 36. William Tracz. Formal Specification of Parameterized Programs in LILEANNA. PhD thesis, Dept. of Electrical Engineering, Stanford University, Stanford, CA, 1997. 36 37. High performance distributed computing (HiPer-D). Available at http://www.nswc.navy.mil/hiperd/index.shtml. 37 38. L. Welch, B. Ravindran, B. Shirazi, and C. Bruggeman. Specification and modeling of dynamic, distributed real-time systems. In Proceedings of the 19th IEEE RealTime Systems Symposium, December 1998. To appear. 25 39. L. R. Welch, B. Ravindran, R. D. Harrison, L. Madden, M. W. Masters, and W. Mills. Challenges in engineering distributed shipboard control systems. In Proceedings of the Work-In-Progress Session, December 1996. The 17th IEEE Real-Time Systems Symposium. 25

40

Binoy Ravindran and Stephen Edwards

40. L. R. Welch, B. A. Shirazi, B. Ravindran, and F. Kamangar. Instrumentation, modeling and analysis of dynamic, distributed real-time systems. International Journal of Parallel and Distributed Systems and Networks, 2(3):105–117, 1999. 31 41. L. R. Welch, A. D. Stoyenko, and T. J. Marlowe. Response time prediction for distributed periodic processes specified in CaRT-Spec. Control Engineering Practice, 3(5):651–664, May 1995. 35 42. L. R. Welch, P. V. Werme, L. A. Fontenot, M. W. Masters, B. A. Shirazi, B. Ravindran, and D. W. Mills. Adaptive QoS and resource management using a posteriori workload characterizations. In The Fifth IEEE Real-Time Technology and Applications Symposium, June 1999. 24

From Application Domains to Executable Domains: ∗ Achieving Reuse with a Domain Network Ulf Bergmann1 + and Julio Cesar Sampaio do Prado Leite2 1

Departamento de Engenharia de Sistemas – Instituto Militar de Engenharia Praça General Tibúrcio 80 - Rio de Janeiro, 22290-240, Brasil 2 Departamento de Informática - Pontifícia Universidade Católica do Rio de Janeiro Rua Marquês de São Vicente, 225 Rio de Janeiro, 22453-900, Brasil {bergmann,julio}@inf.puc-rio.br

Abstract. Software generators are among the most effective methods for achieving software reuse. Describing an application using a domain specific language and then performing a single refinement step to an executable language is the approach used by most generators. This paper shows how to use the Domain Network (DN) concept, a set of interconnected domains, as a way to improve reuse in the context of software generation.

1

Introduction

We have been using Neighbor’s Domain Network (DN) idea [1] in our work with the transformation engine Draco-PUC[2]. We believe that DN allows more effective reuse than that provided by usual software generators. A Domain Network is a set of domains interconnected by transformations. Each domain encapsulates the knowledge of a specific area and is described by a domain specific language (DSL). Transformations are constructed to allow a program written in a source DSL to be implemented by a different DSL. The use of DN in software generation has two main advantages. First, while a usual software generator uses a single refinement step, a DN based generator provides a more effective reuse by using several refinement steps. Second, we don't need to implement a new DSL from scratch because we create the transformations to other domains that are represented as DSLs. This paper describes how we have used the concept of domain network, a core concept in the Draco paradigm [1]. In Section 2 we briefly present an overview of the paradigm and of the Draco-PUC Machine. In Section 3 we describe the domain network we have been using with focus on the partial DN used in the generation of ∗

This work has been partially supported by CNPq and by the Pronex Project of Ministério da Ciência e Tecnologia + This work was performed while this author was a Ph.D. student at Pontifícia Universidade Católica do Rio de Janeiro W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 41-57, 2000.  Springer-Verlag Berlin Heidelberg 2000

42

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

reverse engineering tools described in Section 4 and an example of its use described in Section 5. We conclude by comparing our results with the literature and suggesting future work.

2

The Draco Paradigm

The Draco paradigm may be seen and characterized by several viewpoints [3]. The original motivation for its development was to provide a way of building software from pre-existing components. It may also be seen as a generator, being able to build and maintain a class of similar systems. A third viewpoint is that of high level domain languages to be used in the systems construction process supported by a transformation mechanism capable of generating executable programs from a given DSL specification. What is behind these is a way of organizing components for reuse that is different from the approaches based on libraries. In the Draco paradigm, the reuse elements are the formal languages named domains. These languages are built with the objective of encapsulating objects and operations of a given domain. The programs written in the domain languages need a refinement process to reach an executable language. In order to build software from the point of view of the Draco paradigm, it is first necessary that the domain knowledge be formalized, with well-defined syntax and semantics. Once these domain languages are available, it is possible to achieve reuse at the domain level of abstraction. Clearly, the paradigm has a very high initial cost, but on the other hand it will lower, considerably, the cost of writing software in a domain that has been characterized by a domain language. The paradigm pays off when a domain will be reused several times. The Draco-PUC machine, on the other hand, is a software system that aims to implement the paradigm. The role of the machine is to construct domains described by their specific languages. A domain must contain syntax and semantics. Draco-PUC is composed of: a powerful general parser generator, a prettyprinter generator and a transformation engine. Transformations can be intra domain (horizontal) or inter domain (vertical). The semantics of a domain are expressed by inter domain transformations. The executable domains (like C) do not need reduction semantics since there is already an available compiler/interpreter. Figure 1 shows an example of the domain construction in Draco-PUC. To create the lexical and syntactic specifications we use a Draco domain called GRM (grammar domain). This domain uses an extended BNF. Embedding commands from the Draco domain PPD (prettyprinter domain) in the syntactic specification provide the prettyprinter specification. The file cobol.grm in Figure 1 shows a partial implementation for the Cobol domain. The semantics for the domain are specified by transformations to other domains. These transformations are described using the Draco domain TFM (transformation domain). Basically, a transformation has a recognition pattern (the lhs) and a replacement pattern (the rhs): when the lhs matches any part of the original program it is replaced by the rhs. The file cobol2c.tfm shows an example of the Cobol to C transformation.

From Application Domains to Executable Domains

cobol.grm

cobol2c.tfm

/* . . . */ paragraph : label '.' .NL stat**'.' .( , , .NL , ) end_par ; end_par : 'end' .sp label '.' | ; label : ID | INT ; stat : perform_stat | conditional_stat | atomic_stat | copy_file ; /* . . . */ ID : [a-zA-Z0-9][a-zA-Z0-9]* ; INT : [0-9]* ; Lexical / Syntactic Specifications Parser Generator

43

TRANSFORM GoTo LHS: {{dast cobol.statement /* recognition pattern * / GO TO [[ID L1]] }} POST-MATCH: {{dast cpp.stmt_list /* Post-Match control point */ COPY_LEAF_VALUE_TO(str1,"L1"); FixName(str1); SET_LEAF_VALUE("LABEL",str1); }} RHS: {{dast cpp.dstatement goto [[IDENTIFIER LABEL]]; /* replacement pattern */ }}

DAST- Sintax Mappings

Semantic specification

prettyprinter generator

Transformer generator

Draco-Puc

Cobol Domain

Cobol2C Transformer

1) In lhs, ID is an identifier from Cobol grammar 2) In rhs, IDENTIFIER is an identifier from C++ grammar

Domain Construction

Fig. 1. Domain Construction in Draco-PUC

Figure 2 shows the entire transformation structure. Before and after the usual matching sides of a production rule we have 5 possible control points. Pre-Match is activated each time the lhs is tested against the program. Match-Constraint is activated when there is a bind between a variable in lhs and a part of the program. Post-Match is activated after a successful match between the program and the lhs. Pre-Apply is activated immediately before the matched program section is substituted by the rhs. Post-Apply is activated after the program has been modified.

Fig. 2. Transformation Structure

44

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

Draco-Puc Use

!

parser

program pretty printer DAST1

DAST2

transformers

Fig. 3. Overview of Draco-PUC use

The Draco-PUC use is showed in Figure 3. The parser for the original program is used by Draco-PUC to convert the program in the internal form used in Draco-PUC (DAST – Draco abstract syntax tree). Transformations are applied to modify the DAST and, at any time, we can use the pretty-printer to unparse the DAST.

3

Domain Networks

The process by which a specification written in a library source domain reaches a target domain traverses several other domains. A set of domains that are linked together is called a domain network. This property distinguishes Draco-PUC from the usual generator generators, which typically uses a single refinement step. By reusing previous domain languages Draco uses a strategy of divide and conquer for building complex domains. Given this possibility we decide to build a network of domains to support the generation of applications, starting with a high-level domain language. We chose to avoid strategies like the one proposed in [4] where the software engineer needs to write the transformations, even though eventually reusing the ones available in the transformation library, we decide to build a network of domains to support the generation of applications, starting with a high level domain language. We have used the classification proposed by Neighbors [1], which divides domains as: • application domains – which express the semantics of real world domains or problem classes, • modeling domains – which are domains built to help the implementation of application domains, by encapsulating concepts with a broad range of reusability, and • executable domains – which are domains to which a generally accepted translator exists, as it is the case of well-known programming languages. We also add more one type, the Draco domains, which are used to specify the parser, prettyprinter and transformations used in Draco-PUC.

From Application Domains to Executable Domains Application Domain 1 2 3 4 5

prog.rdoo

Program tool source CPP; Extraction_Rules Begin module: dependence ; End

rdoo2exl

Transform IfMatch20 LHS: {{dast exl.if_match2 IF_MATCH [[dast pad]] DO [[tipo *tps]] [[statement *stmts]] END_IF }} POST-MATCH: {{dast cpp.ext_decl char s2tmp[200]; RawDASTLocater k; GET_VALUE("pad",k); createTransformationName(s2tmp , k); SET_LEAF_VALUE("NTFM",s2tmp); }} RHS: {{dast tfmdom.tfm TRANSFORM [[NAME NTFM]] LHS: [[dast pad]] POST-MATCH: {{dast lc.stmt_list [[statement *tps]] [[statement *stmts]] }} }}

exl2tfm

Set Of Transforms Ana Method Search: Bottom-Up Apply: Single Step Transform ExlTfm1 Lhs: {{ dast cpp.preprocessor #include [[_FILENAME FN]] }} Post-Match: {{dast lc.stmt_list COPY_LEAF_VALUE_TO(stmp,"FN"); strlwr(stmp); if (stmp[0]=='"') { stmp[strlen(stmp)-1]='\0'; strcpy(reg_moddep.nd,&stmp[1]); strcpy(reg_moddep.n,module_name); InsInTab(rel_moddep,(void*)reg_moddep); } }}

tfm2c

Draco Domain

void _export RegisterTransf( Transformer* c ) { SetOfTransforms* sot = new SetOfTransf; /* . . . */

DATA_DEFINITION SECTION TABLE moddep(nd,n) UNIQUE_INDEX ind1moddep(nd,n) INDEX ind2moddep(n) EXTRACTION SECTION PUBLIC BOTTON_UP_METHOD Ana IF_MATCH {{dast cpp.preprocessor #include [[_FILENAME FN]] }} DO GET_VAR FN AT stmp; strlwr(stmp); IF stmp[0]='"' THEN DO stmp[strlen(stmp)-1]='\0'; strcpy(moddep.nd,&stmp[1]); strcpy(moddep.n,module_name); INSERT_REG moddep; END_IF END_IF END_PROGRAM

Modeling Domain

exl2c #include<mbase.h> typedef relation *p_relation; typedef char *p_char; #include "erro.h" #include "contid.c" void append_file(char *d, char *s) { /* . . . */ } #define _ind_ind1moddep 0 #define _ind_ind2moddep 1 #include "moddep.h" relation *rel_moddep; moddep reg_moddep; moddep tst_moddep;

Executable Domain

45

Transform FindCppModule Lhs: {{dast rdoo.ext_rule module : [[single_property* pp]] ; }} Post-Match: {{ dast txt.decls TEMPLATE ("CreateModTable") PLACE_AT("WSTabDef"); END_TEMPLATE; APPLY("BuildCppModExt", "pp"); }} Set Of Transforms BuildCppModExt Trigger: external Method Apply: Single Step Transform ModuleDependence Lhs: {{dast rdoo.single_property dependence }} Post-Match: {{ dast txt.decls TEMPLATE ("CreateModDepTable") PLACE_AT("WSTabDef"); END_TEMPLATE; TEMPLATE ("CreateModDepTr") PLACE_AT("WSTransf"); END_TEMPLATE; SKIP_APPLY(); }} Template CreateModDepTable rhs: {{ dast exl.data_sec TABLE moddep(nd,n) UNIQUE_INDEX ind1moddep(nd,n) INDEX ind2moddep(n) }} Template CreateModDepTr rhs: {{ dast exl.if_match IF_MATCH {{dast cpp.preprocessor #include [[_FILENAME FN]] }} DO GET_VAR FN AT strAux; strlwr(strAux); IF strAux[0]='"' THEN DO stmp[strlen(strAux)-1]='\0'; strcpy(moddep.nd,&strAux[1]); strcpy(moddep.n,module_name); INSERT_REG moddep; END_IF END_IF }}

Transform INDICE2 LHS: {{dast exl.ind UNIQUE_INDEX [[ID IND]]([[ind_field *if]] ) }} POST-MATCH: {{dast cpp.statement_list char sind[100]; COPY_LEAF_VALUE_TO(sind,"IND"); sprintf(sind,"#define _ind_%s %d",sind,ind_count); TEMPLATE("DecInd"); SET_TEMPL_LEAF_VALUE("IND",sind); INSTANTIATE_TEMPLATE_AT(lcDec); END_TEMPLATE; ind_count++; }} TEMPLATE DecInd RHS: {{dast lc.ext_def [[MACRO IND]] }}

Fig. 4. A Partial View of a Domain Network and its Conections

A traditional domain network has as a starting point an application domain, and may involve several application domains and modeling domains in order to be grounded in an executable domain. Our use of Draco-PUC already produced many

46

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

executable domains and transformations between them [2][5]. Recently [6] we have just produced our first two modeling domains: EXL (Extraction Language) and MdL (Model Language) used to help in the extraction and visualization of source code information. Here, we report on two applications domains for design recovery (RDOO – Recover Design OO and RDS – Recover Design Structured). A partial example of the domain network use is presented in Figure 4. Starting with a program written in RDOO (prog.rdoo) and applying successive transformations we obtain a program that is described in the executable domain C. The first transformation (rdoo2exl) create the representation of the original program (application domain) in the modeling domain. The next three transformations (exl2tfm - tfm2c and exl2c) produce the representation in the executable domain C. Note that the knowledge about table manipulation and transformation structure is embedded in the modeling domain and can be reused in the construction of many applications domains.

TFM PPD GRM

Draco Domains

KB

EXL

RDOO MdL

SDL

Fusion

Cobol

Prolog

Pascal

Clipper

VBasic

MBase

Fortran

Estelle

C

Math

Java

Mondel

Http

Txt

C++

Transformations

RDS

DSF

Application Domains Modeling Domains

Executable Domains

Transformations

Fig. 5. Draco-PUC Domain Network

Figure 5 shows the actual domain network available in Draco-Puc Machine. The main domains are briefly described in Figure 6. In the next section we focus on the domain network used in the generation of Design Recovery Tools. Domain GRM TFM PPD RDOO RDS KB EXL MdL SDL Fusion C++, C, ..

Fig. 6. Main Domains

Description Describe the Lexical and Syntactic from the domain language Specify transformations Specify the prettyprinter Recover Design from OO Systems Recover Design from Structured Systems Manipulate a Knowledge Base Specify source code extractions Specify the visualization of information extracted from source code Define a Graphics User Interface Describe models from the Fusion Method [9] Programming Languages

From Application Domains to Executable Domains

47

4 A Domain Network for the Generation of Design Recovery Tools To be able to generate reverse engineering tools we have been using the domain network shown in Figure 7. It consists of two application domains where the source code for design recovery is described. These domains encapsulate the necessary knowledge for recovering the design from structured (RDS) and from object oriented systems (RDOO). Starting with the original source code in RDS or RDOO and applying the transformations shown in Figure 7, we obtain the target code that will perform the design recovery from the original source files. These codes are written in the domains: • TFM: is an intermediate domain (Draco domain) that describes the extraction transformations used to populate the database with the information specified in the original source code. In order to be used by Draco-PUC, this code is transformed to C. • C: contains two kinds of code: the one to export information from the database to files that can be read by the viewer (VG files) and the extraction transformations previously described in TFM. • Mbase: contains the MetalBase [10] scheme that is used to construct the tables needed to storage the extraction information. • C++: contains the code used to visualize the information extracted in a particular style. RDS

Application Domains

RDOO

DSF rde2exl TFM

Exl2tfm tfm2c

rdoo2exl EXL

Modeling Domains

MdL

Exl2c

mdl2cpp

GRM Draco Domains

C

MBase Schema

Cobol

C++

Java

Executable Domains

Fig. 7. Domain Network for the generation of reverse engineering tools

Figure 8 shows an example of how the generated code is used to extract information from source files. The file ext.tfm, that contains the extractions specified by one of the applications domains (RDOO or RDS) and translated to TFM, is used by Draco-PUC to search the syntax tree for the source files and populate the database. The database tables have been defined by the Mbase scheme generated by exl2c transformation (Figure 7). Then the filter, specified in EXL and translated to C, exports partial information to files that can be read by the viewer. The files booch.cpp

48

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

and jsd.cpp specify the style used to show the information to the user. These files are created by a transformation from MdL to C++.

ext.tfm

!!

Source Files

Viewer booch.cpp jsd.cpp

Extraction Draco-Puc

! ! vg files

Extraction DataBase

Filter filter.c

Fig. 8. Information extraction example

By using a domain network to generate these kind of tools, we obtain a high-level reuse each time a transformation is applied: from RDS or RDOO to EXL (by rdoo2exl or rds2exl transformations), we reuse the transformation, database and programming language syntax knowledge; from EXL to TFM (by exl2tfm transformation) we reuse transformation syntax and the database manipulation language; from EXL to C (by exl2c transformation) we reuse the database manipulation used to create filters; from MdL to C++ (by mdal2cpp transformation) we reuse the view structure and manipulation.

4.1 Application Domains The two application domains encapsulate the knowledge about information extraction from source files, one for structured languages and the other for object-oriented languages. They are used to specify what kind of information is to be extracted from source files in a particular class of programming language. Basically, these domains allow the user to specify an extraction at a very high level of abstraction using syntax description and database transactions. The extraction languages are examples of little languages [11], consequently, the languages for these domains are very small. By using these applications domains, the user does not need to specify extractions for all the features from source files. He/she can specify only the extractions needed for a particular problem. This is a very useful characteristic since it will generate a small extractions code, better performance in extraction and a small database. Follows an example of an extraction code in RDS for structured source code.

From Application Domains to Executable Domains

49

program Y2k Source Cobol; Extraction_Rules Begin module: name , dependence; method: name , call , variable_access; variable: name , type , struct; End This example shows extractions specifications for programs written in Cobol. What is to be extracted is specified in the extraction rules. In this case, the user wants to extract: modules names, dependences between modules, methods (paragraphs) names, static call graph, variables accessed by each method, variables names, variables type and the structure for each variable. The next example shows a program in RDOO for Java. Here we are interested in class names and the name, type and access type of each variable declared in a class. Program extractPartial source Java; Extraction_Rules Begin class: name, variable(name , access , type); End Figures 9 and 10 gives an idea of what kind of information can be extracted using RDOO and RDS. Property Type Module Name Dependence Class Name Dependence Inheritance Aggregation Association Method name Method access Method call Variable name Variable access Variable type

Description Module name Dependencies between modules (import , include , ...) Class name Module where the class is defined Superclass Aggregation between classes (when a class has a variable that is an instance from other class) Association between classes (when a class has a variable that is a pointer to another instance) Method name Method access (public, private, ...) Methods called statically Variable name Variable access (public, private, ...) Variable type

Fig. 9. Extraction in RDOO Property Module Variable

Method

Type Name Dependence Name Access Type Name Access Call

Fig. 10. Extraction in RDS

Description Module name Dependencies between modules (import , include , ...) Variable name Variable access (public, private, ...) Variable type Method name Method access (public, private, ...) Methods called statically

50

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

The programs in these domains are transformed to the equivalent program in the modeling domain EXL through the rdoo2exl or rds2exl transformations. These transformations are written in the transformation language (TFM domain) used by Draco-PUC.

4.2 Modeling Domains Extraction Domain (EXL). The domain EXL [6] provides an abstract language for defining transformations for information extraction, information storage in tables and the manipulation of this information. The EXL domain language has three sections: a data definition section, an extraction method definition section and an exportation section. The sections are interconnected. For instance, if we include a table record, automatically the semantics for inclusion will be updated in the extraction section and the semantics for reading will also change in the exportation section. The design of this language had a strong influence on fourth generation database management languages. For this reason it does contain high level commands such as FOR_EACH and EXIST. On the other hand, in the extraction section, EXL aims to simplify the extraction work by means of more appropriated commands for these tasks, see for instance the IF_MATCH command, An example of the extraction section follows that discovers the dependencies between C++ modules (source files). The result is stored in the MetalBase [10] database. EXTRACTION SECTION PUBLIC BOTTOM_UP_METHOD Analysis IF_MATCH {{dast cpp.preprocessor #include [[_FILENAME FN]] }} DO GET_VAR FN AT moddep.nomedependente; strcpy(moddep.nome,module_name); INSERT_REG moddep; END_IF This example shows an EXL code with a search method (PUBLIC BOTTOM_UP_METHOD Analysis) and a pattern matching command (IF_MATCH...DO… END_IF). The command recognizes the pattern in the C++ DAST (dast cpp.preprocessor) and copies the value of FN to the field nomedependente of the table moddep. The other field of this table, nome, is filled with the value of the global variable module_name that stores the current module name. After that, the current record is inserted in the table moddep asserting the existence of the dependence between the current module and the module specified in the include statement. EXL is not a code analyzer language [12][13], EXL programs will be able to transverse a DAST (representing the system to be recovered), find specific patterns and group them in a repository. The reverse engineer according to EXL syntax will specify the transverse strategy and the grouping.

From Application Domains to Executable Domains

51

Model Domain (MdL). The domain MdL helps in the construction of the recovered models. These models are composed of objects that can be nodes, edges and pages. A page contains the edges and nodes, and each edge has a source node and a destination node. Objects as we could see easily model the models, so that was the paradigm we choose to write the MdL domain. The MdL domain was written using a very useful characteristic of the Draco paradigm, that is to allow programs to be written mixing several languages. The MdL domain works together with the C++ domain, in which we write the methods of the MdL classes. In the MdL domain we describe the behavior of the three main objects, so the MdL domain was designed as a class definition language. In the following example we show the node “Sequential” of the JSD entity structure diagram [16]. NODE Sequential { METHOD: {{method_bodyCPP.function_definition.RC("vg.ctx") virtual void Draw(VGDC *dc) { float strw,strh; int strx,stry; dc->DrawRectangle(x, y,w,h); // not allow the node ext region be invalid dc->SetClippingRegion(x,y,w,h); // Calculates the title position dc->GetTextExtent(title,&strw,&strh); strx=x+(w-strw)/2; stry=y+(h-strh)/2; DrawText(dc,title, strx,stry); // Draws the special node character DrawText(dc,"*", x+w-13,y+1); dc->DestroyClippingRegion(); } }} }; In this example we describe the “Sequential” class that embodies the “Draw” method. The syntax for domain change appears after the word “METHOD:”, where there is an identification that there was a change from the domain MdL by the rule “method_body” to the CPP (C++) domain by the rule “function_definition” using the context file “vg.ctx”. The drawing method makes the rectangle, followed by the title and then by the indication of interaction or selection or sequence. The methods “SetClippingRegion” and “DestroyClippingRegion” take care of not drawing out of the established region. The great advantage of MdL is that the defined classes encapsulate completely the aspects of dynamic loading of models, characteristic not available in C++ and very important for our reverse engineering architecture.

52

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

5

Example

Our analysis of the literature on reverse engineering concludes there are four major aspects any reverse engineering tool must address. They are: how to extract information, how to store the information, how to visualize the information and how to selectively visualize parts of the recovered information. Based on that, Freitas and Leite [6] designed an approach to implement these requirements using a transformation tool to generate these kind of tools. Freitas and Leite [6] described all the necessary tool specifications using the modeling domains EXL and MdL. We extended this approach using the applications domains described in Section 4.1. Figure 11 shows the three main activities from our approach: Extraction, Visualization and the Execution. The Extraction is performed by creating two source files: one using the domain RDOO to specify the needed extractions and another using the domain EXL to describe a filter that will be applied to export a subset of the extraction information. By applying transformations on these files we obtain: a transformation file (.tfm file), that can be used to perform the extractions and populate the database; a file containing the MetalBase Scheme (.s file) that will be used to create the necessary database tables; and a C source file that select information from database and create several files (VG files) that can be read by the viewer. Draco-Puc RDOO Domain

rdtool.rds

EXL Domain

Draco-Puc

filter.exl

EXL Domain rdoo2exl Transformer

Extraction Building

rdtool.exl

rdtool.tfm

TFM Domain C Domain

MBase Scheme

exl2tfm Transformer exl2c Transformer

filter.c

Draco-Puc

!!

C++ Source

CPP Domain

rdtool Transformer

Extraction DataBase

filter.ex e

! ! vg files

VG (viewer)

Run

Draco-Puc mod.mdl cdg.mdl jsd.mdl

mod.cpp MDL Domain CPP Domain

mdl2cpp Transformer

Fig. 11. Overview of Recover Design C++ Tool

cdg.cpp jsd.cpp

Visualization Building

From Application Domains to Executable Domains

53

In the Visualization phase we use the MdL domain to specify the particular presentation style that will be used by the viewer. This phase produce the C++ source files that are used by the viewer. The Execution uses the results from the early phases to extract the information and show it to the user. We have used this approach to generate a tool to recover three types of information from the C++ code: the system structure, the relationships between objects and the internal structure of a class. For that we have used three well-known software engineering diagrams: the module diagram [14], the association diagram [15] and the entity structure diagram [16]. The generated tool was applied to recover design information of the same real system used in [6], a medium size system called wxWeb [17] that implements a HTML browser. This public domain browser has the major functionality of the wellknown Netscape and Internet Explorer, having features like mail and authentication. The system wxWeb is written in C++ and uses Internet technology. To recover the structure of wxWeb we wrote one extraction specification in RDOO, one filter specification in EXL and three specifications in MdL. The sizes for the originals, intermediates and finals files are showed in Figure 12. We started with 540 lines of code (original files) and ended up with 2280 lines of code (final files). Original File name size Rdtool.rdoo 10 Filter.exl Cdg.mdl Mod.mdl Jsd.mdl

170 120 120 120

Intermediate File name size Rdtool.exl 630

Final File name size Rdtool.tfm 980 Rdtool.s 50 Filter.c 430 Booch.cpp 250 Jsd.cpp 320 Mod.cpp 250

Fig. 12. File sizes (lines of code)

Figure 13 shows a partial example of a command described in RDOO and the correspondent commands in EXL and TFM generated by the transformations applied by Draco-PUC. The command in RDOO specifies that the information about module names and dependence must be extracted from C++ source files. The first transformation (rdoo2exl) produces a new file (rdtool.exl) that contains the definition of the tables where the information will be stored and the extraction transformation that looks for module dependence in C++ (#include ) source file and inserts this information in the tables. The next transformation (exl2tfm) produces a new file (rdtool.tfm) with the extraction transformations that are used by Draco-PUC to perform the extractions. The transformation exl2c creates the Mbase schema. Note that our program in RDOO is reusing the knowledge encapsulated by the EXL domain. Note that in RDOO we are reusing extraction knowledge that is transformed to EXL that in turn is reusing transformation and database knowledge. Comparing our approach with that used in [6], we have generated a very similar tool for design recovery, but using a more abstract specification, achieving the reuse of the EXL code encapsulated in the application domain.

54

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite Rdtool.tfm

Rdtool.rdoo

Program tool source CPP; Extraction_Rules Begin module: name , dependence ; class: name , inheritance , method(call , access), variable(name , type); End

rdoo2exl

Rdtool.exl DATA_DEFINITION SECTION TABLE modulo(nome) UNIQUE_INDEX ind1modulo(nome) TABLE moddep(nomedep,nome) UNIQUE_INDEX ind1moddep(nomedep,nome) INDEX ind2moddep(nome) EXTRACTION SECTION DECLARATIONS INITIALIZATIONS strcpy(modulo.nome,module_name); INSERT_REG modulo; PUBLIC BOTTON_UP_METHOD Analisys IF_MATCH {{dast cpp.preprocessor #include [[_FILENAME FN]] }} DO exl2tfm GET_VAR FN AT stmp; strlwr(stmp); IF stmp[0]='"' THEN DO stmp[strlen(stmp)-1]='\0'; strcpy(moddep.nomedep,&stmp[1]); strcpy(moddep.nome,module_name); INSERT_REG moddep; END_IF END_IF EXPORTATION SECTION BEGIN_PROGRAM END_PROGRAM

Global-Declaration: {{ dast lc.ext_def_list extern "C" { #include<mbase.h> } char module_name [200 ]; #define _ind_ind1modulo 0 extern "C" { #include "rels\modulo.h" } relation *rel_modulo; modulo reg_modulo; #define _ind_ind1moddep 0 #define _ind_ind2moddep 1 extern "C" { #include "rels\moddep.h" } relation *rel_moddep; moddep reg_moddep; }} Global-Initialization: {{ dast lc.stmt_list strcpy(module_name,GET_FIRST_MODULE_NAME()); strlwr(module_name); rel_modulo=mb_inc("rels\\modulo",""); rel_moddep=mb_inc("rels\\moddep",""); strcpy(reg_modulo.nome,module_name); InsertInTab(rel_modulo,(void*)®_modulo); }} Set Of Transforms Analisys Method Search: Bottom-Up Apply: Single Step Transform ExlTfm1 Lhs: {{dast cpp.preprocessor #include [[_FILENAME FN]] }} Post-Match: {{dast lc.stmt_list COPY_LEAF_VALUE_TO(stmp,"FN"); strlwr(stmp); if (stmp[0]=='"') { stmp[strlen(stmp)-1]='\0'; strcpy(reg_moddep.nomedep,&stmp[1]); strcpy(reg_moddep.nome,module_name); InsertInTab(rel_moddep,(void*)®_moddep); } SKIP_APPLY(); }}

tfm2c

rdoo2exl Rdtool.s relation modulo field nome type char * 100; index ind1modulo on nome without dups; typedef modulo; end relation moddep field nomedep type char * 100; field nome type char * 100; index ind1moddep on nomedep, nome without dups; index ind2moddep on nome ; typedef moddep; end

// . . . // . . .

Fig. 13. Transformations Example

We have also used the same approach to generate a tool to detect Y2K errors in Cobol source files. To do this, we wrote one extraction specification in RDS and one

From Application Domains to Executable Domains

55

error locator specification in EXL. The sizes for these sources, intermediate and final files are showed in Figure 14. We started with 448 lines of code (original files) and ended up with 1810 lines of code (final files). Original File name size Y2k.rds 8 Locerr.exl

440

Intermediate File name size Y2k.exl 620

Final File name size Y2k.tfm 1100 Y2k.s 50 LocErr.c 660

Fig. 14. File sizes (lines of code)

6

Conclusion

Comparing the use of domain networks with the software generators that add domainspecific extensions to industrial programming languages [18][19] we believe that our approach has several advantages. First, it simplifies the task of creating a DSL. We can create the necessary translation from a new DSL to an executable language through transformations to a set of intermediate domains that already have the translation to an executable language. Using intermediate domains we can describe the needed transformations in a more abstract level. Second, by using a DSL we have used the syntax from the application domain and not the one from the host language. If we observe how multiple refinement steps through the domain network occurs, then we will have an idea of how reuse is achieved. For instance, once a domain A has been created by a language specification and the translation into another domain B is specified, we can create several other domains that will be translated to domain A. In this way, all information about how the domain A works is reused. We believe that this approach is a more effective way of achieving reuse than just using a single refinement step from a DSL directly to an executable language. Most current software generators still use this technique. We used the domain network concept in the context of a transformation system implemented by the Draco-PUC Machine. This powerful combination allows us to not only compose components like JTS [18] but also to generate individual pieces of code that once separately compiled communicate during their execution (e.g. MetalBase schema generation). Our solution to the specific problem of the generation of reverse engineering tools (Section 5) is similar to the one proposed by Canfora [20]. However, we use a language based on the application domain (RDOO) instead of using a "strange" (to the user) language, like the algebraic representation proposed by Canfora. This provides a high abstraction level simplifying the task for the reverse engineer. Future work aims at the production of more domains with special emphasis on applying reverse engineering in conjunction with the concept of reengineering [21].

56

Ulf Bergmann and Julio Cesar Sampaio do Prado Leite

7

Acknowledgement

We would like to express special thanks to James M. Neighbors for his valuable comments. We also thanks the anonymous reviewers for they helpful comments.

8

References

1. Neighbors, J., Software Construction Using Components, PhD thesis, University of California at Irvine, 1980. http://www.BayfrontTechnologies.com/thesis.htm 2. Leite, J.C.S.P., M.Sant’Anna, F.G.Freitas, Draco-PUC: a Technology Assembly for Domain Oriented Software Development, Proceedings of the Third International Conference on Software Reuse, IEEE Computer Society Press, 94-100, 1994. 3. Freeman, P., A Conceptual Analysis of the Draco Approach to Constructing Software Systems, IEEE Transactions on Software Engineering, SE-13(7):830-844, July 1987. 4. Harris, D.R., Yeh, A.S., Reubenstein, H.B., Extracting Architectural Features from Source Code, Automated Software Engineering, 3(1/2), Jul. 1996, 109-138. 5. Leite, J.C.S.P, Sant'Anna, M. and Prado, A.F. Porting Cobol Programs Using a Transformational Approach, Journal of Software Maintenance: Research and Practice, Vol. 9, John Wiley Sons Ltd., Vol. 9, pp. 3-31, 1997. 6. Freitas, F.G. and Leite, J.C.S.P., Reusing Domains for the Construction of Reverse Engineering Tools, Proceedings of the 6th Working Conference on Reverse Engineering, IEEE Computer Press, 1999. 7. Leite, J.C.S.P, Sant'Anna, M. and Prado, A.F. Porting Cobol Programs Using a Transformational Approach, Journal of Software Maintenance: Research and Practice, John Wiley Sons Ltd., Vol. 9, pp. 3-31, 1997. 8. Leite, J.C.S.P. and Freitas, F.G. Reusing Domains for the Construction of Reverse Engineering Tools, Proceedings of the 6th Working Conference on Reverse Engineering, IEEE Computer Press, 1999. 9. Coleman, D. et. All, Object-Oriented Development: The Fusion Method, Prentice-Hall, 1994. 10. http://cui.unige.ch/~scg/FreeDB/FreeDB.6.html 11. Bentley, J., Little Languages, Communications of the ACM, 29(8), Aug 1986, pp. 711721. 12. Devanbu, Prem, T. GENOA - A Customizable Language and Front-End independent Code Analyzer, Proceedings of the 14th International Conference on Software Engineering, IEEE Computer Society Press, pp. 307-319, 1992. 13. Christopher A. Welty, Augmenting Abstract Syntax Trees for Program Understanding, Proceedings of the Automated Software Engineering, IEEE Computer Society Press, 1997 14. Booch, G., Object Oriented Analysis and Design with Applications, second edition, Benjamin/Cummings, 1994 15. Rumbaugh, J., et all, Object Oriented Modeling and Design. Prentice Hall ISBN 0-13629841-9, 1991 16. Jackson, M., System Development, Prentice-Hall, 1983 17. http://www.aiai.ed.ac.uk/~jacs/wxwin.html 18. Batory, D. and Smaragdakis, Y., JTS: Tools for Implementing Domain-Specific Languages, Proceedings of the Fifth International Conference on Software Reuse, IEEE Computer Society Press, 1998.

From Application Domains to Executable Domains

57

19. Hudak, P., Modular Domain Specific Languages and Tools, Proceedings of the Fifth International Conference on Software Reuse, IEEE Computer Society Press, 1998. 20. Canfora, G. et All., An Extensible System for Source Code Analysis, IEEE Transactions on Software Engineering, SE-24(9): 721-740, September 1998. 21. Penteado, R., et al., Reengineering of Legacy Systems Based on Transformation Using Object Oriented Paradigm, Proceedings of the 5th Working Conference on Reverse Engineering, IEEE Computer Press, 1998.

Reuse of Knowledge at an Appropriate Level of Abstraction – Case Studies Using Specware Keith E. Williamson, Michael J. Healy, and Richard A. Barker The Boeing Company, Seattle, Washington [email protected]

Abstract. We describe an alternative paradigm for software reuse that attempts to reuse software derivation knowledge at an appropriate level of abstraction. Sometimes that level is a domain theory that is involved in stating system requirements. Sometimes it is a design pattern. Sometimes it is a software component. Often it is a combination of the these. We describe our experiences using Specware for deriving software and reusing software derivations.

1

Introduction

With the advent of intelligent computer aided design systems, companies such as Boeing are embarking on an era in which core competitive engineering knowledge and design rationale is being encoded in software systems [25]. The promise of this technology is that this knowledge can be leveraged across many different designs, product families, and even different uses (e.g., manufacturing process planning). However, this promise has been hard to achieve. The reasons for this are complex, but a large challenge arises from the attempt to reuse software. Programmers, who try to reuse software components written by other people, have run into several problems. First, software components often have assumptions or constraints on their use that are not clearly or explicitly stated. Second, even when these assumptions are clearly and explicitly stated, the assumptions that were applied when the software was originally written may turn out to be different than the assumptions that apply when someone else tries to reuse that component at some point in the future. Third, when this happens, it may be difficult to adapt the software component to different requirements since the original software design rationale is often not stated clearly and explicitly. Generally, these problems arise from a lack of traceability of requirements, through the design process, to software. A fundamental problem in this paradigm of reuse is that what we are trying to reuse is software - the end artifact in a long and complicated process that goes from requirements, through a process of design, to an implementation built on top of some virtual machine. Knowledge sharing and reuse cannot easily and uniformly occur at the software level alone.

W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 58-73, 2000.  Springer-Verlag Berlin Heidelberg 2000

Reuse of Knowledge at an Appropriate Level of Abstraction

59

1.1 Motivations for Software Reuse In attempting to improve the state of the art in reuse, let us back up and ask, “Why are we attempting to reuse software in the first place?” From a software engineering standpoint, it is desirable to: • Increase software system quality • Decrease software development time and costs • Decrease software maintenance time and costs Industry demands that software development and maintenance be made faster, cheaper, and better. Conspiring against this are high labor turnover rates in the software industry, and increasingly in American industry more broadly. Institutional memory concerning software development and maintenance is being lost in this turnover. Is there another way to capture, structure, use and then reuse this knowledge for the purposes of improved software development and maintenance?

1.2 Reuse of Software Derivations Within the field of automated software engineering, there is an approach to software development and maintenance that appears to solve some of these problems [19,21,22,25,1,2]. In essence, this paradigm for software development and maintenance is one that allows the capture and structuring of formal requirement specifications, design specifications, implementation software, and the refinement processes that lead from requirements to software. In this approach, the refinement process can guarantee correctness of the synthesized software. By recording, modifying, and then replaying the refinement history, we are able to more easily maintain the software. By capturing, abstracting, and structuring requirement, design, and implementation knowledge in a modular fashion, we are able to more easily reuse this knowledge for other applications. Knowledge reuse occurs at whatever level of abstraction is most appropriate. Sometimes that level is a domain theory that is involved in stating requirements. Sometimes it is a design pattern. Sometimes it is a software component. Often it is a combination of these. Even within these different levels – requirement, design, and implementation – knowledge can be teased apart, abstracted, and structured in such a way as to make knowledge components that can be more easily reused in other, related applications. As an example, a simplified theory of physics can be stated once and used in many different contexts. As another example, a specification of optimization problems can be stated once and used for stating requirements, designs, and implementations. In this way, software derivation knowledge is captured, abstracted, and structured so that the intellectual effort that goes into system development can be leveraged for other purposes in the future. It is interesting to note that when this technology is applied to software systems whose outputs are designs for airplane parts, the design rationale that is captured is not only software engineering design rationale, but also design rationale from other, more traditional, engineering disciplines (e.g., mechanical, material, manufacturing, etc.). This suggests the technology provides an approach to general systems engineering that enables one to structure and reuse engineering knowledge broadly.

60

Keith E. Williamson et al.

1.3 Overview of Paper We begin this paper with some formal preliminaries, followed by a brief description of the software development tool Specware™. We then describe our experiences using this tool for the derivation and maintenance of Boeing engineering software. Along the way, we describe an excellent example of the challenges of reuse at the software level. Finally, we describe our current work on extending this technology into the realm of requirements elicitation.

2

Formal Preliminaries

The field of category theory [13,16] provides a foundational theory. This theory was applied to systems theory [5,9]. This theory was embodied in the software development tool Specware™ [19,21,22].

2.1 Category of Signatures A signature consists of the following: 1. A set S of sort symbols 2. A triple O = < C, F, P > of operators, where: a. C is a set of sorted constant symbols, b. F is a set of sorted function symbols, and c. P is a set of sorted predicate symbols. Sorts correspond to types. Thus, a signature gives typing information about the various symbols used in a specification. A signature morphism is a consistent mapping from one signature to another (from sort symbols to sort symbols, and from operator symbols to operator symbols). The category Sign consists of objects that are signatures and morphisms that are signature morphisms. Composition of two morphisms is the composition of the two mappings.

2.2 Category of Specifications A specification consists of: 1. A signature Sig = < S, O >, and 2. A set Ax of axioms over Sig Given two specifications <Sig1, Ax1> and <Sig2, Ax2>, a signature morphism M between Sig1 and Sig2 is a specification morphism between the specifications iff: ∀a∈Ax1, (Ax2 |- M(a)) That is, every one of the axioms of Ax1, after having been translated by M, can be proved to follow from the axioms in Ax2. This assures that everything that is provable from Ax1 is provable from Ax2 (modulo translation). Of course, Ax2 may be a stronger theory. The category Spec consists of objects that are specifications and morphisms that are specification morphisms.

Reuse of Knowledge at an Appropriate Level of Abstraction

61

2.3 Diagrams and Colimits A diagram in a category C is a collection of vertices and directed edges consistently labeled with objects and morphisms of C. A diagram in the category Spec can be viewed as expressing structural relationships between specifications. The colimit operation is the fundamental method in Specware™ for combining specifications. This operation takes a diagram of specifications as input and yields a specification, commonly referred to as the colimit of the diagram. See figures 1 and 2. The colimit specification contains all the elements of the specifications in the diagram, but elements that are linked by arrows in the diagram are identified in the colimit. Informally, the colimit specification is a shared union of the specifications in the original diagram. Shared here means that sorts and operations that are linked by the morphisms of the diagram are identified as a single sort and operation in the colimit. For example, in figure 2, the function weight that appears in the panel specification and the manufactured parts specification are linked by the arrows emanating from the part specification (which introduces the weight function). The colimit operation can be used to compose any specifications, which can represent problem statements, theories, designs, architectures, or programs. The fact that specifications can be composed via the colimit operation allows us to build specifications by combining simpler specifications modularly, just as systems can be composed from simpler modules. import

Real Numbers import

Physics physical-object, g, weight, mass, volume, density, weight(p) = mass(p) * g, mass(p) = volume(p) * density(p)

Geometry geometry, volume, box, height, length, width, box-volume, cylinder, radius, depth, cylinder-volume, box-volume(b) = height(b) * length(b) * width(b), cylinder-volume(c) = depth(c) * pi * radius(c)^2

import Materials material, aluminum-7075, if material(p)=aluminum-7075 then density(p)=20

Parts part, g, weight, mass, volume, ..., material, aluminum-7075, geometry, box, box-volume, …, weight(p) = mass(p) * g, ... , if material(p)=aluminum-7075 …, box-volume(b) = ..., …

Figure 1. Colimit of a Specification Diagram

62

Keith E. Williamson et al.

Parts part, weight, mass, ..., volume, height, ... weight(p) = mass(p) * g, ... , box-volume(b) = ..., ...

import

import

Panels

Manufactured Parts

panel, boundary, hole, number-of-holes, vertical separation, horizontal separation, volume(p) =box-volume(boundary(p)) (number-of-holes(p)*cylinder-volume(hole(p))) material(p) = aluminum-7075

part, manufacturing-cost, cost-of-raw-stock, cost-of-drilling-hole, If material(p)=aluminum-7075 then cost-of-drilling-hole(p,h)= 2*cylinder-volume(h) cost-of-raw-stock(p) = 5*raw-stock-volume(p)

Colimit of Diagram import Manufactured Panels panel, cost, raw-stock-volume(p) = box-volume(boundary(p)) manufacturing-cost(p) = cost-of-raw-stock(p) + number-of-holes(p)*cost-of-drilling-hole(p,hole(p)) cost(p) = (5*manufacturing-cost(p)) + (2*weight(p))

Figure 2. Another Colimit followed by a Specification Morphism

3

Specware - A Software Development Tool

Specware™ is a software development and maintenance environment supporting the specification, design, and semi-automated synthesis of correct-by-construction software. It represents the confluence of capabilities and lessons learned from Kestrel’s earlier prototype systems (KIDS [18], REACTO [23], and DTRE [4]), grounded on a strong mathematical foundation (category theory). The current version of Specware™ is a robust implementation of this foundation. Specware™ supports automation of: • Component-based specification of programs using a graphical user interface • Incremental refinement of specifications into correct software in various target programming languages (e.g., currently C++ and LISP) • Recording and experimenting with alternate design decisions • Domain-knowledge capture, verification and manipulation • Design and synthesis of software architectures • Design and synthesis of algorithm schemas • Design and synthesis of reactive systems • Data-type refinement • Program optimization

Reuse of Knowledge at an Appropriate Level of Abstraction

63

The Specware™ system has some of its roots in the formal methods for software development community. Within this community, there are numerous languages that have been used for specifying software systems; e.g., Z [20], VDM [3], and Larch among many others [6]. Of the many formal specification languages, the Vienna Development Method (VDM) is one of the few that tries to formally tie software requirement specifications to their implementations in programming languages. This system is perhaps the closest to Specware™ in that it allows an engineer to specify a software system at multiple levels of refinement. Each step of the refinement process can be formally proven. VDM tools allow for the capture and discharging (sometimes manually) of “proof obligations” that arise in the refinement of a specification from one level to another. Specware™ differs from VDM by having category theory as its fundamental underlying theory. This appears to give several benefits. It allows for a greater level of decomposition, and then composition, of specifications (the use of diagrams and colimits provides a general framework for this). It provides a solid basis [10,15] for preserving semantics in all refinement operations - not only within Slang (Specware’s specification language), but also across different logics (e.g., from the logic of Slang into the logics underlying target programming languages). It allows for parallel refinement of diagrams [22], which helps with the scalability of the technology. Multiple categories underlie Specware™ - signatures, specifications, shapes, interpretations, and so forth. Within each category, the notions of morphism, diagram, and colimit play an analogous role in structuring and composing objects. The utility of category theory lies in its general applicability to many contexts.

4

Stiffened Panel Layout

We began our evaluation of this technology with an example of a software component that was being considered for inclusion in a component library for structural engineering software [24,25]. The software component solves a structural engineering layout problem of how to space lightening holes in a load-bearing panel. The component was originally part of an application that designs lay-up mandrels, which are tools that are used in the manufacturing process for composite skin panels. At first glance, the software component appears to solve the following onedimensional panel layout task (this was pulled from a comment in the header of this component). Given a length of a panel, a minimal separation distance between holes in the panel, a minimal separation distance between the end holes and the ends of the panel, and a minimum and maximum width for holes, determine the number of holes, and their width, that can be placed in a panel. See Figure 3. This software component solves a specific design task that is part of a broader design task. Prior to the invocation of this function, a structural engineer has determined a minimum spacing necessary to assure structural integrity of the panel. Upon closer inspection of the software, one realizes that this function actually minimizes the number of holes subject to the constraints specified by the input parameter values. The original set of constraints defines a space of feasible solutions. Given a set of parameter values for the inputs, there may be more than one solution to

64

Keith E. Williamson et al.

picking the number of holes and their width so that the constraints are satisfied. So, the software documentation is incomplete. However, going beyond this, one is inclined to ask, “Why did the programmer choose to minimize the number of holes?” Is there an implicit cost function defined over the feasible solutions to the original set of constraints? If so, what is it? Presumably, this is all part of the engineering design rationale that went into coming up with the (not fully stated) specification for the software component in the first place. If we were to use this component to design a panel that was to fly on an airplane, the panel would be structurally sound, but not necessarily of optimal cost (e.g., not making the best trade-off between manufacturing cost and overall weight of the panel). Panel Width End Separation

Separation

Hole

End Separation

Separation

Hole

Hole

Figure 3. Stiffened Panel Layout Problem

Rather than put this incompletely documented software component into a reuse library, we seek to explicate the engineering design rationale and tie it directly to the software. For this purpose, we used the Specware™ system to first document the structural and manufacturing engineering design rationale leading to the software component specification, and then generate software that provably implements the specification (which in turn requires documenting software design rationale). Specware™ allows specifications to be composed in a very modular fashion (using the colimit construction from category theory). In this example, we were able to generate a specification for basic structural parts by taking a colimit of a diagram, which relates specifications for basic physical properties, material properties, and geometry (see Figure 1). A specification for stiffened panels was derived by taking the colimit of another diagram, this time relating basic structural parts to panel parts and manufactured parts (see Figure 2). This specification was then imported into another, which added manufacturing properties that are specific to stiffened panels (it is here that we finally state the (originally implicit) cost function). From this specification, and another describing basic optimization problems, we are able to formally state the panel layout problem. This specification was then refined into Lisp software [25].

4.1 The Challenge of Software Maintenance As business processes change, software requirements must change accordingly. Some software changes are straightforward. Other changes are harder to make, and

Reuse of Knowledge at an Appropriate Level of Abstraction

65

the inherent complexity is not always obvious. In the stiffened panel layout example, suppose there is a change to the material of the panel. If the density of the new material is less than five, then the search algorithm that was used is no longer applicable [25]. In fact, with this single change to the cost function, it is more cost effective to have no holes in the panel at all! What is fundamentally missing in the software (the end artifact in the software development process) is the fact that a design decision, that of picking a particular algorithm to solve a class of optimization problems, is reliant on a subtle domain constraint. Indeed, in the original software component, the cost function is nowhere to be seen in the software, nor the documentation that was associated with it. Knowledge sharing and reuse cannot easily and uniformly occur at the software level. If we place requirement specifications, design specifications, and software derivations in a repository, we can reuse them to derive similar engineering software. When requirements change (e.g., in response to a change in manufacturing processes), we are able to change the appropriate specifications, and attempt to propagate those changes through the derivation history. Sometimes the software can be automatically regenerated. Other times, some of the original software design will break down (due to some constraints no longer holding). In this case, we need to go back to the drawing board and come up with a new design to satisfy the requirements. But even in these cases, presumably only some portions of the software will need to be redesigned. We leverage those parts of the software design that we can. In this way, we reuse knowledge at the appropriate level of abstraction, and not solely at the software level.

5

Equipment Locator Problem

After the successful experience of using Specware™ on the stiffened panel layout component, we decided to see if the technology would scale up to industrial strength applications. There were various criteria that we used to pick this application. The application should: • Be large enough to test scalability. • Be a real problem of importance to Boeing. • Already have requirement documents written. • Be an engineering application with relatively simple geometry. • Have requirements that change over time. • Be in a family of related applications. • Have overlap with the panel layout problem. • Be functional in nature (i.e., no real time constraints). Some of these requirements were chosen in an effort to maximize reuse of knowledge over time and across applications. We have felt that the additional up front costs (associated with rigorously defining requirement specifications and design specifications) can more easily be justified if there is a high probability that those costs can be amortized over a relatively short period of time (i.e., two or three years). Only the last requirement is due to current state of the technology (although work is being done in this area).

66

Keith E. Williamson et al.

After some searching, we found the equipment locator problem, which satisfied all of the criteria listed above. This is the problem of determining optimal placements of electronic pieces of equipment (e.g., the flight data recorder, inertial navigation systems, flight computers, etc.) on shelves of racks in commercial airplanes. The purpose of the equipment locator application is to support the equipment installation design process for determining optimal locations for electrical equipment. The application supports the designers in determining optimal locations for equipment on a new airplane model, as well as finding a suitable location for new electrical equipment on an existing airplane model. The application is intended to reduce the process time required to determine equipment locations, and also improve the quality of the equipment location designs. Numerous specifications are needed for stating and solving this problem; e.g.: • Theory of geometry, • Global and relative part positioning, • Major airplane part and zone definitions, • Operations and properties for pieces of equipment, shelves, and racks, • Separation and redundancy requirements for equipment, • An assignment of a piece of equipment to a position on a shelf, • A layout (a set of assignments), • Hard constraints on layouts, • Cost function on layouts, • Theories of classes of optimization problems, • Theories of search algorithms for classes of optimization problems, • The equipment locator problem statement, • An algorithmic solution to the problem (instantiating a branch and bound algorithm) All in all, about 7,000 lines of requirement and design specifications are needed to state and solve this problem. The generated Lisp software exceeds 7,000 lines. The fact that the number of lines of specifications roughly equals the number of lines of code is coincidental. In other situations, the code may far exceed the specifications.

5.1 General Problem Statement With some simplification, the equipment locator problem has as inputs: 1. A set of shelves 2. A set of equipment 3. A partial layout of equipment to shelves And produces as output the set of all layouts of equipment to positions on shelves, such that: 1. The partial layout is preserved/extended, 2. All pieces of equipment are placed in some position on some shelf, 3. All hard constraints are satisfied, 4. Layout costs (e.g., wiring distances between pieces of equipment) are minimized. The hard constraints, which define feasible layouts, are things like: • Equipment assignments can not overlap, • Equipment must be placed on shelves with appropriate cooling properties,

Reuse of Knowledge at an Appropriate Level of Abstraction

67

• • • • •

Redundant pieces of equipment must be placed on separate cooling systems, Critical pieces of equipment have certain restricted regions in space, Equipment with low mean time to failure must be easily accessible, Voice and flight data recorders must be placed in the front electrical bay, Equipment sensitive to electromagnetic interference must be separated (by a certain distance) from other equipment emitting that interference. The cost function on layouts includes such things as: • Equipment wiring distances minimized, • Heavy equipment should be placed as low as possible (for ergonomics), • Voice and flight data recorders should be placed as far aft as possible. The following portion of the requirement specifications give an illustrative example of the specification language (Specware™ does have a prefix notation, but we did not use it). The first axiom states that for any two assignments in a layout, if they contain redundant pieces of equipment, then the minimal distance between them must be greater than the required separation distance for redundant pieces of equipment. The second axiom states that for any two assignments in a layout, if they contain redundant pieces of equipment, then the cooling properties of the shelves that contain them must be different. Both are hard constrains that must be satisfied to assure safety of the aircraft configuration under unusual circustances.

op redundant-separated-enough : layout -> boolean axiom (iff (redundant-separated-enough l) (fa (a1:assignment a2:assignment) (implies (and (in a1 l) (in a2 l)) (implies (redundant (equipment-of a1) (equipment-of a2)) (gt (min-distance (assigned-geometry a1) (assigned-geometry a2)) (redundant-sep (equipment-of a1) (equipment-of a2))))))) op redundant-separate-cooling : layout -> boolean axiom (iff (redundant-separate-cooling l) (fa (a1:assignment a2:assignment) (implies (and (in a1 l) (in a2 l)) (implies (redundant (equipment-of a1) (equipment-of a2)) (not (equal (cooling (shelf-of a1)) (cooling (shelf-of a2))))))))

5.2 Process for Technology Use So how does one go about using this technology for industrial applications? After having learned some of the underlying theory, and then Specware™ (from working on the stiffened panel layout problem), we proceeded to learn the domain of our new

68

Keith E. Williamson et al.

application. We had three English requirement documents to work from. These comprised about 20 pages of writing, drawings, etc. In addition, we had several pieces of supporting material (tables, drawings, etc). Only two discussions with a domain expert were needed, since the requirement documents were fairly clear and complete. Once understood, we formalized the requirements. Part of this involved figuring out how to best decompose and abstract various portions of the problem domain. We estimate that we captured roughly 98% of the requirements found in the informal material. The remaining 2% of the requirements dealt with interfacing with other software systems (of which we had insufficient information at the time). Next, we went through a manual validation process in which we compared the formal requirements with the informal ones. We wrote a brief document noting places where either: • Requirements were not formalized (the 2% mentioned above), • Additional detail was needed to formalize the requirements (due to some degree of ambiguity in the English documents), or • Some choice was made between alternate interpretations of the written material (since the three English documents were written at different times, there were minor inconsistencies). Once the requirements were formalized, we made and then encoded our design decisions. Again, there were decisions to be made about decomposition and abstraction. For each design decision, we needed to choose data structures for sorts and algorithms for operators. Specware™ comes with many built-in specifications that can be used for this (and other purposes). For example, there are specifications for sets, lists, and sets interpreted as lists. These design decisions then had to be verified to ensure that requirement properties were upheld. Specware™ has a built-in resolution based theorem prover. This was used to prove roughly 25% of the proof obligations. The other 75% were proven by hand. Since these proofs were done informally, some errors may be present (most proofs were done mentally, and not actually written down). Eventually, every sort and operation had to be refined down into some data structure and operation provided by the Lisp programming language. Finally, once the software was initially generated, we maintained the software with Specware™. As we learned more about the problem domain, several changes were made to the requirement specifications, and the software was easily regenerated. None of these changes required significant redesign efforts, fortunately. However, one other change did. The initial optimization algorithm used an exhaustive search. For purposes of rapid prototyping, we had used the optimization problem theories and search theories from the stiffened panel layout problem. Since these were inefficient when applied to this problem, we encoded an additional theory of branch and bound optimization problems, and applied a corresponding search theory to the domain of the equipment locator problem. The general branch and bound theories are completely reusable (i.e., independent of the domain in which they are instantiated).

Reuse of Knowledge at an Appropriate Level of Abstraction

69

5.3 Getting the Technology into Broader Use Our overall impression is that this technology does work for industrial strength applications, but that it needs additional work to make it more usable [26]. We briefly describe some suggestions in this subsection. For maximum ease of use, the user interface of any system should reflect and reinforce the user’s mental model of the artifacts and processes involved. The interface of the Specware™ needs to be designed with this in mind. Some other, specific suggestions for improvement of Specware™ include: • Support for linking nonformal requirements to formal requirements (e.g., perhaps hyperlinks between English documents and formal requirement specifications). • Better support for viewing dependencies between requirements, designs, and software. While those dependencies are present in proofs, it would be handy to view them directly. • Better proof support (e.g., better theorem provers, enhanced with constraint solvers and other types of theorem proving). • Support for program level optimization (e.g., compiler-like optimizations and finite differencing found as in KIDS [18]). • Better support for software derivation replay. Some of this work is already underway at Kestrel Institute. Creating an environment surrounding Specware(TM) that is tailored to specific domains of application would also enhance the effectiveness of the technology. This, together with improved theorem proving, would make the technology more suitable for safety critical applications (e.g., avionics software systems).

6

Requirements Elicitation

Systems development and engineering does not often begin with a clear and formal statement of requirements. A system such as Specware™ allows reuse of knowledge from that point forward, but preceding this, are there opportunities for knowledge reuse? If so, can one find a common underlying theory for knowledge structuring and reuse that allows an integration of requirements elicitation techniques with the systems development techniques describing previously in this paper? These are some of the questions underlying our current work.

6.1 Human Factors Engineering The most common causes of failure of software development projects are a lack of good requirements and a lack of proper understanding of users' needs (www.standishgroup.com and [8]). System developers have long recognized how difficult it is to elicit good requirements from users and customers. Even experienced developers, who are intelligent people with at least a normal amount of common sense, still fall prey to this problem. Why?

70

Keith E. Williamson et al.

There are two parts to this problem. First, eliciting the requirements from users. Second, inserting those requirements into the system development process. People have difficulty verbalizing their inner thought processes. This is called “The Fallacy of Conscience Access” [7]. To make matters even more challenging, some of the domain knowledge may exist only as collective knowledge of a group of people. This "tribal" knowledge is not usually written down nor is it formally encapsulated. One solution is to use the tools and techniques from a specialty engineering discipline called Human Factors Engineering (HFE). HFE uses the principles of cognitive psychology to elicit knowledge from users and customers, and designs interfaces that allow users to interact with the system so as to perform their tasks efficiently and effectively. Human Factors engineers have professional training in techniques for interviewing, observing, questionnaires, surveying, human testing, and how to build task models of user-system interactions. These techniques and processes are outlined in [14,27]. Data obtained using these techniques specify not only the users work processes, but also the data and system behavior the user needs to accomplish those work processes. The data and behavior are grouped into user-centered Information Control Groups (ICG). A study of the users’ cognitive tasks has been shown to lead to shorter development projects and better products [8]. Although the requirements elicitation phase of the project is lengthened, the system construction phase is shortened. The overall length (and cost) of the project is less. The resulting system better meets customer needs and therefore requires less maintenance. The second part of the system development problem, inserting user requirements into the system development process, requires that the users’ task models be formalized and inserted into the system development process at the appropriate time. The task models can be described as a series of steps in which the user accesses an ICG, executes some behavior on the data it contains, and goes on to the next step in the work process. The data and behavior requirements encapsulated in an ICG therefore specify a large proportion of the system behavior in most business applications. Further, a description of the number of users and the frequency with which tasks are executed specifies performance requirements of the system. The challenge is to capture the data and behavior encapsulated in an ICG using more formal methods. The ability to represent domain knowledge as a user interface allows us to do two key things. First, using a user interface prototype as a communication tool can iteratively refine our knowledge of the domain. User and domain experts often have difficulty expressing highly technical domain knowledge in terms an expert in another domain, such as software engineering, can grasp. Second, the user interface can be used to allow the users and domain experts to interact with the to-be system (albeit in a limited way) to perform common tasks. Customers can then "buy-off' on the to-be system before system construction begins since, to the customers, domain experts, and users, the user interface is the system [14]. Buying off on the system, before system construction, is very effective at stabilizing requirements. A major cause of high software maintenance costs is "changing customer requirements." Closer examination shows that the customer didn't change requirements - the requirements were poorly understood until system delivery when the user first could get hands on experience with the system.

Reuse of Knowledge at an Appropriate Level of Abstraction

71

6.2 Algebraic Semiotics We propose that category theory provides a mathematical foundation for translating user task models and domain knowledge into formal system requirements. Possible techniques for doing this have been proposed under the term algebraic semiotics [11]. Semiotics is the study of systems of symbols and their meaning. Symbol systems include, for example, Object Oriented class models, user interfaces, task models, and even the users' internal cognitive representation of domain knowledge (i.e., mental models [17]). Formalizing these representations of knowledge in category theoretic systems allows a well-defined, mathematical approach to understanding reuse of engineering domain knowledge at higher levels of abstraction. The process for moving from domain knowledge to software proceeds through several discrete stages. The highly informal and unstructured domain knowledge that exists in the minds of domain experts and users is represented as a task model. The task model can be represented as a symbol system whose structure is defined in category theory. The users' interface to the system is some translation of the users' perception of the task model, and is itself a symbol system. The symbol systems as well as the translations are represented in category theory [11]. The groupings of controls and displays in the user interface, and the order in which users access them to perform tasks, determine the information processing demands imposed on the system by the user. This defines the system requirements for most business systems. This does not mean that all aspects of system functions are in the user interface, only that the need for the system functions is implied by the user interface. For example, in the equipment locator problem above, the formula for calculating RFI is not in the user interface. However, the user interface does show the need for making this calculation, and the requirement is defined.

7

Summary

Reuse cannot easily and uniformly occur at the software level alone. In this paper, we have described an alternative paradigm for reuse that attempts to reuse knowledge at an appropriate level of abstraction. Sometimes that level is a domain theory that is involved in stating system requirements. Sometimes it is a design pattern. Sometimes it is a software component. Often it is a combination of these. We have described our experiences in applying a category theory based approach to industrial strength software specification, synthesis, and maintenance. This paradigm is one that allows the capture and structuring of formal requirement specifications, design specifications, implementation software, and the refinement processes that lead from requirements to software. In this approach, the refinement process can guarantee correctness of the generated software. By recording, modifying, and then replaying the refinement history, we are able to more easily maintain the software. By capturing, abstracting, and structuring knowledge in a modular fashion, we are able to more easily reuse this knowledge for other applications.

72

Keith E. Williamson et al.

It is interesting to note that when this technology is applied to software systems whose outputs are designs for airplane parts, the design rationale that is captured is not only software engineering design rationale, but also design rationale from other, more traditional, engineering disciplines (e.g., mechanical, material, manufacturing, etc.). This suggests the technology provides an approach to general systems engineering that enables one to structure and reuse engineering knowledge broadly.

Bibliography 1. 2. 3. 4. 5.

6. 7. 8. 9. 10. 11.

12. 13. 14.

Balzer, R., A 15 Year Perspective on Automatic Programming, in IEEE Transactions on Software Engineering, Vol. SE-11, no. 11, November 1986, pp. 1257-1268. Baxter, I., Design Maintenance System, in Communications of the ACM, vol. 35, no. 4, April 1992, pp. 73-89. Bjorner, Dines and Jones, Cliff, Formal Specification & Software Development, Prentice-Hall International, 1982. Blaine, Lee and Goldberg, Allen, DTRE – A Semi-Automatic Transformation System, in Constructing Programs from Specifications, ed. B. Moller, North Holland, 1991. Burstall, R. M. and Goguen, J. A., The Semantics of Clear, a Specification Language, in Proceedings of the Copenhagen Winter School on Abstract Software Specification, Lecture Notes in Computer Science, 86, Springer-Verlag, 1980. Gannon, John et al., Software Specification - A Comparison of Formal Methods, Ablex Publishing. Gardiner, M. and Christie, B. Applying Cognitive Psychology to User-Interface Design, John Wiley & Sons, 1987 Gibbs, W., Taking Computers to Task, Scientific American, July 1997. Goguen, J. A., Mathematical Representation of Hierarchically Organized Systems, in Global Systems Dynamics, ed. E. Attinger and S. Karger, 1970, pp. 112-128. Goguen, J. A. and Burstall, R. M., Institutions: Abstract Model Theory for Specification and Programming, Journal of the Association of Computing Machinery, 1992. Goguen, J. A., An Introduction to Algebraic Semiotics, with Applications to User Interface Design, in Computation for Metaphor, Analogy and Agents, edited by Chrystopher Nehaniv, Springer Lecture Notes in Artificial Intelligence, 1999. Jullig, R. and Y. V. Srinivas, Diagrams for Software Synthesis, Proceedings of the 8th Knowledge-Based Software Engineering Conference, Chicago, IL, 1993. MacLane, Saunders, Categories for the Working Mathematician, SpringerVerlag, 1971. Mayhew, Debra J., The Usability Engineering Lifecycle, Academic Press/Morgan Kauffman, 1999.

Reuse of Knowledge at an Appropriate Level of Abstraction

73

15. Meseguer, Jose, General Logics, Logic Colloquium ‘87, Eds. Ebbinghaus et al., Elsevier Science Publishers, 1989. 16. Pierce, Benjamin C., Basic Category Theory for Computer Scientists, MIT Press, 1994. 17. Rogers, Yvonne, et. al, Models in the Mind – Theory, Perspective, and Application, Academic Press, 1992. 18. Smith, Doug, KIDS: A Knowledge Based Software Development System, in Automating Software Design, Eds. M. Lowry and R. McCartney, MIT Press, 1991. 19. Smith, Doug, Mechanizing the Development of Software, in Calculational System Design, Ed. M. Broy NATO ASI series, IOS Press, 1999. 20. Spivey, J. M., The Z Notation: A Reference Manual, Prentice-Hall, New York, 1992. 21. Srinivas, Y. V. and Jullig, Richard, Specware™: Formal Support for Composing Software, in Proceedings of the Conference of Mathematics of Program Construction, Kloster Irsee, Germany, 1995. 22. Waldinger, Richard et al., Specware™ Language Manual 2.0.1, Suresoft, 1996. 23. Wang, T. C. and Goldberg, Allen, A Mechanical Verifier for Supporting the Design of Reliable Reactive Systems, International Symposium on Software Reliability Engineering, Austin, Texas, 1991. 24. Williamson, K. and Healy, M., Formally Specifying Engineering Design Rationale, in Proceedings of the Automated Software Engineering Conference, 1997. 25. Williamson, K. and Healy, M., Deriving Engineering Software from Requirements, Journal of Intelligent Manufacturing, to appear, 1999. 26. Williamson, K. and Healy, M., Industrial Applications of Software Synthesis via Category Theory, in Proceedings of the Automated Software Engineering Conference, 1999. 27. Human Engineering Program – Processes and Procedures, US Department of Defense, Handbook MIL-HDBK-46855A, 1996.

Building Customizable Frameworks for the Telecommunications Domain: A Comparison of Approaches Giovanni Cortese1, Marco Braga2, and Sandro Borioni3 1

Processes, Reuse & Technologies Sodalia S.p.A., Via V. Zambra, 1, Trento, TN 38100, Italy [email protected] 2 TDM Business Unit Sodalia S.p.A. [email protected] 3 IS & PL Architecture Sodalia S.p.A. [email protected]

Abstract. Based on the experience of development of industrial application frameworks for the telecommunications domain, we compare different approaches and techniques for achieving software reuse. In particular, we describe an assessment we performed on two application frameworks for the telecommunications domain developed in Sodalia. The assessment had the objective of collecting evidence on the benefits and implications of different techniques which can be adopted for achieving large-grain reuse in product line development. Keywords: Software Architecture, Object-Oriented Framework, Design Patterns, Software Reuse, Distributed Systems, Product Lines, Network and Service Management, Network Traffic Data Analysis.

1

Introduction

Successful programs evolve to become more reusable. As they evolve, domain abstractions, originally embedded in the code, tend to surface either in the software or in the data architecture. If a business driver exists, this evolution may lead to the development of an application framework for the domain, which can be deployed in different custom projects with a limited customization effort. 'Reusability', i.e. the ability to reuse functionalities in a variety of technical and business contexts, can be obtained with several technical approaches: configuration mechanisms domain-specific scripting languages object-oriented frameworks metadata W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 74-88, 2000.  Springer-Verlag Berlin Heidelberg 2000

Building Customizable Frameworks for the Telecommunications Domain

75

This evolutionary path (see [18] for a more extended introduction of the subject) has been occurring quite regularly in our software development experience, both when reengineering for reuse medium-grain software components, and, on a much larger scale, when evolving custom applications to application frameworks. This paper describes an analysis we performed on two application frameworks developed within Sodalia. We surveyed the mechanisms and techniques which our engineers adopted to build large-grain reusable software assets, in order to assess their effectiveness in our business and their relevance to our asset base. Specifically, we wanted to get some insight on how these mechanisms are related to productivity, time-to-market, and other architectural qualities, and on the degree of penetration of specific reuse techniques in our software developers’ community. The paper introduces the method we followed in the analysis, provides an architectural analysis of the application frameworks from the specific point of view of adopted reuse techniques, and provides a summary of the findings of this assessment.

1.1 Business and Organizational Context Sodalia S.p.A. is an Italian company in its sixth year of activity. Its mission is the development of innovative telecommunications software products for the management, administration, and maintenance of telecommunication networks and services. Reuse Program From its founding, Sodalia has adopted a Reuse Program whose goal is to make software reuse a significant and systematic part of the software process. A dedicated group, over the years accounting for roughly 3-4 percent of the company’s development staff, has acted as facilitator in the adoption of reuse practices, by taking actions such as development of reusable components, development of methodology, training, and dissemination of information. Product Lines and Application Frameworks The company delivers custom solutions to its customers by reusing whenever possible an Application Framework for a specific domain (e.g. Service Fulfillment, Service Assurance, Network Data Management). According to [15] “A software product line is a set of software-intensive systems sharing a common, managed set of features that satisfy the specific needs of a particular market segment or mission. Substantial economies can be achieved when the systems in a software product line are developed from a common set of core assets. A new product, then, is formed by taking applicable components from the asset base, tailoring them as necessary through pre-planned variation mechanisms such as parameterization, adding any new components that may be necessary, and assembling the collection under the umbrella of a common, product-line-wide architecture. Building a new product (system) becomes more a matter of generation than creation; the predominant activity is integration rather than programming.”

76

Giovanni Cortese et al.

Sodalia’s Application Frameworks are developed as the core of a product line, from a development process point of view. They have been built mostly in a bottomup fashion, in an iterative process of generalizing software components developed for a previous project to accomodate requirements for a subsequent custom project (or new releases of existing ones). In a few cases, investments have been made to rearchitect important assets in order to introduce the flexibility needed to deal with ‘likely’ customer scenarios. For each product line two development groups exist, one for engineering the core and one for delivering the solutions to the customer. A product line architect guarantees technical coordination between the two groups. Reusable Asset Repository and Sodalia Architectural Framework The Application Frameworks presented in this paper share a number of reusable domainindependent components, which provide a common application infrastructure (available in a Reusable Asset Repository), and a common set of architectural guidelines (Sodalia Architectural Framework [16]), defined to increase the interoperability between software developed by different teams. The common infrastructure and architecture is developed by the Reuse Support Organization. The remainder of this paper is structured as follows. First, we recap some useful concepts on customization mechanisms and introduce the classification criteria which we adopted for this analysis. The bulk of the paper is represented by the two case studies, where each application framework is described with emphasis on the customization mechanism used for each of its subsystems, and by the assessment summary, where the results of the analysis are shown. Last, conclusions and further directions of work are presented.

2 A Taxonomy of Techniques for Design of Customizable Software In this section, we present a simple taxonomy of approaches for designing adaptable/ customizable software. Each of them represents an alternative for introducing new domain-specific behavior into a customizable component. Though there might be more accurate or fine-tuned ways of making this taxonomy, we found that these five categories fit the descriptive needs of our analysis.

2.1 Object-Oriented Frameworks OOFs are application frameworks designed according to a number of well documented object-oriented techniques (see for example [20]). To extend the capabilities of an OOF [17], a combination of the following techniques can be used:

Building Customizable Frameworks for the Telecommunications Domain

77

in white-box frameworks, the existing functionality is reused and extended by (1) inheriting from the framework base classes (2) overriding predefined hook methods via patterns [5] like the Template method. black-box frameworks support extensibility by defining interfaces for components which can be plugged into the framework via object composition. Existing functionality is reused by (1) defining componens which adhere to a particular interface, (2) integrating these components into the framework using patterns such as Strategy and Functor Though the actual mechanisms may vary depending on the chosen implementation techniques and language, often OOF customization requires availability of the development environment.

2.2 Active Object Models Metamodels are another technique for designing highly customizable and reusable software. With this approach, the focus is on making data more reusable, by including in the object model of the application a number of objects which provide explicit representation of other objects and their relationships. Data that describe other data, rather than aspects of the application domain itself, are called metadata. An important class of applications whose design exploits metadata can be described according to the Active Object Model (AOM) pattern [18]: “An ACTIVE OBJECT- MODEL is an object model that provides ‘meta’ information about itself so that it can be changed at runtime .. A system with an ACTIVE OBJECT-MODEL has an explicit object model that it interprets at run-time.. As this evolutionary process unfolds, and the architecture of a system matures, knowledge about the domain becomes embodied more and more by the relationships among the objects that model the domain, and less and less by logic hardwired into the code.. In the end, this design allows some application configuration decisions to be pushed to the user ..” An AOM implementation is typically comprised of:   



the metamodel (typically data, may include a software interface, e.g. through CORBA IDL, which is used by applications to interact with the metamodel) a number of generic applications, which reason on the domain metamodel a parser of the domain-specific language, which can be used to load and extend the metamodel a visual builder, for interactive manipulation of the metamodel Examples follow: a software application which supports the provisioning process of Telecom/ Internet Services [19]. The business rules which describe how to combine simple service elements (for example, a Frame Relay virtual circuit) and network resources (for example, a customer premises router), to deliver aggregated, end-toend services according to commercial offers are represented in the object model. Entities describing new types of services, network resources and commercial offers together with their relations can be added dynamically to the model (by the marketing staff itself). Generic applications, such as the resource reservation

78

Giovanni Cortese et al.

algorithm which is executed to fulfill a new customer order, are not impacted by the extensions to the model a workflow engine, which is able to execute different workflow schemas Customization of an AOM can be made at run-time, by using the parser of the associated domain-specific (meta)language or a visual builder. All the AOM software components are reused black-box. Also, metadata are often reused in different customizations.

2.3 Property-Based Customization Components may be customized by having them expose a number of properties, i.e. attribute-value pairs. Java Beans represent an example of components which can be customized by setting values for properties. This category may include components whose degree of customizability varies widely. The power and flexibility in customization depends obviously on how much semantics can be associated with the property values. We chose to classify in this category components with relatively simple configuration options, where the property values are used mostly to select between available logic/ behavior. Customization of this type of component is usually done when packaging the product or at installation time.

2.4 Macro Preprocessors/Code Generators Borrowing again from [18], “Often, users will want to specify complex new behaviors that are beyond what can be specified using traditional properties or tables. Therefore, have a program generate the code, based upon some description, and compile or interpret it. Macro systems write code based on their arguments and on expansion rules given by their (human) authors. Some macro systems make heavy use of metadata. Macros may or may not be expanded at run-time.”

2.5 Domain-Specific Scripting Languages As a customization mechanism, scripting languages can be used to add at run-time1 new business rules / algorithms to an existing component. While also AOMs often rely on a language which is used for the purpose of interacting with the metamodel, and often include a parser, scripting languages (e.g.

1

In a sense, this approach is very similar to the macro preprocessor. Both are driven by the desire to embed domain-oriented language primitives into a fully featured programming language. With scripting languages, the focus is on an interpreted run-time environment.

Building Customizable Frameworks for the Telecommunications Domain

79

domain-specific scripting languages such as Tcl-based Scotty, an SNMP- oriented2 language interpreter) are more procedural in nature. They represent very powerful ways to program new algorithms to an extensible component, and can complement the other approaches mentioned in this chapter e.g. be configured into a component via properties implement ‘Strategy’ hooks in an OOF

3

Case Study: STM/AF

3.1 Main Functionalities Sodalia Traffic Manager (STM/AF) is an application framework for network traffic data collection and analysis. The most important functionalities provided by the system are: Data Collection: traffic data are collected and stored in a repository after being mapped to a common representation that hides technology specificity. Network surveillance: collected data are evaluated against predefined thresholds to generate alerts on network congestion. Traffic engineering: collected data are aggregated across different dimensions to spot trends on a daily, monthly, and yearly time scale. Reporting: the system is completed by a report environment that provides a mechanism able to schedule and generate reports according to user requests.

3.2 Variability Requirements The framework has been used to address the needs of a number of custom projects. While the functionalities each customization must provide are typically very similar, the framework has to be able to manage different network technologies (voice and data) e.g. Circuit Switch (CS) technology, ATM, IP, FTTC. Specifically, it has to deal with variability in: network protocols data formats interfaces to customer legacy Operations Support Systems (OSS)

3.3 Architectural Overview and Reuse Techniques To address the variability requirements presented so far, STM/AF design relies mostly on a powerful AOM-based repository, and on an easily extensible subsytem acting as an adaptation layer to external data sources. STM/AF architecture is summarized by Figure 1. 2

Simple Network Management Protocol, an application level protocol for development of network management applications.

80

Giovanni Cortese et al.

OOF DCCustom Generic AOM Apps.

VBC

RSRE

MCF

NSEB

NSEBV

Macro Processor RSRS

DCN DCCC TEDAC NSEC

PB Appl

MDR

AOM kernel

NSTE

CFAT CNET

CNE

NSTEV

MVC based appl. CFATV

CNEV

Fig. 1. STM/AF Architecture

At the heart of the system lies the Metadata and Data Repository (MDR). The repository is based on a relational database and is optimized for dealing with very large sets of data. The repository implements a meta-model for objects such as network topologies, network elements and network performance measurements. The meta-model can be instantiated through a visual builder tool (VBC), which allows the user of the system to create descriptions of ‘real world’ network objects. Metadata configuration files (MCF) are then created through a generation process. Within the Data Collection subsystem, the DC Custom component is in charge of the interface with network elements or external OSSs. The DC Custom is based on Bulk Data Transfer (BDT). BDT is an OOF, following the ‘Pipe&Filter’ ([1]) architectural pattern, which can be customized to implement a number of different data transfer, compression, and ‘cleanup’ strategies. The data collection subsystem is completed by a few ‘generic applications’ whose behavior is completely driven by the metamodel, hence are reused ‘black-box’, such as Data Collector Normalizer (DCN) and the Consistency Checker (DCCC). Similarly, ‘generic applications’ represent a significant portion of the Network Surveillance subsystem (Exception Calculator Engine - NSEC, Exception Browser Model - NSEB, Threshold Editor Browser Model - NSTE), of the Traffic Engineering subsystem (Data aggregation and calculator engine - TEDAC), and of the Configuration subsystem (Network Element Configuration Model - CNE, Network Element Type Configuration Model - CNET, Formula Aggregation Type Configuration Model - CFAT). At the architectural/ infrastructural level, the Model-View- Controller pattern ([7), together with an OOF which provides its implementation in a Java-CORBA ([9],[10])

Building Customizable Frameworks for the Telecommunications Domain

81

environment, provides a uniform method of interfacing the ‘model’ component of the applications already mentioned with their GUIs. The GUIs (views) are configurable via properties (Exception Browser View NSEBV, Threshold Editor View - NSTEV, Network Element Configuration View CNEV, Formula Aggregation Type Configuration View (CFATV). Finally, the Report Subsystem is supported by a Macro Processor which is able to generate at run-time HTML pages based on templates.

4

Case Study: SISM/AF

4.1 Main Functionalities SISM/AF, an integrated service management application framework [4], offers integrated customer-focused service and network management capabilities for heterogeneous, multi-domain networks [3]. The application framework aims to isolate service problems across a broad range of modern network technologies for diverse types of services (ATM, FR, IP, etc.). This requires a complete set of fault, performance, and configuration management functionalities organized into customer views.

4.2 Variability Requirements SISM/AF is organized as an application framework so that it can be quickly customized to handle new network technologies and differences in customer environments. The requirements which shaped the architectural strategy oriented to large-grain reusability of SISM can be summarized in the ability of dealing with the following variations: Business Process variations. Software applications, such as SISM, whose target customers are telecommunication service providers, should flexibly adapt to peculiarities in operational workflow and organizational roles. Network Technology and Management Protocol variations. The main goal of SISM is to provide integrated and homogeneous management capabilites across a wide variety of network technologies and management protocols. Service variations. The current trend in the Telecommunication market is to compete through increased differentiation in the service offering portfolio and reduced time-to-market of new services. SISM must allow the user to define new services through system configuration. OSS interface variations. Deploying SISM in a specific customer environment requires taking into account integration with the existing, legacy OSSs of the customer.

82

Giovanni Cortese et al.

4.3 Architectural Overview and Reuse Techniques The SISM framework addresses these challenges by customizability techniques at different levels of its architecture. Client Apps (Service View)

Client Apps (Alarm View)

Client Apps (Topology View)

.....

Nw and Service Instance DB Nw and Service Inventory

Nw and Service Fault

External OSS Interface Framework

Nw and Service QoS

applying

different

SISM Management Applications Client Tier

SISM Management Applications Server Tier

Nw and Catalog DB (Metadata)

Core VNM

Core VNM

Core VNM

....

.... Core TL1

Core SNMP Cust. SNMP1

Cust. SNMPn

Custom TL11

CISCO

IBM

X

Custom TL1k

Y

SISM Management Adaptation Tier

Cust. NEMS1 Cust. NEMSk

Nortel

Lucent

Network/ Network Element Layer

Fig. 2. SISM/AF Architecture

The picture below presents the main architectural subsystems of SISM: Virtual Network Manager (VNM) Core. VNM components are adapters for interfacing different types of network equipment. They provide a uniform CORBA management interface between SISM applications and the managed environment. VNMs are developed by specializing via inheritance a C++ OOF. VNM Core SNMP, Core TL1. An additional layer of customizable software is aimed at managing two broad classes of network devices, specifically those manageable through the SNMP and TL/1 protocols. Variations are handled through algorithms written in a scripting language (Tcl). Network and Service Inventory (NSI). A persistent, high performance repository of objects describing the managed environment (e.g. devices, connections, service agreements) implements a model of the managed environment. The design of this component is based on the AOM approach, that is to say service and network configuration data are modelled through a generalized object model of the network. The model can be extended via scripts and a visual builder. All SISM applications are based on the NSI metamodel. This allows easy extension of the management scope (i.e., add new service types) at run-time avoiding system recompilation and code changes. Some of these applications combine this ability with additional mechanisms which allow adaptability and reuse. For example, the Event Correlation engine can interpret a scripting language through which an experienced user can add new rules for diagnosing service

Building Customizable Frameworks for the Telecommunications Domain

83

problems. In addition, most applications reuse from infrastructural components (see below). A few applications, which present to the user network events and alarms, are derived by customization of the Alarm Browser OOF (ALB). ALB is a C++ framework which allows persistent storage, manipulation, and display of alarm records. Within the software infrastructure of the system (not shown in figure) smaller grain frameworks allow additional reuse and promote architecture. Frameworks from which server and GUI components are derived provide for architectural standardization and reuse of implementation for infrastructural services (e.g. events, directory services, application management).

5

Assessment Summary

The next step in our research was to gather data regarding the size of the software components which constitute the application frameworks under assessment. The analysis was then discussed with the project managers responsible for framework development in order to draw conclusions and add qualitative considerations.

5.1 Quantitative Reuse Analysis The data we present in this section try to answer two questions: Which reuse techniques have been most widely used to develop the company’s application frameworks (i.e. within the ‘core part’)? What is the relevance of each technique to the ‘typical’ solution delivered to the customer ? What is the customization effort for the different techniques in relation to the customer-perceived value ? 3 To answer the first question, we have listed the major subsystems or components, grouped by the customization technique they rely on, and provided a size indication (first three columns of Table 1 and Table 2). To measure the size in a programming language independent way, Function Points, calculated through backfiring, have been used ([21]). Then, to assess the ‘business relevance’ of each technique we measured the size of the customized solution for an average installation (fourth column in tables). The Function Points are again measured through backfiring. The last column is intended to provide further insight on the customization activities required, thus helping the reader have a better interpretation of the reported figures, and relate them to the effort required to perform the customization. The reuse analysis for the two case studies follows (see Table 1, “STM/AF Reuse Analysis” and Table 2, “SISM/AF Reuse Analysis”). The section is closed by a number of remarks which provide conclusions and additional qualitative considerations from the assessment team. 3

This specifically represents a starting point for further analysis on productivity and overall business effectiveness of reuse techniques

84

Giovanni Cortese et al.

Customization Technique

Subsystem/ Component

Core Asset Size (FPs)

Size of typical Custom Solution (FPs)

Table 1. STM/AF Reuse Analysis

OOF

DCC (BDT)

350

625

MVC

100

100

AOM

VBC + MFC

400

8200

4000

4000

AOM Applicati ons

MDR DCN, DCC, NSEC, TEDAC...

Customization requires C++ development of framework plug-ins. See remark in section ‘Component Libraries’) MVC is reused 4 times in the core itself (see ‘OOFs in the infrastructure’) Customization consists of instantiation of the metamodel. Size of custom solution seems very high. Though a relevant analysis effort is behind this customization, the figures are influenced by code generation (see ‘Effects of Code Generation’). See also remark on ‘Component Libraries’ The Metamodel ‘engine’ - reused black box

1575

1575

Generic applications - reused black box Graphical user interfaces - Customization is marginal rework specific to customer process, and configuration file definition Customization through creation of templates based on macro keywords. Macro expansion is done run-time (see ‘Effects of Code Generation’)

Property Based

All Views

725

845

Macro Processor

RSRE

700

800

RSRS

125

175

7975

16320

Totals

Notes

OOF

AOM

Subsystem/ Component

Core Asset Size (FPs)

Size of typical Custom Solution (FPs)

Customization Technique

Table 2. SISM/AF Reuse Analysis

VNM

770

2645

Infrastructure

820

820

ALB

452

691

NSI

1316

2150

3043

3043

350

628

AOM Applica- All (PerfMgr, tions TopoMgr, ...) Domain Spe- VNM SNMP, cific Scripting VNM TL1

Notes

Customization requires C++ development of framework plug-ins. See remark on ‘Component Libraries ’ See note ‘OOFs in the infrastructure’ There are three applications based on ALB The repository implementing the (meta)model, and all customizations of the model Generic applications, reused black box

Subsystem/ Component

Core Asset Size (FPs)

Size of typical Custom Solution (FPs)

Customization Technique

Building Customizable Frameworks for the Telecommunications Domain

Event Correlator

280

560

7031

10357

85

Notes

Languages

Property Based Macro Processor Totals

n.a.

Customization requires writing diagnostic rules for each network technology Considered marginal - all applications have already been accounted for in previous categories

n.a.

5.2 Conclusions Metamodels for large grain functional subsystems The basic evidence derived from this analysis is that AOMs have independently emerged as the preferred architectural approach for the design of large-grain reusable components in different product lines. However rough these figures may be, metamodels and generic applications based on the metamodel account for more than 65 percent of the software developed in the core of the two product lines (the relevance in custom solutions reaches higher than 70 percent). This trend is further proven by what is happening in the third company product line for Service Provisioning, recently established, whose architecture is centered on a workflow engine and a Network Service Inventory subsystem, both conceived as AOMs. Based on interviews with project managers, a strong driver for the choice of this technique is its ability to enable the design of an application which is highly customizable at run-time either by the end user or by Sodalia field staff. OOFs in the infrastructure The analysis has shown that OOFs are more widely adopted in the infrastructure (with a few important exceptions, e.g. VNM) than in the design of application subsystems, where the metamodel approach has shown a wider application. Examples include BDT, GUI framework, Generic Server Framework, MVC; they have been conceived to relieve application components from infrastructural tasks. Reuse Analysis shows that the relevance of OOFs in our assets is 16 percent in the core and 18 percent in the custom solution. It must be noticed that the Reuse Analysis tables, more focused on functional subsystems, are not fair to these type of components. In fact, infrastructural OOFs are actually reused many times in the framework itself, though not shown in the tables. In addition, their importance has been rated very high by the project manager due to the ‘enforcement of architecture’ they perform on the software system.

86

Giovanni Cortese et al.

Trend towards configurability in the user environment The assessment shows a ‘marginal’ dependency of the core and custom solution on scripting languages. Based on interviews with project managers, however, the importance of this mechanism is much higher than shown by the quantitative analysis. The current trend is to implement customizations, whenever feasible, through a mechanism which does not require availability of a complex development environment (e.g. C++). It should be possible to perform most configurations in the user environment (by properly ‘authorized’ personnel, such as an application administrator or support staff). Scripting languages are perceived as another important mechanism in addition to AOMs to address this business driver. Although not as powerful as the AOM approach, they result in a simpler design, thus enabling some degree of customization in the application architecture with limited risk and cost.

5.3 Other Remarks A few other comments, more related to the method we used to analyse and present the data, follow. Effects of Code Generation Being calculated through function point backfiring, the figures related to ‘custom solution size’ in the tables are sometimes biased by the effects of code generation. To be properly understood, the following considerations may help: when the technique used for customization relies on run-time expansion or interpretation of powerful domain abstractions, the reported size may underestimate the size in terms of ‘user-perceived functionality’ on the contrary, when code generation is involved, the reported figure may be higher than expected Component Libraries When creating a customization (e.g. an adapter for a new network technology), often the resulting component itself becomes a reusable part of the application framework. This applies both when the component is encoded as a C++ plug-in for an OOF, or is a new metamodel configuration. In the tables, however, for sake of simplicity, we always kept such components separate from the ‘core’ and counted them in the ‘custom’ part.

6

Future Research

The expected follow-up of this assessment will be in two main directions. Metamodelling infrastructure This analysis provides strong evidence that software and patterns which assist in the development of customizable software are themselves a strategic reusable asset in our business. We plan to generalize the patterns and software implementations discovered in the assessment, specifically those in support

Building Customizable Frameworks for the Telecommunications Domain

87

of metamodelling, with the objective of extending the company’s architectural guidelines and Reusable Asset Repository (See “Reusable Asset Repository and Sodalia Architectural Framework”) with a common flexible infrastructure for this type of application. Productivity and Cost Estimates Evidence emerged in this assessment regards the unavailability of reliable effort data allowing us to calculate the costs of implementation of the reusable core components. As these components have been developed over a number of project iterations, it proved too difficult to analyze the collected effort data in a coherent way. As product line development emerges as the most widely adopted software development process in the company, with a corresponding dramatic growth of the impact of reuse on software process metrics, we need to refine our practices in this area. A simple but effective framework for calculating software process metrics is a target for our future activities.

Acknowledgements Authors wish to thank M. Banzi for the help provided.

References 1. 2. 3. 4.

5. 6. 7. 8. 9.

Bushmann, F., et al. Pattern Oriented Software Architecture. John Wiley & Sons, 1996. Coplien, J.O., Schmidt, D.C. Pattern Languages of Program Design, vol. I. Addison-Wesley, 1995. Borioni, S., Marini, M.A Service Management Application framework: Business, Interoperability and Architectural requirements. Proceeding Interworking, 1998. Feldkhun, L., Marini, M., Borioni, S. Integrated Customer-Focused Network Management: Architectural Perspectives. Proceedings of the Fifth IFIP/IEEE International Symposium on Integrated Network Management, San Diego, California, USA, May 12-16, 1997. Gamma, E., Helm, R., Johnson, R., Vlissides, J. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1994. Johnson, R.E. Frameworks = (Components + Patterns). Communications of the ACM, October 1997, pp.71-77. Krasner, G.E., Pope, S.T. A Cookbook for Using the Model View Controller User Interface Paradigm in Smalltalk-80. Journal of Object Oriented programming, August, 1988. Martin, R., Riehle, D., Bushmann, F. Pattern Languages of Program Design, vol. III. Addison-Wesley, 1997. Object Management Group. The Common Object Request Broker: Architecture and Specification, Revision 2.0, July, 1995.

88

Giovanni Cortese et al.

10. Object Management Group. Common Object Services Specification, Volume 1. OMG Document Number 91-1- 1, Revision 1.0, March 1, 1994. 11. Taligent, Inc. Building object-oriented frameworks, 1994. 12. Vlissides, J., Coplien, J.O., Kerth, J.M. Pattern Languages of Program Design, vol. II. Addison-Wesley, 1996. 13. Willars, H. Amplification of Business Cognition through Modelling Techniques. Proceedings of the 11th IEA Congress, Paris, July 1991. 14. Wirfs-Brock, R.J., Johnsson, R.E. Surveying current research in object-oriented design. Communication of the ACM, 33(9), pp. 104- 124, September 1990. 15. Clements, P., Northrop, L. A Framework for Software Product Line Practice Version 2.0, July 1999 16. Cortese, G., Fregonese, G., Zorer, A. Architecture Architectural Framework Modeling in Telecommunication Domain. Proc. ICSE 99, May 1999 17. Fayad, M., Schmidt, D. Object Oriented Application Frameworks. CACM vol. 10. n 40, October 1997 18. Foote, B., Yoder, J. Metadata and Active Object Models. PLoP 98 19. Sodalia DE/NAM. Service Provisioning Tool System Architecture. Sodalia internal document, 1998. 20. Pree, W. Framework Patterns, SIGS Books and Multimedia, 1996 21. Jones, Capers. Backfiring: converting lines of code to function points. Computer Vol. 28, No 11, Nov. 1995, pp.87-88.

Object Oriented Analysis and Modeling for Families of Systems with UML Hassan Gomaa Department of Information and Software Engineering George Mason University Fairfax, VA 22030-4444, USA (703) 993 1652 [email protected]

Abstract. This paper describes how the Unified Modeling Language (UML) notation can be used to model families of systems. The use case model for the family is used to model kernel and optional use cases. The static model for the family is used to model kernel, optional and variant classes, as well as their relationships. The dynamic model for the family is used to model object interactions in support of kernel and optional use cases, and for modeling all state dependent kernel, optional, and variant objects using statecharts.

1

Introduction

A software reuse area of growing importance is that of domain engineering of families of systems [Parnas79], also referred to as software product lines, where an application domain is modeled by analyzing the common and variant aspects of the family [Coplien98, DeBaud99, Dionisi98, Kang90]. At George Mason University, a project is underway to support software engineering lifecycles, methods, and environments to support software reuse at the requirements and design phases of the software lifecycle, in addition to the coding phase. A reuse-oriented software lifecycle, the Evolutionary Domain Lifecycle [Gomaa95], has been proposed, which is a highly iterative lifecycle that takes an application domain perspective, allowing the development of families of systems. Earlier research addressed the analysis and specification phases of the Evolutionary Domain Life Cycle for developing families of concurrent and distributed applications. It also addressed the domain modeling environment developed at GMU to support configuring target systems from a domain model [Gomaa94, Gomaa96, Gomaa97]. The domain analysis and modeling method described in [Gomaa95] emphasizes analyzing the common and variant aspects of an application domain. This paper describes a new approach for analyzing and modeling a family of systems, which uses the Unified Modeling Language (UML) notation [Booch98, Rumbaugh99]. This paper starts by briefly describing the earlier Domain Analysis and Modeling method. It then describes how the UML notation for use case modeling, static modeling, and dynamic modeling can be used to model families of systems. Examples are given from a factory automation domain. W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 89-99, 2000.  Springer-Verlag Berlin Heidelberg 2000

90

Hassan Gomaa

2

Domain Modeling Method

A Domain Model is a multiple view object-oriented analysis model for the application domain that reflects the common aspects and variations among the members of the family of systems that constitute the domain. The domain modeling method [Gomaa95, Gomaa96] is similar to other object-oriented methods when used for analyzing and modeling a single system [e.g., Rumbaugh91]. Its novelty is the way it extends object-oriented methods to model families of systems. The method allows the explicit modeling of the similarities and variations in a family of systems. In a domain model, an application domain is represented by means of multiple views, such that each view presents a different perspective on the application domain. Four of the views, the aggregation hierarchy, the object communication diagrams, the generalization/specialization hierarchy, and the state transition diagrams have similar counterparts in other object-oriented methods used for modeling single systems. However, in the domain modeling method, the aggregation hierarchy is also used to model optional classes, which are used by some but not necessarily all members of the family of systems. Furthermore, the generalization / specialization hierarchy is also used to model variants of a class, which are used by different members of the family of systems. The fifth view, the feature/class dependency view, is used to represent explicitly the variations captured in the domain model. This view relates the end-user's perspective of the domain, namely the features (functional requirements) supported by the domain, to the classes in the domain model. It shows for each feature the classes required to support the feature. Also defined are any prerequisite features required and any mutually exclusive features. This view is particularly important for optional features, since it is the selection of the optional features, and the classes required to support them, that determine the nature of the desired target system.

3

Domain Modeling for Families of Systems with UML

Object-oriented concepts are considered important in software reuse and evolution because they address fundamental issues of adaptation and evolution. Object-oriented methods are based on the concepts of information hiding, classes, and inheritance. With the proliferation of notations and methods for the object-oriented analysis and design of software systems [Jacobson92, Rumbaugh91, etc.], the Unified Modeling Language (UML) is an attempt to provide a standardized notation for describing object-oriented models [Booch98, Jacobson99, Rumbaugh99]. However, for the UML notation to be effectively used, it needs to be used in conjunction with an object-oriented analysis and design method. The Object Oriented Analysis and Modeling method for single systems [Gomaa00] uses a combination of use cases [Jacobson92], object modeling [Rumbaugh91], statecharts [Harel96, Rumbaugh91], and event sequence diagrams used by several methods [Jacobson92, Rumbaugh91, etc.]. Next, consider how the UML notation may be used to model families of systems.

Object Oriented Analysis and Modeling for Families of Systems with UML

3.1

91

Use Case Model for Families of Systems

The functional requirements of the system are defined in terms of use cases and actors [Jacobson92]. An actor is a user type. A use case describes the sequence of interactions between the actor and the system, considered as a black box, to satisfy a functional requirement. For a single system, all use cases are required. When modeling a family of systems, only some use cases are required by all members of the family. These use cases are referred to as kernel use cases. Optional use cases are those use cases required by some but not all members of the family. Some use cases may be variant, that is different versions of the use case are required by different members of the family. The variant use cases are usually mutually exclusive. With the Kernel First Approach [Gomaa95], the kernel of the application domain is determined first. In other words, the common use cases that are used by all members of the family are determined first. The optional use cases are then determined iteratively. With the View Integration Approach [Gomaa95], which is most applicable when there are existing systems that can be analyzed, each system is considered a view of the application domain and the different views are integrated. In terms of use cases, this means that the use cases for each member of the family are specified. If the use cases do not exist, then it is necessary to develop them; in effect this is a reverse engineering exercise. After developing the use cases for each member of the family, the use cases from the different systems are compared. Common use cases to all members of the family constitute the kernel of the application domain. Uses cases that are only used by an individual system or a subset of the systems constitute the optional use cases. A kernel or optional use case may also be parameterized using variation points [Jacobson97]. An example of a use case model using the UML notation is given in Fig. 1. The Factory Operator actor uses two use cases View Alarms and Generate Alarm and Notify. Briefly, in the View Alarms use case the actor is the factory operator, who views outstanding alarms and acknowledges that the cause of an alarm is being attended to. In Generate Alarm and Notify, a robot generates an alarm and the operator is notified. 3.2

Static Model for Families of Systems

The static modeling notation is a rich notation for modeling classes and their relationships on class diagrams. It can thus be used for modeling the associations between classes (as done for single systems), as well as for modeling the hierarchies used in domain models for families of systems, namely the Aggregation Hierarchy and the Generalization / Specialization hierarchies (Section 2 and [Gomaa95]). A static model for an application domain has kernel classes, which are used by all members of the family, and optional classes that are used by some but not all members of the family of systems. Furthermore, a generalization / specialization hierarchy is used to model variants of a class, which are used by different members of the family of systems. UML stereotypes are used to allow new modeling elements,

92

Hassan Gomaa

tailored to the modeler’s problem, which are based on existing modeling elements [Booch98, Rumbaugh99]. Thus, the stereotypes <> and <> are used to distinguish between kernel and optional classes.

Pick and Place Robot

Generate Alarm and Notify Assembly Robot Factory Operator

View Alarms

Fig. 1. Example of Use Case Model

An example of an Aggregation Hierarchy from the factory automation domain is given in Fig. 2. The kernel factory aggregate class is composed of a kernel factory workstation class and an optional Automated Guided Vehicle Manager. An example of a generalization/specialization hierarchy is given in Fig. 3, in which the factory workstation class is specialized to support three variants, the flexible workstation, the high volume workstation, and the factory monitoring workstation. The way the static model for the family is developed depends on the strategy used for developing the domain model. With the View Integration Approach, a separate static model is developed for each member of the family. Each static model is considered a separate view of the application domain. The static model for the application domain is produced by integrating the individual views. If the Kernel First Approach is used, then the static model for the kernel is developed first and evolved as variations are considered for inclusion in the domain model. When static models for the different members (views) of the family are integrated, classes that are common to all members of the family are kernel classes of the integrated static model, which is referred to as the domain static model. Classes that are in one view but not others are optional classes of the domain static model. Classes that have some common aspects but also some differences are generalized. The common attributes and operations are captured in the superclass while the differences are captured in the variant subclasses of the superclass. 3.3

State Machine Model for Families of Systems

A statechart is developed for each state dependent object, including kernel, optional, and variant objects. There have been some attempts to model variations using

Object Oriented Analysis and Modeling for Families of Systems with UML

93

hierarchical statecharts, where the superstate is used to model the generalized aspects of the superclass while the substates are used to model the variations used in each subclass [Harel96]. <> Factory

0..*

1 <> Factory Workstation

<> Automated Guided Vehicle (AGV) Manager

Fig. 2. Example of Aggregation Hierarchy <> Factory Works tation

<> Flexible Workstation

<> High Volum e Workstation

<> Factory Moni torin g Workstation

Fig. 3. Example of Generalization / Specialization Hierarchy

State dependent control objects are depicted using statecharts. Since there can be variants of a control object, each variant is modeled using its own statechart. In this situation, the statecharts are all mutually exclusive as they model different variants. Each state dependent object would support a different feature and all the features would be mutually exclusive. For example, an automobile cruise control system may have a controlled deceleration feature or may not. Each of the alternative features is supported by a different Cruise Control object with a different statechart. The features (cruise control with controlled deceleration, cruise control without controlled deceleration) are mutually exclusive. However, it is possible in some applications for the variant features not to be mutually exclusive. Consider an Elevator Control System where there are multiple elevators, and where some elevators have a high speed feature for bypassing the first twenty floors and other do not. This case would again be represented by two different features, where each type of elevator is modeled using a different statechart. However, since the two elevators can co-exist in the same

94

Hassan Gomaa

system, in this case it is possible to select both features (for different elevators) and hence to have co-existing variant statecharts. An example of a statechart is given in Fig. 4 for a state dependent control class, namely the High Volume Workstation variant class (depicted in Fig. 3). Workstation Startup / Part Request

Awaiting Part from Predecessor Workstation

Part Coming / Next Operation Request

Part Arriving

Part Arrived / Robot Pick

Part Ready / Start Assembly

Robot Picking

Operation End [Part Requested] / Robot Place

Part Placed / Part Coming, Part Request

Robot Placing

Assembling Part

Operation End [Part Not Requested]

Part Request / Robot Place

Awaiting Part Request From Successor Workstation

Fig. 4. Example of statechart 3.4

Collaboration Model for Families of Systems

As with single systems, the collaboration model is used to depict the objects that participate in each use case, and the sequence of messages passed between them [Booch98, Jacobson99]. In families of systems, the collaboration model is developed for each use case, kernel or optional. Once the use cases have been determined and categorized as kernel, optional, or variant, the collaboration diagrams can be developed. Fig. 5 shows the collaboration diagram for the View Alarms use case depicted in Fig. 1. This is a simple client/server use case [Gomaa98] involving a client object and a server object. S1: Operator Request

S1.1: Alarm Request Alarm Handling Server

Operator Interface m : Operator Interface S1.2: Alarm Data

S1.3: Display Info : Factory Operator

Fig. 5. Example of Collaboration Diagram

In the domain modeling method [Gomaa95], for each feature, the objects that are needed to support the feature are determined and depicted on a feature based object communication diagram, which is similar to a collaboration diagram. With this UML based approach, the objects are determined from the use cases. The relationship between use cases and features is described in Section 5.

Object Oriented Analysis and Modeling for Families of Systems with UML

4

95

Feature Analysis

Feature analysis is an important aspect of domain analysis [Cohen98, Gomaa95, Griss98, Dionisi98, Kang90]. In the FODA (Feature-Oriented Domain Analysis) method [Cohen98, Kang90], features are organized into a feature tree. In FODA, features may be mandatory (kernel), optional, or mutually exclusive. The tree is an aggregation hierarchy of features, where some branches are kernel, some are optional, and others are mutually exclusive. In FODA, features may be functional features (hardware or software), non-functional features (e.g., relating to security or performance), or parameters (e.g., red, yellow, or green). Features higher up in the tree are composite features if they contain other lower level features. In the domain modeling method, for each feature, this view shows the classes required to support the feature [Gomaa95]. In domain analysis, features are analyzed and categorized as kernel features (must be supported in all target systems), optional features (only required in some target systems), and prerequisite features (dependent upon other features). There may also be dependencies among features, as described below. This view emphasizes optional features, because it is the selection of the optional features, and the classes required to support them, that determines the nature of the desired target system. Feature/class dependencies may be modeled in UML using the package notation, where a package is a grouping of model elements [Booch98]. An example of feature/class dependencies for the factory automation domain is given in Fig. 6. The High Volume Manufacturing feature is depicted as a package with the stereotype <>, which groups the three optional classes that support this feature, the Receiving Workstation, the Line Workstation, and the Assembly Workstation. «feature» High Volume Manufacturing

«optional» Receiving Workstation

«optional»

«optional»

Line Workstation

Shipping Workstation

Fig. 6. Example of Feature/Class Dependency

5

Features and Use Cases

In the object-oriented analysis of single systems, use cases are used to determine the functional features of a system. They can also serve this purpose in families of systems. Griss [Griss98] has pointed out that the goal of the use case analysis is to get a good understanding of the functional requirements whereas the goal of feature

96

Hassan Gomaa

analysis is to enable reuse. The emphasis in feature analysis is on the optional features, since the optional features differentiate one member of the family from the others. Use cases and features may be used to complement each other. In particular, use cases can be mapped to features based on their reuse properties. In the Domain Modeling Method [Gomaa94, Gomaa95], functional requirements that are required by all members of the family are packaged into a kernel feature. From a use case perspective, this means that the kernel use cases, which are required by all members of the family, constitute the kernel feature. Optional use cases, which are always used together, may also be packaged into an optional feature. For example, the two use cases shown in Fig. 1 could be packaged into an Alarm Handling feature, as shown in Fig. 7.

<> Alarm Handling

Pick and Place Robot

Generate Alarm and Notify Assembly Robot Factory Operator

View Alarms

Fig. 7. Feature As Use Case Package

In the UML, use case relationships can also be specified. Thus, common functionality among several use cases can be split off into an abstract use case, which can then be included in other use cases. This dependency among use cases is analogous to feature dependency, where one feature may require another feature as a prerequisite. Thus in the factory automation domain, High Volume Manufacturing and Flexible Manufacturing are optional use cases. However, the common functionality among the two use cases is split off into an abstract use case called Factory Production. The abstract use case is used by the other two, now more concise, use cases (Fig. 8). Based on this, we can choose to have features corresponding to each of these use cases, where the High Volume Manufacturing and Flexible Manufacturing features both require the Factory Production feature. Another form of use case relationship is the extend relationship, where one use case may extend another when certain conditions hold. In the example, the Flexible Manufacturing with Storage use case can be used to extend the Flexible Manufacturing use case (Fig. 8). Thus, introducing intermediate part storage in the

Object Oriented Analysis and Modeling for Families of Systems with UML

97

factory is an extension of the case where no intermediate part storage is provided. As before, each use case is mapped to a feature where the Flexible Manufacturing with Storage feature requires the Flexible Manufacturing feature. Factory Production

<>

High Volume Manufacturing

<>

Flexible Manufacturing

<<extend>>

Flexible Manufacturing with Storage

Fig. 8. Use Case Dependencies and Feature Dependencies

6

Target System Configuration

The analysis model for the target system is configured from the domain model by selecting the desired optional features subject to the feature/feature constraints [Gomaa94, Gomaa96]. Kernel features are automatically included. With the UML based domain modeling method, the analysis model for the target system consists of all kernel use cases and the optional use cases that correspond to the optional features. In addition, the analysis model for the target system includes the object collaboration diagrams that correspond to the selected use cases and a tailored class diagram that includes all kernel classes and those optional classes that support the selected features.

7

Conclusions

This paper has described how the Unified Modeling Notation can be used to model families of systems. The use case model for the family is used to model kernel and optional use cases. The static model for the family is used to model kernel, optional and variant classes, as well as their relationships. It is also used for modeling feature dependencies. The dynamic model for the family is used to model object interactions in support of kernel and optional use cases, and for modeling all state dependent kernel, optional, and variant objects using statecharts. Future plans include developing a second generation knowledge based software engineering environment [Gomaa94, Gomaa96, Gomaa97] for generating target system analysis models and architectures from the UML based domain model for the family of systems.

98

Hassan Gomaa

References [Booch98] [Cohen98] [Coplien98] [DeBaud99] [Dionisi98] [Gomaa94]

[Gomaa95] [Gomaa96]

[Gomaa97]

[Gomaa00] [Griss98] [Harel96] [Jacobson92] [Jacobson97] [Kang 90]

G. Booch, J. Rumbaugh, I. Jacobson, “The Unified Modeling Language User Guide”, Addison Wesley, Reading MA, 1999. S. Cohen and L. Northrop, “Object-Oriented Technology and Domain Analysis”, Proc. International Conference on Software Reuse, Victoria, June 1998. J. Coplien, D. Hoffman, D. Weiss, “Commonality and Variability in Software Engineering”, IEEE Software, Nov/Dec 1998. J.M. DeBaud and K. Schmid, “A Systematic Approach to Derive the Scope of Software Product Lines”, Proc. IEEE Intl. Conf. Soft. Eng., LA, May, 1999. A. Dionisi et al., “FODAcom: An Experience with Domain Modeling in the Italian Telecom Industry”, Proc. Intl. Conf. Software Reuse, Victoria, June 1998. H. Gomaa , L. Kerschberg, V. Sugumaran, C. Bosch, I Tavakoli, “A Prototype Domain Modeling Environment for Reusable Software Architectures,” Proc. IEEE Intl. Conf. on Software Reuse, Rio de Janeiro, Brazil, November 1994. Gomaa H, "Reusable Software Requirements and Architectures for Families of Systems", Journal of Systems and Software, May 1995. H. Gomaa, L. Kerschberg, V. Sugumaran, C. Bosch, I Tavakoli, "A Knowledge-Based Software Engineering Environment for Reusable Software Requirements and Architectures," J. Auto. Softw. Eng., Vol. 3, Nos. 3/4, Aug. 1996. H. Gomaa and G. Farrukh, “Automated Configuration of Distributed Applications from Reusable Software Architectures”, Proc. IEEE International Conference on Automated Software Engineering, Lake Tahoe, November 1997. H. Gomaa, "Designing Concurrent, Distributed, and Real-Time Applications with UML", Addison Wesley, Reading MA, 2000. M. Griss, J. Favaro, M. D’Alessandro, “Integrating Feature Modeling with the RSEB”, Proc. International Conference on Software Reuse, Victoria, June 1998. Harel, D. and E. Gary, “Executable Object Modeling with Statecharts”, Proc. 18th International Conference on Software Engineering, Berlin, March 1996. I. Jacobson et. al., Object-Oriented Software Engineering, Addison Wesley, Reading MA, 1992. I. Jacobson, M. Griss, P. Jonsson, “Software Reuse - Architecture, Process and Organization for Business Success”, Addison Wesley, 1997. Kang K. C. et. al., “Feature-Oriented Domain Analysis,” Technical Report No. CMU/SEI-90-TR-21, Software Engineering Institute, November 1990.

Object Oriented Analysis and Modeling for Families of Systems with UML

[Parnas79]

99

Parnas D., “Designing Software for Ease of Extension and Contraction,” IEEE Transactions on Software Engineering, March 1979. [Rumbaugh91] Rumbaugh, J., et al., “Object-Oriented Modeling and Design," Prentice Hall, 1991. [Rumbaugh99] J. Rumbaugh, G. Booch, I. Jacobson, “The Unified Modeling Language Reference Manual,” Addison Wesley, Reading MA, 1999.

Framework-Based Applications: From Incremental Development to Incremental Reasoning Neelam Soundarajan and Stephen Fridella Computer and Information Science, The Ohio State University Columbus, OH 43210 {neelam,fridella}@cis.ohio-state.edu

Abstract. Object-oriented frameworks provide a powerful technique for developing groups of related applications. The framework includes one or more template methods that at appropriate points call various hook methods. Each application built on a framework reuses the template methods provided by the framework; the application developer provides definitions, tailored to the needs of the particular application, for only the hook methods. Our goal is to develop a technique for reasoning in which we reason about the framework behavior just once; whenever a new application A is developed, we arrive at its behavior by composing the behavior of hook methods defined in A with the behavior of the framework. Just as the template methods allow the application developers to reuse the code of the framework, our technique allows them to reuse the effort involved in reasoning about the framework in understanding each application built on the framework. We illustrate the technique by applying it to a simple example, and contrast our approach with a more standard approach based on behavioral subtyping.

1

Introduction

Object-oriented frameworks [5,12] provide a powerful technique for developing groups of similar or related applications. The framework designer designs the main classes and methods, including in particular the key methods that direct the flow of control, and call appropriate methods of various classes. One or more of the called methods will be virtual1 or pure virtual; indeed, one or more of the classes may just be interfaces (abstract base classes in C++ terminology), i.e., consist entirely of pure virtual methods. In the patterns literature [6], the method(s) directing the flow of control are called template methods, and the (pure) virtual methods that they invoke, hook methods. In order to implement a complete application based on this framework, the application developer would provide suitable definitions for all the hook methods; a different developer could 1

For concreteness we often use C++/Java-terminology, but our approach is not language specific.

W. B. Frakes (Ed.): ICSR-6, LNCS 1844, pp. 100–116, 2000. c Springer-Verlag Berlin Heidelberg 2000


Framework-Based Applications

101

produce a (possibly very) different application by providing an alternate set of definitions for the hook methods. If the framework has been designed carefully and provides the right hooks, an entire new application can be developed with just the incremental effort involved in designing a new set of hook methods. In this paper we develop a similarly incremental technique for reasoning about the framework and the applications. Using our technique, we would reason about the framework behavior just once; every time a new application is developed using this framework, we would incrementally arrive at the behavior of this application by first reasoning about the behavior of the newly defined hook methods, and then plugging this behavior into the behavior of the framework. The key idea underlying our approach that makes this possible is the notion of the hook method call trace; with each template method we associate such a trace and record on it, information about every call the template method makes to a hook method. As we will see, specifying the behavior of the template method not just in terms of the member variables of the class but also in terms of this trace, allows us to plug-in the behavior of the hook methods as defined in the derived class, to arrive at the application-specific behavior. By contrast, the standard approach to dealing with applications built on OO frameworks, based on the notion of behavioral subtyping [9,10], focuses on just the behavior provided by the framework. The main contributions of this paper may be summarized as follows: – It makes the case that behavioral subtyping by itself is not sufficient to deal with framework-based applications since it is concerned only with behavior that is common to all the applications based on the given framework, completely ignoring application-specific behavior. – It presents a specification notation and reasoning technique using which we can include sufficient information in the specifications of template methods, so that information about the behavior of hook methods –as defined in the application– can be plugged-in, to arrive at specifications appropriate to the particular application. – It illustrates the approach by applying it to a simple example. The rest of the paper is organized as follows: In Section 2, we summarize the behavioral subtyping approach to dealing with framework-based applications. In Section 3 we consider, via a simple framework and several applications that might be built on it, what additional information needs to be included in specifications of template methods, and how this may be done. In Section 4 we see how application-specific information about the hook methods may be plugged into the specification of the template methods. Throughout, our focus is on motivating and intuitively justifying our approach rather than just the formal details. In Section 5 we apply the approach to a simple example, a continuation of the one used in Section 3. In the final section we reiterate the need for going beyond behavioral subtyping in dealing with frameworks, summarize how our approach does so, and point out problems that remain to be addressed.

102

2

Neelam Soundarajan and Stephen Fridella

Behavioral Subtyping

Consider a simple situation: the framework consists of a single class C that has one non-virtual method t() and one virtual2 method h(); C may also include one or more data members. In the design patterns terminology, t() is a template method and it invokes (one or more times) the hook method h(). In order to develop an ‘application’ using this framework, the developer would define a derived class D of C that would provide a definition for h(). A client programmer who wishes to use this application would create an object X of type D and invoke the method t() on it. OO polymorphism will ensure that during this execution of t(), the invocations of h() will in fact call the method defined in D, so that this call to t() will exhibit the behavior appropriate for the particular application. The standard approach, based on the notion of behavioral subtyping [9,10], to specifying such a framework may be summarized as follows: First arrive at a specification St for the template method t(). This specification consisting in the usual manner of pre- and post-conditions, will give us the effect that an execution of the method has on the values of member variables of C. Also provide a specification Sh for the hook method h(), specifying its effect on the values of the member variables of C. Next, validate the specification St –either formally or informally– by analyzing the body of t() as given by its definition in the class C. During this analysis, make use of the specification Sh for analyzing the effects of the calls to h() that appear in t(). If C does not provide a definition for h() (so h() is a pure virtual method in C), then we are done with reasoning about C. If C does include a definition for h() (so the framework C is, by itself, a complete application), then ensure that this definition satisfies the specification Sh . Next, when we develop an application by defining a derived class D of C and providing a definition in D for the method h(), arrive at a specification Sh corresponding to this h(), check that the h() defined in D satisfies Sh , and show that Sh is consistent with Sh ; more precisely, show that any method that satisfies Sh must necessarily also satisfy Sh . The last step of showing that Sh is consistent with Sh , is crucial to the approach. It ensures that D is a behavioral subtype of C, in other words that the behavior that methods of D exhibit is consistent with the behavior of the methods of C as specified by St and Sh . As a result, we can be sure, without any reanalysis, that t() will satisfy St even though the calls to h() that this t() makes will be to the h() defined in D, rather than the one defined in C. This 2

In Java and Eiffel all methods are virtual by default, and the non-virtual methods, that is those that are not to be redefined in the application, are flagged as final; in C++, final is the default, and virtual methods are so flagged. Even methods that are not flagged as virtual in C++ can be redefined in the derived classes but these redefinitions will not be visible in the base class C; i.e., any calls in t() to such an h() will invoke the one defined in C, not the redefinition in the derived class.

Framework-Based Applications

103

is because in our previous analysis of t() to check that it satisfies St , the only assumption we made about h() was that it would satisfy the specification Sh . While this is valid, it ignores an important point: the power of frameworks derives from the fact that the application developer can, when he3 defines the hook method h() in the class D, tailor the definition to suit the needs of the particular application; OO polymorphism ensures that although the definition of t() is inherited from the framework, as far as clients of this application are concerned, the h() that will be invoked during the execution of t() will be the one defined in D; hence t() will exhibit the behavior tailored to this application. But the specification St is not so tailored; rather, it is written to be valid for all applications that are built on this framework. In other words, as far as the behavioral subtyping approach is concerned, there is no difference between the different applications that may be built on this framework! What we need, then, is a specification of t() that can be tailored to the individual D by plugging-in the specification of h() corresponding to that particular D. Such a specification will capture the unique (as well as the common) behavior provided by that application. This is very important to the client because the reason he chose to use this application rather than one of the others is to exploit the unique behavior provided by this application. Thus a specification technique that brings out the unique behaviors in the different applications built on a common framework is key to utilizing the power of the framework approach; ‘vive la difference’, so to speak! We conclude this section with a note about one point that we have ignored so far – abstraction. Clients of classes should not be concerned with internal details of member variables of the class, or how the methods modify the values of these variables. The standard way [7] of addressing this is to have two specifications, a concrete one for the class designer/implementor, and an abstract one for the client. All of this applies in a standard manner to the reasoning technique we develop, and hence we omit further discussion of it, using only concrete specifications throughout. Once the concrete specification has been obtained for an application, we can provide an abstract specification for it and relate it to the concrete specification in the standard manner.

3

Specifying the Framework

What extra information do we need to include in the specification of a template method t() so that we can plug in appropriate information about the hook method from the application? The example framework we consider next and the applications that may be built on it, will help us answer this question. Our example is a simple banking framework, specifically a general type of bank account. The definition4 of the BankAccount class appears in Figure 1. Deposit and Withdraw, as their names suggest, are used to deposit money into and withdraw 3 4

Following standard practice, we use ‘he’, ‘his’, etc. as abbreviations for ‘he or she’, ‘his or her’ etc. For concreteness, we use a Java-style syntax in examples.

104

Neelam Soundarajan and Stephen Fridella

class BankAccount { protected int bal; // current account balance protected nmonthly; // no. of monthly transactions protected Array monthlies; // transactions which happen every month

}

BankAccount(int b) { bal = b; monthlies.init(0); nmonthlies = 0; } public void Deposit(int amt) { bal = bal + amt; } public void Withdraw(int amt) { bal = bal − amt; } public final int GetBalance() { return bal; } public final void AddMonthly(int amt) { if (monthlies.size() <= nmonthlies) { monthlies.grow(5); } monthlies[nmonthlies++] = amt; } public final void NewMonth() { for (int i = 0; i < nmonthlies; i++) { if (monthlies[i] > 0) { this.Deposit(monthlies[i]); } else { this.Withdraw(−monthlies[i]); } } }

Fig. 1. Class BankAccount

money from the account. It is expected that the application designer will provide alternate definitions for these two methods tailored to the kind of bank account needed for his particular application, which is why these are not flagged as final. monthlies[] is an array of transactions that are expected to be performed once every month; new transactions may be added to this array by calling the AddMonthly method. NewMonth is the method that will perform all the transactions in this array and is expected to be invoked once a month. When NewMonth is invoked, it does not directly update bal, but instead calls Deposit and Withdraw to perform the transactions; so if the application developer provides new definitions for Deposit and/or Withdraw, NewMonth will invoke these newly defined methods. Thus NewMonth is the template method of our framework and Deposit and Withdraw the hook methods. How do we specify the behavior of these methods? We will use f(x).pre and f(x).post to denote the pre-condition and post-condition respectively of a method f(), x being the parameter to the method. Consider the Deposit method: Deposit(amt).pre ≡ true Deposit(amt).post ≡ (bal = #bal + amt) ∧ !{nmonthlies, monthlies, amt}

(1)

Framework-Based Applications

105

As usual, pre-conditions are assertions on the state of the object and parameters immediately before the method is invoked5 ; post-conditions are assertions over the state immediately before and immediately after a method is invoked. The specification states that if the pre-condition holds for the state before a method invocation, then the post-condition is guaranteed to hold over that same state and the state when the method finishes. In our post-conditions, we use the notation #var to refer to the value of a variable in the state before invocation and var to refer to the variable’s value in the final state. Writing the name of a variable within braces preceded by “!” is a shorthand way of specifying that the value of that variable is the same in the initial and final states. Thus the post-condition above asserts that Deposit updates bal as expected, and does not affect the array of monthly transactions, the number of those transactions, or the amt parameter. Withdraw can be specified similarly. What of the template method? How do we specify its behavior? A specification similar to that of Deposit would look like: NewMonth().pre ≡ true NewMonth().post ≡ nmonthlies−1 monthlies[i]) (bal = #bal + Σi=0 ∧ !{nmonthlies, monthlies}

(2)

This states that bal will be updated to account for all the deposits and withdrawals in monthlies[], and the other variables unaffected. But this specification will not be sufficient from the point of view of the application designer. It does summarize the effect of the NewMonth method on the variables of BankAccount, but it makes no mention of the fact that NewMonth calls the hook methods Deposit and Withdraw. Why is this information important? An example ‘application’ will tell us. Suppose the application designer wants to create a a promotional account. Perhaps the bank has entered into a promotional agreement with an airline to offer frequent flier miles to the bank’s customers; the more a customer uses his account, the more miles he earns. The designer can implement this as class PromoAccount that inherits from BankAccount, adds a data member miles which stores the number of miles accumulated by a customer, and methods for getting and resetting this value. Most importantly, PromoAccount would include new versions of Deposit and Withdraw which update miles appropriately. A simple scheme that awards twenty-five miles for each transaction is easily implemented, as in Figure 2. PromoAccount will inherit BankAccount’s facilities for monthly scripted transactions. Moreover, since NewMonth invokes the hook methods Deposit and Withdraw to perform these transactions, the frequent filer miles total for the account will be properly updated which, of course, is the whole point of the example. 5

In a real system, we would have included the clause amt > 0 in the pre-condition of Deposit. In order to keep specifications simple, we omit this clause. This does not compromise correctness, it just means that our Deposit method does not assume that the amt to be deposited will necessarily be positive.

106

Neelam Soundarajan and Stephen Fridella

public class PromoAccount extends BankAccount { protected int miles; // no. of miles earned PromoAccount(int b) { miles = 0; super(b); } public void Deposit(int amt) { super.Deposit(amt); miles += 25; } public void Withdraw(int amt) { super.Withdraw(amt); miles += 25; } }

Fig. 2. Class PromoAccount

But we cannnot arrive at this conclusion from the specification (2) since it does not tell us that NewMonth invokes Deposit or Withdraw, so there is no way to know what effect NewMonth may have on miles. The application designer might even conclude (incorrectly) from (2) that NewMonth will have no effect on miles, and provide a new body for this method in PromoAccount to ensure correct updating of miles. (This would not just lead to unnecessary work– if the new body first calls the base class version to perform the transactions, and then updates the milage total, the account would receive twice as many miles as it should . . . a bug!) Hence, specifications of template methods should contain at least the following information: – Names of the hook methods it invokes. – Number of times it invokes each hook method. Given this information, the designer could mentally “plug-in” the behavior of the new versions of the hook methods to conclude that NewMonth, as defined in the framework, will update miles appropriately. Are these two pieces of information always sufficient? Unfortunately, the answer is no. Suppose the application designer wanted to use a more complicated scheme for awarding miles; suppose, for example, that in order to encourage deposits and discourage withdrawals, the designer deems that each successive deposit would result in an award of double the number of miles awarded by the previous deposit. However, a withdrawal results in no miles being awarded and a resetting of the “deposit award” to twenty-five. Such a scheme could be easily coded, but now even if the specification of NewMonth said that Deposit and Withdraw are called once for each positive and negative element respectively in the monthlies array, the application designer would be unable to reliably conclude how many miles are awarded by a particular call to NewMonth. The problem is that, quite possibly, NewMonth might perform all the deposits before all the withdrawals (the application designer cannot rule this out based on the specification we just considered), and a much different number of miles may be awarded than if NewMonth, as is actually the case, performs the deposits and withdrawals in the order that they appear in the monthlies array. Hence, in general, we need another piece of information to be added to the specification of a template method: – The interleaving of the calls to the hook methods.

Framework-Based Applications

107

And we are still not quite finished. Still more mileage schemes can be envisioned. For example, suppose twenty-five miles are given for both deposits and withdrawals, but not if the withdrawal overdraws the account. In such a case, knowing only the interleaving of the calls to Deposit and Withdraw would not allow the designer to figure out whether one of the calls to Withdraw would result in an overdraft. For this, the specification of NewMonth would have to include information about the parameters of each call to the hook method (e.g.,the parameters to each call are the corresponding values in the monthlies array) as well as information about the value of bal –in general the state of the object– immediately preceeding each call to a hook method. Similar arguments can be made to show that we may also need to know about the state immediately after the hook method’s return. So we have a fourth kind of information that should be present in the specification of a template method: – The state of the object and parameters immediately before and after each hook method call. How do we include information about these four items in the specification of a template method? With each such method t, we associate a hook method call trace, τ . In this variable we record the interactions between the template method t and the hook methods it invokes. τ will be a sequence; each of its elements will represent a single call to (and return from) a hook method; these elements will be in the same order as the hook method calls. A call to the hook method h() will be represented as the element (h, σ  , aa , σ, aa) in the trace τ ; the first component of this element is the identity of the hook method being called; the second component, σ  , is the state immediately prior to the call to h(); the third, aa , is the set of values of the arguments passed to h() in this call; the fourth, σ, is the state immediately after the return from h(); and the fifth, aa, is the set of values of the arguments upon return from h(). τ will have the value , the empty sequence, at the start of t (since at its start, t has not yet invoked any hook methods). The specification of t will include assertions about the form and content of τ as well as relations among the various elements of τ , and with the final state of the class when t finishes as well as any values t may return. In the worst case the resulting specifications can be unwieldy, but in practice for most frameworks the needed information can be expressed in a fairly concise and comprehensible manner. It is useful to note what is not included in τ . No information about the sequence of operations that the template method performs between successive calls to the hook methods is recorded; also not recorded are calls to non-hook methods that the template method might make. In other words, information about the state of the object is recorded only at those points where the template method interacts with the hook methods. This is precisely the information the application designer needs in order to arrive at the complete behavior of the template method once he has specified the behavior of the hook method bodies as defined in his specific application.

108

4

Neelam Soundarajan and Stephen Fridella

Incremental Reasoning

In this section we present our reasoning technique. We discuss both reasoning performed by the framework designer and that performed by the application developer who uses the framework. For his part, the framework designer must check that the pre- and post-condition specification for each method of the framework is implemented correctly by the code, in the framework, for that method. Similarly, the application developer must check that each method code defined in his derived class meets its specification. But this developer has two additional tasks: he must ensure that each of these methods continues to satisfy its base class specification; and he must arrive at the richer specification for template methods by plugging-in the enriched behavior of the hook methods. Our approach is essentially an extension of standard axiomatic reasoning techniques, see, for example [1]. Considering first the task of framework designer, we need a rule to deal with calls to hook methods. The standard rule for method calls is adequate for dealing with calls to non-hook methods but for calls to hook methods we need a new rule –R1 below– that would take account of recording the call on the trace τ . In this rule, σ represents the state of the object, i.e., the values of all member variables of the class; last(τ ) is the last element of τ ; and abl(τ ) is the sequence that contains all elements of τ but the last one: R1. Hook Method Call Rule p ⇒ h(x).prexaa σ, aa #σ, #x, x [(∃σ  , aa ).[ pτ, abl(τ ), σ
, aa
∧ h(x).postσ
, aa
, aa   ∧ last(τ ) = (h, σ , aa , σ, aa) ] ] ⇒ q { p } this.h(aa); { q } The first antecedent of R1 requires that p (which is an assertion summarizing what we know about the state immediately before h is invoked) must imply the pre-condition of h (with the actual parameter aa substituted for the formal parameter x). The second antecedent ensures that we have added a new element to τ corresponding to this call and that the state at this point (and the returned values of the arguments) satisfy the post-condition of h. In more detail, the left side of this antecedent asserts that the state (and argument values) that existed immediately before the call and the trace, less its last element, satisfy the precondition; the post-condition of h is satisfied with appropriate substitutions for the before- and after-states and argument values; and that the (newly added) last element of τ consists of the name of the called method (h), the state (σ  ) immediately before the call, the initial value (aa ) of the parameter, the state (σ) immediately after the return from h, and the final value of the parameter (aa). Note that the post-condition of h that this rule refers to is the one provided with the framework, not any application-specific post-condition (which we do not yet have, since we do not yet have any applications). How can we be sure that this reasoning remains valid when the application designer redefines the hook method h()? This is part of the reasoning responsibility of the application designer, and the behavioral subtyping rule R2 will

Framework-Based Applications

109

allow this designer to ensure this. We first introduce some notation: Let F denote the framework and A the application we are interested in. Let h.f.pre, h.f.post

denote the pre- and post-conditions of the hook method h as specified in the framework, and h.a.pre, h.a.post the pre- and post-conditions we wish to establish for h in the application. We will use F :: h.f.pre, h.f.post to denote that this specification has been established for the framework F , and a similar notation for the application. R2. Behavioral Subtyping (for Hook Methods) F :: h.f.pre, h.f.post

{h.a.pre} A.H {h.a.post} h.f.pre ⇒ h.a.pre, h.a.post ⇒ h.f.post A :: h.a.pre, h.a.post

The first antecedent requires the appropriate specification to have been established for the framework. A.H is the body of the hook method as defined in the application; the second antecedent requires us to reason about this body using the application-specific pre- and post-conditions. The third antecedent imposes the behavioral subtyping requirements. In the interest of keeping the presentation simple, we have not allowed for parameters to h in this rule, but it would be straightforward to do so. Also in the interest of simplifying the presentation, we have not included class invariants. Note however, that class invariants are especially important if h.a.pre imposes any conditions on member variables introduced in the derived class, since h.f.pre cannot ensure such conditions. Our final rule will allow the application designer to establish an applicationspecific behavior for a template method t by plugging into the framework specification of t, the application-specific behaviors of the hook methods that t invokes. This “plugging-in” can often be done informally by the designer as long as a few key facts are kept in mind: First, the behavior of the hook method as defined in the application must be consistent with its behavior specified in the framework; this is the behavioral subtyping condition imposed by R2. Second, the application-specific data members introduced in a derived class cannot be affected by t except by calls to hook methods; in other words, the only changes that happen to the values of these data members during the execution of t are because of calls that t makes to the hook methods defined in the derived classes. Third, the state immediately before a call to a hook method h and the state immediately after the call will be re