BlocksInJavaIntro

Prev: BlocksInJava Next: BlocksInJavaAst

---

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 );

 assert( aBlock.is( x, y ) );  // passes

 y = new Long( 11 );

 assert( aBlock.is( x, y ) );  // fails!!

The following example creates the same binary predicate using expression composition:

 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:

1. The basic interfaces
2. The fundamental-operator classes that implement these interfaces
3. Adapters used to compose the fundamental-operators into expressions

Layers two and three define the Abstract Syntax Tree and are used primarily for expression composition. To support serialization, each interface extends the java.io.Serializable marker interface. All the classes and interfaces are defined in a package called ast for Abstract Syntax Tree. However, before getting into the actual implementation, I'd like to explore expression specialization and expression composition a little further.

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:

• Convert Binary Expression to a UnaryPredicate:

      final String second_argument = "some_name";
      UnaryPredicate aBlock =
          new BinderSecond(
              new Equal(),
              second_argument ) );  // bind second argument of equals

• Send the UnaryPredicate to a HigherOrderFunction:

      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.

---

RobertDiFalco

---

Prev: BlocksInJava Next: BlocksInJavaAst

---