99 Beers!

I was perusing Lau Jensen's excellent Best In Class blog. Now, Lau Jensen is a Clojure-person, and that's one of the best languages out there in my opinion. So, when he compares it to other languages, that's never a nice experience to those being compared.

Personally, I think OO and infix methods (dot-style or operator notation) are essential for a well-rounded, popular language, which makes something of an uncrossable chasm between Clojure and me for "serious" stuff.

At any rate, his recent second take at Python got me curious about the Rosetta Code project. First, I got curious about his discussion of the Counting Programming Example problem, and the Python and Clojure implementations shown. I took my own shot at it, going the parallel way like the Clojure version, but I'm unsatisfied with the result. Sure, it is short, but it lacks... sense of cohesion, I guess. In fact, I just changed it from what I submitted to Rosetta. Here:

import java.net.{URL, URLEncoder}

val URLs = Map(
  'allTasks -> "http://www.rosettacode.org/w/api.php?action=query&list=categorymembers&cmtitle=Category:Programming_Tasks&cmlimit=500&format=xml",
  'oneTask -> "http://www.rosettacode.org/w/index.php?title=%s&action=raw"
  )
def oneTaskURL(title: String) = URLs('oneTask) format URLEncoder.encode(title.replace(' ', '_'), "UTF-8")

def getPage(url: String) = scala.io.Source.fromURL(new URL(url))(scala.io.Codec.UTF8)

val pattern = "(?i)==\\{\\{header\\|".r
def countPattern(title: String) =
  pattern findAllIn (getPage(oneTaskURL(title)) mkString) length

val allTasks = scala.xml.parsing.XhtmlParser(getPage(URLs('allTasks)))
val counts = 
  for (task <- allTasks \\ "cm" \\ "@title" map (_.text)) 
  yield actors.Futures.future((task, countPattern(task)))

counts map (_.apply) map Function.tupled("%s: %d examples." format (_, _)) foreach println
println("\nTotal: %d examples." format (counts map (_.apply._2) sum))

I won't bother explaining it, because I think it is self-explanatory, if a bit arcane. Scala's partial XPath support is put to good use, and future just works here. In case you aren't familiar with Future, it just detaches a thread to handle some computation you passed, and then, when you call "apply", it joins that thread and get the result. Sort of. If anyone wants to take a go at making this better, I'd like to see the results.

At any rate, while perusing the Rosetta site, I noticed that 99 Bottles of Beer problem allowed for creativity in reaching a solution. Most examples went for conciseness. My own concise Scala looks like this:

99 to 1 by -1 foreach {n =>
  println("""|%d bottles of beer on the wall
             |%d bottles of beer
             |Take one down, pass it around
             |%d bottles of beer on the wall\n""".stripMargin format (n, n, n -1))}

However, as I thought about the problem and how to make it interesting, I decided to model it with Actors. Sure, it is an absolute overkill for this problem, but I think the modelling itself shows off Actors pretty nice.

Here it is:

object Song {
  import scala.actors._
  import scala.actors.Actor._
  
  abstract class Beverage { def name = this.toString.toLowerCase }
  case object Beer extends Beverage
  
  object Wall {
    private var contents: List[Beverage] = Nil
    
    def count(what: Beverage) = contents count (_ == what)
    def isEmpty = contents isEmpty
    def stock(n: Int, what: Beverage) = contents :::= List.fill(n)(what)
    def get(what: Beverage) {
      def takeOneFrom(contents: List[Beverage]): List[Beverage] = contents match {
        case `what` :: rest => rest
        case other :: rest => other :: takeOneFrom(rest)
        case Nil => println("Sorry, we are out of "+what.name); Nil
      }
      contents = takeOneFrom(contents)
    }
  }

  sealed abstract class Messages
  case class SingSong(what: Beverage) extends Messages
  case class HowManyMore(what: Beverage) extends Messages
  case class HowManyNow(what: Beverage) extends Messages
  case class ThereAreStill(n: Int, what: Beverage) extends Messages
  case class ThereAreNow(n: Int, what: Beverage) extends Messages
  case class Gimme(what: Beverage) extends Messages
  case class HereIs(what: Beverage) extends Messages
  case object ClosingTime extends Messages
  
  def plural(count: Int, noun: String, nouns: String) = if (count == 1) noun else nouns
  def countIt(n: Int, what: Beverage) = "%d %s of %s" format (n, plural(n, "bottle", "bottles"), what.name) 
  
  object Waitress extends Actor {
    def tellThem(what: String) = println("%s on the wall" format what)
    def act = loop {
      react {
        case HowManyMore(it) =>
          val total = Wall count it
          tellThem(countIt(total, it))
          reply (ThereAreStill(total, it))
        case Gimme(it) =>
          print("Take one down, ")
          Wall get it
          reply (HereIs(it))
        case HowManyNow(it) =>
          val total = Wall count it
          tellThem(countIt(total, it))
          if (Wall isEmpty) {
              reply (ClosingTime) // You don't have to go home, but you can't stay here
              exit
          } else
          reply (ThereAreNow(total, it))
        case _ =>
          println("You wish, honey!")
      }
    }
  }
  
  object Patrons extends Actor {
    def act = loop {
      react {
        case SingSong(what: Beverage) =>
          Waitress ! HowManyMore(what)
        case ThereAreStill(n, it) =>
          println(countIt(n, it))
          Waitress ! Gimme(it)
        case HereIs(it) =>
          println("pass it around")
          Waitress ! HowManyNow(it)
        case ThereAreNow(n, it) =>
          println()
          Waitress ! HowManyMore(it)
        case ClosingTime =>
          exit
        case _ =>
          println("Say what???")
      }
    }
  }
  
  def Sing99Beers = {
    Wall stock (99, Beer)
    Waitress.start
    Patrons.start
    
    Patrons ! SingSong(Beer)
  }
}

Now, this code has a structure to it. To begin with, there are two concerns. First, there is the "wall", where the beverages are kept, and the beverages themselves. The beverages are modeled as case objects derived from a sealed class, which is an alternative to enumerations, as I have discussed in my Matrix series.

I suppose the wall ought to be synchronized, but I'm working with an assumption here. Only one agent can get things from the wall, and the wall can only be restocked while that agent is not working. It would be nice to have this enforced by the compiler, and a paper from the EPFL guys gives me hope of being able to in the future.

The second concern is the interaction between the patrons and the waitress. Again, it is further divided into two: the messages they exchange between themselves, and the actors themselves and their behavior.

Defining the messages as a subclass from an abstract class doesn't really give me anything. The Actors in the standard library are untyped, so they can receive anything as message. There is one typed Actor library for Scala, though, which is a model much more to my liking. If used, I'd not have to provide for handling of unknown messages.

The song gets sang as the patrons ask how many beers there are, the waitress answers, the patrons order one beer, get it, and then ask again how many beers there are. No actor ever waits for the answer. Instead, they finish their present reaction, and wait for another message -- which might be the answer they were waiting for, or not. What the actor do is solely defined by what message they received.

To get the song started, the wall is first stocked, patrons and waitress started, and, then, the patrons are asked to begin the song. I'm pretty sure bar owners everywhere hope it would be this easy to get people drinking until the stock is sold-out. :-)

I hope you enjoyed this post half as much as I enjoyed writing that code! If you are feeling the need to write some code right now, try modifying the program so that, when the stock of whatever is being consumed is finished, the patrons ask what else there is, and start a new song on a new beverage.

Or, better yet, why don't you find a fun problem on Rosetta Code, for which no solution exists in a language you like, and submit a solution to it? It's as easy as editting a wiki article, so go for it!