Friday, October 30, 2009

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!

7 comments:

  1. Like this post lots, and some comments and question

    "The Actors in the standard library are untyped". I think it is because Scala's Actor lib is inspired by Erlang,a dynamic type language.

    The "Wall" object can be an private object within Waitress.

    In Wall's "takeOneFrom" method, "case Nil => println("Sorry, we are out of "+what.toString.toLowerCase); Nil" should it be what.name ?

    last thing, why there is HowManyMore message? is HowManyNow enough for this case or I miss something?

    ReplyDelete
  2. Thanks, Yuan.

    That's a good guess about the Actor library, but I suspect the real reason is that the type system wasn't powerful enough at the time to handle it.

    I considered Wall being private to Waitress, but the Wall belongs to the pub, not to the Waitress. That's technically irrelevant here, but good models are true to their business domain.

    Yes, it should be "what.name" there! I'll fix it. That's what happens when you refactor without IDE support. :-)

    The difference between HowManyMore and HowManyNow is the reply given to the Patrons. Note that the Patrons react differently to ThereAreStill and ThereAreNow. Without this, the song would not be correctly reproduced.

    ReplyDelete
  3. Hi I appreciate this example, it's really educational. I've been trying to compile it.. other than List.fill not being in 2.7.6, I've this question which I can't seem to answer:

    What is the purpose of the following two match statements
    case `what` :: rest => rest
    case other :: rest => other :: takeOneFrom(rest)

    is other a keyword? and why is the apostrophe the ' character different in the `what`? What's the significance?

    Thank you again for the excellent example. I enjoyed it very much, as well as the whole fun cool part about modeling it with Actors

    ReplyDelete
  4. Hi, John!

    I really ought to have gone into details about how things work. In fact, I quite possibly will do so, but, for now, let's address your questions.

    The code was tested on Scala 2.8, but I didn't expect it not to run on Scala 2.7. I'm surprised List.fill isn't available on 2.7, but I expect it should be easy to replace. Looking up the API on object List, List.make(n, what) will do the same thing.

    As for the case statements, if you are unfamiliar with Scala, the expression between "case" and "=>" is a "pattern match". That means the compiler will verify if the expression passed to "match" matches the expression for each case statement, and select the first where a match happens.

    Starting with the simpler one, "other :: rest" means the expression passed can be matched to a list formed by a head element, here called "other", and a tail list, called "rest". I chose "other" and "rest" arbitrarily. If I followed the reallyLongNamesJavaConventionOfStyle, I might have called "other" as "someOtherBeverage".

    The only list that cannot be divided into a head and a tail is the empty list. So the intention here is, match any list other than the empty one, and then return the first element of this list and the rest of this list minus one beverage of the proper type (takeOneFrom(rest)).

    If the match can be made (ie, the list is not empty), then the first element of that list will be assigned to a val called "other", and the rest of the list will be assigned to a val called "rest". Note that the type of "other" will be "Beverage" and the type of "rest" will be "List[Beverage]".

    Now, I know "other" is not the beverage I want because, if it were, I would have matched it in the first case statement.

    When I write an identifier between ` in a case statement, I'm telling the compiler that I want to compare the value passed to the value of that identifier.

    So, the pattern matching expression "`what` :: rest" means "a list formed by an element equal to "what" as its first element, followed by any list".

    In which case I return just the rest of the list, and, thus, take "what" out.

    I hope you could follow it. You may try typing the following in the REPL:

    val (other :: rest) = List(1,2,3,4)
    val (`other` :: tail) = List(1,2,3,4)
    val (`other` :: tail) = rest

    This works just like the case statements, except an exception is thrown if the match can't be made, such as the last line.

    ReplyDelete
  5. Hey, thanks for enjoying the site! Rosetta Code is my baby*, and I love to hear when people derive enjoyment from encountering it.

    You likely already saw my "hotshot" comment in Lau's blog, so I don't think I need to link to the list of tasks not yet implemented in Clojure. (Though a massive list of all such reports may be found here: http://rosettacode.org/wiki/Category:Unimplemented_tasks_by_language ...

    Don't limit yourself to just filling in examples, though. If you know at least a couple languages, create a task! Look around at the various tasks already on the site, and consider a task that might showcase some innate capability of your preferred language. Remember, though, that your task needs to be able to be compared to other languages; The task demonstrates how to do something in your language, but at the same time the presence of those other languages helps those familiar with them better understand your code by analogy. There's a balance between specificity and flexibility, and there's an art to finding it, but that doesn't mean you shouldn't try.

    * To the extent that I founded it, maintain the server and guide the community from time to time.

    ReplyDelete
  6. Ah, I didn't realize ` is a key on my keyboard! I actually fired up character map and kinda noticed it underneath the tilda at the corner of the keyboard while looking intensely at the screen.

    Thanks for the explanation! I understand what it does now! I was trying to get it to work with
    case what :: rest => rest but the compiler told me the second statement is unreachable. I thought using what would kinda be like a closure but I'm only partly right in that when putting variables in the matching statements it actually assigns values to the variables hence the ` character is required to only match but not assign. I hope I'm reading it right.

    Thanks again! Really appreciate your time.

    ReplyDelete
  7. @John: your understanding looks correct to me. The ` character has another meaning in Scala, which is to enable arbitrarily name identifiers.

    For example, if you wanted to call the method "yield" on Java's Thread, you would not be able to write it "Thread.yield", because it is a keyword, and thus reserved. You can write it as this, though: Thread.`yield`. This way, it gets interpreted as a keyword.

    @Michael: I have a thing for unusual languages, and could definitely fill in many blanks. :-) Alas, I don't have time for it. I just hope to be able to fill in some tasks now and then.

    Anyway, thanks for the comment. I hope I was able to draw more eyes toward your project!

    ReplyDelete