©2008 Felleisen, Proulx, et. al.

5  Abstracting over Data Definitions; Accumulators

5.1  Abstracting over Data Definitions.

A bank customer can have three different accounts: a checking account, a savings account, and a line of credit account.

Review of Designing Methods for Unions of Classes.

The code in lab4-banking.bjava defines the classes that represent this information.

  1. Make examples of data for these classes, then make sure you understand the rules for withdrawals.

    Now design the methods that will manage the banking records:

  2. Design the method canWithdraw that determines whether the customer can withdraw some desired amount.

  3. Design the method makeDeposit that allows the customer to deposit a given amount of money into the account.

  4. Design the method maxWithdrawal that computes the maximum that the customer can withdraw from an account.

  5. Design the method moreAvailable that produces the account that has more money available for withdrawal.

Save the work you have done. Copy the files and continue.

Abstracting over Data Definitions: Lifting Fields

Save your work and open it again with the file type ’ijava’. Change the language level to Intermediate ProfessorJ.

Look at the code and identify all places where the code repeats — the opportunity for abstraction.

Lift the common fields to an abstract class ABanking. Make sure you include a constructor in the abstract class, and change the constructors in the derived classes accordingly. Run the program and make sure all test cases work as before.

Abstracting over Data Definitions: Lifting Methods

For each method that is defined in all three classes decide to which category it belongs:

  1. The method bodies in the different classes are all different, and so the method has to be declared as abstract in the abstract class.

  2. The method bodies are the same in all classes and it can be implemented completely in the abstract class.

  3. The methods look very similar, but each produces a different variant of the union — therefore it cannot be lifted to the super class.

  4. The method bodies are the same for two of the classes, but are different in one class — therefore we can define the common body in the abstract class and override it in only one derived class.

Now, lift the methods that can be lifted and run all tests again.

Save the work you have done up to the time you took the quiz.

5.2  Quiz

You have 10 minutes.

After the quiz, continue with the second part of the lab.

5.3  Designing Recursive Methods with Accumulators

Our goal is to practice converting the structural recursion into recursion that uses accumulators to keep track of the previous knowledge.

The code in the lecture from January 24th 2007 implements the following methods for classes that represent a list of songs:

// Count the number of songs in *this* LoS
int count();

// Find the total size of all the songs in *this* LoS
int totalSize();

// Is a song by the given artist in *this* LoS
boolean contains(String artist);

// Create a list of all songs by the given artist in *this* LoS
LoS allBy(String artist);

You can find the lecture at


Designing the loops with accumulators

We now convert our methods to use the accumulator style. As we did in Scheme, we will design a helper method that takes one more argument, the accumulator. The accumulator at any given point in the computation will hold the "answer" to our question thus far.

The first question to ask is:

Step 1: What is the type of the expected result?

This determines not only the return type for the method, but also the type of the value that will be accumulated. If the type is <code>AccType, we add an argument AccType acc to the method signature and add Acc to its name.

That means we add the following methods to the interface:

// Count the number of songs in *this* LoS
int countAcc(int acc);

// Find the total size of all the songs in *this* LoS
int totalSizeAcc(int acc);

// Is a song by the given artist in *this* LoS
boolean containsAcc(String artist, boolean acc);

// Create a list of all songs by the given artist in *this* LoS
LoS allByAcc(String artist, LoS acc);

The next step is to change the purpose statements to explain the meaning of the accumulated value.

Step 2: Change the purpose statements for all new methods.

For example, we say:

// add to the acc the number of songs in *this* LoS
int countAcc(int acc);

Next we need to figure out what are the values each method produces when it is invoked withe the empty list. Think of where can you find out. We call this the base value.

Step 3: Make a list of the base values for all new methods.

Of course, the base value for the count method is 0 .

We now deal with the following problem. The original question did not mention the accumulator. That means that the method that uses the accumulator is only our helper method. The original method needs to invoke this helper so that it would produce the original result.

There are two steps that make this possible.

Step 4: Invoke the method that uses the accumulator using the base value as the initial accumulator value.

For example we get:

// Count the number of songs in *this* LoS
int count(){
  return this.countAcc(0);

As the things stand now, we need to add this method body to the method definition in both the empty class (MtLoS) and the class that represents a nonempty list (ConsLoS). In the next section we will learn how to do this only once.

The next step deals with the class that represents the empty list.

Step 5: Implement the method body in the class MtLoS.

The purpose statement makes it clear that the method just produces the value of the accumulator. This makes sense. If the original method is invoked by an instance of the empty class, it produces the base value, as expected.

Implement all method bodies for the class MtLoS.

Now comes the hardest part of the whole process.

Step 6: Design the update method.

Let us examine what happens inside of the method body in the class ConsLoS. We list all method definitions here:

// Count the number of songs in *this* non-empty LoS
int count(){ return 1 + this.rest.count();

// Find the total size of all the songs in *this* non-empty LoS
int totalSize(){  return this.first.size + this.rest.totalSize();

// Tell if there is a song by the given artist in *this* non-empty LoS
boolean contains(String artist){
  return this.first.artist.equals(artist) ||

// Create a list of all songs by the given artist in *this* non-empty LoS
LoS allBy(String artist){
    return new ConsLoS(this.first, this.rest.allBy(artist));
    return this.rest.allBy(artist);

In each case, there is some computation that involves this.first and the recursive invocation of the original method by the list this.rest, though in the count method it only contributes 1 to the count.

The update method has the following common structure:

// update the value of the accumulator using this.first value
AccType updateMethodName(Song first, AccType acc){ ... }

For the method count the updateCount method is defined as:

// update the value of the count by adding the first item to the count
int updateCount(Song first, int acc){ return 1 + acc;

Design the remaining update methods. And, yes, do follow the design recipe.

We are just about done.

Step 7: Complete the body of the method using the update method.

The method that uses the accumulator is the same for all cases. The instance of the rest of the list invokes the method self-referentially, using the updated value of the accumulator.

For the count method this will be:

// add to the acc the number of songs in *this* LoS
int countAcc(int acc){
  return this.rest.countAcc(this.updateCount(this.first, acc));

While this may look to be very complicated for the simple count method, it is much more useful and cleaner for the remaining methods.

Finish designing the bodies of the remaining methods. When done, run the original tests for the main methods as well as all of your other test cases.

Save the work you have done.

Last modified: Monday, February 4th, 2008 4:29:43pm