Proposal for a 90 Minutes Tutorial at ECOOP 2008

More Flexible Software By Abstracting Over Traversals and Communication
=======================================================================

Abstract
========
Adaptive Programming (AP) has promoted the idea of calling methods
indirectly through traversals. Aspect-Oriented Programming (AOP)
took this to the next level by calling methods indirectly through
general programs, not just traversals. Both AP and AOP are
departures from the traditional functional and object-oriented
approaches that suffer from two major problems: they explicitly
mention by name the subterms or subobjects that need to be traversed
(explicit traversal problem) and they explicitly mention parameters
that are passed down to subterms or subobjects, whether or not they
are relevant to the current term or object (explicit argument
problem). The reason for the two problems is a low-level use of
"follow the structure" or "follow the grammar".

We propose two new approaches to implicit calls and communication.

The first approach, called AP-F, is a functional approach that
parameterizes the traversal with three kinds of function objects:
transformers, builders and augmentors. Our current implementations of
AP-F are called DemeterF-Java and DemeterF-Scheme.
DemeterF-Java is provided as a Java library that heavily
relies on reflection. DemeterF-Java also includes a static type checker.

The second approach, called AP-P, is an interposition visitor approach
that relies on traversals and before/after methods. An interposition
visitor uses interposition variables that facilitate implicit
communication. Our current implementation of AP-P is called DemeterP-Java
and relies on code generation using AspectJ.

AP-F is a departure from traditional object-oriented programming.
While traditional oop uses the Law of Demeter: "talk only to your friends"
AP-F uses the variant: "listen only to your friends".
In AP-F, the methods deposit information at predetermined places
where other methods arefree to pick it up. 
This point of view leads to an explanatation of 
AP-F in terms of neurons.

Think of each node in the object tree as a neuron.
Each neuron has two states: the DOWN state and the UP state.
Initially all neurons are in the DOWN state and once
a neuron in the DOWN state has fired, it switches to the UP state.

In the DOWN state, a neuron takes input from a parent (or the outside
if it is the root neuron) potentially
updates this information and sends it down to all children 
who are free to use or ignore this information.

The UP state has two substates, called TRANSFORM and COMBINE.
In the COMBINE state, the neuron listens for the inputs from
its children. If there are no children, the output from
the TRANSFORM state is used.
In the TRANSFORM state, if there are children,
the neuron takes input from the COMBINE state and otherwise
the information at the leaf is used.

The firing of the neurons starts with the root neuron.

The code executed at the neurons is specified based on the
types of the incoming information. The AP-F program
that drives the neurons is checked statically. 
The type checker guarantees that each neuron will know
what to do in all states.

We have successfully used DemeterF programs for refactoring
interpreters and compilers from the EoPL book by Friedman and Wand,
making the programs both simpler and more flexible.
We are using DemeterF-Java as implementation language in two graduate courses.

We noticed in the graduate courses that in DemeterF-Java
programs can be written in a beautiful incremental style. This becomes possible
because computations are broken down into many small update, combine and
apply methods that provide for many points of extension.

For an example, consider the problem of reducing a conjunctive normal form (cnf)
when a variable is set. The reduced cnf is a reconstruction of
the original cnf with some of the clauses shortened by one literal
and others become satisfied. Now consider a generalized cnf,
where a clause is satisfied when at least two literals are satisfied.
Using DemeterF-Java, the implementation of reduction for the generalized cnf
is a simple additive extension of the implementation of reduction
for normal cnf.

DemeterF-Java is an excellent tool to concisely express differences
and commonalities between computations thanks to the fine-grained
decomposition of computations. Yet, DemeterF-Java follows the SYB
(scrap your boiler plate) approach so that the programmer only
has to write interesting code. For example, the DemeterF-Java library
offers a TUCombiner class which parameterized by a class T.
TUCombiner is used for type-unifying computations and 
defines commonly used combine methods.

Why cannot ECOOP not live without this tutorial?

The Law of Demeter is still a lively
debated topic on various websites (google: Law of Demeter).
AP-F provides a fresh functional look at how to follow the Law of Demeter
by shifting from talking to listening.
AP-P offers a new imperative look at the Law of Demeter.

We hope that this tutorial will contribute to the Law of Demeter discussions
on the web.

Both AP-F and AP-P are light-weight ideas that can be easily incorporated
into current technology.

AP-F has been in the works for about 2 years, and it has a stable implementation:
http://www.ccs.neu.edu/research/demeter/DemeterF/
that is being used. It is the PhD work of Bryan Chadwick. 


Joint work with Bryan Chadwick, Ahmed Abdelmeged and Therapon Skotiniotis.

Speaker Bio
===========

In the mid 1980s, Karl Lieberherr founded the Demeter research team,
which studied the then-novel idea of Adaptive Programming, also known
as structure-shy programming and produced the Law of Demeter ("talk
only to your friends": an explicit form of coupling control) and
several systems for separating concerns in an object-oriented
programming context: Demeter/Flavors, Demeter/C++, DemeterJ, DJ and
XAspects.

In 2006 he added Systems Biology to his areas of interest. He spent
his 2006 sabbatical at Novartis Institute for Biomedical Research and
discovered that SAT and CSP solvers play an important role in
biological applications.

The tutorial will be presented jointly by Karl Lieberherr and one
or two of the contributors to this work who are PhD students
at PRL/CCIS/Northeastern:
Bryan Chadwick, Ahmed Abdelmeged and Therapon Skotiniotis.

Possible Titles: 
Traversal Scoped Variables
Abstracting Over Transformations and Communication (in Traversal-Related Concerns)

Outline

1. Introduction
   Implicit versus explicit calls and communication
   Running Examples: evaluator, type checker, translator
2. AP-F
2.1 Dynamic join point model
2.2 Operational semantics
2.3 Type-checking
    Transformers
      Typing rule at object level
      Typing rule at class level
      Theorem from mp 8 linking the two
    Combiners
    Augmentors
2.4 Design Issues: From requirements to AP-F
2.5 Implementation
    DemeterF-Java
    DemeterF-Scheme
    Example code
3. AP-P
   Interposition visitors
3.1 Dynamic join point model
3.2 Operational semantics
    Simulating Transforms and Combines.
    Parameterized Copy Visitor.
    Visitor Combination.
3.3 Design Issues: From requirements to AP-P
3.4 Implementation
    DemeterP-Java
    Example code

4. Comparsion
5. Related Work
   SYB, Attribute Grammars, Functional Visitors
6. Experience Report