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 HigherOrderFunction''''''s and FunctorObject''''''s 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 FunctorObject''''''s using ''function objects''. In Java, we can enclose a lexical unit of code within an Object with AnonymousInnerClass''''''es. 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 Summing''''''Visitor() );
In this example, the tree accepts a visitor that will sum each of its elements. In this scenario, the ''Summing''''''Visitor'' 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 FunctorObject''''''s, I do provide some example implementations for HigherOrderFunction''''''s 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 FunctionObject''''''s 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'':

 B''''''inaryPredicate aBlock = new B''''''inaryPredicate() {
     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 ''B''''''inaryPredicate''. 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'':

 B''''''inaryPredicate 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:

	0. The basic interfaces
	0. The ''fundamental-operator'' classes that implement these interfaces
	0. 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 AnonymousInnerClass''''''es. In fact, you are probably doing this already if you write Swing applications. For example, consider the following use of ''W''''''indowAdapter''. 

 addWindowListener( 
     new ''W''''''indowAdapter''() {
         public void windowClosing( W''''''indowEvent e ) {
             System.exit(0); } } );
This '''specializes''' the ''W''''''indowAdapter'' interface using an AnonymousInnerClass. You can say that in the above example, the FunctorObject interface named ''W''''''indowAdapter'' 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 ''U''''''naryPredicate''. 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 '''U''''''naryPredicate'''() {
     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 ''U''''''naryPredicate'' interface:

 U''''''naryPredicate ''aBlock'' =
     new '''U''''''naryPredicate'''() {
         public boolean '''is'''( Object ''each'' ) {
             return ''each.equals( "some_name" )''; } } );
This really isn't that much different than:

 class E''''''qualsSomeName implements U''''''naryPredicate
 {
     public boolean '''is'''( Object ''each'' )
     {
         return ''each.equals( "some_name" )'';
     }
 }
 
 U''''''naryPredicate ''aBlock'' = new E''''''qualsSomeName();
We are just using an anonymous class name since we are never going to reuse this specialization of ''U''''''naryPredicate''. 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''( '''U''''''naryPredicate''' ''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 '''U''''''naryPredicate'''() {
     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 FunctorObject''''''s 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 U''''''naryPredicate 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 '''U''''''naryPredicate'''() {
             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 U''''''naryPredicate:
      final String second_argument = "some_name";
      '''U''''''naryPredicate''' ''aBlock'' =
          new B''''''inderSecond(
              new Equal(),
              second_argument ) );  ''// bind second argument of equals''
* Send the U''''''naryPredicate 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''. B''''''inderSecond 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 B''''''inderSecond implements U''''''naryPredicate
 {
     private B''''''inaryPredicate ''m_pred'';
     private Object          ''m_arg2'';
	 
     public B''''''inderSecond( B''''''inaryPredicate 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 ''U''''''naryPredicate'' 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 HigherOrderFunction''''''s used by AlexanderStepanov in STL and the Ada Generic Library.

----
RobertDiFalco
----
Prev: BlocksInJava
Next: BlocksInJavaAst
----