Automata-theoretic approach compiler for adaptive software

Abstract

A compiler which generates object-oriented code from high level models is disclosed. The compiler uses a class graph to construct a finite intermediate automaton which is used in conjunction with an adaptive program to generate an object-oriented program in a target language. The intermediate automaton enables general case compilation of most combinations of adaptive programs and class graphs. The automaton also enables use of standard minimization techniques which reduce the size of the generated object-oriented code.

Claims

What is claimed is:

1. A compiler for providing software code in a target object-oriented language from an adaptive program and a class graph, comprising:

an automata generator operative to provide a traversal automaton representative of a selected set of paths in the class graph, said automata generator providing said traversal automaton from a traversal specification in the adaptive program and the class graph, wherein

said traversal automaton is a non-deterministic finite state automaton which is transformed into a minimal deterministic finite state automaton for the purpose of code generation and said automaton is a generalized automaton which contains state transitions of the form:

{n}x where n is a set of numbers and x is a part to be traversed, set n controlling the circumstances under which x is traversed such that a source s* and target t* are added to said traversal automaton and further wherein all nodes are marked which are reachable from s* and from which t* is reachable; and

a Traversal Method Algorithm ("TMA") operative to associate said traversal automaton with operations defined in the adaptive program, thereby translating said adaptive program into a traversal-state-passing program in the target language,

whereby the traversal specification of the adaptive program does not need to satisfy constraints with respect to the class graph, and hence said compiler is a general compiler.

2. The compiler of claim 1 wherein the traversal specification of said adaptive program is a general directed graph with a constraint map, wherein a constraint map assigns class graph element exclusion constraints to the edges of the traversal specification.

3. The compiler of claim 1 wherein said class graph corresponds to a Unified Modeling Language class diagram or a Demeter class dictionary.

4. The compiler of claim 1 wherein said target language is an object-oriented target language selected from the group consisting of Java, C++, SmallTalk and CLOS.

5. The compiler of claim 2 wherein the traversal automaton is constructed by making k copies of the class graph, where k is the number of edges in the traversal specification.

6. The compiler of claim 2 wherein tokens are used as parameters to the traversal methods algorithm, and each token is a node in the traversal automaton.

7. The compiler of claim 6, wherein each hop in the class object graph updates the tokens based on the edges in the traversal automaton.

8. The compiler of claim 7, wherein the TMA is used to generate target code.

9. The compiler of claim 3 wherein said code generator is operative to provide a finite state automaton Auto.PHI.(A,B), wherein V.sub.in and V.sub.out are two distinguished copies of V where elements are subscripted by in and out, respectively, .PHI.=(V,E) is a class graph, and A, B.epsilon.V, such that Auto.PHI.(A,B) includes:

a set of states being V.sub.in .orgate.V.sub.out ;

an alphabet being V.orgate.N.orgate.{.diamond.};

a start state being A.sub.in ;

a single accept state being B.sub.out ; and

transitions being: ##EQU18## 10.

10. The compiler of claim 2 wherein the traversal specification of said adaptive program satisfies the grammar:

D::=›A,!.vertline.D.D

and where the compilation algorithm has been modified to keep all automata deterministic, resulting in a polynomial time algorithm.

Description

FIELD OF THE INVENTION

The present invention relates generally to compilers for computer software, and more particularly to compilers for adaptive software.

BACKGROUND

Adaptive software systems are used in conjunction with object-oriented programming languages to produce object-oriented programs which adapt automatically to changes in class structure. In general this automatic adaptation is possible because adaptive software exists at a higher level of abstraction than the object-oriented language with which it is used. More particularly, the adaptive program is generalized such that little redundancy exists and hence modifications are simplified.

Object orientation has demonstrated that properties such as encapsulation, inheritance and late binding are useful in the discipline of software engineering. However, object-oriented languages suffer from an inherent rigidity which can make software modification and re-use both awkward and laborious. The key feature of most object-oriented languages is that the description of actions is attached to the description of classes. In other words, methods are tightly coupled with classes. While this characteristic property can be useful, it has been observed that changes in the structure of data, i.e., "class definitions," may necessitate re-writing large portions of the action code, i.e, "method definitions." Unfortunately, this is true even if the underlying algorithm remains essentially unchanged.

Adaptive software systems address the above-described limitation in object-oriented languages by supporting a programming style in which class descriptions are only loosely coupled with action code. Changes in class definition thus usually involve a relatively small number of updates in the action code. However, current compilers for adaptive software are not general in the sense that there are certain combinations of adaptive programs and class graphs which the compilers reject. If an adaptive program and a class graph cannot be compiled, then the adaptive program has to be rewritten. This defeats the original motivation of adaptive programs which is the automation of adaptiveness.

SUMMARY OF THE INVENTION

According to the present invention, a compiler for use with an adaptive program and a class graph includes an automata generator which produces a finite deterministic automaton representative of a set of paths from the class graph, wherein the compiler provides an object-oriented program in a target language based on the adaptive program and the automaton. Given an automaton M and a state s, Outgoing.sub.M (s) denotes the set of all transitions s.fwdarw.s', and P.sub.M is the program in the target language such that method names in P.sub.M are the states of M as follows: if ##EQU1## where c is a class name, and ##EQU2## then P.sub.M (c,s)={l.sub.1.m.sub.1 . . . l.sub.n.M.sub.n }, where l.sub.j <l.sub.k for 1.ltoreq.j<k.ltoreq.n; otherwise, if c is a concrete class and s is a state in M, then P.sub.M (c,s)={ }; and otherwise, P.sub.M (c,s) is undefined. The automaton may also be reduced to provide an object-oriented program of reduced size.

The compiler of the present invention provides an adaptive software system with generality and optimality. Unlike previous adaptive software systems which were limited to use with specific combinations of adaptive programs and class graphs, the system of the present invention is capable of compiling most combinations of adaptive programs and class graphs. Hence, the system has the desirable quality of generality. Further, an intermediate automaton allows use of reduction algorithms to reduce the size of the generated object-oriented program. The system thus has optimality in the sense that it generates an object-oriented program of reduced size.

The compiler of the present invention also indirectly enables utilization of various advantages associated with adaptive software. For example, adaptive software allows for shorter programs by focusing on core actions and reducing redundancy. Further, adaptive software allows development of application-oriented, domain-specific reusable libraries which can be reused in similar projects without added reusability cost. By providing a generalized compiler, the present invention extends these advantages to a wider variety of applications.

BRIEF DESCRIPTION OF THE DRAWING

Other features and advantages of the invention will become apparent in light of the following detailed description of the drawing in which:

FIG. 1 is a block diagram of an adaptive software system;

FIG. 2 illustrates the exemplary class graph of FIG. 1;

FIG. 2A is an alternative exemplary class graph;

FIG. 3 illustrates the exemplary adaptive program of FIG. 1;

FIG. 3A is an alternative exemplary adaptive program;

FIG. 4 illustrates the semantics of traversal specifications;

FIG. 5 is a block diagram of the automaton generation process; and

FIGS. 6-10 illustrate intermediate steps involved in computing a minimal deterministic automaton.

DETAILED DESCRIPTION OF THE DRAWING

FIG. 1 is a block diagram which illustrates an adaptive software system for compiling an adaptive program and a class graph to produce a desired object-oriented program in accordance with the present invention. The adaptive software system includes use cases 100, a class graph 102, an adaptive program 104, an object-oriented program 106 and a compiler 108 having a code generator 110 and an automata generator 112 which generates an automaton 114.

The adaptive software system achieves adaptability by separating the object oriented program 106 into two parts: the class graph 102 which defines objects, and the adaptive program 104 which defines operations. The class graph and adaptive program are then compiled to create the desired object-oriented program 106. Modification of the object-oriented program can therefore be accomplished by making relatively simple changes in the class graph or adaptive program and re-compiling.

The combination of the adaptive program 104 and the class graph 102 contains all of the information required to generate the object-oriented program 106. It should be noted however that the manner in which the class graph and adaptive program are represented is not critical to the present invention, e.g., the class graph could be represented by strings. Operations that are to be applied to objects are defined in the adaptive program and desired traversals are generated from the class graph. In practice, the adaptive program 104 can be produced from informal specifications. First, requirements are written in the form of use cases 100. A use case is an English language description of how the program 104 should react in a specific situation. The class graph 102 is derived from the use cases 100. Propagation patterns are also developed from the use cases. The propagation patterns are designed to have minimal dependency on the class graph.

In order to provide generality and optimality, the automaton 114 which represents the class graph 102 and adaptive program 104 is produced by the automata generator 112 for use by the code generator 110. More particularly, the automaton enables general case compilation of most combinations of adaptive programs and class graphs. Use of automata also enables use of standard minimization techniques which reduce the size of the generated object-oriented program 106.

FIG. 2 illustrates another exemplary class graph 102 of FIG. 1. The class graph is a labeled directed graph which represents the static class structure of the program 106 (FIG. 1) and expresses the "has-a" and "is-a" relations among classes. Subclass edges 200 represent is-a type relations and construction edges 202 represent has-a type relations. Generally, a directed graph is a pair (V,E) where V is a set of nodes, E is a set of edges and E.OR right.V.times.V. If (v.sub.1,v.sub.2).epsilon.E, then v.sub.1 is the source, and .nu..sub.2 is the target of (v.sub.1,v.sub.2). Each edge is labeled by an element from N.orgate.{.diamond.}. An edge (u,v) with label .diamond. is written ##EQU3## are subclass edges 200, which indicate that v is a subclass of u. If l.epsilon.N, then the edge ##EQU4## indicates that the class represented by u has an instance variable with name l and with a type represented by v. Such an edge is called a construction edge 202. The construction edge ##EQU5## indicates that the l-component of objects of class u is an object of class v.

A more complex exemplary class graph is illustrated in FIG. 2A. Two types of classes are employed by the graph: construction classes 204 (illustrated as .quadrature.) which are used to instantiate objects with a fixed number of parts, and alternation classes 206 which are abstract classes. Together, the classes and edges describe object structure. For example, the subclass edge ##EQU6## 208 means that class Officer 210 is a super class of class ShareHolding.sub.-- Officer 212, and the construction edge ##EQU7## 214 means that class Conglomerate 216 has a data member called head of type Company 218. The Company class 218 optionally contains a subsidiary list class 224 and it contains a list of Officer class 230 and has data members called a name 232, a location 234, and a turnover 236. A Subsidiary object 238 is either an instance of WhollyOwned 240 or an instance of PartiallyOwned 242 and contains a Company object 218. An Officer object 210 is either an instance of ShareHolding.sub.-- Officer 212 or of Ordinary.sub.-- Officer 244.

FIG. 3 illustrates an exemplary adaptive program 104 of FIG. 1. The adaptive program includes a traversal specification 300 and wrapper code 302. The traversal specification selects objects according to their classes. A traversal specification of the form ›A,B! is interpreted as "all objects of class B which are subobjects of an object of class A." The wrapper code associates actions with selected objects. Hence, with the proper wrapper code attached to class B, the interpretation of the adaptive program could be "for each object of class B contained in the class A object, add its value to a sum variable."

An exemplary adaptive program 104A is illustrated in FIG. 3A. Compiling the adaptive program 104A with the class graph of FIG. 2A provides an object oriented program which computes total salary expenditure for the Conglomerate object. More particularly, as described in the traversal code 300A and the wrapper code 302A, the program will return the sun of all Salary objects in the Conglomerate object. It should be appreciated that the adaptive program is modifiable for use in other tasks. For example, if the desired object oriented program were directed to computing the total weight of an object Airplane (for which a class graph exists) the adaptive program of FIG. 3A might be modified as follows: change SumSalary to SumWeight, change Conglomerate to Airplane, and change Salary to Weight. The program will then return the sum of all Weight objects in the Airplane object.

Referring again to FIG. 3, the traversal specification 300 denotes a set of paths to be traversed at run time. The traversal specification is an expression generated by the grammar D ::=›A,B!.vertline.D.multidot.D.vertline.D+D, where A and B are class names. Given a graph G=(V, E) with edge labels N.orgate.{.diamond.}, a path is a sequence .nu..sub.o l.sub.1 .nu..sub.l l.sub.2 . . . l.sub.n .nu..sub.n where .nu..sub.o . . . , .nu..sub.n .epsilon.V, and for all 0.ltoreq.i<n, ##EQU8## and l.sub.1 . . . ,l.sub.n .epsilon.N.orgate.{.diamond.}, wherein the terms .nu..sub.o and .nu..sub.n are the source and target of the path, respectively. If p.sub.1 =.nu..sub.o . . . .nu..sub.i and p.sub.2 =.nu..sub.i . . . .nu..sub.n, the concatenation can be defined as p.sub.1.p.sub.2 =.nu..sub.o . . . .nu..sub.i . . . .nu..sub.n. It will be appreciated that p.sub.1.p.sub.2 contains only one copy of the meeting point .nu..sub.i. Letting P.sub.1 and P.sub.2 be a set of paths such that all paths in P.sub.1 have target .nu., and all paths of P.sub.2 have source .nu., then: P.sub.1.P.sub.2 ={p.vertline.p=p.sub.1.p.sub.2 where p.sub.l .epsilon.P.sub.1 and p.sub.2 .epsilon.P.sub.2 }.

The paths of interest are those obtained by removing prefixes containing only .diamond.-labeled edges. Reduce (R) is the set of paths obtained by removing all .diamond. prefixes from each path in R, where R denotes an arbitrary set of paths. For a path set R, Reduce(R)={.nu..sub.n . . . .nu..sub.n+m .vertline..E-backward..nu..sub.0,.nu..sub.1 . . . .nu..sub.n-1 such .nu..sub.0 .diamond..nu..sub.1 .diamond. . . . .diamond..nu..sub.n . . . .nu..sub.n+m .epsilon.R}. Head (R) is defined to be the set of all nodes which are sources of paths in Reduce (R) , i.e., Head (R)={.nu..sub.0 .vertline..nu..sub.0 . . . .nu..sub.n .epsilon. Reduce (R)}. For a node u, select (R, u) is defined to be the set of suffixes of paths in R that start with .nu. after skipping a leading .diamond.-labeled prefix. Select (R, u)={.nu..sub.0 . . . .nu..sub.n .vertline..nu..sub.0 . . . .nu..sub.n .epsilon. Reduce (R), .nu..sub.0 =u}. Finally, Car (R, u) is defined to be a set of the first edges in select (R, .nu.), and for a given label l, Cdr (l, R, u) is defined to be the set of tails of Select (R, .nu.) where the head has label l. That is, ##EQU9## and Cdr (l, R, u)={.nu..sub.1 . . . .nu..sub.n .vertline..nu..sub.0 l.sub.1 .nu..sub.l . . . .nu..sub.n .epsilon. Select(R, u),l.sub.1 =l}.

The semantics of traversal specifications are shown in FIG. 4. A traversal specification must be well formed in order to be meaningful. A traversal specification is well formed if (1) it determines a source node and a target node, (2) each concatenation has a "meeting point," and (3) each union of a set of paths preserves the source and the target. The predicate WF is defined in terms of two functions Source and Target, given in FIG. 4, and the following recursive definition. ##EQU10## If D is well formed, then PathSet.sub..PHI. (D) is a set of all paths in .PHI. from Source(D) to Target(D).

The manner in which the traversal specification denotes path sets in the class graph is important to the performance of the generated program. To illustrate, paths can be denoted as strings, and the traversal specification D from FIG. 3 and the class graph from FIG. 2 examined in light thereof. Using the standard notation of regular expressions and denoting the language defined by a regular expression E as L(E), it follows that: PathSet.sub.G (D)=L(Expression (.diamond. Compound (arg1+arg2)Expression)+.diamond.Numerical). Turning back to FIG. 1, the compiler will reject the adaptive program and class graph of FIG. 2 and FIG. 3, respectfully, if an automaton is not employed to generate the program. More particularly, the program generated will be as follows.

    ______________________________________
    CLASS Compound     CLASS Numerical
    VAR arg1, arg2; Expression
    METHOD m             METHOD m
    arg1.m;arg 2.m         Wrapper code here
    END                  END
    END                END
    ______________________________________

    ______________________________________
    CLASS Compound     CLASS Numerical
    VAR arg1, arg2: Expression
    METHOD m             METHOD m
    arg1.n; arg2.n
    No code here
    END                END
    METHOD n           METHOD n
    arg1.n;arg2.n
    Wrapper code here
    END                END
    END              END
    ______________________________________

• Inventors
  Lieberherr, Karl; Palsberg, Jens; Patt-Shamir, Boaz;
• Assignee
  Northeastern University (Boston, MA)
• Published
  Aug-31-1999
• Current US Classes:
  717/116
  717/118
  717/146
  717/157
• Application #
  620502
• International Classes
  G06F 009/45
• Field of Search
  395/701 395/702 395/704 395/705 395/706 395/707 395/708 395/709
• Examiner
  Toplu; Lucien U.
• Agent
  Weingarten, Schurgin, Gagnebin & Hayes LLP
• US Patent References:
  4558413
  4783730
  4912637
  5075847
  5278979
  5313646
  5355317
  5410703