Tail Calls, Tail Recursion, TCO

I'm going to tell a story that I think explains Tail Calls, Tail Recursion and TCO. I might decide to post some code about it, I might not. I don't actually find it necessary. First, a few definitions. If they aren't clear now, the stories should make them so.

• Tail Call - When the last thing a function does is call another function, and then immediately returns the result of that call.
• Tail Recursion - Just a special case of tail call where the function tail called is the same as the caller function. Tail Recursion won't come up again in this post, so if the definition isn't clear, don't worry about it.
• Tail Call Optimization - A compiler technique for avoiding adding an activation record to the stack for a tail call. (However, I don't like the word 'optimization' here. It is more like the correct implementation. More on that later.)

Regular Function Calls

Here, I tell a story about normal function calls, and introduce the theme and characters that will be used throughout the rest of this post.

Imagine that you have the munchies (feel free also, to imagine any reason why you might have the munchies :). Your particular craving at the moment is popcorn. A big bucket of salty, buttery popcorn. Standing next to you is your friend, Mr. Salt. He owns a salt shaker. Standing next to Mr. Salt is his friend Mr. Butter. Mr. Butter owns one of those liquid butter pumping machines that you see at the movie theaters. You don't really care that that happens to be a heart attack in the making. In fact, you don't really care about much of anything right now except the munchies and getting your popcorn :) Standing next to Mr. Butter is his friend Mr. Popper. Mr. Popper has a pop corn popper and a giant bin full of popcorn, and he's more than happy to dish some out.

You turn to Mr. Salt and ask, "like, duuude...I'd really like some salty, buttery, delicious popcorn right now. Could you get it for me? Here's five bucks." You hand him the five dollars.

Mr. Salt says, "Sure, but just give me a second to get some buttery popcorn and I'll put some salt on it for you." He then turns to Mr. Butter and says, "I can haz buttery popcorn? I got 5 bills." Mr. Butter replies, "Oh hai, u can haz. Hold on a sec."

Mr. Butter turns to Mr. Popper and asks him for some popcorn, handing him the 5 bucks. Mr. Popper obliges, and hands Mr. Butter a giant bucket of freshly popped plain popcorn.

Mr. Butter takes the popcorn, puts some butter on it, and hands it to Mr. Salt. Mr. Salt then takes the buttery delicious popcorn from Mr. Butter, puts a pile of salt on it, and hands it to Mr. Hungry Man (that's you).

These are examples of normal function calls, not tail calls. A tail call, once again, is when you make a function call, and have nothing left to do but return the result. But Mr. Butter and Mr. Salt did have work left to do with the result. Mr. Butter had to take the result (the plain popcorn) and apply butter to it. Similarly, Mr. Salt had to take the buttery popcorn and apply salt to it. Mr. Hungry Man had to eat the popcorn. (Mr. Popper didn't actually make a function call at all, he just immediately returned a result. Think 'def seven = 7').

Notice that each person in the chain is like an activation record on the stack, and that they all eventually have to be popped off the stack.

Tail Calls

To demonstrate tail calls, we only need to change the story slightly. You, (Mr. Munch, Mr. Hungry Man, Sir Smokealot) have decided to go on a diet. You ask Mr. Salt for some plain popcorn. He turns to Mr. Butter and asks him for plain popcorn. Mr. Butter turns to Mr. Popper and asks for some plain popcorn.

Here is where we really demonstrate the difference between a regular function call and a tail call.

Mr. Butter takes the popcorn from Mr. Popper and does nothing with it at all except turn around and hand it to Mr. Salt. He doesn't first apply butter to it. And, exactly the same, Mr. Salt takes the plain popcorn from Mr. Butter and turns around and hands it to Mr. Hungry Man. He doesn't put any salt on it.

Those are tail calls. Remember the definition: "When the last thing a function does is call another function, and immediately return the result of that call." The last thing those middle men did was ask someone else to get them something, took that thing from them and gave it to whoever asked them for it.

One important thing to notice here. I haven't talked at all about tail call optimization. Mr. Salt and Mr. Butter are still on the stack. They still take up space on the stack, and they still need to eventually be popped off the stack.

Before I talk about TCO, let's talk about the need for TCO.

The Problem

Imagine simply, that the line of people between you and the popcorn was 1000 dudes long. You still just want some plain popcorn, but have to go through 999 middle men to get it. That's 999 guys on the stack. 999 guys that eventually have to get popped off the stack as well.

Ok, fine. That might work. I guess it depends on how big your stack is.

But now imagine that the line is one million men long! 999999 middle men. 999999 guys on the stack right? WRONG. Stack Fricken Overflow Dood.

In the JVM world, this is what you get. There are of course techniques to avoid it, but you're severely limited on the JVM because it doesn't support tail call optimization (it doesn't have a tailcall byte code).

Tail Call Optimization

Okay. Now is the part where I change the story to describe TCO, and how it works. It's actually very easy.

You turn to Mr. Salt and say, "Can I please have some plain popcorn?" He turns the Mr. Butter and says, "Mr. Hungry Man would like some plain popcorn. Can you please get it for him? I don't really feel like it. In fact, I'm out of here." Mr. Salt then goes home for the day.

Mr. Butter turns to Mr. Popper and says the same thing: "Mr. Hungry Man would like some plain popcorn. Can you please get it for him? I don't really feel like it. In fact, I'm out of here." Mr. Butter than also goes home for the day.

Mr. Popper gets a bucket of popcorn and simply hands it to Mr. Hungry Man.

And that folks, is the end of the story. Case closed!

Ok fine, I guess it deserves at least a little more explanation. Mr. Salt, who knows he has a tail call where he would just take the result and give it to Mr. Hungry Man, can instead just have Mr. Butter give it to him. It makes absolutely no difference (ok a tiny difference that I'll explain later) who hands the popcorn to Mr. Hungry Man, so he might as well leave. In technical terms, Mr. Salt and Mr. Butter going home means they go off the stack. This could be implemented in a few different ways - maybe the top activation record is completely torn off the stack, or maybe it is just modified accordingly. Either way, this strategy saves stack space, and a little computation time too (remember that string of a million gotos that would have happened if the stack didn't overflow, all those instructions are saved).

Conclusion

I'd like to take this time to point out a confusion, or at least a point of contention in language designer circles (academics and non-academics alike). Because the term itself 'TCO' contains 'O' many people view TCO as just that, an optimization, while others view it simply as correct language design and implementation.

I fall into the latter camp. I think it is analogous to garbage collection. I don't think most programmers would consider GC as an optimization, but simply correct implementation. It isn't ok to just run out of heap space because you didn't bother to implement a GC. And so, it isn't ok to run out of stack space just because you didn't bother to correctly implement tail calls.

I believe this post is consistent and self contained and I don't want to spoil it with code, too many technical details, or language specific details. For that reason, I believe a Scala related follow up post is in order. It would explain things like:

• How the Scala compiler can turn tail recursive functions into while loops, and why it can't do so with non-final functions.
• What @tailrec does.
• Mutually recursive functions, trampolining and scala.util.control.TailCalls.

I also think I could extend this story to explain continuations. Maybe someday I'll get the chance to do that as well.

References

• Lambda: the ultimate goto

http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf

• Fortress Blog - ObjectOrientedTailRecursion

http://tinyurl.com/yjbgks3

• Rich Dougherty - Tail Calls, Tail Rec, Trampolines

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

• John Rose - Tail Calls in the JVM

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

• Matthias Felleisen - A Tail-Recursive Machine with Stack Inspection

http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf

• Stack Overflow - @tailrec and non-final methods

http://bit.ly/stacko-tailrec

Code Styles and Readability

Today at work we went on a quest to make a piece of code as readable as possible. I'm not fully convinced that we've succeeded entirely, but we learned a few things along the way.

The problem we're trying to solve is pretty simple. Given an activation record which represents the last call on the call stack, generate a List of Strings to be used in building the stack trace. This will require going all the way up to the first call on the stack by following parent pointers, grabbing the name of each procedure.

Before we begin, we need to understand a few things about the system.
One could imagine these simple classes:

case class Procedure_V1(name: String)
case class Activation_V1(procedure: Procedure, parent: Activation)

If that's all there was, there probably wouldn't be much to write about. I'll give a small bit more detail. In our world, a Procedure holds a List of Commands that it executes one by one until it is done. Any Command in this list could be a primitive, or a call to another procedure. If the Command is a primitive, it can just be executed on the spot. One example of a primitive is +. If the command is a call to another procedure then upon execution of this Command, a new Activation gets created. So the objects now look like this:

case class Command_V2(name:String)
case class Procedure_V2(name: String, commands: List[Command])
case class Activation_V2(procedure: Procedure, parent: Activation)

There's one minor catch that makes this whole thing interesting: any particular Activation might need to put two different entries into the stack trace. 1) Its own procedures name, and possibly 2) The name of its parent's current command. I wish I had time and space enough to explain why, but that's simply out of scope. For now, I'll just explain some simple rules.

A command should show up in the stack trace only if it calls other code. Activations have a return address which an index into it's parents commands List. It points to currently running command in the parent Activation. These rules allows us to write the final versions of the classes:

case class Command(name:String, callsOtherCode: Boolean)
case class Procedure(name: String, commands: List[Command])
case class Activation(procedure: Procedure, parent: Activation, returnAddress:Int)

Lets also say that these classes are sealed (or that we can't modify them). With these, we can take a stab at the original problem.

def callStack_V1(act: Activation): List[String] = {
  val parentCommandMaybe: Option[String] = Option(act.parent).flatMap(p => {
    val c = p.procedure.commands(act.returnAddress)
    if(c.callsOtherCode) Some(c.name) else None
  })
  List(Some(act.procedure.name), parentCommandMaybe).flatten :::
          callStack_V1(act.parent)
}

This was the first version I wrote. I liked it then, I still like it now. But, I wanted to see if I could make it better. First, lets see if we can clean up that last line. The list creation is a little confusing.

def callStack_V2(act: Activation): List[String] = {
  val parentCommandMaybe: Option[String] = Option(act.parent).flatMap(p => {
    val c = p.procedure.commands(act.returnAddress)
    if(c.callsOtherCode) Some(c.name) else None
  })
  act.procedure.name :: parentCommandMaybe.toList ::: callStack_V1(act.parent)
}

Only slightly better. Maybe if we remove the recursion things will be nicer.

def callStack_V3(act: Activation): List[String] = {
  Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList.flatMap { a =>
    val proc = act.procedure.name
    val parentCommandMaybe: Option[String] = Option(a.parent).flatMap(p => {
      val c = p.procedure.commands(a.returnAddress)
      if (c.callsOtherCode) Some(c.name) else None
    })
    act.procedure.name :: parentCommandMaybe.toList
  }
}

That first bit before the first flatMap turns the stack into a List[Activation]. While that idea is simple enough, the code to do it really isn't. And, the remainder of the code is really hard to follow too. I still manage to struggle to fully understand a single flatMap sometimes, let alone two. Sure the type annotations help explain what is happening, but I still felt I could do better. Let's keep the same idea, but refactor a bit and see if that helps.

def unfold(act: Activation) =
  Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList

def callStack_V4(act: Activation): List[String] = {
  unfold(act).flatMap { a =>
    val parentCommandMaybe: Option[String] = Option(a.parent).flatMap(p => {
      val c = p.procedure.commands(a.returnAddress)
      if (c.callsOtherCode) Some(c.name) else None
    })
    act.procedure.name :: parentCommandMaybe.toList
  }
}

Maybe thats ok, it gets some of that clutter out of the way and let's us think. But lets take a complete step back and try an imperative version. All the flattening is still hurting my head.

def callStackImperative(act: Activation): Seq[String] = {
  val buf = collection.mutable.ListBuffer[String]()
  for(a <- unfold(act)) {
    buf += a.procedure.name
    if (a.parent != null) {
      val c = a.parent.procedure.commands(a.returnAddress)
      if (c.callsOtherCode) buf += c.name
    }
  }
  buf
}

This is a case where an imperative style actually does quite well. I usually try to avoid this style like the plague, but in this case theres little doubt that this code is simple.

I still thought I could do better, so I continued. This time with a Racket friend.

def callStackSchemer(act: Activation): List[String] = {
  def callStackInner(act: Activation): List[String] = {
    if (act == null) Nil
    else {
      val rest = callStackInner(act.parent)
      def parCmd = act.parent.procedure.commands(act.returnAddress)
      act.procedure.name ::
        (if (act.parent != null && parCmd.callsOtherCode) parCmd.name :: rest
         else rest)
    }
  }
  callStackInner(act)
}

The advantage of this approach is that it could be read by a 10 year old. Ok maybe not 10. But, there are no for comprehensions, options, or flattening bits here. However, I do think there is a little bit of mixing up what is happening with how its happening. That is, the result building is mixed up with the structural recusion on the Activation. For this little function, it almost certainly doesn't matter that much. For something larger, it might.

Let explore a different topic for a bit. Sometimes, even with inner defs, pulling something outside of the body of a function helps clear out the clutter and makes it more readable. We did this already with unfold. There are tradeoffs of course, such as you then have a function in the top level that is only being used in one place. But, lets try it again anyway and see where it gets us..

def parentCommandMaybe_V1(act: Activation): Option[String] =
  Option(act.parent).flatMap(p => {
    val c = p.procedure.commands(act.returnAddress)
    if (c.callsOtherCode) Some(c.name) else None
  })

Pulling that out also helps me realize just how complicated that bit is. Maybe we can do better just on this part. Here are two attempts.

def parentCommandMaybe_V2(act: Activation): Option[String] =
  if(act.parent == null) None
  else{
    val command = act.parent.procedure.commands(act.returnAddress)
    if(command.callsOtherCode) Some(command.name) else None
  }

def parentCommandMaybe_V3(act: Activation): Option[String] =
  for{p <- Option(act.parent)
      c = p.procedure.commands(act.returnAddress)
      if c.callsOtherCode}
  yield c.name

To be quite honest, none of these solutions are glorious. I'm tempted to use V2 because any knuckehead could read it, and its of comparable size. I could have easily decided on V1 or V3 because we don't have any knuckeheads on our team. We do however, occasionally have students on the team and we are attempting to open source our code. Is that a good reason to dumb down the code? No, certainly not. But, if a particular function is of comparable size, then maybe it is a good idea. Or maybe not, maybe leaving the more advanced constructs (like for comprehensions) would make code readers learn more about the language that they are using. I'm undecided on this. Given the lack of wanting to make a decision here, I'll just choose V3.

Better solutions to this are most welcome.

Now that we've pulled that out, we can rewrite our function.

def callStack_V7(act: Activation): List[String] = {
  unfold(act).flatMap { a => 
     act.procedure.name :: parentCommandMaybe_V3(act).toList
  }
}

I think this is a really nice version. But...now that we've cleaned up some of the helper methods, lets see what things look like if we put them back in.

def callStack_V8(act: Activation): List[String] = {
  def unfold(act: Activation) =
    Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList
  def parentCommandMaybe_V3(act: Activation): Option[String] =
    for{p <- Option(act.parent)
        c = p.procedure.commands(act.returnAddress)
        if c.callsOtherCode}
    yield c.name
  unfold(act).flatMap { a => 
    a.procedure.name :: parentCommandMaybe(a).toList
  }
}

Not bad. It may be a few lines longer than version 1, and it took quite a while to get here, but I do think this version is the best we can do. 'We' being my team. Finally, I'll add in some comments and call it a day. It would be nice if the code was so blatently obvious that this wasn't needed, but it's ok. Comments are helpful.

/**
 * Return a List representing the call stack.
 * The list includes procedure names and any commands
 * that call other code.
 * @param act - the final call on the stack.
 **/
def callStack(act: Activation): List[String] = {
  // unfold turns an activation into
  // List(act, act.parent, act.parent.parent ... )
  def unfold(act: Activation) =
    Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList
  // if an activations parent is executing a command that can trigger
  // other code, it also needs to be added to the stack trace.
  def parentCommandMaybe(act: Activation): Option[String] =
    for{p <- Option(act.parent)
        c = p.procedure.commands(act.returnAddress)
        if c.callsOtherCode}
    yield c.name
  // flatMap because each activation can result in 1 or 2 entries
  unfold(act).flatMap { a => 
    a.procedure.name :: parentCommandMaybe(a).toList
  }
}

If you can write this better, please do. Send it to me and I'll learn something.

App Inventor Review (plus some functional programming)

I App Invented all day today. Half of this was because it was fun, the other half was because it took all day to get anything reasonable done. Before I get into this at all, let me say that I had fun. I think App Inventor could be a cool tool in the future, and it was relatively bug free and nice to use. I think they have done a good job on it and I'm very happy for them. I don't know what their plans are for adding more language features in the future, but even though it was fun, I won't be using it again until they add a few things. I'll explain.

But lastly, before I do, I want to say that I hope I simply haven't overlooked anything. These are my impressions after using it for a day, and they are impressions from my language designers perspective. If I've managed to overlook some capabilities because of failure to read everything I was supposed to read, then I apologize. I don't think this is the case though.

After growing up and becoming a decent functional programmer (and/or growing out of Java), whenever I try to learn a new language that doesn't have certain functions that I've grown accustomed to (like head, tail, list-to-string, string-to-list, filter, map, flatten, and more) I find that I build them immediately and then start actually building something. Guy Steele put this so elegantly in his talk Growing a Language.

So, I set out to build them. But I found out right away that the blocks in App Inventor were severely limited. You do have the ability to create your own functions, but there are no higher order functions so right away you lose the ability to write map and filter (without repeating the mapping and filtering logic every time). Both map and filter could be accomplished with data abstraction (albeit slightly unnaturally), but that doesn't exist either. Ok, I'll be honest, I didn't expect this higher order functions, so this is ok. I didn't really expect data abstraction either. So I'll let that slide too. But, it sure would be nice if we could have a blocks language that does have them.

App Inventor does have Lists though, and Strings. But, Strings are not Lists, and no functions are provided to convert between the two. This bit was quite frustrating. Having to write string-to-list and list-to-string seemed wrong, especially when those are two of the main data types in the system. Lists did seem to implicitly convert to Strings in certain situations, but wrapped in parens. If I simply wanted to convert [a, b, c, d, c] to "abcde", I had to use my function.

So I set out to build both of those functions, and I started with string-to-list. This is when I found out the really bad news, the one fundamental flaw with App Inventor. You can't have local variables in your procedures... Worse yet, every time you need to name something, it becomes a global variable.

• When you need a temp, create a global.
• Globals are event created for every procedure argument.

The last one is particularly bad, because if you have two operations that work on lists, you have to pick a new name for the argument to each of the functions. For example, imagine if you had to do this in Scala:

def head[A](aList:List[A]): A = ...

def tail[A](anotherList:List[A]): List[A] = ...

def toString(yetAnotherList:List[_]) = ...

And imagine further that these names followed you around wherever you go.

You might be thinking, 'Well, maybe its not too big of a problem. After all, it's probably the case that App Inventor was designed for small things, and for teaching.' Well, the global thing is a real problem. Having to explain this to beginners trying to learn would be a nightmare. Thankfully, the App Inventor team does recognize this. Hal Abelson said on this thread,

"We're planning on adding local variables (no ETA). We agree that these are important for teaching programming."

Phew. But then again, that was August 7th and we're now pushing into December. (But I know how this goes as I've been working on a couple of my own language features for over a year now.)

Now back to the second point; having every procedure stomp all over the global namespace did turn out to be a problem in a relatively small amount of code. Yes I wrote all day, but I did't really churn out that much. Part of this was because I was slowed down mucking through the UI trying to find my procedure call blocks. I ended up with so much stuff in the My Definitions thingy, that it was a nightmare to find anything. This could probably be cleaned up pretty easily if they added the ability to sort it alphabetically. But even so, the globals business is bad for other reasons too. It just sort of continues encouraging imperative programming in a very unsatisfying way. I feel dirty after it. Oh well, hopefully they can get it fixed. Like I said, I did have fun, so I'm not trying to be negative, just blatantly honest.

Ok, finally back to string-to-list. Right away I noticed that there wasn't a charAt function. There is a 'segment' function which is basically substring, but I wanted charAt. So I wrote it, and fortunately it was one of the easier functions to write. Here it is:

The first time I wrote the string_to_list function, I wrote it using globals in typical imperative style. Here it is:

Hopefully that doesn't come out too difficult to read. If it does, you can just click on it to view it bigger. I just looped until the end of the String, adding to an accumulator. The accumulator was a global, along with the loop index. This is pretty gross, but whatever, it works. I tried it without the globals, but this turned out to be even worse, I think. Well, maybe not worse, but bigger, and uglier:

This one might actually be too small to read, and I screwed up the screen shot, but you can click it. I think most of what you need is there. Because I am not using a global, I have to use recursion. But this means I have to have the index and acc parameters passed in. Because I don't want users to have to pass this in, I just used two functions. The actual meat of the function is roughly the same size as the other. Fine. We'll they are both pretty huge, so not fine...but fine.

Ok, 1/2 the day is gone and I have string-to-list and charAt written (maybe an exaggeration, I can't really remember). At this point in writing this post I went to look for list_to_string. I couldn't find it. I swear I wrote it. Didn't I? Did I not need it? This just goes to show the problems with finding things in App Inventor. It's a big pain.

So maybe I didn't write it. But I did write some others I was going to need. I've explained most of the problems that I encountered, so most of the rest of the functions can be displayed without ceremony.

Here are head and tail:

Head was fine. Tail was kind of disgusting because I had to mutate a global so that I didn't have to mutate the argument. Try explaining any of that to a beginner.

Zip suffered from problems already discussed:

Unzip also demonstrates nothing new:

Filter was problematic as I explained earlier. You can't pass lambdas around, so any time you want to filter you just have to reproduce the logic. There's no way around it. Map too (though I didn't write map, but I guess unzip is just a map). Here is a simple filter. I didn't really test it because I used a much more complicated one. But, I think it should work:

Finally, I wrote flatten. This one proved to be tricky and fun. I haven't actually used it anywhere yet, but thats ok. It was tough to figure out at first, but I got it. See if you can understand it:

Some other remarks and random comments:

• Testing was not too bad. When I had a function that didn't quite work right on the phone the first time, I could easily set up a call to it in the IDE, and see the results. That was nice. It would be much nicer to have a way to define actually test cases on these things, but no one ever seems to listen to me on that.
• Code organization was a huge problem. As procedures grew, I'd have to shift everything around. It only gives you so much vertical space. Horizontal space seemed unlimited, but it was tricky to make it grow. They have an auto-organize feature, but it did some things that I didn't want it to do, such as moving globals away from the only procedure that they were used in.
• When I named something incorrectly (I often put a dash, forgetting that it is illegal), the system yelled at me and says that it is an illegal name, but didn't say why. Then...it reverts back to whatever name was there before. So, if I had typed in a long name, I'm forced to retype it all again. that was super aggravating.
• Sometimes it would say there was an error in a procedure, but it wouldnt tell me what the error was.
• Things are slow. Yes, I know, I should expect them to be nearly as fast as typing. But, I found myself getting frustrated with just how slow things seemed. certainly, beginners won't be working as fast as myself, but there are times when I could imagine them getting frustrated too. Removing many of the globals would help. A quick-find for procedures would help too.
• Message passing, Scratch style, would be very nice. I could easily imagine different GUI components passing messages to each other. My 9 year old son uses that style in Scratch all the time and it works great.
• When there was a runtime error, it was difficult to tell what the error was. Additionally, the application would just halt. No option to continue. That seemed odd. Why not just let it continue in its current state and let the user decide to restart?
• I was pretty easily able to find things in the documentation the few times that I needed to look things up. That was nice.

That's just about it. I guess I'll conclude. I had fun, I like App Inventor. By the end of the day, I had a working game going (not described here). I think App Inventor could be made pretty awesome by fixing some of the things I mentioned above. I'm not sure I'll continue to teach it to my son or not. On one side of the coin, it can do some pretty fun things with the phone (some of which I haven't tried, and none of which I've written up here.) On the other side, it's got severe limitations and I might as well move my son to Build Your Own Blocks. I probably actually have more comments, but I'm getting pretty tired at this point. Goodnight Moon.

SBT and Test Arguments

If you want to pass arguments to tests in SBT, you've come to the right place. First know this - it only works in certain situations, it's a bit crufty, and its subject to change. But I'll try to keep this page up to date if it does change.

Another important note, if you want to pass arguments at the sbt command line, you can only do it for test-quick, and test-only (I think). It doesn't work for the default "test" command. This is a bit unfortunate, but there is a workaround (not a very good one, but at least it exists).

A final note: these examples are for ScalaTest and ScalaCheck. I don't yet have examples for Specs, but Eric has implemented argument handling (in 1.6.2.1-SNAPSHOT for scala 2.7.7 and 1.6.4-SNAPSHOT for scala 2.8.0.Beta1).

Passing Args to ScalaTest from the Command Line

Let's say you have this little ScalaTest class that uses both params and tags:

import org.scalatest.fixture.FixtureFunSuite
import org.scalatest.Tag

class WickedCoolTest extends FixtureFunSuite{
 type FixtureParam = Map[String,Any]
 override def withFixture(test: OneArgTest) {
   test(test.configMap)
 }
 test("1", Tag("dood1")){ conf => println("dood1: " + conf) }
 test("2", Tag("dood2")){ conf => println("dood2: " + conf) }
 test("3", Tag("dood3")){ conf => println("dood3: " + conf) }
}

To run all tests in in this class use:

test-only WickedCoolTest

To run only tests tagged with "dood1" use:

test-only WickedCoolTest -- -n dood1

To run tests tagged with dood1 or dood2, use:

test-only WickedCoolTest -- -n "dood1 dood2"

To run all tests except for tests tagged with dood2, run:

test-only WickedCoolTest -- -l dood2

To run all tests except for tests tagged with dood2 dood3, run:

test-only WickedCoolTest -- -l "dood2 dood3"

To pass configuration parameters to a test, use:

test-only WickedCoolTest -- -Danswer=42

To pass many config params, add more -D's:

test-only WickedCoolTest -- -Danswer=42 -DrealAnswer=54

Tags and parameters can be used in combination, like so:

test-only WickedCoolTest -- -n "dood dood2" -Dhey=you -Dm=f

This runs only tests tagged with dood or dood2 and produces the following output:

dood: Map(hey -> you, m -> f)
dood2: Map(hey -> you, m -> f)

Passing Args to ScalaCheck from the Command Line

I'll spare you the entire example and just get to the point here.

To set the minimum number of successful tests, use '-s'

> test-only *IntParallelArrayCheck -- -s 5000
...
[info] == scala.collection.parallel.mutable.IntParallelArrayCheck ==
[info] OK, passed 5000 tests.

The rest of the examples are very similar. Consult ScalaCheck itself for further documentation.

• -s (minSuccessfulTests): Number of tests that must succeed in order to pass a property
  
• -d (maxDiscardedTests): Number of tests that can be discarded before ScalaCheck stops testing a property
  
• -n (minSize): Minimum data generation size
  
• -x (maxSize): Maximum data generation size
  
• -w (workers): Number of threads to execute in parallel for testing
  
• -z (wrkSize): Amount of work each thread should do at a time
  

Default Arguments

Maybe you want to pass default arguments to your test framework of choice. That is, you want to pass the same arguments every time you run your tests (and still be able to pass more dynamically, if you wish). You can do this too, by adding elements to 'testOptions'. Doing so will take effect when you run sbt test, sbt test-only, sbt test-quick, etc.

Let's say you want the minimum number of ScalaCheck passing tests to be 5000 every time you run ScalaCheck. Here is how you do that:

override def testOptions = 
  super.testOptions ++ 
  Seq(TestArgument(TestFrameworks.ScalaCheck, "-s", "5000")) 

Or maybe you only ever want to run your fast ScalaTest tests.

override def testOptions = 
  super.testOptions ++ 
  Seq(TestArgument(TestFrameworks.ScalaTest, "-n", "fast")) 

Custom Test Tasks

Maybe you have some test that you run all the time. At the sbt command line, instead of saying > test-quick blah.blah.Blah, you just want to say: > blah.

You can do that too, and you can pass args to it dynamically, and you get the default arguments as well. You'll have to take the following code and put it into your sbt file. It's ugly, I know, but the results are nice.

lazy val blah = singleTestTask("blah.blah.Blah")
 
private def singleTestTask(className: String) = task { args =>
  defaultTestTask(TestFilter(_ == className) :: 
   testOptions.toList ::: ScalaTestArgs(args))
}

private def newScalaTestArg(l: String*) = 
  TestArgument(TestFrameworks.ScalaTest, l:_*)

private def ScalaTestArgs(args: Seq[String]): List[TestArgument] = {
  def KVArgs(args: Seq[String]): TestArgument = 
    newScalaTestArg(args.map("-D" + _):_*)
  def tagsFromArgs(tags: Seq[String]): List[TestArgument] = {
    if (tags.isEmpty) Nil else 
      List(newScalaTestArg("-n", tags.mkString(" ")))
  }
  val (kvs, tags) = args.partition(_.contains("="))
  KVArgs(kvs.toSeq) :: tagsFromArgs(tags.toSeq)
}

Subclasses

Finally, maybe you want to set up tasks like 'test-fast' and 'test-slow' which only run your fast and slow tests. Let's imagine that you've created a trait called blah.blah.SlowTest and all of your slow tests extend that trait. Tests that don't extend SlowTest are considered to be in the fast group. With the code below, at the sbt command line you'll be able to say > test-fast, and > test-slow.

Again, it's a bit ugly to put this stuff in your sbt project file, but it works for now, until I come up with a better plan :)

lazy val testSlow = 
  runSubclassesOf("org.nlogo.util.SlowTest")
lazy val testFast = 
  runEverythingButSubclassesOf("org.nlogo.util.SlowTest")

private def runSubclassesOf(className: String) = {
  val subclass: Boolean => Boolean = x => x
  subclassTest(className, subclass)
}
  
private def runEverythingButSubclassesOf(className: String) = {
  val notSubclass: Boolean => Boolean = x => ! x
  subclassTest(className, notSubclass)
}

private def subclassTest(className: String, 
                         subclassCheck: Boolean => Boolean) = task { 
  args =>
  lazy val jars = 
    testClasspath.get.toList.map(_.asURL).toArray[java.net.URL]
  lazy val loader = 
    new java.net.URLClassLoader(jars,buildScalaInstance.loader)
  def clazz(name: String) = Class.forName(name, false, loader)
  lazy val superClass = clazz(className)
  def filter = 
    TestFilter(c => 
      subclassCheck(superClass.isAssignableFrom(clazz(c))))
  defaultTestTask
    (filter :: testOptions.toList ::: ScalaTestArgs(args))
}

Yeah...

Let me know if you have any issues with any of this, I'll be happy to help. I put it together pretty quickly. If there are any glaring errors or omissions, please tell.

Introducing Sweet

 
In this post I introduce Sweet, the fully complete test framework (even with IDE support) in only 99 lines of code. Sweet is compiled against the new Scala-2.8.0.Beta1-RC1, and works great with simple build tool 0.6.3. Sweet lives at: http://github.com/joshcough/Sweet.

Your First Sweet

Sweets are just like ScalaTest's FunSuite, using the test("name"){ ... } style. The syntax is exactly the same:

class HelloWorldSweet extends Sweet {

  test("hello, world!"){
    "hello, world!" mustBe "hello, world!"
  }
}

Just this (and one minor sbt configuration) will get you fully up and running with simple build tool. Your tests will be discovered and run automatically by sbt, just as they are with the other Scala test frameworks.

Assertions

Sweet currently offers only two assertions, in matchers style: mustBe and mustNotBe. Let's extend the hello world example to show usages of each:

class HelloWorldSweet2 extends Sweet {

  test("hello, world! with mustBe"){
    "hello, world!" mustBe "hello, world!"
  }
  test("hello, world! with mustNotBe"){
    "hello, world!" mustNotBe "goodbye, world!"
  }
}

And while were at it, let's how a quick boolean example:

class BooleanAssertionExampleSweet extends Sweet {

  test("hello, world!"){
    val b = imagaryCallThatReturnsABoolean()
    b mustBe true
  }
}

I know it's not much, but it probably covers 90% of common assertions, which are normally of the form:

assertEquals( 1, 1 )
assertTrue( something )

Could there, should there, will there be more matchers and different types of assertions in the near future? My Magic 8 Ball says, "Rely on it".

Running in the IDE

Sweet runs in the IDE by piggybacking on the TestNG IDE plugins. Currently, you all you need to do is mix in the SweetTestNGAdapter trait into your test to get full IDE capability. Here, I modify the Hello World example to provide IDE support:

class HelloWorldSweet extends Sweet with SweetTestNGAdapter {

  test("hello, world!"){
    "hello, world!" mustBe "hello, world!"
  }
}

That's it!

Note: There is a chance that I simple add this capability right into Sweet so that you don't have to mix in this trait at all, but there are some disadvantages. First, it would require that all users of Sweet also depend on TestNG. Secondly, the community is currently working on a common set of test interfaces that all test frameworks would implement. The hope that eventually all the IDEs (and other tools) would use these interfaces, and that any test framework implementing the API could run in the IDE. For now, I'll leave SweetTestNGAdapter as a trait, and hold out hope.

What's next for Sweet?

I plan to use Sweet somewhat as an experimental framework for ideas that are a bit too radical for ScalaTest. A staging grounds if you will. Here are some of the things in the works currently, or planned.

• Making use of my scala-parallel project, I've already added a Sweet that allows all tests to be run in parallel.
  
• I've added my concurrent programming test API in, so multi-threaded code can be testing very easily.
  
• I plan eventually to add Actor testing API here.
  
• Certain more as well.
  

Why Sweet?

This is really two questions. Why did I write Sweet, and why should you use Sweet?

As I explained, I want to use Sweet for experimental ideas.

You should use Sweet if you're looking for something that is always up to date with the latest Scala builds, and tools. I understand that there's only a handful of people using the nightly builds, and with beta coming out, it won't really matter. But for now, I plan to build Sweet nightly. Also, it's Sweet, Dood. Come on!

Implementation

Given that it's only 99 lines, I might as well just list the entire implementation here. However, you can also find it at github. Below, I had to make some of the lines shorter so that they would fit in my blog, but I assure you, the actual implementation is 99 lines.

Sweet.scala

package sweet

trait Sweet extends Assertions {

  private[sweet] var tests = List[TestCase]()

  case class TestCase(name: String, f: () => Unit) {
    def apply(reporter: SweetReporter) {
      try{
        reporter(TestStarting(name))
        f()
        reporter(TestSucceeded(name))
      }catch {
        case t: SourAssertionException => {
          reporter(TestFailed(name, t))
        }
        case t: Throwable => {
          reporter(TestErrored(name, t))
        }
      }
    }
    override def toString = name
  }

  def test(name: String)(f: => Unit) {
    if (tests.map(_.name).contains(name)) println("duplicate test name: " + name)
    tests = tests ::: List(TestCase(name, f _))
  }

  def run(reporter: SweetReporter) {
    tests.foreach(_(reporter))
  }
}

Assertions.scala

package sweet

trait Assertions {

  case class Equalizer(a:Any){

    def mustBe(b:Any){ 
      if( ! a.equals(b) )toss(a + " did not equal " + b + " but should have") 
    }

    def mustNotBe(b:Any) { 
      if( a.equals(b) ) toss(a + " must not equal " + b + ", but did") 
    }

    def toss(message: String){ throw new SourAssertionException(message) }
  }

  implicit def Any2Equalizer(a: Any) = Equalizer(a)
}

SourAssertionException.scala

package sweet

class SourAssertionException(message: String) extends RuntimeException(message)

SweetFramework.scala (implementation of Framework from test-interfaces)

package sweet

import org.scalatools.testing._

class SweetFramework extends Framework {
  def name = "Sweet"
  def tests = Array(new TestFingerprint { 
    def superClassName = "sweet.Sweet"; def isModule = false
  })
  def testRunner(testLoader: ClassLoader, loggers: Array[Logger]) = { 
    new SweetRunner(testLoader, loggers)
  }
}

SweetRunner.scala (implementation of Runnerfrom test-interfaces)

package sweet

import org.scalatools.testing._

class SweetRunner(val classLoader: ClassLoader, 
  loggers: Array[Logger]) extends Runner {

  def run(testClassName: String, fingerprint: TestFingerprint, 
    eventHandler: EventHandler, args: Array[String]){
    val testClass = Class.forName(testClassName, 
                     true, classLoader).asSubclass(classOf[Sweet])
    val sweet = testClass.newInstance
    val reporter = new MySweetReporter(eventHandler)
    sweet.run(reporter)
  }

  class MySweetReporter(eventHandler: EventHandler) extends 
    SweetReporter with NotNull{

    def newEvent(tn: String, r: Result, e: Option[Throwable]) {
      class MyEvent(val testName:String, 
                    val description:String, 
                    val result:Result, val error:Throwable) extends Event
      eventHandler.handle(new MyEvent(tn, tn, r, e getOrElse null))
    }

    def apply(event: SweetEvent) {
      event match {
        case t: TestStarting => 
          loggers.foreach(_ info "Test Starting: " + t.testName)
        case t: TestFailed => 
          newEvent(t.testName, Result.Failure, Some(t.reason))
        case t: TestErrored => 
          newEvent(t.testName, Result.Failure, Some(t.reason))
        case t: TestSucceeded => 
          newEvent(t.testName, Result.Success, None)
      }
    }
  }
}

SweetReporter.scala

package sweet

trait SweetReporter {
  def apply(event: SweetEvent) 
}

SweetEvent.scala

package sweet

trait SweetEvent

case class TestStarting(testName: String) extends SweetEvent
case class TestFailed(testName: String, 
  reason:SourAssertionException) extends SweetEvent
case class TestErrored(testName: String, 
  reason:Throwable) extends SweetEvent
case class TestSucceeded(testName: String) extends SweetEvent

Proof

Here's proof that it's really just 99 lines:

$ wc -l Assertions.scala \
        SourAssertionException.scala \
        Sweet.scala SweetEvent.scala \
        SweetFramework.scala \
        SweetReporter.scala \
        SweetRunner.scala \
        SweetTestNGAdapter.scala
     14 Assertions.scala
      2 SourAssertionException.scala
     28 Sweet.scala
      7 SweetEvent.scala
      8 SweetFramework.scala
      4 SweetReporter.scala
     29 SweetRunner.scala
      7 SweetTestNGAdapter.scala
     99 total

Teaching Kids To Read Programs

 
Today I taught my 8 year old son Jacy how to read some simple programs. I've been taking my time in picking what to teach him next about programming because I don't want to push him too hard. He get's frustrated sometimes and I have to be inventive in my teaching styles. I had an idea a few weeks back about a Simon Says related game that I thought would work, and tried it out today.

The concept is quite simple, write out a simple if/else if/else statement centered around some particular value, have him read it, then say "Simon Says 'value is something'". Here's a very, very simple example. I write down this program and have him read it:

if x is 7 then jump
else sit down

Then I say, "Simon Says x is 5!", and he would know to sit down.

This worked, but as soon as I tried some more complicated programs he lost interest almost immediately. I don't give up easily though (or ever), and so I quickly came up with a new plan.

He complained that he didn't understand, and I think the x was throwing him off just a little bit (even though I think he understood it, and he certainly did later on). So, I decided to use crayons instead, since they are more concrete. Also, I decided to make it a bit more fun by adding pretending to the mix. I started over with the following program:

if color is red then PICK NOSE
else PUKE

Of course, all boys like to pretend to pick their nose and puke. This program was much more fun to him and he was much more willing to read it. Like I said, I'm sure he understood the first programs just fine, but it has to be fun.

Now, instead of saying "Simon Says Color is Red!", I had a box of crayons, and I'd simply pull a crayon out of the box. Less abstract, more concrete, more visible, more involved, more fun. This worked like a charm as he quickly pretended to pick his nose.

Now that I had his full attention I was easily able to add in an else if statement that I had failed on earlier:

if color is red then PICK NOSE
else if color is black then DIE
else PUKE

This was easy for him. I'd pull a red crayon out of the box and he'd pretend to pick his nose. I'd pull a yellow crayon out and he'd realized the first two don't match, and he'd pretend to puke. I'd pull a black crayon out and he'd pretend to die. No big deal, but still very cool.

Now I was able to add in some more interesting boolean logic:

if color is red or yellow then PICK NOSE
else if color is black or blue then DIE
else PUKE

This was also very trivial to him, as I expect anyone would imagine. But, I think all of this was necessary to get him back to the abstract forms that I started with. Now that I had the fun element, and the else ifs, I was able to go back to a program similar to the one I first failed on.

if x is 7 then PICK NOSE
else if x * 10 is 20 then DIE x times
else PUKE

This one is a lot more complicated than the any of the previous programs, but I felt that he did get it right from the start, he just needed the right encouragement (puking, picking, and dying, of course). Sure enough, he was ready for it. I said, "Simon Says 'x is 2'", and he pretended to die 2 times. He really did understand what x meant. However, I could see how some of this was a leap, and suggest progressing slower if needed. Here are some examples:

if x is 7 then PICK NOSE
else if x is 5 then DIE 5 times
else PUKE

followed by:

if x is 7 then PICK NOSE
else if x is 5 then DIE x times
else PUKE

then maybe something simpler than multiplication:

if x is 7 then PICK NOSE
else if x + 1 is 3 then DIE x times
else PUKE

There's a ton of room to be very creative here, and anyone can go at their very own pace, and each step can be broken down very slowly. This is all very exciting. My son is reading simple code! It won't be long at all before he's writing it. But, certainly it will be great to have him master reading it first. We do much more reading of code than writing as software pro's, and it's a skill that far too many students never learn. :(

What's next? I'm not sure. Probably nested expressions. I think I could do that by introducing two colors like so:

if first color is red then 
  if second color is blue then PICK NOSE
  else THROW TANTRUM
else if first color is black or blue then DIE
else PUKE

Those of course could get far more complex.


A few final notes to those who actually intend to try this with their kids.

1. He was very particular about having solid lines separating the if part from the else if parts, and the else parts. This helped him read the program a lot more clearly. I think a good deal of space would have done just as good. My initial programs were a bit bunched up, and he didn't like that at all.
   
2. He didn't really feel comfortable reading the program out loud to me. He would read it, and I knew he understood it, but if I asked him to read it out loud he got mad.
   
3. Along the same lines, if I asked him to explain how he got his answer he didn't want to tell me. I'd have to point to parts of the program and ask him if that's where he was, but it just didn't go very well at all. He knew the answers, just didn't like talking about it. Help understanding this phenomenon would be appreciated.
   

Please let me know what you think!

Changes

Back in February I wrote that it was time for me to go back to grad school. More or less, that time has come - I've decided to leave my job. I don't believe that this is a reflection of the quality of work at the job (or previous jobs), its just time for me to study languages. I would find my thoughts drifting constantly to languages while at work. I don't think it's fair to the teams I work with (as long as we're not working on languages), and I don't think it's good for me to be in a position that can't possibly allow me to work on everything I want. It's simply time.

I want to say thanks to Ken, Daniel, Evan, Mark and Marek at Simon and Schuster. It's a very good development team, and they were very good to me. I wish them absolutely the best of luck on all things in the future. While they all deserve credit, I think Daniel deserves extra credit for being an amazing, intelligent, patient boss. He probably gave me more slack than I earned, and I will never forget that. I would highly recommend the job for someone smart, but junior. It would be a position where you could learn from agile experts, as well as some fun technologies to work with, and a great team.

As for whats next, I don't have a definite plan yet. I do have tentative plans A and B, and will announce them once things get settled. Unquestionably though, it will be working in languages and/or studying towards Phd. Hopefully it can involve my passion for teaching, especially teaching children. I'm going to take a little bit of time off to spend extra time with my son before I get back into things. He deserves it.

That's all. Bye.

What JVM Language Do You Write Tests In?

 
At a recent NYC Scala meetup, I got chatted up and basically was asked the following:

I know you've been writing multi-threaded testing API's in Scala, but we're still writing tests in Java, so do you know any good Java multi-threaded testing API's?

(As a matter of fact I do, but that's not the point of this post.)

I couldn't help but immediately feel very bad. I feel genuinely sorry. Overwhelmingly sorry, in fact. Why? Because people in this world are still writing tests using Java. So, I'm calling on people to help me build an argument that can be used by people still trapped in a cave writing tests in Java. Most of the rest of this post will be a rant to start generating ideas, I'll try to formalize the argument by reading comments and then put it into another post.

Random Ranting To Generate Ideas

Scala and Groovy and JRuby and Jython and Clojure and so many more are by far better alternatives for testing on the JVM, and some of them have been for a long, long time. I started testing using Scala almost two years ago. I submit that if you can't get your organization to switch your testing language, you should leave. It's not even production code!

You can still run your old tests anyway, even if just in your current runner. ScalaTest also gives you many alternatives for running all your old tests and new tests very easily in the same runner.

You might argue that now you have to maintain two different code bases, two different languages for your tests. Honestly, I say Come On!. First, the new code tests will be far easier to maintain than any new tests you would have written in Java. Second, were professional software developers. If you can't manage one extra directory of code, you probably shouldn't be in this business.

I think of more later.

Poll

Also, I'm creating a new poll. What JVM Language Do You Write Tests In? If you are reading this from a feed, you might have to click to get in: http://jackcoughonsoftware.blogspot.com/

Testing Multi Threaded Scala Code

 
Recently I did a (somewhat brute force) port of MultithreadedTC. All of this work stems directly from it, and I deserve basically no credit. However, I've done a bunch of interesting work around it, and I wanted to talk about it a bit. First I want to mention a few important points.

1. We all know that the concurrency model used in Java has proven to be far too complex. About 5 people in the world can actually do it right. While this test api can be used to test code written in that style pretty easily, I'm not advocating writing anything in that style.
   
2. java.util.concurrent is still very useful. This api can be used to test j.u.c, Scala libraries that wrap it, and Scala libraries that use it.
   
3. This code will be in an upcoming release of ScalaTest, and (pending discussions) could make its way into Specs as well.
   
4. In the very near future this library should be very useful for testing actor code as well. Discussions and experimental implementations are ongoing. Expect a post about that very soon. Additionally, any Actor testing api will most definitely make its way into ScalaTest.
   

Onward to an example! I'm going to dump it out, and explain after.

package scala.util.concurrent.locks


class PimpedReadWriteLockTest extends MultiThreadedSuite with 
  MustMatchers with MustBeSugar {
  
  val lock = new java.util.concurrent.locks.ReentrantReadWriteLock
  import Implicits.RichReentrantReadWriteLock

  thread("writer thread") {
    waitForTick(1)
    lock.write {tick mustBe 2}
  }

  thread("reader thread") { 
    lock.read { waitForTick(2) } }
  }

  5.threads("reader thread("+_+")") {
    lock.read { waitForTick(2) }
  }

  10 anonymousThreads {
    lock.read { waitForTick(2) }
  }
}

There's a huge amount of stuff going on here, and I'll do my best to explain it one line at a time. Also, for the purposes of understanding and clarity, I might intentionally leave out some details that would only confuse. Okay, go.

class PimpedReadWriteLockTest extends MultiThreadedSuite with 
  MustMatchers with MustBeSugar {

MultiThreadedSuite is a ScalaTest suite that contains all the goodies for multithreaded testing. Those goodies will be covered as we go. The matchers give me my must methods as seen in: tick mustBe 2.

  val lock = new java.util.concurrent.locks.ReentrantReadWriteLock
  import Implicits.RichReentrantReadWriteLock

Create a read/write lock, and then import the code to Pimp it. The rich version allows you to say lock.read{...}, and lock.write{...}. These do basically what you would imagine, but here's a shallow example for lock.read (its not exact, but you get the idea):

  readLock.lock()
  f()
  readLock.unlock()

Creating a test Thread

  thread("writer thread") {
    ...
  }

On this line, a Thread is created with the name "writer thread". The thread method also returns the Thread, so you could assign it to a val and use it later on like so: val writer = thread("writer thread"){ ... } When the thread is started, it will run the code in between the curly brackets. I'll explain that code now.

Wait For Tick

Internally, MultiThreadedSuite maintains a clock. The clocks time starts at 0 and only advances when the following conditions hold:

1. ALL test threads are blocked.
   
2. At least one of those threads is waiting for the clock to tick.
   

Why the last condition? If all threads are blocked, and no one is waiting for a clock tick, you have a deadlock!

waitForTick(n) blocks the current thread until time n is reached on the clock. If the current time on the clock is greater than n, then the thread does not block.

Revisiting the code:

  thread("writer thread") {
    waitForTick(1)
    lock.write {tick mustBe 2}
  }

The writer thread immediately blocks, waiting for tick 1. When time 1 is reached, the thread unblocks, and attempts to acquire the write lock. As we'll find out later shortly, it will be unable to do so just yet. That's the important part of this test.

Next:

  thread("reader thread") { 
    lock.read { waitForTick(2) } }
  }

Just as with the writer thread, this code creates a thread that will run during the test. When the thread runs it will acquire the read lock, and then wait for tick 2. This thread is guaranteed to get the read lock before the writer thread gets the write lock. How? Because the write thread immediately blocks waiting for tick 1. Recall that the clock doesn't tick until ALL threads are blocked. The reader thread doesn't block until it says waitForTick(2), at which point it already has the read lock. :)

Now, the curious reader might wonder, why waitForTick(2). Let me explain. The test notices that someone is waiting for a tick, and if all threads are blocked, it advances the clock. The thread waiting for a tick only unblocks if the current time is equal to the time its waiting for, otherwise it stays blocked. The test system sleeps for a little bit, wakes up, realizes that all threads are still blocked and someone is still waiting for a tick, and advances the clock again.

With that explained, you can see that waitForTick(2) is just shorthand for:

waitForTick(1)
waitForTick(2)

Breaking it up this way will help us analyze what is happening in the test, and I'll do that shortly. First though, lets take a look at the rest of the code.

Creating LOTS of threads

  5.threads("reader thread("+_+")") {
    lock.read { waitForTick(2) }
  }

This code simply creates 5 threads. They all happen to be reader threads, and they are given the names "reader thread(1)" ... "reader thread(5)". It's a convenience method for creating many threads that you want to do exactly the same thing.

  10 anonymousThreads {
    lock.read { waitForTick(2) }
  }

Creates 10 anonymous threads that also happen to be reader threads. They are actually given names, because all threads have names. The name is "Thread N", where N corresponds to the number of threads created so far. So these guys will actually get named something like Thread 7 ... Thread 16. I don't really recommend using anonymous threads, but the style is a little bit less verbose, so maybe someone will like it.

Now, these methods return List[Thread]. I've chosen to ignore the return value here, but I can imagine cases where its very useful to have. The code could easily be rewritten:

  val readers: List[Thread] = 5.threads("reader thread("+_+")") {
    lock.read { waitForTick(2) }
  }
  val namelessReaders: List[Thread] = 10 anonymousThreads {
    lock.read { waitForTick(2) }
  }

Step by Step

1. waitForTick(1) blocks the writer thread until tick 1 happens.
   
2. The reader threads all get the read lock.
   
3. waitForTick(1) blocks the reader thread until tick 1 happens. The writer thread is also waiting for tick 1. They will all get the read lock, and then all block waiting for tick 1. When they all get to that point, the clock is advanced, and the threads continue.
   
4. The write thread will wake up and try to grab the write lock, but it wont be able to, because the read lock is held 16 times over! It will block.
   
5. waitForTick(2) causes the reader threads to block waiting for tick 2. The clock can advance because all the reader threads are blocked waiting for tick 2, and the writer thread is blocked waiting for the write lock.
   
6. After tick 2, all the reader threads wake up. The writer thread is still blocked, waiting for the read lock.
   
7. The reader threads all give up the read lock in concert.
   
8. The writer thread finally gets the write lock. When it does, it makes sure that the current tick is 2. Indeed, it is.
   

Summary

This should be the foundation of some really interesting work to come. I'll keep everyone informed.

Pimp vs Just Plain Fix my Library

 
I assume most people familiar with Scala are familiar with Pimp My Library. It's just a fun and useful thing to be able to add a missing method onto an API, or to sometimes be able to treat an object like something else.

As fun as it is (especially with the word Pimp), I kind of want to take the fun out of it a little bit. I want to say that its not just about adding that one great feature. Let me make this boring and annoying assertion: Pimping is most useful for fixing crappy, terrible, miserable API. And while that's cool, and useful, it kind of sucks. There's so much terrible code out there that is a nightmare to work with. I feel like I shouldn't have to be fixing up other people's crap, but at least I can.

Now for an example. Ever dealt with Java's ThreadGroup? Ever want to just get the Threads in a ThreadGroup? Sounds reasonable enough right? Holy Mother.... Couldn't be more wrong. Check out this gem that I lovingly stole straight from the Javadoc:

enumerate

public int enumerate(Thread[] list)

Copies into the specified array every active thread in this
thread group and its subgroups.

First, the checkAccess method of this thread group is
called with no arguments; this may result in a security exception.

An application might use the activeCount method to
get an estimate of how big the array should be, however if the
array is too short to hold all the threads, the extra threads are
silently ignored. If it is critical to obtain every active
thread in this thread group and its subgroups, the caller should
verify that the returned int value is strictly less than the length
of list.

Due to the inherent race condition in this method, it is recommended
that the method only be used for informational purposes.

Parameters:

list - an array into which to place the list of threads.

Returns:

the number of threads put into the array.

WHAT?!? This API is just plain broken. It desperately needs fixing. All I want to do is get all the Threads in the Group...why should I have to deal with creating my own Array (and guessing the size), having it work entirely off side effects...And does it really return the number of threads it put into the Array? I'm afraid so. Broken. And does it really SILENTLY IGNORE things when there are too many threads to fit in the array!?! Horrible disaster.

Not even that fun to fix to be honest, but the resulting code is far more manageable. But here's a solution.

object PimpedThreadGroup {
  implicit def threadGroupToPimpedThreadGroup(tg: ThreadGroup) = {
    new PimpedThreadGroup(tg)
  }
}

class PimpedThreadGroup(threadGroup: ThreadGroup) {

  def getThreads: List[Thread] = getThreads(true)

  def getThreads(recursive: Boolean): List[Thread] = {
    def getThreads(sizeEstimate: Int): Seq[Thread] = {
      val ths = new Array[Thread](sizeEstimate)
      if (threadGroup.enumerate(ths, recursive) == sizeEstimate) 
        getThreads(sizeEstimate +10)
      else for (t <- ths; if (t != null)) yield t
    }
    getThreads(threadGroup.activeCount() + 10).toList
  }

  def filter(state: State): List[Thread] = {
    getThreads.filter(_.getState == state)
  }

  def exists(state: State): Boolean = {
    getThreads.exists(_.getState == state)
  }

  def any_threads_alive_? = {
    getThreads.exists(t => t.getState != NEW && t.getState != TERMINATED)
  }

  def any_threads_running_? = {
    getThreads.exists(_.getState == RUNNABLE)
  }

  def any_threads_in_timed_waiting_? = {
    getThreads.exists(_.getState == TIMED_WAITING)
  }
}

Most important: def getThreads: List[Thread]. Now I can simply call threadGroup.getThreads and get back a List[Thread]. That's all I ever wanted. Is that too much to ask?

I can also add something to simply treat a ThreadGroup as a List[Thread], if I want. I'm not sure I like this because it could get me into some trouble (and it always does recursive search), but I do like the power it gives - I can call any method on List directly on the ThreadGroup.

  implicit def ThreadGroupToList(tg:ThreadGroup): List[Thread] = {
    new PimpedThreadGroup(tg).getThreads
  }

By the way, I'm not going to explain it. I'm assuming you already know how it works (I might add a few more examples of how it can be used though, but I'm sure most people already understand). If you don't, you can click the Pimp My Library link above, or Google it. There's plenty out there.

In conclusion, was this a bit of a rant? I guess. Here's what we should take away from this though: Pimp My Library is a very effective tool not just for adding nice things to API's, but fixing broken ones. If it's our duty to refactor our broken code, to always make our code better when we have to modify it, then it's just as much our duty to fix up API's. In this case, we just don't have the original source. Refactoring without source code. It's actually pretty awesome.

Scala MultithreadedTC Port

I haven't posted in quite a while now, but only because I've been working really hard. I asked Doug Lea if I could help him on his upcoming Scala concurrent data structures endeavor, especially on testing and to my surprise he sounded quite happy about the idea. He's going to get started sometime in July, and I figured from now until then would be a great time to get caught up on testing concurrent data structures, and have a nice framework in place before any code actually gets written. To that end, I've decided to port MultithreadedTC to Scala.

The reasons for doing so are quite simple - we can take advantage of Scala's flexible syntax, HOF's, yada yada...I don't think that that needs to be explained yet again. And, I don't think this particular example demonstrates something like, "but here those features are particularly valuable". The resulting code is definitely nicer than the original Java code, and that's simply all.

Over the next few days I'll probably update this post giving more examples. I'll start with one tonight. Also, you can also learn more about how it all works by clicking the link above.

I'll start with an example from the original Java code from the MultithreadedTC source, and I'll try to give a reasonable explanation of what is going on.

1  class MTCTimedOffer extends MultithreadedTestCase {
2   ArrayBlockingQueue<Object&rt; q;
3 
4   @Override public void initialize() {
5     q = new ArrayBlockingQueue<Object>(2);
6   }
7 
8   public void thread1() {
9     try {
10      q.put(new Object());
11      q.put(new Object());
12
13      freezeClock();
14      assertFalse(q.offer(new Object(), 25, TimeUnit.MILLISECONDS));
15      unfreezeClock();
16
17      q.offer(new Object(), 2500, TimeUnit.MILLISECONDS);
18      fail("should throw exception");
19    } catch (InterruptedException success){ assertTick(1); }
20  }
21
22  public void thread2() {
23    waitForTick(1);
24    getThread(1).interrupt();
25  }
26}

This code tests the interactions of two threads. The second thread interrupts the first thread (line 24) as its attempting to offer an object to the queue on line 17. One challenge that the library means to solve is - How can we be sure that thread2 calls interrupt at the appropriate time? It does so by maintaining and internal metronome (or clock). The clock ticks forward only when all threads are blocked and at least one thread is waiting for the clock to tick.

On line 23 thread2 waits for the clock to tick. Remember, the clock doesn't tick until all threads are blocked. So when does thread1 become blocked? Well, since the queue can only contain two elements, it becomes blocked on line 14, when it tries to offer a third object. However, in this case, we've frozen the clock, so the clock will not tick, and thread2 will continue to wait.

Finally on line 17 thread1 becomes blocked offering a third object to the queue, and the clock is not frozen. Behind the scenes the framework sees that all threads are blocked, and indeed someone is waiting for the clock to tick (thread2). The clock ticks, and thread2 advances. He then interrupts thread1 using the getThread method. thread1 enters its catch block on line 19, checks to see that the clock has indeed reached 1, and everyone is happy.

Sort of...

There are a few things we can do better. Most importantly, of course - we can get rid of a lot of semicolons! Ok maybe that's not most important, but I really hate semicolons. Here's a more serious list of the deficiencies in the code above (oh and, its really not that bad at all).

1. The call to getThread is not type safe at all, and break on a refactoring if you decided to rename a thread. How does that work anyway? Answer: the threads are named by the method names. On line 8 we have "public void thread1" and so we have a thread named thread1. This was originally done for a good reason - creating threads in Java is very verbose. This cleans that up a lot, at the minor price of some type safety.
   
2. When we freeze the clock we could easily forget to unfreeze it, leading to quite a bit of headache.
   

There are more, and I will address them here, but let us focus on those two for now. I'll give the Scala equivalent first, then explain how I've addressed those issues.

1 class MTCTimedOffer extends MultiThreadedSuite {
2
3   val q = new ArrayBlockingQueue[String](2)
4
5   val producer = thread{
6     q put "w"
7     q put "x"
8
9     withClockFrozen {
10      q.offer("y", 25, TimeUnit.MILLISECONDS) mustBe false
11    }
12
13    intercept[InterruptedException] {
14      q.offer("z", 2500, TimeUnit.MILLISECONDS)
15    }
16
17    tick mustBe 1
18  }
19
20  thread{
21    waitForTick(1)
22    producer.interrupt()
23  }
24}

Notice that the code isn't much smaller, 24 vs 26 lines. I'm not touting a giant absurd improvement in any way. However, lets look at the issues above.

1. On line 5 ( val producer = thread{ ) an actual Thread object is returned, and that thread can be referenced by any of the other threads in the system by name, in an intuitive, type safe way. I do this simply, by having the thread method take a HOF and wrapping that HOF in a Thread. Easy. Notice on line 22 the second thread references the producer thread directly.
   
   Also, If I don't feel like it, I don't have to assign the thread to a val, and I don't have to reference it anywhere. The Thread created in line 20 isn't really needed by anyone else, so it remains anonymous (behind the scenes it actually gets the name thread2, and can still be gotten using the getThread method seen above).
   
2. The second issue was a very simple one where we could forget to unfreeze the clock. Simple is ok, because all these simple fixes added up big in the long run, IMO. This issue is solved by using the withClockFrozen which appears on line 9. This is also a method that takes a function. It then does the work of freezing the clock for you, running the function, then unfreezing the clock. Simple, but effective.
   

Ok, its really late, and I have to work tomorrow. But, expect this post to be updated regularly in the near future. I'll likely be working with Bill Venners and Eric T. on getting this stuff into ScalaTest and/or Specs, and DL on improving this stuff, and hopefully Bill Pugh, the original author. Any ideas, comments, improvements, etc would be greatly appreciated! I'll have the source code somewhere where people can see it very soon. Bye!

Comedy: Scala vs. Ruby vs. Objective C

 
Please submit your favorite (or least favorite) language!

Added: Java, Clojure, JavaScript

Scala

this.computers = Array(
 Map("Name" -> "MacBook", "Color"->"White"),
 Map("Name" -> "MacBook Pro", "Color"->"Silver"),
 Map("Name" -> "iMac", "Color"->"White"))

Ruby

self.computers = [
 {:Name=>"MacBook", :Color=>"White"},
 {:Name=>"MacBook Pro", :Color=>"Silver"},
 {:Name=>"iMac", :Color=>"White"}]

Objective C

NSDictionary *row1 =
 [[NSDictionary alloc] initWithObjectsAndKeys:
   @"MacBook", @"Name", @"White", @"Color", nil];
NSDictionary *row2 =
 [[NSDictionary alloc] initWithObjectsAndKeys:
   @"MacBook Pro", @"Name", @"Silver", @"Color", nil];
NSDictionary *row3 =
 [[NSDictionary alloc] initWithObjectsAndKeys:
   @"iMac", @"Name", @"White", @"Color", nil];

NSArray *array =
 [[NSArray alloc] initWithObjects: row1, row2, row3, nil];

self.computers = array;

[row1 release];
[row2 release];
[row3 release];
[array release];

Java

Assuming this field:

 Map<String, String>[] computers;

Then:

Map[] maps = {
     new HashMap(){{
         put("Name", "MacBook");  
         put("Color", "White");
     }},
     new HashMap(){{
         put("Name", "MacBook Pro");
         put("Color", "Silver");
     }},
     new HashMap(){{
         put("Name", "iMac");     
         put("Color", "White");
     }}
 };
 this.computers = maps;

Notice you can't use generics with the array creation, and, 4 space indenting! Yeah!

Clojure

(def computers [
 {:Name "MacBook"}
 {:Name "MacBook Pro" :Color "Silver"}
 {:Name "iMac" :Color "White"}])

JavaScript

this.computers =
[{'name':'MacBook', 'color':'White'},
{'name':'MacBook Pro', 'color':'Silver'},
{'name':'iMac', 'color':'White'}];

Good Use Case for Named Arguments

 
I found what I consider a really great use case for using keyword arguments. I'm sure there are tons of them, I just want to list this one.

Here I have some code that I had in CPU Simulator that I was using to test a FlipFlopChain, which is essentially just an N Bit Memory (maybe I'll rename it that).

    val data = AllGeneratorNumber(8)
    val chain = FlipFlopChain(data, Generator.on)
    ...

Notice that the second parameter to FlipFlopChain is Generator.on. What is this parameter though? We have to navigate into FlipFlopChain just to find out that it represents the write bit. If we didn't have the source, we might have no idea.

So I changed the code to make it more explicit, by declaring a writeBit val.

    val data = AllGeneratorNumber(8)
    val writeBit = Generator.on
    val chain = FlipFlopChain(data, writeBit)
    ...

Note that I never use the writeBit again in the test code, its just there to help the reader understand what that second parameter is.

With keyword arguments, there is a much better solution:

    val data = AllGeneratorNumber(8)
    val chain = FlipFlopChain(data, writeBit=Generator.on)
    ...

Win!

Some Simple Scala Refactorings

 
I constantly go back and tinker with my old Scala code, especially in my CPU Simulator project. When I'm in the old code I notice something that I haven't really noticed before - the code is still good. In a previous life when I wrote Java code, I'd go back and look at old code and want to throw up. Scala is so concise that this just doesn't happen. Yes, I do find room for improvement here and there, but overall I'm still really happy with the code (there was an exception, when I didn't know anything about functional programming, and refactored from imperative to functional...but that doesn't count).

Anyway, I have a few refactorings that I wanted to mention.

Refactoring to Case Classes

I refactored all of my LogicGate classes to be case classes instead of regular classes. The reason? The code is just prettier. I'm not a huge fan of the new keyword in general, and I especially don't like it littering up my code.

Old Code:

class XorGate(inputA: PowerSource, inputB: PowerSource) 
  extends LogicGate {
  val output: PowerSource = 
    new AndGate(
      new OrGate(inputA, inputB), 
      new NandGate(inputA, inputB))
}

New Code:

case class XorGate(inputA: PowerSource, inputB: PowerSource) 
  extends LogicGate {
  val output: PowerSource = 
    AndGate(OrGate(inputA, inputB), NandGate(inputA, inputB))
}

The difference is small, but I literally had hundreds of new calls littered throughout my code. Now, I could also mention the extra power that case classes give as well - nice toString, pattern matching, hash code and equals... I happened to not really be using most of those things in the CPU simulator, so I don't have an immediate example. Oh well. In my opinion/experience, favor case classes over regular classes.

This does violates encapsulation somewhat though. Previously, inputA and inputB weren't accessible from outside the class. I can get around that easily enough by adding private to my vals:

case class XorGate(private val inputA: PowerSource, 
                   private val inputB: PowerSource) 
  extends LogicGate {
  val output: PowerSource = 
    AndGate(OrGate(inputA, inputB), NandGate(inputA, inputB))
}

Now I'm not exposing those fields, I still have all the power mentioned above, and I don't have the pesky "new" statements hanging around.

Refactoring to Fewer Files

I noticed something a little unsettling. I had separate files LogicGate.scala, AndGate.scala, OrGate.scala, NandGate.scala NorGate.scala, XorGate.scala. One for each type of gate. Several files, and they were all very very small, less than 10 lines each, all with a common package statement, and similar imports.

So I tried something - putting them all into one file. This is something I normally do by default now. I'm not sure when I started putting lots of classes into one file and not spreading them out...Anyway, in my opinion the result was a lot better. Instead of 6 files roughly 5-10 lines long, I have one file less than 40 lines long. I got rid of the redundant package and import statements. But most importantly, now I can see everything there is to know about my logic gates on the screen at one time.

package com.joshcough.cpu.gates

import electric.{Relay, Inverter, Wire, PowerSource}

object LogicGate{
  implicit def logicGateToPowerSource( lg: LogicGate ): PowerSource = lg.output
}

trait LogicGate{
  val inputA: PowerSource
  val inputB: PowerSource
  val output: PowerSource
}

case class AndGate(val inputA: PowerSource, 
  val inputB: PowerSource) extends LogicGate {
  val output: PowerSource = Relay(inputA, Relay(inputB))
}

case class NandGate(val inputA: PowerSource, 
  val inputB: PowerSource) extends LogicGate{
  val output = new Wire
  Inverter(inputA)-->output
  Inverter(inputB)-->output
}

case class NorGate(val inputA: PowerSource, 
  val inputB: PowerSource) extends LogicGate{
  val output: PowerSource = Inverter(inputB, Inverter(inputA))
}

case class OrGate(val inputA: PowerSource, 
  val inputB: PowerSource) extends LogicGate{
  val output = new Wire
  inputA-->output
  inputB-->output
}

case class XorGate(val inputA: PowerSource, 
  val inputB: PowerSource) extends LogicGate {
  val output: PowerSource = 
    AndGate(OrGate(inputA, inputB), NandGate(inputA, inputB))
}

I know some people who have said they will never do this, never having more than one class in a file. I think that's wrong. When you have several small classes, seeing everything at once overrules most arguments.

More

I probably should suck it up and turn my logic gates into actual functions at some point in the near future. That should provide some really interesting material on refactoring. Until then, cya.

Simple Scala Keyword Parameters

Everything here is mostly intuitive, but I'm putting it here for personal reference. Should be helpful to a lot of people though. There's probably a whole ton of interesting cases I'm leaving out, and I'll try to keep this updated when I think of them. For now I'm covering Default Values, No Default Values, and Overloading. (Note, this doesn't come out until 2.8, I'm working off trunk)

Default Values

• Define a class that takes two keyword args, name and lives, and provide default values.
  

  
  scala> case class Cat(name:String="kitty", lives:Int=9)
  defined class Cat
  

  
  
• Instantiate the cat providing no arguments.
  

  
  scala> new Cat
  res1: Cat = Cat(kitty,9)
  

  
  
• Instantiate a cat providing both params, unnamed.
  

  
  scala> Cat("Java", 1)
  res2: Cat = Cat(Java,1)
  

  
  
• Instantiate a cat providing just the first param, unnamed.
  

  
  scala> Cat("Scala")
  res3: Cat = Cat(Scala,9)
  

  
  
• Instantiate a cat providing both params, named.
  

  
  scala> new Cat(name="newspeak", lives=20)
  res4: Cat = Cat(newspeak,20)
  

  
  
• Instantiate a cat providing both params in reverse order. (Only works if names the argument names are given.)
  

  
  scala> new Cat(lives=20, name="newspeak")
  res5: Cat = Cat(newspeak,20)
  

  
  
• Instantiate a cat providing the first param, named.
  

  
  scala> new Cat(name="newspeak")
  res6: Cat = Cat(newspeak,9)
  

  
  
• Instantiate a cat providing the second param, named.
  

  
  scala> Cat(lives=4)                     
  res7: Cat = Cat(kitty,4)
  

  
  
• Instantiate a cat providing the first argument unnamed, and the second argument named!
  

  
  scala> new Cat("Lua", lives=1)
  res8: Cat = Cat(Lua,1)
  

  
  
• Attempt to instantiate a cat providing the first argument named, and the second argument unnamed. You can't do it! After you name a parameter, the parameters that follow must be named.
  

  
  scala> new Cat(name="Lua", 1)     
  :7: error: positional after named argument.
        new Cat(name="Lua", 1)
                            ^
  

No Default Values

• Redefine class Cat without supplying default values. This means values must be provided when instantiating a cat (more generically, calling a function).
  

  
  scala> case class Cat(name:String, lives:Int)
  defined class Cat
  

  
  
• Instantiate a cat providing both params, unnamed.
  

  
  scala> Cat("Java", 1)
  res9: Cat = Cat(Java,1)
  

  
  
• Instantiate a cat providing both params, named.
  

  
  scala> new Cat(name="Douglas", lives=42)          
  res10: Cat = Cat(Douglas,42)
  

  
  
• Attempt to instantiate a cat, not providing values for the arguments.
  

  
  :7: error: not enough arguments for constructor Cat:
  (name: String,lives: Int)Cat, unspecified parameters:
  value name, value lives
        new Cat
        ^
  

Overloading

• Redefine the class, overloading the constructor.
  

  
  scala> case class Cat(name:String="kitty", lives:Int=9){
      | def this(name:String) = this(name, -54)
      | }
  

  
  
• Instantiate a cat providing just the first argument, unnamed. Since the compiler does find a method with the exact signature (in this case - one String), it calls it.
  

  
  scala> new Cat("Martin")
  res11: Cat = Cat(Martin,-54)
  

  
  
• Here's a couple of other similar, and interesting cases. First, overload the constructor giving the argument a different name than the one defined in the primary constructor.
  

  
  scala> case class Cat(name:String="kitty", lives:Int=9){
      | def this(x:Int) = this("hello", x+99)   
      | }
  defined class Cat
  

  
  
• Instantiate a cat, using the keyword 'lives'. Since the overloading method uses the name x, and x!=lives, and the original constructor uses 'lives', that is the method that is invoked.
  

  
  scala> new Cat(lives=8)                                
  res12: Cat = Cat(kitty,8)
  

  
  
• Instantiate a cat - same as the String overloading case above.
  

  
  scala> new Cat(8)     
  res13: Cat = Cat(hello,107)