6.894 Administrivia
• Sign up for paper presentations on
2/27.
– look at titles, find papers,
– once selected, we’ll copy.
• Next lecture: JB on VM’s (&
interpreters)
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
1
OODL’s - The Big Picture
•
•
•
•
•
Abstraction
Dynamism
Reflection
Types
Objects
Meta-object
Protocols
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
2
What else?
Abstraction
•Inheritance
• -abstraction (A. Church, 1934)
•macros
– operations, abstracted over actual values.
• Abstract Data Types (ADT) •???
– interface, abstracted over actual
implementation. Classes are ADT’s.
• Dynamic Dispatch
“structure imposed on values.”
– abstracts idiom “choice by type”.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
3
Dynamism
• What is traditionally fixed at some
point in a program?
– code (def’n of functions)
new code, over net, via debugger
– types (and their structure)
new subclasses
– binary image (incl. optimizations)
optimizations, based on runtime data, more
thorough analysis.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
4
Enabling Dynamism
• How to add to language?
– (set! sort qsort)
– (add-subclass Tree BinaryTree)
– (set! “sort” qsort) Disabling Dynamism
• How to implement?
• for performance?
– (+ x y) -- in a tight loop
• for security?
– (dyncall walk a-fun a-tree)
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
5
Reflection
• Computation Reflection [Mae87]:
Computational reflection is the activity performed
by a computational system when doing
computation about (and by that possibly
affecting) its own computation.
• From [SF96]:
reflection-oriented programming [is]
programming as if the interpreter had been
modified.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
6
Reflection, cont’d
• Terminology:
– Reification = elt. of interpreter state
made manipulable by user program.
– Reflection = program value injected
into interpreter’s state. (what I earlier
called “dynamism”).
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
7
Java Reflection API
• Ex.: Java Reflection API.
– ms = x.getClass().
getDeclaredMethods();
ms[i].invoke(y, args);
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
8
What’s Missing from Java
Reflection?
• Reflection, aka Dynamism!
– Java’s reflection is “read only”.
– for every get, there should be a set!
• Java does have dynamic class loading
– a big hammer.
• Also: performance, context (system,
memory, load), dispatch hooks.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
9
Reflection + Dynamism
=
Adaptivity
• Design: How do we expose structure
• How do we structure value domains?
and behavior? • What’s a mechanism for choosing
different behavior?
• Implementation: “Pay as you go.”
• Analysis: can a function be redefined?
• Optimistic optimization: is this function unlikely to be
redefined?
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
10
Adaptive Programming,
Different Approaches
• Lieberherr et al., [Lie96].
– Abstract over paths
•
•
•
•
Common Theme:
Different Perspectives
for different purposes
Norvig & Cohn [NC97]
Metaobject Protocols (MOP)
Aspect-oriented Programming (AOP)
Refactoring [FBB+99], Extreme
Programming
• Subject-Oriented Programming[HO93]
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
11
Aspect-Oriented Programming
• Programming “crosscutting concerns”
– Ex.s: synchronization, scheduling,
persistence, replication.
• See: www.aspectj.org, [KLM+97]
• Recall “hack program or hack
interpreter.”
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
12
AspectJ
pointcut setters(Point p1, int newval): instanceof(p1) &&
(receptions(void setX(newval) ||
receptions(void setY(newval)));
before(Point p1, int newval): setters(p1, newval) {
System.out.println("About to set something in " + p1 +
" to the new value " + newval);
}
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
13
Meta-Object Protocols (MOP’s)
• Like Java, “reified” program elements
are instances of “metaclasses” (Class,
Method, etc.), but they can be
subclassed!
• Metabehavior (semantics) defined by
methods on metaclasses.
– compute-applicable-methods, allocateinstance, compute-effective-method, etc.,
and they can be overridden!
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
14
MOP’s, cont’d.
• See [KdB91], The Art of the MetaObject Protocol.
• Aaron Ucko, MEng project: adding
predicate dispatching to CLOS.
– subtypes generic function and method
metaclasses.
• Can you see how to implement AOP
with a MOP?
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
15
WHOA?
(What Has Openness Accomplished?)
 Gained: Abstraction, Dynamism,
Adaptibility!
 Lost: Safety, Performance.
• fill(aShape, aColor);  NAM?
• for(i=1; i < bigNum; i++)
find and sort all
a[i,j] = b[i,j] + c[i,j];
methods on +
each time?
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
16
Safety First
“Message not understood”
• Types & Type Checking.
• The basic rule:
A  f :    A  x : 
A  f ( x) : 
“The arg type matches the fun type.”
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
17
Type Checking for Java
• anObject.aMethod(arg1, ..., argn);
– inheritance (subsumption),
– overloading (dispatch by signature)
– overriding (dynamic dispatch by receiver
concrete type).
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
18
Limitations of Java Types
• From the Java Language Spec.:
class Point {
int x = 0, y = 0, color;
void move(int dx, int dy) { x += dx; y += dy; }
int getX() { return x; } // errors
int getY() { return y; } // errors
}
class RealPoint extends Point {
float x = 0.0f, y = 0.0f;
void move(int dx, int dy) { move((float)dx, (float)dy); }
void move(float dx, float dy) { x += dx; y += dy; }
float getX() { return x; } // errors
float getY() { return y; } // errors
}
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
19
Java Type Issues, Cont’d.
class Point extends Object {
int x_val = 0;
int y_val = 0;
// ...
boolean equal (Point other) {
return((x_val == other.x())
&& (y_val == other.y()));
}
boolean equal (Object other) {
return(false);
}
}
class ColorPoint extends Point {
// ...
boolean equal (ColorPoint other) {
return((x_val == other.x())
&& (y_val == other.y())
&& (color_val == other.color()));
}
boolean equal (Object other) {
return(false);
}
}
class TestOverLoad extends Object {
public static void main (String[] args) {
Point aPoint = new Point(2, 3);
ColorPoint aCPoint = new ColorPoint(2, 3, 5);
System.out.println(aPoint.equal(aCPoint));
// System.out.println(aCPoint.equal(aPoint));
}
}
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
20
Too Much Typing?
public static int foo(int x, int y) {
int t;
if (x < y)
t = x + 1;
else
t = y - 1;
return t * 2;
}
• We should be able to skip annotating t with
type int.
• Type Reconstruction, aka Type Inference.
• Still an open research area for Java.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
21
Binary Methods
• See [BCC+95]
• Several proposed “solutions”...
Multiple Dispatch
boolean equal(Point p1, Point p2) {...}
boolean equal(ColorPoint p1, ColorPoint p2) {...}
•We also need:
boolean equal(Point p1, ColorPoint p2)
{return(false);}
boolean equal(ColorPoint p1, Point p2)
{return(false);}
• See [CL95], [CLCM00]
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
22
What are Types For?
• Software Engineering
– Classes: data abstraction, modularity, reuse.
In Java, classes are also types.
• Safety
– type checking.
• Control Abstraction
– Dynamic dispatch
– choice of code depending on receiver type.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
23
Making Types More Expressive
• Predicate Types, [EKC98]
predicate on-x-axis([email protected])
when ([email protected] and
test(p.y == 0))
or ([email protected] and
(test(p.theta == 0)or
test(p.theta == pi)));
draw the point:
method draw([email protected]) {...}
use a contrasting color so point is visible:
method draw([email protected]) {...}
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
24
Dynamic vs. Static Typing
• Safety  Expressiveness tension.
• Mixed typing?
– Soft typing for Scheme [CF91,Wri94]
• UI / Language features to support delimited
regions with diff. regimes
• Dynamism and strong typing
– new code must maintain invariants.
– uncharted territory.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
25
Implementing Reflection
• Recall the motivation: hack all over
the program, or hack the interpreter.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
26
Implementing Reflection.
Strategies
• Interpreter Tuning
– Threading, VVM
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
27
Dynamic Optimization
• Customization [CUL91,DCG95]
• Dynamic Partial Evaluation [Sul01]
• Dynamic compilation to native [Sun
HotSpot]
– IR  Native (IR/Native interoperability)
• Jalapeño from IBM [AAC+99]
– simple native, optimized native
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
28
Dynamic Optimization, Cont’d
• HP Dynamo [BDB00]
– Native Interpreter + trace cache
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
29
Optimizing in the
Face of Dynamism
•
Key insight: while most everything
might change, most does not.
 Optimize with respect to “quasiinvariants”.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
30
Basic Technique:
Partial Evaluation
• Produces specialized versions of code
based on assumptions about values.
• See [JGS93, CD93].
• From [CD93]:
the essential purpose of partial evaluation:
eliminating interpretive overhead.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
31
Partial Evaluation
Specializing functions
f(n,x) = if (n = 0) then 1
else if (even(n) then
f(n/2, x)^2;
else x * f(n-1, x);
f5(x) = x * (x^2)^2;
• specialization with respect to 1st
parameter.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
32
When to Partially Evaluate?
• When some argument values change
much less frequently than others.
– Ray tracing, interpreters.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
33
Definition of PE
• out = [p](in1, in2)
p_in1 = [mix](p, in1)
out = [p_in1] in2;
• Equational definition of mix:
[p](in1, in2) = [ [mix] (p, in1) ] in2
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
34
Futamara Projections
• See [Fut71]
• 1st: target = [mix] (int, source)
• 2nd: compiler = [mix](mix, int)
target = [mix](int, source)
= [[mix](mix, int)](source)
= [compiler](source)
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
35
Futamura, cont’d
• 3rd: cogen = [mix](mix, mix)
[p](in1, in2) = [ [mix](p, in1) ](in2)
= [ [ [mix](mix, p) ] (in1) ](in2)
= [ [ [ [mix] (mix, mix) ](p) ] (in1) ] (in2)
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
36
Challenges for Partial
Evaluation
• Infinite looping, infinite specialization
• Efficiency, especially:
– Dynamic PE -- open challenge.
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
37
Staged Programming
•
•
•
•
Closely related to partial evaluation
Quasiquotation [Baw99]
MetaML [TS00], Modal ML[]
DyC[GPM+99], `C[EHK96], Tempo
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
38
Notes to myself
• staged programming, metaml?
• Discuss the DVM?
• Projects:
– “real” MOP for Java.
– type inference for Java.
• on stack replacement, deoptimization
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
39
Another Favorite Java Gotcha
class Problem1 extends Object {
// P is a subclass of Object,
// C is a subclass of P.
public static void foo(P x) {
bar(x);
}
public static void bar(P aP) {
System.out.println("bar on P");
}
public static void bar(C aC) {
System.out.println("bar on C");
}
public static void main (String[] args) {
foo(new C());
}
} // class Problem1
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
Object
P
C
40
Talk Overview
6.894, Spring 2001 - OODL Overview - Greg Sullivan - February 8
41
Descargar

OODL’s - The Big Picture