99 Bottles of Beer — Introducing Mahlee™

The “99 Bottles of Beer” beer song is much less inane than many popular Norwegian drinking songs that I've sung along to in bars in Bergen. The best was about a hundred of us at Zakkariasbryggen one 17th of May singing¹ [1For those that aren't Scandinavian all you need to know is that “øl” means “beer”, “og” means “and”, and “mere” means “more”.]:

Øl, øl og mere øl
Øl, øl og mere øl
Øl, øl og mere øl
Øl, øl og mere øl

However you may feel about Norwegian drinking songs, the purpose of this exercise is to write a Mahlee™ version of the “99 Bottles of Beer” song for inclusion on the 99 Bottles of Beer web site. The version I'm using here is adapted from a version used as a test case for Mahlee™.

Thread recursion

The version I'm going to write here uses thread recursion — that is it will be a recursive implementation where each recursive call will actually be executed in its own thread. By the time we have our 99 verses we will have 100 threads (the main thread plus one for each verse).

As is normal for recursion we need a base case and a recursive case. This gives me a skeleton that looks like this:

function Verse( i ) {
	if ( i ) {
		// Recursive case
	} else {
		// Base case
	}
}

function main() {
	var song = Mahlee.create( Verse, 99 ).song().result();
	FHost.echo( song );
}

The recursive case

Let's look at one of the middle versus to get some idea of what they look like:

68 bottles of beer on the wall, 68 bottles of beer.
Take one down and pass it around, 67 bottles of beer on the wall.

I'm going to rather arbitrarily split the calculation into three parts:

bottles—Will return the bottles part of each verse. For any given verse it only depends on how many bottles there currently are.
verse—Will return the full text for a given verse. This will need to know the number of bottles from the next verse.
song—Will return the full text of the song from a given verse. This is the real recursive function as it will need to assemble the song from the previous verse's version of the song and its own verse.

We can see here that the bottles will comprise a number and the text “bottles of beer”. Any more and we won't be able to reuse the same string due to the ending of the first line of each verse. This gives us:

		this.bottles = function() {
			if ( i == 1 )
				return "1 bottle of beer";
			else
				return i + " bottles of beer";
		}

Note that there is a special case for when we're down to one bottle because of the pluralisation rules in English.

A verse can be written in terms of this function with one small problem:

		this.verse = function() {
			return this.bottles() + " on the wall, " +
						this.bottles() + ".\n" +
					"Take one down and pass it around, " +
						??? + " on the wall.";
		}

We need the bottles for the next verse. We have a similar requirement of needing something from the next verse in order to build the song:

		this.song = function() {
			return this.verse() + "\n\n" + ???;
		}

The next verse

In order to get anything from the next verse we need to perform the recursive step. We'll do that by creating a new Verse object which we can reference.

		this.next = Mahlee.create( Verse, i - 1 );

Now we can write the verse and song members to use this:

		this.verse = function() {
			return this.bottles() + " on the wall, " +
						this.bottles() + ".\n" +
					"Take one down and pass it around, " +
						this.next.bottles().result() + " on the wall.";
		}
		this.song = function() {
			return this.verse() + "\n\n" + this.next.song().result();
		}

Hopefully it should be fairly clear how this recursion gives us the result we want.

Timing difference

At the moment we're using threads, but we're not being very smart about how we're using them. We can do better by starting the calculation in the sub-thread the moment we make it and then checking back later for the result. Here's one way of doing it:

		this.next_bottles = this.next.bottles();
		this.next_song = this.next.song();

		this.verse = function() {
			return this.bottles() + " on the wall, " +
						this.bottles() + ".\n" +
					"Take one down and pass it around, " +
						this.next_bottles.result() + " on the wall.";
		}
		this.song = function() {
			return this.verse() + "\n\n" + this.next_song.result();
		}

This is actually much better in that we are now starting the calculation as soon as possible and fetching the result as late as possible. When writing multi-threading applications this processing pattern will often give the best overall performance.

The base case

The base case is so simple I'm just going to list it straight out:

		this.bottles = function() {
			return "no more bottles of beer";
		}
		this.verse = function() {
			return "No more bottles of beer on the wall, " +
						"no more bottles of beer.\n" +
					"Go to the store and buy some more, " +
						"99 bottles of beer on the wall.";
		}
		this.song = this.verse;

I've just hard coded the bottles and the verse functions here. I suspect that this would bother me more if I were doing this as anything other than a Mahlee™ demonstration.

Also note that because the verse and the song are the same for the last verse I just re-use the verse member for the song member.

Full listing

For the final listing I've made two additional changes:

The number of bottles that are to be used can now be passed in via the command line.
Because of this the recursive creation of the next Verse has to change slightly to pass on the number of bottles for the first verse and the last verse has to make use of this information.

function Verse( i, first ) {
	if ( i ) {
		this.bottles = function() {
			if ( i == 1 )
				return "1 bottle of beer";
			else
				return i + " bottles of beer";
		}
		this.next = Mahlee.create( Verse, i - 1, first || this.bottles() );

		// Start calculations for next verse
		this.next_bottles = this.next.bottles();
		this.next_song = this.next.song();

		this.verse = function() {
			return this.bottles() + " on the wall, " +
						this.bottles() + ".\n" +
					"Take one down and pass it around, " +
						this.next_bottles.result() + " on the wall.";
		}
		this.song = function() {
			return this.verse() + "\n\n" + this.next_song.result();
		}
	} else {
		this.bottles = function() {
			return "no more bottles of beer";
		}
		this.verse = function() {
			return "No more bottles of beer on the wall, " +
						"no more bottles of beer.\n" +
					"Go to the store and buy some more, " +
						first + " on the wall.";
		}
		this.song = this.verse;
	}
}

function main( number ) {
	var song = Mahlee.create( Verse, number ? parseInt( number, 10 ) : 99 ).song().result();
	FHost.echo( song );
}

It's certainly possible to write a shorter version, but this isn't too bad considering that we're managing so many threads. In fact, this only has two extra lines of code compared to a similar approach in normal JavaScript (the early call of bottles and song in the constructor). That's a tiny overhead for a multi-threaded application.

Note though that due to the tiny amount of calculation this runs much faster in the single threaded Mahlee™ host extension rather than the multi-threaded one.

Categories: Mahlee™