# Using Nested Loops and Arrays to Sing Cumulative Songs

In this assignment we will practice using nested loops and introduce the use of arrays. Make sure you have read Chapter 6 of the textbook; you may want to review Chapter 4 as well.

What to turn in:

You should select a specific song with cumulative structure to implement in Java; it may be Old MacDonald, but it you may choose a different song, too. You should turn in your Java code and the output it prints; if there are variations (e.g., different animals and orders for Old MacDonald), you may want to turn in more than one version of the output.

Note that you do not have to read in lyrics (or variations) with a scanner!

## The Structure of Cumulative Songs

There is a certain style of song, sung mostly by children (sometimes on holidays and often on busses!) known as a cumulative song. These songs feature a special kind of lyrical repetition, where new things of some kind are introduced with each verse, but where the older things are also reviewed, usually in reverse order, after the new ones are introduced. You can read about these songs at the Wikipedia entry on cumulative songs, but you probably know a lot of them already from your own childhood. Examples include: and many others.

This type of song seems to occur in many different cultures, but they seem to be popular with children in particular. Presumably, this has something to do with children at a certain age learning about order and memory; perhaps when in this stage of development they are also more willing to put up with long-winded repetition of simple patterns .

(I don’t have a bunch of references on academic perspectives on song patterns to quote, but here’s at least a link to an article in the Journal of American Folklore about the history of certain cumulative songs:

Songs of the “Twelve Numbers” and the Hebrew Chant of “Echod Mi Yodea”.

Personally, I have fond memories of reading and singing from the book Down by the Station when my kids were small.)

(By the way, the famous computer scientist Don Knuth used the Old MacDonald song as an an example in his short humorous paper on The Complexity of Song; in the paper, Knuth analyzes the structure of this kind of song in terms of asymptotic complexity theory!)

## The Structure of Old MacDonald

Let's take as our main example the song Old MacDonald Had a Farm: it consists of a series of verses, each of which starts and ends with a common refrain (“Old MacDonald had a farm, E-I-E-I-O”). After the first refrain, each verse introduces a new animal from the farm, providing the name of the animal in a lyric context (“And on that farm he had a pig, E-I-E-I-O”). Then the sound of the animal is celebrated in a rhythmic fashion, including an occasional “doubling” of the sound:

With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink
This is followed by the closing refrain.

But here’s where the interesting part comes in: with each subsequent verse (of the same structure), a new animal and sound are introduced. But the length of the verses also grows, because after the new animal and its sound are introduced, we also repeat the sound portion for every animal already sung about, in the reverse of the order in which they were introduced. Thus in verse one, we sing about the first animal by name and sound; in verse two, we sing about the second animal by name and sound, but repeat the sound portion for the first animal; and in each subsequent verse we add a new animal, but repeat the sound portions for all previous animals.

Well, it's perhaps best shown by example; here’s a sample of the first three verses:

```Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a pig, E-I-E-I-O,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a cow, E-I-E-I-O,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a horse, E-I-E-I-O,
With a neigh-neigh here and a neigh-neigh there,
Here a neigh, there a neigh, everywhere a neigh-neigh,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.
```

In fact, the number of animals and the specific sequence used is typically chosen during the singing of the song, so that the actual lyrics will vary from singing to singing.

The idea of this lab is to write a program which will generate the lyrics to a (version of) the song, but where we can easily change the actual animals, their sounds and their order.

## Storing the Animals and Sounds in Arrays

As a first step in generating the lyrics, we will need a way to store a sequence of animals and their sounds. Now that we know how to use arrays, we can just declare two arrays of strings, one with animal names and one with their sounds. We can declare constant arrays using braces in Java as follows:

```String[] animals = { "pig", "cow", "horse", "chicken", "sheep" };
```
(Here you must remember to put a semi-colon after the closing brace, unlike for many Java statements which end in closing braces.)

Note that the String array is declared without any specific mention of its size in the square brackets; this is because the Java compiler can determine the size from the specific sequence mentioned on the right-hand side. For some array declarations, namely those whose elements we do not know in advance, we might declare the size of the array at the time we declare the array itself, like this:

```Song [] favorites = new Song[10];
```

In the case of Old MacDonald and his farm, we could declare two arrays of strings, one for animals and one for sounds ... but make sure they are actually of the same length, and that the sounds match up properly. (We’ll see how to make this less error-prone when we study Java objects later on.)

If you choose to implement a song other than Old MacDonald, you may need just a single array of strings, or perhaps three or four, depending on the specific structure of your song. The main idea is to discover the parts of repeated verses that vary from verse to verse, and to store them as arrays of Strings.

For example, if you chose to generate lyrics to The Twelve Days of Christmas, you might use three arrays, one each for the gifts, the names of the numbers as such (also called cardinals; no relation to the birds in the song) and the names of the numbers when used for order (also called ordinals):

```String[] gifts = { "partridge in a pair tree", "turtle doves", "French hens", ... };

String[] cards = { "a",   /* or "one" */       "two",          "three",       ... };

String[] ords  = { "first",                    "second",       "third",       ... };
```
(Note the “cheap trick” used here of starting the cardinal number names with "a" rather than "one": this will make the words work out better for the actual song.) Of course, since the cardinal number names are always used right adjacent to the gifts, you could simply combine those two parts ... but the way I’ve done it here would allow you to vary the order of the gifts to suit your taste, without requiring any other changes (except perhaps for singular versus plural).

## Generating the Verse Structure

The verse structure of cumulative songs varies a lot with the specific song, but they share the common idea of repeating older lyrics after newer ones are introduced. In general, this will have the structure of two nested loops. Try running this code to see the idea (you can cut and paste this right into Dr. Java’s interactions window):

```for(int i=0; i<7; i++) {

for(int j=i; j>=0; j--) {

System.out.print(j + " ");
}
System.out.println();
}
```

Here the outer loop counts up from 0 through 6 inclusive (up to less-than-7), but the inner loop counts down from the outer loop number (i) down to and including 0. It probably seems more natural to use a limit of 1 rather than 0, but remember that Java arrays are indexed starting from 0, and so we will want to use that kind of counting in order to access all the elements of the array. (How would you change the loop above to start at 1 and include 7?)

You can also see the general pattern more “graphically” by replacing the numbers with simple asterisks, in order to generate a triangular shape, as follows:

```for(int i=0; i<10; i++) {

for(int j=i; j>=0; j--) {

System.out.print("*");
}
System.out.println();
}
```

As with Old MacDonald, most songs will have some parts of the lyrics (refrains, etc.) that fit into this general pattern in other places than the middle “counting” portion: these can usually be included by judicious placement of code in one of several places:

• before the outer loop for lyrics which begin the whole song, but don’t get repeated with each verse;
• between the loop headers for lyrics which begin each verse, but don’t get repeated for each new item (or whatever) that is introduced;
• after the inner loop for lyrics which are repeated at the end of each verse;
• after the outer loop for lyrics which end the whole song, but don’t get repeated with each verse.

For the specific case of Old MacDonald, we can put one refrain each right before and after the inner loop, and include the introduction of the new animal right after the first refrain, but before the inner loop.

In my solution, I also used String constants and String-returning methods as a way to capture some of the other structure of the song. For example, when calling out the animal sounds, I used a method that doubles the sound (e.g., “moo-moo”) and places these doubled sounds in the context of a single line:

```static String herethere(String sound) {

return ("With a " + dub(sound) + " here and a " + dub(sound) + " there");

}
```
Judicious use of String constants and methods like this one can make it much easier to see the “forest” of the overall structure of the song rather than the “trees” of the individual lyric words.

## Longer Sample Output

Here's a longer sample output of the Old MacDonald song using seven animals in all:

```Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a pig, E-I-E-I-O,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a cow, E-I-E-I-O,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a horse, E-I-E-I-O,
With a neigh-neigh here and a neigh-neigh there,
Here a neigh, there a neigh, everywhere a neigh-neigh,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a chicken, E-I-E-I-O,
With a cluck-cluck here and a cluck-cluck there,
Here a cluck, there a cluck, everywhere a cluck-cluck,
With a neigh-neigh here and a neigh-neigh there,
Here a neigh, there a neigh, everywhere a neigh-neigh,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a sheep, E-I-E-I-O,
With a baah-baah here and a baah-baah there,
Here a baah, there a baah, everywhere a baah-baah,
With a cluck-cluck here and a cluck-cluck there,
Here a cluck, there a cluck, everywhere a cluck-cluck,
With a neigh-neigh here and a neigh-neigh there,
Here a neigh, there a neigh, everywhere a neigh-neigh,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a duck, E-I-E-I-O,
With a quack-quack here and a quack-quack there,
Here a quack, there a quack, everywhere a quack-quack,
With a baah-baah here and a baah-baah there,
Here a baah, there a baah, everywhere a baah-baah,
With a cluck-cluck here and a cluck-cluck there,
Here a cluck, there a cluck, everywhere a cluck-cluck,
With a neigh-neigh here and a neigh-neigh there,
Here a neigh, there a neigh, everywhere a neigh-neigh,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a goose, E-I-E-I-O,
With a honk-honk here and a honk-honk there,
Here a honk, there a honk, everywhere a honk-honk,
With a quack-quack here and a quack-quack there,
Here a quack, there a quack, everywhere a quack-quack,
With a baah-baah here and a baah-baah there,
Here a baah, there a baah, everywhere a baah-baah,
With a cluck-cluck here and a cluck-cluck there,
Here a cluck, there a cluck, everywhere a cluck-cluck,
With a neigh-neigh here and a neigh-neigh there,
Here a neigh, there a neigh, everywhere a neigh-neigh,
With a moo-moo here and a moo-moo there,
Here a moo, there a moo, everywhere a moo-moo,
With an oink-oink here and an oink-oink there,
Here an oink, there an oink, everywhere an oink-oink,
Old MacDonald had a farm, E-I-E-I-O.
```