%% LaTex template for merit report \documentstyle[12pt]{article} %% EDIT THE FOLLOWING LINE TO CONTAIN YOUR NAME \def\name{Karl Lieberherr} \def\APPCs{AP\&P components} \def\APPC{AP\&P component} \def\reportyear{1998} %%% LEAVE THE FOLLOWING ALONE: \pagestyle{myheadings} \parindent 0pt % this makes unvarnished paragraphs % nice lists. \parskip=0.75ex plus 0.25ex \title{Annual Merit Report for \reportyear} \author{\name} \markright{\name\ and Demeter Research Group --- \reportyear} %% ADD YOUR OWN MACROS HERE \input common.tex \begin{document} \bibliographystyle{alpha} \maketitle \section{Research} Our research moved towards applying our expertise in Adaptive Programming (AP) and Aspect-Oriented Programming (AOP) to component-based software development. This is a natural direction for the Demeter research group because of the current interest in component-based software development. It is a continuation of our earlier work because Ian Holland's PhD thesis on executable contracts \cite{holland:thesis93} completed in our group six years ago is an early work on components. The most important work of this year is our OOPSLA '98 paper with Mira Mezini as first author on Adaptive Plug-and-Play Components. \subsection{Adaptive Plug-and-Play Components (\APPCs)} % APPC what and why \APPCs\ are an integration of Mira Mezini's PhD work on variation-oriented programming (Rondo) with Demeter ideas. See Mira Mezini's Ph.D. thesis \cite{mezini:thesis97} for her related ideas on Rondo. Basically, an \APPC\ is a piece of behavior that is formulated in an ideal context (an abstract class graph) and later mapped into a concrete context (a concrete class graph). The motivation for using an abstract class graph comes from our experience of programming against concrete class graphs. Such programs are both more brittle and longer than they need to be. % map with AP For expressing the mapping from abstract to concrete class graphs we can reuse our work on AP. It turns out that with AP we can express a mapping from an abstract class graph to a concrete class graph without committing to the details of the concrete class graph. This is a significant benefit because the concrete class graphs often change and maintaining the map can be time consuming. AP facilitates initial development and maintenance of the maps. % structure of APPC An \APPC\ has a required and a provided interface and contains behavior definitions for the participants of the \APPC. Two or more \APPCs\ may be connected by connectors that link the required and provided interfaces. The class graphs mentioned above are parts of those interfaces: the abstract class graph sits in a required interface and the concrete class graph in a provided interface. %where adaptiveness Our earlier work on traversal/visitor style programming was the predecessor of \APPCs. In traversal/visitor style programming you separate traversal programming from programming of actions that need to be executed during traversal. This programming style is still useful with \APPCs. Because the \APPCs\ are written modulo an abstract class graph the use of traversal strategies to express navigation is less urgent. In other words, programming with \APPCs\ can be done by delegating all adaptiveness to the connectors only. This is a good approach for getting \APPCs\ used by practitioners because they can be implemented with pure oo techniques and the "clever" AP techniques are only used in the connectors that are conceptually easier than the \APPCs. % connection beween abstract and concrete class graph Programming with \APPCs\ is a form of parameterized programming where formal and actual parameters are linked by connectors and where the formal parameters define constraints on graphs that must be satisfied by the graphs serving as actual parameters. This is different than template programming in C++. Next we define the concept of refinement-instance that we have developed over the last few years and that is fundamental to the concept of instantiating \APPCs. It needs to be stressed that the concept is independent of AP and is useful in contexts where graphs are "instantiated". We first introduce the concept of instance of a graph. The graphs we refer to here are UML class diagrams; however, to understand the definition of refinement-instance it is sufficient to consider graphs with labeled nodes and labeled edges without distinguishing between different kinds of nodes and edges. This generalization is not hard and is presented in papers on AP \cite{lieber-palsberg-xiao94} and environmental acquisition \cite{Gil:1996:EAN}. Informally, a graph G is an instance of graph S if G contains the connectivity of S. We think of S as an abstract graph and G as a concrete graph. Formally, a graph G is an instance of a graph S, if S is a connected subgraph of the transitive closure of G. Informally, a graph G is a refinement-instance of a graph S if the connectivity of S is in "pure form" in G. By pure form we mean that there are no "surprise uses" of the nodes of S. Formally, a graph G is a refinement-instance of a graph S, if S is a connected subgraph of the pure transitive closure of G with respect to the node set of S. The pure transitive closure of G=(V,E) with respect to a subset W of V is the graph G*=(V,E*), where E*={(i,j): there is a W-pure path from vertex i to vertex j in G}. A W-pure path from i to j is a path where i and j are in W and none of the inner points of the path are in W. Connectors use traversal specifications to specify class graph to class graph mappings. Traversal specifications are best thought of as anchored graph patterns which match a substructure of the class graph or a substructure of an object graph. The graph pattern can be thought of as a regular expression over the alphabet of the node and edge labels of the class graph. A special symbol "any" is used to denote any node or edge in the class graph. For example, A any* B, denotes the set of paths starting at node A and going through several edges and terminating in node B. Instead of using a regular expression notation for traversal specifications, we prefer to use strategy graphs. A strategy graph is a directed graph which defines positively the overall topology of the traversal. The edges are labeled with constraints which describe negatively the nodes and edges in the class graph which must be avoided. We like such a separation into positive and negative information although it would also be possible to assign regular expressions with "any" to the edges of a strategy graph. In such a representation the regular expressions on the edges could express further positive information about the traversal. The compilation of strategy graphs posed interesting problems. Palsberg, Xiao, Lieberherr \cite{lieber-palsberg-xiao94} presented a fast compilation algorithm for a restricted set of propagation directive and class graph combinations. Palsberg, Patt-Shamir, Lieberherr \cite{gener-comp-j:jens-boaz-karl} present a general compilation algorithm PPL which may be exponential for some inputs. Indeed, Lieberherr, Patt-Shamir \cite{strategies-tr:LP97} show that the PPL algorithm is exponential for certain inputs. Lieberherr, Patt-Shamir \cite{strategies-tr:LP97} also show a polynomial general compilation algorithm LP for any combination of strategy graphs and class graphs. Algorithm LP can be roughly summarized as follows. The summary is rough because it does not deal with abstract classes and inheritance. The key subcomputation is the intersection of non-deterministic finite automata. The strategy graph is viewed as a non-deterministic finite automaton and the intersection with the class graph NDFA yields a new automaton, called a traversal graph automaton. The application of the traversal graph automaton to a specific object graph can again be viewed as an NDFA intersection problem, namely the intersection of the traversal graph NDFA and the object graph DFA. In practice, the traversal of an object graph according to a traversal graph automaton is done in a similar way as the simulation of an NDFA. Algorithm LP solves the compilation problem in a very satisfactory way. Will Clinger and Lars Hansen and Mitch Wand observed that strategy graphs only allow for a certain kind of normalized traversals and that for some applications the traversals should be more complex. Mitch Wand and Johan Ovlinger \cite{trav-auto:wand-ovlinger} proposed that we use traversal automata to specify traversals of object graphs. Traversal graphs encode the details of the object structure in them and are therefore not structure-shy. Strategic traversal automata were then invented as a way to describe more complex traversals in a structure-shy way. Instead of being formulated for a concrete class graph, strategic traversal automata are formulated in terms of an abstract graph. \subsection{Class Graph Views} Johan Ovlinger developed the concept of class graph views. Views are closely related to \APPCs, in that views are the tools with which programming constructs like \APPCs\ can be implemented. An \APPC\ is a high-level programming construct for promoting code reuse. It provides the programmer with tools to write code that is easily added to a variety of host class graphs. \APPCs\ are a vehicle for research into programming constructs for reusable code. \APPCs\ are implemented by using class graph views. A view is a low-level programming pattern that is able to view one class graph as though it were another. Views are a vehicle for research into implementations of module systems for object oriented languages. Class graph views also incorporate some of the goals of Subject Oriented Programming \cite{Harr93a}, but at a lower level than originally proposed. Class graph views thus incorporate the core features of reuse, module systems, and subject oriented programming into a single programming pattern. The following terminology/capability maps show similarities and differences (APPC = \APPC): \begin{verbatim} Similarities ===================================================== Views APPC view classes participant classes provided interface provided interface required interface required interface map connector view class graph interface class graph host class graph implementation class graph apply one view to apply one APPC to several host class several implementation class graphs graphs apply one view apply one APPC several times to several times to same same host class graph implementation class graph apply multiple views apply multiple APPC to same host to same implementation class graph class graph compatibility between compatability between view class graph and interface class graph and host class graph implementation class graph views are reusable APPC are reusable components components \end{verbatim} \begin{verbatim} Differences ===================================================== Views APPC host-to-view view-to-host layering layering instantiate view participant classes classes are not instantiated supports basics of not the case because subject-oriented APPC are not programming self-contained intent: intent: modularization reuse unintentional reuse intentional reuse hide host behind view inject view into host view clients provided APPC clients provided with higher with code abstraction \end{verbatim} The goal of both Views and \APPCs\ is reuse. Other differences between Views and \APPCs\ are: Views are intended to be more basic. Views only use Java code in the maps while \APPCs\ may use higher-level constructs such as traversal strategies and regular expressions in the connectors. Class graph views are similar to Catalysis type models \cite{souza:catalysis}. They are abstractions of a UML class model in a similar way as interface class graphs are abstractions of concrete class graphs. Unlike a UML class diagram that describes the design for a single implementation, a type model captures constraints that must be true in any conforming implementation. In Catalysis, the behavior of type models is defined by type collaborations that are an abstraction of the UML collaboration concept. The connection between Catalysis and Views and \APPCs\ needs to be further studied. \APPCs\ are different than Catalysis type models because of the adaptive features. \subsection{Personalities} Luis Blando developed the concept of personalities. A personality is basically a Java interface with code or an \APPC\ for one class only. A personality describes popular behaviors of classes. A personality may be used by several personifying classes. See \cite{blando:personalities-98,blando-seke:personalities} and \bv http://www.ccs.neu.edu/home/lblando/personalities/ \end{verbatim} for more information. An implementation was developed in Argentina under Luis Blando's direction. \subsection{Demeter/Java} Demeter/Java was in 1998 further refined by Doug Orleans. See: \bv http://www.ccs.neu.edu/research/demeter/DemeterJava/ \end{verbatim} (especially the CHANGES file). Demeter/Java is our main tool to develop adaptive programs. Demeter/Java was used very successfully in COM 3360 in the fall of 1998 and in COM 3362 in the spring of 1998. Demeter/Java enjoys an active user group. We don't know its size but we expect to have about 100 active users outside Northeastern. Traversal/visitor style programming, the concept behind Demeter/Java, is probably much more widely used. \subsection{AP Library} In 1998, Doug Orleans extracted a separate reusable library from Demeter/Java. It is called the the AP library and contains the core algorithms for compiling adaptive programs. The AP library is currently used in both Demeter/Java and DJ (see below). For more information, see: \bv http://www.ccs.neu.edu/research/demeter/AP-Library/ \end{verbatim} \subsection{Aspects} In 1998, Josh Marshall has perfected his generic weaver that is used by Demeter/Java. The generic weaver can be viewed as a precursor to the \APPC\ language for AOP. The weaver is an auxiliary meta program which is used for implementing aspects in general, not just COOL and RIDL. Johan Ovlinger implemented RIDL for Demeter/Java. We developed a definition for AOP, based on earlier work in \cite{karl:demeter}, that is better than the Xerox PARC AOP definition. Our definition is not programming language dependent and is applicable also to aspect-oriented information engineering, not just AOP. See: \bv http://www.ccs.neu.edu/home/lieber/AOP.html \end{verbatim} \subsection{Visual Programming} Kedar Patankar and Binoy Samuel have refined AP Studio for visual adaptive programming. AP Studio allows you to develop strategy graphs visually in the context of a concrete class graph and to visualize the selected path set as a subgraph. The UML class diagram notation is used to represent class graphs. Doug Orleans has integrated AP Studio into Demeter/Java. \subsection{DJ} DJ is the little sister of Demeter/Java described at \bv http://www.ccs.neu.edu/research/demeter/DJ \end{verbatim} and implemented by Joshua Marshall. With DJ you can do AP without having to learn a new language. All programming is done in Java by calling a few methods from a library. We hope that DJ will eventually lead to a much larger dissemination of AP ideas. % \subsection{Summary} % % Give here a brief summary of your research activities for the year. \subsection{Books in Print} Karl J. Lieberherr, ``Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns'', {\em Book published by PWS Publishing Company}, 1996, 650 pages. \subsection{Journal Articles (Published)} ``Evolution of Object Behavior Using Context Relations'', with Linda Seiter and Jens Palsberg, {\em IEEE Transactions on Software Engineering}, Vol. 24, no. 1, pages 79-92, 1998. % \subsection{Journal Articles (Accepted)} \subsection{Journal Articles (Submitted)} ``Generic Programming with Graph Refinement'', with Boaz Patt-Shamir, {\em Schloss Dagstuhl Proceedings on Generic Programming}, 1998. \bv http://www.ccs.neu.edu/research/demeter/biblio/graph-refine.html \end{verbatim} \subsection{Refereed Conference Papers Published} ``Adaptive Plug-and-Play Components for Evolutionary Software Development'' with Mira Mezini. OOPSLA '98. {\it 1998 Proc. Object-Oriented Programming Systems, Languages and Applications Conference (OOPSLA), Special Issue of SIGPLAN Notices}, Vol. 33, no. 10, pages 97-116, ACM Press. An anonymous OOPSLA '98 reviewer evaluates and describes \APPCs\ as follows: {\em This is the kind of work that the software industry needs most. Hard core work, aimed at developing tangible and implementable mechanisms to help bridge the chasm between illusive design methodologies of arrows, bubbles, use cases, processes, etc., and the tough reality of the programmers in the trenches. Even the simple observation and unequivocal statement that a design segment should be a distinct lingual construct, have formal parameters that can be matched against several locations in the class graph merits honorable publication, since most previous work tried and failed to do so while using existing programming constructs (see e.g., observer pattern implementations using inheritance and templates). There is however in the paper much more than that, ... } ``From CSCW Applications to Multicast Routing: An Integrated QoS Architecture'' with I.\ Matta and M.\ Eltoweissy. {\it 1998 Proc. IEEE International Conference on Communications--ICC}, Atlanta, Georgia. Give Ibrahim 90\% for this paper and give me 10\%. \subsection{Refereed Conference Papers Accepted} ``Modeling Behavior with Personalities'' with Luis Blando and and Mira Mezini, {\it 1999 International Conference on Software and Knowledge Engineering}, Kaiserslautern, Germany, 7 pages. %\subsection{Invited Conference Presentations} %Keynote Speaker at STJA, Erfurt, Germany, September 1997. Title: %Adaptive and Aspect-Oriented Programming. \subsection{Unrefereed Publications} The Demeter home page has numerous links to unrefereed publications. They attract a significant readership based on the web statistics. % \subsection{Technical Reports} \subsection{Invited Talks, Colloquia, etc.} DARPA PI meeting, Los Angeles, CA, March 16 - March 19 Schloss Dagstuhl Workshop on Generic Programming (April 1998, 1 week) July 19 - July 24: DARPA EDCS Demo Days and PI meeting in Baltimore. Demonstration of Demeter/Java during 2 days with Doug Orleans. \subsection{Technology Transfer Activities} We (with Jens Palsberg and Boaz Patt-Shamir) have applied for a US Patent for Compiling Adaptive Programs. I had numerous discussions with the patent lawyers and the patent examiner and finally the patent was approved. It will be formally issued in 1999. It is based on \cite{gener-comp-j:jens-boaz-karl,strategies-tr:LP97}. Technology Transfer Activities is a very significant effort for us because of our involvement with DARPA which asks for technology transfer reports frequently. Our effort goes into developing, maintaining and promoting Demeter/Java, and the AP Library and into promoting the ideas behind AP. We use the Demeter home page \bv http://www.ccs.neu.edu/research/demeter/ \end{verbatim} as a very important technology transfer tool and spend significant time in maintaining those pages. I am on the technical advisory board for Tendril Software, Inc. They develop a tool using some of the Demeter ideas. There are projects using our technology at companies such as Xerox, GTE, Motorola, HP, Novell and SUN. \subsection{Grants} \begin{enumerate} \item ARPA EDCS grant, \$750000 1996-1999, Karl Lieberherr, PI, Evolution of Software via Adaptive Programming, DARPA and Rome Laboratory under agreement F30602-96-0239. \end{enumerate} \subsection{Grant Proposals} I wrote two grant proposals to DARPA with outside people. One was with GTE/BBN (Zincky/Anderson), the other with Miriam Leeser and David Lorenz. Unfortunately, both were not funded. \subsection{Conferences Attended} ECOOP PC meeting, January 1998. Oct. 18 - 22: OOPSLA '98, Vancouver, Canada. Two DARPA PI meetings mentioned earlier. \section{Teaching} \subsection{Courses} I taught three courses becuase of a DARPA buyout. I developed a new course on software testing (COM 3220, 7 students). \bv http://www.ccs.neu.edu/home/lieber/com3220/com3220.html \end{verbatim} I taught my favorite course, COM 3360. \bv http://www.ccs.neu.edu/home/lieber/com3360.html \end{verbatim} Maybe it should count as 1.25 courses since I teach two sections of the course: the local section (18 students) and the national NTU section (3 students). I prepared many hundred new viewgraphs for this course which are all available from my home page in Postscript and PowerPoint formats. The course went very well this Fall. Many successful Demeter/Java projects were completed. I also taught COM3362, Advanced Object-Oriented Systems, with 6 students. It is another one of my favorite courses. \bv http://www.ccs.neu.edu/home/lieber/com3362/com3362.html \end{verbatim} \subsection{Curriculum Development} I developed a new course on software testing (see above). \subsection{Seminar} Preparation for the Demeter Seminar takes a significant amount of time since it requires reading the latest literature relevant to our project. There is quite a bit of that. For many of the seminars I prepare PowerPoint viewgraphs which are available from my home page. %\subsection{Textbook Development} %I started to update my text book from Demeter/C++ to Demeter/Java. \subsection{Ph.D. Students} Currently, Doug Orleans and Johan Ovlinger are my Ph.D. students. They both are working towards their thesis proposal. \subsection{Ph.D. Committees} I serve on the committee of Michael Werner. He comes regularly to the Demeter seminar and is working on topics of interest to our research group. The advisor is Ken. \subsection{Master's Thesis} Luis Blando has written his Master's thesis with Mira Mezini and me as advisors. See \bv http://www.ccs.neu.edu/home/lblando/personalities \end{verbatim} \subsection{Reading and Project Courses} I supervised reading courses by my Ph.D students Doug Orleans and Johan Ovlinger. %\subsection{Refereed tutorial} \section{Service} \subsection{Summary} A major service component is the Editor-in-chief position for TAPOS (Theory and Practice of Object Systems, a John Wiley journal). \subsection{College Committees} I am on the Graduate Committee. I am on the hiring committee. I took an active role in attracting both Mira Mezini and David Lorenz to our College. I am on the tenure committee. No activity. I am on the full professor committee. No activity. I am on the sabbatical committee (chair). With Mitch and Will I am on the PL languages field committee. \subsection{University Committees} I am a member of the University Graduate Council. I am on the program review committee that started meetings again in the fall. \subsection{Professional Service} Editor-in-chief for TAPOS. Solicite and review papers and select about 16 per year (4 issues). I was on the program committee of ECOOP '98 and ECOOP '99 reviewing about 25 papers in the December/January time frame. I attended the the 1998 PC meeting in Copenhagen (January 98) and the 1998 PC meeting in Lausanne (January 99). \bibliography{/home/lieber/papers/new-obj/bibliography/biblio} \end{document}