warpedjavaguy

Imperative by day and functional by night

Polymorphism by Closure Injection?


Instead of defining many classes to do the same thing differently through polymorphism, you could define just one class and achieve the same through closure injection!
 

I recently downloaded the feature complete BGGA closures prototype and had a bit of a play. My first experiment was to refactor an existing codebase and replace all anonymous inner classes with closures. The ones that extended single abstract method (SAM) interfaces were easy to convert. The ones that extended multiple method (non-SAM) types were a bit trickier. In the end though, I managed to successfully convert all of them, and with very little effort.

In converting the non-SAM types, I discovered that the functional equivalent of polymorphism can be achieved by injecting closures into a single concrete implementation having no subclasses.

The codebase I refactored was a small (fictitious) railroad application that provided customers with information about routes. In particular, it calculated things like the number of routes between two cities, the number of routes that do not exceed a given number of stops, the distances of individual routes, and the like. It did this by deriving routes on the fly from a given set of legs and dynamically yielding only those that match a given predicate (or condition).

Here is the original predicate code using anonymous inner classes:

public abstract class Predicate<T> {

  public boolean eligible(T item) {
    return yield(item);
  }

  public abstract boolean yield(T item);

  /* Pre-defined predicates follow */

  public static Predicate<Route> routesWithMaxStops(final int maxStops) {
    return new Predicate<Route>() {
      public boolean yield(Route route) {
        return route.getLegs().size() <= maxStops;
      }
    };
  }

  public static Predicate<Route> routesWithStops(final int stops) {
    return new Predicate<Route>() {
      public boolean eligible(Route route) {
        return route.getLegs().size() <= stops;
      }
      public boolean yield(Route route) {
        return route.getLegs().size() == stops;
      }
    };
  }

}

In the above code only two predefined predicates are shown for brevity (the actual code has got more).

Note that the predicate has two methods. Only routes for which both methods return true are yielded.

  • eligible – determines if a route satisfies a boundary condition
  • yield – determines if a route should be yielded

Here is the converted closure equivalent:

public class Predicate<T> {

  private {T => boolean} eligible;
  private {T => boolean} yield;

  public Predicate({T => boolean} yield) {
    this(yield, yield);
  }

  public Predicate({T => boolean} eligible, {T => boolean} yield) {
    this.eligible = eligible;
    this.yield = yield;
  }

  public boolean eligible(T item) {
    return eligible.invoke(item);
  }

  public boolean yield(T item) {
    return yield.invoke(item);
  }

  /* Pre-defined predicates follow */

  public static Predicate<Route> routesWithMaxStops(int maxStops) {
    return new Predicate<Route>(
      {Route route => route.getLegs().size() <= maxStops});
  }

  public static Predicate<Route> routesWithStops(int stops) {
    return new Predicate<Route>(
      {Route route => route.getLegs().size() <= stops},
      {Route route => route.getLegs().size() == stops});
  }

}

If you look carefully, you will notice that both the original and converted code produce a redundant invocation when the eligible and yield expressions are identical. Fortunately, this is a flaw that can be very easily corrected in the closure version.

A possible correction is shown below (see lines 5, 17, 18, and 22):

public class Predicate<T> {

  private {T => boolean} eligible;
  private {T => boolean} yield;
  private boolean isEligible;

  public Predicate({T => boolean} yield) {
    this(yield, yield);
  }

  public Predicate({T => boolean} eligible, {T => boolean} yield) {
    this.eligible = eligible;
    this.yield = yield;
  }

  public boolean eligible(T item) {
    isEligible = eligible.invoke(item);
    return isEligible;
  }

  public boolean yield(T item) {
    return (isEligible && eligible == yield) ? true : yield.invoke(item);
  }

  /* Unchanged pre-defined predicates not shown here */

}

Applying the same correction to the original closureless version is not nearly as simple. It would require a more complex solution and could even involve changing the interface.

It is very interesting that polymorphic functionality can be achieved by injecting closures into one concrete class instead of defining multiple subclasses of an abstract class. Closures and anonymous inner classes, injection and inheritance, deferred execution and late binding. So many great choices!

Advertisements

Written by warpedjavaguy

September 4, 2008 at 11:31 pm

Posted in java, programming

Tagged with

6 Responses

Subscribe to comments with RSS.

  1. Surely inner classes are simpler and clearer because you can give meaningful names:

    public interface IsRouteOK { boolean test(Route route); }

    public class RouteTests {
    private IsRouteOK eligible;
    private IsRouteOK yield;
    private boolean isEligible;

    public RouteTests(IsRouteOK yield) {
    this(yield, yield);
    }

    public RouteTests(IsRouteOK eligible, IsRouteOK yield) {
    this.eligible = eligible;
    this.yield = yield;
    }

    public boolean eligible(Route route) {
    isEligible = eligible.test(route);
    return isEligible;
    }

    public boolean yield(Route test) {
    return (isEligible && eligible == yield) ? true : yield.test(route);
    }

    /* Pre-defined predicates not shown here */

    }

    Howard Lovatt

    September 5, 2008 at 5:59 pm

  2. It is interesting that you do that Howard, because what you have done is refactored my closure version to use SAM interfaces. The question is would you have originally coded it by injecting interfaces or would have coded it using an abstract class and anonymous inner subclasses? To achieve polymorphism, would you have originally chosen deferred execution over late binding?

    WarpedJavaGuy

    September 5, 2008 at 8:55 pm

  3. I think I’d call these functional programming abstractions and functional composition techniques “abstraction through closure injection” and not “polymorphism through closure injection”. It seems the point of the Strategy Pattern isn’t to achieve polymorphism but to achieve an abstract solution framework that can be applied to many different problems. Functional composition, which is kinda what the strategy pattern is about, strives for the same goal.

    WarpedJavaGuy – September 8, 2008

    Hamlet, my original non-closure version used polymorphism. Hence the reasoning behind the title.

    Hamlet D'Arcy

    September 8, 2008 at 8:52 am

  4. I agree with Hamlet D’Arcy – it is the sort of thing I do with the Strategy pattern often.

    I would also say that if I wrote the code I would possibly do it differently, I say possibly because I haven’t seen the whole example (which is fair enough this is a blog after all). Two things look out of place in the fragment presented are:

    1. The use of generics – there is only Route shown, so why not code to Route directly or extend generic interfaces to encode Route – see below

    2. eligible and yield have a lot of overlap in their functionality – in normal optimisation and searching algorithms (operations research) you would typically have:

    interface Penalty { double cost( T t ); }

    /** Route Penalty is the time taken for a given Route */
    interface RoutePenalty extends Penalty {}

    interface Constraint { boolean isOK( T t ); }

    /** Route Constraint is if a given Route is feasible and if it is within user constraints like maximum number of stops */
    interface RouteConstraint extends Constraint {}

    The search algorithm is usually generic and accepts a Penalty (the cost of the solution, e.g. time of Route) and a List of Constraints (all of which have to be satisfied if the route is OK), so I would be tempted to code the example using the standard searching conventions. The call to optimise would typically be:

    /** List of Routes sorted by their penalty */
    interface SortedRoutes extends SortedList {}

    final Optimiser optimiser = new Optimiser();
    optimiser.setPenalty( routePenalty );
    optimiser.setConstraints( routeConstraints );
    optimiser.setMethod( OptimiserType.GENETIC );
    final SortedRoutes possibleRoutes = optimiser.optimise( routes );

    The reason for introducing RoutePenalty, RouteConstraint, SortedRoutes, etc. is that they give you somewhere to comment what the penalty, constraints, method of sorting, etc. is for a Route, they also reads a little better in the code.

    The above is pseudo code – but hopefully gives an idea of how standard searching algorithms are used.

    Howard Lovatt

    September 8, 2008 at 11:14 am

  5. Howard,

    In response to 1:
    I actually use the predicate on Legs as well as Routes. Therefore the use of generics here is justified. Sample snippet:

    new Predicate<Leg>(
     {Leg leg => leg.startsAt(origin)});

    In response to 2:
    My code does not perform a search on a list of existing routes, but rather on a dynamic iteration of routes that are generated on the fly. The predicate is used to yield eligible routes in real time as they are generated. Having said that, the pattern you describe can still be applied here.

    WarpedJavaGuy

    September 8, 2008 at 8:59 pm

  6. Hamlet,

    You make an interesting point about the strategy pattern being used to create functional programming abstractions. Would you say that discrete units of abstraction like SAM interfaces actually encourage a more functional style of programming as opposed to abstract classes which may not be as discrete? If so, and if this is the preferred, better, and more standard approach, would having closures in Java be a natural step forwards for the language?

    There are those who want closures and those who don’t, but most of us I think agree that interfaces are good. In terms of SAM interfaces, there is not much difference between them and closures. Both define a single unit of abstraction. But interfaces are considered object oriented whereas closures are not. Surely closures would make for a more pleasant programming experience when used in this way.

    WarpedJavaGuy

    September 10, 2008 at 8:47 pm


Comments are closed.

%d bloggers like this: