JUndo-- Beyond Java with Undo

This is the text of a presentation on JUndo that I gave to Pikes Peak Java Development Group (PPJDG) on Sept. 26, 2006. This was apparently the last meeting that PPJDG had. The group is now defunct. There has been no traffic on its mailing list for the last year, as shown here:


http://groups.yahoo.com/group/ppjdg/



Regardless, I think this provides a good overview of the language for those who don't want to read through long technical descriptions. Note: I've improved the implementation since I gave this presentation, so some of the "to-do" items no longer apply.




Presentation


Object-Oriented Programming (OOP)

Aspect-Oriented Programming (AOP)

Time-Oriented Programming (TOP)

This is a TOP presentation.




History


Conceived at Arizona State University circa 1998.

Major Inspirations: Prof. Edward Ashcroft, Prof. Tony Faustini

First cut of compiler tested in mid-1999.




Background


Verdantium Compound Document Framework

Distribute Small Components (Desktop Apps) Over Network

Many components need multi-level undo support in order to be viable




Motivation


Having each component implement its own undo framework causes each component to be large

Hence the need for a common framework

Framework must be general enough to encompass all components




Problems


Object Creation

Changing object members and object-object references

Objects becoming unreachable / garbage collection

Decisions (i.e. if-then)



More Problems


Scripting

Nested Operations

Error Recovery




Possible Solutions


Create A “Reverse Command” for every command (u/ by Swing).

For Instance, the reverse of “insert character” is “delete character”.

But... (see next page)




Example


int value;


public void dumbCommand()
{
if( value > 100 )
{ value = 5; } else { value = 6; }
}




Possible Solutions


Save a Memento of the data state before running command.

Comes from Design Patterns book.

Prohibitively Expensive To Save Everything.



Possible Solutions



For each member use a class with an overloaded assignment operator. Store values.

Override equiv. of malloc() and free().

Hard to implement other than C++ (e.g. Java).




Undo


General undo requires tracking all object creation, deletion, and member assignment.

This changes the semantics of the original language, and perhaps is better handled at the language level.




JUndo


JUndo is intended to provide a semantics that simplifies undo and error handing.

But it’s more than just Java with Undo...




JUndo Example



public class IntRef
{
private int val;

public int getVal( )
{ val };

public milieu setVal( int invb )
{ val := invb };

}




Operators



In JUndo there are no statements. Everything in a method body is an expression.

“:=” is a function that takes in a milieu and a value, and returns a milieu.




Currying



In C++ the “this” pointer is curried into each instance method. The JVM uses a similar technique.

In JUndo a “this-milieu” reference is curried into each method.

Jundo also provides a “now” keyword.




Pairs



Consider the next() method on a Java Iterator. Often this method both alters the iterator’s members and it returns an object.

This kind of update-and-return method is so pervasive that JUndo has a special type called the pair to handle it.




Example



public class IntRef
{
private int val;

public int getVal( )
{ val };

public milieu setVal( int invb )
{ val := invb };

public static pair[ IntRef ] new_IntRef( int in )
{
let
{
pair[ IntRef ] ref = IntRef.allocate_IntRef();
milieu asgm = ref.setVal( in );
}
with [ ref.cobj , asgm ] fi
};

}



Example



pair[ IntRef ] ap = IntRef.new_IntRef( 3 );

IntRef a = ap.cobj;
milieu t0 = ap.milieu;

milieu t1 = [ a , t0 ].setVal( 7 );

milieu t2 = [ a , t1 ].setVal( 4 );

/* ********************************************** */

int a0 = [ a , t0 ].getVal();
int a1 = [ a , t1 ].getVal();
int a2 = [ a , t2 ].getVal();

a0 is always 3.
a1 is always 7.
a2 is always 4.




If-Then Expr.


Like everything else in JUndo, if-then is an expression rather than a statement.

The expression can return any type, including milieu and pair.

if x > 5 then 25 else 36 fi

Switch is similar.





Garbage Collection



In Java, an object can be collected when it is no longer reachable.

In JUndo, an object can be collected when it is no longer reachable from any object in any milieu.

A milieu can be collected when it is no longer reachable from any object in any milieu.



Iteration



In Java, programs are primarily constructed using loops (e.g. while loops).

In intensional languages (e.g. Lucid) recursive definitions x = 5 fby prev( x )+3.

JUndo uses selections inspired by TRC.




Iteration



public interface Iterator
{
public pair[ boolean ] hasNext();
public pair[ Object ] next();
}



public interface IteratorFactory
{
public pair[ Iterator ] iterator();
}




Example



public class TestClassB
{

public static pair[ IteratorFactory ] calc( IteratorFactory fac )
{
seq now into
{
pair[ IteratorFactory ] res = select a from a : fac where
[ seq now into
{
IntRef r = ( [ IntRef ]( [ a , now ] ) ).cobj;
}
with ( r.getVal() > 10 ) fi ]
fi;
}
with res fi
};



Example



public class TestClassA
{

public static milieu calc( IteratorFactory fac )
{
seq now into
{
IteratorFactory res = ( select
[ seq now into
{
IntRef r = ( [IntRef]( [ a , now ] ) ).cobj;
r.setVal( 5 );
}
with now fi ]
from a : fac where true fi ).cobj;
Iterator it = ( res.iterator() ).cobj;
IteratorUtils.getLastItem( it );
}
with now fi
};




Example



int calc()
{
int total = 0;
int i;
int j;
for( i = 0 ; i < 10 ; i++ )
{
for( j = 0 ; j < 10 ; j++ )
{
total += i + j;
}
}
return( total );
}



public static int calc( )
{
seq now into
{
IteratorFactory af = ( ForIntLe.new_ForIntLe( 0 , 10 , 1 ) ).cobj;
IteratorFactory bf = ( ForIntLe.new_ForIntLe( 0 , 10 , 1 ) ).cobj;
IntRef total = ( IntRef.new_IntRef( 0 ) ).cobj;
IteratorFactory res = ( select
total.setVal( [ { [ForIntLeIterator]( [ a , now ] ) }.getValue() ] +
[ { [ForIntLeIterator]( [ b , now ] ) }.getValue() ] +
[ total.getVal() ] )
from total ; a : af , b : bf where true fi ).cobj;
Iterator it = ( res.iterator() ).cobj;
IteratorUtils.getLastItem( it );
}
with total.getVal() fi
};




Referential Transparency



Function returns the same thing when given the same params, i.e. f(10).

Many critical functions in C, e.g. malloc, violate this.

Like C, JUndo allocates. But the language is contrived to preserve referential transparency




Transparency



Transparency presumes that “this” and “thismilieu” are counted as parameters.

Comparison operators not supported for milieux.

Some safety is traded to get both transparency and performance.




Safety



Like C++ and C#, JUndo trades away some safety.

Comparisons should only be used on objects in the same milieu. For objects from different milieux, results are undefined but transparent.

Don’t try to access an object in a milieu where it doesn’t exist. The result is undefined.




So What Is This Good For?




It’s difficult to just “add” undo to an existing program.

JUndo started as an investigation of the feasibility of adding undo capability to Java software developed for the Arizona State University department of Physics.

there are potential applications for scripting, error control, and formal definition of algorithms.

In addition to simple classes, JUndo also has undoable maps.




Undo Mgmt.



class UndoNode
{
UndoNode nxt;
MilieuRef state;
}

class UndoImpl
{
UndoNode undoStk;
UndoNode redoState;
UndoNode currentState; /* nxt always null in currentState */

public MilieuRef getCurrentMilieu()
{ currentState.state };

public milieu commitStateAction( MilieuRef newState )
{
seq now into
{
UndoNode node = currentState;
node.nxt := undoStk;
pair[ UndoNode ] newPair = [ UndoNode , now ].allocate_UndoNode();
UndoNode newNode = newPair.cobj;
newNode.state := newState;
currentState := newNode;
redoState := null;
}
with now fi
};





Undo Mgmt.



public milieu performUndo()
{
if undoStk != null then
performUndoComp() else now fi
};

protected milieu performUndoComp()
{
seq now into
{
currentState.nxt := redoState;
redoState := currentState;
currentState := undoStk;
undoStk := undoStk.nxt;
currentState.nxt := null;
}
with now fi
};



Undo Mgmt.





public milieu performRedo()
{
if redoState != null then
performRedoComp() else now fi
};

protected milieu performRedoComp()
{
seq now into
{
pair[ UndoNode ] nodep = [ currentState , now ];
UndoNode node = nodep.cobj;
node.nxt := undoStk;
undoStk := node;
currentState := redoState;
redoState := redoState.nxt;
}
with now fi
};




Example-JUndo



class BorderModel
{
protected jobj borderClass;
protected jobj borderTypes;
protected jobj borderParam;

public jobj getBorderClass( )
{ borderClass };

public jobj getBorderTypes( )
{ borderTypes };

public jobj getBorderParam( )
{ borderParam };

public milieu setBorderObject (
jobj _borderClass ,
jobj _borderTypes ,
jobj _borderParam )
{
seq now into
{
borderClass := _borderClass;
borderTypes := _borderTypes;
borderParam := _borderParam;
}
with now fi
};

/* ... */




Example-Java




public String getClassName() {
Object obj = borderModel.pdxm_getBorderClass(undoMgr.getCurrentMil());
return ((String) obj);
}

public Class[] getBorderTypes() {
Object obj = borderModel.pdxm_getBorderTypes(undoMgr.getCurrentMil());
return ((Class[]) obj);
}

public Object[] getBorderParam() {
Object obj = borderModel.pdxm_getBorderParam(undoMgr.getCurrentMil());
return ((Object[]) obj);
}

public void setBorderObject(String CName, Class[] types, Object[] params)
throws ResourceNotFoundException {
ExtMilieuRef mil =
borderModel.pdxm_setBorderObject(
undoMgr.getCurrentMil(),
CName,
types,
params);

undoMgr.handleCommitTempChange(mil);
firePropertyChangeEvents();
}




Undo-Java



public Object processObjEtherEvent(EtherEvent in, Object refcon)
throws Throwable {

Object ret = EtherEvent.EVENT_NOT_HANDLED;

if (in instanceof PropertyEditEtherEvent) {
if (in.getEtherID().equals(PropertyEditEtherEvent.isBorderSupported))
return (PropertyEditEtherEvent.isBorderSupported);

if (in.getEtherID().equals(PropertyEditEtherEvent.setBorderObject)) {
Object[] myo = (Object[]) (in.getParameter());
UTag utag = new UTag();
undoMgr.prepareForTempCommit(utag);
setBorderObject(
(String) (myo[0]),
(Class[]) (myo[1]),
(Object[]) (myo[2]));
undoMgr.commitUndoableOp(utag, "Border Change");
return (null);
}
}

return (ret);
}




Other J-Lang


AspectJ.

Godiva (goal-directed evaluation).

Nice (ML, Haskell, and Eiffel).

Kiev (Prolog inspired)

Bistro (Smalltalk Inspired)

Scripting languages (BeanShell, Groovy)

JRuby (Ruby), Jython (Python)

Source: Wikipedia




To-Do


Improve garbage collection of JUndo objects

Exception Handling (try-catch)

JUndo linked lists (Vectors too)

Provide more coding examples / convert more components to use JUndo

Educate people

Fix remaining compiler bugs

Method Overloading




Questions?



http://verdantium.blogspot.com/