Transcript Open Modules: Reconciling Aspects and Modularity

Selective Open Recursion
Modular Reasoning about
Components and Inheritance
Jonathan Aldrich
Carnegie Mellon University
Kevin Donnelly
Boston University
Outline




The Fragile Base Class Problem
Selective Open Recursion
Implementation & Analysis
Discussion
Inheritance and Information Hiding

Parnas’ advice:

Modularize a system to hide information that may
change
Inheritance and Information Hiding

Parnas’ advice:


Modularize a system to hide information that may
change
Research question

How to hide information in component-based
systems with inheritance?
A Challenge: Open Recursion

Recursion

Objects can make self-calls to their own methods
A Challenge: Open Recursion

Recursion


Objects can make self-calls to their own methods
Open Recursion

Self-calls are dynamically dispatched


I.e., target of call is “open” and can be overridden
Beneficial in “template method” design patterns
Open Recursion
Window
class Window {
void draw() {
// draw background
this.drawForeground();
}
void drawForeground() { … }
}
class MyWindow {
void draw() { super.draw(); }
void drawForeground() {
super.drawForeground();
...
}
...
}
draw
drawFore
Open Recursion
Window
class Window {
void draw() {
// draw background
this.drawForeground();
}
void drawForeground() { … }
}
class MyWindow {
void draw() { super.draw(); }
void drawForeground() {
super.drawForeground();
...
}
...
}
draw
drawFore
Window
MyWindow
draw
draw
drawFore
drawFore
Hook Methods

Hook methods



Called by this when some event occurs
Intended as extension point for subclasses
Open recursion is necessary
Hook Methods

Hook methods




Called by this when some event occurs
Intended as extension point for subclasses
Open recursion is necessary
Other methods



Perform some task
May be overridden, but has no “event” semantics
Open recursion unnecessary


At best, minor convenience
Has potential to cause the Fragile Base Class Problem
The Fragile Base Class Problem
class CountingSet extends Set {
private int count;
void add(Object elem) {
super.add(elem);
count++;
}
void addAll(Collection c){
super.addAll(c);
count+=c.size();
}
int size() { return count; }
// other functions
}
Set
CountingSet
addAll
addAll
add
add
The Fragile Base Class Problem
class CountingSet extends Set {
private int count;
void add(Object elem) {
super.add(elem);
count++;
}
void addAll(Collection c){
super.addAll(c);
count+=c.size();
}
int size() { return count; }
// other functions
}
Set
CountingSet
addAll
addAll
add
add
Implicit assumption:
Set.addAll does not call Set.add
If this assumption is violated
(or changed), CountingSet breaks
The Fragile Base Class Problem

Definition (for this instance of FBC)

A class may depend on the calling patterns of a
superclass, and break if these are changed
Two Solutions to the FBC

Document open recursion
[Kiczales & Lamping, Steyaert et al., Ruby & Leavens]


Exposes information, rather than hiding it
Prohibits natural changes to superclass
Use forwarding to avoid open recursion
[Bloch,Szyperski]
Gives up benefits of open recursion
Can we get the benefits of open recursion without
the reasoning costs?
Two Solutions to the FBC

Document open recursion
[Kiczales & Lamping, Steyaert et al., Ruby & Leavens]



Exposes information, rather than hiding it
Prohibits natural changes to superclass
Use forwarding to avoid open recursion
[Bloch,Szyperski]

Gives up benefits of open recursion
Can we get the benefits of open recursion without
the reasoning costs?
Two Solutions to the FBC

Document open recursion
[Kiczales & Lamping, Steyaert et al., Ruby & Leavens]



Exposes information, rather than hiding it
Prohibits natural changes to superclass
Use forwarding to avoid open recursion
[Bloch,Szyperski]


Gives up benefits of open recursion
Can we get the benefits of open recursion without
the reasoning costs?
Outline




The Fragile Base Class Problem
Selective Open Recursion
Implementation & Analysis
Discussion
Selective Open Recursion
Use open recursion only where necessary

Hook methods

Use open modifier on method


Expresses “hook method” intent
All calls to open methods dispatched dynamically

Just as in Java today
Selective Open Recursion
Use open recursion only where necessary

Hook methods

Use open modifier on method


All calls to open methods dispatched dynamically


Expresses “hook method” intent
Just as in Java today
Other methods

Calls to non-open methods on this dispatched statically



The only change vs. Java
Hides internal calling patterns from subclasses
Other calls dispatched dynamically

open ≠ virtual
Selective Open Recursion Examples
class Set {
void add(Object o) {
// adds an element
}
void addAll(Collection c){
foreach (Object o in c)
this.add(o);
}
}
add is not open, so subclass cannot
intercept and depend on the call. Set can
change without affecting subclasses.
Selective Open Recursion Examples
class Set {
void add(Object o) {
// adds an element
}
void addAll(Collection c){
foreach (Object o in c)
this.add(o);
}
}
add is not open, so subclass cannot
intercept and depend on the call. Set can
change without affecting subclasses.
class Set {
// invoked for each add op.
open void add(Object o) {
// adds an element
}
void addAll(Collection c){
foreach (Object o in c)
this.add(o);
}
}
add is open, indicating the developer’s
intent to expose this method as a semantic
event to subclasses. Any changes to class
Set must preserve these semantics.
Design Principles

Non-open as default

Only use open recursion when explicitly intended
Design Principles

Non-open as default


Only use open recursion when explicitly intended
Annotate the method, not the call

Design intent is attached to operation
Do you have to change the language?

Coding guidelines




Never call a public method on this
Hook methods should be protected
Non-hook, protected methods should be final
Not our idea


Suggested by Ruby & Leavens
Used extensively in JDK libraries
Do you have to change the language?

Coding guidelines




Not our idea



Never call a public method on this
Hook methods should be protected
Non-hook, protected methods should be final
Suggested by Ruby & Leavens
Used extensively in JDK libraries
However—


This solution relies on programmer discipline
Language integration provides automated checking
Outline




The Fragile Base Class Problem
Selective Open Recursion
Implementation & Analysis
Future work and Conclusion
Implementation in Java

Extension to Barat compiler


Rewrite calls to non-open methods on this


Bokowski & Spiegel
Call a final method with the implementation for the
current class
Available at http://www.archjava.org/
Open Recursion Inference

Analysis to compute open annotations

Method m in class C must be open if:



Method m’ in class C’ <= C calls this.m
Class C’’ <= C’ overrides m
Class C’’ inherits or super-calls C’.m’
Open Recursion Inference

Analysis to compute open annotations

Method m in class C must be open if:




Method m’ in class C’ <= C calls this.m
Class C’’ <= C’ overrides m
Class C’’ inherits or super-calls C’.m’
Results may be imperfect

Assumes whole program is available


Misses open methods that are not overridden
May mark methods open that should be refactored to be
non-open
Experiments

Ran open recursion inference

java.* packages in JDK 1.4.2

Except java.nio, java.sql (see paper)
Experiments

Ran open recursion inference

java.* packages in JDK 1.4.2


Except java.nio, java.sql (see paper)
Hypotheses


Open recursion is rarely needed
Selective open recursion enables more
optimization
Frequency of Open Recursion


9897 methods in our portion of stdlib
246 (2.5%) of methods were inferred open
Frequency of Open Recursion

9897 methods in our portion of stdlib
246 (2.5%) of methods were inferred open

Maybe the stdlib doesn’t use inheritance



1394 of these methods are overridden
Only 18% of these are open
Open recursion is rarely needed
Thus making it selective may enable substantial information
hiding
Frequency of Open Recursion

9897 methods in our portion of stdlib
246 (2.5%) of methods were inferred open

Maybe the stdlib doesn’t use inheritance




1394 of these methods are overridden
Only 18% of these are open
Open recursion is rarely needed

Thus making it selective may enable substantial
information hiding
Optimization Potential


22339 calls in our portion of stdlib
6852 self-calls

716 to open methods


Must be dynamically dispatched
6136 to non-open methods


Can be inlined in our proposal (27% of total calls)
Inlining in Java would require private, final, or
whole-program analysis
Outline




The Fragile Base Class Problem
Selective Open Recursion
Implementation & Analysis
Future Work and Conclusion
Future Work:
Application to Formal Reasoning

Formalizing as Featherweight Java + module
system
Future Work:
Application to Formal Reasoning


Formalizing as Featherweight Java + module
system
Goal: bisimulation-based proof technique for
showing contextual equivalence of modules in the
presence of inheritance
Future Work:
Application to Formal Reasoning



Formalizing as Featherweight Java + module
system
Goal: bisimulation-based proof technique for
showing contextual equivalence of modules in the
presence of inheritance
Use selective open recursion and other
techniques to provide more information hiding

i.e. prove more programs equivalent
Conclusion

Open Recursion complicates reasoning


rarely used in practice
Selective open recursion




retains benefits of open recursion where needed
avoids fragile base class problem
can be efficiently inferred
may allow more optimization and reasoning
Open Recursion
class Set {
void add(Object elem) {
// adds an element
}
void addAll(Collection c) {
foreach (Object o in c)
this.add(o)
}
...
class CountingSet extends Set {
private int count;
void add(Object elem) {
super.add(elem);
count++;
}
void addAll(Collection c){
super.addAll(c);
count+=c.size();
}
int size() { return count; }
// other functions
Calls to this are dispatched to
subclass
Thus subclass can tell exactly
when each method is called
}