Lecture 12: Abstracting over behavior: Function objects
Learn how to represent behavior as an object
Practice abstraction over behavior.
BostonMarathon.java
Lecture 12: Outline
The need to abstract over behavior
Defining function objects
Using function objects
Designing tests for the use of function objects
1 Abstracting over behavior: Function objects
Introduction: Young at Heart —
The most popular Boston sports event takes palce every year on a Monday in April, on the Patriot’s Day holiday. It is not a baseball game, or a football game. There are over 10000 athletes who take part in the event, with over 100000 spectators, bringing the whole city to a standstill for most of the day.
Boston Marathon has been held for over 100 years, with some of the runners becoming legends. The best known among them is Johnny Kelly, who died in 2004 after having run the marathon for more than fifty times, winning it three times in the 1920’s. You can still see him running on the course at the base of the Heartbreak Hill in Newton, the old one holding the hand with the winner from 1920’s  a statue named "Young at Heart".
We want to help the organizers to keep track of all the runners. For each runner they record the name, the age, the bib number, the runner’s time, and whether the runner is male or female.
The following classes represent the list of runners. We show the class diagrams here, and add the code at the end:
++ 
 ALoR <+ 
++  
++  
/ \  
  
  
  
   
++ ++  
 MTLoR   ConsLoR   
++ ++  
++ + Runner first   
  ALoR rest + 
 ++ 
 
v 
++ 
 Runner  
++ 
 String name  
 int age  
 int bib  
 boolean isMale  
 int time  
++ 
We would like to sort the runners by their names, so we can issue the bibs. At the finish line, we would like to sort the runners by the bib numbers, so we can check easily whether they returned their timer chip, as well as to record the running time. At the end of the race, we need to make a list of runners sorted by their time. We also want to sort the runners by their age, to see how many are in each age category, and who are the winners for each age category. We also need to make a separate list of male and female runners.
We start with examples of runners and a list fo runners:
Runner johnny = new Runner("Kelly", 100, 999, true, 360); 
Runner frank = new Runner("Shorter", 32, 888, true, 130); 
Runner bill = new Runner("Rogers", 36, 777, true, 129); 
Runner joan = new Runner("Benoit", 29, 444, false, 155); 

ALoR mtlist = new MTLoR(); 
ALoR list1 = new ConsLoR(johnny, new ConsLoR(joan, mtlist)); 
ALoR list2 = new ConsLoR(frank, new ConsLoR(bill, list1)); 
Let us start by recalling what we remember about insertion sort for lists, that we have studied earlier.
We recall, that besides the method sort() in the classes that represent a list, we also needed an insert(...) method. For our examples, in the class ALoR we start with:
// produce a sorted list from this list of runners  by name 
abstract ALoR sortByName(); 

// produce a sorted list from this list of runners  by age 
abstract ALoR sortByAge(); 

// insert the given runner into this sorted by name list of runners 
abstract ALoR insertByName(Runner r); 

// insert the given runner into this sorted by age list of runners 
abstract ALoR insertByAge(Runner r); 
We also recall that in the class MTLoR, the method body did not depend on the contents of the list or the criterion use to order the list elements:
ALoR sortByName(){ return this; } 
ALoR sortByAge(){ return this; } 

ALoR insertByName(Runner r){ return new ConsLoR(r, this); } 
ALoR insertByAge(Runner r){ return new ConsLoR(r, this); } 
Let us make a couple of examples for the nonempty lists:
// sorting by the runner's names: 
list2.sortByName() > new ConsLoR(joan, 
new ConsLoR(johnny, 
new ConsLoR(bill, 
new ConsLoR(frank, mtlist))))); 

// sorting by the runner's ages: 
list2.sortByAge() > new ConsLoR(joan, 
new ConsLoR(frank, 
new ConsLoR(bill, 
new ConsLoR(johnny, mtlist))))); 
Of course, we do not know how to indicate to the sort method that the criterion should be ’by name’ or ’by age’. We can start by adding the methods ’byAge’ and ’byName’ to the class Runner. Each method consumes a Runner and produces a boolean value. Here are examples:
joan.byName(bill) > true 
bill.byName(joan) > false 

frank.byAge(johnny) > true 
bill.byAge(joan) > false 
The method bodies are:
// determine whether this runner's name comes before the given one's 
boolean byName(Runner r){ 
return this.name.compareTo(r.name) < 0; 
} 

// determine whether this runner is younger than the given runner 
boolean byAge(Runner r){ 
return this.age < r.age; 
} 
We can now finish the sort methods (and the helper insert methods):
// produce a sorted list (by names) from this list of runners 
ALoS sortByName(){ 
// insert the first item into the sorted rest of this list 
return this.rest.sortByName().insertByName(this.first); 
} 

// produce a sorted list (by ages) from this list of runners 
ALoS sortByAge(){ 
// insert the first item into the sorted rest of this list 
return this.rest.sortByAge().insertByAge(this.first); 
} 

// insert the given runner (by name) into this sorted list of runners 
ALoS insertByName(Runner r){ 
if (r.byName(this.first)) 
return new ConsLoR(r, this); 
else 
return new ConsLoR(this.first, this.rest.insertByName(r)); 
} 

// insert the given runner (by name) into this sorted list of runners 
ALoS insertByAge(Runner r){ 
if (r.byAge(this.first)) 
return new ConsLoR(r, this); 
else 
return new ConsLoR(this.first, this.rest.insertByAge(r)); 
} 
Let us compare the two solutions. If we renamed the methods to sort instead of sortByName and sortByAge, the only place where the two methods differ over all three classes are in the if condition for the method in the class ConsLoR:
if (r.byName(this.first)) ... 
if (r.byAge(this.first)) ... 
Let us look at the methods byName and byAge in the class Runner:
boolean byName(Runner r){ 
return this.name.compareTo(r.name) < 0; } 

boolean byAge(Runner r){ 
return this.age < r.age; } 
The method signatures are the same  each of them consumes a Runner and produces a boolean value. We could abstract by defining an interface:
interface ICompRunner{ 
// is this runner 'better' than the given runner? 
boolean compRunner(Runner r); 
} 
However, if we try to modify the class Runner to implement this interface, we still have a problem, as we can only implement one of the two methods.
We try a different approach. Let us recall, that in DrRacket, the sort function consumed a function that determined how two elements of the list should be compared (a function of the type X x X > Bool). We define a new interface ICompRunners wehre the comparison method consumes two runners to be compared:
interface ICompRunners{ 
// is the first runner 'better' than the second runner? 
boolean compRunners(Runner r1, Runner r2); 
} 
Let us look again at the two ’if’ conditions:
if (r.byName(this.first)) ... 
if (r.byAge(this.first)) ... 
With the above interface, we could try something like:
if (~~~byName.compRunners(r, this.first)) ... 
if (~~~byAge.compRunners(r, this.first)) ... 
This looks promising, because if ~~~byName and ~~~byAge were instances of some class, we could pass these instances to the sort and insert methods as arguments. Now, if we want this instance to invoke the method compRunners, it must be of the type ICompRunners, i.e. an instance of a class that implements the ICompRunners interface.
Well, the only thing we can do if define two new classes, each of which implements this interface. We do not need these classes to do anything else than deliver the method compRunners to be used in the comparison.
Here are the two classes:
class ByName implements ICompRunners{ 
// is runner r1's name before runner r2's? 
boolean compRunners(Runner r1, Runner r2){ 
return r1.name.compareTo(r2.name) < 0; 
} 
} 

class ByAge implements ICompRunners{ 
// is runner r1 younger than runner r2? 
boolean compRunners(Runner r1, Runner r2){ 
return r1.age < r2.age; 
} 
} 
We did not show the constructors  they are the same as in the Examples class  consume no arguments and initialize no fields.
The insert method in the class ConsLoR can now consume an instance of either of these classes, and the method becomes:
// insert the given runner into this sorted list of runners 
ALoR insert(Runner r, ICompRunners comp){ 
if (comp.compRunners(r, this.first)) 
return new ConsLoR(r, this); 
else 
return new ConsLoR(this.first, this.rest.insert(r, comp)); 
} 
This of course means that the method signature for the insert method has to change in the classes ALoR and MTLoR as well, and the ’ comp argument has to be passed to it at every invocation. That leads us to realize that we need to pass the comparison object to the sort method itself  so it could then invoke the insert method with the correct argument. The final code is shown below.
Of course, we also have to rewrite the original tests so that we verify that our abstraction allows us to solve the original problem. The tests are:
boolean testSortNames2(Tester t) { 
t.checkExpect(list2.sort(new ByName()), 
new ConsLoR(joan, 
new ConsLoR(johnny, 
new ConsLoR(bill, 
new ConsLoR(frank, mtlist)))))) && 

t.checkExpect(list2.sort(new ByAge()), 
new ConsLoR(joan, 
new ConsLoR(frank, 
new ConsLoR(bill, 
new ConsLoR(johnny, mtlist)))))); 
} 
As an exercise, you should add the remaining classes needed to sort the list by the bib numbers and by the time, and write the tests to make sure your implementation works as desired. You can also sort the list by gender.
The object that is the carrier of the method we really want is sometimes called function object. It is Java’s cumbersome way to pass a method as an argument to a fucntion. It is used extensively when defining the action the program should take in response to a GUI event, such as clicking on a button, or hitting a key.