Several exciting research projects are available suitable for Master's Projects or Master's Theses or independent study projects for undergraduates, or (with smaller scope) for course projects. The latest projects are towards the end of the list. The first two entries are still sources for good projects. Some of the projects after the third are already done.
Prerequisites: CSG 260 (for graduate projects). CSU 670 (for undergraduate projects). If you would like to do one of those projects and you have questions, please send mail to Karl Lieberherr.
Abbreviations used: AP = Adaptive Programming PP = propagation pattern
Add some or all of the following extensions to DJ:
Support for visitor methods on strategies.
DJ supports a domain specific language for navigating through
objects. The language is a graph language where the
nodes are classes and the edges define navigation paths
in the object graph. It is useful to program directly
in terms of those graphs.
For class graph edges we use the interface:
// for edge from S to T with name partName
void cbefore(Source s, String partName, Target t); //construction edge
// Source is a collection of Target-objects
void rbefore(Source s, Target t); //repetition edge
For strategy graph edges we use the interface:
// for strategy graph edge from S to T
void sbefore(Source s, Target t);
The code in such a strategy graph edge will be executed
before we execute the traversal selected by this edge.
In the sbefore method, for example, we can set a variable in
Target that tells us that we arrived through this strategy edge.
In summary:
Visitor methods
For nodes:
void before(A host);
For edges:
void cbefore(Source s, String partName, Target t); // construction 1
void cbefore(Source s, String partName); // construction 1
void cbefore(String partName, Target t); // construction *
void cbefore(String partName); // construction *
void cbefore(Source s, Target t); // construction *
void rbefore(Source s, Target t); // collection
void sbefore(Source s, Target t); // strategy
void sbefore(Strategy s); // strategy
void sbefore(String str); // strategy
The different cases are explained below:
void cbefore(Source s, String partName, Target t); // construction 1
Selects one construction edge. In the body we can refer to both
source and target and to the name of the edge.
void cbefore(Source s, String partName); // construction 1
Same as above, except that we can not refer to the target.
void cbefore(String partName, Target t); // construction *
Selects multiple construction edges. Whenever an edge with name
partName and Target t is traversed, the code is executed.
The code may refer to the target.
void cbefore(String partName); // construction *
Selects multiple construction edges. Whenever an edge with name
partName is traversed, the code is executed.
void cbefore(Source s, Target t); // construction *
Selects multiple construction edges that have different part names.
Whenever an edge with source s and target t
is traversed, the code is executed.
void rbefore(Source s, Target t); // collection
Selects one repetition edge. Code is executed for each
iteration step through the collection.
void sbefore(Source s, Target t); // strategy
A strategy before method is very different from cbefore.
Because any visitor is ultimately given as an argument to
the traverse method of an ObjectGraphSlice-object and the
ObjectGraphSlice-object knows (or should know about: requires
small addition to DJ interface) about the strategy,
the visitor methods may refer to strategy graph edges or
substrategies in general.
This allows programming at a higher level of abstraction.
The code in sbefore will be executed before the traversal
corresponding to this strategy (edge) starts.
void sbefore(Strategy s); // strategy
void sbefore(String str); // strategy
Execute the method body before the substrategy is "entered".
S must be a substrategy of the current strategy.
Support for around methods similar to the around methods in DemeterJ.
Support for before, after and around methods also for edges (not
only nodes). Around methods for nodes should allow
edge-specific subtraversals. Something like: subTraversal.apply("e")
means that the subtraversal is done only following the e edge.
It is often necessary, to extend objects during a traversal only.
Implement for class Visitor the following methods
(why for class visitor? why not class graph?)
void setValue(Object o, Object v);
Object getValue(Object o);
with getValue(o) you get back the object associated with o.
The implementation should use a hash table.
Solution:
class Visitor {
Map values = new HashMap();
void setValue(Object o, Object v) { values.put(o, v); }
Object getValue(Object o) { return values.get(o); }
}
One use of those methods is to mark objects that have been
visited during a traversal. v.setValue(o, new Boolean(true))
will mark object o as visited and v.getValue(o).booleanValue()
tells us whether o has been visited.
DemeterJ and XML
DemeterJ currently provides a PrintVisitor and a DisplayVisitor
to print out an object. Implement a third visitor generator
for DemeterJ that produces an XMLPrintVisitor. The XMLPrintVisitor
will print an object in markup form , i.e. in
a form that is acceptable to a general XML parser.
Also generate a class called XMLSchema with one static method: print()
that prints the class dictionary as an XML schema.
The descriptions produced by the XMLPrintVisitor (if the traversal
goes everywhere: from Source to *) should conform to the schema.
See
http://www.ccs.neu.edu/research/demeter/DemeterJava/use/latest-demjava/generate/gendisplayvis.beh
for the generation code for the DisplayVisitor. It is only about two pages.
There are several options on how to translate a
class dictionary into an XML schema. The first part of the project
is to propose such a translation.
Demeter and the Data Binding Approach in XML: Demeter/XMLJ
Implement the Data Binding Approach in XML using Demeter/Java and DJ.
See
http://www.ccs.neu.edu/research/demeter/technology-transfer/XML/index2.html
for links to data binding sites (SUN, IBM, etc.).
Call the new system: Demeter/XMLJ.
Input is a DTD or schema and output is a set of Java beans.
http://www.breezefactor.com/overview.html
contains more ideas. The value added of this project is that
the traversals and some visitors are generated automatically.
In Demeter/XML it will be possible to read sentences from URLs:
PriceList pl = (PriceList) ObjectFactory.createObjectFromUrl(
"http://www.breezefactor.com/breeze/data/pricelist.xml");
See also the
"XML schema evolution project" described below for further ideas
for Demeter/XML/J
Maintaining XML documents
(see also
http://www.ccs.neu.edu/research/demeter/related-work/microsoft/bernstein/genericModelManagement.html
)
XML documents are hard to maintain under changing DTDs because each document
encodes many of the details of the DTD into each document. There is a strong
need to have tools that help with the maintenance of XML documents.
Idea:
Consider the DTD evolution from L1 to L2 in:
http://www.ccs.neu.edu/research/demeter/technology-transfer/XML/XMLnavigation/XMLnavigation.html
Can you come up with LL(1) grammars LL-L1 and LL-L2 such that L1 and LL-L1
are object-eqivalent and L2 and LL-L2 are object-equivalent and such that
LL-L1 defines a sublanguage of LL-L2? If you can find such grammars,
the XML documents can be maintained automatically. Notice that if you have
1000 documents for L1 that you need to move to L2, it is easier to
write two grammars LL-L1 and LL-L2 than editing 1000 documents.
Provide a tool that helps to find LL-L1 and LL-L2.
For the definition of object-equivalence, including an adaptive
implementation, see:
http://www.ccs.neu.edu/research/demeter/biblio/dem-book.html
Under which circumstances do LL-L1 and LL-L2 exist given L1 and L2?
They seem to exist if L2 is an "enhancement" of L1.
Design an XML document maintenance service that reads in an old
schema, a new schema, a set of documents
for the old schema and that returns a set of updated documents
for the new schema.
For further information, see:
Regression Testing.
A more abstract formulation of the problem is:
Given two class dictionaries cg1 and cg2, do there exist
class dictionaries cg3 and cg4 such that
cg1 is object-equivalent to cg3 and cg2 is object-equivalent to cg4
and L(cg3) is a sublanguage of L(cg4).
All class dictionaries are assumed to be LL(1) and not left-recursive.
L(cg) is the set of objects Objects(cg) in printed form.
Tcl, Java and Adaptive Programming
Integrate Tcl and Java and DJ to create an adaptive
scripting environment for developing web applications.
Two tools are available from Scriptics: Tcl Blend and Jacl.
With Tcl Blend, a Tcl programmer can
allocate Java objects and invoke Java methods inside Tcl.
Jacl is an implementation of Tcl written in 100 percent pure Java.
It isn't a Tcl extension, for it doesn't add new commands to the Tcl
interpreter. It is simply a rewrite of the Tcl interpreter
using Java source code instead of C source code.
Using Jacl, Tcl programmers
can define variables and procedures as well as interact
with Java objects.
This interaction is made possible by the java package,
which is a set of Tcl commands shared by
Jacl and Tcl Blend that provide access to Java's reflection API.
See:
http://dev.scriptics.com/software/java/java.html
and
Isthmus: Demeter/C++ and Tcl/Tk integration (1995-1996)
For more ideas, check out the MIT Web course.
http://philip.greenspun.com/teaching/one-term-web
XML, XHTML
Use XML with a data binding approach to Java code generation, and
XHTML (generate XHTML from XML using Java) to build a simple web
application. Many companies use XSLT instead of Java and a data binding
approach to XML.
See: http://www.xmlspy.com/default.html.
Adapting web pages to a customer profile
A customer category is represented by a class dictionary
with start class C.
A specific customer in the category is represented by a C-object.
We would like present information to customers on a web site that
is generated on the fly and specialized to a specific customer category
and a specific customer.
We parameterize the information presentation program by a class dictionary
and write it as an adaptive program that works for an infinite family
of customer categories.
Come up with a specific application of this idea in a specific business
and implement using Java Server Pages and Demeter/Java or DJ.
Traversal Graph controls parser
Given an XML document and a traversal strategy, build the minimal
Java object that is needed to execute the traversal strategy.
Motivation: The XML object might be huge and we only want to build a subobject
of it that is needed for processing. The traversal strategy defines a view on
the object.
Questions: is the sub-object a legal object with respect to the schema?
Not ncessarily, but that is ok.
Solution: Build the traversal graph from the class graph and the traversal
strategy and let it control the parser in a similar way
as a traversal graph controls a traversal. It is sufficient to
collapse the traversal graph into a sub class graph of the original class
graph.
XML Path Language (XPath)
The goal is to either certify XPath or XQL as structure-shy
selection, iteration and traveersal languages. If they are not
structure-shy, extend them to make them structure-shy.
For a good summary of Xpath:
http://www.caucho.com/products/resin1.0/ref/xpath.html
is it already a good language for selecting and iterating through
XML objects?
If not
extend the XPath language for selecting and iterating through
XML objects with structure-shy capabilities.
Is XPath already a good language for defining traversals?
If not
extend XPath language to make it a traversal specification language.
Consider
XQL
http://www.caucho.com/products/resin1.0/ref/xql.html
Is XQL a structure-shy query language? Does it have the
capabilities of AQL?
http://www.ccs.neu.edu/home/lieber/theses-index.html
see Coleman Harrison's Master's thesis
If not extend XQL.
In all cases, implement a very small subset of the original language
plus the extensions you added. Can you use XML4J from IBM
as a starting point?
Integrate Java Server Pages (JSP) with Demeter
Write a JSP (http://java.sun.com/products/jsp/) with
Java/XML/Demeter and maintain it remotely.
Suggested by Salil Pradhan, HP Research Lab.
Project: Adaptive Plug-and-Play Components (AP&PC) and UML
http://www.ccs.neu.edu/research/demeter/biblio/components.html
and
http://www.ccs.neu.edu/research/demeter/biblio/aspectual-comps.html
offer a good approach to modeling systems at a high level. UML
offers collaborations to describe AP&PC but UML also has Activity diagrams
that are useful to model business processes.
See: The Unified Modeling Language User Guide by
Booch, Jacobson and Rumbaugh for info on Activity Diagrams.
Propose a way to use Activity Diagrams and Collaborations to describe
AP&PC.
Project: Document Object Model (DOM)
The document object model
http://w3c.bilkent.edu.tr/TR/REC-DOM-Level-1/
allows you to model documents that you can access through an API.
Design and implement an integration of DOM and traversal strategies
by providing a higher level API that makes it easy to navigate.
Use:
http://www.ccs.neu.edu/research/demeter/AP-Library/
to make it easier to navigate through complex documents in a structure-shy
way. Without such an integration, DOM navigation code is of the form:
A.B...C.D which results in a blatant violation of the Law of Demeter.
Project: XML schema evolution project
Class dictionaries and XML grammars are closely related.
An XML grammar is called a DTD or an XML schema. As described at
http://www.alphaworks.ibm.com/tech/Xeena
DTD's tend to change frequently which requires updating
both the XML descriptions for a given DTD as well as the
programs that process the XML descriptions. AP helps to facilitate
the maintenance of DTDs and associated programs.
Write a program that maps an XML grammar to a class dictionary.
Organize the translation so that the languages are the same.
Now you can use AP to manipulate your XML documents for the
given DTD in a stucture-shy manner.
Find an application of this idea. An example would be that
you express processing of business objects that are expressed
in XML. What are the limitations of Demeter/Java and
the Java Compiler Compiler for
applications of this kind?
Instead of Demeter/Java, you could use DJ. All parsing would be done by
an XML parser that gives you back a Java object when it gets
a DTD and an XML description. Can you find
such a parser on the web? I found one at:
http://falconet.inria.fr/~java/classes/xml4j/TXapiDocs/
It makes heavy use of traversal visitor style programming.
You process the Java objects using
a Java program written using DJ. This will protect you against changes in the
DTD or XML Schema.
As XML parsers, consider:
http://www.alphaworks.ibm.com/tech/Xeena
and
http://xdev.datachannel.com/downloads/xjparser/
The latter one talks about how to create Java objects with the
parser.
Host: Johan Ovlinger
Project: XML and DJ
The "XML for Java Compatability" classes described at:
http://falconet.inria.fr/~java/classes/xml4j/TXapiDocs/
offer a traversal/visitor style to processing XML documents.
However, the traversal/visitor style is limited.
It is not easy to specify traversals that are needed
for processing.
Only RecursivePreorderTreeTraversal and
NonRecursivePreorderTreeTraversal and TreeTraversal
are provided and they visit the entire document.
This project is about integrating DJ
http://www.ccs.neu.edu/research/demeter/DJ/
with the "XML for Java Compatability" classes.
The goal is to have a method
void traverse(org.w3c.dom.Node startNode, Visitor v)
for class TraversalGraph of DJ.
With this approach, you can flexibly specify traversals of documents
with the visitors you need.
The class graph has to be constructed from the XML Schema.
Project: XML in AP Tools: DTDs for artifacts used by Demeter
We would like to exchange design information about
design artifacts between different
tools. The important artifacts are:
Collaborations as defined in:
http://www.ccs.neu.edu/research/demeter/biblio/components.html
and in
http://www.ccs.neu.edu/research/demeter/biblio/aspectual-comps.html
and in
http://www.ccs.neu.edu/research/demeter/biblio/DynCompGlue.html.
An improved paper about component gluing is available from lieber@ccs.neu.edu.
See also http://www.ccs.neu.edu/research/demeter/uml/collaborations/UML.html
for collaborations in UML.
Class dictionaries
http://www.ccs.neu.edu/research/demeter/DemeterJava/use/generate.cd
Traversal Specifications (traversal strategies)
http://www.ccs.neu.edu/research/demeter/DemeterJava/UserManual/
the section on traversal strategies.
Traversal Graphs
http://www.ccs.neu.edu/research/demeter/AP-Library/doc/EDU/neu/ccs/demeter/aplib/TraversalGraph.html
Develop a DTD for each of those artifacts
and then use Xeena
http://www.alphaworks.ibm.com/tech/Xeena
or a similar tool to create XML descriptions that satisfy the DTD.
See http://lynx.neu.edu/c/cturcanu/xml for work in progress.
Project: Evaluate usefulness of AP
Choose a suitable part of a project which you and others implemented
elsewhere and redo that part with Demeter/Java.
This can be an academic or commercial project of your choice.
It would be good to have statistics on the old project regarding
code size and development time etc.
Keep a good record of statistical information for the new project
and compare the results for the old project with the results
for the new project. How can you measure the flexibility of the
adaptive software relative to the old software?
Did adaptiveness help? Is the software more understandable?
A variant of this project has two students of similar training
implement the same student
selected project (for example a game).
One does it in Java directly and the other in Demeter/Java.
Then the results are compared.
For earlier evaluation projects, see:
http://www.ccs.neu.edu/research/demeter/evaluation
Project: 100% Pure Java with traversals
Demeter/Java adds traversals to Java by using a language which contains
Java as a sublanguage. The purpose of this project is to add traversals
to Java without extending Java but only by using predefined classes,
including a traversal class.
Traversals are created by calling the constructor of the traversal class
with a traversal strategy as string argument.
A traversal object t is called with
t.traverse(o,{v1,v2, ... ,vn}), where o is the object to be traversed
and {v1,v2, ... ,vn} is a vector of visitor.
The traversal class will implement a new algorithm developed in 1997
which translates a strategy and a class graph into a traversal
graph which is interpreted when a traversal executes.
A traversal strategy describes the high-level intent behind
a potentially large number of traversal methods.
A strategy first outlines a traversal in terms of key classes
to be visited and then it refines the traversal in terms
of associations which may be traversed. A traversal strategy itself
is represented as a graph.
The prerequisites for this project are:
Willingness to read a paper and translate the algorithms
from the paper into Java. Willingness to learn Java and Java's
reflective capabilities. Willingness to learn about the
Java Compiler Compiler to parse Java source code and retrieve the class
graph.
Project: Java demonstration
Use Java to develop an interactive demonstration for AP. This is
meant to be more of a tutorial on AP, rather than a front-end to the
Demeter system. The tutorial should be for the new Demeter/Java
and AP Studio.
It should be possible to run the tutorial anywhere on the WWW.
Project: UML GUI for AP
Propose a new feature for AP Studio and implement it.
The AP Studio source code is available from the Demeter/Java
and AP Studio Resource page:
http://www.ccs.neu.edu/research/demeter/DemeterJava/use/
The GUI needs to support the class diagrams of the Unified Modeling Language
of Rational.
http://www.rational.com/
So the tool will use the Unified Modeling Language (based on the widely used
Booch/Rumbaugh and Jacobson methodologies).
For example,
implement undo for AP Studio. AP Studio already uses the Command
design pattern, so it is set up to implement undo.
Project: Demeter/Java for general context objects
The current implementation of Demeter/Java is for context objects which are
attached to method calls. Context objects
http://www.ccs.neu.edu/research/demeter/biblio/context.html
may also be attached to objects. The purpose of this project
is to implement context objects as described in
http://www.ccs.neu.edu/research/demeter/biblio/context.html
by a preprocessor which translates into Java.
This requires that your program detects context attachments (to both
objects and calls) in the Java code and that it translates those
attachments to updates of function tables.
The lookup in the function tables
occurs for every method invocation (translate to lookup of
method body and context object(s)).
The paper
http://www.ccs.neu.edu/research/demeter/biblio/context.html
and
Linda Seiter's thesis
http://www.ccs.neu.edu/home/lieber/theses-index.html
(chapters on context objects)
contain more information.
For a detailed project description see:
/course/com3360/f96/projects/general-context-objects/project
Project: Reuse of Adaptive Programs
Adaptive programs can be reused through metaphoric polymorphism.
A calculus for extracting adaptive programs and for incrementally
changing them needs to be implemented for Demeter/Java.
Literature: ECOOP '96
Project: Exception Handling
In our work on adaptive distributed systems
we are trying to come up with a good way
of handling failures. We would like to use
the ideas behind AP to improve the
state-of-the-art of exception handling.
See
http://www.ccs.neu.edu/research/demeter/DemeterJava/use/for-uguide/aao/
for work done last year.
The tasks are:
Learn about Aspect-Oriented Programming:
Read: http://www.ccs.neu.edu/home/lieber/AOP.html
and related links.
Combine Adaptive Programming and exceptions
(build a prototype as part of Demeter/Java) and write a paper.
OTHER PROJECTS
======================
GEF (Graph Editing Framework) is explained in assignment 2.
http://www.ccs.neu.edu/research/demeter/course/f96/hw/2/assign.txt
Some projects have a host assigned. If you cannot find the information
you need after a reasonable amount of time, ask your host or me.
For projects which don't have a host assigned, ask me directly.
Make optimal use of the time of your host.
Project List:
==============================================
ContainerTraversalSupport: Extend Demeter/Java so that traversals and the
other methods work with Vectors and Dictionaries.
In a class dictionary it should be possible to write
Vector(Fruit) or Dictionary(Name,Integer).
Vector and Dictionary are defined in java.util.
Features: Java Applet development, some code generation.
Host: Doug Orleans
Combine with P3, a Genvoca product.
==============================================
Eliminate repetition classes from Demeter/Java.
Host: Doug Orleans
==============================================
Designing and implementing a document editor
--------------------------------------------
The design pattern book by Gamma et al. describes a
case study about a document editor. Since we currently have
mostly Demeter/Java programs used in Demeter/Java, it would be useful
to have an example of an adaptive Java program outside the
domain of Demeter/Java.
Do an adaptive design and implementation
of the document editor and implement it with
Demeter/Java.
Please start thinking about groups now; I will briefly describe the
projects and I expect your selection of preferences soon.
Send your group formation and preferences by email to me.
Only one message per group.
Your first task for the project is:
Write down a few paragraphs what the requirements will be.
(We keep this simple, since we practice evolutionary
software development where the requirements change quickly.
We also have a lot of existing non-Java
code which defines some of the requirements.)
Write a UML class diagram in textual form which defines the
organization of the classes which you plan to develop.
Project: Demeter/Java for Java Beans
Study the Java Beans definition, design a Demeter/JavaBeans system
and modify the existing Demeter/Java code generator to produce
Java Beans. The advantage is that the resulting software is
more adaptable for integration with other Java Beans software.
Plan for the Java/Beans project:
1. Take two Java programs generated by Demeter/Java and rewrite them
into a Java bean. Take detailed note about the changes you have
to make. Write some glue code to let two beans talk to each other.
2. Design a class dictionary for an aspect language for Java Beans.
It should allow us to talk about the events which a class exports.
3. Translate the aspect language into weaving instructions for the generic
aspect weaver written by Josh Marshall (jayantha@ccs.neu.edu). Use the
-aspect flag when you call Demeter/Java. A description of the
weaving instructions will appear shortly in
http://www.ccs.neu.edu/research/demeter/DemeterJava/use/for-uguide/
4. Run the weaver to generate the Java beans.
It is not expected that the project is completed.
Project: AP Hypertext Explanation
Write a program which takes as input an adaptive program
consisting of a class graph, several behavior files and
input files containing objects and which
converts the program files into a hypertext document (html) for
browsing and understanding the program. Some suggestions for
the design:
for a strategy show the class graph and selected subgraph.
clicking on a keyword in a sentence shows the corresponding class
defining the keyword.
Project: Design by Contract
Modify Demeter/Java so that it supports design by contract
(see Bertrand Meyer's book.) The idea is simple:
Define a DesignByContract aspect which allows to express assertions:
pre- and post- conditions on methods and class invariants. Those
assertions will be checked during debugging only and are woven
into the application code.
For further information:
http://www.promigos.ch/kramer (see NEW)
Project: Quality of Service Aspect
Work on the Quality of Service aspect for network sensitive
applications. In collaboration with professor Matta.
Requires familiarity with networks.
See http://www.dist-systems.bbn.com/projects/DIRM
for related information.
Project: Interpreter for Web scripting language
Use Demeter/Java to write an interpreter for a WWW scripting language
which deals with failures and slow transmission rates.
In this language you could write:
gateway get("http:///www.altavista.digital.com/cgi-bin/query",
what ="web" q="java")
to look up "java" on the AltaVista serach engine.
repeat(limit(1,1,url("http://www7.conf.au/")))
to fetch a page in Australia. If the fetch fails or the rate drops below 1
Kbytes/sec, then it starts again.
See SRC report 148 by Luca Cardelli and Rowan Davies, Digital
Equipment Corporation.
For more info:
http://www.research.digital.com/SRC/publications/
http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-148.html
Project: Design Checking
Compositional consistency checking for Demeter/Java.
See page 477 in AP book. This checker is needed to tell the
Demeter/Java users when a subgraph representation of a traversal
is inadequate.
Project: Design Checking: object and language equivalence
Check whether two class dictionaries define the same class graph,
the same language. Needed for AP Studio.
See chapter 13 for a partial solution in Demeter/C++.
Project: Testing 1
Develop a test suite for the Cool aspect.
Project: Testing 2
Build a test suite for testing AP Studio, for example using
Javastar from SunTest (the company which develops JavaCC).
Project: Reverse Engineering
Write a program which takes as input a Java program and produces
as output a class dictionary. Use the Java grammar available
from the Demeter/Java resource page.
Project: Metrics for Java
From Binoy Samuel:
the december'97 issue Dr Dobb's Journal is on OOP and it has an
interesting article on Object Oriented metrics.
It can also be read online at
http://www.ddj.com/ddj/1997/1997.12/bans.htm
The whole thing might be too big for a com3360 project, but I guess a
lot of it can be done if someone is interested...
---------
Yes, this is an ideal project for Demeter/Java: Start with the
Java language grammar available from the resource page
http://www.ccs.neu.edu/research/demeter/DemeterJava/
Read in a Java program, creating an object and then write strategies
and adpative methods to collect the metrics.
Include in your program a metric which violates the number of violations
of the Law of Demeter (class form). Companies have found in proprietary
studies that having many violations of the Law of Demeter is a strong indicator
of high maintenance costs.
Project: Metrics for Demeter/Java
Same as above but for Demeter/Java. Use the demjava class
dictionary from the resouce page and the Java class dictionary,
but in a seperate package. The code in Text-objects
you parse by the Java parser.
Projects suitable for a Master Thesis Adapt known automata algorithms to solve the following problem: TRAVERSAL EQUIVALENCE PROBLEM: Given two strategy/class graph pairs (S1,G1) and (S2,G2) such that Common = Objects(G1) intersect Objects(G2) is not empty, determine whether they define the same traversals for all objects in Common. (Also treat the case where the question is whether one is always a subtraversal of the other.) If the traversals are different for some objects, give an object where the traversals are different. Motivation: during the evolution of adaptive programs and class graphs, we need to know how traversals change. Ideas: Construct the traversal graph as described in http://www.ccs.neu.edu/research/demeter/biblio/strategies.html using Doug's implementation in Demeter/Java. View the traversal graph as a generalized finite state machine (instead of processing strings, we process objects. The output is in both cases a string.) Generalize finite automata eqivalence algorithms. Use the Mona tool to check traversal strategies for equivalence. An interesting example formula that Mona can express is: There is no object x of type A s.t. there exists an object y of type B and an object z of type C s.t. both y and z are in x. (from the TOPLAS paper by Klarlund and Schwartzbach) Consider also: horizontal regular expressions, routing expressions, caterpillar expressions. --------- SELF-AWARE PROGRAMS (suggested by Ken Anderson, BBN) Design and prototype an aspect language for self-adaptive performance improvement. The self adaptation should be based on observing the run-time behavior and then modifying the class graph to improve performance. The program needs to be self-aware of memory and time consumption of certain parts of the computation. For related work by Batory's group on adaptive collection class selection, see Batory's home page. ---------- Integrate adjusters and visitors, design an improved form of Demeter/Java and build a prototype. http://www.ccs.neu.edu/research/demeter/design-decisions/related-work/software-generators/integrate ---------- Exception Handling Aspect Develop an exception handling aspect for DemeterJ (based on the work by Lars Hansen; see his page.) ------------ Object Migration/Replication Aspect Develop an object migration aspect for Demeter/Java with RIDL. How should communication be handled with a remote object? Prototype using Voyager from ObjectSpace? ----------------
Application layer | Middleware layer | Physical layer VYou want to write the code in a middleware-shy way so that you can replace the middleware within limits without having to change your code. This application, if successful, will use our existing AP technology (the AP Library and DAJ) plus likely extensions that are needed for middleware-shy programming. Currently we are good at structure-shy programming and we would like to move towards layer-shy programming, with middleware-shy as a special case. We will need to add a capability to traverse through edges that have arguments and the idea of first-class traversals (subtraversal) in functional visitors. Traversals will need to be generalized to work in a distributed environment.
Related paper:
http://www.ccs.neu.edu/research/demeter/biblio/api-navig.html
@TECHREPORT{api-navig:allemang,
AUTHOR = "Dean Allemang and Karl J. Lieberherr",
TITLE = "{Softening Dependencies between Interfaces}",
INSTITUTION = "College of Computer Science, Northeastern University",
YEAR = 1998,
MONTH = "April",
NUMBER = "{NU-CCS-98-07}",
ADDRESS = "Boston, MA"
}
August 2003: > Work that still needs to be done: > Write a plug-in that helps to write plug-ins. > * support all of the ajc command line flags > * use incremental compilation feature of ajc to speed up xajc (if possible) > * clean up krufty parts of the code Add support for personalities: http://www.ccs.neu.edu/research/demeter/personalities/ Add support for multimethods: http://citeseer.nj.nec.com/174216.html Add support for COOL (ask Jun Gong) and RIDL (ask Bing Zhang) Develop a DSL for interprocess communication (synchronization and data sharing between processes) and add it to XAspects. Develop a DSL for benchmarking and timestamping that can select a control flow that defines the region under the microscope. Study Jac (Pawlak et al.): http://citeseer.nj.nec.com/context/2157414/0 and add JAC motivated DSLs to XAspects Study the paper by Crista Lopes at al. on exception handling: http://citeseer.nj.nec.com/lippert00study.html and add an exception DSL to XAspects. (Suggested by Macneil Shonle and Ankit Shah)
See also: http://www.ccs.neu.edu/research/demeter/biblio/XAspects.html
This for PhD students. Investigate continuized grammars for traversal strategies. Continuations and Quantification.
(1) every meaningful subexpression has a continuation; and (2) the continuation of an expression is always relative to some larger expression containing it. What is the continuation of B in "from A via B to C"?
AspectWerkz. Do a project expressing aspects using Java (basically the AOP concepts are made available as Java classes in the same way as DJ makes the AP concepts available as Java classes) and weave them at run-time. Redo XAspects, but using AspectWerkz instead of AspectJ as weaving engine. What are the benefits of dynamicity and the different deployment models of AspectWerkz?
Adaptive Programming uses the core concepts: ClassGraph, ObjectGraph, Strategy and Visitor. For optimization reasons we also use Traversal and the special case of a TraversalGraph, and ObjectGraphSlice.
By analogy, AOP uses the core concepts: ProgramGraph, DynamicCallGraph, PointCut, Advice. It also uses ClassGraph (with methods) and InterTypeDeclaration.
Do we need DynamicCallGraphSlice and ProgramCut (corresponding to Traversal)? Can we use this analogy to build an AOP library for Java?
Use the ideas of the paper below and develop XAspects plug-ins based on them.
@misc{ soares02implementing,
author = "S. Soares and E. Laureano and P. Borba",
title = "Implementing distribution and persistence aspects with AspectJ",
text = "Sergio Soares, Eduardo Laureano, and Paulo Borba. Implementing distribut
ion
and persistence aspects with AspectJ. In Proceedings of OOPSLA'02, Object
Oriented Programming Systems Languages and Applications. ACM Press, November
2002.",
year = "2002",
url = "citeseer.nj.nec.com/soares02implementing.html" }
Use the ideas from ArchJava and develop XAspects plug-ins based on them.
Study the following aspect implementations: AspectWerkz, Nanning, JBoss, AOP Alliance, AspectC++, Jac and integrate a good mixture of features as XAspects plugins.
http://nanning.codehaus.org http://aopalliance.sourceforge.net
Extend AspectJ with an improved cflow construct as described in: http://www.ccs.neu.edu/research/demeter/biblio/strategies.html
An adaptive method will only work correctly for certain class graph and traversal strategy combinations. An AspectJ aspect will only work correctly with certain base programs. Invent a constraint language that let's us formulate the constraints that should hold for the adaptive method or aspect to work correctly.
We would like to unify the two models, strengthening both of them. What is common: we have (1) selectors, (2) graphs and (3) trees that are instances of the graphs. The selectors select a subset of the nodes and edges of the trees. We need a general model (S, G, T) and a mapping to Demeter: (strategies, class graphs, object trees) and to AspectJ: (pointcut designators, static call graphs, dynamic call graphs).
Benefits to AspectJ: More expressive pcds in the "cflow" domain. More expressive type patterns. More expressive wildcard capabilities leading to higher level and more reusable pcds.
Benefits to Demeter: More expressive pcds replacing the visitor method signatures. More expressive traversal specifications.
Implementation possibilities: (1) Extend the AspectJ compiler with the unified model. (2) Provide an XAspects plug-in for the unified model and mapping plug-ins.
Sources: John Sung's Master's thesis: http://www.ccs.neu.edu/research/demeter/DAJ/index-john.html PL Day talk: http://www.ccs.neu.edu/home/matthias/PL/karl.ppt The strategies paper: http://www.ccs.neu.edu/research/demeter/biblio/strategies.html
Extend the AP Library with new features.
Support sequences: "{A|B1, B2, ... ,Bn}" means to start from A and visit in sequence: B1, B2, ... ,Bn. The Bi-objects don't have to be nested. So "from A via B1 via B2 ... via Bn" selects a subset of the desired objects. Motivation: The Arachne system at the "Ecole des Mines de Nantes" (Mario Suedholt).
A more powerful support for sequences is to consider sequences of traversal strategies (or selector expressions in general) combined with a predicate that filters the desired sequences of targets of the strategies. This is similar to the Kerf system for intrusion detection. http://kerf.cs.dartmouth.edu/outline.shtml Given a sequence of traversal strategies, we are interested in sequences of nodes that are targets of the strategies and that satisfy the predicate. The predicate has access to the nodes along the paths using variables.
What are applications of sequences of selector expressions? They report information about the state of a distributed computation. They are useful for encapsulating crosscutting concerns of the form: if computation1 is in state s1 and computation2 is in state s2 and p(s1,s2) holds, I want to execute this code.
Support filtering: from A to B[s] where s is a strategy starting at B. Selects only the B-objects where the strategy s is successful in selecting at least one target object. Motivation: XPath. Also support the parent and child axis: "from A to B .. C". Finds all the C-objects that are one level up from B-objects. "from A to B/C" finds all the C-objects that are immediate parts of B-objects.
Constructing the product graph of all strategies and then creating the traversal graph using the product strategy may lead to an exponentially large traversal graph (for general n). This is the state explosion problem when automata products are applied repeatedly.
Paul Attie has studied ways to avoid the state explosion problem. See http://www.ccs.neu.edu/home/attie/pubs.html. Can his techniques be applied to the state explosion problem for traversal graphs? What kind of constraints do the strategies have to satisfy?
Strategies have the disadvantage that when we add new classes to the class dictionary the traversals might go through extra paths that are not desirable. In a hard-coded traversal this is not the case. Can we freeze the strategy for a class dictionary? We have a grwoth plan: a sequence of class dictionaries that grow in size. Instead of just having strategies, we map each strategy to a class dictionary in the growth plan. This gives us the benefits of fixed traversals as well as the flexibility of strategies. A similar issue applies to aspects. The growth plan consists of a sequence of programs that grow in size. We map each pointcut to a program in the sequence. This gives us the benefits of manual editing and the flexibility of pointcuts. Another issue with traversals is that they traverse through private parts. we are no longer free to change the implementations because we might break traversals. The same issue applies to aspects. After we have written a pointcut, we are no longer allowed to freely change the implementations because we might select the wrong join points. See: http://www.ccs.neu.edu/research/demeter/papers/boaz-jacm/sound.html (written in 1997). See also the paper by Kiczales and Mezini in ICSE 2005.
Start with Doug Orleans' PhD dissertation. What kind of declarative branch-predicate languages can be used to make the predicate implication problem decidable or even polynomial? The following paper and related papers by the same authors might give you an idea.
@incollection{douence:aosdbook05,
title = {Trace-Based Aspects},
pages = {201-217},
author = {Remi Douence and Pascal Fradet and Mario {S\"udholt}},
crossref = {:aosdbook05},
}
@book{:aosdbook05,
publisher = {Addison-Wesley},
address = {Boston},
title = {Aspect-Oriented Software Development},
editor = {Robert E. Filman and Tzilla Elrad and Siobh\'an Clarke and Mehmet {Ak{\c s}it}},
year = 2005,
isbn = {0-321-21976-7}
}
For example, we want to collect the join points of all method calls of methods that have two arguments of the same type and whose target object contains at least one object of class A. Here we have two meta graphs involved: The static call graph and the class graph. There is a link from each call node of the dynamic call graph to a node of an object graph (the target object of the call).
Another example: we want to collect all object nodes whose class has only private data members. Here two different class graphs are involved: the application class graph and the class graph of the programming language. The task is to design an enhanced query language and efficient algorithms for executing the queries. The task is to study the computational complexity of various algorithmic problems related to the enhanced query language: both efficient algorithms and lower bounds.
If the requirement says to find all people waiting at a bus stop, the strategy: s1 = "from BusRoute via BusStop to Person" does not capture the intent of the strategy. However, the strategy: s2 ="from BusRoute via BusStop via -> *,waiting,* to Person" does capture the intent. s1 does not capture the intent because it would also catch Person objects drinking coffee at the bus stop. s2 excludes those. In this case, the selector language is expressive enough to express the intent. The intent = interface language might need more expressiveness, in general?
Terminology is in: http://www.ccs.neu.edu/research/demeter/biblio/unified.html.
What are the implications if we select a richer language for sets of paths? This was indeed the point of an investigation of a Xerox PARC and Northeastern team in 1995: John Lamping proposed a set language, called ERE, for sets of paths:
http://www.ccs.neu.edu/research/demeter/design-decisions/reg-exp-for-traversals/GOOD
What are the benefits of adding more of ERE or the traversal strategy language of Demeter to AspectJ? What are the benefits of combining SAJ and SD in http://www.ccs.neu.edu/research/demeter/biblio/unified.html. Basically you replace the flow construct of SAJ with the SD language and you introduce a conversion operator nodes() that transforms a set of paths into a set of nodes.
SAJ and SD epitomize AspectJ and Demeter selector languages, respectively. AspectJ is about selecting sets of nodes in an instance tree (dynamic call tree) and about selecting sets of paths in an instance tree (also dynamic call tree). The sets of paths are selected by writing patterns that select stack configurations. For example, cflow(call void A.f(*)) is a pattern that accepts a stack that after the call to main() has a call to A.f(Arg arg) for some argument type Arg. By applying a conversion operator nodes(), the set of paths is translated into a set of nodes.
Is the added complexity justified by the benefits?
Study the issues involved in developing such incremental algorithms.
==================
The goal of this project is to try to learn queries for nodes in trees where the trees represent call trees or object trees. Can the learning be improved if meta information is known, the meta graph is given?
Proposed by Rick Schantz and Joe Loyall of BBN:
idea #1: Investigate, distinguish and organize the relationship(s) between AOP and component programming as system and application decomposition and composition approaches.
Sergei Kojarski's work in our college addresses this problem.
idea #2 (new): Investigate the feasibility of language-neutral AOP programming.
Prospector currently lets the user choose from a set of solutions at the Java level. Instead we would like the user to select at the selector expression level from which the Java level is generated. The selector expression is used during future evolution/reuse of the program. http://snobol.cs.berkeley.edu/prospector/
For more information, including slides, references, see: http://www.ccs.neu.edu/research/demeter/related-work/berkeley/prospector/
Hi Karl,
I came upon something interesting on the AspectJ mailing list recently (forwarded below). At the very bottom of the message is a use-case from someone who would like to annotate fields in Java in order to automatically generate an "equals" method. You could imagine that an annotation style (similar to Elide) could be useful for many other domain-specific aspect languages, including RIDL.
The Sun Annotation Processing Tool also provides a compile-time reflective mechanism: http://java.sun.com/j2se/1.5.0/docs/guide/apt/GettingStarted.html Unfortunately, it requires the presence of Java source code, and thus would not be able to reflect on AspectJ generated bytecodes.
Nevertheless, it might be an interesting project for someone to explore an APT-like tool with the power of XAspects, or for some way to get XAspects to use this tool (or perhaps the bytecode reflection we already use will have the routines it needs).
For AOSD, I think the trend will be more in the direction that base code will have to prepare in some ways to be advised by aspects, but it can be done in ways that promote information hiding and ease of change.
Note by Karl: Agreed: Demeter has done this 15 years ago (Demeter/C++). In the current DJ tool, a traversal specification is preparing the base code for an aspect to apply. The preparation consists of "annotating" the code with traversal methods and the aspect is an adaptive visitor using a pointcut language of the form: (all nodes and edges must be in the scope of the traversal) All nodes with name X, all nodes, all edges starting at X, all edges ending at X, all edges labeled Y, all edges, etc. The advice is in the visitor method bodies.
---------- Forwarded message ----------
From: Adrian Colyer
Generation of a method like this is not something that AspectJ can easily help you with.
You could write a generic equals method that uses reflection to find out which fields have the annotation and compare them (and then maybe use itds to declare that equals implementation on behalf of the target types). Avoiding reflection though, I think the best solution to this is probably to use something like APT: http://java.sun.com/j2se/1.5.0/docs/guide/apt/
-- Adrian
Adrian_Colyer@uk.ibm.com
neil@theharts.org
17/05/2005 20:26
To
aspectj-users@eclipse.org
cc
Subject
[aspectj-users] Marker Annotations
I've been using AspectJ a bit and I've got a question that is way outside of my experience and was wondering if someone could help.
I would like to use a Market Annotation on fields in a class to generate an equals method. Something like:
When we design an adaptive method, it is important to define
the aspectual interface of the method. This interface describes
the assumptions that the class graph must fullfil.
Example 1: Given is a recursive class C and we want to find
all top-level parts of type Y. The aspectual interface says
"from C bypassing C to Y" must define at least one path.
Example 2:
Given is a class B that has a nested part that contains
an Ident-object giving the name of the B-object. The
Ident-object itself is contained in a BName-object. The assumption
is that every B-object contains exactly one BName-object.
The aspectual interface says: there is exactly one path
from B to BName and the path does not contain a loop or
an edge with cardinality *. The aspectual interface
could be summarized as: from B to BName: loopfree, exactly one.
(This is best computed by eliminating edges with multiplicity *
and by eliminating strongly connected components from the
class graph and then check whether there is a unique path from
B to BName. Subproject: extend the AP Library by introducing
path constraints: loop-free and exactly-one)
The importance of aspectual interfaces lies in their support
for evolution.
Whne the class dictionary changes and the aspectual
interface is violated, we must likely change the adaptive method.
On the other hand, the aspectual interface should express
all the rules that must hold so that we can change the
class graph any way we like provided the aspectual interface is
satisfied. Note that the aspectual interface consists of more
than just strategies.
See the OOPSLA 1998 paper by Mezini and Lieberherr and the
aspectual component TR of 1999 by Lieberherr, Lorenz and Mezini.
For recent work, see the FSE 2005 paper by Sullivan and Griswold.
Currently the transition from a Java project to a DAJ project is not
straitght-forward when you want to use the full capabilities of DAJ:
The data binding capabilities for LL(k) grammars and the adaptive
programming capabilities. It would be useful to have a tool, called JtoDAJ
which takes a Java package and returns a class dictionary and
the methods in rewritten form so that they work with the
code generated by DAJ. The resulting DAJ program has the same functionality
as the original Java program. JtoDAJ will generate a class dictionary
that is LL(1), inductive and non-left-recursive. This means that
JToDAJ will add sufficiently many tokens to the class graph.
The user can then rearrange those tokens to get a "nice"
application-specific language.
But the DAJ program can now be more easily developed further:
1. Objects can be defined using sentences. This is useful for robust testing suites etc.
2. Much functionality becomes available: *Visitor, e.g., DisplayVisitor or PrintVisitor.
3. Behavior can be expressed adaptively.
There are several interesting questions: can we find a class dictionary
with a minimal number of tokens efficiently?
Answer the question: Can a general purpose partial evaluator
really replace the compilation algorithms for AP?
Is it as efficient, both in time and space?
See the paper by Peter Thiemann:
Peter Thiemann:
Compiling Adaptive Programs by Partial Evaluation.
In CC 2000, volume 1781 of Lecture Notes in Computer Science,
Berlin, Germany, Mar 2000. Springer-Verlag.
http://www.ccs.neu.edu/research/demeter/papers/about-ap/compiling-adaptive-programs-by.pdf
Peter Thiemann: An Algebraic Foundation for Adaptive Programming.
In Fossacs 2000, Lecture Notes in Computer Science, Berlin, Germany, Mar 2000.
Springer-Verlag.
http://www.ccs.neu.edu/research/demeter/papers/about-ap/thiemann99algebraic.pdf
Can you improve it?
public class Rubble {
@Equal
private Long fred;
@Equal
private String wilma;
}
would build a new:
public boolean equals(Object value) {
Rubble rubbleValue = (Rubble)value;
return (fred.equals(rubbleValue.fred &&
wilma.equals(rubbleValue.wilma));
}
Obviously the example equals method logic isn't complete. I would probably use EqualsBuilder or something to make it easier.
TIA
Neil Hart
Project: Design of Adaptive Methods (May 2005)
Project: Make transition to DAJ easier
Project: AP and Partial Evaluation (June 2006)
Project: Algebraic Foundation of AP (June 2006)
Consider the Algebraic Foundation presented in: