Alexander Sakharov
 
     
 
Recursive Data Types in Java

Download source code

I am trying to raise awareness about having standard facilities for processing recursive data types in Java. Many solutions to the issue of supporting recursive types have been proposed for different languages but none of them have been standardized in any major imperative language. Facilities of this kind are particularly helpful for symbolic computations and for compilation programs. I sent a proposal to Sun Microsystems, Inc. about possible inclusion of classes for handling recursive data types in the java.util package. Also, my letter on this issue is published in the December 1998 issue of SIGPLAN Notices. Source code is available for download.
 

Overview

Support for recursive types in Java is described here. Recursive types are classes containing members of the same type. Data of recursive types are usually viewed as directed graphs. Each class object represents a node in a graph as well as a subgraph rooted at this node. Most of cyclic graphs representing recursive data types contain cycles because of backward references. It means that most of cyclic graphs are essentially acyclic graphs or even trees and are treated as such in programs.

There is an abstract class for representing trees (Tree) and an abstract class for representing rooted acyclic graphs (DAG). (Note that class DAG was named Graph in the SIGPLAN Notices letter.) Classes Tree and DAG provide methods to store and update references to children. These classes provide random access to immediate children of each node. Every object of class Tree holds the parent of the node. Objects of class DAG have a reference to the root instead of the parent. Two methods in each class are abstract and should be defined in a derived class. Classes Tree and Graph contain methods implementing substitutions in graphs, graph comparison and pattern matching. Special terminal nodes called slots are placeholders that are matched against graphs.

Unlike collection implementation, iterators for trees and rooted acyclic graphs are classes, not interfaces. All iterator functionality (that is pretty complex compared to collection iteration) is pre-implemented. Users do not have to write their own code supporting graph iteration, which is also called traversal. Several traversal orders are implemented for iteration over graph nodes. Fail-fast iteration is not currently supported, but can be easily added.

The classes Tree and DAG depend on few properties of their iterator classes. Similarly to the C++ STL, these classes are deliberately de-coupled from their iterators. Here are iterator requirements:

 
Documentation

Class Tree

Class TreeIterator
 
Class DAG

Class DAGIterator
 
Note that this documentation has not been edited after its generation with javadoc. Some .gif files and links are not made available in the two aforementioned documents..
 

Sample Class
import graph.*;

public class Expression extends Tree implements Cloneable {
        
        public String tag;

public Expression() {
        tag="";
}

public Expression(String s) {
        tag=s;
}

public Expression(Expression left, String s, Expression right) {
        tag=s;
        embed(left,1);
        embed(right,2);
}

public Expression(Expression e) {
        tag="";
        slot(e);
}

public boolean nodeEqual(Tree q) { 
        if ( !tag.equals(((Expression)q).tag) )
                return false;
        return true;
}

public Tree nodeCopy() { 
        Expression e;
        e = new Expression();
        e.tag=tag;
        return e;
}

}
Example of Usage
import graph.*;
import java.io.*;

public class Sample {

public static void main( String args[] ) throws IOException { 
        Expression expr;
        int index;
        Expression temp;
        boolean flag;
        int i;
        int m; 
        double number;
        String identifier;
        TreeIterator trace;
        Expression current;

        // Rewriting rules
        Expression x = new Expression();
        Expression lhs[] = new Expression[4];
        Expression rhs[] = new Expression[4];

        lhs[0] = new Expression(new Expression(x),"+",new Expression("0.0"));
        rhs[0] = new Expression(x);

        lhs[1] = new Expression(new Expression(x),"-",new Expression("0.0"));
        rhs[1] = new Expression(x);

        lhs[2] = new Expression(new Expression(x),"-",new Expression(x));
        rhs[2] = new Expression("0.0");

        lhs[3] = new Expression(new Expression("0.0"),"+",new Expression(x));
        rhs[3] = new Expression(x);

if (args.length!=2){
        System.out.println("Should be two files as parameters");
        return; 
}

try {

        FileInputStream inStream = new FileInputStream(args[0]);
        Reader reader = new BufferedReader(new InputStreamReader(inStream));
        StreamTokenizer input = new StreamTokenizer(reader);

        FileOutputStream outStream = new FileOutputStream(args[1]);
        PrintWriter outFile = new PrintWriter(outStream,true);

        expr = new Expression();
        trace = expr.iterator();

        m=input.nextToken();
        current=(Expression)(trace.allorder());
        current.tag="";

        for ( ; m!=StreamTokenizer.TT_EOF && m!='/'; m=input.nextToken() ) {
                if ( m==StreamTokenizer.TT_EOL ) 
                        continue;
                if ( current.isLeaf() )
                        index=1;
                else
                        index=current.lastIndex()+1;
                if ( m==StreamTokenizer.TT_NUMBER ) {
                        number=(int)input.nval;
                        temp=new Expression();
                        temp.tag=String.valueOf(number);
                        current.embed(temp,index);
                        current=(Expression)(trace.allorder());
                        current=(Expression)(trace.allorder());
                } else if ( m==StreamTokenizer.TT_WORD ) {
                        identifier=input.sval;
                        temp=new Expression();
                        temp.tag=identifier;
                        current.embed(temp,index);
                        current=(Expression)(trace.allorder());
                        current=(Expression)(trace.allorder());
                } else {
                        if ( m=='(' ) {
                                temp=new Expression();
                                temp.tag="";
                                current.embed(temp,index);
                                current=(Expression)(trace.allorder());
                        } else if ( m==')' ) {
                                current=(Expression)trace.allorder();
                        } else {
                                current.tag=String.valueOf((char)m);
                        }
                }
        }

        // Print original expression
        trace = expr.iterator();
        while ( (current=(Expression)(trace.allorder()))!=null ) {
                if ( current.isLeaf() ) 
                        outFile.print( current.tag + " ");
                if ( !current.isLeaf() && trace.visit()==1 )
                        outFile.print("( ");
                if ( !current.isLeaf() && trace.visit()>1 && !trace.isPost() )
                        outFile.print(current.tag + " ");
                if ( !current.isLeaf() && trace.isPost() )
                        outFile.print(") ");
        } 
        outFile.println("");

        // Rewriting loop
        do {
                trace=expr.iterator();
                flag=false;
                while ( (current=(Expression)(trace.postorder()))!=null ) {
                        for(i=0;i<lhs.length;i++) { 
                                if ( lhs[i].match(current) ){
                                        if ( current==expr ) 
                                                expr=(Expression)rhs[i].instantiate();                                  
                                        else
                                                current.substituteCopy(rhs[i].instantiate());
                                        flag=true;
                                        break;
                                }
                                lhs[i].clean();

                                rhs[i].clean();
                        }
                }
        } while ( flag );

        // Print transformed expression
        trace = expr.iterator();
        while ( (current=(Expression)(trace.allorder()))!=null ) {
                if ( current.isLeaf() ) 
                        outFile.print( current.tag + " ");
                if ( !current.isLeaf() && trace.visit()==1 )
                        outFile.print("( ");
                if ( !current.isLeaf() && trace.visit()>1 && !trace.isPost() )
                        outFile.print(current.tag + " ");
                if ( !current.isLeaf() && trace.isPost() )
                        outFile.print(") ");
        } 
        outFile.println(""); 

        inStream.close();
        outStream.close();

} catch(IOException iofailure) {
        System.out.println("I/O Error"); 
}

}

}
Sample Computation
Input:
( ( a + ( b + 0.0 ) ) - ( ( c - 0.0 ) - ( c + 0.0 ) ) )
Output:
( a + b )

 

Copyright 1998 Alexander Sakharov

Need to relax? Try brain teasers. I would recommend those marked 'cool'.