'. '

Talk:Closures

From APIDesign

(Difference between revisions)
Jump to: navigation, search
Line 473: Line 473:
/* My internal API implementation for moving FORWARD. */
/* My internal API implementation for moving FORWARD. */
-
private static class MoveFoward
+
private static final class MoveFoward
-
implements Move
+
extends Move
{
{
/* Get the sibling node in the implied movement direction. */
/* Get the sibling node in the implied movement direction. */
Line 490: Line 490:
/* My internal API implementation for moving BACKWARD. */
/* My internal API implementation for moving BACKWARD. */
-
private static class MoveBackward
+
private static final class MoveBackward
-
implements Move
+
extends Move
{
{
/* Get the sibling node in the implied movement direction. */
/* Get the sibling node in the implied movement direction. */
Line 507: Line 507:
/* My internal API implementation for moving TO_HEAD. */
/* My internal API implementation for moving TO_HEAD. */
-
private static class MoveToHead
+
private static final class MoveToHead
-
implements Move
+
extends Move
{
{
/* Get the sibling node in the implied movement direction. */
/* Get the sibling node in the implied movement direction. */
Line 527: Line 527:
/* My internal API implementation for moving TO_TAIL. */
/* My internal API implementation for moving TO_TAIL. */
-
private static class MoveToTail
+
private static final class MoveToTail
-
implements Move
+
extends Move
{
{
/* Get the sibling node in the implied movement direction. */
/* Get the sibling node in the implied movement direction. */

Revision as of 00:31, 7 February 2010

Hand-written Closures in Java

2010 February 6

I've seen very few "real world" examples in Java of how the closure paradigm eases object oriented design and programming. Java developers have used inner classes to implement closures. The current Java closure proposals are for enhancing the Java compiler to "re-write" source code that is decorated with syntactic sugar for closures. They each have their strengths and weaknesses, which I will not delve into here.

Essentially speaking, the proposals rely on variations of using the inner class mechanism and they allow the closure to read and write the local variables of the method in which the closure is instantiated.

The current Java language specification forbids an anonymous inner class from writing to the local variables and allows reading the final local variables that are definitely assigned before instantiation. This restriction is easily overcome by the Java compiler simply re-writing the source code to wrap the local variables in a nested static class. The class is instantiated and assigned to a final local variable and the reference is passed as an implied constructor parameter to the closure inner class. Everywhere that the local variables are referenced in the method and in the closure are replaced with the reference to the instance fields of the static class instance.

Original with "syntactic sugar" for the closure:

public class Fubar
{
    public int fubar()
    {
        int gork;
        int result;
 
        gork = 12;
        { int fred; :: {result = fred + gork * 2;} }.invoke(3);
 
        return result;
    }
}

In the above example, the closure syntax is { type Name1; type Name2; :: { closure_block } }

The closure block can accept zero or more formal parameters with type "type Name1" separated by semi-colon. The double colon "::" notation separates the formal parameters from the closure code block that is enclosed in braces. This is an important piece of syntax to tell the Java compiler that it is parsing a closure block, rather than an ordinary block.

The example has one formal parameter "int fred;", which receives the value 3 from the invocation ".invoke(3);".

Some closure proposals have the implied closure method returning an explicit result of the implied type of the last statement in the closure block. In my humble opinion, that is too much of a language change. I think most programmers could live quite comfortably with only implicit output variables and no explicit result.

If the closure code block refers to the local variables of the enclosing method, then the Java compiler also generates a static container class for those local variables and implicitly instantiates that class and passes the reference to the instantiated closure inner class as a constructor parameter. The Java compiler re-writes the source code for the closure block and for the enclosing method to refer the instance fields of the container class.

Logically re-written by the Java compiler:

public class Fubar
{
    private static class T5432
    {
        private int gork;
        private int result;
    }
 
    private class C6789
    {
        /* reference to "common" local variables. */
        private final T5432 t5432;
 
        /* constructor to receive the local variable container. */
        private C6789(T5432 theT5432)
        {
            t5432 = theT5432;
        }
 
        /* the closure method. */
        private void closure0(int fred)
        {
            t5432.result = fred + t5432.gork * 2;
        }
    }
 
    public int fubar()
    {
        /* instantiate the local variable container. */
        final T5432 t5432 = new T5432();
 
        /* instantiate the closure and invoke the method. */
        (new C6789(t5432)).closure0(3);
 
        /* return the result that was calculated by the closure. */
        return t5432.result;
    }
}

The compiler generates a static class for holding the "local variables" that are referenced by both the method and the closure. Then the compiler generates an inner class for the closure code methods. In the above example, there is one closure code method, but there could be several generated depending on the enclosing method fubar().

The class names are logically hidden from the original source code in a separate namespace, so there is never a name clash.

The above example is not a "real world" situation. It is a simple example of how the Java compiler may re-write the closure source code and conform to the current Java language specification with respect to the "final local variable" requirement and using an inner class to implement the closure block.

My "real world" example is about managing a group of doubly-linked lists and their nodes. The list and node API is custom and unrelated to the Java Collection API. The list is a "sentinel" list that has permanent fake nodes (i.e., "sentinels") for anchoring the head and tail. This design is for constant-time removal and insertion.

public interface Node
{
    /* Get the current LinkList that has this Node. */
    public abstract LinkList getLinkList();
 
    /* Is this a sentinel (fake) node? */
    public abstract boolean isSentinel();
 
    /* Remove this Node from its list. */
    public abstract void remove();
 
    /* Get the Node that is next in the list. */
    public abstract Node getNext();
 
    /* Get the Node that is previous in the list. */
    public abstract Node getPrev();
 
    /* Insert this node after the specified Node. */
    public abstract void insertAfter(Node theNode);
 
    /* Insert this node before the specified Node. */
    public abstract void insertBefore(Node theNode);
}
 
/*
 * I omit the LinkListStandard class implementation of the interface.
 * It is not needed for this example.
 */
public interface LinkList
{
    /* Get the Head node. */
    public abstract Node getHead();
 
    /* Get the Tail node. */
    public abstract Node getTail();
 
    /* Append the specified node to the tail of the list. */
    public abstract void append(Node theNode);
 
    /* Prepend the specified node to the head of the list. */
    public abstract void prepend(Node theNode);
}

My "original" design started with an array of LinkList to hold the group of lists, and several methods for managing the nodes on those lists. (I have simplified much of this example to focus on the key concepts.)

/* A selection code to pick a LinkList from an array. */
public Enum Select
{
    /* Select the Blue list. */
    BLUE,
 
    /* Select the Red List. */
    RED;
}
 
/* The original list manager class. */
public class ManageListsBySelect
{
    /* The array of LinkList. */
    private final LinkList[] linkLists;
 
    /* Construct the instance. */
    public ManageListsBySelect()
    {
        int blue = Select.BLUE.ordinal();
        int red  = Select.RED.ordinal();
 
        linkLists = new LinkList[2];
 
        //n.b.: The LinkListStandard is the concrete implementation
        // of the LinkList interface.
        linkLists[blue] = new LinkListStandard();
        linkLists[red]  = new LinkListStandard();
    }
 
    /* Add a Node. */
    public void add(Select theSelect, Node theNode)
    {
        LinkList linkList;
 
        if(null == theNode.getLinkList())
        {
            linkList = linkLists[theSelect.ordinal()];
            linkList.append(theNode);
        }
        else
        {
            throw new IllegalArgumentException();
        }
    }
 
    /* Remove the Node. */
    public void remove(Select theSelect, Node theNode)
    {
        LinkList linkList;
 
        linkList = linkLists[theSelect.ordinal()];
        if(linkList == theNode.getLinkList())
        {
            theNode.remove();
        }
        else
        {
            throw new IllegalArgumentException();
        }
    }
 
    /* Move the Node forward (towards the head) in its list. */
    public boolean moveForward(Select theSelect, Node theNode)
    {
        boolean result;
        Node sibling;
        LinkList linkList;
 
        linkList = linkLists[theSelect.ordinal()];
        if(linkList == theNode.getLinkList())
        {
            sibling = theNode.getPrev();
            if( (( result = !sibling.isSentinel() )) )
            {
                theNode.remove();
                theNode.insertBefore(sibling);
            }
        }
        else
        {
            throw new IllegalArgumentException();
        }
 
        return result;
    }
 
    /* Move the Node backward (towards the tail) in its list. */
    public boolean moveBackward(Select theSelect, Node theNode)
    {
        boolean result;
        Node sibling;
        LinkList linkList;
 
        linkList = linkLists[theSelect.ordinal()];
        if(linkList == theNode.getLinkList())
        {
            sibling = theNode.getNext();
            if( (( result = !sibling.isSentinel() )) )
            {
                theNode.remove();
                theNode.insertAfter(sibling);
            }
        }
        else
        {
            throw new IllegalArgumentException();
        }
 
        return result;
    }
 
    /* Move the Node to the head in its list. */
    public boolean moveToHead(Select theSelect, Node theNode)
    {
        boolean result;
        Node sibling;
        LinkList linkList;
 
        linkList = linkLists[theSelect.ordinal()];
        if(linkList == theNode.getLinkList())
        {
            sibling = theNode.getPrev();
            if( (( result = !sibling.isSentinel() )) )
            {
                theNode.remove();
                linkList.prepend(theNode);
            }
        }
        else
        {
            throw new IllegalArgumentException();
        }
 
        return result;
    }
 
    /* Move the Node to the tail in its list. */
    public boolean moveToTail(Select theSelect, Node theNode)
    {
        boolean result;
        Node sibling;
        LinkList linkList;
 
        linkList = linkLists[theSelect.ordinal()];
        if(linkList == theNode.getLinkList())
        {
            sibling = theNode.getNext();
            if( (( result = !sibling.isSentinel() )) )
            {
                theNode.remove();
                linkList.append(theNode);
            }
        }
        else
        {
            throw new IllegalArgumentException();
        }
 
        return result;
    }
}

You can see there are some problems with the original design. The two most important problems are:

1. The movement methods are nearly identical, but the subtle differences are embedded within the logic. This code is screaming for closures. In particular, the Node.getNext(), Node.getPrev(), Node.insertAfter(), Node.insertBefore(), LinkList.append(Node), and LinkList.prepend(Node) are peculiar to each movement method.

2. All of the methods have the same invariant parameter "theSelect" that specifies which LinkList to use. This screams for refactoring and API layering to allow for implicitly specifying which LinkList to use.

A little later in the design process, I needed to add a different selection mechanism for a matrix. That meant copy-and-pasting the original code and changing the explicit selection parameter to specify row and column Enum types. The methods' code were almost identical to the original, with only the change to the formal parameters for specifying which LinkList.

I need a forward-compatible design that can tolerate changing the selection mechanism. I need a closure design that can intersperse bits of code through-out the refactored code block that moves the Node.

I need a closure API that handles the Node.getNext() and Node.getPrev() as getSibling(Node). The closure simply "knows" whether to use the getNext() or the getPrev() method. The closure implicitly handles the Node.insertAfter(Node), Node.insertBefore(Node), LinkList.append(Node), and LinkList.prepend(Node) calls as appropriate for the particular kind of movement.

The movement methods all look very similar. The differences will be factored out as distinct closure API methods, so that there is one movement method that relies on the other implicit methods.

/*
 * Refactoring node movement into a closure API implies
 * performance improvements by indexing an array of
 * implementations.
 */
public Enum Movement
{
    /* Move the Node forward (towards the head) in its list. */
    FORWARD,
 
    /* Move the Node backward (towards the tail) in its list. */
    BACKWARD,
 
    /* Move the Node to the head in its list. */
    TO_HEAD,
 
    /* Move the Node to the tail in its list. */
    TO_TAIL;
}
 
/* My closure API for managing a Node in its LinkList. */
public interface LinkListClosure
{
    /*
     * Get the implied LinkList from the underlying
     * selection mechanism.
     */
    public abstract LinkList getLinkList();
 
    /* Add the Node to the implied LinkList. */
    public abstract void add(Node theNode);
 
    /* Remove the Node from the implied LinkList. */
    public abstract void remove(Node theNode);
 
    /* Move the Node in its implied LinkList. */
    public abstract boolean move(Node theNode, Movement theMovement);
 
    /* Move the Node forward (towards the head) in its list. */
    public abstract boolean moveForward(Node theNode);
 
    /* Move the Node backward (towards the tail) in its list. */
    public abstract boolean moveBackward(Node theNode);
 
    /* Move the Node to the head in its list. */
    public abstract boolean moveToHead(Node theNode);
 
    /* Move the Node to the tail in its list. */
    public abstract boolean moveToTail(Node theNode);
}
 
/* My partial API implementation of the closure. */
public abstract class LinkListClosureAbstract
implements LinkListClosure
{
    /*
     * My internal movement API. This is where the various
     * bits of code are semantically declared for use by
     * the move(Node) method.
     */
    private static abstract class Move
    {
        /* Get the sibling node in the implied movement direction. */
        protected abstract Node getSibling(Node theNode);
 
        /* Insert the specified node relative to the sibling node. */
        protected abstract void insert(Node theNode, Node theSibling);
 
        /* Move the Node. */
        private boolean move(Node theNode)
        {
            boolean result;
            Node sibling;
 
            sibling = getSibling(theNode);
            if( (( result = !sibling.isSentinel() )) )
            {
                theNode.remove();
                insert(theNode,sibling);
            }
 
            return result;
        }
    }
 
    /* My internal API implementation for moving FORWARD. */
    private static final class MoveFoward
    extends Move
    {
        /* Get the sibling node in the implied movement direction. */
        protected Node getSibling(Node theNode)
        {
            return theNode.getPrev();
        }
 
        /* Insert the specified node relative to the sibling node. */
        protected void insert(Node theNode, Node theSibling)
        {
            theNode.insertBefore(theSibling);
        }
    }
 
    /* My internal API implementation for moving BACKWARD. */
    private static final class MoveBackward
    extends Move
    {
        /* Get the sibling node in the implied movement direction. */
        protected Node getSibling(Node theNode)
        {
            return theNode.getNext();
        }
 
        /* Insert the specified node relative to the sibling node. */
        protected void insert(Node theNode, Node theSibling)
        {
            theNode.insertAfter(theSibling);
        }
    }
 
    /* My internal API implementation for moving TO_HEAD. */
    private static final class MoveToHead
    extends Move
    {
        /* Get the sibling node in the implied movement direction. */
        protected Node getSibling(Node theNode)
        {
            return theNode.getPrev();
        }
 
        /* Insert the specified node relative to the sibling node. */
        protected void insert(Node theNode, Node theSibling)
        {
            LinkList linkList;
 
            linkList = theSibling.getLinkList();
            linkList.prepend(theNode);
        }
    }
 
    /* My internal API implementation for moving TO_TAIL. */
    private static final class MoveToTail
    extends Move
    {
        /* Get the sibling node in the implied movement direction. */
        protected Node getSibling(Node theNode)
        {
            return theNode.getNext();
        }
 
        /* Insert the specified node relative to the sibling node. */
        protected void insert(Node theNode, Node theSibling)
        {
            LinkList linkList;
 
            linkList = theSibling.getLinkList();
            linkList.append(theNode);
        }
    }
 
    /* My array of internal movement API references. */
    private static final Move[] moves;
 
    static
    {
        moves = new Move[4];
        moves[Movement.FORWARD.ordinal()]  = new MoveForward();
        moves[Movement.BACKWARD.ordinal()] = new MoveBackward();
        moves[Movement.TO_HEAD.ordinal()]  = new MoveToHead();
        moves[Movement.TO_TAIL.ordinal()]  = new MoveToTail();
    }
 
    /* Add a Node. */
    public void add(Node theNode)
    {
        LinkList linkList;
 
        if(null == theNode.getLinkList())
        {
            linkList = getLinkList();
            linkList.append(theNode);
        }
        else
        {
            throw new IllegalArgumentException();
        }
    }
 
    /* Remove the Node. */
    public void remove(Node theNode)
    {
        LinkList linkList;
 
        linkList = getLinkList();
        if(linkList == theNode.getLinkList())
        {
            theNode.remove();
        }
        else
        {
            throw new IllegalArgumentException();
        }
    }
 
    /* Move the Node as specified. */
    public boolean move(Node theNode, Movement theMovement)
    {
        boolean result;
        LinkList linkList;
        Move handler;
 
        linkList = getLinkList();
        if(linkList == theNode.getLinkList())
        {
            handler = moves[theMovement.ordinal()]; // get Move handler
            result = handler.move(theNode); // perform the Move
        }
        else
        {
            throw new IllegalArgumentException();
        }
 
        return result;
    }
 
    /* Move the Node forward (towards the head) in its list. */
    public boolean moveForward(Node theNode)
    {
        return move(theNode,Movement.FORWARD);
    }
 
    /* Move the Node backward (towards the tail) in its list. */
    public boolean moveBackward(Node theNode)
    {
        return move(theNode,Movement.BACKWARD);
    }
 
    /* Move the Node to the head in its list. */
    public boolean moveToHead(Node theNode)
    {
        return move(theNode,Movement.TO_HEAD);
    }
 
    /* Move the Node to the tail in its list. */
    public boolean moveToTail(Node theNode)
    {
        return move(theNode,Movement.TO_TAIL);
    }
}

At this point, most of the LinkListClosure is implemented in a forward-compatible design. Only the LinkListClosure.getLinkList() method is abstract, because it depends on the selection mechanism, array or matrix. Regardless of where the LinkList is stored or how it is implicitly selected, the redesigned list manager can add, remove, and move the nodes.

/* My row selection. */
public Enum Animal
{
    /* Select the CAT row. */
    CAT,
 
    /* Select the DOG row. */
    DOG;
}
 
/* My column selection. */
public Enum Fruit
{
    /* Select the APPLE column. */
    APPLE,
 
    /* Select the TOMATO column. */
    TOMATO;
}
 
/* My LinkListClosure for an array indexed by Select. */
public class LinkListClosureArray
extends LinkListClosureAbstract
{
    /* The array of LinkList. */
    private final LinkList[] linkLists;
 
    /* Construct the instance. */
    public LinkListClosureArray()
    {
        int blue = Select.BLUE.ordinal();
        int red  = Select.RED.ordinal();
 
        linkLists = new LinkList[2];
 
        //n.b.: The LinkListStandard is the concrete implementation
        // of the LinkList interface.
        linkLists[blue] = new LinkListStandard();
        linkLists[red]  = new LinkListStandard();
    }
 
    /* My current Select parameter. */
    private Select select;
 
    /* Set the current Select parameter. */
    public void setSelect(Select theSelect)
    {
        select = theSelect;
    }
 
    /* Get the implied LinkList. */
    public LinkList getLinkList()
    {
        return linkLists[select.ordinal()];
    }
}
 
/* My LinkListClosure for a matrix indexed by Animal,Fruit. */
public class LinkListClosureMatrix
extends LinkListClosureAbstract
{
    /* The matrix of LinkList. */
    private final LinkList[][] linkLists;
 
    /* Construct the instance. */
    public LinkListClosureMatrix()
    {
        int cat    = Animal.CAT.ordinal();
        int dog    = Animal.DOG.ordinal();
        int apple  = Fruit.APPLE.ordinal();
        int tomato = Fruit.TOMATO.ordinal();
 
        linkLists = new LinkList[2][];
        linkLists[cat] = new LinkList[2];
        linkLists[dog] = new LinkList[2];
 
        //n.b.: The LinkListStandard is the concrete implementation
        // of the LinkList interface.
        linkLists[cat][apple]  = new LinkListStandard();
        linkLists[cat][tomato] = new LinkListStandard();
        linkLists[dog][apple]  = new LinkListStandard();
        linkLists[dog][tomato] = new LinkListStandard();
    }
 
    /* My current Animal parameter. */
    private Animal animal;
 
    /* Set the current Animal parameter. */
    public void setAnimal(Animal theAnimal)
    {
        animal = theAnimal;
    }
 
    /* My current Fruit parameter. */
    private Fruit fruit;
 
    /* Set the current Fruit parameter. */
    public void setFruit(Fruit theFruit)
    {
        fruit = theFruit;
    }
 
    /* Get the implied LinkList. */
    public LinkList getLinkList()
    {
        return linkLists[animal.ordinal()][fruit.ordinal()];
    }
}

Refactoring and closure design have removed the code duplication and removed the underlying dependency on the LinkList selection mechanism. The invariant parameters for selecting the LinkList are moved downward to a subclass and eliminated from the closure API and implementation. The code duplication in the original movement methods is replaced by a single move method that invokes the appropriate closure implementation.

Two cents worth. Your mileage may vary.

Jeffrey D. Smith

Personal tools
buy