Blocks In Java Blocks In JavaAlso see BlocksInCsharp for the CeeSharp translation of this excellent work.
Creating Abstract Syntax Trees and using Blocks in Java
I have designed and constructed a simple JavaLanguage package that enables me to use HigherOrderFunctions and FunctorObjects in Java. If this sentence leaves you feeling a little cold, I will attempt to define these terms in the context of an object-oriented language like Java. A HigherOrderFunction is any method that takes expressions (rather than data) as its argument. Examples include the SmalltalkLanguage enumerators #detect and #do, the LispLanguage #mapcar function, or the CeePlusPlus standard library algorithms std::for_each or std::accumulate. A FunctorObject encloses expressions within an object that can be passed around as data and dynamically evaluated by a HigherOrderFunction. Smalltalk blocks are a kind of FunctorObject. The CeePlusPlus Standard Library simulates FunctorObjects using function objects. In Java, we can enclose a lexical unit of code within an Object with AnonymousInnerClasses. Consider the following Java code that uses the java.lang.Runnable class to enclose an expression within an object:
Runnable thread_logic = new Runnable() {
public void run() {
Documents.getCurrent().checkSpelling(); } };
We literally en-close the method checkSpelling so it can be passed around as data and evaluated dynamically by sending thread_logic the message run. This kind of object is sometimes called a block, closure, or lexical closure. They put functions into a form that is suitable for passing to a HigherOrderFunction, such as an InternalIterator.
For a very straight forward object-oriented example of this, consider the VisitorPattern. In this pattern, we have a participant called the Visitor whose instances can be accepted by a data structure and applied to each of its elements. The accept member is referred to as an InternalIterator because it allows us to traverse its elements without having to use an external iterator object. For example:
tree.accept( new SummingVisitor() );In this example, the tree accepts a visitor that will sum each of its elements. In this scenario, the SummingVisitor is a kind of FunctorObject and tree's accept method is a specific type of HigherOrderFunction referred to as an InternalIterator. The VisitorPattern allows a programmer to enclose the logic to process a node or element within a FunctorObject called a visitor and apply that logic using a HigherOrderFunction called accept(visitor). You can follow the links for HigherOrderFunction or FunctorObject to learn more about these terms.
While this page concentrates on the foundation for creating and using FunctorObjects, I do provide some example implementations for HigherOrderFunctions that can use these closures. This foundation was created to (1) approximate Smalltalk blocks or closures that can be easily specialized and constructed on the fly and (2) provide a set of predefined expression blocks, adapters, and combinors that can be composed to form complex expressions. Client code should be able to treat these FunctionObjects uniformly without knowing the technique that was used to create them. Both techniques will produce expressions that can be passed around and sent messages just like any other object. Because each interface in the foundation extends the java.io.Serializable interface, each FunctorObject can also be serialized.
I will refer to these two techniques as expression specialization and expression composition. The first technique allows programmers to create a FunctorObject on the fly by specializing an expression interface. The second allows a programmer to literally compose a FunctorObject from concrete classes that represent fundamental binary/unary operators such as and, or, not, less, equals, and so on.
Turning Expressions into Objects
Consider the following expression that determines if an object arg1 is greater than or equal to another object, arg2:
assert( arg1.longValue() >= arg2.longValue() );This is your run of the mill expression. To be a little more specific, it is a binary expression. It is called this because it compares two values. To be even more specific, it is a binary predicate because it uses a binary relational operator to produce a boolean result. While all this is interesting, it is still just an expression. It can only be executed where it exists in the source code, when it is encountered in the stream of execution, and it can only be evaluated with the values of arg1 and arg2 at the time of evaluation.
The simple binary predicate above becomes much more than just an expression when it is enclosed within an object. Each of the stated constraints is broken just by turning the expression into FunctorObject. Consider the following example, which creates a FunctorObject using expression specialization:
BinaryPredicate aBlock = new BinaryPredicate() {
public boolean is( Object lhs, Object rhs ) {
return ((Long)lhs).longValue() >= ((Long)rhs).longValue(); } } );
We have specialized the binary predicate by implementing an interface named BinaryPredicate. This allows us to evaluate the expression (a) wherever we want (by passing it around as data), (b) whenever we want (by invoking is), and (c) with whatever values we want (by passing them as arguments to is).
Consider the following examples which use our new FunctorObject:
Long x = new Long( 10 ); Long y = new Long( 10 );The following example creates the same binary predicate using expression composition:assert( aBlock.is( x, y ) ); // passes
y = new Long( 11 );
assert( aBlock.is( x, y ) ); // fails!!
BinaryPredicate aBlock =
new Compose( new Or(), new Greater(), new Equal() );
This version of aBlock encloses the same basic functionality as the previous example. However, unlike the block created with specialization, this technique does not require us to implement the is member explicitly. Instead we have composed it from fundamental expression building blocks.
Client code executing these two expression object will have no idea which was created with specialization or which with composition. This is the advantage to providing a single abstraction for both. In fact, composition simply creates concrete implementations of the same interfaces we create closures for with specialization. The foundation has three layers:
More on Expression Specialization
We can support the expression specialization with a few basic interfaces that can be implemented on the fly with AnonymousInnerClasses. In fact, you are probably doing this already if you write Swing applications. For example, consider the following use of WindowAdapter.
addWindowListener(
new WindowAdapter() {
public void windowClosing( WindowEvent e ) {
System.exit(0); } } );
This specializes the WindowAdapter interface using an AnonymousInnerClass. You can say that in the above example, the FunctorObject interface named WindowAdapter has been specialized for handling windowClosing expressions. Unfortunately, this interface is not generic enough to implement generalized expressions. For example, the interface member windowClosing would clearly not be appropriate for adding two numbers together or checking the equality of two objects. Even if we were to ignore its inappropriate name, it has no return value.
As an alternative, the following example uses an interface named UnaryPredicate. This interface is appropriate for any kind of boolean expression (i.e. a predicate) that operates on a single argument (i.e. unary). The example specializes this interface to compare each element in a name array to a specified string. This is done by passing itself as data to an InternalIterator named detect. The detect iterator evaluates each element in its collection against whatever unary predicate object is passed into it and returns the first element that causes the predicate to answer true.
Object found = name_array.detect( new UnaryPredicate() {
public boolean is( Object each ) {
return each.equals( "some_name" ); } } );
In this example, I explicitly write the expression logic - i.e. each.equals( "some_name" ) - just as I would in a while loop. However, instead of using it as a loop condition, I store it in an object that I can pass to an iterator function. The loop encapsulated by the iterator function uses my expression object to control its iteration. The unary predicate code is just like any other expression in my source-code save for the fact that I have put it into a format that allows me to pass it around as data. There is nothing all that fancy about doing this - I am just defining an interface member on the fly with the expression I want to be executed.
Creating a HigherOrderFunction
Lets look a little closer at the InternalIterator named detect. This is just a function that, together with my FunctorObject, encapsulates the following use of an ExternalIterator (sometimes called outer iterator):
03: Iterator at = name_array.iterator();
04: while ( at.hasNext() )
05: {
06: Object each = at.next();
07: if ( each.equals( "some_name" ) )
08: return each;
09: }
This is what most of us Java programmers are used to seeing. This particular use of the Iterator detects the first element for which the expression at line 07 evaluates as true. Let's slowly transform this use of the ExternalIterator java.util.Iterator to the InternalIterator detect.
First, let's leave the ExternalIterator, but replace the expression with a message sent to an object - a FunctorObject. To do this we will take the expression at line 07 and place it into the specialization of the UnaryPredicate interface:
UnaryPredicate aBlock =
new UnaryPredicate() {
public boolean is( Object each ) {
return each.equals( "some_name" ); } } );
This really isn't that much different than:
class EqualsSomeName implements UnaryPredicate
{
public boolean is( Object each )
{
return each.equals( "some_name" );
}
}
UnaryPredicate aBlock = new EqualsSomeName();
We are just using an anonymous class name since we are never going to reuse this specialization of UnaryPredicate. It's a one-time specialization. Next, we need to replace the expression we took from line 07 with the unary predicate object we just constructed:
03: Iterator at = name_array.iterator();
04: while ( at.hasNext() )
05: {
06: Object each = at.next();
07: if ( aBlock.is( each ) )
08: return each;
09: }
Okay, so we now have a loop whose behavior can be changed based on the FunctorObject passed to it - i.e. based on the definition of aBlock. The final step to making it an InternalIterator is to place it within a method of our Collection class. This method will allow us to send different objects for use by the loop. We can do this very easily. In fact, we don't even need to change the loop code, just move it under a method named detect, change the name of the variable name_array to the class's private collection instance, and indent the whole thing:
01: public Object detect( UnaryPredicate aBlock )
02: {
03: Iterator at = name_array.iterator();
04: while ( at.hasNext() )
05: {
06: Object each = at.next();
07: if ( aBlock.is( each ) )
08: return each;
09: }
10:
11: return null;
12: }
Congratulations!! You've just created a generic HigherOrderFunction that uses a FunctorObject!! We can now quickly create new expressions without ever having to re-code this kind of loop. For example:
Object found = name_array.detect( new UnaryPredicate() {
public boolean is( Object each ) {
System.println( each.toString() );
return false; } } );
This example doesn't even detect anything. In fact, the predicate always returns false so that we can print every element in the collection on its own line. Pretty cool, huh? We can make the expression embedded in the Functor as simple or as complex as we want. We can create new objects, call other methods... Almost anything we can do in explicit looping code, we can do with a FunctorObject and an HigherOrderFunction.
Expression Composition
So far, the FunctorObjects we have been creating use expression specialization. Expression composition is only slightly different. Unlike specialization, we need more than a few basic interfaces. Composition requires concrete classes that we can construct and aggregate together. It requires that I be able to construct the same expressions I can build with specialization, but without having to explicitly code those expressions. For example, I need to be able to recreate the example expression from the previous section without having to explicitly implement the UnaryPredicate interface with the equals( "some_name" ) expression. Let's take another look at that first example so we have it in our memories:
Object found =
name_array.detect(
new UnaryPredicate() {
public boolean is( Object each ) {
return each.equals( "some_name" ); } } );
In this FunctorObject we are actually executing a binary predicate. However, we have bound the second argument so that we can execute the expression as a unary predicate, where the only argument is each element of the collection. Contrast this to the following that aggregates instances of predefined concrete classes:
final String second_argument = "some_name";
UnaryPredicate aBlock =
new BinderSecond(
new Equal(),
second_argument ) ); // bind second argument of equals
Object found = name_array.detect( aBlock );
This code performs the same traversal and provides the same results as the first example. However, it does so without requiring that we hand-code the equals expressions. BinderSecond is actually a Unary Predicate that adapts a Binary Predicate. It does this by using any valid Binary Predicate and saving (binding) its second argument. In this case, we take an input value of "some_name" and an instance of the binary (i.e. two arguments) predicate named Equal. The Binder second adapter binds that input value as the second argument of the binary predicate Equals.is( a1, a2 ). The result is a two argument predicate minus one argument, in other words, a unary predicate. Consider the following code for Binder Second:
class BinderSecond implements UnaryPredicate
{
private BinaryPredicate m_pred;
private Object m_arg2;
public BinderSecond( BinaryPredicate pred, Object arg2 )
{
m_pred = pred;
m_arg2 = arg2;
}
// The Unary Predicate Interface
public boolean is( Object arg1 )
{
return m_pred.is( arg1, m_arg2 );
}
}
It's actually pretty simple when you see the code. It literally binds the second argument of a binary predicate so it can be called as a unary predicate.
Expression specialization and Expression composition both do the same thing, but the specialization approach requires a priori knowledge of the problem being solved. We can not change the solution without changing our source code. In our second implementation of the example, We would only need to construct a different instance of the UnaryPredicate by supplying it with different arguments.
Specialization works great for the same problems on which you would use Smalltalk blocks while the composition is great for Visual Rule or Constraint Builders that allow the user to dynamically build expressions using drag and drop on a database of serialized FunctorObject legos.
The Abstract Syntax Tree (com.tripwire.rdifalco.ast) package I show here allows a programmer to take either approach in Java. Because both use the same abstraction, it becomes easy to make a static system using specialization into a dynamic system using composition. The interfaces are the same!! So, rather than using the traditional GangOfFour InterpreterPattern, which can get pretty complex, I use a simple design that is more similar to the function-objects and HigherOrderFunctions used by AlexanderStepanov in STL and the Ada Generic Library.
Basic Concepts...
I split the class tree of the ast package into three basic clusters:
To ease the use of these classes in a way that is similar to Smalltalk blocks, I provide a default implementation of each interface into a class called ast.Block. The block class can still be used as the base for AnonymousInner closures, it will just be easier to type and simpler to use. The user need only remember one instead of nine class names. Consider the example we opened this page with:
Object item = names.detect( new UnaryPredicate() {
public boolean is( Object arg ) {
return arg.equals( "some_name" ); } } );
Using the helper class Block, we can write the same code like so:
Object item = names.detect( new Block() {
public boolean is( Object arg ) {
return arg.equals( "some_name" ); } } );
Now consider the following three examples which show the versatility of the Block:
1. Block as UnaryPredicate
Person joe = (Person)
names.detect( new Block() {
public boolean is( Object each ) {
return ((Person)each).isName( "Joe" ); } } );
String sOnePerLine = (String)
collection.inject( new String(), new Block() {
public Object eval( Object val, Object each ) {
return val.toString() + each.toString() + '\n'; } } );
3. Block as UnaryProcedure
final Mutable.Integer counter = new Mutable.Integer();
collection.enum( new Block() {
public void run( Object each ) {
++counter.value; } } );
Before we get into the Block class, we need to define the foundational interfaces it simplifies. The basic package name I will use is ast for abstract syntax tree. The full package name will be com.tripwire.rdifalco.ast.
Implementation of Basic Interfaces
If you recall, we have three clusters, each with three basic interfaces. I call these the AST foundational interfaces. The pattern is well defined and consistent - each interface has a single member. The member takes zero, one, or two arguments as Objects and returns a boolean, an Object, or void. Each should be placed into its own source file:
Cluster: Predicate
#package com.tripwire.rdifalco.ast;public interface Predicate extends java.io.Serializable { boolean is(); }
#package com.tripwire.rdifalco.ast;public interface UnaryPredicate extends java.io.Serializable { boolean is( Object arg ); }
#package com.tripwire.rdifalco.ast;public interface BinaryPredicate extends java.io.Serializable { boolean is( Object arg1, Object arg2 ); }
Cluster: Function
#package com.tripwire.rdifalco.ast;public interface Function extends java.io.Serializable { Object eval(); }
#package com.tripwire.rdifalco.ast;public interface UnaryFunction extends java.io.Serializable { Object eval( Object arg ); }
#package com.tripwire.rdifalco.ast;public interface BinaryFunction extends java.io.Serializable { Object eval( Object arg1, Object arg2 ); }
Cluster: Procedure
#package com.tripwire.rdifalco.ast;public interface Procedure extends java.io.Serializable, java.lang.Runnable // NOTE: { void run(); }
#package com.tripwire.rdifalco.ast;public interface UnaryProcedure extends java.io.Serializable { void run( Object arg ); }
#package com.tripwire.rdifalco.ast;I see a lot of ConceptualIntegrity here. The interfaces are simple and consistent. This is essentially all we need to build everything else. Note that the Procedure class extends java.lang.Runnable. This allows us to use our ast abstractions anywhere, even in those places where java requires an Runnable instance, such as with the java.lang.Thread class.public interface BinaryProcedure extends java.io.Serializable { void run( Object arg1, Object arg2 ); }
Without going any further, we can start using these interfaces for anonymous inners and InternalizeExternalIterators. For example, consider the following internalization of the java.util.Iterator:
public class Iterate
{
static public
Object detect(
List list,
UnaryPredicate aBlock )
{
Iterator at = list.iterator();
while ( at.hasNext() )
{
Object each = at.next();
if ( aBlock.is( each ) )
return each;
}
return null; // indicate none-detected
}
static public
void enum(
final List list,
final UnaryProcedure aBlock )
{
detect( list, new UnaryPredicate() {
public boolean is( Object each ) {
aBlock.run( each );
return false; } } );
}
[...]
}
And so on. You can do this for all the basic InternalIterator types - #inject, #select, #reject, #collect, and so on. We can start using this package now just with its basic interfaces. For example::
File file = (File)Iterate.detect( aFiles,
new UnaryPredicate() {
public boolean is( Object each ) {
((File)each).getName().equals( "temp.dat" ); } } );
Defining a Concrete and Universal Java Block
With the block class, I can use detect without having to remember the name of the nine interface types. One can simply type Block and remember is for boolean, eval for java.lang.Object, and run for void. The Universal Block class is incredibly convenient and straightforward. It essentially provides a default implementation for all of the interfaces we just defined. Besides providing a mapping from multiple interfaces to a single class, the Block implementation of the Function interfaces will forward to the Predicate interfaces and then convert its boolean result to java.lang.Boolean (i.e. an Object). The Predicate and Procedure interfaces, if not overridden, will call the Function interfaces and either convert or discard the return value appropriately.
#package com.tripwire.rdifalco.ast;public class Block implements Procedure, UnaryProcedure, BinaryProcedure, Function, UnaryFunction, BinaryFunction, Predicate, UnaryPredicate, BinaryPredicate { //..The Procedures
/* [JavaDoc Header] * Default implementation of a <code>Procedure</code> interface. This * implementation calls the <code>Function</code> interface member * <code>eval</code> and discards its return value. */
public void run() { eval(); }
public void run( Object arg1 ) { eval( arg1 ); }
public void run( Object arg1, Object arg2 ) { eval( arg1, arg2 ); }
//..The Functions
/* [JavaDoc Header] * Default implementation of a <code>Function</code> interface. This * implementation calls the <code>Predicate</code> interface member * <code>is</code> and returns its <code>boolean</code> value as an * instance of <code>java.lang.Boolean</code>. */
public Object eval() { return is() ? Boolean.TRUE : Boolean.FALSE; }
public Object eval( Object arg1 ) { return is( arg1 ) ? Boolean.TRUE : Boolean.FALSE; }
public Object eval( Object arg1, Object arg2 ) { return is( arg1, arg2 ) ? Boolean.TRUE : Boolean.FALSE; }
//..The Predicates
/* [JavaDoc Header] * Default implementation of a <code>Predicate</code> interface. * This implementation calls the <code>eval</code> member of the * <code>Function</code>, casts its result as a * <code>java.lang.Boolean</code>, and returns the result of * calling <code>booleanValue</code>. */
// NOTE: No error checking!!
public boolean is() { return ((Boolean)eval()).booleanValue(); }
public boolean is( Object arg1 ) { return ((Boolean)eval( arg1 )).booleanValue(); }
public boolean is( Object arg1, Object arg2 ) { return ((Boolean)eval( arg1, arg2 )).booleanValue(); } }
A Brief Excursion on Iterators
I want to stop here to say that all of my abstract data types and foundational structures use InternalIterator functions like Smalltalk rather than the ExternalIterator objects talked about in DesignPatterns, used by STL, and supplied with the Java Collection Classes. Furthermore, I have done performance tests on all of these and the InternalIterators win every time over the java.util collections. Sometimes they are 4 or 5 times faster than their ExternalIterator equivalents.
The reason for this is pretty straightforward. When creating an ExternalIterator class, iteration is decoupled from the data structure - it is not part of the collection. As a result, it must use the same public interface everyone else does. Even if you avoid this by exploiting package visibility and inner-classes, it is still an unbounded operation with little control. You cannot control how many times next is called and as such, each access calls a member of the collection object that must check the range of the specified index. Furthermore, it is difficult to implement an ExternalIterator for a distributed system or to control synchronization. For more on this, see Iterators: Signs of Weakness in Object-Oriented Languages at ftp://ftp.netcom.com/pub/hb/hbaker/Iterator.html.
Using iterator methods as Smalltalk and Lisp do is much more efficient. Since the iterator can share the implementation of the data structure, the author has complete control over the iteration! For example, the iterator function for an array class need not check the validity of its indices:
public void forEach( UnaryProcedure aBlock )
{
int end = m_nCount;
for ( int at = 0; at != end; ++at )
aBlock.eval( m_contents[ at ] );
}
Simple. Since the function forEach is bounded, we need not perform a boundary check on each access. Now consider its usage:
list.forEach( new Block() {
public void run( Object each ) {
Dbg.trace( "item: " + each ); } } );
Contrast this to the following use of the Iterator DesignPattern:
Iterator iter = list.iterator();
while ( iter.hasNext() )
Dbg.trace( "item: " + iter.next() );
We can zero out on the construction of the Iterator object since we must also create a Block instance with the internal version. However, every operation on Iterator must map to the list object's class and every iteration of the loop must check the current value of the Iterator against the boundaries of the collection represented by list.
My big question is why didn't Java use iterator functions with code blocks rather than an ExternalIterator class? My guess is that because of its syntactical similarity to C++, it is easier for programmers to relate Java to C++ than to Smalltalk or Lisp. As a result, it was more natural for the designer of the Java Collections to take a more traditional C++ view of the world and support procedural over Object-Oriented iteration. Even though procedural iteration is not as optimal as fully-encapsulated O-O iteration, it either just didn't occur to them, or they did not have the courage to take the Java/C++ community in a new and different direction. Anyway, check out that paper I provided a link to earlier in this section. If you can get through some mighty ugly Lisp code, there are some interesting points to find.
If you are interested, here are the iterators I support. If I get enough requests, I will also publish my adt (abstract data types) package. I use the traditional Smalltalk enumerators with a couple of additions and variations to accommodate Java's feel. I'm just going to list the enumerators here and leave off the collection members:
interface Items // a bunch of items (unordered collection)
{
the enumerators
//* eval block for each
void enum( UnaryProcedure aBlock );
//* increment count for each true
int count( UnaryPredicate aBlock );
//* remove item for each block that answer true
void remove( UnaryPredicate aBlock );
//* detect first for block answers true
Object detect( UnaryPredicate aBlock );
//* inject value into block with each item
Object inject( Object value, BinaryFunction aBlock );
//* answer new collection for each true
Items select( UnaryPredicate aBlock );
//* answer new collection for each false
Items reject( UnaryPredicate aBlock );
//* answer new collection of non-null results
Items collect( UnaryFunction aBlock );
}
While it's a simple collection hierarchy, I have another interface for items that can be sequenced. This interface adds another bunch of its own enumerators in addition to those defined by Item:
interface ItemSequence extends Items
{
enumerators
//* apply block in reverse order
void enumBack( UnaryProcedure aBlock );
//* apply pairs to block.enum( at( n ), at( n + 1 ) )
void enumPairs( BinaryProcedure aBlock );
//* detect last item for block.is( eachItem )
Object detectLast( UnaryPredicate aBlock );
//* detect first Index for block.is( eachItem )
Index atFirst( BinaryPredicate aBlock );
//* detect last Index for block.is( eachItem )
Index atLast( BinaryPredicate aBlock );
binary blocks for index,item pairs
//* Like enum but for index and item
void withIndexEnum( BinaryProcedure aBlock );
//* detect Index for block.is( eachIndex, eachItem )
Index withIndexDetect( BinaryPredicate aBlock );
//* detect last Index for block.is( eachIndex, eachItem )
Index withIndexDetectLast( BinaryPredicate aBlock );
}
That's the basic set of enumerators (i.e. InternalIterators) I use. All of these work for most anything I would ever want to do in an abstract data type whether that be a List, Array, Sorted List, Set, Bag, Dictionary, whatever. I haven't had an instance for a long time where I felt I needed to code a for...next or iter.next() while loop by hand.
Compositors and Binders
Here is where we start to attack my second reason for this package - expression composition. I have a desire to use these interfaces as more than just simple blocks or anonymous inners. For example, I would like to be able to use them as objects each of which can represent a composable chunk of logic, I would also like to be able to aggregate them into efficient expressions. For this, I did go to the work of Alexander Stepanov and David R. Musser (see: STL functors). This approach seemed much simpler and more intuitive to me than the InterpreterPattern, but your mileage may vary. The STL constructs allow me to create executable logic without having to create new specializations. These could then be used in a variety of ways. While it is usually easier to simply create an anonymous inner that implements one of the interfaces for in-code use, the composable functors are great for something like a Rule Language whose bits and pieces of logic can be visually arranged into expressions that can be persisted and executed.
Toward this end, I wanted to be able to create generic constructs such as the following:
UnaryPredicate inRange =
new BinaryCompose(
new And(),
new BinderSecond(
new Greater(),
new Long(00) ),
new BinderSecond(
new Less(),
new Long(11) ) ) );
This object can then be passed around as a unary predicate that checks to see if some variable is within the range [1,11) (i.e. [1,10]). Now that it is in object form, it can be used as an assertions like so:
public void foo( Long value )
{
Dbg.assert( inRange.is( value ) );
.
.
.
}
Or with something more complex like a detect iterator to find the first element in a collection of Long objects that is in the specified range:
Long item = (Long)numbers.detect( inRange );Of course, if this is a one time thing, you can simply do the following:
Long item = (Long)
numbers.detect( new UnaryPredicate() {
public boolean is( Object each ) {
long value = ((Long)each).longValue();
return value > 0 && value < 11; } } );
The only problem with this is that it requires a priori knowledge about the logic and does not allow that logic to be dynamically composed such as by a user using a visual logic builder. If you are not familiar with STL, BinaryCompose aggregates a Binary Predicate with two Unary Predicates into a single Unary Predicate. For example, if "bp" is the binary predicate with "up1" and "up2" as unary predicates, BinaryCompose can be used to create "bc" such that:
bc.is( value );is the same as evaluating:
bp.is( up1.is( value ), up2.is( value ) );The Binder predicates bind the first or second argument of a Binary Predicate so that it acts as a Unary Predicate. So, a Binary Predicate such as Equals can have one of its arguments bound like so:
UnaryPredicate equalsJohn =
new BinderFirst( new Equals(), "John" );
Dbg.assert( equalsJohn.is( sName ) );
This is the same as saying:
BinaryPredicate equal = new Equals();If you are interested in this stuff, I suggest you read the link I placed in this section on programming with generic algorithms. It's interesting stuff and was implemented in Ada before it ever showed up in C++.Dbg.assert( equals.is( "John", sName ) );
Concrete Building Blocks
Before we can create the classes that adapt and compose functors into expressions, we have to define the building blocks they work on. These are the atomic unary and binary building blocks we all use in expressions. We know them very well, relational (>,<), equality (==,!=), conditional (and,or), arithmetic (*,/,+,-,%), and so on. These are extraordinarily easy to implement so I will just show enough here to get you going. In this document, I am only going to cover what I call the logical operators -- i.e. relational, equality, and conditional.
While it may not be a perfect name, I will first create two classes - UnaryLogicalFunctor and BinaryLogicalFunctor. These classes allow the logical operators to be called either as Functions (ala UnaryFunction) returning a Boolean object or as Predicates (ala UnaryPredicate) returning a boolean primitive. For example, a binary Equal FunctorObject can then be used in the following ways:
BinaryFunction equal = new Equal();
Boolean b = (Boolean)equal.eval( new Long(1), new Long(1) );
BinaryPredicate equal = new Equal();
boolean isEqual = equal.is( new Long(1), new Long(1) );
Maybe the abstract class that Equal implements might be better named BinaryPredicateFunction, but BinaryLogicalFunctor seemed more appropriate at the time.
Because Java does not have generic types or variants that do not require casts, this feature (calling logical operators as functions or predicates) becomes very important in RealWorld scenarios such as when relational and arithmetic FunctorObjects are composed together. I suppose I could have just eliminated the predicates altogether, but they are so elegant and straightforward (and used often enough) that I figured the simpler interface was worth the more complicated implementation (see: the MIT approach versus the New Jersey approach).
The two logical functor classes have only one purpose - mapping between predicate usage and function usage. Note that these abstract classes would not be required by something like arithmetic operators that should always be implemented as functions.
public
abstract
class BinaryLogicalFunctor
implements BinaryPredicate,
BinaryFunction
{
//* Subclass must implement
abstract
public boolean is( Object arg1, Object arg2 );
//* Call predicate interface and map to object result
public Object eval( Object arg1, Object arg2 )
{
return
is( arg1, arg2 )
? Boolean.TRUE
: Boolean.FALSE;
}
}
public
abstract
class UnaryLogicalFunctor
implements UnaryPredicate,
UnaryFunction
{
//* Subclass must implement
abstract
public boolean is( Object arg );
//* Call predicate interface and map to object result
public Object eval( Object arg )
{
return
is( arg )
? Boolean.TRUE
: Boolean.FALSE;
}
}
That's all there is to 'em. Now, lets dig into some concrete classes that build on these abstract classes. These are the classes one would most often use when constructing constraints.
Conditional: And
#package com.tripwire.rdifalco.ast;final public class And extends BinaryLogicalFunctor { public boolean is( Object arg1, Object arg2 ) { return ((Boolean)arg1).booleanValue() && ((Boolean)arg2).booleanValue(); } }
Conditional: Or
#package com.tripwire.rdifalco.ast;final public class Or extends BinaryLogicalFunctor { public boolean is( Object arg1, Object arg2 ) { return ((Boolean)arg1).booleanValue() || ((Boolean)arg2).booleanValue(); } }
Equality: Value
#package com.tripwire.rdifalco.ast;final public class Equals extends BinaryLogicalFunctor { public boolean is( Object arg1, Object arg2 ) { return arg1.equals( arg2 ); } }
Equality: Reference
#package com.tripwire.rdifalco.ast;final public class Same extends BinaryLogicalFunctor { public boolean is( Object arg1, Object arg2 ) { return arg1 == arg2; } }
Relational: Less
#package com.tripwire.rdifalco.ast;final public class Less extends BinaryLogicalFunctor { public boolean is( Object arg1, Object arg2 ) { return ((Comparable)arg1).compareTo( arg2 ) < 0; } }
Relational: Greater
#package com.tripwire.rdifalco.ast;final public class Greater extends BinaryLogicalFunctor { public boolean is( Object arg1, Object arg2 ) { return ((Comparable)arg1).compareTo( arg2 ) > 0; } }
Logical: Not
#package com.tripwire.rdifalco.ast;You get the idea. Please note that I define these building block operators as final classes. You may not like this restriction. My rationale is that one cannot extend the implementation of And or Equals. If one needs a specialized And (whatever that may be), one should simply implement a new BinaryLogicalFunctor. However, this detail is up to you and is not a major issue in the design of the AST package.final public class Not extends UnaryLogicalFunctor { public boolean is( Object arg ) { return ((Boolean)arg).booleanValue() == false; } }
Implementing Composers and Binders in Java
We can use this as is. However, if we really want to be able to dynamic construct expressions without writing code, we will need some adaptors that will help us construct these bits into expressions. In this document, I am going to show two specific types of adaptors -- Composers and Binders. The compositors take two functions and chains them together, as if to curry them. As with everything else, they come in Unary and Binary flavors.
The first is called BinaryCompose. It is a unary functor that uses a binary functor to evaluate two unary functors. Think of a simple range constraint checker:
UnaryPredicate inRange =
new BinaryCompose( new And(),
new UnaryPredicate() {
public boolean is( Object arg ) {
return ((Long)arg).longValue() >= LONG_START; } },
new UnaryPredicate() {
public boolean is( Object arg ) {
return ((Long)arg).longValue() < LONG_END; } } );
Dbg.assert( inRange.is( new Long( 10 ) ) );
The name is misleading, while it does perform a binary compose, it actually instantiates unary FunctorObjects. In this example, we are still not free from writing code since we had to bind the second arguments of the range check manually as well as some other binary compositions.
If we were to really pick this expression apart, we could see that we are currying 5 FunctorObjects, all of which are logical binary operations.
Once we go over binders we will come back to this example and see how we can eliminate all manual coding from this expression object. In other words, have a completely dynamic system to create something like the Visual Rule Builder or Visual Constraint Builder we talked about earlier. For now, here is the implementation of the compositors.
BinaryCompose Implementation
package com.tripwire.rdifalco.ast;public class BinaryCompose extends UnaryLogicalFunctor { /// Implementation.
private BinaryPredicate m_binary; // is( unaryL.is, unaryR.is ) private UnaryPredicate m_unaryL; private UnaryPredicate m_unaryR;
/// Interface.
/** * @param binary Any subclass of <code>BinaryPredicate</code> called in * response to is with the result of <code>unaryL</code> and * <code>unaryR</code>. * @param unaryL A subclass of <code>UnaryPredicate</code> whose result * will be used as the first argument to <code>binary</code> * when evaluating <code>is</code>. * @param unaryR A subclass of <code>UnaryPredicate</code> whose result * will be used as the second argument to <code>binary</code> * when evaluating <code>is</code>. */ public BinaryCompose( BinaryPredicate binary, UnaryPredicate unaryL, UnaryPredicate unaryR ) { m_binary = binary; m_unaryL = unaryL; m_unaryR = unaryR; }
/** * @param arg The value is sent the member <code>is</code> of the two * unary predicate sent to the constructor. * @returns A boolean value equivalent to evaluating:<p> * <code> bResult = binary.is( unaryL.is( arg ), unaryR.is( arg ) );</code> */ final public boolean is( Object arg ) { return // NOTE: arguments must be objects!! m_binary.is( m_unaryL.is( arg ) ? Boolean.TRUE : Boolean.FALSE, m_unaryR.is( arg ) ? Boolean.TRUE : Boolean.FALSE ); }
//..Some convenient factory methods
//* And two unary predicates static final BinaryCompose and( UnaryPredicate u1, UnaryPredicate u2 ) { return new BinaryCompose( new And(), u1, u2 ); }
//* Or two unary predicates static final BinaryCompose or( UnaryPredicate p1, UnaryPredicate p2 ) { return new BinaryCompose( new Or(), p1, p2 ); }
//* Create half-open range constraints static final BinaryCompose inRange( Comparable start, Comparable end ) { return BinaryCompose.and( BinaryCompose.or( new BinderSecond( new Greater(), start ), new BinderSecond( new Equals(), start ) ), new BinderSecond( new Less(), end ) ); } }
UnaryCompose Implementation
Just like Binary Compose but for two Unary Functors.
#package com.tripwire.rdifalco.ast;public class UnaryCompose extends UnaryLogicalFunctor { /// Implementation.
private UnaryPredicate m_pred1; private UnaryPredicate m_pred2;
/// Interface.
public UnaryCompose( UnaryPredicate pred1, UnaryPredicate pred2 ) { m_pred1 = pred1; m_pred2 = pred2; }
final public boolean is( Object arg ) { return // Convert boolean to Boolean m_pred1.is( m_pred2.is( arg ) ? Boolean.TRUE : Boolean.FALSE ); }
//..Factor Methods
//* compose negation public static UnaryCompose not( UnaryPredicate pred ) { return new UnaryCompose( new Not(), pred ); } }
AbstractBinder Implementation
This helps us build the two other binders.
#package com.tripwire.rdifalco.ast;public abstract class AbstractBinder extends UnaryLogicalFunctor { private BinaryPredicate m_predicate; // Binary Predicate private Object m_bound; // Bound Value
//..State
final public boolean isBound() { return m_bound != null; }
//..Bind Values
/** Rebind the l-value */ final public void bind( Object arg ) { m_bound = arg; }
/** Readapt this instance to a new binary predicate */ final public void adapt( BinaryPredicate pred ) { m_predicate = pred; }
/// Implementation
final protected boolean doIsAsFirst( Object arg ) { return m_predicate.is( arg, m_bound ); }
final protected boolean doIsAsSecond( Object arg ) { return m_predicate.is( m_bound, arg ); } }
BinderFirst Implementation
public
class BinderFirst
extends AbstractBinder
{
//..Constructors
public BinderFirst( BinaryPredicate predicate )
{
this( predicate, null );
}
public BinderFirst( BinaryPredicate predicate, Object arg1 )
{
super.adapt( predicate );
super.bind( arg1 );
}
//..UnaryPredicate Responsibility
/**
* Evaluates the specified argument agains the bound argument using
* the currently adapted predicate.
*/
public boolean is( Object arg2 )
{
return super.doIsAsSecond( arg2 );
}
}
BinderSecond Implementation
public
class BinderSecond
extends AbstractBinder
{
//..Constructors
public BinderSecond( BinaryPredicate pred )
{
this( pred, null );
}
public BinderFirst( BinaryPredicate pred, Object arg2 )
{
super.adapt( pred );
super.bind( arg2 );
}
//..UnaryPredicate Responsibility
/**
* Evaluates the specified argument against the bound argument using
* the currently adapted predicate.
*/
public boolean is( Object arg1 )
{
return super.doIsAsFirst( arg1 );
}
}
Putting It All Together revisit example...
UnaryPredicate inRange =
new BinaryCompose( new And(),
new UnaryPredicate() {
public boolean is( Object arg ) {
return ((Long)arg).longValue() >= LONG_START; } },
new UnaryPredicate() {
public boolean is( Object arg ) {
return ((Long)arg).longValue() < LONG_END; } } );
Build up expression dynamically, no anonymous-inners, no Java code, just instantiate objects and have inputs and outputs...
break-down from binder and composer section...
Discussion and Suggestions:
Very elegant! I implemented something similar (but simpler) for evolving programs with strongly typed sexual reproduction (aka crossover) in both Java and C++. However, my system was a much more basic use of the Interpreter pattern and didn't include curried functions.
One thing I included in my library was type safety. The Java version had reflective capabilities that could be used to ensure type safety when built in to the AST; each function or predicate had a method for querying the Class of the returned value and arguments. The C++ version used templates to ensure type safety at compile time. Have you considered type safety in your libary?
Finally, are you planning to release this to the public? -- NatPryce
Nat, thanks. About type-safety, I've thought about it a bit. One part of me would like to add it explicitly while another part would like the ast package to be a foundation that one could construct a type-safety solution on top of (if needed for their solution domain). I do use some simple error checking in my implementation to ensure, for example, that the Object returned by a Function is a Boolean before retrieving its booleanValue in a Predicate. As you know, this sort of thing is much cleaner with C++ templates. I also started a GJ implementation and that was a joy. However, in actual use I was surprised at how sufficient a job the Java VM did of reporting type problems with un-checked exceptions. While that may be fine in some applications, it wont be in others.
I would like to release it publicly. In a way I have here. -- RobertDiFalco
As for releasing the package, how about setting up a SourceForge project? -- NatPryce
I finally got around to reading this page, and I am very impressed with the whole presentation. I've wanted something like this in the past - but I didn't have a clear idea as to what kind of infrastructure would work well, and at the time the desire didn't seem strong enough to warrant the work. Please do consider making the package itself available somewhere, and also register my interest in your abstract data types package. -- Brett Neumeier
Very Cool. The thought just occurred to me that I should atleast learn Smalltalk so I will know what is missing in Java. -- Venu Thachappilly
Wow. I am very impressed. This has given me a lot to think about. I get the gist from the text and code examples, however I've become stuck trying to actually code an InternalIterator of my own. I would be very grateful if you would publish the AST and ADT packages for others to use and learn from. -- EricHerman
A few of years later, I'm amazed that there was a time when the subject matter seemed at the edge of my understanding. I use blocks "all the time" now, and this page really changed the way I program in Java and thus gave me a window into understanding some of what is so nice about the way some other languages (Ruby, Smalltalk) handle blocks so nicely. This page will remain a wiki clasic for me. -- EricHerman
Robert, this is great stuff. Really elegant code. Writing interpreters for predicate trees in java is no fun at all, but this helps take the pain. I really miss prolog for this, but I may have learn some smalltalk now :-) Are you still thinking about making these packages (ast, adt) available? -- BillDehora
Robert, I am too lazy to assemble this document into Java source. You should put this on sourceforge soon. It would really be a significant contribution. -- ThomasEnebo
Using this document I've written my own version of these interfaces and classes in about three hours. I didn't go all the way with re-writing the Java collections; I'm using a static utility-type class to encapsulate the iterator mess but it works well and maybe sometime in the future I'll rework the collections for performance. Overall, this is a fantastic page and Robert did a great job summing up his work. Much appreciated, Robert. -- JeffPanici
Fantastic stuff. Unfortunately the ItemSequence interface flew completely over my head. How would one go about using that? I keep seeing Index as an STL iterator, which is probably not what it is at all. Could anyone who understands ItemSequence put up a code snippet that would show it's use, please? -- JonThoroddsen
I keep coming back to this, and I do like it; even though it illustrates the poverty of a language which cannot generate its own code and run it. I was wondering about whether it was worth adding parenthesis? I may be missing something in my partially grokked state, of course. -- RichardHenderson.
Binders are essentially parenthesis. -- RobertDiFalco
I have a project in SourceForge that is attempting to cover much the same ground. Look at http://jga.sf.net/ (JavaGenericAlgorithms)
There is also an apache project that seems to be working in the same conceptual area (I just found it today, myself). The apache project is http://jakarta.apache.org/commons/sandbox/functor/
-- DavidHall
For yet-another-set-of-functor-interfaces, these ones with java 1.5 generics and varargs, see http://www.dishevelled.org/functor -- MichaelHeuer
For those who would prefer true syntax and types for blocks and who can afford to use a Java extension instead of Java itself, you should look at the NiceLanguage. -- DanielBonniot
Building on RobertDiFalco's work, I have been using a couple of classes with some success. Admittedly, they do not achieve the performance gains of rewriting collections, but they work well and are conceptually simple. Both classes are wrappers for the existing java interfaces. -- AnonymousDonor
public class InternalIterator
{
private Iterator at;
// constructor
public InternalIterator( Iterator at )
{
this.at = at;
}
//* eval block for each
public void enum( UnaryProcedure aBlock )
{
while ( at.hasNext() )
aBlock.run( at.next() );
}
//* increment count for each true
public int count( UnaryPredicate aBlock )
{
int count = 0;
while ( at.hasNext() )
if (aBlock.is( at.next() ))
count++;
return count;
}
//* remove item for each block that answer true
public void remove( UnaryPredicate aBlock )
{
while ( at.hasNext() )
if ( aBlock.is( at.next() ) )
at.remove();
}
//* detect first for block answers true
public Object detect( UnaryPredicate aBlock )
{
while ( at.hasNext() )
{
Object each = at.next();
if ( aBlock.is( each ) )
return each;
}
return null;
}
//* inject value into block with each item
public Object inject( Object value, BinaryFunction aBlock )
{
Object nextValue = value;
while ( at.hasNext() )
nextValue = aBlock.eval( nextValue, at.next() );
return nextValue;
}
//* answer new collection for each true
public Collection select( UnaryPredicate aBlock )
{
Collection result = new ArrayList();
while ( at.hasNext() )
{
Object each = at.next();
if (aBlock.is( each ))
result.add( each );
}
return result;
}
//* answer new collection for each false
public Collection reject( UnaryPredicate aBlock )
{
Collection result = new ArrayList();
while ( at.hasNext() )
{
Object each = at.next();
if (!aBlock.is( each ))
result.add( each );
}
return result;
}
//* answer new collection of non-null results
public Collection collect( UnaryFunction aBlock )
{
Collection result = new ArrayList();
while ( at.hasNext() )
{
Object each = aBlock.eval( at.next() );
if (each != null)
result.add( each );
}
return result;
}
}
public class AstCollection
implements Collection
{
private Collection m_items;
//* constructor
public AstCollection( Collection items )
{
m_items = items;
}
//* eval block for each
public void enum( UnaryProcedure aBlock )
{
getInternalIterator().enum( aBlock );
}
//* increment count for each true
public int count( UnaryPredicate aBlock )
{
return getInternalIterator().count( aBlock );
}
//* remove item for each block that answer true
public void remove( UnaryPredicate aBlock )
{
getInternalIterator().remove( aBlock );
}
//* detect first for block answers true
public Object detect( UnaryPredicate aBlock )
{
return getInternalIterator().detect( aBlock );
}
//* inject value into block with each item
public Object inject( Object value, BinaryFunction aBlock )
{
return getInternalIterator().inject( value, aBlock );
}
//* answer new collection for each true
public Collection select( UnaryPredicate aBlock )
{
return getInternalIterator().select( aBlock );
}
//* answer new collection for each false
public Collection reject( UnaryPredicate aBlock )
{
return getInternalIterator().reject( aBlock );
}
//* answer new collection of non-null results
public Collection collect( UnaryFunction aBlock )
{
return getInternalIterator().collect( aBlock );
}
//* wrap an Iterator with InternalIterator
private InternalIterator getInternalIterator()
{
return new InternalIterator( iterator() );
}
/* (non-Javadoc)
* @see java.util.Collection#add(java.lang.Object)
*/
public boolean add( Object o )
{
return m_items.add( o );
}
/* (non-Javadoc)
* @see java.util.Collection#addAll(java.util.Collection)
*/
public boolean addAll( Collection c )
{
return m_items.addAll( c );
}
/* (non-Javadoc)
* @see java.util.Collection#clear()
*/
public void clear()
{
m_items.clear();
}
/* (non-Javadoc)
* @see java.util.Collection#contains(java.lang.Object)
*/
public boolean contains( Object o )
{
return m_items.contains( o );
}
/* (non-Javadoc)
* @see java.util.Collection#containsAll(java.util.Collection)
*/
public boolean containsAll( Collection c )
{
return m_items.containsAll( c );
}
/* (non-Javadoc)
* @see java.util.Collection#isEmpty()
*/
public boolean isEmpty()
{
return m_items.isEmpty();
}
/* (non-Javadoc)
* @see java.util.Collection#iterator()
*/
public Iterator iterator()
{
return m_items.iterator();
}
/* (non-Javadoc)
* @see java.util.Collection#remove(java.lang.Object)
*/
public boolean remove( Object o )
{
return m_items.remove( o );
}
/* (non-Javadoc)
* @see java.util.Collection#removeAll(java.util.Collection)
*/
public boolean removeAll( Collection c )
{
return m_items.removeAll( c );
}
/* (non-Javadoc)
* @see java.util.Collection#retainAll(java.util.Collection)
*/
public boolean retainAll( Collection c )
{
return m_items.retainAll( c );
}
/* (non-Javadoc)
* @see java.util.Collection#toArray()
*/
public Object[] toArray()
{
return m_items.toArray();
}
/* (non-Javadoc)
* @see java.util.Collection#toArray(java.lang.Object[])
*/
public Object[] toArray( Object[] a )
{
return m_items.toArray( a );
}
/* (non-Javadoc)
* @see java.util.Collection#size()
*/
public int size()
{
return m_items.size();
}
}
From the above code... me thinks someone's been looking at SmallTalk's collection hierarchy, I say that because I HaveThisPattern, and wrote something similar for my own collections.
This page mirrored in JavaIdioms as of April 29, 2006