Verdantium, JUndo, and Meta

BTW, Check Out My Art-Related Blog

2008-09-08T19:17:00.000-07:00

While you're surfing, check out my art-related blog at the following address:

http://randomartbits.blogspot.com/

First Draft of Undoable Threaded Binary Trees Finished (Finally!)

2007-11-15T22:03:00.000-08:00

I've got a final draft of undoable threaded binary trees in the Umeta Sourceforge package of the JUndo Runtime project. Now I can actually use it for something...

Verdantium Artwork?

2007-11-07T21:36:00.000-08:00

I've also noticed that someone (NOT me) created a work of computer art called Verdantium:

http://wrecks.deviantart.com/art/3i-verdantium-36268967

The fractals do seem to remind one of multiple layers of embedded components...

Very Old Poster Abstract Is Still Around

2007-11-07T21:21:00.000-08:00

I was searching the web, and I noticed that an old Verdantium-related poster session link from far back in the past still works:

http://portal.acm.org/citation.cfm?id=367845.367953

It's amazing the link still works after this long. And the poster cross-references with the topic "Computing Milieux." Fascinating.

Undoable Threaded Binary Trees Almost Completed

2007-11-07T21:09:00.000-08:00

The latest draft of the umeta package of the JUndo Runtime Sourceforge project is now up (version 0.0.12). This update moves the binary tree classes much closer to completion. Hopefully I'm close to wrapping up umeta (at least in an initial draft).

More Compound-Document Formats

2007-11-05T10:10:00.001-08:00

The set of compound-document file formats seems to be expanding. At one time, the debate was primarily between Apple's Bento and Microsoft's offerings. Then came a set of formats using XML like OOXML:

http://en.wikipedia.org/wiki/Office_Open_XML

and ODF:

http://en.wikipedia.org/wiki/OpenDocument

As if two XML compound-document formats weren't enough, there is now a move to promote a new compound-document format called CDF that is being promoted by the W3C:

http://www.w3.org/2004/CDF/

And then there's Verdantium, which saves compound documents in a XML format that is closely aligned with Java's XML object serialization. It's going to be interesting to see what happens.

Test Classes Added To JUndo Sourceforge Project

2007-11-04T07:28:00.000-08:00

Added several test classes from previous demos to the TestClasses package of the JUndo project on sourceforge. In particular, TestClass.JUndo demonstrates performing simple computations and a select expression that quantifies over multiple iterator factories. Tests C, D, E, and F .java are Java test drivers that execute JUndo code. TestClassF.java executes the same computation in both Java and JUndo and then prints the answers.

TestClass.JUndo illustrates the need to quantify over iterator factories as opposed to iterators. Iterators are expended after the first use, so some mechanism is needed to refresh the iterator if one wants a second entity to quantify over it. The iterator factory provides the mechanism in JUndo for refreshing the iterators.

Origins Of The JUndo Language-- Plus Some JUndo Example Code

2007-11-03T10:43:00.000-07:00

The history of JUndo runs back to about 1998. At the time, I had written the initial versions of the compiler and the runtime. I had ideas for using a JUndo class to perform undo in an actual component (Verdantium components were already around at that time), but they were far from being fully implemented. At the time the language was called ParadoxX, and it was going to contain a series of paradoxical recursive classes. This is why the string "_pdx_" is generated by the JUndo compiler. It's an abbreviation: "_pdx_" is short for "ParadoxX". Later on in 1998 or 1999, someone (I think Professor Edward Ashcroft) read the fine print and realized that I couldn't graduate unless I had submitted a paper to somewhere. Even though the language was far from complete, we decided to submit a paper (with both of us as co-authors) about it as an initial concept and see what happened. During the editing process, Professor Ashcroft noted that a popular DBMS called Paradox already existed in the literature, and hence we probably couldn't submit the paper using the name ParadoxX. At that point I started looking for a name that I could very quickly bolt onto the existing paper. Thinking very quickly due to time constraints, I conjectured that my home town, Ephrata, was so small and isolated that the odds of someone naming a significant piece of software after it were insignificant (no offense to some of my friends who still live there). The name of the language was very quickly changed from ParadoxX to EphrataX.

I decided to re-post this paper here for a couple of reasons. First, nobody seems to know what happened to the original submission that was completed in 1999. Second, the paper provides several examples that may be useful for JUndo programmers. I made a couple of modifications to the original text to make the original examples more readable by those looking for JUndo examples. I changed "methodical" to "seq", I changed ".class" to ".cobj", etc. All the changes were syntactic in nature. Where I have something to add to the text I have put it as a comment in italics.

EphrataX—A functional programming language for investigating complex issues in software design

Summary

Few, if any, programming languages can effectively merge declarative concepts with object-oriented (imperative) programming. A first-order functional language, EphrataX, is presented here that allows manipulations of object-oriented data to be expressed in a declarative manner. Further, sets of objects can be reverted to a previous state in a straightforward fashion using the language’s constructs. Among other things, this can be very useful for returning an object system back to a previous consistent state after encountering an exceptional condition. Other areas of common programming practice where EphrataX has advantageous characteristics are given.

Key Words: object-oriented programming, functional languages, declarative languages, EphrataX

Introduction

Typical uses of purely functional programming languages like ISWIM [1] have focused on producing arithmetic functions using recursive concepts. One example of this is the example of computing factorials, which many are already familiar with.

However, focusing on arithmetic functions such as factorials as an application of functional programming has a number of drawbacks. First, the problems (e.g. how to compute various arithmetic functions recursively) tend to be primarily academic ones. Few software designers lose sleep over the particular implementation used for calculating factorials. Second, the problems tend to adequately solved for current systems. There are no particular weaknesses with the iterative methods typically used for calculating these functions that functional programming could exploit. Third, functional programming tends to use a great deal of caching of data compared to similar iterative methods, and this data caching performs no real purpose other than as a technique for improving performance. Finally, despite the caching the computational performance of functional programming is often inferior to its iterative counterpart.

This paper proposes techniques for creating more sophisticated first-order functional languages based on object-oriented concepts. These languages are primarily designed for using functional programming for solving difficult software design and engineering problems. Because many software design problems are very complex, run-time performance is much less of an issue. Functional programming can provide solutions to some problems in a few hundred lines of code that would require thousands of lines (if not more) in a procedural language. Procedural programs that perform complex tasks are often very difficult to design, create, and debug. Because they may have several pieces of code enforcing the same semantic axioms, they must be extensively tested. Some problems are so difficult to procedurally implement that it is extremely difficult for a small design team to implement a solution in a reasonable period of time. Even though the run-time performance of functional programming may not be quite as good as procedural programming for these tasks, the functionally programmed project can potentially be implemented in a shorter period of time, at less cost, with a greater degree of robustness, and with less “smoke and mirrors” in the implementation (more on this later).

Implementing interactive programs in a particular programming language requires a mechanism for the program to take a user command, and based on that command change the state of the program’s variables from a previous state to a new state. To implement interactive programs using a functional notation, a program must define the current state of the program’s variables at a time index “t” (as an explicit parameter) as a function of the previous state of the program’s variables (i.e. the state at index t – 1) and the latest command entered by the user, where there is one command for every value of “t” from the value of “t” for the first command up to the value of “t” for the current command. The command for a index “t” can itself be treated as a function of “t”, as can the state of the program’s variables at a index “t” given that a default initial state is used for the index before the first command is executed. Thus, a function getState() that defines the state of an interactive program can be written in pseudocode as the following:

command getCommand( int t ) = /* An expression for the input command
given “t” for 1 <= t <= last command received */;

state getState( int t ) if t == 0 then /* initial state */
else /* An expression using getCommand( t ) and
getState( t – 1 ) */ fi;

where the words state and command are meta-level symbols that are replaced by the actual datatypes used to represent a program state and a program command (sometimes also called an event) respectively in a particular design. For instance, in an object-oriented language one might declare a class that represents a command in a particular kind of system.

When such a parameter “t” is used in a piece of code to define how a program or routine like getState() reacts to a set of consecutive inputs, “t” is called a time stream. A set of consecutive values returned by a function on a time stream “t” is said to be defined in terms of the stream “t”. This has some similarities to the concept of a time stream in the programming language Lucid [2], and the Lucid-like implementation of interactive programs in Visual Java [3]. Visual Java in particular provides a compelling example of how an intensional language can be used to implement interactive software. However, there are some important differences between the term “time steams” as used in this paper, and “time streams” in Lucid. In Lucid, a time stream is a concept of intensional programming that is based on an implicit context. For the purposes of this paper, a time stream is a design pattern based upon the use of explicit parameters in functions. A time stream may be used in a functional paradigm any time that one wants to implement a state machine in terms of “stateless” functional programming by expressing the state as a recursive function of the index.

As an example of the use of a time stream, consider a functional program that emulates a subset of the interactive behavior of the “MS-DOS Prompt” found on many personal computers. The DOS prompt provides a blinking cursor. As the user types alphanumeric characters, the characters are interactively appended to the prompt line, and the position of the cursor is moved to the end of the line. A special character, which in this example will be called the backspace character, deletes the last character that appears on the prompt, and moves the cursor back one position, allowing the user to substitute another character in place of what was previously there. Assuming the initial state is a prompt line with no characters, the table below shows how the entry of sequential characters (over time) affects the interactive state of the DOS prompt:

Character Entered	DOS Prompt Display
A	A
B	AB
C	ABC
BACKSPACE	AB
D	ABD
E	ABDE
F	ABDEF
BACKSPACE	ABDE
W	ABDEW

These input characters can be handled in a functional notation by assigning each input character in sequence a number starting at 1. For instance in the example above, the first input character, “A,” would get the number 1, the second input character, “B,” would get the number 2, etc. Thus one can declare a function like the following:

char inputChar( int t ) = /* … */;

where the character returned by the function is the tth character in the input sequence. For instance, in the example given in the table above, inputChar( 1 ) would be “A,” inputChar( 2 ) would be “B,” inputChar( 4 ) would be BACKSPACE, etc. The inputChar function acts as the implementation of the getCommand, in the pseudocode given above, for this example. It defines a series of commands (not the same as DOS commands) over a parameter “t”, where each command is the input character that the user has entered. The term “command” is used in this context because each character typed represents an interactive request by the user to change the current state of the DOS prompt. That is to say, when the user types “A,” the user is commanding the system to add the character “A” to the current prompt display. For implementation in an interactive program, assume that the implementation of this function is dynamically linked in some manner to the external system API that actually gets characters from the keyboard. Also, it is assumed that a routine calling inputChar is not going to use a value of “t” that is “from the future.” That is to say, it will not use a value of “t” corresponding to a character that is after the last character entered in the current runtime state of the prompt (in principle requests for future characters could be handled, but the user interface to do this is unwieldy in practice because it potentially asks the user questions like “what is the twentieth character you’re going to type?”).

One can then define two functions to get the length of the prompt at a particular “t,” and the contents of the prompt at a particular “t” as follows:

int getLength( int t )
= if t == 0 then 0 else
(
if inputChar( t ) == BACKSPACE then
(
if getLength( t – 1 ) > 0
then getLength( t – 1 ) – 1 else 0 fi
)
else getLength( t – 1 ) + 1 fi
) fi

int getStringChar( int t , int ChrIdx )
= if ChrIdx > ( getLength( t ) – 1 ) then ERROR_CHAR
else
(
if ( ( getLength( t ) – 1 ) == ChrIdx ) && ( inputChar( t ) != BACKSPACE )
then inputChar( t )
else getStringChar( t – 1 , ChrIdx ) fi
) fi

These two functions are the analogue of the getState function defined above. An explicit assumption is being made that some external system API is tracking what these functions are returning for the most recent value of “t,” and is writing this information to the display device. It is also assumed that this external API will not try to call either function for a value of “t” that is “from the future.” Because the prompt may contain multiple characters, a mechanism is needed to define what each character in the prompt is. This is provided by the ChrIdx parameter of getStringChar. Passing values of ChrIdx , for a particular “t,” between 0 and getStringLength( t ) – 1 inclusive returns each character in the prompt from left to right, unless getStringLength( t ) is zero. If getStringLength( t ) is zero, then the prompt is empty. The combination of the length of the prompt plus the set of characters in the prompt define the state of the prompt for a particular “t”.

In the context of using time streams to investigate difficult software design and engineering problems, one can also view the caching of data in a different light. A functional implementation of the MS-DOS prompt example above would likely need to use caching for strictly reasons of improving runtime performance. The use of a cache keeps the implementation from using recursion in an excessive fashion each time a character is added to the prompt. However, the cache is useful for more than just a gain in runtime performance. Many complex applications already engage in the caching of data, but they use different terminology to describe it. Many examples of applications software for personal computers implement what is called “multilevel undo”. That is to say, they allow the user to retract an arbitrary number of previously committed actions. To do this, they must keep a store of previous program states, and then be able to restore those states later. If the user’s actions are considered to be defined over a time stream, then the caching of all changes from one program state to another provides a straightforward and efficient representation of the information that that application already needs in order to perform multiple levels of undo. For instance, multilevel undo could be added to the MS-DOS prompt example by providing a mechanism for an UNDO character command to cause the prompt to return a state for a time “t” that is identical to a previous one (before t – 1 ).

Another example of software that already stores cache-like data sets concerns those programs that already keep logs or audit trails of their actions. These logs are often kept so that transactions on the system that had the effect of leaving the system in an inconsistent state can be rolled back, placing the system back in a previous consistent state, or for the purposes of recovery in the event of a crash. In many cases these logs store all of the information that an implementation of a functional language would place in its cache, but for different purposes. This process of rolling such a system back to a previous state is similar in some aspects to multilevel undo, but appears in a different (often non-interactive) context and with different overall requirements.

Functional languages excel at the ability to return a system to a previous state in a straightforward fashion, and the caching of information is much less of a problem because the log being stored can double as a cache of previously computed information. Using a functional language would simply put that log (i.e. cache) in a functional context.

Sophisticated error handling is an area where the caching of data is useful for similar reasons. Many times the semantics of a module are so complex that a program actually starts to modify its data until something is found that violates one of the axioms that the module is trying to enforce. That is to say, it is sometimes extremely difficult to determine what will lead to an error condition a priori. For example in a system that stores employee information, a set of axioms, such as one that asserts that no supervisor can make more that ten times the sum of the salaries of those employees he or she directly supervises, would make it difficult to check a priori a request to adjust the salaries of multiple employees based on some criteria. It usually makes more sense in this example to adjust all the employee salaries first, and then see if anything went wrong. At this point where a problem is found the module attempts to change the data back to its original state, and then return a status value indicating that some error had occurred. In many procedural implementations, this is easier said than done. At the point that the error was detected, the procedural implementation has to “know” what changes were made previously. For simple systems, algorithms can be written that can reverse the original actions. But often the systems are not simple, and thus can not be done without a large input of man-hours on the part of those implementing the system. We will show that functional programming through the use of constructs such as time streams provides a mechanism to ensure that an entire system or sub-system can be returned to its previous state using a single assertion. Any valid time value can be passed to a function defined over a time stream. As a result, a function defined over a time stream can handle exceptional cases by returning the last consistent state found previously in the time stream. That is to say, it returns the result of a function call with a previous time value.

Functional languages could operate very efficiently in those domains where caching (by any other name) is already widespread. And for some of the reasons listed earlier, procedural languages often do not provide an adequate solution to many design issues that are seen in practice (as opposed to purely academic ones), whereas functional languages have features that make them advantageous for implementing these systems. So why are functional languages not generally used here? The main problem is that there has not been a functional language that supports the level of data abstraction required to directly address these problems. Data abstraction allows complex pieces of data to be subdivided into simpler ones that can be individually manipulated. For instance, a list of data can be manipulated independently of other structures. A data abstraction can also be used in several places to manage other varying kinds of data (e.g. a list of people, a list of buildings, etc.). The ability to use the same abstraction in multiple areas reduces the amount of code required to implement a particular project, but requires that the operations that act on the data also be abstract in the sense that they can operate on different kinds of data (e.g. removing an element from a list has to work independently of whether that list is a list of people or a list of buildings).

Object-oriented languages provide an extremely flexible framework for data abstraction, so one might be motivated to attempt to make a functional language object-oriented (or vice versa). Although some object-oriented concepts can be implemented using a functional language, creating a real merger of the two is very difficult. The abstract operations that allow structures to be manipulated in a more straightforward fashion than is possible in a non-OO language, by separating the interface to a structure from its implementation and providing built-in high-level functionality, tend to be very procedural in nature. And this procedural nature has to be removed in some fashion so that operations so can be rolled back at a later time. However, many of the practical requirements for data abstraction create roadblocks that tend to stymie attempts to integrate OO and functional concepts. A piece of abstract data (called an object in object-oriented circles) often has sub-data which also is abstract. An operation on such a piece of data often has effects that carry through to operations being performed on the sub-data. As a result, it is difficult to declare the state of a piece of data without some knowledge of all operations that might directly or indirectly affect that data. Because a typical OO language is imperative, it does not need to declare the values stored in each object in some functional, clausal, or other axiomatic sense. Instead, an imperative OO method overwrites the previous data states, destroying whatever used to be there. This greatly limits the number of places where a data abstraction can be used in a declarative language as opposed to an imperative one. An abstract structure A can only be used in some other structure B if all the places where operations on B might affect A have already been declared in some fashion. This does not provide a particularly abstract form of programming because every structure has to know about every other structure that might use it.

In hindsight, today I would probably do something like a DOS prompt with JUndo objects as opposed to JUndo recursion. See the DrawApp component in Verdantium for an example.

This paper presents a language called EphrataX that solves the problem of merging the functional and object-oriented data models. EphrataX combines elements of syntax and semantics from the Java [4] object-oriented language and the ISWIM [1] functional language, with some additional structures to integrate the semantics of the two. EphrataX is able to achieve this merger by defining how the state of a set of objects, i.e. the particular values of all members of all objects and classes in a set of objects that does not contain a reference to any object outside the set, changes over time in a functional manner. In a language like C++ [5], a set of objects has a particular runtime state that changes in real time, and accessing a particular object always returns the current runtime state of that object. The state changes at runtime because the C++ program overwrites various object members during its execution. While the runtime state of a set of objects in C++ is a function of time, the state of a set of objects in EphtataX is, analogously, defined as a function of an explicit context. Thus, examining the state of an object requires a combination of two data items in EphrataX. The first item is the unique identifier of the object, similar to an object reference in Java. The second item is the context that represents the equivalent of a timepoint (in a language like C++) for which a set of (potentially interdependent) objects have a particular state. In EphrataX, this context for a set of objects is called a milieu, and is a fundamental datatype in the language. The values of the members of the objects defined in terms of a particular milieu do not change. Modifications are not made directly to the state defined by a milieu in the same sense that methods in an OO language modify objects on the heap. Instead, a method that “changes” an object value, defined by a milieu A, returns a milieu B that defines object values identical to those defined by milieu A, except for the change made by the method.

For instance, suppose one wants an EphrataX method that mimics the behavior of a Java [4] method that sets member W of object X to value Y, where the previous value (before the execution of the method) of member W of object X will be called Z. The Java method will use a statement such as X.W = Y;. In doing this, it overwrites the previous value of X.W. An EphrataX method, given a milieu A, emulates the semantics of such an overwrite by returning a milieu B such that all objects’ member values defined by B are identical to those defined by A except X.W. In the returned milieu, B, X.W will have value Y. By contrast, X.W in milieu A will still have its original value of Z.

As the state of set of objects is defined as a function over the set of milieux, a particular milieu can be treated as if it is the state of an object-oriented program. Hence the word state in the getState() pseudocode presented earlier is often (but not always) replaced by milieu in an actual EphrataX program. This means that a milieu is also an important datatype for defining state machines in the language. A function defined over a stream that returns a milieu completely defines the runtime state of an object-oriented program after executing a sequential list of input commands.

Because methods do not actually alter the state defined by a milieu, the milieux act in a manner consistent with any other declarative functional definition. The fact that a milieu represents the state of a set of interdependent objects at a particular time means that for any piece of data in a milieu, its sub-data are also in the same milieu. As a result, an operation on a piece of abstract data can modify its sub-data without violating either the principles of data abstraction or the fundamental concepts of functional programming. The next section will show some examples of the language, and explain why this is true.

The EphrataX language

As a language, EphrataX is currently in the design phase, with attempts underway to produce an implementation of a compiler for a first version of the language. However, enough of the language has been defined to give a working description of how an EphrataX program would function. To get an introduction to how the EphrataX language works, consider the simple EphrataX example class below:

class IntRef
{
private int val;

public int getVal( )
{ val };

public milieu setVal( int inv )
{ member{ [ this , thismilieu ].val := inv } };

}

This is a simple class that allows access to a single private integer val through two public accessor methods, getVal and setVal. Note that, similar to other OO languages but unlike ISWIM [1], datatypes are declared for each parameter and value returned. Unlike most other OO languages, the method body enclosed in curly braces is an expression rather than a compound statement. In fact, there are no statements in EphrataX at all, only functional declarations in the form of methods. This makes EphrataX a totally declarative language in the sense that imperative semantics (i.e. statements that either directly alter or side-effect previously defined values) are never used. Instead, functions are defined that leave previously declared values unchanged. One can construct compound definitions in EphrataX (the closest equivalent to a compound statement in a traditional language) using a ISWIM-like let block.

The functional nature of EphrataX may lead one to ask “how do I modify an object W in a milieu X to a state Y if I’m not allowed to directly alter or side-effect W?” It sounds impossible, bit it’s not. The answer is not to modify the state of the object in X, but to declare a new milieu Z that is identical to X except for the fact that the state of the object W is Y. That is to say, one needs an operation that returns a milieu as a function of another milieu such that the appropriate modification appears in the returned milieu. An instance of such an operator is shown in the setVal method in the above example. This method will be discussed in more detail below.

EphrataX performs strong type checking in all parts of the language. Besides the declared parameters, two additional elements are curried into each instance method. The first is the this reference that points to the instance on which the method is being called. The second is a milieu called thismilieu that contains the milieu on which the method is being called. In a typical OO language (e.g. C++ [5], Java [4]), an object on the heap may contain different values at different times. Since a milieu defines the state of an object at a particular time, the same object may contain different values in different milieux. As a result, an instance method must know both the OID (an OID is a reference that uniquely identifies a particular object) of the object and the milieu in which execution is taking place in order to be able to uniquely specify the element of instance member data to be accessed. The getVal( method returns the instance value of val. Just as the object accessed in the expression is assumed to be the this object, the milieu is assumed to be the thismilieu milieu. As a result, nondestructive accessor methods can be written in a manner very similar to that in other OO languages.

In a typical OO language like C++ [5] or Java [4], an object OID or pointer is curried into each call to an instance method, and then this curried reference shows up in the method either implicitly or through the keyword this. EphrataX is different because an OID alone does not provide sufficient information to access the state of a particular object. Instead, a milieu is needed as well. As a result, both an OID and a milieu are curried into all EphrataX instance methods, and a milieu is curried into all EphrataX class methods. The curried OID in an instance method can be accessed by using the keyword this, and the curried milieu can be accessed by the keyword thismilieu. Both this and thismilieu are also used implicitly in EphrataX in a manner analogous to the implicit use of this in C++ and Java. For instance, the getVal( method in the example above makes implicit use of both this and thismilieu.

The setVal( method in the example above deserves closer attention:

public milieu setVal( int inv )
{ member{ [ this , thismilieu ].val := inv } };

Where the usual setVal( method in C++ [5] or Java [4] returns void, this method returns a milieu, and the milieu returned is given by the expression member{ [ this , thismilieu ].val := inv }. This expression demonstrates how instance members are modified in EphrataX. Note that this expression does NOT use the lvalue/rvalue semantics in C or C++. Instead EphrataX treats this expression as a single production with the following BNF: member{ . := }. In terms of semantics, the expression returns a milieu that is identical to thismilieu except that the val member of the this object has value inv. Although this expression does not have any side-effects, it can be used in a straightforward fashion to produce sequences of milieux that are analogous to how methods in a typical OO language modify the heap over time. In general, the expression member{ [ A , B ].C := D } returns a milieu identical to B except that the value of A.C is equal to D.

In EphrataX, a milieu is a primitive type just like an integer or a character. Milieux can be manipulated and stored in objects just like any other datatype. This is an important feature because it allows object systems to manipulate entire milieux of data within an application. This allows a set of instances to be pigeonholed into a single element that can be moved from structure to structure as necessary. There are a number of design advantages in being able to keep a closed system of objects as an independent element in a data structure. It makes that set of instances so that they can not be manipulated by another object unless that object has access to that particular milieu. This can be used to shield a set of objects from unauthorized access. It also allows for the creation of data structures of milieux, which is important for implementing concepts such as multilevel undo. An example of a simple class containing a milieu as an instance member is shown below:

class MilieuRef
{
private milieu val;

public milieu getVal( )
{ val };

public milieu setVal( milieu inv )
{ member{ [ this , thismilieu ].val := inv } };

}

The MilieuRef class in this example is just like the IntRef class given above, except that every instance of the word int was replaced with milieu. Otherwise, they have identical semantics. Storing a milieu inside an object is useful when attempting to implement sophisticated error handling, and/or multilevel undo. Note that in the setVal( method, the milieu stored in val if different from the milieu curried into the keyword thismilieu. The thismilieu milieu defines the context in which the MilieuRef object has a particular state. Meanwhile, the member val can take on a variety of states depending on the context thismilieu in which it is accessed. As a result, the value of val is defined by the context thismilieu but may not be equal to thismilieu. However if [ W , X ].setVal( Y ) returns a milieu Z, then one can say that the value of W.val is defined to be equal to Y in the milieu Z. Or put another way, Y is equal to [ W , Z ].getVal().

An object can also be an instance member of another object. EphrataX uses the same conventions for instance declarations as Java [4] in that a declaration as a member or a variable is actually only declaring a reference to a “heap allocated” object, not an actual object. The reference may point to an actual object, or it may point to null. Objects can be created through class methods. The construction of objects will be discussed in detail in a subsequent part of the text. A simple example of an object that stores a reference to another object is shown below:

class MilieuRefRef
{
private MilieuRef val;

public MilieuRef getVal( )
{ val };

public milieu setVal( MilieuRef inv )
{ member{ [ this , thismilieu ].val := inv } };

}

class IntRefRef
{
private IntRef val;

public IntRef getVal( )
{ val };

public milieu setVal( IntRef inv )
{ member{ [ this , thismilieu ].val := inv } };

}

Like the MilieuRef example earlier, this is another simple modification of the IntRef example above with different datatypes.

Using Methods

The real power in EphrataX is not so much in the fact that objects can be declared as it is in how the declarations can be put together. Below is an example of a class called ControllerClass that demonstrates this concept. This is not intended to be a complete class definition in itself, but is intended to demonstrate a concept. Assume that ControllerClass has other accessor methods that are not shown here.

class ControllerClass
{
private IntRef val1;
private IntRefRef val2;

/* … */

public milieu modifyVals( int v1 , int v2 )
{
let
{
milieu p1 = method{ [ val1 ,
thismilieu ].setVal( v1 ) };
IntRef v3 = method{ [ val2 , p1 ].getVal( ) };
milieu p2 = method{ [ v3 , p1 ].setVal( v2 ) };
}
with p2 fi
};

}

The class contains an IntRef and an IntRefRef, which are classes defined in earlier examples in this paper. The method modifyVals( sets the single-referenced integer to v1, and the double-referenced integer to v2. The operation is defined functionally using a let block that is similar to the let block in ISWIM [1], except that each entry in the let block has a type declaration. Note that the second and third lines of the let block use the milieu p1 rather than thismilieu. If they used thismilieu, then the modification in the first line of the let block would be lost because thismilieu does not contain the modification. Instead, the second modification needs to act on the milieu that contains the first modification. In this way, one can create a milieu that contains subsequent changes to multiple members of objects.

As mentioned earlier, milieux in EphrataX provide a context for an entire closed system of objects, rather than a context for a single isolated object. If instead there were one context per object, a method would need a context for every object that it was designed to read or modify. Further such a method would need to return one new context for every object that it modified, and dependencies between objects (which can form a possibly cyclic digraph) would be difficult to manage. By contrast, consider the EphrataX semantics in the first line of the let block above:

milieu p1 = method{ [ val1 , thismilieu ].setVal( v1 ) };

Because a milieu describes the state of all objects in a closed system, the syntax of getting the necessary context information from a method is invariant of the complexity of the method’s implementation, the number of objects the method modifies, or the number of members in each object that the method modifies. The method setVal( can modify one object defined by thismilieu or every object defined by thismilieu, and it only needs to return one milieu to describe the change(s). This invariance is an important feature of the language because it means that a method in EphrataX can act as a “black box” that can be re-implemented to modify objects in different ways without the need to change the parameters used to call it. Thus, EphrataX methods can implement abstract operations on arbitrary pieces of data. In the case above p1 is set to the result of calling the setVal( black box the parameter value v1.

So p1 contains a milieu that is (more than likely) different from thismilieu in some way. One may now be tempted to ask “How does one make use of the new context contained in p1 as opposed to the previous one in thismilieu?” Now that the black box has caused a modification, how is that modification interrogated? This is shown in the second line of the let block in the example above:

IntRef v3 = method{ [ val2 , p1 ].getVal( ) };

This line calls getVal( on the object val2 like previous examples. The difference is the milieu used in the call. The milieu used is p1 rather than thismilieu. If the object referenced by val2 had in fact been modified by the setVal( method in the first line of the let block, then v3 would show that change. But that is not the case in this example, so the method simply returns the same reference found in thismilieu. Getting the OID for v3 is important to completing the last line of the let block:

milieu p2 = method{ [ v3 , p1 ].setVal( v2 ) };

This creates a milieu p2 that is a modification of p1. This shows how successive modifications to a set of objects can be implemented in EphrataX. The first modification took thismilieu to p1. The second modification took p1 to p2. The choice to which milieu to employ in a particular modification is very important. For instance if the second modification took thismilieu to p2, then it would lose anything in p1 that was different from thismilieu. Sometimes losing information in this fashion is a good thing. As an example, it can be used to throw away modifications that were caused by erroneous input data. In the example above, however, the desired result is a milieu containing data from both modifications. Therefore, p2 is implemented as a function of p1.

Note that the objects modified by the method were objects other that the one that the method was called on. If one considers the ControllerClass instance to be a piece of data, and the IntRef objects to be its sub-data, the one can see how many aspects of data abstraction can be specified in a declarative fashion. Methods can be used to provide a more object-oriented implementation as follows:

class IntRefRef
{
private IntRef val;

public IntRef getVal( )
{ val };

public milieu setVal( IntRef inv )
{ member{ [ this , thismilieu ].val := inv } };

public milieu setReferencedVal( int inv )
{ method{ [ val , thismilieu ].setVal( inv ) } };

}

class ControllerClass
{
private IntRef val1;
private IntRefRef val2;

/* … */

public milieu modifyVals( int v1 , int v2 )
{
let
{
milieu p1 = method{ [ val1 ,
thismilieu ].setVal( v1 ) };
milieu p2 = method{ [ val2 ,
p1 ].setReferencedVal( v2 ) };
}
with p2 fi
};

}

This example is very similar to the previous ControllerClass example. Here the same modification is made to member val2 through the method setReferencedVal. This shows how modifications can be routed through multiple methods. The modifyVals( method calls setReferencedVal( which calls setVal(. It is the milieu returned by setVal( that is the one that actually shows up in p2. The object that gets modified by setReferencedVal( is two methods removed from the one on which modifyVals( was called. Arbitrarily sophisticated uses of method calls can be set up in a similar way. Any kind of modification of objects through method calls that is possible in a language such as Java [4] can be implemented functionally in EphrataX through the appropriate use of milieux.

Pairs and Object Creation

Like the language Objective C, EphrataX does not have constructors. Objects are constructed using class methods. This is advantageous for classes that are designed to only create objects in a selective fashion. For example, some classes are designed to only allocate a new object if an object of identical value does not already exist. A number of string implementations use this to ensure that two strings are identical iff. their OIDs are. This can greatly reduce the amount of computation time required for string comparison. Using a class method (as indicated by the static keyword) instead of a new operator gives each class direct control over when and how its instances are created. An example of a class method to create an object of class UniqueUnionClass is:

public static pair[ UniqueUnionClass ] new( StreamClass arga ,
StreamClass argb )
{
let
{
pair[ UniqueUnionClass ] q = class_method{
[ UniqueUnionClass , thismilieu ].allocate() };
pair[ NonUniqueUnionClass ] r = class_method{
[ NonUniqueUnionClass , q.milieu ].new() };
milieu q2 = member{
[ q.cobj , r.milieu ].arg1 := r.cobj };
}
with [ q.cobj , q2 ] fi
};

This example also introduces a new EphrataX data type called the pair. The pair of a object reference of type A is defined as . Pairs do NOT have OIDs, and they do not exist in milieux except as members of objects or classes. One can see why the pair is useful by thinking about what the new method does. It both creates a new object, and it creates a modified milieu that contains that new object. The pair makes it easy to return both of these entities to the caller at the same time. A pair is built by placing the item and milieu that it is to contain in brackets in a manner like the following: [ obj , thismilieu ]. Elements can be extracted from a pair using the .cobj and .milieu operators. The construction class methods, which can be given arbitrary names, allocate new objects by using the protected class method allocate( provided by the runtime. After allocating the object, the method is then free to initialize it in arbitrary ways (as the above example does).

Because a pair always contains two and only two elements, the compilation of a pair takes on many of the characteristics of the compilation of a primitive type. An EphrataX compiler treats pairs very differently from the manner in which a standard compiler would handle code generation for a typical derived type such as an array or a record. To review, expressions on a primitive type in typical languages are mapped to primitive operations (in a language like Three Address Code) that write to temporary variables defined by the compiler. Each primitive operation has one primitive temporary variable as its result. Similarly each primitive expression on an EphrataX pair, in the compiled representation, has two temporary variables as its result: one for the object reference and one for the milieu. Moreover each primitive operation on a pair maps to two Three Address Code operations, one for each of the two temporary variables that make up the pair. In this way pairs get mapped directly to lines of Three Address Code in the same way that a primitive type does, except that everything with a pair gets mapped to two lines instead of one. This allows operations on pairs to mapped into more efficient code than is otherwise possible. This is an important optimization because pairs play a fundamental role in the language.

Inheritance, Encapsulation, and Polymorphism with Functional Programming

An object-oriented language can be defined as one that supports inheritance, encapsulation, and polymorphism. EphrataX supports all of these concepts. Inheritance is declared using the extends keyword:

class abc extends xyz
{

private int added_field;
}

If the extends clause is not specified, the class is assumed to extend a common base class called Object. The first version of EphrataX is currently expected to support single inheritance, with multiple inheritance to be studied as a possibility for a future version. Encapsulation is provided by the private and protected keywords. These keywords can be used to prevent data from being accessed in an unauthorized fashion, which makes the software more robust against accidental corruption. Encapsulation can potentially also apply to classes. For instance, a declaration like the following could be created:

protected class xyz
{
/* … */
}

However, the exact semantics of class-level encapsulation have not been worked out at the present time. Polymorphism exists because a subclass can add members and/or override methods. All methods in EphrataX are “virtual” in the sense that they can be overridden by subclass methods unless the method is declared to be final. Further, any class can be subclassed unless the class is declared to be final.

Abstract classes and methods (also known as pure virtual methods) can be declared using the abstract keyword (similar to Java [4]). A method can only be abstract if it is contained in a class declared to be abstract. The allocate() method of a class will not exist unless the class is not abstract. A subclass of an abstract class is defined to be abstract unless it overrides all abstract superclass methods with non-abstract declarations.

In addition to its object-oriented features, EphrataX is also a fully functional language. Any EphrataX method can contain an entire ISWIM-like program. For example, here is an example of a program that performs recursive processing within a EphrataX method.

class FacClass
{

public static int evalFactorial( int inv )
{
let
{
int fac( int x ) = if x == 0 then 1
else x * fac( x – 1 ) fi;
int y = inv;
int outv = fac( y );
}
with outv fi
}

}

JUndo doesn't allow a function to be defined in a let block as shown above. Although doing so can be used to create some interesting mathematics, it can also be used to create bad software engineering. Functions like fac( should be declared as methods so that one can take advantage of inheritance, polymorphism, and encapsulation. This leads to cleaner designs.

EphrataX follows the Java [4] convention that all “code” (e.g. all functional programs) must exist within some method. That is to say, there are no “global” functions. All functions lie within the scope of some class. However as can be seen in the example above, this does not place any limitation on what one can actually accomplish. A EphrataX program can be executed by calling a class method with the curried value of the initial milieu (also available from the initial_milieu keyword), similar to the use of the main( method in Java applications. The precise mechanism for doing this has not yet been worked out. The current version of EphrataX under development contains a complete set of functionality for producing an functional program, but does not provide some of the operators from intensional programming such as “fby”, “prev”, “next”, and “at”. These operators will be addressed in a future version of the language.

Looking back, I eventually addressed the "fby" problem by doing something different. The typical "fby" expressions generate recursive schemas that can't be mapped into while schemas without sophisticated optimization techniques. One possible alternative was something similar to the Domain Relational Calculus in the Datalog language, but there were some severe mismatches inherent in this approach. JUndo now uses the "select-from-where" declarative syntax from Tuple Relational Calculus (TRC) languages such as SQL. That JUndo select doesn't actually use TRC even though the select expression has the same syntax. The advantage of the "select" syntax is that it's a declarative syntax that generates while schemas by default (while schemas are usually more efficient than recursive schemas). It also potentially permits some 4GL-like code optimizations in the future.

Seq Blocks

In addition to let expressions, EphrataX also provides seq expressions as a form of “syntactic sugar” to aid in the creation of code. The use of milieux can sometimes be tedious. In a let block, a milieu has to be declared for every state change, and then that milieu has to be used in the context of the proper method. The seq expression is intended to simplify this process by currying milieux in a sequential manner so as to produce a semantics resembling a sequential block of procedural code. Below is an example of an expression and its seq counterpart.

let
{
milieu a0 =[ abc , thismilieu ].setVal( 20 );
int q2 = [ xyz , a0 ].getVal( 15 );
milieu a1 = [ xyz , a0 ].setVal( 45 );
milieu a2 = [ def , a1 ].setVal( q2 );
milieu qx = [ ghi , a2 ].setVal( [ abc , a2 ].getVal() +
[ xyz , a2 ].getVal() );
}
with qx fi

seq thismilieu into
{
abc.setVal( 20 );
int q2 = xyz.getVal( 15 );
xyz.setVal( 45 );
def.setVal( q2 );
milieu qx = ghi.setVal( abc.getVal() +
xyz.getVal() );
}
with qx fi

As one can see, the seq block greatly simplifies performing an ordered set of tasks. It does this by using a set of heuristics to transform the lower seq expression into something computationally identical to the upper let expression. Essentially, the seq block is parsed as if it is a piece of procedural code, and then the compiler determines how to declare and curry the proper milieux so that each method gets the right conceptual snapshot of the heap. This isn’t as hard as it sounds. In EphrataX, a method can not have a “side effect” in the procedural sense unless it returns a milieu. So for instance the milieu that goes into the method on the third line of the seq block, xyz.setVal( 45 );
, is found by moving upward until one finds a line where a milieu was returned by the expression, but no milieu was declared as taking that expression. This yields the milieu returned by the first line of the block, abc.setVal( 20 );. The procedure becomes slightly more complex when path expressions are employed, but follows the same general principle.

Casting of Object Types

One of the powerful features of the Java [4] language is the ability to use typecast and instanceof operators to cast an object from a common superclass to a subclass. This is particularly useful when a data structure contains a number of instances of a superclass as its data, and one wants a traversal procedure to separate these instances based on their subclass memberships. Java automatically checks all object casts, and returns a cast value of null if the superclass object being casted is not actually a member of the desired subclass. This prevents an object reference from ever pointing to an object of the wrong type, and prevents the Java VM (at least in theory) from ever entering a situation where it might core dump. In EphrataX, a pair of type pair[ A ] can be cast to pair[ B ] where B is a subclass of A. Although a pair can be cast, an object by itself can not. This is because some object languages (NOT the current version of EphrataX) allow for subclass membership to be predicate-defined. That is to say, which subclass an object belongs to is based on a predicate whose truth can change at run-time. For instance, an object of superclass Person may have two subclasses called Child and Adult with a predicate stating that a Person is an Adult if its age attribute is 18 years or greater, otherwise it is a member of the Child class. Updating the age of a Person could then cause that Person object to switch from being an instance of Child to an instance of Adult. In the EphrataX paradigm, this means that that an object can belong to a different class depending on which milieu it is in. Although EphrataX does not implement this kind of functionality, letting the programmer cast an OID without reference to what milieu it is in would effectively prohibit any future extension of EphrataX from ever being able to directly use predicate-defined subclassing. So to leave the door open to possible future enhancements, it is a requirement that only a pair can be typecast. A EphrataX runtime can then check the actual snapshot of the object in the milieu specified as part of the pair before casting. An example of an object cast in EphrataX is as follows:

[ SubClass ]( [ super_class_object , object_milieu ] )

Path Expressions

Path expressions are a typical part of OO programming in languages such as C++ [5] and Java [4]. For instance, in a set of Java classes like the following:

class Z { /* … */ }

class Y {
/* … */

Z getZ( ) { return( MyZ ); }
Z MyZ;
}

class X {
/* … */

Y getY( ) { return( MyY ); }
Y MyY;
}

class W {
/* … */

X getX( ) { return( MyX ); }
X MyX;
}

a Java program can use a variable MyW of type W in an expression such as MyW.getX().getY().getZ(). A analogous expression can be written in EphrataX as long as one is conscious of which milieu is being curried in. One can make the milieux explicit by using the bracketed form [ [ [ MyW , p1 ].getX() , p2 ].getY() , p3 ].getZ() where p1, p2, and p3 are milieux.

Emulating Pass by Reference Semantics

Passing variables by reference is a technique commonly used in a number of procedural languages. In Java [4], the OID of a mutable object A can be passed as a parameter to a method B, and then the code for B can modify the state of A. Such a modification is typically referred to as a side-effect. Even though EphrataX is a functional language, it can take advantage of an object passed to a parameter in a similar way. Consider the following method:

public static milieu incrementObject( IntRef inv )
{
let
{
int v = inv.getVal();
milieu outv = [ inv , thismilieu ].setVal( v + 1 );
}
with outv fi
}

The method above takes in the OID of an IntRef inv (which is assumed to be valid in the context thismilieu). It then creates a milieu outv in which the value contained in inv has been incremented. Finally, it returns outv as the result of the method. To computations using the milieu returned by incrementObject(), it will appear as if the incrementObject() method had produced a side-effect on the passed object inv. In this way, it should be possible to translate any use of pass-by-reference into EphrataX code.

Re-Examining the previous MS-DOS prompt example

Now that many of the constructs of EphrataX have been defined, one might wonder how the MS-DOS prompt example given above would be modified if it were to be coded in EphrataX. The DOS prompt example listed earlier in this article used a “clever” recursive algorithm to define each character in a string for a particular time “t”. By “clever,” the author means that some amount of inductive sophistication is required on the part of the reader in order to fully comprehend why the code returns the correct prompt character for a particular value of ChrIdx. However, in a real-world program it is very hard to maintain a set of source code that repeatedly employs this kind of clever use of recursion. Object-oriented techniques in EphrataX can be used to shield the programmer from the complexities of these inductive relationships. Instead of recursion based on the value of ChrIdx, an EphrataX program would simply make use of a string class that supports methods for concatenating characters to strings, and extracting substrings. An example of this is given below assuming the existence of a String class patterned after the one in Java [4]. Although the code below is somewhat more lengthy than the previous DOS prompt example, it requires much less inductive sophistication, it is more modularly organized, and it can accept future modifications in a much more robust and flexible manner.

class DosPrompt extends Object
{

public static pair[ KeyEvent ] getKeyEventPair( int t )
{ /* … */ }

private static milieu getInitialStateMilieu( )
{
let
{
pair[ String ] strp = class_method{ [ String ,
initial_milueu ].new() };
milieu initm = member{
[ DosPrompt , strp.milieu ].StateString
:= strp.cobj };
}
with initm fi
}

private static milieu handleNormalBackspace( )
{
let
{
String prev_str = class_method{ [ DosPrompt ,
thismilieu ].getStateString( ) };
int len = method{ [ str , thismilieu ]
.length( ) };
Pair[ String ] new_str = method{ [ prev_str ,
thismilieu ].substring( len - 2 ) };
milieu outm = member{
[ DosPrompt , new_str.milieu ]
.StateString :=
new_str.cobj };
}
with outm fi
}

private static milieu handleBackspace( )
{
let
{
String str = class_method{ [ DosPrompt ,
thismilieu ].getStateString( ) };
int len = method{ [ str , thismilieu ]
.length( ) };
milieu outm = if len > 0 then
(
class_method{ [ DosPrompt ,
thismilieu ]
.handleNormalBackspace( ) };
)
else thismilieu fi;
}
with outm fi
}

private static milieu handleRegularChar( char InChar )
{
let
{
String prev_str = class_method{ [ DosPrompt ,
thismilieu ].getStateString( ) };
Pair[ String ] new_str = method{ [ prev_str ,
thismilieu ].concat( InChar ) };
milieu outm = member{ [ DosPrompt ,
new_str.milieu ].StateString :=
new_str.cobj };
}
with outm fi
}

private static milieu getModifiedStateMilieu( int t )
{
let
{
milieu prev_e = class_method{ [ DosPrompt ,
thismilieu ].getSysStateMilieu(
t – 1 ) };
pair[ KeyEvent ] prev_k = class_method{
[ DosPrompt , prev_e ]
.getKeyEventPair( t ) };
milieu prev = prev_k.milieu;
char InChar = method{ prev_k.getKeyChar() };
milieu outm = if InChar == KeyEvent.BACKSPACE then
(
class_method{ [ DosPrompt , prev ]
.handleBackspace() }
)
else
(
class_method{ [ DosPrompt , prev ]
.handleRegularChar( InChar ) }
) fi
}
with outm fi
}

public static milieu getSysStateMilieu( int t )
{
if t == 0 then
(
class_method{ [ DosPrompt , thismilieu ]
.getInitialStateMilieu() }
)
else
(
class_method{ [ DosPrompt , thismilieu ]
.getModifiedStateMilieu() }
) fi
}

public static String getStateString( )
{ StateString }

private static String StateString;
}

The DosPrompt class definition above makes use of two external classes, String and KeyEvent. String is the string class that the program uses to represent the state of the prompt. KeyEvent is a class whose instances represent keypress events from the keyboard, and is an implementation of command from the time stream example earlier in the paper. Similarly, getSysStateMilieu represents an implementation of getState from the time stream example, and getKeyEventPair represents an implementation of getCommand from the time stream example. Instead of a single character or integer, the getSysStateMilieu method returns a milieu that can potentially contain an arbitrarily complex set of objects, and can be accessed in arbitrarily complex ways by whatever interface code is dynamically linked to the class. For instance, the string instance StateString, that defines the state of the prompt for a particular milieu returned by the getSysStateMilieu method, can be retrieved by calling the static method getStateString with the milieu returned by getSysStateMilieu for a particular “t”. Once the string is retrieved, its length can be determined by calling the length instance method on the string in the same milieu. In this way, the single getSysStateMilieu method replaces two interrelated recursive methods, getLength and getStringChar, from the earlier example. A single recursive method returning a milieu can in a sense be equivalent to an arbitrary number of interrelated recursive methods returning primitive types in a similar fashion. Incidently, getSysStateMilieu is coded so as to be called with the initial_milieu milieu, regardless of the value of “t”.

The getKeyEventPair method shows one way in which instances of event classes can be used in EphrataX. This method, which is assumed to be dynamically linked to an external event-handling API, takes the curried milieu thismilieu and creates a new milieu that is identical to thismilieu except that it contains a new event object representing the input character for the time “t”. It then returns the pair [ X , Y ], where X is the new event object and Y is the new milieu that contains X. Arbitrarily complex event types can be handled by this kind of arrangement. The author believes that it is important to integrate event objects into the same milieux as the system of objects that holds the state that the events are affecting. This allows objects associated with the system state to hold references to various event objects, much as they do in C++ and Java programs now.

Potential Applications

One may wonder is EphrataX isn’t a great solution in search of a problem. On the contrary, there are a number of problems for which EphrataX could greatly aid the tasks of design and implementation. A few examples are given here.

Error Handling in Complex Systems

A subsystem may make one or more modifications to its data before an error is discovered. These modifications then have to somehow be removed so that the system can return to a consistent state. In procedural languages, it is often difficult to design an algorithm that can properly affect this reversal in state. Often the resulting implementation has a number of special cases that must be very extensively tested. Some languages attempt to use exception handling to deal with erroneous cases by providing a way for an error to interrupt program execution in a controlled fashion. However the state may have already been changed by the time the error is found, and exception handling provides no built-in mechanism for reversing these changes. This kind of state recovery can be handled in EphrataX by combining the use of milieux with a layered design technique. An example of this is shown below:

class RequestHandler
{

public pair[ boolean ] handleRequest( RequestClass e )

/* Handles a user request. If the request produces an error,
returns true and leaves the system in its original state.
Otherwise adds the request to the data state and returns
false. */

{
let
{
milieu ths = thismilieu;
pair[ boolean ] res = handleRequestImpl( e );
milieu output = if res.cobj then ths
else res.milieu fi;
}
with [ res.cobj , output ] fi
}

protected pair[ boolean ] handleRequestImpl( RequestClass e )
{
/* Actual implementation here, returns true if there
is an error. This part does not have to worry
about returning error conditions to the original
state. */
}

}

The design of this class has two conceptual layers. The outer public interface layer is represented by the method handleRequest, while the inner implementation layer is represented by the method handleRequestImpl. The outer layer is responsible for calling the inner layer, and then returning the data to a consistent state if an error is found. As one can see, this can be done very simply in EphrataX. As long as the inner layer correctly detects the errors, the outer layer will always be able to recover the data to the previous consistent state. This is true regardless of how complex the implementation of handleRequestImpl is, or the extent to which it made modifications to its data before the error was detected. As the design of the system for which error handling is required becomes more and more complex, the use of a language like EphrataX for the implementation becomes increasingly advantageous.

This has been used in Verdantium. For instance, that a Verdantium script execution fails halfway through there is some milieu rollback that is performed by the UndoManager. I want to do more with this in the future.

Undo

Unless a program is simple enough that every action requested of it has a straightforward generic inverse action, undo can be difficult to implement using procedural languages. The requirements of many complex interactive programs require both OO programming to simplify the actions and some mechanism so that those objects reverse state when the user selects the “Undo” option from a pull-down menu. A program as part of the implementation of its action may create several objects, remove all references to some others, add or remove objects from data structures, and/or create or delete other arbitrarily relationships between objects. Functional programming could greatly reduce the amount of time and effort required to design code that would reverse these actions. Similar to the error handling mechanism described previously, EphrataX could be used to store the milieu containing the object state prior to the user’s last operation in some structure. When the user hits “Undo”, the current milieu is replaced by the stored milieu, changing the program state back to its previous condition.

This is now being used by several Verdantium components.

Scripting

Another potential application is the implementation of “scripts” or “macros”, where a macro is a series of actions recorded by the user for use at a future time. When a macro is used, the program essentially handles an action that contains an ordered list of more primitive actions (that were recorded earlier). The ability to perform recursion on objects greatly simplifies the task of scripting. The program simply breaks the complex action into a series of simpler actions that are sequentially fed into the system. For systems that require both undo and macro support, the advantages are even greater. Because a milieu functions correctly irrespective of how complex a set of operations were used to create it, performing an undo operation on a script is no more difficult than performing the same undo on any other action. Sophisticated scripting systems do not require equally sophisticated undo mechanisms just to reverse whatever changes they made to the object state (as they do in many procedural languages).

As it turns out scripting and undo have to work very closely together in systems that support both. The paper on Temporal Undo from Xerox PARC speaks to this topic. It gets relatively complex for a lot of systems when a scripted event, consisting of several events, has to be rolled back. This is one place where JUndo works quite well.

Use of Formal Specifications

One technique that has been researched in Software Engineering is the formal specification of software. This involves defining the algorithm that a program uses in terms of a set of axioms, and then attempting to produce an implementation that closely conforms to those axioms. Because EphrataX is a completely functional language, it may be very useful for implementing axioms specified in a functional notation. EphrataX also provides the ability for the designer to axiomatically specify the operation of an interactive program. This is because the commands that are entered interactively can be specified in terms of a time stream. That is to say, the first command is the command at time 1, the second command is the command at time 2, etc. This can greatly simplify the development of certain kinds of interactive programs.

Re-entrant Programming

In imperative languages, many procedures temporarily leave some data in an inconsistent state until the procedure finishes executing. As a result, if the procedure were called recursively the nested call might return a incorrect or incomplete result. The term “re-entrant” is used to refer to a procedure that always returns the proper result from such a recursive call. When a procedure might return improper data from a recursive call, it is thus not re-entrant. In EphrataX, recursive calls can be made to give correct results even in algorithms that have not been implemented in a re-entrant fashion. The recursive call can be made using the milieu corresponding to the last consistent state of the algorithm. Using such a previous milieu guarantees that the algorithm will not miscalculate data due to an inconsistency of state.

Merging of Data Models

Because EphrataX merges the object-oriented and functional data models in a relatively seamless fashion, concepts from the language are potentially applicable in a variety of cases where two very different data models need to be merged into a single system. For instance, one area of active research in the database field concerns techniques for merging object-oriented and deductive databases. That is to say, there are some databases systems that are based on object-oriented data abstractions, and there are other databases that are based on concepts inspired by the Prolog language, including the ability to deduce facts from other facts. Merging declarative and procedural models into a single system can be problematic. The fact that EphrataX’s data model is both object-oriented and functional may make this task easier. Where a deductive system uses a relation, an functional system uses a function, which in terms of mathematics is just a special kind of relation. Also, the fact that EphrataX uses a completely declarative style of programming should make EphrataX programs more compatible with database query optimization algorithms than other languages (e.g. C++ [5]).

Updates to the state of a particular element of data are also much easier to represent in EphrataX than in certain other declarative languages (e.g. Datalog). EphrataX can either represent updates as declarative changes defined over a time stream, or can declare them in terms of “actions” that map one milieu into another. Interactive systems based on the time stream concept, such as Faustini’s Visual Java [3] project, have already demonstrated how functional programming can be used to represent updates to GUI programs in a declarative fashion.

Databases are not the only systems where complex data management issues arise. Many applications that do not engage in either persistent storage or transactions must nonetheless manipulate and access large sets of data. The more flexible data model in EphrataX makes it possible to design these applications without having to create entire subsystems devoted just to data management.

Implementation

At this time, many of the implementation details for this language are still being worked out. One important design consideration is the determination of the mechanism to use for evaluating recursive functions. For instance, consider the functions below for finding whether a Person object is the supervisor of another Person:

abstract class SupervisorFinder
{
public abstract boolean isImmediateSupervisor( Person A ,
Person B );

public abstract int getNumEmployees( );

public abstract Person getEmployeeByNumber( int num );

protected boolean isSupervisorImpl( Person A , Person B ,
int num )
{
let
{
boolean result_1 = if num < 1
then isImmediateSupervisor( A , B )
else let
{
person X = getEmployeeByNumber(
num );
boolean ba = isSupervisorImpl(
A , X , num - 1 );
boolean bb = isSupervisorImpl(
X , B , num - 1 );
boolean result_2 = ba && bb;
}
with result_2 fi
}
with result_1 fi

}

public boolean isSupervisor( Person A , Person B )
{
isSupervisorImpl( A , B , getNumEmployees() );
}

}

How can this be compiled into an efficient implementation? One approach is to attempt to convert the recursive methods into iterative methods performing the same function. This might be accomplished by having the computation performed in a bottom-up rather than a top-down manner. More research will need to be done in order to work out the details of this.

I am less concerned about bottom-up eval. now than I was when I wrote that. I simply don't have many classes that track such recursive relationships, and hence I don't have any recursion performance issues to worry about at present.

Implementation of Milieux and Caching

One potential criticism that some might have of EphrataX is that the creation of milieux from other complex milieux might require a lot of complex copying of data, leading to redundant data and poor performance. However, this is only true if each milieu contains a copy of all objects. Instead, a milieu can also be defined only in terms of the differences between itself and some other milieu. For instance, creating a new milieu that is an alteration of a previous milieu can be set up in such a way that the previous milieu is defined in terms of the differences between it and the more recent milieu. The previous milieu would both be compact and accessible, while direct access would be available to all objects in the latest milieu. In other cases, recalculation can be used instead of caching. If all the base information on which the program computed is still in memory, then any computation performed by the program can potentially be repeated. This saves a large amount of memory at the expense of computational time.

It may also be desirable to introduce language constructs that give the programmer more direct control over which methods have their results cached. In many programs written in procedural languages, programmers already cache the results of calculations in order to optimize the computational time the programs require. The only difference is they do it manually in terms of storing redundant data in programmer-defined structures. In effect, they cache implicitly instead of explicitly. This creates a number of problems in procedural designs because updating a particular abstract datum in the design requires updating multiple redundant pieces of data in the implementation. In cases where all the data items do not get updated in a manner consistent with each other, bugs eventually result from the inconsistent program states. It might make a lot of sense to try to replace the current implicit procedural caching with explicit functional caching. That is to say, auxiliary structures would not be as necessary to store the values returned by some methods because those values would always be cached by the runtime itself.

Garbage Collection

An EphrataX system may need to engage in two different kinds of garbage collection. First, there is the garbage collection of milieux in the global heap of the EphrataX runtime. Second, there is the possibility that an object in a milieu can be garbage collected because the EphrataX program is no longer using it. As an example of the garbage collection of milieux, consider the following expression:

let
{
milieu p1 = member{ [ x , thismilieu ].val1 := 10 };
milieu p2 = member{ [ x , p1 ].val2 := 15 };
}
with p2 fi

The milieu p1 may be created in the process of evaluating the expression for p2, but once p2 is needed, there may no longer be a need to have a direct reference to the value of p1. The program may have gotten to a point where the above let block is never evaluated again, and thus it will be impossible for any expression to directly access p1. At this point, the milieu p1 can be garbage collected by the system. The milieu p2 could then be defined in terms of thismilieu, rather than the milieu p1. The mechanism for doing this is probably beyond the scope of this paper. Nevertheless, it is possible to reduce a system to only those milieux that are being used at a particular time.

Garbage collection of programmer-defined objects in EphrataX is different from garbage collection in other programming languages. A reference to an OID may exist in a number of different milieux. An OID from a milieu may be combined with an OID from any other milieu to produce a pair that can be used to attempt to reference the value of that object (the runtime has the responsibility of making sure that a particular object is actually in a particular milieu before attempting to access it). This means that if a reference to an OID exists in any milieu, then “copies” of the object in all milieux must be immune from garbage collection. Otherwise, a EphrataX program would not be guaranteed to have access to the “past” or “future” state of an object. At first this may seem to require a prohibitive amount of memory compared to a procedural language, which can garbage collect an object in a particular snapshot of the heap if there are no references to the object in that snapshot. However, if one uses a smarter implementation of the concept of a milieu, this is not the case. A milieu does not need to contain copies of all objects, only the differences between itself and another milieu. For an object that is no longer in use, there is nothing to garbage collect from such a milieu because there are no changes being made to that particular object. In many cases, such a milieu implementation can store sets of related object values in a space-efficient manner without ever garbage collecting. Once an object stops changing, those changes simply never take up any space in a subsequent milieu.

This has a number of potential implications for the performance of languages that use both garbage collection and some mechanism where multiple “copies” of a heap are kept in memory. Because garbage collection may not be employed, the time overhead required for garbage collection may not be necessary. This is at the expense of storing information about the previous changes to all objects. However, if the milieux that contain certain object states become garbage collected then some references to OIDs can disappear because the milieux containing those references no longer exist. So the garbage collection of a milieu can potentially create a condition where the garbage collection of an object can take place because there no longer exists a milieu containing the OID of the object in question. As a result the garbage collection of milieux can result in increased computational overhead to garbage collect objects, but at the benefit of reducing the amount of storage space required by the program.

Future Research and Concluding Remarks

Solutions have been presented for how a functional language can be used to investigate several software design problems in a cleaner way than is possible in procedural languages. Further a language, EphrataX, has been described which has been designed for these types of problems. A number of possible future research directions exist. One question that comes to mind is “what should be the equivalent of CORBA for systems that use an functional object model similar to that in EphrataX?” Current object standards are not expressive enough to fully support the use of objects in the context of functional programming. New procedures would need to be developed in order to guarantee interoperability between functional object systems.

There are also a number of possible improvements to the language itself. EphrataX needs a more complete set of primitive data types, as well as additional complex types such as arrays. The problem of making objects persistent needs to be researched, as do the issues of improving performance, and providing suitable interfaces to the outside world. By “outside world”, the author is referring to a number of external systems. A GUI is one prominent example of such a system, but so is something such as an interface to a serial port, or an external piece of procedural software.

Nevertheless, it is believed that EphrataX provides exciting possibilities for future growth. The author plans to present future developments of the language in a subsequent paper.

References

1. W. W. Wadge, and E. A. Ashcroft, Lucid, the Dataflow Programming Language, Academic Press, New York, NY, 1985.

2. P. J. Landin, ‘The Next 700 Programming Languages’ CACM, 9, 157-166 (1966).

3. T. Faustini, Visual Java, Computer Software, (unpublished).

4. K. Arnold, and J. Gosling, The Java Programming Language, Addison-Wesley, Menlo Park, CA, 1996.

5. B. Stroustrup, and M. A. Ellis, The Annotated C++ Reference Manual, Addison-Wesley, Menlo Park, CA, 1990.

New Umeta Update-- 071021 (Undoable Threaded Binary Trees)

2007-10-21T15:59:00.000-07:00

I finished more code for undoable threaded binary trees. Hopefully, I'm getting close to wrapping this up. It seems like I've been working on nothing but trees for a while now. At the same time, the code does show how general a language JUndo is becoming (assuming anybody is reading it).

Microsoft .NET AJAX ad is Blocking Downloads for JUndo Runtime

2007-10-14T11:11:00.000-07:00

I just tried to move a file across using the JUndo Runtime download, and there is an advertisement for Microsoft .NET AJAX on the the download page that is blocking access to the direct download link (it is visually extending outside its bounds and covering the link). Meanwhile the automatic download refuses to proceed. Thus, the Microsoft ad is effectively preventing the JUndo Runtime from being downloaded on Sourceforge. The workaround is to view source on the page, and then use the link tag in the source to manually build the HTTP location for direct download. Thank you, Microsoft.

Update: It's clearly visible when I use the Safari browser. The link for "direct" downloads is on the left of the Sourceforge download page for JUndo Runtime, and the Microsoft ad is on the far right of the page. The ad extends its region all the way to the left (while remaining visually transparent) so that when you click on the direct download link the click activation is taken by the Microsoft ad. Hence, one's mouse click is usurped by the Microsoft ad, and never goes to activate the link. Clicking the area of the link clearly highlights the ad instead.

New Umeta Update-- 071014 (Undoable Threaded Binary Trees)

2007-10-14T10:09:00.000-07:00

I put a new Umeta update on Sourceforge for undoable threaded binary trees. I'm trying to get the threaded trees finished as fast as possible so I can start using them in some practical applications. More later.

Binary Tree Traversals in Umeta

2007-10-12T21:13:00.000-07:00

I just finished a draft version of the traversal code for the LowLevelBinTree class in the Umeta Sourceforge package of the Jundo Runtime, although I may revise it later.

One change I made in Umeta is that the Callback class from Meta isn't in Umeta and never will be. Umeta uses a different (Jundo-specific) design pattern for traversals. Here is the reasoning. In typical procedural code, a routine traverses a data structure such as a tree, and performs a "visit" on each traversed node. Hence, the logical thing to do is to provide a callback for each visit.

Hence, the typical Java code for using the traversal would be as follows:

Callback x = [Your callback here];
myDataStructure.someTraversal( x );

with the presumption that x would be called on each visit. JUndo provides a select expression syntax that doesn't exist in Java. In JUndo, it makes more sense to take advantage of the selection functionality rather than use a callback. The JUndo equivalent would be as follows (in a seq block):

IteratorFactory fac = myDataStructure.someTraversal();
IteratorFactory fac2 = select [Your callback here] from a : fac where true fi;
Iterator itf = ( fac2.iterator() ).cobj;
IteratorUtils.getLastItem( itf );

The advantage is that more possibilities are available. For instance, the select expression can be changed to:

IteratorFactory fac2 = select [Your callback here] from a : fac where [your condition here] fi;

One can apply arbitrary filters to the traversal, and this provides the ability to traverse a subset of a structure's elements. It's also possible to quantify over more than one IteratorFactory. For instance, one could perform a join between two different traversals. Imagine having a callback that gets invoked when items from two different structures match respective conditions as follows:

IteratorFactory fac2 = select [Your callback here] from a : faca , b : facb where [your condition here] fi;

Your callback and condition code gets access to both "a" and "b" in the select! This has a potentially limitless set of creative uses.

Sun Promotes JavaFX's Declarative Semantics

2007-10-11T17:49:00.000-07:00

About a year ago at the last Pikes Peak Java Developer Group (PPJDG) meeting, several people responded as if I was crazy when I spoke about the advantages of declarative languages in relation to JUndo (JUndo has been a declarative language from the beginning). Now more people seem to be getting on the declarative language bandwagon, including Sun Microsystems. John O'Connor has an article on Sun's web site about the declarative nature of the new JavaFX scripting language:

http://java.sun.com/developer/technicalArticles/scripting/javafx/lc/part2/

The similarities and differences between JUndo and JavaFX are interesting. JavaFX provides a declarative user interface to a web application, which presumably has either a server-side file store or a server-side RDBMS as its data model. So one could think of it as a declarative user interface for a mostly imperative data model. JUndo provides a declarative data model that is then wrapped with a imperative Swing interface as part of a Verdantium component. That is to say, the two technologies are opposites in this sense.

JavaFX is a potentially important language, and one that will probably influence other declarative languages in the future. Will GUI code becomes declarative in the future? Perhaps. Only time will tell.

Started Adding Binary Tree Code to Umeta package of JUndo Runtime

2007-10-11T17:21:00.000-07:00

I've found threaded binary trees to be a useful data structure on several occasions. That is one of the reasons why they exist in the Meta project. However, I have realized that there is a need for a binary tree that is undoable. That is to say, modifications to the tree can be reversed upon user request. To facilitate this, I have started adding undoable binary tree classes to the Umeta package of the JUndo Runtime Sourceforge project. The code is still in an incomplete state, and it will take some time to get the (non-undoable) Java fully converted to (undoable) JUndo. Once the tree classes are complete, I plan to use them in some Verdantium demo code.

One thing to notice is that the erasure patterns in methods pruneLeft() and eraseAll() differ from those in LowLevelBinTree in the Meta project. In the Java Meta code, pointers had to be assigned so that the identity of the next node would be picked up before the node was disconnected (disconnection deletes this information from the node by setting the node references to null). This creates some code that is tricky and hard to follow. It uses the temporary pointers in some rather complex ways. In addition, the technique for using the temporary pointers varies depending on the data structure. For instance, lists and trees require different temporary pointer techniques.

The new JUndo code for LowLevelBinTree uses a completely different paradigm in pruneLeft() and eraseAll(). The JUndo code traverses the structure in one time stream and disconnects the nodes in a different time stream. In the traversal time stream, the nodes aren't disconnected and hence there is no reason to build temporary traversal pointers such as delTemp. However, the nodes still get disconnected in the other time stream. The disconnection time stream's final milieu is the one that gets returned by the erasure method. This pattern for using multiple time streams makes deletions simpler and more consistent across data structures.

Added SimpleForm component to Verdantium Downloads

2007-09-24T20:45:00.000-07:00

Like SimpleSax from my previous post, SimpleForm is another simple demo component. A lot of GUIs display forms with text fields and pull-down menus. A good example is a GUI that asks for name, address, phone number, social security number, etc. For a GUI like this it is very useful to separate then Model and Controller from the View in a Model-View-Controller (MVC) architecture. This component provides a simplified example of how such a separation can be implemented. In this component the view, i.e. the topPane panel in class SimpleForm, is separate from the model, the SimpleForm instance, that actually controls the behavior and the persistence. Unlike Java Beans where the component extends a GUI, a Verdantium component like SimpleForm has a GUI through aggregation. I think this is a much cleaner architecture. It makes more sense to build topPane from an external model/controller than it does to effectively "extend" topPane.

Another problem with JavaBeans is that making the bean "extend" topPane and implement Serializable tends to create a class that serializes the details of its GUI (i.e. all the text fields, labels, etc.). Verdantium intentionally puts the persistence methods in class VerdantiumComponent so that the component only serializes its data model.

Give this one a try by loading its ".xnl" file through the Discovery component.

Added SimpleSax component to Verdantium Downloads

2007-09-20T21:07:00.000-07:00

One of my goals with Verdantium is to provide a large number of demo conponents so that developers have lot of examples that show how to write different applications. I've observed that a lot of other Java-enabled frameworks, particularly Jini, were not adopted (at least in part) because there were few real examples for a developer to work from, and I wanted to make sure that Verdantium did not fall into a similar trap. Toward this end, I have added the Simple Sax component as a package of the Verdantium project on Sourceforge.

The typical Verdantium object persistence serializes Externalizable objects to XML, which is good enough for most applications. However, there are occasions when one wants to persist object data in a particular XML format or in a format using a particular XML schema. Simple Sax shows how to do this. The conponent writes its data as XML text, and then reads the data back using a SAX parser. This shows how to build customized persistence into a Verdantium component. It shouldn't be hard to retrofit this to use DOM, or some other XML parser.

Like the other demo components I have blogged about previously, the easiest way to load SimpleSax into Verdantium is to use the Discovery component. By the way, someday I need to modify the Verdantium-related online help files so that they refer to using Discovery instead of making modifications to the Verdantium apps.cfg file.

Sent feedback to JSR-296

2007-09-18T15:10:00.000-07:00

I sent a suggestion note to the JSR-296 people late yesterday. The archive of it is here:

https://appframework.dev.java.net/servlets/ReadMsg?list=users&msgNo=1015

I tried to keep the note very simple and concise. I could have written some very flowery sentences about compound documents, but I decided to not do that for a first E-Mail. The full text is here:

Content-Type: multipart/alternative; boundary=Apple-Mail-1--818406117
From: Thornton Green
Date: Mon, 17 Sep 2007 22:27:54 -0600
Subject: Suggestions for enhancing JSR-296

Hi,

To quote the appframework web page:

"So we're looking for feedback at this point. Constructive feedback
would be great; ranting and raving is OK too, particularly if it's
funny. We're not looking to adopt an existing framework or even for
code contributions however if there's an existing Swing application
framework you're fond of, then feedback of the form: "framework X has
a feature that JSR-296 lacks and the reason X is important is ...",
would be great."

And hence I hereby submit my suggestions. In my case, "framework X"
is Verdantium as described here:

http://verdantium.blogspot.com/

And with code posted here under GPL:

http://sourceforge.net/projects/verdantium/
http://sourceforge.net/projects/jundoruntime/
http://sourceforge.net/projects/meta/

This is an opening precis about features in Verdantium that do not
exist in JSR-296. The reason why these are important? If anybody
has questions about these items I can address them on a case-by-case
basis. Here is a partial list of features:

* Built-in Print / Print Preview / Page Setup Support

* Support for changing page size for printing (e.g. A4 versus Super-B)

* Built-in support for Printable interface

* Support for macro recording and playback

* Model-View-Controller separation of application from GUI (i.e. the
application isn't a frame).

* Better Multi-level undo. The Swing APIs implemented undo based on
the inverse-command pattern. Inverse commands are almost impossible
to write for a lot of applications. Undo really needs to be data-
driven to work across all application domains (similar to temporal
undo in JUndo).

* Visual embedding of one application within another to produce
compound documents. This allows applications to leverage each
other. I think this is very important, and it really takes advantage
of the strengths of the Java language and its ClassLoader APIs.

* Ability to embed applications directly in online help pages. This
simplifies the process of creating certain kinds of online help.

* Data oriented application loading. Framework looks at the file
being opened, and the selects the most appropriate application to
open the file.

* More support for reading and writing files in multiple formats,
including binary formats and XML.

* Better support for versioning of persistence formats.

* Larger set of lifecycle states. For instance, an embedded
application inside a container with multi-level undo can exist in
"hidden but not deleted" states that currently part of appframework.

* Support for running in MDI (e.g. JDesktopPane), as opposed to only
running in a JFrame.

* Remote loading of applications.

* More example programs. For instance, one of the applications in
Verdantium that could be used for example code is
verdantium.standard.DrawApp a drawing/container application that
support multi-level undo. I think it is important to provide several
examples of full application that provide support for container
embedding, multi-level undo, macro recording, printing, etc.

I'll stop here. I might think of more later. If you want to see
more detail, the source code for the complete framework is on
Sourceforge. I understand that you don't want to adopt a framework,
but perhaps we can find a way to cooperate.

-- Thorn

It's Time For Open Source-- Part 2

2007-09-17T19:06:00.000-07:00

A chinese student has recently sued Microsoft for using Windows Genuine Advantage (WGA) to infringe in his privacy. See the link below.

http://news.xinhuanet.com/english/2007-09/13/content_6718045.htm

This highlights a much bigger problem. Without the source code one simply doesn't know how much information a product (e.g. Microsoft Office) is collecting about its users and then sending back over the network to some other location like a corporate headquarters. The ability to collect information plus the ability to apply a reduced functionality mode (see my previous blogs) adds up to a lot of power.

Open source is not only THE choice for the protection of privacy, it is potentially the ONLY choice for the protection of privacy. Perhaps Verdantium, perhaps something else, but I think an open-source productivity suite makes a lot of sense today.

Finalization in the JUndo Runtime

2007-09-17T18:34:00.000-07:00

Sun has a new article on its website about Java finalization:

http://java.sun.com/developer/technicalArticles/javase/finalization/

The JUndo runtime uses finalization methods to reclaim memory, and hence finalization issues such as those described in the above article by Tony Printezis affect the design of the JUndo runtime. The article seems to assume that finalization is used in cases where a native resource needs to be managed from within the Java Virtual Machine. The JUndo runtime is using the same finalization techniques to address a different set of problems that do not include the managing of native memory.

To understand the JUndo finalization mechanism, one needs to grasp how JUndo addresses the problem of declarative memory management. In a typical intensional language, declarations are written recursively with an expression like the following:

x = 1 fby ( 2 * ( prev x ) )

Hence, x at time=0 is 1, x at time=1 is 2, x at time=2 is 4, etc. Assuming that no high-level optimizations are performed, each calculation of "x" at time 38 in the example above requires making 37 recursive calculations. This is an expensive process, so intensional languages often use cache memory. The result for "x" at time 38 is stored after the first time it is computed, and then the cached value is used for subsequent requests for "x" at time 38. This raises the question "what items need to remain in the cache, and what items can be removed at a later time?" That is to say, is there a time when a particular item in the cache expires?

JUndo addresses the cache expiration problem in the context of object-orientation. When objects are allocated, their milieu states are added to the cache. When an assignment operation operates on the member of a class, new milieu states are added to the cache. When a particular JUndo object ID is no longer reachable all milieu states related to that object ID can be removed from the cache. Milieux also get collected. The milieu is a primitive type in the JUndo language, but it maps to a JUndo runtime ExtMilieuRef in the generated object code that executes on top of the runtime. ExtMilieuRef instances are garbage-collected by the JVM when they are no longer reachable, i.e. when they are no longer being used by any piece of JUndo code. Milieu go out of scope and/or become unused, and hence it makes sense to get rid of the underlying objects at that point.

When an ExtMilieuRef is collected all milieu states related to that ExtMilieuRef (all object creations, object changes, etc.) can also be collected. This requires some amount of processing, and hence ExtMilieuRef uses Java's finalization APIs to setup that processing. Each definition of a milieu A in terms of a milieu B (e.g. through object creation) makes a B that is access-wise identical to A with the exception of a finite set of changes (e.g. B has an object that A doesn't due to the object creation). At the time B is created A already exists in the JUndo runtime cache in the form of an EntMilieuRef. Hence, the JUndo runtime often creates an EntMilieuRef for B that contains a set of changes (e.g. the object creation) in a table, and delegates the rest of the changes to A. Even more often, the JUndo runtime will structure the delegation so that A delegates to B (rather than the other way around). However, such reversal of the direction of delegation is beyond the scope of this blog post. The important thing to understand is that performing several operations in sequence causes a linked chain EntMilieuRef delegations to be constructed in memory. That is to say, E delegates to D which delegates to C which delegates to B which delegates to A, etc.

Consider the chain running from E to A in the previous paragraph. References can become unreachable in any other in a Java program, so suppose that C gets collected first. C can't just disappear because the delegation path from D to B would be broken. Instead it changes the delegation path so that D delegates directly to B. Moreover, some of the change information that was originally in C is migrated into D. For instance, suppose that an object was created in C and D expects to be using this new object. Just because C was collected doesn't mean the object is going away. It's still valid to use that object from D and E. Hence, information about the object creation has to find its way into D.

To free its memory properly, an EntMilieuRef must know about both its delegators and its delegates. As a result, the chains of EntMilieuRef instances have bidirectional references. An EntMilieuRef can't just be left to garbage collection for this reason-- it won't collect until the chains are broken. Even if it could be collected, one wouldn't want to collect it until the chain has been properly reformatted.

The basic procedure for solving this problem is as follows. Each ExtMilieuRef points to an associated EntMilieuRef. First, the ExtMilieuRef garbage collects. When the ExtMilieuRef collects its finalization method runs, and this finalization method executes a request that asks its associated EntMilieuRef to reformat itself for garbage collection. The reformatting has to be done carefully from a thread standpoint. The finalization method is called on one thread, while the milieu delegation chains are being accessed on another one. Synchronization was ruled out as being inefficient. Instead, it is observed that Verdantium typically runs on the Swing Event Dispatch Thread. At least for the time being, the thread issue is solved by having the reformatting invoked on the Swing Event Dispatch Thread. To use the JUndo Runtime with something other than Swing, one probably should change the threading of the invocation code that causes the EntMilieuRefs to be reformatted.

In summary, the JUndo runtime solves a series of sophisticated finalization problems in order to provide efficient memory organization. This contrasts with the idea that finalization is used to manage objects that reference blocks of native memory, and code for the JUndo runtime on Sourceforge represents the current solution. The reduction in the length of the delegation chains through garbage collection also reduces the number of delegations through which the runtime might need to perform a lookup. As a result, there is a significant performance benefit in addition to the efficient finalization of unused memory.

There is a lot of overlap between Verdantium and the proposed JSR-296 Specification

2007-09-14T16:11:00.000-07:00

Verdantium and JSR-296:

http://jcp.org/en/jsr/results?id=3801

are trying to solve similar problems. JSR-296 is trying to provide a framework for Swing applications running as standalone entities from a main() method. Verdantium provides a framework for application COMPONENTS-- classes that can run as standalone applications (they have a main() method) but are also flexible enough to be visually embedded inside other applications.

There is a lot that JSR-296 could learn from looking at the current Verdantium implementation on Sourceforge and/or this blog. The scope of Verdantium is in many ways larger than what JSR-296 is proposing. For instance, Verdantium has lifecycle states related to embedded components participating in multi-level undo that do not exist in the current proposal for JSR-296.

While there is still time, perhaps it would be in the best interest of the future of the Java platform if Verdantium and JSR-296 interacted and shared information in some useful way. I'm looking at joining the JCP, and hopefully people associated with JSR-296 might look at this post and/or my code on Sourceforge for ideas.

To be continued in a subsequent post...

Re-adopted opensourcecomponents Yahoo Group

2007-09-13T22:56:00.000-07:00

In the past I used to moderate an opensourcecomponents Yahoo group related to Verdantium and similar technologies. Later I got too busy to fuss with it, Yahoo seemed to be deteriorating in general, and the group only had about five members anyway.

I just happened to be visiting Yahoo recently, and to my great surprise I found that the site seemed to have gained its own momentum (30+ people have joined). Moreover, Yahoo seems to have improved. Or at least it seems to be better about accepting my password. I'm updating the original group profile, and integrating it with this blog. Hopefully, this will provide a place for people who are interested in this blog to interact.

Yes, people could interact by posting comments to this blog. And yes, I could use the discussion group features related to the Sourceforge projects for Verdantium, Meta, etc. Yahoo seems to be more popular, though. I will probably try to funnel discussion to either this blog or the Yahoo group. I don't think I could handle posts on multiple discussion groups hosted by multiple Sourceforge projects. That would require more time than I have. Besides, I want to use my time to write more code.

The discussion group is here:

http://tech.groups.yahoo.com/group/opensourcecomponents/

Sign yourself up! Things blogged here should cross-post to the Yahoo group.

Posts on blog should cross-post to opensource components.

2007-09-13T22:53:00.000-07:00

Posts on blog should cross-post to opensource components.

Microsoft Reduced Functionality Mode-- It's Time for Open Source Software

2007-09-12T10:17:00.000-07:00

Microsoft has recently announced that it has activated a "Reduced Functionality Mode" for Windows that allows it to defunctionalize particular copies of Microsoft Windows. It is also believed that Microsoft will extend their technology for "reduced functionality" to other products such as Microsoft Office (if they haven't done so already). According to the following news report:

http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=9035478

the reduced functionality includes reducing one's computer to a black screen after one hour of browsing, no start menu or task bar, and no desktop.

Certainly this is legal, conforms with Microsoft license agreements, etc. But who's to say that the functionality will only be reduced for legitimate purposes? Suppose Microsoft doesn't want people using Google. Who is to say Microsoft couldn't defunctionalize Windows for those people? Suppose Microsoft doesn't like your business. Who is to say Microsoft couldn't defunctionalize all of your copies of Windows? The only way to know for sure is to look at the source code, and Microsoft always jealously guards the source code so that nobody knows the extent to which functionality can be reduced. One could seek remedy using a civil suit against Microsoft, but the suit would drag on for years. Meanwhile, you have no working computers and no revenue. And of course the fact that you signed your life away by accepting Microsoft's license agreement will be raised in court. Your business will probably end its death spiral before the case is resolved (i.e. shades of Stac vs. Microsoft).

One of the advantages of open source projects over software such Microsoft Office is that in the open source world there isn't a large entity that can remotely defunctionalize your software. You can see the source code. Other people can see the source code. There are no surprises. I think the time for open-source productivity software has come. Perhaps Verdantium, perhaps something else. But definitely something that can't be defunctionalized on a whim.

Creating Non-Rectangular Visual Components in Verdantium

2007-09-10T20:51:00.000-07:00

Subclasses of java.awt.Component have rectangular bounds, but within those bounds a component can have a non-rectangular shape. Sun documented this capability but I am not aware of Sun releasing any demonstration classes that take advantage of it. Non-rectangularly shaped components fit perfectly into the Verdantium paradigm, so I do provide example code for this seldom-used feature of the JDK. See the NonRectangular package of the Verdantium download.

In the NonRectangular demo component, I chose a circular shape for the non-rectangular component because it was the simplest non-rectangular shape to implement (I try to keep things as simple as possible). However, any arbitrary shape is possible. A non-rectangular JComponent usually has three things:

* A transparent background.

* An overridden paint() method that draws the non-rectangular shape (and possibly an overridden update() method that calls the paint() method).

* Optionally, an overridden contains() method that returns whether the mouse position is inside the shape.

Because of the transparency of the background, the isOpaque() method of the JComponent should return false. For some JComponents, calling setOpaque() will work. For others, isOpaque() may need to be overridden to return false. Transparency essentially means that the JComponent element doesn't do an initial fillRect() on its extent before calling paint()-- there isn't much point to making something non-rectangular if the surrounding rectangular bounds get filled anyway.

The paint() method is where the non-rectangular shape is shown to the world. Java-2D provides general APIs for doing this.

The contains() method is a rather strange and interesting invention from Sun. In several other APIs that perform similar tasks (e.g. collision detection in Sun's own Java-3D), the geometry is passed to the framework and then the framework solves the inside/outside/collision relationships using a high-efficiency algorithm (e.g. binary space partitioning). Instead, AWT polls your JComponent every time the mouse is moved to determine if it is inside or outside the non-rectangular shape. If your shape contains complex geometry, then you get to write your own space partitioning framework in order to make inside/outside calculations efficient. What you need to do is the following: override contains() so that it returns true iff. the X-Y position in the parameters is inside your non-rectangular shape. If this is properly implemented, then AWT will send your JComponent mouse entry/exit events when the mouse enters and leaves your non-rectangular shape.

That covers it. The ability to display non-rectangular components has been a differentiator for component frameworks such as OpenDoc, so give this a try.

Extending Java Beans to support a Compound Document Model: Project Verdantium

2007-09-09T13:26:00.000-07:00

This is a paper that I wrote years ago for the OOPSLA conference as a representative of Arizona State University. It was rejected for publication mainly due to some of the comments it made about XML. My more recent comments/observations are in brackets: "[ text ]".

Extending Java Beans to support a Compound Document Model: Project Verdantium

Thornton Green
Arizona State University

ABSTRACT
Client-side visual Java Beans are poorly suited to the implementation of document-level software components such as text editors. This reduces the applicability of visually displayed Beans, limiting the client-side API primarily to a means for interchanging widgets between different integrated development environments (IDEs). By using an alternate API (Verdantium) for the embedding of beans in a visual context, clients-side code can implement a full compound document display model while leaving server-side APIs (Enterprise Java Beans) and the fundamental bean property model unchanged. Fully functional applications (i.e., word processors, illustration programs, equation editors, etc.) can be implemented as individual software components that can either run independently or be embedded in other applications using the same API. [Java Beans hasn't changed much since this was written; all of this is still true today]
Keywords
Component software, compound-documents, embedding, Java Beans.
1. INTRODUCTION
When Sun introduced the original container application for visually embedded Java Beans [5, 14, 16 18], the Bean Box, it included as sample components a couple of buttons, a molecule viewer, and some other components with a similar level of sophistication. Since then, little has changed. The APIs introduced by the Bean Box have been used as a way to build applications from simpler widgets in a development environment, but have not led to the widespread sharing of visual components between Java applications outside of the software development world. The term “widget” refers to a subclass of java.awt.Component (or its equivalent in another framework). This paper sometimes uses “widget” instead of “component” so that the term “component” can be used in the context of component software.

To understand the problem, one must first answer the question, “what is a Java Bean?” There are three different senses in which the term “Java Beans” tends to be used:

* As a programming standard for specifying “get” methods, “set” methods, property change events, etc [18]. The resulting components can be visually manipulated regardless of whether the have GUIs. For instance, a ComboBoxModel can be manipulated in Symantec Visual Café [22].

* As a server-side API for interacting with transaction environments and legacy code (Enterprise Java Beans) [16].

* As an API (on the client side) for subclasses of java.awt.Component to be read by the Bean Box (or similar program) from a jar file.

It is the latter of the three that creates problems for document embedding. Container applications that emulate the functionality of the BeanBox are difficult to write. Further, pure Java implementations of bean containers have inherent display problems. Many visual beans are “heavyweight” widgets, making it difficult for the pure Java container app. to superimpose a resize widget over the top of the bean.

Support for native or legacy file formats is lacking in the visual beans’ persistence standards. A class written for the Bean Box can serialize itself by implementing one of two interfaces, Serializable or Externalizable. Neither of which can support foreign file formats, unless they are object-based. This means that for example a text editor bean would need a second entirely separate persistence mechanism in order to load or save plain text files saved on the local disk. There is also no built-in mechanism for two beans to support the same persistence format. For instance, a PDF distiller bean can not serialize itself in such a way that the serialized format will be read by the free PDF reader bean when opened. Instead, the identity of the object’s class (in this case the PDF distiller bean) is “hard-coded” into the persistent data. When the file is loaded from persistent storage, the hard-coded class is used to read the object data. [Sun effectively deprecated Externalizable for XML object persistence, and uses a new system for XML. Nevertheless, the above is still true for non-XML formats.]

The way that beans are embedded into a container also presents a number of less fundamental problems that nevertheless present a series of practical difficulties. One of them is the use of subclassing of AWT components (i.e. widgets) to create beans. One of the original articles on the JDK 1.1 event model, [17], states “subclassing should be reserved for circumstances where [AWT] components are being extended in some functional or visual way.” Java Beans do not adhere to this principle. To make a bean that can be displayed in the Bean Box, the developer must subclass a widget regardless of whether she intends to extend the base widget in a functional or visual way. To quote this same page again, subclassing of AWT components “does not lend itself well to maintaining a clean separation between the application model and the GUI because application code must be integrated directly into the subclassed components at some level.” To be fair, the latter quote is referring more to using subclassing to handle events. However, it would also seem to apply to subclassing widgets in order to use them as visual beans. Any methods that talk to an interface implemented by the bean or to the bean’s “get/set” methods must necessarily go through the subclass of the widget, and can not be routed directly to the application code.

Because the APIs for visually displayed beans were created with the assumption that heavyweight widgets could be used, there is no unified API support for beans that are visually transparent. This makes it difficult for a text label bean to overlay (with a transparent background) the display content of a graphics bean with predictable results. Unfortunately, even the most basic presentation software requires this capability from its components. For instance, imagine how ugly a Microsoft Powerpoint presentation with a gradient-filled background would look if all the text labels had individual opaque rectangular backgrounds of a single color. As a practical matter, transparency support is necessary for getting useful results from visual components in a variety of situations.

Multi-page printing also presents a problem from a practical perspective. A Java Bean has one method, print(), with which to print itself into a graphics context. Unlike the APIs generally available to applications, the print() method does not support multi-page printing because it is a widget-level operation as opposed to a document-level operation. This gives the writer of the bean two choices: restrict the bean to something that only prints single pages, or implement a custom set of printing routines entirely separate from the Beans APIs.

The ability to read previous versions of the serialized state of a bean can be difficult to accomplish. The Serializable and Externalizable interfaces attach versioning information to the persistent state of a class based upon the bytecode information of the classes being serialized. If the bytecode of the class changes even slightly, older serialized files are no longer compatible. This can be remedied to an extent by defining the serialVersionUID field of each class. This will make the class able to read serialized information made by any other version of the class using the same serialVersionUID. However, this does not in itself solve the versioning problem. The class must still read a set of objects from a linear stream, attempt to ascertain which version of the software these objects refer to, and employ some type of filter to derive meaningful data from the object stream. Filtering data from a linear stream of objects can be difficult because in general there are no tags indicating what instance member name each object of the stream belongs to. As a result, it may be very difficult to derive the proper meaning from the object stream when two previous versions of the class had similar but not identical formats, and several instance members of the same class. [XML persistence using Serializable no longer seems to be using serialVersionUID.]

2. THE SOLUTION
Verdantium, a prototype API based on a set of software components the author developed to support his Ph. D. dissertation [10], extends client-side beans by implementing a compound-document model for visual components. The idea behind this model is to be able to construct complex documents by having a series of software components (beans) working together to represent the document’s various parts. For instance, a word processor and its equation editor can be separate beans that cooperate to allow the user to insert equations into a paper that she is editing. Instead of having very large monolithic applications as illustrated in Figure 1, a series of smaller beans cooperate to replicate the functionality typically seen in large applications. The construction of documents using components is more flexible because components for editing different parts of a document can be added and/or interchanged.

Figure 1 An example of modern software with all of its toolbars turned on. Taken from a screenshot of a 800 x 600 display. Note the amount of functionality that has been packaged in a single monolithic application.

Verdantium’s document model is implemented using the Model-View-Controller (MVC) philosophy. That is to say, the user interface for a certain kind of document is kept separate from its application logic [7]. Beans that are displayed in the Bean Box are subclasses of a view class, with no inherent support given to the underlying model. The VerdantiumComponent by contrast is a Java interface implemented by the model class, with the GUI stored in a separate object (though one may optionally integrate the two). The major design principles supporting the use of an interface are flexibility and pluggability as noted in [4]. Components based on interfaces are more flexible because they can extend any chosen base class, and they are pluggable in the sense that one implementation of an interface can be replaced by another that uses the same methods. One important aspect of the flexibility of using an interface is that the VerdantiumComponent does not need to subclass a widget. Instead, the user interface of the VerdantiumComponent is the Swing JComponent returned by the VerdantiumComponent’s getGUI() method.

package verdantium;

import javax.swing.*;
import java.awt.*;
import java.awt.datatransfer.*;

public interface VerdantiumComponent extends
EtherEventHandler
{
public JComponent getGUI();
public void handleDestroy();
public DataFlavor[]
getPersistentOutputDataFlavorsSupported( );
public void loadPersistentData( DataFlavor flavor ,
Transferable trans );
public Transferable savePersistentData(
DataFlavor flavor );
}

Figure 2 The definition of a VerdantiumComponent.

The defintion of a VerdantiumComponent is as given in Figure 2, where EtherEventHandler is a Verdantium-defined interface for handling scriptable events. The simplest Verdantium components do not need to handle any such events, and can simply provide a stub implementation of EtherEventHandler’s only method. In addition, a VerdantiumComponent capable of being used in a compound document must have a null constructor, and implement one required method not shown in the listing above. The method’s signature is as follows:

public static DataFlavor[]
getPersistentInputDataFlavorsSupported( )

This method is called at runtime using the Java Reflection API. By studying the interface definition above, one can see that every VerdantiumComponent must do three basic things. It must present a Swing GUI, it must be able to handle its own destruction, and it must be able to support a persistence architecture based on AWT’s Transferable and DataFlavor concepts. Different components implement the same interface, but provide different behaviors. In other words, the interface provides the basis for implementing a Strategy pattern with respect to multi-flavor persistence and GUI presentation [9].

The mandatory use of Swing widgets to implement Verdantium GUIs greatly simplifies the implementation of the overall framework. Heavyweight widgets make certain kinds of controls difficult to implement because the heavyweight widgets tend to display in front of any widget that does not have a peer [This has generally been true since JDK 1.1, but Sun announced during a session at JavaOne 2007 that they wanted to change this. For essentially all current JDK implementations this is still they way Java Z-Orders heavyweight instances of jaav.awt.Component]. Because Swing widgets are entirely lightweight, there are fewer problems to contend with when attempting to design controls that resize or translate the widgets. For example, Swing already provides JDesktopPane and JInternalFrame classes that implement Multiple-Document Interface (MDI) resize controls on other Swing widgets in a robust manner.

2.1 Persistence Support
To support persistent storage, a VerdantiumComponent reads and writes Transferable objects in multiple data flavors. The use of the Transferable object in the loading and storing of persistent states can be thought of as similar to the Memento pattern in [9]. The Transferable object is the Memento, the VerdantiumComponent is the originator, and the persistence system is the Caretaker. The main differences are that the VerdantiumComponent does not have to deal with a constraint solver in the same sense as the systems that served as the motivation for the Memento pattern, and that the VerdantiumComponent contains support for through data flavors for creating Transferable data in multiple formats.

The data flavors that a component can support fall into two general types. The first type is object data intended to be read from or written to a Java object stream. This allows the component to use the standard Java Beans persistence mechanism with Serializable objects. However, there is an important semantic difference between Verdantium’s object serialization and that in client-side beans. Client-side beans tend to serialize data from the widgets they inherit from, including the full view hierarchy. This has two problems. First, Swing widgets tend to store a very large amount of data to persistent storage. Much of this information is of little real use to the overall application. Second, Swing’s persistence format is still under revision as of Java 2. Verdantium components avoid these problems because they serialize the model, not the view. For instance a text editor component serializes the text of the document, not the details of the view hierarchy. There is a drawback in that the Verdantium component has to do more work to load a file than its bean counterpart. Sometimes a component written in Verdantium has to take a representation of a document and map it to an appropriate set of widgets and layout managers, or vice versa . However, the author feels that the benefits outweigh the drawbacks. [In recent versions of Verdantium the format for this has shifted from binary object streams (i.e. class ObjectOutputStream) to XML object streams. Newer versions of Verdantium also contain logic that map most implementations of Externalizable to XML. The author feels that Externalizable is much simpler, more elegant and more object-oriented than Sun's XML callback mechanism, and hence it makes sense to use the XML callback mechanism to bridge Externalizable into the XML format.]

The second general type of data flavor that Verdantium supports is raw data from a file stream. For instance, a text editor can read a standard plain text document as a set of bytes that have been loaded from an input stream. The Verdantium system has the responsibility of mapping the input file to an appropriate MIME type, and then sending this MIME type to the Verdantium component in the form of a DataFlavor object. The surrounding Verdantium system can determine if a component can read a particular file type by calling the getPersistentInputDataFlavorsSupported( ) method and then ascertaining whether the MIME type of the file is a match for one of the MIME types returned.

One drawback of this approach is that loading of persistent data fails if the Verdantium system maps a file to the wrong MIME type. This is similar to what happens in Microsoft Windows if a file extension is mapped to the wrong application. Some care must be taken to make sure that the mappings are complete and correct. Also, the particular mapping scheme that should be used seems to be highly platform-dependent. For instance Windows and Unix distinguish file types by using file extensions, while the Mac OS uses a special four-letter code stored separately from the file name [This has changed now that Mac OS X runs as a Unix variant]. How to unify the mapping schemes of all platforms under a single bytecode implementation is unclear at this time. The current version of the system runs on the Windows platform.

If a particular component is missing, Verdantium can query all other registered components and determine which component(s) can respond to an input file of a particular data flavor. To provide faster indexing, it also uses a series of hash tables to map data flavors to components, and to map file extensions to MIME types. This querying system provides an ability to interchange visual components that is not found in client-side Java Beans. One component can replace another if there is an appropriate mapping of MIME types. This gives developers greater flexibility in deploying components. Consider how Adobe Acrobat has been successful because Acrobat Reader, a free product, is able to read files of the same MIME type as the sold-for-profit Acrobat and Acrobat Distiller. Verdantium can replicate this kind of relationship more readily than client-side Java Beans.

2.2 Verdantium’s User Interface for Embedding
In order to provide appropriate support for embedded documents and take full advantage of JFC/Swing functionality, Verdantium uses a very different user interface than that exemplified by the Bean Box. One of basic problems in any compound document system is that of how the user interface distinguishes between the operations that can be performed on embedded documents. These operations fall into three basic types:

* Resizing the embedded document in the container.

* Translating the embedded document to different positions in the container.

* Editing the embedded document’s content (e.g. drawing onto an embedded paint program using the mouse).

Almost all embedding systems perform the resizing and translating of embedded documents by placing a border around the document that can be dragged with the mouse. Borders have some advantages. Large borders are easy for the user to find and drag with the mouse. They can also have distinct on-screen controls for translating as opposed to resizing. However, borders also have serious drawbacks. The display of borders moves the container document away from a WYSIWYG appearance. Borders also tend to obscure part of the document’s content. This can frustrate people attempting create complex documents because the display of borders while resizing can interfere with the user’s ability to determine whether the embedded component is the “right size” to fit neatly into its surrounding content.

Apple’s OpenDoc [1, 2, 8, 12] system uses two approaches to address this design problem: only place a border around the currently selected component, and use a really thin border. OpenDoc attempted to make resizing versus editing an embedded document as modeless as possible. That is to say, one doesn’t have to select a particular mode from a palette or a pull-down menu in order to switch from resizing to editing or vice versa. However, Apple the lack of modes also meant that there was no way to completely turn the border off. So to compensate for the fact that the selected component will always have a border (with the drawbacks that entails), OpenDoc displays a border that is about four pixels in width for translating the component. The drawbacks of this approach are that the border is very difficult for naïve users to select with the mouse, and is so small that even intermediate users who are not already familiar with OpenDoc would likely not recognize the border as a translation control.

Several container applications such as the BeanBox, Microsoft Office [13], and Symantec Visual Cafe [22] keep the concept that only the selected component has a border displayed for translating and resizing, but use a larger border with individual controls for different kinds of resize operations. The larger borders fix the selection and recognition problems, but make it more difficult to see a document in the context of the surrounding space. Also, the fact that one has to select an embedded component before resizing it creates inherent problems. Suppose the embedded component is a button. Does clicking on the button mean that a button-press event should be sent, or does it mean that the user wants to resize it? So many common components rely on single-click operations that using mouse-click selections to control the display of borders is not entirely practical outside of IDEs, which have separate “Design” and “Execute” modes that determine whether the embedded components respond to the mouse.

Verdantium takes a very different approach to the problem of how to distinguish resizing and translating from the editing of content. The Verdantium approach is based on the MDI window concept, which many users are already familiar with from their use of popular office applications. Translating a document equates to dragging the title bar of the MDI window, and resizing the document is performed by dragging the MDI’s resize control. The MDI control in the typical form found in other software is large enough that users can easily drag it and is familiar enough that users understand what to use it for, but it displays too large a border to work well in a variety of situations. To fix this problem, Verdantium requires that users accept a somewhat modal interface with the associated learning curve. The property editor palettes for the Verdantium container applications provide push-button controls for determining whether or not the MDI frames are displayed around the embedded components. The frames display differently depending on the mode of the pushbutton control (see Figures 3, 4, and 5). At the risk of sounding ridiculous, the author decided to use very simple names for each of the modes (such as “Move Mode”) to avoid names that throw too many long words at the naïve user (such as “Translate Mode”).

Figure 3 Simple components displayed in “Move Mode.”

Figure 4 Simple components displayed in “Resize Mode.”

Figure 5 Simple components displayed in “Edit Mode.”

Verdantium’s container app. MDI frames have one more important difference versus typical MDI implementations: Verdantium frames have transparent backgrounds (see Figure 6). This allows for Verdantium components to be used as semi-transparent overlays in a container application (thanks to Swing’s transparency support). There are a number of compound document scenarios where this is an extremely important capability. For example, the transparency support provides the means to lay text over graphics (see Figure 7). One drawback of this transparency implementation is that the Verdantium code tends to delve deeply into Swing’s Pluggable Look And Feel (PLAF) code in order to produce a subclass of JInternalFrame with the proper border and transparency characteristics. At least for the time being, this results in the container frame being hard-wired for a particular look-and-feel. The Java Look-And-Feel (JLF) is being used for the current implementation [this has since been extended to include Windows and Mac LAFs].

Figure 6 MDI container app. frames in Verdantium have transparent backgrounds, and take advantage of Swing’s transparency support. This allows the document creator to overlay non-rectangular shapes. A component can avoid the use of transparency by drawing an opaque background.

Figure 7 An example of why support for transparency is useful. In this illustration, a graphics component is displaying a curve, and an embedded text component that is rendering text over the top of the graphics. Note how the text is inside the curve, but the resize rectangle of the text component extends outside at the top corners.

2.3 Document-Level Printing Support
Unlike Java Beans, which only provides widget-level printing, Verdantium provides a document-level printing interface called BookPrintable. BookPrintable gives the component total control over the printing process from the time the user selects the “Print” command on the component to the time that the component decides the print operation has concluded. Verdantium also keeps the widget-level printing functionality from AWT / Java Beans. This means that there can be as many as two separate execution paths by which a Verdantium component may be printed (a document path and a widget path). The reason for this is that embedded components need to have a different printing protocol from the component that gets the original request. That is to say, there is a “master” component and there are “slave” components in the printing process, and the slaves (the ones embedded somewhere in the master’s document) do not get all of the privileges of the master. The master gets to select how many pages to print, and what will show up in each page at a document level. The slaves’ responsibility is to respond to calls to their GUIs’ print() method in a reasonable way. In most cases, the default implementations of the print() method supplied by AWT already work well enough to support the slave side of the relationship. The use of multiple paths of execution for printing allows a Verdantium component to properly support printing as either a stand-alone application or an embedded component.

2.4 Versioning
Support for persistent versioning is very important for applications software. Almost all applications have legacy file formats from previous versions of the software, and being able to interrogate these legacy formats in a useful manner helps to convince customers to spend money on regular upgrades. Versioning of serialized objects is also a tremendously difficult problem. Verdantium provides the ability for an Externalizable object to save itself in a more versionable way using an object-oriented version of a property list. The class’ implementation of the writeObject() method of the Externalizable interface creates this property list object, writes a series of objects to the property list with different property names, and then sends the property list down the stream to be serialized. The advantage of the property list is flexibility in dealing with versioning issues. For instance, an object reading persistent information from a property list can query the list to see if certain property names have objects associated with them. Also, different versions of a class can write data to different property names regardless of how or whether the schema of the class changed. The property list can then be interrogated on the read side to determine which set of property names is contained in the list. Another key advantage of the property list is that objects do not have to be read in the same order in which they are written. For instance the writeObject() may write the property for the number of items in a list after the list items because the list was read using an iterator. However, the readObject() method for the same class read the number of items first, and then loop through the property name of each list item using a simple for-next statement. The ability to arbitrarily order the reading of items from the property list greatly aides the ability to perform non-trivial versioning because the schema for the latest version of the class may not be well-suited to reading data in the order saved using previous versions of the class.

It may be useful in a future version of Verdantium to modify the existing property list system to serialize in terms of XML [20, 24]. XML would provide an ASCII representation of the object property files that could be analyzed using a standard text editor. This is a topic for future research. [This has been implemented in more recent versions. Serializing property lists to XML provides the best of both worlds. The file format is standard XML, but the object read/write system has the flexibility of object properties.]

2.5 Creating Actual Components
All of Verdantium’s capabilities would be useless if they made Verdantium components and Verdantium container applications impossible to write. In contrast to the complexity required to replicate the Bean Box, a great deal of work has been put into streamlining the number of lines of code required to construct simple Verdantium components. The Verdantium HelloWorld component currently requires 140 lines of code, including comments (not counting the optional class providing online help). The DemoContainerApp, an example class that demonstrates how to write a simple container application, currently requires 440 lines of code with comments (not counting code for an optional class devoted solely to providing online help).

3. Verdantium as a Document Model
Verdantium was created with the idea that a client-side component should be able to support all the functionality that a typical GUI application does so that the components can have wider applicability. The VerdantiumComponent revises and extends the Beans component model to support these features. Perhaps the most important of these extensions is the expanded support for persistence. Components in Verdantium can read and write files of any MIME type through a Transferable interface, or save and load Serialized objects to persistent storage. Assuming that the Verdantium system can map each file to an appropriate MIME flavor and load the raw data stream into a Transferable object, the component can support any number of file types simultaneously. Multiple components can share the same file type, allowing more flexibility in how they can be distributed. Finally, Verdantium makes it easier for Externalizable objects to be compatible with future versions of the software using alternate persistence formats.

Verdantium supports multi-page printing at the component level, allowing applications such as word processors and illustration programs to be written as components. The AWT widgets’ print() method is also supported for imaging embedded components to a particular rectangular region of the printed page. Some might argue that giving the component total control over multi-page printing makes it incompatible with use in a Java applet. However, multi-page printing can not be allowed in any form from an applet because an errant applet can request an arbitrarily large number of pages. Hence, the applet’s security manager simply would not allow a print request to be fully processed. Moreover, the browser can still perform widget-level printing of the applet through the standard interface. [This point is moot now that newer versions of IE have made it very difficult to write an HTML block that executes the Java Plug-In across all browsers (e.g. removing support for Netscape plugins). Applets are probably dead, and Verdantium is now really a framework for Java applications, and components pulled in from the network through the Verdantium Discovery system. Verdantium Discovery is probably a lot more reliable than using Applets anyway.]

Verdantium components can be used to build compound documents. Complete container applications can be written as Verdantium components in significantly less than 1000 lines of code, and structured using a robust MVC architecture. Because Verdantium code is based on Swing and the container functionality is based on JDesktopPane, the resulting GUIs are both stable and easy to use. Hopefully this will lead to a larger number of container implementations to be included with general-purpose applications such as illustration programs. Embedded components can fully utilize Swing’s support for transparency, allowing embedded components to act as transparent overlays.

One might argue that Verdantium is not compatible with many IDEs because of the techniques they use for building GUIs visually. The visual builders of many IDEs express GUI code in terms of the subclassing of java.awt.Container (or some subclass thereof), which is precisely what Verdantium was designed to avoid. In this case, there are two approaches that one might use. First, allow the model class and the view class to merge. That is to say, have the generated view class implement VerdantiumComponent. This isn’t a perfect solution, but it can work. The second is to express the entire GUI in terms of UI panes, and have each VerdantiumComponent create an instance of the appropriate IDE-generated UI pane class as a member and then return it using the getGUI() method. The disadvantage of this approach is that it may produce a series of independent pane classes where none may be necessary.

4. RELATED WORK
In many ways the environment that is architecturally the most similar to Verdantium is Apple’s now-defunct OpenDoc [1, 2, 8, 12] project. OpenDoc was a cross-platform compound-document model implemented using IBM’s System Object Model (SOM). OpenDoc components were typically written in a language such as C or C++ with a binding that allowed them to be compatible with SOM’s more sophisticated object model. The need to communicate with a separate object model through an API created extra work for the programmer and made components more difficult to write. Also, typical OpenDoc components on the Macintosh platform did not use a set of layout managers to automate GUI interactions as is often done with JFC/Swing or X-Motif widgets. For instance instead of using the equivalent of a JScrollPane to manage the GUI of a document, many OpenDoc components would have code to respond to each individual scroll bar action. This further contributed to the complexity of constructing workable OpenDoc implementations.

Among OpenDoc’s notable features were its cross-component scripting architecture, its support for embedded components, and its ability to have a component read and write files to arbitrary formats while still supporting embedding. One problem with OpenDoc was a lack of memory-protection to keep errant objects from overwriting each other. In particular, on the Mac platform there was no memory protection at all. On other platforms, components were protected from each other, but the objects that comprise a component could still compromise each other in that component’s memory space. Contrast this with the Java VM, where objects are not allowed to clobber each others’ memory. OpenDoc’s lack of memory protection meant that a single ill-behaved component could crash other components in a document, seriously affecting the robustness of the architecture. OpenDoc is no longer supported by its original vendors, and very little development of new OpenDoc components has been done in the past two years.

Java Beans [5, 14 16, 18], the standard component architecture for Java, is more robust than OpenDoc in the sense that the Java VM prevents ill-behaved objects from clobbering each other. Moreover, Java Beans are easier to write in many ways because the Beans object model is the same as that for the Java language. The use of Java layout managers automates many of the more complex tasks related to the GUI, allowing the developer to focus on those events that actually affect the domain logic of the component. The problems with client-side beans were discussed earlier in the paper. For the sake of brevity, they are not repeated here.

Object Linking and Embedding (OLE) is Microsoft’s environment for creating compound documents in the form of custom controls with a WYSIWYG appearance [11]. OLE uses Microsoft’s COM object model to provide an interface mechanism for components to communicate. Like OpenDoc’s SOM model, COM components are written in a language like C or C++ with wrappers that allow them to work in the COM model. OLE components also require a host application to support their display. Microsoft Office applications use OLE as a means to interoperate. ActiveX, a close cousin of OLE, provides an architecture for controls to be displayed on the web.

Aldus developed the Vamp environment as a compound-document implementation designed to streamline the development and maintenance of software components within the company, and to aid in the porting of code between the Macintosh and Windows platforms [6]. The architecture of Vamp was based on Model-View-Controller with the use of event-driven state machines to alter component states. Vamp allowed large programming teams at Aldus to be divided into smaller groups working on individual components. Reenskaug and Skaar [15] developed a documentation environment with a number of compound-document capabilities, and with the additional ability to collapse part of a document. Embedded components included class and method definitions. Netscape worked on a compound document extension to Java Beans two years ago [23]. However, little information has been released about this project.

Faustini’s Visual Java, an early ancestor of the Bean Box, provided a purely visual environment for building GUIs in a container application as mentioned in [21]. Not only were the GUIs visually built, but the algorithms tied to the GUI actions were also built from visual components. Visual Java used a data model based on the programming language Lucid expressed using an operator net concept. Each operator in the net was capable of running on independent threads of execution and could potentially operate in either a deterministic or nondeterministic fashion. The name “Visual Java” is now used for a different product. The closest environment to Faustini’s Visual Java today is Java Studio [19].

Improved persistence models for Java Beans have recently become a topic of much interest. One persistence standard seeing increasing use is XML [20, 24]. XML is an HTML-based language for representing object-oriented data [This sentence was one of the major reasons why the paper got rejected. Should I have written "HTML-like" instead of "HTML-based"? Should I have written "SGML-based" instead of "HTML-based"? Both HTML and XML owe their lineage to SGML. SGML is a meta-language that doesn't describe a particular format (i.e. how to define tags). HTML defines a format for part of SGML. XML also defines a format for part of SGML, and defines the tag format (e.g. use of angle brackets for tags) the same as HTML. As a result, XML loads directly into many browsers designed for HTML, but the browsers simply don't recognize the content of the tags. So XML was IMHO based on many tag format concepts from HTML, but the paper got rejected anyway.]. Objects are represented in XML by a set of tags that describe the states of each of the objects’ members. The XML format also provides a means to support versioning. A program can accomplish this by parsing the XML data to interrogate its format, and then converting the old format to match that required by the current software. One of the advantages of XML is that it is not dependent on a particular object model. XML data can be read and written by systems outside the Java architecture such as relational databases. Because XML is HTML-based, XML parsers can not read or write formats such as non-HTML plain text files or images. [As noted before, Verdantium now persists objects in XML].

XML can be used in a variety of applications. An example of XML’s flexibility is the Simple Object Access Protocol (SOAP) which uses XML as the basis of a wire format for remote method invocation using HTTP [3]. The Java implementation of SOAP has some architectural similarities to Verdantium in the sense that they both use Java interfaces as opposed to base classes to represent the fundamental object types of the system. The element types in SOAP are implemented using an interface hierarchy to provide the methods supported by each type of SOAP data. Instead of the properties list metaphor used by Verdantium, SOAP represents data as a linked collection of structured types: arrays, simple types, compound records, and object references. [It could be said that XML describes "nouns and verbs" but it doesn't describe any kind of "vocabulary". As a result, Verdantium has classes that scan the format of the XML file, and then determine which component should load it. In a sense, it answers the question, "which component speaks in this vocabulary?"]

5. ACKNOWLEDGMENTS
The author would like to thank all the people who made helpful suggestions about the architecutre: Dr. Edward Ashcroft, Dr. Timothy Lindquist, Dr. David O. Hestenes, Dr. David Halliday, Al Butkus, Pat Reany, and Dwain Desbien. I would also like to thank Dr. Tony Faustini, without whom I may never have discovered the Java language.
6. REFERENCES

[1] Apple Computer. Inside Macintosh OpenDoc Cookbook, Addison-Wesley, Menlo Park, CA (1996).
[2] Apple Computer. Inside Macintosh OpenDoc Programmer’s Guide, Addison-Wesley, Menlo Park, CA (1996).
[3] Chappell, D., “Simple Object Access Protocol (SOAP) and Firewalls,” Web Page, http://msdn.microsoft.com/xml/ general/soap_white_paper.asp
[4] Coad, P., and P. Mayfield, Java Design, Printice Hall, Upper Saddle River, NJ (1999).
[5] Feghhi, J. Web Developer's Guide to Java Beans, Coriolis Group Books, New York, NY (1997).
[6] Ferrel, P. J., and R. F. Meyer, “Vamp: The Aldus Application Framework,” Proc. ACM OOPSLA, 185-189 (October, 1989).
[7] Fowler, M., Refactoring, Addison-Wesley, Menlo Park, CA (1999).
[8] Fuller, J., and A. Meadow. Essential OpenDoc, Addison-Wesley, Menlo Park, CA (1996).
[9] Gamma, E., R. Helm, R. Johnson, and J. Vlissides, Design Patterns, Addison-Wesley, Menlo Park, CA (1995).
[10] Green, T., “Research Issues of Geometry-Based Visual Languages and Some Solutions,” Ph. D. Dissertation, Arizona State University, Tempe, AZ (1999).
[11] Li, S., and P. Economopoulos, Professional Visual C++ 5 ActiveX/COM Control Programming, Wrox Press, Chicago, IL (1997).
[12] MacBride, A., and J. Susser. Byte Guide to OpenDoc, McGraw-Hill, New York, NY (1996).
[13] Microsoft. “Microsoft Office”, Computer Software, Redmond, WA.
[14] Morrison, M. Presenting Java Beans, Sams, Indianapolis, IN (1997).
[15] Reenskaug, T., and A. L. Skaar, “An Environment for Literate Smalltalk Programming,” Proc. ACM OOPSLA, 337-345 (October, 1989).
[16] Sun Microsystems, “Enterprise JavaBeans Technology,” Web Page, http://java.sun.com/products/ejb/
[17] Sun Microsystems, “Java AWT: Delegation Event Model,” Web Page, http://java.sun.com/products/jdk/1.1/docs/guide/ awt/designspec/events.html
[18] Sun Microsystems, “Java Beans, Part 1,” Web Page, http://developer.java.sun.com/developer/onlineTraining/ Beans/Beans1/simple-definition.html
[19] Sun Microsystems, “Java Studio,” Web Page, http://developer.java.sun.com/developer/Books/ Graphics2/index.html
[20] Sun Microsystems, “Java Technology and XML,” Web Page, http://java.sun.com/xml/index.html
[21] Sun Microsystems, “Keynote Presentation,” Web Page, http://java.sun.com/javaone/javaone96/McNealy.html
[22] Symantec, “Visual Café,” Computer Software, Cupertino, CA.
[23] Vizard, M., “Pull over, Sun; Big Blue’s gonna drive,” InfoWorld, 19(8), 3-4 (Feb, 1997).
[24] W3C, “Extensible Markup Language (XML) 1.0,” Web Page, http://www.w3.org/TR/1998/REC-xml-19980210

New Verdantium Version -- 0906

2007-09-06T22:54:00.000-07:00

I did a lot of work over labor day, particularly on the JUndo Runtime. Here is what's in the latest version:

JUndo Runtime-- Fixed a series of issues in the runtime, particularly memory reclamation. Much of the original finalizzation code has been fixed, and turned back on. This is to say, the code that actually reclaims milieux after a garbage collection run has been turned on again. The JUndo Runtime actually gets faster after it has garbage-collected milieux, so this should provide large performance improvements for some operations. In addition, a number of C++-isms have been removed from the code.

I think this is a huge change in the grand scheme of things. It makes the undo system much more efficient, particularly for very large programs. This was one of the last serious bugs I have observed in the runtime, and fixing it brings the runtime much closer to moving to a pre-alpha or alpha state. It also gives people who read code an idea of how the runtime is supposed to manage memory when fully implemented. In most programs, the vast majority of milieux are garbage-collected, and hance only the remaining milieux should contribute to the performance of milieux lookups by the runtime. This goes a long way toward demonstrating how JUndo classes can be efficient.

Verdantium-- A series of new features has been added to the DrawApp drawing application such as the ability to erase individual rendering primitives. I focused on DrawApp operations that are relatively easy to do, but relatively difficult for non-temporal systems to undo. I think the new DrawApp code makes a very strong case for temporal undo, particularly with the new refinements to the JUndo Runtime described above.

Poseidon Sourceforge Package of Verdantium-- Poseidon shows how to create a small, useful component that can be embedded in other components (or run standalone), provide macro-scripting, support multi-level undo, be printable, display page setup and print preview windows, have a reasonable user interface (although without pretty icons), load/save files in a fairly compact XML format, provide illustrated online help, and fit within a .jar footprint of a little less than 100K. This will provide a template for third parties to add their own custom components to the Verdantium system. Different components can be compiled seperately from each other and then dynamically linked into the Verdantium system using Discovery. In terms of content, this component is a simple ripple-tank simulator for educational use in entry-level (e.g. high school) physics classes. It allows one to specify simple wave positions, frequencies, relative amplitudes, etc. and then see how the waves interfere. The underlying algorithm provides a very quick-and-dirty approximation of wave effects, and isn't guaranteed to be accurate in all circumstances (it chooses speed over accuracy). This release resolves symbols that changed due to the recent refactoring of Meta.

DocPrinter package added to Verdantium -- 0828 ; Printing

2007-08-28T20:13:00.000-07:00

This has been a busy week. I completed the century (100 mile) bicycle ride in the Tour De Cure in Longmont, Colorado on Sunday. It's a charity event to support Diabetes research. At the same time, I also got Tour De France winner Greg LeMond's autograph (yeah!). Coding this week has been delayed by all of the fun.

One of the visions that I've had for Verdantium is to make it a system for high-quality and resolution-independent printing. I've always wanted Verdantium to provide better printing APIs than those provided by Java Beans. The Java Beans framework primarily has the component (the bean) print on a single page by overriding the print() method of the java.awt.Component class. Java provides an AWT Printable interface with multi-page printing capability, but strangely Java Beans does nothing to detect or utilize a bean that implements the interface.

Verdantium provides direct support for a variety of printable components and printing scenarios. In the simplest case, a component may be embedded in the one doing the printing (e.g. a picture component in a word processing document). In this case, the typical print() method in java.awt.Component will be used.

If the component being printed is the top-level embedding component of the print job, then the following steps will be performed:

* First, Verdantium will determine if the callee implements the Verdantium BookPrintable interface. If this is the case, then BookPrintable will be used. BookPrintable is the most versatile interface, but is probably too heavyweight for most components.

* Second, if the component does not implement BookPrintable, Verdantium will determine if the callee implements the AWT Printable interface. If so, then Verdantium will work through the Printable methods, and potentially print on multiple pages. Most components that print on multiple pages will probably utilize this option.

* Third, if neither Printable nor BookPrintable are implemented by the callee, then Verdantium will use the print() method on the component's GUI.

For the typical multi-page component implementing Printable, Verdantium will automatically generate Print Preview windows, show Page Setup dialogs, work with the Swing RepaintManager, etc. Ditto for simple single-page components that don't implement Printable. BookPrintable is only useful of one wants to implements one's own PrintPreview GUI and/or one finds design issues having the Verdantium component directly implement Printable (i.e. sometimes it makes more sense for the Printable to be a separate class).

I think the support for Printable and BookPrintable makes Verdantium's printing significantly different from that in Java Beans, and creates possibilities for document automation (i.e. automated printing) that aren't possible in the Beans framework. To demonstrate this, I added a new component package called DocPrinter to the Verdantium project on Sourceforge. DocPrinter is a simple component that prints other components through a common interface. This includes components that print on multiple pages.

During the testing of DocPrinter I also noticed a series of Verdantium bugs that were created by some of the new multi-level undo improvements. Hence I posted a new Verdantium version, 0828, on Sourceforge that closes some issues that had to be fixed in order to make DocPrinter work with certain documents.

Like the EventViewer component posted earlier, DocPrinter is best used by first launching Verdantium ProgramDirector, and then loading DocPrinter's .xnl file through the Discovery component.

All of the Verdantium's printing frameworks use the Java Foundation Classes (JFC) Java-2D APIs. Java-2D uses resolution-independent coordinates, and should be able to take advantage of any high resolution (i.e. 300 DPI and above) printer. The specification for Java-2D was written by the same company (Adobe) that created PostScript, Display PostScript, and Adobe Illustrator. There are two issues to keep in mind with Java-2D. First, Java-2D can display characters with completely different font metrics depending on whether anti-aliased rendering is utilized. Second, Java-2D has been equivocal about the pixelation limits of its rendering.

Pixelation limits have dogged high-resolution rendering for decades-- long before Java existed. The original Mac used 16 bit pixel coordinates that extended from -32K to +32K. Different implementations of Win32 APIs have had different pixelation limits. If my recollection serves, Win95 had 16-bit pixel coordinates, whereas Win NT 4.0 had 32-bit coordinates. Different versions of Java-2D have had different coordinates sizes. On Windows, Sun JDK 1.2.2 and JDK 1.3 had coordinates that extended completely across the floating-point space. This later got truncated by Sun to smaller coordinates. Then Sun accepted a bug number to bring the larger coordinates back. If trying to make something work on multiple platforms and multiple JDK versions than one should probably assume truncated coordinates.

Nevertheless, Java-2D is a very sophisticated API and Verdantium takes full advantage of it. It should be possible to build some very powerful printing capabilities using Verdantium and Java-2D.

Added EventViewer package to Verdantium

2007-08-23T21:13:00.000-07:00

Posted EventViewer, a component that acts as a debugging tool for watching event traffic moving through the Verdantium system.

To use EventViewer, one probably wants to load it into an existing system through the Verdantium Discovery component. Discovery allows one to discover Verdantium components over the network in a manner similar to how network printers are discovered in most modern operating systems.

Unlike Sun's older Applet concept, discovered components don't have a security model. One needs to make sure to only discover components from trusted sources (probably from within one's own network). However, the lack of a security model is very advantageous. A discovered component has full access to the computer on which it is running, and this makes life a lot easier. Want to write to a file? Just select "Save." Want to print? Just select "Print." You get the idea.

The procedure for loading EventViewer through Discovery is as follows:

* Drop EventViewer.jar and EventViewer_14.xnl into the same directory.

* Launch the verdantium.ProgramDirector class from Verdantium.

* Click the "Run..." button, select the "New" tab from the resulting editor, select the "Discovery" component from the "New" tab list, and then click the "Apply" button.

* The Discovery component will launch in a separate window. Click the "Choose File" button, and then navigate and select the "EventViewer_14.xnl" file from the file chooser. The "Event Viewer" listing will then be added to the bottom of the list of components under the Program Director's "New" tab.

* Select the newly added "Event Viewer" item under the Program Director's "New" tab, and click the "Apply" button. The Event Viewer will be launched. Subsequent Program Director actions will be shown in the Event Viewer.

Using the URL option of the Discovery component, this same procedure works over HTTP. This makes it possible to dynamically load Verdantium components over the network. Try it.

New Verdantium Version -- 0822

2007-08-22T22:20:00.000-07:00

This version is closer to Sun's standard naming conventions for the Java programming language, e.g. constants in all-caps. A lot of the changes are focused on the Meta project. There's a reason why Meta hasn't followed typical Java conventions: Meta is older than the Java language. It originally existed in C++, and was ported to Java circa JDK 1.0. It has undergone several changes since then. Parts the original Meta were dropped because they were obviated by the Java instanceof operator, other parts were later dropped because they were obviated by Java Collections Framework (JCF), classes were later added to handle XML encoding/decoding, etc. I've also added more Java exception support.

Several parts of the original Meta still haven't been obviated by the Java language. For instance, the FlexString class is still very useful. FlexString was originally a response to severe performance issues encountered with strings in C and C++. Adding a character to the start of a large C or C++ string requires pushing the entire existing contents of the string one character to the right. With Java, string performance is even worse. Adding a character to any part of a Java string causes a completely new string to be allocated, which copies the entire original string. FlexString is modeled after the standard pattern in simple text editors-- multiple text buffers with a mid-section gap between them. Changing the gap position allows characters to be efficiently inserted into any position of a large string. I find it amazing that a mainstream programming language hasn't added something like this to its standard libraries.

I think Meta is approaching a mature state. It will probably change in the future to accomodate generics, but I don't see any other major changes coming.

The new Meta caused basically everything to change: JUndo, JUndo Runtime, Umeta, and Verdantium. One needs the latest of everything to build.

There's more for me to do, but I wanted to get the changes to Meta done before the baseline grows too large. More on this later. I'm tired.

New Verdantium Version -- 0818 ; Book "Beyond Java"

2007-08-18T19:59:00.000-07:00

I think I now have a fully working (except for bugs) version of undoable verdantium.standard.DrawApp. All of the persistence code is in now. I have done some smoke tests on the persistence, and it seems to work. This should be the full implementation.

In addition to Verdantium, one also needs the latest versions of Meta and the JUndo Runtime for this to build and work.

All I need to do with this now is fix bugs, documentation quirks (e.g. lack of copyright headers), and other small issues. I also might want to make some of the code more elegant, but that's an issue for later.

On a completely separate note, I purchased an interesting book this morning: "Beyond Java" by Bruce A. Tate (O'Reilly). On one hand, I applaud this book for raising the question of what is beyond Java. I think there are issues that Java and C# don't address. I had to write JUndo in order to address some of these issues. However, I am completely perplexed by how the author selected which languages were important, and which languages were not important. The book considers Python, Ruby, Groovy, and .NET (mostly C#) as major contenders for next generation languages. AspectJ only gets ONE SENTENCE in the entire book. The author doesn't even consider whether the next major programming language might be aspect-oriented. AspectJ deserved much more than one sentence of mention from this book.

I think Java has a few more years in it, particularly since many Java developers haven't even upgraded to JDK 1.5 and generics yet. Nevertheless, the time has come to think about what's next after Java and OOP. The idea for the book was great, but the book's implementation of that idea left me wanting more. One can find several projects on either Wikipedia or Sourceforge that seem significant, but get no mention in the book. For instance the language Pizza was never widely adopted, but was tremendously successful in demonstrating how generics could be added to the Java language. JDK 1.5's generics probably owe something to the Pizza language. Languages that never get wide adoption can be very important in defining the future of programming, and I wish this book would have included many more obscure languages.

JUndo-- Beyond Java with Undo

2007-08-14T16:37:00.000-07:00

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/

Object Models, Google, and Star Office

2007-08-13T20:53:00.000-07:00

According to "The Haskell School of Expression" by Paul Hudak, "Java's recent astonishing rise in popularity is rather perplexing on one hand, yet quite understandable on another. As a language, it is simple and elegant, but certainly not revolutionary." The syntax of Java is similar to C and C++ and there are semantic similarities (hence Java's not revolutionary), but this does not explain why Java was successful or what should be done next.

C++ preceded Java, but C++ objects were basically C structures with added intelligence. Objects in the C++ runtime did not retain their identity. For instance, there was no way to introspect the objects generated by the early C++ compilers such as cfront.

Document object frameworks such as Apple's OpenDoc and Microsoft's Object Linking and Embedding (OLE) required objects with a built-in identity that could be dynamically linked. Objects for these frameworks needed to be separately compiled, and loaded at runtime. Microsoft solved this problem with the Microsoft Common Object Model (COM). Apple's OpenDoc used IBM's System Object Model (SOM), which was an implementation of the Common Object Request Broker Architecture (CORBA).

Typical CORBA development had the programmer produce Interface Definition Language (IDL) bindings to a standard language such as C or C++. This required the production of several entities such as IDL stubs, IDL skeletons, etc. Introspection in CORBA required the use of a Dynamic Invocation Interface (DII) in which dynamic requests were built through a long series of C-like API calls. The CORBA code then had to be submitted to an Object Request Broker (ORB). This made OpenDoc programming a labor-intensive process. Apple tried to solve this problem by creating a "Direct-To-SOM" compiler that would take C++ class definitions and compile them into CORBA objects.

Java appeared at the perfect time and it succeeded where Direct-To-SOM failed-- it provided a simple, straightforward language for building CORBA-like objects. The objects ran in a Virtual Machine (VM), but the VM acted much like an ORB. Later, Sun published a Introspection API for Java that made CORBA DII look like a cumbersome dinosaur.

Java quickly became the perfect language for writing an OpenDoc-like component model. An early pioneer in this realization was one of my former ASU professors: Tony Faustini. Faustini taught computer language courses at Arizona State, and two of his passions were visual languages and functional programming. When Sun announced Java and Applets to the world, Faustini immediately understood the implications. Very early in the history of the language, around the time when Sun was releasing Beta Applet APIs for the upcoming Java 1.0, he did something that I wouldn't fully appreciate until much later. He apparently found the Java ClassLoader APIs, and used them to build a container that loaded a series of visual components on startup. As it went through the loading process it displayed the loaded components in a progress bar-- much like the one Photoshop used when loading plugins on startup. The result was called Visual Java (not to be confused with the commercial product that is currently being called Visual Java). Visual Java could best be described as a GUI builder using an operator-net representation of the programming language Lucid, where the operator-net entities were dynamically loaded at runtime through a ClassLoader.

Through some promotional efforts by Faustini, Visual Java soon found its way to Sun Microsystems and Java evangelist Miko Matsumura. There is an early Java-related telecast with Miko Matsumura and Sun engineer John Gage where Miko used Visual Java to first make an animated dog run forward and then run backward. I developed a MacDraw-like component for Visual Java called Fresco. Verdantium was influenced by all of this.

To make a long story short, part of Visual Java wound up in Sun's BeanBox container for Java Beans. Part of Visual Java wound up in a Sun product called Java Studio. Java Studio seems very far removed from Tony's original vision. I don't know what, if anything, happened to Fresco. In a sense Visual Java turned into Java Beans, and then Java Beans integrated, after many travails, into systems like Star Office.

Suffice it to say I found it interesting when Google today announced it was going to start bundling Star Office with its products. I think Google is starting to understand reality-- they've realized that they aren't going to do everything with web applications and AJAX. I also have doubts about whether Star Office will be a success against Microsoft Office.

Microsoft Office is the McDonalds Happy Meal of the software industry. It is a single monolithic box packed with a hamburger (Microsoft Word), french fries (Microsoft PowerPoint), a soft drink (Microsoft Excel), and a toy (Microsoft Access). Microsoft produces lots of them with enormous economies of scale, and they're all pretty much the same. Star Office is trying to be the cheaper Happy Meal, or the more agile Happy Meal, or the more international Happy Meal, or the Happy Meal that is available in more places, etc. It's hard to imagine any of Star Office's marketing slogans really working, particularly if Microsoft tried to marginalize Star by cutting the price of MS Office. It's hard to make a big monolithic box better than Microsoft. Star seems to be trying to make something a lot like MS Office, and generally seems to be trying to beat Microsoft as its own game. As a strategy, this doesn't seem to be smart.

To compete with Microsoft, Google and Sun need to address the big truth that Microsoft ignores: most people don't want Happy Meals. As Simon Phipps stated during the 2007 JavaOne conference, people want to go to a buffet table where they are free to choose what suits their tastes. That is to say, the Java community needs to develop framework technologies that can be used to leverage the best talents of the Open Source community. Different people want different application suites. Ever notice how Adobe's application suite (i.e. Photoshop, Illustrator, etc.) looks very different from Microsoft's? Observe: Adobe doesn't even provide a spreadsheet. This shows the kinds of choices that people want from their "buffet table." Some people want Photoshop instead of Microsoft Paint (or vice versa). Some people want a page layout program instead of a word processor. Some people want Gantt charts built directly into the suite, and other people would rather not have to drag all of that code through their CPUs like a boat anchor.

Unlike the typical Microsoft offerings, Java is a language that can make the buffet table work. Tony Faustini demonstrated years ago how how to write code that can put the various items on the table at runtime. It's one of the main reasons why Java has been successful as a language. Choice is a fundamental human desire, and it's a desire that Microsoft doesn't satisfy. An open framework providing choice fully utilizes the best strengths of the Java programming language. Instead of another Happy Meal called Star Office with pre-configured applications, Google and Sun should be providing the full buffet table.

New Verdantium Version 0812

2007-08-12T18:21:00.000-07:00

This was another day in which I have been doing a lot more coding than blogging. As in previous days, I have been continuing to work on the new version of class verdantium.standard.DrawApp. Today I got some persistent writes to work from the new DrawApp. Haven't had a chance to test persistent reads yet.

The new Verdantium requires downloading a new JUndo Runtime (both the jundoruntime and umeta packages). Otherwise, the new persistent writes won't work at all.

I also uploaded a new version of the JUndo compiler. Very small changes here. Mostly I fixed some nebulous error message generation.

New Verdantium Version-- 0811

2007-08-11T08:15:00.001-07:00

This release has more work on the undoable version of verdantium.standard.DrawApp. I think all of the functionality is in place for undoable DrawApp except for the persistence support.

Now that I'm almost finished with an undoable drawing application, I've been thinking about producing an undoable text application to replace class verdantium.standard.TextApp and connecting to Sourceforge's Subversion capability. Use of Subversion would allow Verdantium source code to show up on Google Code Search. That would be a good thing.

I might also rewrite some of the change log descriptions in the JUndo and JUndo Runtime projects. Some of my recent uploads on these projects have proven more stable than I thought they would be, and I might rewrite the version logs to declare them to be stable baseline versions.

Anyway, I'm doing more coding than blogging today, so this is a short post. More later.

Is AJAX really the next big thing?

2007-08-09T18:27:00.000-07:00

I woke up this morning and realized to my surprise that it's been about ten years since Apple cancelled its ill-fated OpenDoc project. The cancellation of OpenDoc led directly to the creation of the first version of Verdantium, and ten years later I'm still not finished with it.

Ten years is a long time in the technology field. OpenDoc, even after all of this time, still seems ahead of its time. OpenDoc's concept of small cooperating visual components still does not seem to have been replicated by any popular mainstream framework. Nevertheless, I have thought about Verdantium's future. One one hand someone could argue that Verdantium is a really quaint JFC/Swing system that has been outmoded by the new shift toward Web Applications, Asynchronous Javascript and XML (AJAX) and Service Oriented Architecture (SOA). On the other hand, Verdantium's still seems to suggest a utopian future software architecture rather than a prosaic replay of the past.

There are some projects that the new AJAX web applications do well, and there are other projects that they don't seem to do well at all. Google Documents seems like the ultimate blog creation system rather than something that could overthrow office applications like Microsoft Word. The Google system ignores the printed page-- there's no page view, no print preview, no headers, no footers, no table of contents generation, no settings for different printer page sizes (e.g. A4), no color matching, no kerning, etc. Supporting all of this would require two things: first getting printer information to the network server, and second sending lots of bitmaps over the network in real-time. The second of these is likely to be prohibitive compared to Microsoft Word running in Page View. All of the bitmaps probably won't cross the network fast enough.

In spite of the hype about AJAX-based office applications running on a thin client, it's hard to imagine an AJAX-enabled word processor replacing current desktop software. And that's just the word processor. What about image processing? Would anybody want to use the equivalent of Photoshop over a network pipe?

I think the dominant productivity applications of the future are still going to run very thickly (as in thick-client or typical MS-style office application) on the CPU of the end-user's PC. But at the same time, I think it is possible to have a paradigm shift in how those applications are created.

In the currently dominant office applications Microsoft Office, Corel Ofice, Star Office, etc., there are a small number of enormous monolithic container applications (Microsoft Word, Microsoft PowerPoint, etc.) that embed smaller custom components (e.g. JPEG Movie Players) through protocols (e.g. Microsoft OLE/Active-X). This is counterproductive for both users and developers. Users can't mix and match components as they see fit. Developers don't have options for collaborating.

Imagine a framework where one could create a custom productivity suite by rolling together a large number of very small components through a protocol. No dominant office application-- just a protocol. That was what Apple originally proposed with OpenDoc, and even today it still seems like an exciting idea. Leverage each developer's particular skills. Have each developer write a small component in the domain she knows. Don't try to write a huge containing application, but instead provide a way for many smaller components to work together to create the equivalent of a powerful office suite.

Ever notice that it seems hard to write container applications in Microsoft OLE and Active-X? Of course it is. A lot of small, utilitarian container applications embedding each other could gang up on Microsoft Office.

In Verdantium, I tried to make it especially easy for developers to write container applications. In fact, anybody can write a container component supporting multi-level undo and scripting in a few hundred lines of code. In fact, there's a package in the Verdantium download on Sourceforge called MyContainerApp that gives a fully coded example of this. One who looks through the Verdantium source code long enough will find several other examples. I still think this is relevant post-AJAX.

The Verdantium undo system seems much more advanced than the other undo frameworks I've seen. It's more advanced (and faster) than trying to roll back a relational DB. It's more advanced than the system Sun has in the Swing APIs (which uses the inverse command pattern). It's more advanced than what Apple used to ship with OpenDoc. I am not aware of any Java-enabled open-source framework that is providing a temporal undo capability. I'm not aware of any web application frameworks for doing this, either. Temporal undo is highly advantageous for keeping the self-consistency of the multi-level undo implementation high while keeping the SLOC count (and hence the number of bugs) low. People like small, powerful components that are bug-free. Did I mention that multi-level undo is a capability that many Microsoft Office users ABSOLUTELY REQUIRE? That is to say, they will NEVER switch without it.

I think there is a point to all of this in the post-AJAX and post-SOA world. As computers get faster, there will be a point in the future where a Java-enabled system such as Verdantium will be "fast enough" compared to the current productivity suites. Verdantium will get there long before AJAX does (if AJAX gets there at all). Time is still available because technology hasn't yet advanced to make either alternative fast enough (yet!). "The future" could still happen.

A short description of JUndo

2007-08-07T20:02:00.000-07:00

JUndo-- A Novel Declarative Language

This is the text of a journal paper that I once submitted to SIGPLAN. The paper was rejected on the argument that JUndo was too similar to Haskell. I don't recall Haskell supporting inheritance, polymorphism, or late binding... oh well.

Summary

Typical object-oriented languages such as C++, C#, and Java do not provide direct support for declarative programming. However, large object-oriented programs often integrate declarative concepts in order to implement requirements such as transaction rollback in complex object systems, multi-level undo in large applications, and sophisticated forms of error handling that are intended to return the software to an initial state after an exceptional condition is encountered. A novel language, JUndo (pronounced "jun-doh"), is presented here that allows manipulations of object-oriented data to be expressed in a declarative manner. Further, a set of objects containing an arbitrarily complex set of object-object references can be reverted to a previous state in a straightforward fashion using the language’s constructs. This can be very useful for returning an object system back to a previous consistent state after encountering an exceptional condition.

Key Words: object-oriented programming, functional languages, declarative languages, history management, undo, redo, JUndo

Introduction

This paper describes a language motivated by issues in the implementation of undo capabilities in complex object systems with typical languages (C, C++, Java). One possible undo implementation is to implement the Memento pattern from [9], and then save a Memento before executing each individual command. For many complex object systems this has prohibitive memory and/or performance costs. Another possibility is to use a Command pattern such that there is a "reverse" operation for each operation performed [9]. For instance, the "reverse" of changing the drawing color from blue to red is to change the same color back from red to blue. Edwards suggests that this approach often doesn't work in "real world" applications [8]. This is because the precise side-effects a command may generate can not be known a priori, and hence it is sometimes extremely difficult to compose a command that will reverse them. Edwards solved this problem in the Flatland system by breaking each user-generated command into a sequence of simpler "atomic" commands for which the undo operations could be expressed [8]. Performing undo on a Flatland user command involves invoking the undo operation for each of the simpler commands in the sequence. The author contends that even this approach will not scale for certain types of large systems. That is to say, there are certain types of systems for which it is non-trivial to create simpler "atomic" commands. Consider a command that parses an expression, evaluates the expression, and then side-effects the system by assigning the results of the expression into variables that are used to calculate the results of other expressions (using a topological sort to determine the order of expression evaluation). Generating simpler undoable commands for this requires opening the private internal data of the entire parsing, evaluation, and topological sort pipeline to the command processor so that the undoable commands can access all the individual data members. At best, this seems like a questionable idea from an architectural standpoint. It could also be extremely difficult to implement.

ACIS [6], a commercial solid modeler, provides an example of a undo implementation that does scale. ACIS defines its own base class, and its own pointer class with overloaded assignment operators. Whenever an object is created or deleted or a pointer is reassigned, a record of each change is stored by ACIS. The ACIS undo process essentially consists of reversing each stored object change in the proper order. The ACIS API represents undo information in the form of delta states, where a delta state is, in a very high-level sense, a pointer to a ordered set of undoable object changes. This implementation succeeds because it does not attempt to generate any a priori commands. Instead, the overloaded assignment /creation/destruction operators react to changes as they happen at the object-member level. Arbitrarily complex commands can be handled by such as system with no need to break them into simpler commands as done in Flatland [8]. Such an implementation is very complex, but it does work. The ACIS system is so complex that it borders on being its own programming language. The ACIS APIs were written in C++ using C++ operator overloading. The use of operator overloading to such an extent arguably changes the semantics of C++ objects. For instance, using the delete operator does not actually delete such an object. Instead, the discarded object is attached to a change list.

The JUndo Language

JUndo is motivated by the idea that the semantics of undoable objects, e.g. those created by the operator overload method, are better defined at the language level. That is to say, the language should provide high-level abstractions of the object system state that enable the programmer to focus on creating value-added algorithms rather than laboring on yet another undo implementation. Intensional languages such as ISWIM [1] define time streams that are in many aspects similar to the timelines in [8]. However the intensional time stream, like the delta state, defines streams of data rather than streams of commands. JUndo is not used to write programs. Instead, it generates undoable classes that are embedded in much larger programs such as Verdantium [10]. The rest of this paper will describe the language, to the fullest extent possible in the remaining space, using a set of small coding examples. In Java, a simple class with getters and setters is written as follows:


class IntRef
       {
       private int val;

       public int getVal( ) 
              { return( val ); }

       public void setVal( int inv ) 
              { val = inv; }
       }

The JUndo equivalent of this class is as follows:


 class IntRef
       {
       private int val;

       public int getVal( ) 
              { val };

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

First, JUndo method bodies are expressions rather than collections of statements. Second, note the presence of the keyword "milieu". This keyword, named by ASU professor Edward Ashcroft, defines an environment containing the state of a set of cross-liked objects. Third, the expression val := inv does not side-effect an object member in the usual sense. Instead, it is a functional operator that takes in a milieu and a value (in this case inv) and returns a milieu. The milieu input to operators such as := is curried into each method, much as the "this" reference is curried into each instance method.

JUndo allows multiple parenthesis-types in an expression (parenthesis, brace, or bracket), so the following is also valid:


class ExprnClass
       {

       public int getVal( int a , int b , int c , int d ) 
             { a * ( b % [ c - { d * d } ] ) };

       }

The nesting of multiple levels of parentheses in other languages such as LISP and Scheme can be confusing. The use of multiple types of parentheses in JUndo is intended to help address this issue, and allow a syntax that is more similar to that or C++, Java, and C#.

there is no "return" statement in JUndo. Unlike methods in Java and member functions in C++, methods in JUndo can not have a "void" return type. In fact, there is no "void" keyword (and no equivalent) in the JUndo language. Methods in JUndo must return some non-void entity. This makes JUndo a totally declarative language in the sense that imperative semantics (i.e. statements that either directly alter or side-effect previously defined values) are never used. Instead, methods are defined that leave previously declared values unchanged. JUndo equivalents to methods or member functions with a "void" return type would most likely return "milieu" as in the sample code above.

In JUndo, a milieu is a primitive type just like an integer or a character. Milieux can be manipulated and stored in objects just like any other datatype. This is an important feature because it allows object systems to manipulate entire milieux of data within an application. This allows a set of instances to be pigeonholed into a single element that can be moved from structure to structure as necessary. There are a number of design advantages in being able to keep a closed system of objects as an independent element in a data structure. It makes that set of instances so that they can not be manipulated by another object unless that object has access to that particular milieu. This can be used to shield a set of objects from unauthorized access. It also allows for the creation of data structures of milieux, which is important for implementing concepts such as multilevel undo. An example of a simple class containing a milieu as an instance member is shown below:


class MilieuRef
       {
       private milieu val;

       public milieu getVal( ) 
              { val };

       public milieu setVal( milieu inv ) 
              { val := inv };

       }

Pairs and Object Creation

Like the language Objective C, JUndo does not have constructors. Objects are constructed using class methods. This is advantageous for classes that are designed to only create objects in a selective fashion. For example, some classes are designed to only allocate a new object if an object of identical value does not already exist. A number of string implementations use this to ensure that two strings are identical iff. their OIDs are. This can greatly reduce the amount of computation time required for string comparison. Using a class method (as indicated by the static keyword) instead of a new operator gives each class direct control over when and how its instances are created. An example of a class method to create an object of class Singleton is:


class Singleton
{
     protected static Singleton instance;
 
     public static pair[ Singleton ] new_Singleton( )
     {
        if instance != null then [ instance , thismilieu ] else
        let
        {
           pair[ Singleton ] sing = [ Singleton , thismilieu ].allocate_Singleton();
           milieu q = [ Singleton , sing.milieu ].instance := ( sing.cobj );
        }
       with [ instance , q ] fi fi
    };
 
 
        /* More Code Here ... */
 
 
}

This example also introduces a new JUndo data type called the pair. The pair of a object reference of type A is defined as . Pairs do NOT have OIDs, and they do not exist in milieux except as members of objects or classes. One can see why the pair is useful by thinking about what the new method does. It both creates a new object, and it creates a modified milieu that contains that new object. The pair makes it easy to return both of these entities to the caller at the same time. A pair is built by placing the item and milieu that it is to contain in brackets in a manner like the following: [ obj , thismilieu ]. Elements can be extracted from a pair using the .cobj and .milieu operators. The construction class methods, which can be given arbitrary names, allocate new objects by using the protected class method allocate( provided by the runtime. After allocating the object, the method is then free to initialize it in arbitrary ways (as the above example does).

Because a pair always contains two and only two elements, the compilation of a pair takes on many of the characteristics of the compilation of a primitive type. An JUndo compiler treats pairs very differently from the manner in which a standard compiler would handle code generation for a typical derived type such as an array or a record. To review, expressions on a primitive type in typical languages are mapped to primitive operations (in a language like Three Address Code) that write to temporary variables defined by the compiler. Each primitive operation has one primitive temporary variable as its result. Similarly each primitive expression on an JUndo pair, in the compiled representation, has two temporary variables as its result: one for the object reference and one for the milieu. Moreover each primitive operation on a pair maps to two Three Address Code operations, one for each of the two temporary variables that make up the pair. In this way pairs get mapped directly to lines of Three Address Code in the same way that a primitive type does, except that everything with a pair gets mapped to two lines instead of one. This allows operations on pairs to mapped into more efficient code than is otherwise possible. This is an important optimization because pairs play a fundamental role in the language.

Inheritance, Encapsulation, and Polymorphism with Functional Programming

An object-oriented language can be defined as one that supports inheritance, encapsulation, and polymorphism. JUndo supports all of these concepts. JUndo's implementation of these concepts is almost identical to JDK 1.4 (except that JUndo doesn't support inner classes). Intensional languages often define functions by declaring them in let blocks. In contrast, JUndo doesn't support this. JUndo, following the Java convention, requires "functions" to be implemented as methods in the scope of some class. However, JUndo methods can call each other in the same recursive fashion as intentional functions. Methods are preferred over let-functions for a couple of reasons. First, methods can be translated into efficient object code more easily then let-functions. This is particularly true when writing code for a Java virtual machine. Second, methods can be overriden yielding a greater degree of expressive power. Finally, the use of methods is more consistent with the concepts of data abstraction.

JUndo contains a complete set of functionality for producing a functional program, but does not provide some of the operators from intensional programming such as “fby”, “prev”, “next”, and “at”. The semantics of these operators are such that their implementation tends to be recursive, although there are optimizations for mapping special cases such as tail-recursion to non-recursive code. A language does not necessarily need to be recursive in order to define its operations using a declarative semantics. For example, the Datalog programming language uses Domain Relational Calculus to map a number of Datalog rules into iterative relational queries. In Tuple Relational Calculus, an example of a declaration of a simple iterative (SQL-like) query expression is as follows:


select A.emp from A, B where [boolean expression]

Another trend in Object-Oriented programming is the use of iterators in frameworks such as Java Collections Framework (JFC). For instance, a Java method using iterators might resemble the following:


public Iterator getEmps( Iterator E , Supervisor S )
{
Vector v = new Vector();
while( E.hasNext() )
 {
 Employee emp = (Employee)(E.next());
 if( emp.getSalary() > S.getSalary() )
  {
  v.add( E );
  }
 }
return( v.iterator() );
}

Similar code no doubt exists in a number of production programs written in Java. Note that the above program can be written in a form of pseudocode that looks like the following:


public Iterator getEmps( Iterator E , Supervisor S )
{
 return( select Emp from Emp in E where ( (Employee) Emp ).getSalary() > S.getSalary() );
}

The above code has some SQL-like syntax, but the semantics is different. The above expression iterates over an Iterator, whereas typical SQL iterates over relations. More importantly, the above expression suggests a mechanism for expressing JFC-like iteration patterns through declarations (as opposed to imperative while loops). This "select" semantics provides an alternative to operators from intensional programming such as “fby”, “prev”, “next”, and “at”. The "select" semantics creates declarations that map readily to iterative code, whereas typical intensional language compilation requires an optimization process to remove recursive elements of the intensional declarations. A typical select expression in JUndo looks like the following:


pair[ IteratorFactory ] empFac = select e 
 from e : Employees , s : Supervisors 
 into now 
 where ( [Employee] e ).getSalary() > ( [Supervisor] s ).getSalary();

In the above expression, which finds all employees who make more than some supervisor, "Employees" and "Supervisors" are of type IteratorFactory, where IteratorFactory is an interface with a single method called iterator() that returns an Iterator. For instance, the java.util.Vector class in the Java language could easily by turned into a Java iterator factory because it already has an appropriate iterator() method. Several other classes in JCF have similar iterator() methods. In the JUndo syntax, Iterator and IteratorFactory can be defined as follows:


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

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

Referential Transparency in JUndo

Functions in pure functional languages obey the concept of referential transparency defined as "the execution of a function always produces the same result when given the same parameters" (7). A form of referential transparency also holds for JUndo methods. Consider the following call to a JUndo instance method:


[ myObj , myMilieu ].myMethod( a , b , c , d )

In a typical implementation of a JUndo compiler, myObj would be curried into a this parameter in the object-code version of the method call (much as is currently done in most C++/Java/C compilers). The milieu myMilieu would also be curried into a this_milieu parameter in the object-code version of the method. In JUndo defining referential transparency requires the inclusion of the "hidden" parameters that are typically curried into the object code. For instance, the instance method myMethod above always returns the same result (to within the ability to observe differences using the language) as long as the equivalents of a, b, c, d, myObj, and myMilieu remain the same. This includes functions that return milieu describing modifications to objects and functions that return milieu describing the creation of new objects. The definition of referential transparency for a JUndo class method is similar, but only this_milieu is curried (a this parameter isn't curried because it is an error for class methods to use a this reference).

Conclusion

Multi-level undo can be implemented in JUndo by creating a class library that associates a milieu with each important point in the undo/redo timeline. Details have been omitted in order to fit SIGPLAN's length limitation. To conclude, the reasons for motivating the JUndo language have been expressed, and some novel features of the language have been described. There are a number of other elements in the language, such as arrays and let expressions, that are not described in this paper. For additional explanation, please see the following web site: http://verdantium.blogspot.com

References

1. W. W. Wadge, and E. A. Ashcroft, Lucid, the Dataflow Programming Language, Academic Press, New York, NY, 1985.

2. P. J. Landin, ‘The Next 700 Programming Languages’ CACM, 9, 157-166 (1966).

3. T. Faustini, Visual Java, Computer Software, (unpublished).

4. K. Arnold, and J. Gosling, The Java Programming Language, Addison-Wesley, Menlo Park, CA, 1996.

5. B. Stroustrup, and M. A. Ellis, The Annotated C++ Reference Manual, Addison-Wesley, Menlo Park, CA, 1990.

6 J. Corney, and T. Lim, 3D Programming with ACIS, Saxe-Coburg, Stirling, UK, 2001.

7. R. W. Sebesta, Concepts of Programming Languages, Seventh Edition, Addison-Wesley, San Francisco, CA, 2005.

8 Edwards, K., Igarashi, T., LaMarca, A., and Mynatt, E. D. A Temporal Model for Multi-Level Undo and Redo. In Annual ACM Symposium on User Interface Software and Technology, November 2000, pp. 3140. http://citeseer.csail.mit.edu/edwards00temporal.html

9 E. Gamma, R. Helm, R. Johnson, and J. Vlissides, "Design Patterns", Addison-Wesley, Menlo Park, CA, 1995.

10 Green, Thornton, "Verdantium-- Towards a Java-Enabled Compound-Document Model", Poster Session, OOPSLA 2000 Conference, ACM, October 15-19, 2000, Minneapolis, Minnesota.

Verdantium version 070806

2007-08-06T20:33:00.000-07:00

This is a bug-fix for yesterday's version (070805). This version is more stable, but not yet stable. More of the undo functionality in DrawApp is working in this version. There is still much to do on this, particularly for supporting persistence. However, a surprising amount of the multi-level undo support is working in this version.

Changed Verdantium description on SourceForge

2007-08-06T18:48:00.000-07:00

I keep noticing a trend where a lot of people download Verdantium, but few people download the underlying framework projects. For instance there were nine Verdantium downloads within a short period after the latest post, but there were very few downloads of Meta or Jundo Runtime. So I suspect that the current Verdantium downloads aren't producing successfully executing builds. One needs to download the new versions of the other projects in order to build the new Verdantium version. To help this, I've tried to make it easier for people to notice this blog post. The original Verdantium description read as follows:

Verdantium is an OpenDoc-like compound-document framework, and an open-source alternative to frameworks underlying OpenOffice, StarOffice, Corel Office, and Microsoft Office. Verdantium is written in a combination of JUndo, Java JFC/Swing, and Java-2D.

To keep the new description in the in the 254 character limit I changed it to:

Verdantium is an OpenDoc-like compound-document framework, and an open-source alternative to frameworks underlying OpenOffice, StarOffice, Corel Office, and Microsoft Office. Written in JUndo / Java JFC/Swing/Java-2D See http://verdantium.blogspot.com/

More about the 0805 (i.e. August 5) Verdantium / JUndo Update

2007-08-05T20:07:00.000-07:00

Now that the August 5 update is fully posted I wanted to log a little about this particular version. The new version is an unstable test version with an expanded undo capability. I've been coding on this version for a while now, and now that I have got something that is nominally working I wanted to archive it to sourceforge before it got accidentally deleted by something like a hard disk crash (stranger things have happened with my hard disk lately).

So this is a Verdantium release that is partially an advance, partially untested, and partially outright broken. The nexus of the Verdantium changes is the verdantium.standard.DrawApp class. This class now has a partial implementation of multi-level undo. Some of it is actually working quite well. You can add a series of lines to the DrawApp, and then undo them one by one. Other aspects of the implementation, especially DrawApp persistence, are completely broken while I finish writing the code.

As the name implies, "JUndo" is is a multi-level undo language for Java. Hence, it is spelled with a "J" for Java followed "Undo" for undo. JUndo is actually more than that, but undo is the primary practical issue that the language resolves. JUndo makes it feasible to use undo patterns that are difficult to implement in ordinary Java. Many typical systems use one of two patterns: either store a memento on every operation that encapsulates a copy of the entire data state, or create an inverse command for every command. The first is very computationally expensive and memory-consuming for programs storing large amounts of data (imagine making a copy of the entire data store every time you update a field), and the second tends to require the creation of very sophisticated command objects to undo operations such as deletions or sort operations (e.g. a command to sort a list requires an undo command that will "unsort" a list-- think about that the next time you bubble sort). JUndo solves these problems by providing objects which support a temporal model of undo. In Verdantium / JUndo undo, inverse commands aren't needed. The developer simply never needs to create an inverse command. Moreover, the JUndo system is very efficient at only storing changes between states, rather than generating memento patterns describing the entire state of a system.

Some of this can be seen in the new version of DrawApp. Some very complex operations are performed on the rendering primitives in DrawApp, and yet there is no need to create inverse commands. The elimination of inverse commands potentially makes the developer much more prroductive, and potentially makes the resulting system much more self-consistent. Inverse commands sometimes have bugs, and these bugs can produce inconsistent data states and systems that are not self-consistent. JUndo implementations avoid these inconsistencies. Further, operations tend to be fast because only changes to objects are stored.

As an example, primitives can be added to the DrawApp rendering list without the need to produce inverse commands to remove those items from the rendering list. Instead, the undo system simply remembers what the list looked like in its previous state and automatically takes the list back if the user performs an undo operation. This should become very impressive as the new implementation of DrawApp is fully developed. Developers can take advantage of these new extensions to the undo system in their own components.

New Verdantium, JUndo, and Meta Release 070805

2007-08-05T15:39:00.000-07:00

I just put a new release of Verdantium, and JUndo on sourceforge. To get a full working Verdantium build, you need to download code from the following sourceforge projects:

http://sourceforge.net/projects/verdantium/

http://sourceforge.net/projects/jundoruntime/

http://sourceforge.net/projects/meta/

There is a new build requirement in this build: The umeta package from the JUndo Runtime project is now a required library for Verdantium. Also, to build the ".JUndo" files into Java source, one needs the following project:

http://sourceforge.net/projects/jundo/

I've made this blog the project page for all of the above sourceforge projects on the theory that if you are interested in one of them then you should probably be interested in the others. Verdantium requires JUndo and Meta in order to run. Understanding JUndo is useful for writing verdantium components, particularly components that support multi-level undo. Enhancements to JUndo are made just to support Verdantium. If one is interested in developing for Verdantium then one would probably also be interested in JUndo.

Similarly, if one is interested in JUndo then one should probably be interested in Verdantium. Programming languages have to answer the question "what is this [language] good for?" Otherwise, there is no point in developing a new language. Verdantium and its multi-level undo system gives one a context for the kinds of problems that JUndo was created to solve. That is to say, Verdantium ties JUndo to a practical application.

I have been looking at download statistics, and I see many downloads for Verdantium, but far fewer downloads for JUndo and Meta. This seems strange given that one needs the latter in order to run the former. I wonder if people are actually getting workable systems if they are downloading Verdantium, but not JUndo or Meta. If you download Verdantium, then please download the other projects.