Closures

In functional programming, the closure of a function (lamdba) consists of the function itself and an environment in which the function is defined. In Java, a function is replaced by a method of a class.  In particular, the analog to functional programming's lambda function are "inner classes"; classes that are declared inside of other classes.  An inner class is only defined in the context of its outer object (and the outer object of the outer object, etc...) thus creating a well-defined "environment" in which that inner class is defined.   Since Java uses "lexical scoping" -- variables in scope are defined by the nesting of curly braces -- an inner class can access anything contained within any enclosing curly braces.  An inner class together with its nested sequence of outer objects is the equivalent of the notion of closure in functional programming.  Such a notion is extremely powerful. Just like knowing how to effectively use lambda expressions and higher order functions is key to writing powerful functional programs in Scheme, effective usage of anonymous inner classes is key to writing powerful OO programs in Java.

Note: Java lambda functions (expressions) are really just syntactic shortcuts for defining single-method anonymous inner classes, so the discussion here on closures relative to inner classes holds for Java lambda functions as well.

One of the most important ways in which we will use inner classes, particluarly anonymous inner classes, will be to take advantage of their closure properties. Named and anonymous inner classes (and equivalently, lambda functions) are the only objects in Java that can be instantiated in such a manner that the variables in their environments, i.e. their closures, can be dynamically defined. That is, since an inner class can reference a local variable (that is declared final) and since local variables are created every time a method is called, then every the inner class object created has a different set of dynamically created variables that it is referencing. This means that we can make unique objects with unique behaviors at run time.   Typically, since inner classes inside of methods are only used during the execution of that method and usually used only once as well, anonymous inner classes are used.

Factories (see also) are natural partners with anonymous inner classes. With a factory that returns anonymous inner classes, we can instantiate unique objects with unique behaviors. If the factory method takes in parameters, there local variables can be used to alter the resultant object's behavior, a process called "currying" (named after the famous mathematician/computer scientist Haskell Curry). The objects made by the factory are then sent off to various odd and sundry different parts of our OO system but all the while retaining their closures, which were determined at the time of their instantiation. Thus they retain the ability to communicate back to the factory that made them even though they are being used in another part of the system that knows nothing about the factory. We like to call these "spy objects" because they act like spies from the factory. This gives us powerful communications even though the system is decoupled.

Some important points to remember about closures and inner classes:

• An object's closure is defined at the time of its creation.
• An object "remembers" its closure for its entire lifetime.
• An inner object's closure includes any local variables that are declared as final, plus all fields of the enclosing object, including private ones.  In short, the closure includes all variables that are in scope at the point of creation ("lexical scoping").
• Every time a new anonymous object is created, a new closure for that new object is created. This is because the local variables could change between calls.  For instance, a factory method would create a new closure each time it is called in order to capture the differing input parameters for each call.
• Closures enable decoupled communication because an inner class can communicate with its outer class through its closure.

Closures are an important part of one of the 4 pillars of abstraction:

1. Abstract Structure -- abstract representations of the models of and in object systems. (abstract classes, interfaces)
2. Abstract Behavior --  abstract representations of behavior of objects. (abstract methods, strategies, visitors)
3. Abstract Construction -- abstract representations of the building of objects and systems of objects.  ( factories)
4. Abstract Environments --  abstract representations of the environments in which objects operate and interact.  (anonymous inner classes, closures)

Examples

Example 1: Reversing a list using factory and anonymous inner class helper

Write and algorithm on a list, Reverse, that returns a list with the element in reverse order, such that the algorithm takes one parameter, a factory for creating lists, IListFactory, but such that its helper algorithm only takes one parameter (other than the host list) which is the accumulated list.    The factory will be available to the helper algorithm through the helper's closure.

Some background code first, to define the list itself and the factory that is used to create it:

/**
 * Abstract representation of a linked list
 * with a Vistor Design Pattern "accept" method.
 */
public interface IList {
	/**
	 * The "accept" method of the Visitor Design Pattern. 
	 * Accepts the IListAlgo and calls the appropriate method on the algo with the given param input parameter
	 * and returns the result.
	 * @param algo  The algorithm to run on the list
	 * @param param The input parameter to the algorithm
	 * @return The result of running the algorithm on this list 
	 */
	public Object execute(IListAlgo algo, Object... param);
}

/**
 * Abstract representation of an empty list.
 * A typical implemenation of this interace would be a singleton.
 */
public interface IMTList extends IList {
}

/**
 * Abstract representation on a non-empty list, with a "first", the data element at the front of the list,
 * and a "rest", the rest of the list.
 */
public interface INEList extends IList {
	/**
	 * Gettor for the first data element
	 * @return the first data element of the list
	 */
	public Object getFirst();
	
	/**
	 * Gettor for the rest of the list
	 * @return The rest of the list
	 */
	public IList getRest();
}

/**
 * Abstract factory to create IList instances
 */
public interface IListFactory {
	/**
	 * Return an empty list instance
	 * @return an IMTList instance
	 */
	IMTList makeMTList();
	
	/**
	 * Return a new non-empty list instance, with the given first and rest.
	 * @param first the first data element of the returned list
	 * @param rest the rest of the returned list
	 * @return a NEList instance
	 */
	INEList makeNEList(Object first, IList rest);
}

Note that the specific implemenation of the lists and thus the specific implemenation of the IListFactory instance is immaterial here and the list-reversing algorithm can be written purely in terms of a given factory, which will produce a given representation of the list.   The algorithm is independent of both the implementations of the original and resultant lists.   With this algorithm, the implemenation of the original list is not necessasrily even the same as the implementation of the reversed list!

/**
 * Algorithm to reverse an IList
 */
public class ReverseAlgo implements IListAlgo { 
	
	/**
	 * Singleton Design Pattern instance
	 */
	public static final ReverseAlgo Singleton = new ReverseAlgo(); 
	
	/**
	 * Private constructor restricts the instances to just the singleton.
	 */
	private ReverseAlgo() {} 
	
	/**
	 * Reversing an empty list returns an emtpy list
	 * @param facs facs[0] is an IListFactory instance
	 * @return An IMTList as made by the given IListFactory
	 */
	public Object emptyCase(IMTList host0, Object... facs) { 
		return ((IListFactory)facs[0]).makeMTList(); 
	} 
	
	/**
	 * Recursively reverse the list using a forward-accumulator technique and the given IListFactory instance
	 * @param facs facs[0] is an IListFactory instance
	 * @return An INEList as made by the given IListFactory
	 */
	public Object nonEmptyCase(INEList host0, Object... facs) { 
		final IListFactory fac = (IListFactory) facs[0]; // final so that the anon. inner class can access it. Could have made facs final and eliminated f but this is easier to read.
		return host0.getRest().execute(new IListAlgo() {   // Use anon. inner class to define a helper algorithm.  Note that fac is in its closure!
		
			/**
			 * The case is called when the end of the original list is encountered.  
			 * @param acc acc[0] is the fully reversed list by now. 
			 * @return acc[0] 
			 */
			public Object emptyCase(IMTList host1, Object... acc) { 
				return acc[0]; 
			} 
			
			/**
			 * Called when traversing the original list but not yet at its end.  
			 * The current first will be added to the accumulated reversed list and the recursion will continue.
			 * @param acc acc[0] is the reversed list so far  
			 * @return The fully reversed list
			 */
			public Object nonEmptyCase(INEList host1, Object... acc) { 
				return host1.getRest().execute(this, fac.makeNEList(host1.getFirst(), (IList) acc[0])); // The helper algo is closing over the main algo's saved factory, so it doesn't need to be  passed as a parameter to the helper.
			} 
		}, fac.makeNEList(host0.getFirst(), fac.makeMTList()));  // The initial accumulator value is a one-element list with the original list's first.
	} 
}

The code to run the list reversal looks like this:

IListFactory aListFactory = new MyParticularListFactory(); // some concrete implementation of IListFactory

IList aList;  // A reference to an abstract list object

// For example, building up a list:
aList = aListFactory.makeMTList();  // aList is now an empty list
aList = aListFactory.makeNEList(aValue, aList);   // aList is now a one-element list
aList = aListFactory.makeNEList(anotherValue, aList);  // aList is now a two-element list
// etc., etc., etc.

IList reversedList = aList.execture(ReverseAlgo.Singleton, aListFactory) // the list executes the reversal algorithm on itself  (See the Visitor Design Pattern)

Example 2: Ant World, communicating without direct references

Imagine a world of ants that live in a one-dimensional space. A queen ant can make a bunch of worker ants. Each time she gives birth to a worker ant, she gives it a name. A worker ant can always tell what its name is. A worker ant from a particular colony can always calculate its distance from its queen. A worker ant can also move its queen to a different location. Wherever the queen moves to, ALL of her workers always know their relative distance from her. We want to keep track of all the ants in our ant world and all the ants in each of the existing colonies. We want to model the fact that each queen produces its own worker ants, each one which can move its queen around without telling the other ants in the same colony, yet ALL of the ants in the same colony would know where their queen is.

The above can be modeled by a Queen class with an abstract Worker inner class as shown below. This example illustrates the differences between static and non-static fields, methods and embedded classes.

/**
 * Models ants living in a 1-dimensional world
 *
 *
 * The Worker inner objects have direct access to the location of its outer
 * Queen object.
 *
 * @author A.L. Cox
 * @author D.X. Nguyen
 * @author S.B. Wong
 * @since 02/07/2003
 */
public class Queen {
    /**
     * The total number of ants (queens and workers for all the queens) that
     * currently exist in our ant world.
     *
     * Why is this field static?  Is there a way to build the system so that this does not have to be static?  Hint: factories!
     */
    private static int _ants;

    /**
     * The location of this Queen object with respect to 0.
     *
     * Why is this field non-static?
     */
    private int _origin;

    /**
     * The total numbers of living worker ants produced by this Queen object.
     *
     * Why is this field non-static?
     */
    private int _workers;

    /**
     * Is part of a Queen instance, just like the origin field and the
     * makeWorker() method are parts of a Queen instance.
     * The Queen instance is thus in the closure of all Workers she makes!
     * Any concrete implementation of Worker must implement the getName()
     * method to return the name given by its Queen at birth time.
     *
     * Why can't this class be static?
     */
    public abstract class Worker {

        /**
         * The location of this Worker object.
         */
        private int _location;

        /**
         * Increments _ants and _workers because every time a Worker is
         * instantiated, a new ant is added to our ant world, a new worker ant
         * is added to the colony of this outer Queen object.
         * @param loc the starting location of this Worker object.
         */
        public Worker(int loc) {
        	_location = loc;
        	_ants++;            // The worker is an ant.
        	_workers++;	// Not that the Worker is mutating fields of the Queen.
        }

        /**
         * @return the relative distance between this Worker and its outer Queen
         * object.
         */
        public int calcDist() {
           return _location - _origin;  // The worker is closing over the Queen's position so it always has direct access to it.
        }

        /**
        * The name will be given at birth.  The code cannot be written at
        * this point and thus must be abstract.
        * @return name of the worker
        */
        public abstract String getName();


        /**
        * Our worker has been stepped on!  (No one holds a reference
        * to this object anymore.  It's being garbage collected.)
        */
        protected void finalize() {
            _ants--;            // The worker is an ant.
            _workers--;		// Not that the Worker is mutating fields of the Queen.
        }

        /**
         * Changes the location of this Worker object to a new location.
         * @param loc the new location for this Worler object.
         */
        public void moveTo(int loc) {
            _location = loc;
        }

        /**
         * Changes the origin of the outer Queen object to a new location.
         * @param org  the new origin for the outer Queen object.
         */
        public void moveQueen(int org) {
            moveTo(org);    
            _origin = org;   // The worker is communicating back to the Queen, no matter where the worker is.
        }
    }

    /**
     * Initializes the origin of this Queen object to a given location.
     * Increments _ants since this new Queen object is an ant.
     * @param org the starting origin of this Queen object.
     */
    public Queen(int org) {
    	_ants++;            // The queen is an ant.
        _origin = org;
    }

    /**
     * Return the total number of all ants, including all of the
     * queens and their respective workers.
     *
     * Why is this method static?
     * Can it be non-static?
     */
    public static int countAllAnts() {
    	return _ants;
    }

    /**
     * @return the total number of workers that belong to this Queen object
     *
     * Why isn't this method static?
     */
    public int countMyWorkers() {
    	return _workers;
    }

    /**
     * Factory method: relegate the task of manufacturing concrete
     * Worker objects to the Queen object because the Queen object
     * intrinsically "knows" how to make its inner objects.
     * @param name The name of the Worker.
     */
    public Worker makeWorker(final String name) {
        // Anonymously create a Worker object by overriding getName().
        return new Worker(_origin) {
            public String getName() {
                return name;  // requires the parameter name to be final.   Notice how the Worker instance is closing over the input parameter of the factory method that made it. 
            }
        };
    }
}
            

Here is some sample code to test the above system and explore how the closures affect the behaviors of Queens and Workers.   Try other operations and do your own explorations too!

// Make some Queens at different locations:
Queen q1 = new Queen(100);
Queen q2 = new Queen(-100);

// Make a Worker.  Note that a worker is closing over the name string that was the input parameter to makeWorker().
Queen.Worker w1a = q1.makeWorker("w1a");
System.out.println("w1a.getName() = "+w1a.getName());

// Make another worker.  Note that this worker is closing over a different name
Queen.Worker w1b = q1.makeWorker("w1b");
System.out.println("w1b.getName() = "+w1b.getName());

// Make some Workers for the other queen
Queen.Worker w2a = q2.makeWorker("w2a");
Queen.Worker w2b = q2.makeWorker("w2b");

// Workers are made right next to their respective Queens
System.out.println("w1a.calcDist() = "+w1a.calcDist());
System.out.println("w2a.calcDist() = "+w2a.calcDist());

// Move one of the workers and it knows its relative location to its Queen
w1a.moveTo(150);
System.out.println("w1a.calcDist() = "+w1a.calcDist());
// But the other queen's workers are unaffected
System.out.println("w2a.calcDist() = "+w2a.calcDist());

// Move the other queen's worker
w2a.moveTo(-300);
// Each worker only affects its respective queen
System.out.println("w1a.calcDist() = "+w1a.calcDist());
System.out.println("w2a.calcDist() = "+w2a.calcDist());

// move one of the queens
w1b.moveQueen(175);
// Each worker is only affected by its respective queen
System.out.println("w1a.calcDist() = "+w1a.calcDist());
System.out.println("w2a.calcDist() = "+w2a.calcDist());

// Move the other queen
w2b.moveQueen(-314);
// Each worker is only affected by its respective queen
System.out.println("w1a.calcDist() = "+w1a.calcDist());
System.out.println("w2a.calcDist() = "+w2a.calcDist());
 

Example 3: QueenBalls and children balls in BallWorld, parent affecting children and children affecting the parent

Here is an example of a type of ball that can be used in an inheritance-based BallWorld system.   A QueenBall is a Factory for smaller custom balls.    Each child ball is constructed so that it closes over its parent queen ball, i.e. the queen that made it is in the closure of the child ball.  This code demonstrates how closures can be used to both communicate from the parent (the factory) to the children (the factory's products) as well as to communicate from the children back to their parent, all without any explicit references between them.

Here, the queen's position at any time affects the velocity of any child balls that the queen has made by biasing the children's movement such that they will tend to follow their particular queen around.   Each queen ball will only affect the behavior of the children balls that they have created.

Each child ball has a certain probability of "dying", which means that it removes itself from the dispatcher and thus no longer gets updated.    When a child dies, it mutates its parent queen ball such that the parent will flash random colors for a short "mourning" period for each child ball that "dies".

Note:  The code uses some non-obvious numerical calculation techniques to give reasonable and stable random walk and swarming/flocking behavior.  Even so, once in a while, due to round-off errors, a child ball may appear to stop moving.   These mathematical computations are not germaine to the issue of closures so do not focus on them.   Focus instead on how fields and methods in the queen ball are used to create communications both to and from the children balls.

package model.ball;
/**
 * Note that this code may need to be modified to work in your BallWorld system!
 * The names and behaviors of the methods in the abstract ABall superclass may not 
 * match those used here, including the parameters of the constructor. 
 * 
 * This code demonstrates how the closure of child objects over their parent objects
 * enables the parent to affect the behavior of all its children as well as 
 * enables any child to affect the behavior of the parent, all without creating or
 * maintaining any references between the parent and children.
 * 
 * Note:  IDimension is simply an interface that defines a getWidth() and getHeight() 
 * methods that return integers.   Other parts of the Ballworld system connect an IDimension 
 * implementation to the canvas panel that the balls are bouncing in on the view so that 
 * the IDimension instance returns the current width and height of that panel.
 */

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;

import model.IDimension;
import provided.util.dispatcher.IDispatcher;
import provided.util.valueGenerator.IRandomizer;
import provided.util.valueGenerator.impl.Randomizer;

/**
 * A QueenBall periodically spawns smaller child balls of the same color.  
 * While both the queen and the children both exhibit random walking behavior, 
 * the children will tend to follow the queen around ("swarm" the queen).
 * Any child has a certain probability of "dying" (removing itself from the 
 * dispatcher) and when it does, it will cause its parent queen to "mourn" for
 * a while by randomly changing color.
 * @author Stephen Wong
 *
 */
public class QueenBall extends ABall {

	/** 
	 * birth frequency in ticks
	 */
	private static final int BIRTHCOUNT = 50;

	/** 
	 * Random walk max rotation angle 
	 */
	private static final double MAXROTATEANGLE = Math.PI / 5.0;

	/** 
	 * Factor to bias the children's velocity to go towards their parent
	 */
	private static final double SWARMINGFACTOR = 0.2;

	/** 
	 * Probability per tick of a child dying
	 */
	private static final double DEATH_PROB = 0.005;

	/** 
	 * Number of ticks the parent mourns the child's death
	 */
	private static final int DEATHTICKS = 15;

	/**
	 * Randomizer object for internal use
	 */
	private IRandomizer rand = Randomizer.Singleton;

	/**
	 * Need to save a reference to the IDimension object to give to the babies when they are instantiated.
	 */
	private IDimension dim;

	/**
	 * The tick counter to the next child birth
	 */
	private int birthCounter = BIRTHCOUNT;

	/**
	 * The number of ticks left to mourn a child's death
	 */
	private int deathCounter = 0;

	/**
	 * Need to save the original color for use in making children and after mourning is done.
	 */
	private Color origColor;

	/**
	 * Constructor for the class
	 * @param p The location of the Ball
	 * @param r The radius of the Ball
	 * @param v The initial velocity of the Ball
	 * @param c The color of the Ball
	 * @param dim the dimensions of the ball's canvas
	 */
	public QueenBall(Point p, int r, Point v, Color c, IDimension dim) {
		super(p, r, v, c, dim);
		this.origColor = c; // save the color for later
		this.dim = dim; // save the IDimension object for later
	}

	@Override
	/**
	 * Queen does a random walk and mourns dead children
	 */
	public void updateState(IDispatcher<Graphics> disp) {
		randomRotate(this.getVelocity()); // Always rotate the velocity to keep the speed constant

		if (0 < deathCounter) { // deathcounter is non-zero if a child just died
			setColor(rand.randomColor()); // change colors randomly while mourning
			deathCounter--; // decrement the mourning period
		} else {
			setColor(origColor); // reset the color if not mourning
		}
		updateBabies(disp); // make a baby if it is time to do so
	}

	/**
	 * Use anonymous inner class to override the ABall's updateState() method to create a baby ABall that holds
	 * its birth mother queen ball in its closure.  
	 * @param dispatcher  The Queen's dispatcher from her updateState method.  Used to put new babies into the world. 
	 */
	private void updateBabies(final IDispatcher<Graphics> dispatcher) {

		// Make babies periodically, i.e. if the birthCounter has gone to zero
		if (0 == birthCounter) {
			// Make a custom baby ABall using info from the parent QueenBall and add it to the world.
			// Use an anonymous inner class to subclass ABall and create an instance of that subclass, which is then added to the dispatcher.
			dispatcher.addObserver(new ABall(new Point(QueenBall.this.getLocation()), QueenBall.this.getRadius()/2, new Point(QueenBall.this.getVelocity()), 
					QueenBall.this.origColor, QueenBall.this.dim) {

				// Note that the child ball here is closing over the parent QueenBall.
				// "this" refers to this child ball
				// "QueenBall.this" refers to the parent QueenBall.

				@Override
				/**
				 * This is the baby's updateState() method.    The baby ball is a fully functioning 
				 * ball in the world just like any other ball.
				 * @param disp The dispatcher that is updating this baby
				 */
				public void updateState(IDispatcher<Graphics> disp) {
					if (rand.randomDouble(0.0, 1.0) < DEATH_PROB) {
						disp.removeObserver(this); // Commit suicide by removing one's self from the dispatcher
						deathCounter += DEATHTICKS; // Tell the parent to mourn this child.   deathCounter is part of this baby's mother!
					} else {
						randomRotate(this.getVelocity()); // do a random walk

						// Bias the velocity to go towards the parent Queen
						Point toQueen = new Point(QueenBall.this.getLocation().x - this.getLocation().x,
								QueenBall.this.getLocation().y - this.getLocation().y);
						double angle = angleBetween(this.getVelocity(), toQueen); // The angle between the velocity and where the Queen is.
						rotate(this.getVelocity(), SWARMINGFACTOR * angle); // Turn towards the Queen but not all the way
						// Note: The babies are technically "swarming" the queen because their motion is tending towards the queen's location, 
						// not the queen's velocity which would be "flocking". 

					}
				}
			});
			birthCounter = BIRTHCOUNT; // reset the Queen mother's birth tick counter
		} else {
			birthCounter--; // decrement the Queen mother's birth tick counter
		}

	}

	/**
	 * Utility method to rotate v by the given angle
	 * the input Point is mutated.
	 * @param v  A velocity Point
	 * @param angle Angle to rotate by in radians
	 */
	private void rotate(Point v, double angle) {
		double cosA = Math.cos(angle);
		double sinA = Math.sin(angle);
		v.setLocation(cosA * v.getX() - sinA * v.getY(), cosA * v.getY() + sinA * v.getX());
	}

	/**
	 * Utility method to randomly rotate the given velocity Point v
	 * Mutates the given Point object
	 * @param v A velocity
	 */
	private void randomRotate(Point v) {
		//System.out.println("v = "+v);
		double angle = rand.randomDouble(-MAXROTATEANGLE, MAXROTATEANGLE);
		this.rotate(v, angle);
	}

	/**
	 * Utility method to get the signed angle between the two vectors
	 * @param v1  vector #1
	 * @param v2  vector #2
	 * @return the angle from v1 to v2
	 */
	private double angleBetween(Point v1, Point v2) {
		//  Get the vector lengths
		double v1_len = v1.distance(0.0, 0.0);
		double v2_len = v2.distance(0.0, 0.0);

		if (0.0 == v1_len || 0.0 == v2_len) { // safety check to prevent divide-by-zero below
			return 0.0;
		}

		// The cross-product length is product of each vector's length times sine of angle between
		double v1Xv2 = v1.getX() * v2.getY() - v1.getY() * v2.getX(); // calculate cross-product length 
		double angle = Math.asin(v1Xv2 / (v1_len * v2_len)); // extract the angle  
		if (Double.isNaN(angle)) {
			angle = 0.0; // safety check in case something went wrong with the arcsine calculation
		}
		return angle;
	}

}

© 2020 by Stephen Wong