Jack Cough on Software

Tail Calls, Tail Recursion, TCO

2011-07-16T16:18:00.001-07:00

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

2010-12-14T14:08:00.000-08:00

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)

2010-11-27T19:12:00.001-08:00

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

2010-02-24T09:01:00.000-08:00

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

2009-11-13T20:32:00.000-08:00

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

2009-09-07T18:56:00.000-07:00

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.

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.
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.
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

2009-09-01T10:41:00.000-07:00

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?

2009-07-22T21:21:00.000-07:00

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

2009-07-04T21:30:00.000-07:00

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.

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.
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.
This code will be in an upcoming release of ScalaTest, and (pending discussions) could make its way into Specs as well.
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:

ALL test threads are blocked.
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

waitForTick(1) blocks the writer thread until tick 1 happens.
The reader threads all get the read lock.
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.
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.
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.
After tick 2, all the reader threads wake up. The writer thread is still blocked, waiting for the read lock.
The reader threads all give up the read lock in concert.
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

2009-06-24T19:00:00.000-07:00

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

2009-06-14T21:12:00.000-07:00

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).

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.
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.

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).
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

2009-06-01T08:51:00.000-07:00

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

2009-05-31T07:30:00.000-07:00

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

2009-05-30T20:31:00.001-07:00

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.

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

2009-05-30T14:25:00.000-07:00

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)
```

Teaching Functional Programming To Kids

2009-05-19T19:39:00.000-07:00

I started teaching some of the basic concepts of functional programming to my 8 year old son yesterday, and wanted to write a little about it. The wonderful thing about it is that kids really are ready to learn the concepts at a very young age. I'm not actually teaching him programming, just concepts, but when the time comes, he'll basically already know how to program.

I have what I think is an absolutely perfect example. It's one that all parents and kids can identify with: The Dr. Seuss Star Belly Sneetch machine.

This is a simple machine that takes in a Sneetch without a star on its belly, and spits out a Sneetch with a star on its belly. I'm just going by memory here to say that I think kids can probably understand this concept at the age of 3. In this post I'm going to use this style to represent machines:


               -----------
              |           |  
 Sneetch ---> |     *     | ---> Star Bellied Sneetch
              |           |
               -----------

This is the same as the actual picture above, but works for all cases since I don't have pictures for all the concepts I want to represent.

In the Dr. Seuss book there is also the opposite machine that removes the star from a star bellied Sneetch.


               -----------
 Star Bellied |           |  
 Sneetch ->   |     -*    | ---> Sneetch
              |           |
               -----------

While that seems really simple, it's all we need to start teaching a wide range of concepts to kids. I started with this one, because of its similarity with the machines above (for all the things below, Jacy and I worked them out on a whiteboard. But, paper is just as good):


            -----------
           |           |  
 10  --->  |     +5    | ---> 15
           |           |
            -----------

Here we have a machine that adds five to whatever you put into it. Very simple, very easy for kids to understand. It helps to run a few more inputs through (0, 10, a billion) just to let them know that the box doesn't just take 10 and give 15, it works with all numbers.

After this one I followed up with another very easy one.


            -----------
           |           |  
 10  --->  |     -5    | ---> 5
           |           |
            -----------

At this point he pointed out, "Well it could be a divided by two machine instead." This was unexpected, and impressive, and at some point I'll talk about it further...but not yet. It was great to feel that he was understanding it though.

Now that he was getting it, it was time to change things up just a little bit. I introduced the plus and minus machines, which take two inputs instead of one.


            -----------
 7   --->  |           |  
           |     +     | ---> 19
 12  --->  |           |
            -----------


            -----------
 12  --->  |           |  
           |     -     | ---> 5
 7   --->  |           |
            -----------

These presented no challenge whatsoever. In fact (I guess rather surprisingly), nothing I taught him presented any sort of challenge. Next I introduced the biggest and smallest machines (which we programmers call max and min).


            -----------
 7   --->  |           |  
           |  Biggest  | ---> 12
 12  --->  |           |
            -----------


            -----------
 7   --->  |           |  
           |  Smallest | ---> 7
 12  --->  |           |
            -----------


            -----------
 10  --->  |           |  
           |  Smallest | ---> 10
 10  --->  |           |
            -----------

I guess he was a bit surprised when I showed him the last one. But, it only took showing him the answer once for him to fully understand.

I then added an equals machine that spits out YES! if the two numbers are equal, and NO! if they aren't (true and false, obviously). This is different because now we were no longer working with numbers as the inputs and outputs.


            -----------
 7   --->  |           |  
           |     =     | ---> NO!
 12  --->  |           |
            -----------


            -----------
 7   --->  |           |  
           |     =     | ---> YES!
 7   --->  |           |
            -----------

Simple, but effective.

Now, Jacy and I have done considerable work with logic gates, and I wanted to show him how logic gates are really just like machines. I also taught him the word Function at this point, but didn't push it. Kids can relate to machines, not functions.


            ------------
 ON  --->  |            |  
           |  AND GATE  | ---> OFF
 OFF --->  |            |
            ------------


            ------------
 ON  --->  |            |  
           |  OR GATE   | ---> ON
 OFF --->  |            |
            ------------


            ------------
 ON  --->  |            |  
           |  AND GATE  | ---> ON
 ON  --->  |            |
            ------------

While the logic gate examples seem simple, it tied two worlds that we've been working on together very nicely.

Fun

My son has a really short attention span, and all the while I'm doing this I have to think of different ways to make it fun. If it's not fun, hes just going to go play video games. Rightfully so, video games are fun. There were a few ideas I tinkered with before settling on the Dr. Seuss machine. One was a monster that stuffs stuff into his mouth and then spits out the answer. I thought that one was kind of neat. The point is, if you plan on teaching your child, think of something fun they can relate to.

Combining Machines

I could sense we needed some more fun at this point, and we'd learned enough basic machines that I thought it would be great to start combining them. After trying this, I recommend starting with all alike boxes. We did something a little more complicated and I ended up going too fast, and fell back on this:


           -----------
 7   -->  |           |             -------
          |     +     | --> 19 --> |       |
 12  -->  |           |            |       |
           -----------             |       |
                                   |   +   | --> 39
           -----------             |       |
 10  -->  |           |            |       |
          |     +     | --> 20 --> |       |
 10  -->  |           |             -------
           -----------

After you get this first larger machine done, its pretty easy to add in more complicated machines. However, it might be good to wait until the next day, as Jacy was definitely getting it, but might have been getting a little fried. Here's an example though:


           -----------
 7   -->  |           |             -------
          |     +     | --> 19 --> |       |
 12  -->  |           |            |       |
           -----------             |       |
                                   |   =   | --> NO!
           -----------             |       |
 10  -->  |           |            |       |
          |     +     | --> 20 --> |       |
 10  -->  |           |             -------
           -----------

And obviously, change the 7 to an 8 and get a YES! Different kinds of boxes doing and spitting out different kinds of things. In essence, this is really all we do as programmers.

Types

Being a lover of static type systems, I also talked to him about types, by saying "kind(s) of things". For example, I asked him, "What kind of thing does this machine take in (or what kind of thing do you put into this machine)?"


            -----------
           |           |  
 10  --->  |     +5    | ---> 15
           |           |
            -----------

Answer: Number. I avoided Integer for now. What kind of thing does it spit out? Answer: Number.

I then showed him this next example, which should arguably have a section of its own:


            -----------
           |           |  
 D   --->  |     +5    | ---> I
           |           |
            -----------

This machine looks exactly the same as the machine above, except you put Letters into it, and it spits out letters. We also did months. Both are interesting because they have to loop around. I didn't have to teach him that, he just got it.

Then I introduced a formal notation for types:


            -----------
 7   --->  |           |  
           |     +     | ---> 19
 12  --->  |           |
            -----------

(Number,Number) -> Number

And introduced machines that change the type (he had seen it already, but only with YES! and NO! This, I think, is a better example):


            -----------
           |           |  
 5   --->  | To Letter | ---> E
           |           |
            -----------

Number -> Letter

He understands the notation and can write it if I give him slots to fill in like this:

______ -> ______

or

(______, ______) -> _______

Things I don't know how to teach, Yet

I certainly didn't try to teach him anything about machines that take in machines and spit out machines. Also, some of my boxes were polymorphic, but I don't think I know how to explain that to him.

For now, I think Jacy and I will just do this same stuff for a while, reinforcing it. I'm not sure what the best thing to teach him next is. Some of the stuff here I've skimped on writing up, and we actually spent more time on than it seems.

Anyway, this was all really, really fun, for both of us.

Refactoring in Scala

2009-05-14T19:49:00.000-07:00

Another really long post, but why not!

My Lexer is now approaching 500 lines with roughly 350 lines of test code. Maybe that's still trivial, but it doesn't feel trivial. Maybe it doesn't feel trivial because it does a lot. Those 500 lines of code cover so many features. Yesterday night I started to add a bunch more features, and realized a few spots needed some heavy refactoring to achieve what I want. Here's what I wanted to add:

New line support. Yes, my previous lexer could only lex one line at a time. Syntax errors indicated the offset, but not the line. A parser should know what line and file the token occurred in.

Better handling and testing of syntax errors.

Separate Scala lexing from Lexer core, providing a reusable Lexer framework for Lexing any language.

I had a few other goals as well. I wanted to have the tests be much more organized, mostly arranging for testing individual Finders. So far, everything was lumped together in one giant test. I wanted to do a general cleanup of my Lexer trait, and extract the mutability from it. And as usual, I wanted to make sure things were nice and clean and short and readable. I have a few goals on my plate that I didn't get to as well. Comments, Strings, Chars, peeking at the next token without mutating. Some of that stuff might require the Finders to be away of a Context of some sort. I hope not. Also, maybe I could write a preprocessor to replace any comments with white space.

Multi Line Support

Anyway, lets get to the new line support. Like I said, the main goal was to have better syntax error support, knowing the line and the offset, not just the offset. But the parser needs to more information that just the offset, as well. In order to do this, I decided to introduce the idea of a CompilationUnit, which holds all the code. Previously, the Lexer just worked with a single array.

Old code:


trait Lexer extends SyntaxErrorHander {
  var chars: FunctionalCharArray
  var currentIndex = 0

New code:


trait Lexer extends CompilationUnitWalker with SyntaxErrorHander {
  var unit: CompilationUnit

Notice something else important here. The old code held its chars and was responsible for handing its own mutation, and the mutation was a bit cluttered in with the lexing logic. It wasn't horrible, but not great. Now the mutation is all self contained in CompilationUnitWalker, who manages the current line and current character pointers. I'll save the listing for that trait until the end, as its where all the ugliness lives. But that's the good news, its no longer in Lexer. For now though, it helps to see the interface for that trait:


trait CompilationUnitWalkerInterface {
  var unit: CompilationUnit
  def skipChar: Unit
  def skipChars(i: Int): Unit
  def skipLine: Unit
  def currentLine: FunctionalCharArray
  def currentLineNumber: Int
  def currentOffset: Int
  def eofReached_? : Boolean
}

The finders need the current line, Tokens and errors need currentLineNumber and currentOffset, and the Lexer itself needs to know if it processed the whole file (eofReached_?), and needs commands to move in the array (the skip methods). Since some of this stuff wasn't in the original code, this was a refactoring and a feature add at the same time. No big deal though, just pointing it out.

I'll show the remainder of the Lexer code in the next section.

Syntax Error Handling

We're a little bit closer to getting syntax errors with line numbers in them. I didn't show the SyntaxErrorHandler trait in the last post, but it was trivial. It just took a SyntaxError Token (which I've decided was stupid because SyntaxErrors are not tokens), and it just printed them out. Here's both now:

Old code:


trait SyntaxErrorHander{
  def syntaxError(error:SyntaxError):Unit = {
    println(error)
  }
}

New code:


trait SyntaxErrorHander{
  def syntaxError(unit: CompilationUnit, 
                  lineNumber: Int, offset: Int):Unit = {
    println("Syntax Error(" + unit + ", line number:" + 
               lineNumber + ", offset:" + offset + ")")
  }
}

Not much different, but now the handler takes the CompilationUnit, and the line number and offset. Those are all we really need to handle the requirement. And I do it like this:


trait AddToCompilationUnitSyntaxErrorHander extends SyntaxErrorHander{
  override def syntaxError(unit: CompilationUnit, 
                           lineNumber: Int, offset: Int):Unit = {
    super.syntaxError(unit, lineNumber, offset)
    unit.syntaxError(lineNumber, offset)
  }
}

The code for calling into the syntax error handler in the Lexer actually shaped up nicely as well:


trait Lexer extends CompilationUnitWalker with SyntaxErrorHander {
  var unit: CompilationUnit

  def finders: List[FunctionalCharArray => Option[Lexeme]]

  def nextToken: Token = {

    // if we've already lexed the whole file, get the f out.
    if (eofReached_?) return EOF(currentLineNumber)

    // find all possible Lexemes
    val matches = 
      finders.map(f => f(currentLine)).filter(_.isDefined).map(_.get)

    // if we've found no lexemes, syntax error! adjust and try again.
    if (matches.isEmpty) {
      syntaxError(unit, currentLineNumber, currentOffset)
      skipChar
      return nextToken
    }

    // the longest match found should be on top...i think...
    val longestMatch = matches.sort(_.size >= _.size).head

    // deal with the best lexeme
    handleLexeme(longestMatch)
  }

  def handleLexeme(lex: Lexeme) = lex match {
    case NewLine => {
      skipLine
      nextToken
    }
    case WhiteSpace(_) => {
      skipChar
      nextToken
    }
    case lex => {
      val indexOfLexeme = currentOffset
      skipChars(lex.data.length)
      Token(lex, currentLineNumber, indexOfLexeme)
    }
  }
}

In the middle of the nextToken we check to see if matches is empty. If it is, we haven't found any Lexeme's and we call the syntaxError method with the current CompilationUnit (which we hold), and the currentLineNumber, currentOffset which we get from the walker. Done!

Also notice the handleLexeme method at the end, because this completes the first requirement. When it creates a new Token, it passes the currentLineNumber as well. I'm still debating putting the CompilationUnit in the Token as well. Certainly a parser will know which unit its working on, but it might be helpful. I guess I'll wait til I start writing my parser to find out.

Refactoring Towards Reuse

Refactoring Towards Reuse was by far the most broad and complicated requirement/idea in the set - I thought. But as it turns out, it only took a few minutes total. All I had to do was move a few files, change a few names, honestly almost nothing.

First, I created a package called scala under lex, created a Scala file called ScalaLexer.scala, and started pulling in anything that looked Scala specific. I ended up with this:


trait ScalaLexer extends Lexer with ScalaFinders with 
  AddToCompilationUnitSyntaxErrorHander

trait ScalaFinders extends
    ScalaCharFinders with NumberFinder with ScalaIdentifinder with
    WhiteSpaceFinder with CaseClassFinder with CaseObjectFinder

case object CaseClass  extends SimpleLexeme("case class")
case object CaseObject extends SimpleLexeme("case object")

object ScalaIOLBuiler extends IdentifierOnlyLexerBuilder{
  def apply(cu: CompilationUnit) = {
    new ScalaIOL{ var unit: CompilationUnit = cu }
  }
}
trait ScalaIOL extends IdentifierOnlyLexer with ScalaIdentifinder

case class ScalaTwoPartIdentifinder(
  w1: String, w2: String, l: Lexeme) extends
  TwoPartIdentifinder(ScalaIOLBuiler, w1,w2,l)

trait CaseClassFinder extends LexemeFinder {
  override def finders =
    super.finders ::: 
    List(ScalaTwoPartIdentifinder("case", "class", CaseClass).find _)
}

trait CaseObjectFinder extends LexemeFinder {
  override def finders =
    super.finders ::: 
    List(ScalaTwoPartIdentifinder("case", "object", CaseObject).find _)
}

trait ScalaCharFinders extends LexemeFinder {
  override def finders = super.finders ::: CharFinders(
      Underscore, Comma, Dot, Eq, Semi, Colon, LeftParen,
      RightParen, LeftCurly, RightCurly, LeftBrace, RightBrace
  )
}

I also moved Identifinder into the Scala package as well, since it's Scala specific. All in all, I didn't have to do much. It's only about 30 lines of code and a lot of it can probably be cleaned up and reduced further.

Now, if I wanted to lex Java I'd probably have to write a similar 30 lines of code, plus a JavaIdentifinder. I should do it, because then I'd find further areas for factoring out common code.

So I guess in my next installment I'll do just that, and, I'll show the testing at that point too. The testing is coming along really nicely. At some point I plan to contrast this code with the real Scala lexer code, and the tests for it (I still have to find those).

For now I'll give a quick snippit of the testing I did for handling multiple lines, but I'll wait to explain it:


trait NewLineTests extends LexerTest{

  test("new lines") {
    checkCode("x,\ny",
      (0,0) -> Identifier("x"),
      (0,1) -> Comma,
      (1,0) -> Identifier("y"))
  }

  test("more new lines"){
    checkCode("""x,
    y,
      z""",
      (0,0) -> Identifier("x"),
      (0,1) -> Comma,
      (1,4) -> Identifier("y"),
      (1,5) -> Comma,
      (2,6) -> Identifier("z"))
  } 
}

That's all for now. It's late.

Scala over Ruby - My Debate Ends

2009-05-14T19:08:00.000-07:00

I've maintained posts about things I like in better about Scala and/or Ruby, but, it's time to put an end to the debate. I've been doing Ruby every day for almost 6 months now, and finally conclude that for me, it just doesn't feel nearly as nice as Scala. It's not ever close, to be blunt.

My main reason? Refactoring. Over the years I've become very good at refactoring; I've actually been called a refactoring machine. I have a lot of experience refactoring really, really terrible code. Yes, this sucks, I have a history of picking the wrong job. Fortunately though, I also have some experience refactoring really nice code as well. The code that I'm working on now in Ruby is fairly new, and quite good. All the Scala code that I write is pretty good (room for improvement, but pretty good).

I can refactor so easily in Scala with huge confidence and I can't do that in Ruby at all. In Ruby:

It takes a long time to make major refactorings.

I'm never fully confident in my refactorings and almost always get annoyed by runtime errors.

Sometimes the stack traces are all messed up and I can't figure out where my actual error is.

Most code you run into isn't going to have enough test coverage to help anyway.

For all the preachers of TDD and instant feedback - tests untimately/inevitably take (far) longer than the compiler. So I really don't have the instant feedback I need.

If you skip refactorings in Ruby because they are hard, your code becomes harder and harder to refactor. This goes for statically typed languages as well, but, it's a lot harder with Ruby, especially considering the points above.

Ad infinitum...

In my next post I'm going to cover a bunch of major refactorings I just did to my Lexer, and how easy it was.

A Scala Lexer

2009-05-12T17:00:00.001-07:00

This is a really long post, but IM(not so)HO, its really fun!

Sunday I decided, "I'm going to write my own Lexer for Scala", simply because I felt like it. I'm only about 8 hours in, but I've got a lot of functionality. And its only about 300 lines of code so far. Now, that 300 lines doesn't cover nearly all of Scala. It's lacking XML handling, and comments, has limited support for numbers, and String literals, Unicode characters and error handling. But, it does have a lot of nice features including the ability to understand most (maybe all) identifiers, and operators.

There are other really nice things about it as well. First, its very functional - it uses HOF's to recognize tokens and it's mostly immutable, with its mutable state isolated to one very small area. Second, the tests for it are simple end elegant. Third, its quite reusable, as I've managed to leverage several components from within itself.

Before I get to the implementation, let me show how to use it. It can be done very simply at the command line. Example:


scala> import com.joshcough.compiler.lex._
import com.joshcough.compiler.lex._

scala> val code = "x"                                    
code: java.lang.String = x

scala> val lexer = new SimpleLexer(code) with Identifinder
lexer: com.joshcough.compiler.lex.SimpleLexer with com.joshcough.compiler.lex.Identifinder = SimpleLexer(FunctionalCharArray([C@b6aea4))

scala> lexer.nextToken                                   
res0: com.joshcough.compiler.lex.Token = Token(Identifier(x),0)

scala> lexer.nextToken                                   
res1: com.joshcough.compiler.lex.Token = EOF(1)

In this code I create a Lexer only capable of recognizing identifiers by mixing in the trait Identifinder (and yes, that trait name is awesome). The "code" that I use here is simply the String x. When I ask the lexer for its tokens, it gives me back exactly what I'd expect, Token(Identifier(x),0), and EOF(1). This means it found the identifier x at offset 0, and found EOF at index 1. Simple, but obviously not yet very useful. Luckily, the identifier recognition is much more powerful. Let's see some more examples (From now on, where appropriate, I'll remove redundant type info from the output or replace it with "...", and simply indent the output):


scala> lexer lexing "-->"

scala> lexer.nextToken
 Token(Identifier(-->),0)

scala> lexer.nextToken
 EOF(3)

scala> lexer lexing "_ewrk_1212_adf435445_^^^"

scala> lexer.nextToken
 Token(Identifier(_ewrk_1212_adf435445_^^^),0)

Much better. But what happens if I pass in something that the lexer shouldn't understand?


scala> lexer lexing "1"

scala> lexer.nextToken
 SyntaxError(0)
 res4: com.joshcough.compiler.lex.Token = EOF(1)

Not too terrible. "1" isn't a valid identifier and since this lexer only recognizes identifiers, it spits out "SyntaxError(0)", because it did not recognize the input starting at position 0. Now, this is actual System.out output. That's all you get by default. The actual Scala compiler simply adds an error to the Compilation unit with the offset. There really isn't much a lexer can do with errors. Later, I'll show how we can cache them off as well.

The last lexer failed to recognize numbers. That's easy enough to fix. Simply mix in NumberFinder:


scala> val lexer = new SimpleLexer(code) with 
  Identifinder with NumberFinder   

scala> lexer lexing "123"                                                 

scala> lexer.nextToken
 Token(Number(123),0)

scala> lexer lexing "-->"

scala> lexer.nextToken   
 Token(Identifier(-->),0)

Now we can recognize identifiers and numbers. Next up we'll start recognizing all of these single characters: [ ] { } ( ) , . : _ = ; This as just as easy as the others - just mix in CharFinders


scala>lexer lexing "(x,y);"

scala> lexer.nextToken      
 Token(LeftParen,0)

scala> lexer.nextToken
 Token(Identifier(x),1)

scala> lexer.nextToken
 Token(Comma,2)

scala> lexer.nextToken
 Token(Identifier(y),3)

scala> lexer.nextToken
 Token(RightParen,4)

scala> lexer.nextToken
 Token(Semi,5)

Notice that we haven't seen any white space yet. In fact, the lexer here isn't yet capable of handling white space. To do that - you guessed it - mix in WhiteSpaceFinder.


scala> val lexer = new SimpleLexer(code) with Identifinder with
 NumberFinder with CharFinders with WhiteSpaceFinder
lexer lexing "( x , y );"

scala> lexer.nextToken                                                                                            
 Token(LeftParen,0)

scala> lexer.nextToken
 Token(Identifier(x),2)

scala> lexer.nextToken
 Token(Comma,4)

scala> lexer.nextToken
 Token(Identifier(y),6)

scala> lexer.nextToken
 Token(RightParen,8)

scala> lexer.nextToken
 Token(Semi,9)

Notice that like any good lexer, this lexer simply skips over the white space, handing you the next actual token at its right location.

There are a few more, such as RocketFinder (finds =>), CaseClassFinder (finds "case class" and returns it as one Lexeme instead of two seperate identifiers), and CaseObjectFinder (which does exactly the same thing). But, I'm not going to show examples of their usage. I want to get to the implementation.

Lexer Implementation

Earlier I made claim that the Lexer was "mostly immutable". Of course, it has to be somewhat mutable to return something different to the parser on successive calls to nextToken. To do this, the Lexer uses a FunctionCharArray, which is just a very thin wrapper around Array[Char].


case class FunctionalCharArray(chars: Array[Char]) {
  def skip(i: Int) = new FunctionalCharArray(chars.drop(i))
  def size = chars.size
  def nextChar: Option[Char] = get(0)

  def get(index: Int): Option[Char] = {
    if (chars.size > index) Some(chars(index)) else None
  }
}

Taking a brief peek into the Lexer we find that its the FunctionCharArray that is mutated:


trait Lexer extends SyntaxErrorHander {

  var chars: FunctionalCharArray

  var currentIndex = 0

  def finders: List[FunctionalCharArray => Option[Lexeme]]

  ...

There are a few other interesting bits here. The lexer also mutates its currentIndex. It puts the currentIndex into the Tokens when Lexemes are found. We'll see how that works just a bit later on. Most importantly though, is the fact that almost everything else runs through the Lexer's finders.

The finders are actually quite simple. Given a FunctionalCharArray, the finders return an Option[Lexeme]. They return Some(Lexeme...) if they found what they expected at the very beginning of the array, and None otherwise. The remainder of the array is simply ignored by the finder. A few simple examples should help.

The Identifinder returns Some(Identifier(x)) when its given the an array containing 'x' as its only element, and None if the first character in the array is a character that can't legally start an identifier.
The NumberFinder returns Some(Number(123)) when given this array: ['1', '2', '3', ' ', '+', ' ', '7']
The CharFinders only ever look at the first element in the array.

To fully demonstrate just how simple they are, we need to see some. Have at you!


trait WhiteSpaceFinder extends LexemeFinder {
  override def finders = super.finders ::: List(findWhiteSpace _)

  def findWhiteSpace(chars: FunctionalCharArray): Option[Lexeme] = {
    chars.nextChar match {
      case Some(' ') | Some('\t') | Some('\n') => Some(WhiteSpaceLex)
      case _ => None
    }
  }
}

The first thing to notice about this finder is that it immediately adds a finder method to it's super. This is what enabled us to keep mixing in finder after finder in the beginning of this post.

The finder that it adds is its own findWhiteSpace method. As I explained, it takes a FunctionalCharArray and returns an Option[Lexeme]. In this case, it peeks at the top character in the array, and it that char is a space, tab or new line, it returns a Some with the Lexeme, and if its not, it returns None. Simple.

That one is pretty trivial though, it only needs to look at one character. Let's take a look at one that's more involved. Here is a version of CaseClassFinder. It's not the exact implementation, but I've only changed it slightly to help demonstrate.


class IdentifierOnlyLexer(var chars: FunctionalCharArray) extends
  Lexer with WhiteSpaceFinder with Identifinder

trait CaseClassFinder extends LexemeFinder {
  override def finders = super.finders ::: List(findCaseClass _)

  def findCaseClass(chars: FunctionalCharArray) = {
    if (chars.size < 10) None
    else {
      val lexer = new IdentifierOnlyLexer(chars)

      (lexer.nextToken, lexer.nextToken) match {
        case (Token(Identifier("case"), _), 
              Token(Identifier("class"), _)) => {
          Some(CaseClass)
        }
        case _ => None
      }
    }
  }
}

I love this example because it's small, but not trivial, and because it reuses components in the lex package. Before I explain, let's think about what a CaseClassFinder should do. If it see's "case", followed by "class" at the beginning of the array, then it should return the Lexeme CaseClass. Otherwise, it should return None. But, its more important to think about that in a slightly different way:

If a CaseClassFinder finds the Identifier "case" followed by the Identifier "class", then it should return CaseClass.

Well, we already know how to find identifiers...it was the first thing I showed in this post! As it turns out, that's exactly how CaseClassFinder does it as well. It creates a new Lexer with its input, an IdentifierOnlyLexer (technically, it could fire up a Lexer with all the finders, but it's overkill). It then asks the Lexer for its first two tokens, and if those Tokens contain the Lexemes Identifier("case"), and Identifier("class") the it knows its found a case class. BAM!

The Indentifinder and NumberFinder traits are too long to show here. I'll post a link to the codebase.

Now, we have a few things to do to wrap up. I still need to show the how the Lexer itself actually uses the finders. And, the astute reader might have already realized that two finders might both return a Lexeme. For example, given the Array [':',':'], the Colon finder would return Colon, and the Identifinder would return Identifier(::). The Lexer handles this case easily. The real value must be the longer of the two. Simple as that. Now lets take a look at all of Lexer.

Lexer Implementation (for real this time!)


1 trait Lexer extends SyntaxErrorHander {
2  
3   var chars: FunctionalCharArray
4   var currentIndex = 0
5
6   def finders: List[FunctionalCharArray => Option[Lexeme]]
7
8   def nextToken: Token = {
9 
10    def skip(i: Int) {currentIndex += i; chars = chars.skip(i)}
11
12    val token = nextToken_including_whitespace_and_syntaxerror
13
14    token match {
15      case SyntaxError(i) => {
16        syntaxError(SyntaxError(i))
17        skip(1)
18        nextToken
19      }
20      case EOF(_) => token
21      case Token(WhiteSpaceLex, _) => skip(1); nextToken
22      case Token(lex, _) => skip(lex.data.length); token
23    }
24  }
25
26  private def nextToken_including_whitespace_and_syntaxerror = {
27    if (chars.nextChar == None) EOF(currentIndex)
28    else {
29      val lexemesFound: List[Lexeme] = {
30        finders.map(f => f(chars)).filter(_ match {
31          case Some(t) => true
32          case _ => false
33        }).map(_.get)
34      }
35
36      if (lexemesFound.size == 0) return SyntaxError(currentIndex)
37    
38      val lexemesSorted = 
39          lexemesFound.sort(_.data.size >= _.data.size)
40
41      Token(lexemesSorted(0), currentIndex)
42    }
43  }
44
45  def lexing(s: String): Lexer = {
46    lexing(new FunctionalCharArray(s.toCharArray))
47  }
48
49  def lexing(cs: FunctionalCharArray): Lexer = {
50    chars = cs; currentIndex = 0; this
51  }
52}

First, look at the nextToken_including_whitespace_and_syntaxerror which starts on line 26. This method returns the best Token possible (like :: vs : ), but more importantly, it always returns a Token. It returns WhiteSpace and SyntaxError tokens as well. The calling method, nextToken, is the guy in charge of filtering those out, resetting, and continuing. But, well get to that in just a second. For now, lets enumerate the nextToken_including_whitespace_and_syntaxerror methods steps.

The first thing it does is check if there are any characters left. If there are none, it simply returns EOF. Any more calls to nextToken will continue to return EOF until the Lexer gets new data (via the lexing methods).
It then calls all of its finders with the current array: finders.map(f => f(chars))
It then immediately filters the results, because its only interested in any finders that actually returned Some(Lexeme...), and not none. Of course.
At that point (line 36) it checks to see that someone actually found a Lexeme (if (lexemesFound.size == 0) return SyntaxError(currentIndex)). If no finders found anything, the we must have some unrecognized character in the input. Syntax Error!
On line 38 it sorts the Lexemes by size, aiming to get the largest.
Finally it returns the largest token (ignoring any other matches).

Now I'll explain the nextToken method, and then wrap up.

The first action nextToken takes is to call the nextToken_including_whitespace_and_syntaxerror on line 12. With that token, it must make a decision.

If it receives a SyntaxError, then call the notify the syntax error handler of it, and in an attempt to reset/restart - move ahead one space in the input, and recur.
If it receives an EOF, just hand it over to the Parser, it should know what to do with it.
If it receives WhiteSpace, then also move ahead one space and recur. There might be a better strategy here (and/or for syntax errors), but this one is simple, and works ok.
Finally, if it gets a legitimate token, then move the entire array ahead by the length of the Lexeme that was found, and return the token. The next time nextToken is called, it should start at the new location, one character beyond the end of this token.

Wrapping up, the way I've implemented this, I don't think it will be that difficult at all the add in missing features. XML will probably be a bear, just because. I guess I don't have String literal support at all, so I'll add that next, and Char literals too. They should be mostly straightforward.

If you're actually still reading, awesome! Thanks! I hope you've learned something. You can find all the actual source code here. Not bad for about 8 hours huh?

Oh BTW, my only two references for this were the Dragon Book (2 ed), and the Scala compiler itself.

Bye!

Typed Lambda Calculus For Me (And Maybe You)

2009-05-04T20:13:00.000-07:00

I'm reading chapter 10 of Lambda-Calculus and Combinators by J. Roger Hindley and Jonathan P. Seldin, and I wanted to put down some notes. These notes are mostly for myself, much in the spirit of why I started this blog - to measure my own progress. However, since I know I have readers I'll write it in a way that people learn something. If people are interested in this though, since I'm already investing time in it, I'd be happy to do into more detail on the beginners stuff and/or some of the history behind this (I might just do it anyway). Also if anyone smarter than me finds any errors here, or has tips to explain it better, please do. Okay Go.

In the book there is this nugget:


(λx:p->ø->t.
 (λy:p->ø.
   (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t
 ):A
):B

You (the reader) are supposed to solve this for A and B.

For those of you unfamiliar with lambda calculus, and/or typed lambda calculus, this is a lot easier than it looks. What I'll do here is try to explain the steps nice and slow, and then at the bottom maybe try to write this in Scala to demonstrate.

Explicit Type Information

Ok, the important thing here is that we are given a lot of information. Here's a list of the things we definitely know about the types in the statement above:

x:p->ø->t

y:p->ø

In more detail:

x is a function that takes a p and returns a function that takes an ø and returns a t.

y is a function that takes a p and returns an ø

z is simply a p

Or in Scala:

val x:p=>ø=>t

val y:p=>ø

val z:p

How do we know this? Well, that's basic typed lambda calculus. Here are a couple of very basic notes:

The statement (λx:p->ø->t.M) is a function that takes an argument, x, which is of type p->ø->t. Arrows imply function types and hence x is a function that takes a p and returns a function that takes an ø and returns a t.

The return value of the function in this tiny example is M (above is much more complicated, but that's what were getting to).

Function Application

Now, using what we know about the types, and the rest of the statement, what else can we figure out? Hmm, I guess we should talk about function application, by looking at the innermost bit of the statement above.

We see this: (x:p->ø->t z:p):ø->t, and this means we are calling the function x with the argument z. Remember that everything after the colons are simply types. Ignoring the types, we could just write (x z) which is basic function application in lambda calulus. In Scala this would be simply x(z). And what type does calling x yield? Not to beat it into your brain, but remember that x is a function that takes a p and returns a function that takes an ø and returns a t. Calling it with a p will yield a function that takes an ø and returns a t, or more simply ø->t.

In the original statement, we had (x:p->ø->t z:p):ø->t, and this is correct, as I just explained.

That isn't the only function application in the statement either. Right next to it we see (y:p->ø z:p):ø. Does this check out? Remember that y is a function that takes a p and returns an ø, and z is a p. Perfect. Applying y with argument x yields a ø.

Now, that fact that I said "right next to it" is meaningful. Now that we've resolved the first two applications, we end up with another application! The result of the first application ((x:p->ø->t z:p):ø->t) was ø->t, and the result of the second was a ø, and these also match. Applying ø->t to an ø results in a t. And now we've finished this big inner statement: ((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t.

Building Functions

Now that we've looked at the internal parts of the statement boiling it all down to a t, we can start to work our way outwords. Recall that λ is used to denote a function. λx:Int."hey" is a function that takes an Int (named x) and returns a String, "hey". Fully typed this would be (λx:Int."hey"):String

Working our way one step outwards from our function applications, we have (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t. Recall that we already determined the inner part to be a t. We can now thing of this as (λz:p.(some arbitrary t)):p->t. And that's correct. This is a function that takes a argument z of type p, and returns a t. Hence its type: p->t.

Solving for A

Lets take a look back to remember what were trying to solve. One thing we need to find is A:


(λy:p->ø.
   (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t
 ):A

We've already determined the inner part to be correct - its p->t. Using what we just learned about creating functions with λ, and what we learned about types earlier, we know that (λy:p->ø. whatever):A builds a function that takes an argument, y:p-ø. That is - an argument y of type function from p to ø.

Additionally, this new function returns an A. But remember that the type of a function is not just its return type, it is (input type -> output type). So A must be the functions input type (which we know to be the type of the argument y, or p->ø) -> the functions return type (which is the return type of the inner statement, which we solved earlier to be p->t).

A is (p->ø)->(p->t).

Solving for B

To Solve for B, we do exactly what we did solving for A.

Recall:

(λx:p->ø->t.
 (λy:p->ø.
   (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t
 ):A
):B

Or:

(λx:p->ø->t.whatever:A):B

Clearly the first half of B (the input type) is (p->ø->t). The output type is the type of whatever, which (from looking just above) is A.

So B is (p->ø->t)->A

And fully expanded:

B is (p->ø->t)->(p->ø)->(p->t)

Formal Listing

This came directly from the book. I'm not sure if I can even legally put this all here. If I hear that I can't, I'll immediately take it down. All the information here is explained in detail above.


x:p->o->t     z:p             y:p->o     z:p
-----------------            ---------------
     (xz):o->t                      (yz):o
--------------------------------------------
                (xy(yz)):t      
           -----------------------
            (λx:p.(xy(yz))t):p->t
-----------------------------------------------
(λy:p->o((λx:p.(xy(yz))t)p->t)): (p->o)->(p->t)
------------------------------------------------
(λx:p->o->t ((λy:p->o((λx:p.(xy(yz))t)p->t)): 
  (p->o)->(p->t))): (p->o->t)->(p->o)->(p->t)

The Scala Code To Prove It


trait Lambda {
  type p
  type ø
  type t
  type A = (p=>ø)=>(p=>t)
  type B = (p=>ø=>t)=>A

  val f:B = {(x: p => ø => t) => {(y: p => ø) => {(z: p) => {(x(z)(y(z)))}}}}
}

Scala Testing Presentation Outline

2009-04-25T22:53:00.000-07:00

Here's the outline for my upcoming presentation on Scala and Testing. It's a bit ambitious, and I know I won't get through it all, but that's okay. If there's anything glaringly missing, now is the last chance to let me know. It also seems like this could be the start of something bigger, like a short book called something like, "Scala Testing for Java Developers"...maybe. However, the talk is only geared toward Java developers for the first few minutes or so.

Without further ado:


1) The prereqs ... Just Java code
        a) "Production" code
          - A simple List interface
          - An ugly LinkedList implementation
        b) Testing Java with Java
          - JUnit
          - Testng

2) The basics ... Testing Java code with Scala
        a) JUnit with Scala
         - JUnit3 (test, setup/teardown)
         - JUnit4 Annotations
        b) TestNG with Scala
         - @Test
         - @DateProviders
         - All Annotations available

3) The basics ... More testing Java with Scala - Intro to ScalaTest
        a) Suite
         - test methods
         - assert with ===
         - expect(x){}
         - intercept
        b) BeforeAndAfter
        c) TimedTest (displays time information for each class and test ran)
        d) TestNGSuite
         - decorate original TestNG test from step 3, "with TestNGSuite"
         - run in both runners

4) Scala extending/implementing Java classes/interfaces
        a) ScalaLinkedList (simple extention of Java LinkedList class)
        b) ScalaMutableList (ugly impementation of simple List interface)

5) Testing Scala with Scala
        a) Briefly redo #4 - but by testing the new Scala code. 
        b) minor intermission - Can we backtrack and test the new Scala code with Java?

6) A nicer, Functional List implemention in Scala

7) Testing Scala with Scala
        a) FunSuite
          -(including HOF's for those who don't know...maybe?)
          -explain how tests methods work

8) Advanced ScalaTest
        a) ScalaTest matchers (in a FunSuite)
        b) Overview of OOTB matchers
          -String, List, Hash, Option matchers, etc.
        c) Combining matchers with and/or
        d) Extending ScalaTest matchers - Creating your own matchers

9) Specs
        a) Specifications
        b) Matchers
        c) Extending Specs matchers - Creating your own matchers

10) Mocking in Scala (via Specs)
        a) Mockito
        b) JMock

11) ScalaCheck (via ScalaTest Checkers)
        a) Properties
        b) Generators
        c) Arbitrary Magic

12) Ant
        a) ScalaTest
        b) JUnit Scala and Java run together
        c) Specs runs as JUnit
        d) TestNG Scala and Java run together

13) Scala Frameworks Interoperability
        a) ScalaTest and Specs
        b) ScalaTest and ScalaCheck
        b) Specs and ScalaCheck

IntelliJ Now Supports ScalaTest

2009-04-19T18:18:00.001-07:00

IntelliJ 8 now has support for ScalaTest (at least as of build 9805). I believe it comes in via the Scala plugin. It works, but, when I right clicked on my test class I expected to see a run option for ScalaTest and I didn't, which stinks. Not seeing it also made me think it just didn't work. It does.

To run a ScalaTest test in IntelliJ, you have to add a run configuration. Most Intellij users probably know how to do this, but for those who don't, here are the steps.

Click "Edit Configurations" in the Run menu dropdown (right next to the green play arrow).

Click the + button to add a new run configuration. This brings up a dropdown containing different runners.

ScalaTest is in the list, choose it.

Fill in the classname of your test by typing it, or selecting the "..." button to bring up the class finder dialog.

Click ok.

Run!

Thanks IntelliJ Scala guys! Now if you can only get that right click thing working...

Quotes

2009-04-19T11:46:00.000-07:00

Quote from Gilad Bracha

"Tangent: Yes, I did spend ten years at Sun. A lot of it was spent arguing that Java was not the final step in the evolution of programming languages. I guess I’m just not very persuasive."

Gilad is one of my heroes. The work he's doing on Newspeak seems very, very promising.

Sun totally failed in ignoring him. I remember when he left he posted an unflattering blog about Sun, about how he felt that he couldn't get anything done there. He was very frustrated. I'm very glad to feel like I have something in common with such a smart guy.

Quote from Anders Hejlsberg

From Masterminds of Programming, which is (so far) an absolutely fabulous book:

"I think to be really good at something, you have to be passionate about it too. That's something you can't learn. That's just something that you have, I think. I got into programming not because I wanted to make lots of money or because someone told me to. I got into it because I just got totally absorbed by it. You just could not stop me. I had to write programs. It was the only thing I wanted to do. I was very, very passionate about it.

You have to have that passion to get really good at something, because that makes you put in the hours, and the hours are the real key. You need to put in a lot of work."

Anyone who knows me well knows that this describes me exactly. I particularly like, "You just could not stop me. I had to write programs, It was the only thing I wanted to do." I guess I have an important quality in common with another of my heroes. For some childish reason, I'm very excited about this.

Quote from Bill Venners

"I charge $1 for each paren, and $598 for knowing where to put them!"

'Nuff said!

Tests and Booleans and Matchers

2009-04-17T12:07:00.000-07:00

I was working with the new ScalaTest matchers API recently when I came across something that made me think (I usually don't think). I had something simple like:


Nil.empty must be(true)

This seems harmless enough, but when I made it fail intentionally the error message I got was something reasonably similar to:


Expected true but got false.

This obviously isn't a very good error message, and I was thinking at first the maybe we should provide the user API to provide their own error message. Something like so:


Nil.empty must be(true, "expected Nil to be empty, but it wasn't!")

This also seems harmless enough. However, I talked this over with Bill Venners and in this case there is a way to do it using symbols and reflection that gives better error messages:


Nil must be('empty)

If this fails, it will give a nice error message like:


Nil was not empty

This is ok, but type safety people will scream, and they'd probably be right. And, does this work in all cases and can we always get good error messages? I think no. Let me explain why.

What if we have an object that has a method that takes an argument and returns a boolean like this theoretical surroundedBy method that could exist on String:


def surroundedBy( s: String ) = startsWith(s) && endsWith(s)

We can't use the symbol form here because the method takes a parameter. So what can we do? If we go back to the original form then we are back to our original bad error message.


"htth".surroundedBy( "h" ) must be (true)
"http".surroundedBy( "h" ) must be (false)

Do we have any other options? Yes (with caveats as well). But first lets think about what we'd really like to write here. If we were writing pure English, it would be this:


"htth" must be surrounded by "h"
"http" must not be surrounded by "h"

Matchers

ScalaTest 0.9.5 came out with a new Matchers API that I'll touch on briefly here, and point you to documentation for more. Using matchers, we can get our client code pretty close to this. We'll have to define our custom matcher first:


case class surroundedBy(r:String) extends BeMatcher[String] {
  def apply(l: String) =
    MatchResult(
      l.surroundedBy(r),
      l + " was not surrounded by " + r,
      l + " was surrounded by " + r
    )
}

And our client test code turns out to be pretty close to the English:


"htth" must be(surroundedBy("h"))
"http" must not be surroundedBy("h")

I like this a lot, but, only if its going to be used a lot. Otherwise, if it's a one off test, I could just kick it back way old school and use an assert with an error message:


assert( "htth".surroundedBy("h") === true,
     "expected http to be surrounded by h, but it wasnt." )
assert( "http".surroundedBy("h") === false,
     "expected http not to be surrounded by h, but it was!!!" )

This is less readable code, but it is less code - about 6 lines less when you include the custom matcher. You get more or less the same error message in this case as well. It is quite ugly though. In this case I'd much rather have an API that just gives me what I originally wanted:


"htth".surroundedBy("h") must be(true,
 "expected htth to be surrounded by h, but it wasnt.")

or better:


"htth" must be('surroundedBy, "h")

I could see this one existing easily. It's really nice, but not type safe.

Anyway, maybe there already are better alternatives like the ones I've explained I simply don't know about. Maybe I haven't done my homework and I should be scolded. I really hope not, and I'll happily write up (and more importantly - use) anything I find that helps make this code more readable. Until alternatives surface, I guess I'll somewhat reluctantly stay with these rules:

When testing methods that return booleans you can

Use the symbol style ('empty) if the method takes no arguments and you aren't terrible concerned about type safety.

Use old school assertions when the method takes arguments but you won't have a lot of repetitive tests for the method.

Use a custom matcher otherwise

You'll also find that ScalaTest (and Specs which is unfortunately not covered here) provides many matchers that can use for many common types.

In my next post I'll provide a much deeper overview of how to write your own custom matchers in ScalaTest, starting by explaining what that surroundedBy case class means.

In the meantime, you can look at ScalaTest Matchers and Specs Matchers.

Here's all the custom matcher code:


package org.scalatest.examples
 
import org.scalatest.matchers.MustMatchers._  
import org.scalatest.matchers._


class MatcherTest extends FunSuite with MustMatchers{
 
  implicit def surroundable[T](l:String) = new {
    def surroundedBy(r:String) = l.startsWith(r) && l.endsWith(r)
  }
  
  case class surroundedBy(r:String) extends BeMatcher[String] {
    def apply(l: String) = 
      MatchResult(
        l.surroundedBy(r), 
        l + " was not surrounded by " + r, 
        l + " was surrounded by " + r
      )
  }
  
  test("weve got the place surrounded"){
    "htth" must be(surroundedBy("h"))
    "http" must not be surroundedBy("t")
  }
}

ScalaTest IDE Support coming soon.

2009-04-12T20:34:00.000-07:00

I've written something that allows me to write my tests in ScalaTest as normal (don't have to use any TestNG annotations in my tests), but also run them in all the IDE's, piggybacking off the TestNG IDE plugins. The code isn't in ScalaTest yet, but I'm guessing it likely will get in soon.

Until then, anyone using FunSuite can borrow this code and temporarily use MiniFunSuite instead. This all seems to work quite well.

Here's the client/test code:


class FunSuiteExample extends FunSuiteTestNGAdapter{
  test("hey"){ println("hey") }
  test("fail"){ assert( 1 === 2 ) }
}

And here's the library code:


import org.scalatest.testng.TestNGSuite
import org.testng.annotations.{DataProvider, Test}

trait MiniFunSuite{
  var testMap = Map[String, Function0[Unit]]()
  def test(name:String)(f: => Unit) = testMap += (name -> f _)
}

trait FunSuiteTestNGAdapter extends MiniFunSuite with TestNGSuite{

  @DataProvider{ val name="tests" }
  def tests = testMap.map{ case (s,f) => Array(s,f) }.toList.toArray

  @Test{ val dataProvider = "tests" }
  def scalaTest(testName:String, f: => Unit) = { f }
}

Twitter/Ruby/Scala/Blah

2009-04-08T05:33:00.000-07:00

For some reason I feel compelled to chime in on this debate. I like both languages. I like Scala more, but Ruby is fun.

(Reader Beware: This post was written in one pass with little to no editing.)

I don't like how people get all steamed about their languages, as if it's part of them. But, if used properly, this energy can be channeled into creating better languages, so I guess its a necessary evil. The problem is, it not often used properly. Developers seem to just get mad at each other instead of talking through things civilly, and thinking critically and objectively. This is nothing new, and nothing that hasn't been said a thousand times I'm sure, but I think serves well as a nice introduction.

Maybe the problem is that so many of the elements of programming languages are based on feel, as opposed to simple fact. I wish we'd all think more logically and have nice intelligent debates, and I wish we could support our arguments more with fact.

Now for a debate. I was tweeting with Daniel Spiewak who said,

"Obie has once again decided to completely miss the point. Twitter's legacy code is bad *because* of Ruby, not in spite. The experiences described by @stevej and @al3x precisely mirror my own: it isn't impossible to write large, maintainable Ruby...just hard."

I asked him if he could elaborate on "because of", and to that he replied,

"Ruby makes it *hard* to architect a large infrastructure and to keep it maintainable. I think that dynamic typing is part of the problem, but not all of it. Possibly the way the module system works? It isn't impossible to do large apps in Ruby (as Obie and Ola remind us), but it takes more effort and more discipline. Java and Scala both make this sort of large scale code base much easier to create and maintain."

Now, I don't necessarily disagree with that (and recall that I do like Ruby). But I'd like to point out that I've been on a lot of Java projects that were completely unmaintainable. You could easily call them absolute disasters. In fact, the majority of the Java projects that I've been on have been disasters (yes, yes get your laughs in and tell me that its my fault...but its not. I did a lot to help those failing/flailing projects). Maybe that's because I've picked bad projects, and haven't many changes to work with great teams on applications built correctly from the start.

But, I think that emphasizes my point a little. Who has? How many projects are built correctly from the ground up, by talented, disciplined developers? I'd say not many. Most developers are horrible, and the language wouldn't make a shred of difference. And for those developers who are really good, the language probably doesn't make that much difference either. A group of solid developers could easily build something far more maintainable in Ruby than the garbage developers who are writing in Java.

But can those same developers build something more maintainable in Java or Scala? I think it depends on a whole number of things (listed at the end of the post). If there's a good chance of turnover on the project, then you probably want something with type information in the code because it serves so well as documentation. But if there's little chance of turnover it probably doesn't matter.

That said, even with turnover, because Ruby is inherently higher level that Java its probably more easy to maintain. Java is just not a good language anymore, it has not stood the test of time. It came about to fix some problems with C++, and had a syntax that appealed to those developers, but that was 1994. It has not evolved. Ruby is so much more expressive than Java that the lack of type information probably doesn't mean much at all.

Scala on the other hand, probably no contest for large projects. I think Twitter made the right decision. They get the type safety, the type documentation, and the high level expressiveness all together. I do like Ruby a lot, but Scala just feels better to me, and feel is very important, even if its not measurable.

But all that could be wrong. How many large projects have actually been built in Scala? Few. I said in the beginning that I want people to think critically and objectively. It would be nice if we could base some of these debates on fact. Are there any facts out there that large Java projects are more maintainable than Ruby? There may well be, and if so, we should get that information out there. Then again, there may be documentation that supports the opposite.

So I'm not really calling for comments here, though they are always welcome. What I am calling for is experiments, evidence, observations, or facts that support that one language is more maintainable than the other for any sized project.

Here are some questions whose answers would be helpful (in no particular order):

What language was used?

What was the size of the project:
1. LOC? Production and Test code.
2. Number of developers?
3. Number of testers?

How long did the project take?

What was the amount turnover?

What was the experience level of the developers?

The amount of time the team has been together?

The amount of time the developers have spent with the language used?

Type of project? (Obviously if the language chosen was a horrible choice for the project, it makes a difference)

This information is probably pretty difficult to come by. The lack of it shouldn't impede intelligent debate, but the presence of it could help us as a community.

Random Thoughts

2009-04-04T20:14:00.000-07:00

I haven't written in a while, but that doesn't mean that a lot hasn't been going on, just nothing I really felt the need to write about unfortunately. I do have some random thoughts about some things though, and so here they are.

Little Things

I've noticed in some of the comments on my posts that people like to point out that some of the things I mention are no big deal - like not having to put a dot in a method call:


p ! t

vs.

p.!(t) or in Ruby: p.! t

I'd like to point out that sure, they are little things. But, little things add up. The more and more of the little things that a language gets right, the more of a joy it is to program in. Scala seems to get a lot of these things right.

Java 7

I remember months ago (at least 4) I asked, "will Java 7 ever come out?" I did a brief google search and see no evidence that its any closer. Why is this? It's insane.

I think the main reason is (so many people have realized and stated this before) that programming language by committee is BS. There must be a dictator running the show. I hope this is a road that Scala doesn't go down.

There are plenty more reasons of course. Holding on for dear life to backwards compatibility is a bad idea IMO. If companies don't want to move forward to a new version because something has changed, then well, you aren't really at risk of losing them as users anyway. If they want to stay on the old version, let them. As a language designer you should not sacrifice the language. You should always do your best to put out the best language possible. If the language is the best, then when the company finally decides to move off the old version, they will move to the latest version. If your language isn't the best, they won't. No big deal.

ScalaTest

I'm finally getting back into ScalaTest development. I'm really excited about it. It's been a while. I'll be giving a presentation at the next Scala meetup on testing in Scala. It won't be specifically to ScalaTest - I'll be including specs, matchers, mocking, ScalaCheck, lots of cool stuff.

Ruby

Ruby is definitely rubbing off on me. I read an interesting quite by Matz that said something along the lines of, "It really comes down to just how you feel writing in a language that matters". I feel good writing Ruby. I feel even better writing Scala (though I do sometimes end up in fights with the type system and get angry). I feel HORRIBLE writing Java.

camelcase vs. underscores

I've decided that camelcase is much harder to read than underscores, and wish the Java and Scala communities would make the switch. WhenIReadCamelCaseAndEverythingIsBunchedUp, its_just_harder_to_read_than_underscores. I think this is especially true as the statement gets longer. TwoWords is not so_bad. ButAfterThat I think underscores_win_out.

Management

I can't begin to explain how good it feels to have good management again. I had a great one a few years back by the name of Eric Golin. He was so incredibly smart and knew how to speak to me and how to get the best out of all times. This is how I feel at my current job. Management has worked extremely hard to get things running smoothly. It just feels great.

I've had so many terrible, terrible, terrible managers in the past - almost all of them. Its an absolute drag. I need to do better to make sure it doesn't happen again.

Here's one tip - if anyone in the management chain wears sunglasses indoors, run like hell.

C++?

I don't have much experience in C++ at all, but, in what little time that I've spent with it, I like it. And I like it a hell of a lot more than Java. Now, I know Java's appeal was that it fixed so many problems C++ developers had to face, but...for the most part I think it just appealed to the 90% of developers who aren't any good.

But, Java probably was a good step back in order to fix some of those problems, in order to allow really nice things like Scala to come along. You know, I used to really like Java, until Scala came along. Now seeing Java code makes me throw up in my mouth a little.

Algorithms

I need to get better at explaining fundamental algorithms. Its not that I don't understand the concepts, I just don't do a good job of explaining my understanding of them. I will improve this.

School

School is a perfect place for me. I have to go back. I change jobs often because I lose interest. I need to be challenged, always. I need new ideas. I need really smart people I can talk to all the time. Very few jobs can offer even half of what I need. I get all these things and more at school.

If I need a challenge, I just pick a challenging class. Almost everyone in my program will be really smart, and interested in exactly the same things as me. Fantastic. And, I wont have to deal with sunglasses indoors.

Grad School

2009-02-18T19:01:00.001-08:00

I plan on going back to grad school, full time maybe, part time maybe. I want to go for language design, as that's really all I'm interested in, and all I've been concentrating on for the past couple of years (outside of work).

I think the obvious choice is EPFL, but I'm not yet sure what my chances are of getting in. NYU part time is also a good option.

I'm very, very excited about this. In the past two years or so I went nuts and bought probably a dozen language design/compiler books, a dozen math books, and a bunch of books on actual languages. I've clearly been getting ready for this for quite some time, and the time is right.

I need to write my statement of objectives, and if anyone is willing to proofread for me, that would be awesome.

Also, if EPFL doesn't work out, I'd be willing to give some other schools a shot, but only for language design. Anyone out there have any good experiences to share?

NYSE => New York Scala Enthusiasts

2009-02-18T18:36:00.000-08:00

Monday, February 23rd, meeting of NYSE, or New York Scala Enthusiasts*. I suspect I'll be presenting regularly, but I won't be presenting at the first meeting - I think someone is speaking about the Actor model this time. My first presentation will likely be about ScalaTest, Specs, and other Scala testing alternatives.

I encourage people who actually care about programming to join us, and programmers who don't care about programming to fall off the GW bridge.

* (Very funny that its called NYSE, given my very infamous stay with the actual company, and how that sham of a technology company wouldn't accept Scala at all, despite my best efforts. Anyway, looks like there will finally be a NYSE in town that embraces Scala.)

Deeper Look at the Apply Method in Scala

2009-01-28T09:55:00.000-08:00

In Scala, there is a language feature generally referred to as "The Apply Method" that has the following rules:

Any object that has an apply method can be called with the .apply omitted.
Functions are no more than objects.

Let's take a look at an example. Given the following abbreviated definition of class Array, and an instance a,


class Array{
  def get(index:Int) = { ...some code to get from the array... }  
  def apply(index:Int) = get(index)
}

val a = new Array(whatever)

Then the following calls are essentially equivalent:


a.apply(7)
a(7)

and also:


a.get(7)

(the call to get is only equivalent because apply simply calls get. apply could have any implementation, of course.)

While apply is really useful in cleaning up syntax, the real beauty of it is hidden just below the surface. (Note: Some of the following might not be implemented exactly as I describe, I'm not 100% sure, but for the sake of understanding, I think it's okay.)

Scala'a apply is a concept that can be considered universally across functions or methods, objects, anonymous functions, case classes, and the like. In Scala, a method is nothing more than a Function object containing an apply method which takes the same arguments as the method itself.

Let's take a look at a more in depth example. All three of the following are basically equivalent:

  
  def shout1( word: String ) = println(word + "!")

  val shout2 = new Function1[String, Unit] {
    def apply(word: String) = println(word + "!")
  } 

  val shout3 = (word:String) => println(word + "!")

All three are of type Function1[String,Unit], which has an apply method that takes a String and returns Unit. Notice that shout3 uses anonymous function syntax. This is really nothing more than syntactic sugar for Function1. All three can be called like so:


  shout1("hey")
  shout2("hey")
  shout3("hey")

The following client code further demonstrates that they all derive from the same type.


  def ohYeah( f: String => Unit ){
    f.apply("oh yeah")
    f apply "oh yeah"
    f("oh yeah")
  }

  ohYeah(shout1)
  ohYeah(shout2)
  ohYeah(shout3)

However, one thing I find odd that cannot be done is the following:


  shout1.apply("hey") // compiler error!
  shout2.apply("hey") // ok
  shout3.apply("hey") // ok

If anyone smarter than me cares to chime in on that one, I'd be quite happy. Apparently Scala doesn't always treat actual methods exactly the same as the equivalent Function values, but I'm not sure why. I tend to think it should. There must be a good reason.

The first rule applies to top level objects, functions, and objects defining apply, but what about classes? Are classes no more than objects in the language, the same way that functions are?

Unfortunately, it appears the answer is No.

Before we get into that, let's that a quick look at the exception to that - case classes. For any case class C, you can say C(), and that returns you an instance of that class. Hmm... C(). That looks an awful lot like what we've been looking at. As it turns out, it is.

In Scala, when you define a case class, a corresponding top level object with the same name is created. This object is a factory which creates objects of the original class. It contains an apply method that takes the same arguments as the constructor of the original class and simply calls that constructor.

A quick example should help:


  case class Dood(name: String)

  class DoodClient {
    val a = new Dood("Jack")
    val b = Dood("Daniels")
    val c = Dood.apply("Cough")
  }

The expressions in b and c are equivalent. b is just shorthand for c. In both lines, Dood refers to the top level object Dood, and not the class.

Knowing all this, I should correct myself. I said case classes are an exception to the rule that classes aren't simply objects in the language. This isn't really true. Creating the case class Dood creates both a class and a top level object. It's that object that has the apply, and the class itself still isn't a full fledged object.

But why? Well, I think the short answer is that on the JVM classes aren't top level objects. That seems like a cop out answer though. Let me explore it for a bit, though I'm really just thinking out loud.

If they were top level objects containing an apply method then we could probably do away with the new keyword entirely, and then any call to any object would simply be a call to apply. Things would be entirely consistent both from the internal language representation, and from the perspective of the developer as well.

But what are the consequences of this? I guess I'm not sure. I'm going to have to think through it a bit harder. I'd appreciate comments from anyone with more knowledge on the subject than myself.

Maven: WTF

2009-01-26T06:28:00.000-08:00

I'm on the train, trying to do a build, and this happens:

[INFO] ------------------------------------------------------------------------
[INFO] Building myProject
[INFO] task-segment: [clean]
[INFO] ------------------------------------------------------------------------
[INFO] artifact org.scala-tools:maven-scala-plugin: checking for updates from scala-tools.org
[WARNING] repository metadata for: 'artifact org.scala-tools:maven-scala-plugin' could not be retrieved from repository: scala-tools.org due to an error: Error transferring file
[INFO] Repository 'scala-tools.org' will be blacklisted

WTF?

Because I'm not online maven totally explodes and threatens to blacklist stuff?

I'm sure this is 'configurable' or whatever...but wtf, this just shouldn't happen. Since I wasn't online, I couldn't easily lookup what to do, so I couldn't build at all. Thanks Maven.

I'm thoroughly annoyed.

More On My Scala Query DSL

2008-12-28T11:22:00.000-08:00

I know I promised to explain some things that I still haven't explained, but unfortunately I won't be doing that just yet. I've been too busy coding. I made some cool additions to what I do have though. Now, I can query over more things that just a dictionary of words. In this post I'll show some examples using music scales. Additionally, I added orderBy, and limit stuff, which was really fun.

I've added google code project for this as well, because I kept adding stuff to my cpusimulator project, and it clearly didn't belong. Here's the link: dslplayground.

Here's some examples:


1  val c_maj_and_a_min = contains(Chord("C", Maj), Chord("A", Min))
2
3  var scales_desc = 
     Scale find(c_maj_and_a_min) limit 4 orderBy (rootChord, Desc)
4  var scales_asc  = 
     Scale find(c_maj_and_a_min) orderBy (rootChord, Asc) limit 3
5  
6  scales_desc foreach println
7  println("-------------------------")
8  scales_asc  foreach println

Here I'm searching for all Scales (just major and minor scales) that contain Cmaj, and Amin.

On line 3 I'm limiting my search to 4 scales, and ordering the results by the rootChord of the scale, descending.

On line 4 I'm limiting my search to 3 scales, and ordering the results by the rootChord of the scale, ascending. But, notice I've done this in the opposite order as line 3. (The behavior changes though, if I limit the unordered result set before I order it, or after...not sure what to think about that.)

Lines 6,7, and 8 yield:

List(Chord(G,Maj), Chord(A,Min), Chord(B,Min), Chord(C,Maj), Chord(D,Maj), Chord(E,Min), Chord(F#,Dim))
List(Chord(F,Maj), Chord(G,Min), Chord(A,Min), Chord(Bb,Maj), Chord(C,Maj), Chord(D,Min), Chord(E,Dim))
List(Chord(D,Min), Chord(E,Dim), Chord(F,Maj), Chord(G,Min), Chord(A,Min), Chord(Bb,Maj), Chord(C,Maj))
List(Chord(C,Maj), Chord(D,Min), Chord(E,Min), Chord(F,Maj), Chord(G,Maj), Chord(A,Min), Chord(B,Dim))
-------------------------
List(Chord(A,Min), Chord(B,Dim), Chord(C,Maj), Chord(D,Min), Chord(E,Min), Chord(F,Maj), Chord(G,Maj))
List(Chord(C,Maj), Chord(D,Min), Chord(E,Min), Chord(F,Maj), Chord(G,Maj), Chord(A,Min), Chord(B,Dim))
List(Chord(D,Min), Chord(E,Dim), Chord(F,Maj), Chord(G,Min), Chord(A,Min), Chord(Bb,Maj), Chord(C,Maj))

The fantastic thing about all this is the implementation. I've genericized the stuff I did with Scrabble in a really clean way, and to add search support for an already existing Scale library all I had to do was:


object Scale extends Search[Scale]{
  def all = notes.map(MajorScale(_)) ::: notes.map(MinorScale(_))
  def rootChord( s: Scale ) = s.rootChord
}

object ScaleMatchers {
  def contains(chords: Chord*) = (s: Scale) => {
    chords.foldLeft(true){ (b,c) => b && (s contains c) }
  }
}

By extending the Search trait, I get all sorts of nice ability to search. All I need to do is provide the definition of the all function. Then, I just define some matchers (in this case only one), and I'm all set to start searching through my data.

Hopefully I'll be able to extract out some of the common matcher stuff as well. I don't think this will be all that difficult.

Its important to note a choice that I've made here. I'm forcing the definition of the all method. Basically, right now, every search loads all the data, and then works on it. Certainly this won't scale, but, this is just a simple little DSL. The underlying implementation could be optimized later. Doug Lea taught me that that is the way you should design languages. First, work on getting the language correct, then worry about performance.

Fun DSL Query Language for Scala

2008-12-22T14:45:00.000-08:00

(Quick Note: If you just want to skip to the code, it's interspersed throughout the post. But, for your convenience, I've also put it all in one place at the bottom of the post.)

I've done it! Sick as a dog yesterday, I refactored the crap out of my Scrabble stuff, to create a really powerful query DSL. The kicker? It's only 24 lines of code! It allows you to do all sorts of crazily powerful queries. Lets take a look. I'm so excited! I can't stop typing exclamation points! I actually think this is the best code I've ever written. 1

I'd love to talk about the code smells of my last post, and how I ended up where I did, but to be honest, the code seems so much different now that it would be difficult. I'll just dive in.

Once again I'll start with the test code, which models the original requirements. Don't worry if you don't understand how it works just yet, because I'll explain later. For this first bit, I'm just going to try to explain what it does.


  val dictionary = new Dictionary(getWords())
  val tray = "defilnr"

  // the 4 original requirements
  val all  = dictionary find includes_all(tray) 
  val any  = dictionary find includes_any(tray)
  val only = dictionary find includes_only(tray)
  val all_and_only = 
    dictionary find (includes_all(tray) and includes_only(tray))
    
  print(all, only, all_and_only)

Let me sum up what's going on here.

With "all", I've filtered the dictionary to find words that include all the letters in my tray. This produces a small list of very long words - something like: List(adenoliomyofibroma, antifederal, antifederalism, antifederalist, ... )
Similarly with "any", I've filtered the dictionary to find words that include any of the letters in my tray. This produces a gigantic list that I won't even begin to list here.
With "only", I've filtered the dictionary to find words that include only of the letters in my tray. This produces
Finally, the important query, with "all_and_only", filtered the dictionary to find words that include words that include all the letters in my tray, and only the letters in my tray, just as the code reads. This produces something much more helpful to me in Scrabble: List(flinder, infielder)

A key thing to notice is the "and" on this line:


    dictionary.filter(includes_all(tray) and includes_only(tray))

But like I said, I'll explain the hows later. Now I'll introduce a couple of new concepts with this line of code:


   val all_or_min_10 = dictionary(includes_all(tray) or  max_length(7))

The two new concepts on this line are:

"or", which is very similar to "and" and very self explanatory.
Notice I'm not calling dictionary "find" some_criteria, I'm just calling dictionary(some_criteria). I'll explain how this works later as well. I'm not actually sure I like it, but I figured I'd give it a shot to see how the code looks.

Time for more:


  val xin_or_max_4 = 
    dictionary search (starts_with("xin") or max_length(4))
  val van_or_min_4 = 
    dictionary search (ends_with("van") and min_length(4))

Some more new concepts on these lines are:

The "search" method is also an alias for find. But, the actual aliasing is pretty neat, so it will be cool to show how later.
Several new criteria functions - starts_with, ends_with, max_length, min_length, which I think are also very self explanatory in what they do.

If I'm moving quickly its because I'm really excited to get into the next part, where I build up a much more complex query.

Complex Queries


  val complex_query =
    (
      (starts_with("d") and ends_with("ing")) or
      (starts_with("b") and ends_with("ed"))
    ) and max_length(7) and min_length(4)
 
  var result = dictionary find complex_query
  print(result)

Yes! This seems to have really put it all together. In this query I'm asking for words that start with 'd' and end with 'ing', OR words that start with 'b' and end with 'ed', and any words found must have a maximum length of 7 and a minimum length of 4. I build up the query first, and then ask the dictionary to execute it for me. This seemingly innocent feature plays an important role in abstraction. Which hopefully we'll get to see in just a bit.

Executing this query gives me something like: List(babied, backed, bagged, baked, balled, banded, bangled, banked, barbed, barred, ... dueling, duffing, dumping, during, dusting, dyeing, dying)

Adding onto existing queries

But, I'm not satisfied with my results. Maybe I can't seen to find a place on the Scrabble board where an "a" can be used, and I don't have one in my tray. I want to re-execute my query, but remove all the a's. Here's how:


  val complex_query_without_a = complex_query and includes_none("a")
  result = dictionary find complex_query_without_a
  print(result)

Fancy Schmancy! Executing this query gives me: List(bebed, bebled, bedded, beedged, beetled, beeweed, beinked, beliked, ... dueling, duffing, dumping, during, dusting, dyeing, dying)

Language Features

Before we go into the hows, lets take a very, very quick theory break. Taken straight from SICP, any language gives you three things:

Primitive Expressions
A means of combination
A means of abstraction

Does this little DSL cover those criteria? Yes (though point 3 is somewhat shaky). Anyway, as we cover the hows, we'll refer back to those points to demonstrate how this DSL fulfills them.

Primitive Expressions

We're finally to the implementation (though I suppose many of you probably just scrolled down).

The query criteria methods are basically our primitive expressions in this DSL. 2 Here is the list of primitives provided, and their implementations. I suspect that other primitives will be added soon.


1  object WordMatchers{
2    def includes_only(s: String) = (t: String) => 
          inverse(s).foldLeft(true)((b,c) => b && (! (t contains c)))
3    def includes_none(s: String) = (t: String) => 
          s.foldLeft(true)((b,c)  => b && (! (t contains c)))
4    def includes_all(s: String)  = (t: String) => 
          s.foldLeft(true)((b,c)  => b && (t contains c))
5    def includes_any(s: String)  = (t: String) => 
          s.foldLeft(false)((b,c) => b || (t contains c))
6    def starts_with(s: String)   = (t: String) => t startsWith s
7    def ends_with(s: String)     = (t: String) => t endsWith  s
8    def max_length(max: Int)     = (s: String) => s.trim.length <= max
9    def min_length(min: Int)     = (s: String) => s.trim.length >= min
10   def inverse( s: String ) = 
          "abcdefghijklmnopqrstuvwxyz".filter(!s.contains(_) )
11 }

Ok...I hope no one kills me when I say I'm going to save the how for this one for the next post. That's the implementation. It's pretty crazy, and can probably only be read by pretty experienced developers. I'm really tired and still not feeling great, so I'm going to wait so I don't mess it up.

Means of Combination

The means of combination in this DSL are very simple (at least from a users standpoint). They are simply and and or.

The implementation of those combinations are pretty complex though.


1  object Criteria{
2    implicit def funcToCriteria[T](f: Function1[T, Boolean]) = 
       new Criteria(f) 
3  }
4  class Criteria[T](val f: Function1[T, Boolean]) {
5    def apply(t: T) = f(t)
6    def && (c: Criteria[T]): Criteria[T] = (t: T) => f(t) && c.f(t)
7    def || (c: Criteria[T]): Criteria[T] = (t: T) => f(t) || c.f(t)
8  }

Criteria is some seriously powerful magic, and is totally awesome. I'm also going to wait, and explain both the primitives, and combinations in the next post, which will probably be just tomorrow night. Maybe I'll just update it right here. Maybe I shouldn't even post this yet until I'm finished, but I know there are people that read my blog and this is too cool to wait on!

Execution

Before we take a look at our means of abstraction, lets take a quick look at the Dictionary class, which is something like the DSL's runtime environment, and VM. It holds the words (the environment), and executes the queries which search over those words (VM).


1  case class Dictionary( words: List[String] ) {
2    def apply(criteria: Criteria[String]) = words.filter(criteria(_))
3    def find = apply _; def filter = apply _; def search = apply _;
4  }

Its fairly simple, simply asking the Criteria to evaluate themselves, for each word in the dictionary. If the word doesn't fit the criteria, it is filtered out.

One thing that I really wanted to get to (which doesn't have a whole lot of importance, but is really cool) is the method aliasing. Check out line 3. I've aliased find, filter, and search all to apply, so that a user can call any of them. Maybe that's confusing and not needed, but it was fun.

Means of Abstraction

This DSL borrows its means of abstraction from the Scala language itself, but so far does a pretty poor job of it.

Let's revisit the very last example:


  val complex_query_without_a = complex_query and includes_none("a")
  result = dictionary find complex_query_without_a
  print(result)

I intentionally left out the declaration of complex_query. Do you remember what it does? I suspect not. I could tell you that its a query "asking for words that start with 'd' and end with 'ing', OR words that start with 'b' and end with 'ed', and any words found must have a maximum length of 7 and a minimum length of 4. But, I shouldn't have to. Somehow the code should provide that information upon reading it. There are ways we could do this, but they aren't great, in my opinion.

We could say:


  val starts_with_d_and_ends_with_ing_OR_starts_with_b_and_on_and_on_and_on =
    (
      (starts_with("d") and ends_with("ing")) or
      (starts_with("b") and ends_with("ed"))
    ) and max_length(7) and min_length(4)

But, that really doesn't work. I mean, not only does the variable name go right off the stinkin' page, but the entire implementation is encoded into it. I think that its possible that this DSL fails at doing a great job of abstraction because the underlying nature of the thing its trying to represent - queries matching specific criteria - doesn't really lend itself to abstraction very well. If anyone has any ideas on how this could be improved, I'd be grateful.

OK....that's all for now. I know this thing sort of deteriorated at the end as I got tired, but I'll fix it up really soon. Hope you love it!

Implementation

As promised, here's all the code in one place:


package com.joshcough.scrabble

import Criteria._
import Dictionary._
import WordMatchers._
import org.testng.annotations.Test
import scala.io.Source

class ScrabbleTest {

  val lines = Source.fromFile("/usr/share/dict/words").getLines
  val words = lines.toList.map(_.trim.toLowerCase)
  val dictionary = Dictionary(words)

  @Test def tests {

    val tray = "defilnr"

    // the 4 original requirements
    val all =  dictionary find includes_all(tray)
    val any =  dictionary find includes_any(tray)
    val only = dictionary find includes_only(tray)
    val all_and_only = dictionary find 
      (includes_all(tray) and includes_only(tray))
    print(all, only, all_and_only)



    // additional cool things 
    // (use of Dictionary.apply and Criteria's "||" method )
    val all_max_7     = 
      dictionary(includes_all(tray) and max_length(7))
    val all_or_min_10 = 
      dictionary(includes_all(tray) or  max_length(7))
    print(all_max_7, all_or_min_10)



    // more things (use of Dictionary.filter, 
    // starts_with, ends_with, max_length, min_length)
    val xin_or_max_4 = 
      dictionary search (starts_with("xin") or max_length(4))
    val van_or_min_4 = 
      dictionary search (ends_with("van") and min_length(4))
    print(xin_or_max_4, max_4_or_van)


    
    // more complex query
    val complexQuery =
      (
        (starts_with("d") and ends_with("ing")) or
        (starts_with("b") and ends_with("ed"))
      ) and max_length(7) and min_length(4)

    var result = dictionary find complexQuery
    print(result)



    // hmmm, but i didnt like my result...
    // how about i modify my query...
    val complexQueryWithoutAs = complexQuery and includes_none("a")
    result = dictionary find complexQueryWithoutAs
    print(result)
  }

  def print[T](lists: List[T]*) = lists foreach println
}

/**
 * @author dood
 * Date: Dec 21, 2008
 * Time: 10:09:24 PM
 */
object Criteria{
  implicit def funcToCriteria[T](f: Function1[T, Boolean]) = 
    new Criteria(f) 
}

class Criteria[T](val f: Function1[T, Boolean]) {
  def apply(t: T) = f(t)
  def and (c: Criteria[T]): Criteria[T] = (t: T) => f(t) && c.f(t)
  def or  (c: Criteria[T]): Criteria[T] = (t: T) => f(t) || c.f(t)
}

/**
 * @author dood
 * Date: Dec 21, 2008
 * Time: 11:24:22 AM
 */
case class Dictionary( words: List[String] ) {
  def apply(criteria: Criteria[String]) = words.filter(criteria(_))
  def find = apply _; def filter = apply _; def search = apply _;
}

/**
 * @author dood
 * Date: Dec 22, 2008
 * Time: 3:12:35 PM
 */
object WordMatchers{
  def includes_only(s: String) = (t: String) => 
    inverse(s).foldLeft(true)((b,c) => b && (! (t contains c)))
  def includes_none(s: String) = (t: String) => 
    s.foldLeft(true)((b,c)  => b && (! (t contains c)))
  def includes_all(s: String)  = (t: String) => 
    s.foldLeft(true)((b,c)  => b && (t contains c))
  def includes_any(s: String)  = (t: String) => 
    s.foldLeft(false)((b,c) => b || (t contains c))
  def starts_with(s: String)   = (t: String) => t startsWith s
  def ends_with(s: String)     = (t: String) => t endsWith  s
  def max_length(max: Int)     = (s: String) => s.trim.length <= max
  def min_length(min: Int)     = (s: String) => s.trim.length >= min
  def inverse( s: String )     = 
    "abcdefghijklmnopqrstuvwxyz".filter(! s.contains(_) )
}

(1) - I hate the NYSE for keeping me in an intellectual prison for so long, and hate myself for not leaving sooner.

(2) - However, this is an internal DSL, and so you are free to build up more and more primitives, which makes them seem not really like primitives at all...

Using Scala First Class Functions By Name

2008-12-21T08:51:00.001-08:00

WARNING: Today I changed this code all around, and I'll be reposting it soon. This post is still cool, and nothing is wrong with it, but, now the code is wicked awesome!!! So, look for it to be refreshed soon!

It occurred to me that while I knew really well how to pass anonymous functions around in Scala, I had very little experience passing around functions by name. I'm not sure why this is, but I think there isn't all that much out there written about it. It's important to understand that anywhere you could use an anonymous function, you could also use an existing function. Passing functions by name really helps clarify the intent of your code, and for DSL's in general. I'm going to try to demonstrate how to do so, for those who might be in the same boat as me.

I wrote a little app that searches through /usr/dict/words to find words matching the letters that I have in my Scrabble tray. Yes, I could have easily done this with "cat /usr/dict/words | grep someRegEx", but, the point was to learn more about functions.

(quick note...this post is really really long, but i think its full of good information)

First, I needed to be able to determine the following information about a word:

Does the word contain ALL the letters in my tray? (but maybe some other letters)
Does the word contain ONLY the letters in my tray? (no other letters allowed)
Does the word contain ANY of the letters in my tray?
Does the word contain NONE of the letters in my tray?
Lastly, does the word contain ALL of the letters in my tray, and ONLY the letters in my tray?

To do this I added a function to String that takes the characters to search for, and then any number of additional criteria. The criteria are functions that I reference by name. Lets see the client code, then I'll explain in more detail. Bear with me, I know its frustrating not seeing the actual library code, but I do think it helps to understand how its used before reading it.


1  class StringSearchTest {
2   
3   import org.testng.annotations.Test
4   import PimpedString._
5   import Equalizer._
6 
7   @Test
8   def testSearch {
9     var word = "ketoid"
10    word.searchFor("ke",  word.includes_all)  mustBe true
11    word.searchFor("ke",  word.includes_none) mustBe false
12    word.searchFor("xzy", word.includes_none) mustBe true
13    word.searchFor("ke",  word.includes_only) mustBe false
14
15    word = "keyyek"
16    word.searchFor("key", word.includes_only) mustBe true
17    word.searchFor("xyz", word.includes_any)  mustBe true
18    word.searchFor("abc", word.includes_any)  mustBe false    
19    word.searchFor("key", word.includes_only, word.includes_all)  mustBe true
20    word.searchFor("key", word.includes_all,  word.includes_none) mustBe false
21  }
22}

Let's break down line a few lines:


10    word.searchFor("ke",  word.includes_all)  mustBe true

"word" is the word we are searching.
"ke" is what we are searching for.
"word.includes_all" is the criteria. This particular criteria states that 'word' must include all the letters we are searching for. In this case, word must contain both k and e.
The statement itself (word.searchFor("ke", word.includes_all)) returns a Boolean. True if the word matches the search criteria, false otherwise.


11    word.searchFor("ke",  word.includes_none) mustBe false
12    word.searchFor("xzy", word.includes_none) mustBe true

includes_none is very much the opposite of includes all. It ensures that the word contains NONE of the things we are looking for. The statement in line 11 evaluates to false because the word does contain k (and e for that matter). Line 12 evaluates to true because they word does not contain x, y, or z.


16    word.searchFor("key", word.includes_only) mustBe true

This is nearly the same as the line 10, but the criteria is more restrictive. includes_only states that the word must include only letters that we are searching for. If we were searching for "key" in the word "hey", this would fail, because our word contains an "h".


17    word.searchFor("xyz", word.includes_any)  mustBe true

Also very similar to above, but includes_any evaluates to true if the word contains ANY of the things we are searching for.


20    word.searchFor("key", word.includes_only, word.includes_all)  mustBe true

Finally the moment of truth, line 20 is the most important of all. It states that the word must contain ONLY the letters in my tray, and ALL of the letters in my tray. This is the easiest way to find Bingo words. (It doesn't yet work perfectly, if my tray contained "key" and the word was "keyyyy", it would still evaluate to true. I need to fix this.)

Finally, before we see the actual library code, lets take a second to understand what "word.includes_all" actually is. "word.includes_all" is a higher order function that takes an Array of Char, and returns a function that takes a Char and returns a Boolean. A higher order function is a function that takes a function as an argument, returns a function, or both. includes_all does both. Higher order functions have been explained by everyone and their brother since 1960, so I won't be doing that here. I'm just explaining how to pass functions by name.

Ok, lets take a look at the library code and I'll explain in more detail.


1  object PimpedString {
2    implicit def pimpMyString(s: String): PimpedString = 
3         new PimpedString(s)
4    implicit def convertToCharArray(s: String): Array[Char] = 
5         s.toCharArray
6  }
7 
8  class PimpedString(s: String) {
9  
10   def includes_all(chars: Array[Char])  = 
11        fold(chars)(s contains _)
12   def includes_none(chars: Array[Char]) = 
13        fold(chars)(!s.contains(_))
14   def includes_any(chars: Array[Char])  = 
15        chars.foldLeft(false)((b,c) => b || (s contains c))
16   def includes_only(chars: Array[Char]) = 
17        includes_none(inverse(chars))
18
19   private val letters = "abcdefghijklmnopqrstuvwxyz".toCharArray
20   private def fold(chars: Array[Char])(f: Char => Boolean) = 
21        chars.foldLeft(true)(_ && f(_))
22   private def inverse( chars: Array[Char] ) = 
23        letters.filter(! chars.contains(_))
24   def searchFor(chars: Array[Char], 
25                 criteria: Function1[Array[Char], Boolean]*): Boolean = {
26     criteria.foldLeft(true){(b, f) => b && f(chars)}
27   }
28 }

(quick note: I've written about implicits here, and here, and I've written about foldLeft here, and I won't be covering them in any detail here.)

Let's just skip right ahead to line 10:


10    def includes_all(chars: Array[Char])  = fold(chars)(s contains _)

As advertised, includes_all is a higher order function that takes an Array of Char, and returns a function that takes a Char and returns a Boolean. Let's take a look back at the original code to see how it was used:


10    word.searchFor("ke",  word.includes_all)  mustBe true

Now, I could have just used an anonymous function here for my criteria. Assuming that the fold method wasn't private, it would look like this:


10    word.searchFor("ke",  word.fold(chars)(s contains _))  mustBe true

The call to fold is basically saying look at each of the search characters and make sure I contain it. fold also returns a function that is executed in search. I could do this, but since includes_all is so common, so reusable, that instead of passing it anonymously, I give it a name, and reuse it all over. And, giving it a name makes it much, much more clear as to what is going on. The second version of line 10 is almost indecipherable.

That basically sums up how to reference functions by name, and pass them around. I'm going to finish the post, showing the actual Scrabble code. However, I don't think there are any ideas that I haven't already covered. Let's start by reviewing the original requirements, since its been a while:

Find all possible words where:

The word contains ALL the letters in my tray. (but maybe some other letters)
The word contains ONLY the letters in my tray. (no other letters allowed)
The word contain ANY of the letters in my tray. (other letters allowed)
The word contains ALL of the letters in my tray, and ONLY the letters in my tray.

Now to be consistent, lets look at the test/client code, because that's where you should always start.


1  object ScrabbleTest extends Application{
2    val tray = System.getProperty("tray").toString
3    val scrabble = Scrabble(tray)
4  
5    println(scrabble.find(scrabble.all_letters_in_tray))
6    println(scrabble.find(scrabble.only_letters_in_tray))
7    println(scrabble.find(scrabble.any_letters_in_tray))
8    println(scrabble.find(
9       scrabble.only_letters_in_tray,
10      scrabble.all_letters_in_tray))
11 }

I think I have to take some pride in this. The code reads very, very close to the actual requirements. So much that I'm not going to explain it, except to point out again that scrabble.all_letters_in_tray is another example of passing a function by name.

Let's just go right to the library code.


1  case class Scrabble(tray: Array[Char]) {
2    val lines = Source.fromFile("/usr/share/dict/words").getLines
3    val words = lines.toList.map( _.toLowerCase )
4
5    def only_letters_in_tray(s: String): Function1[Array[Char], Boolean] = 
6          s.includes_only
7    def all_letters_in_tray(s: String): Function1[Array[Char], Boolean] =
8          s.includes_all
9    def any_letters_in_tray(s: String): Function1[Array[Char], Boolean] = 
10         s.includes_any
11
12   def find(criteria: Function1[String, Function1[Array[Char], Boolean]]*) = {
13      words.filter( word => { 
14        word.searchFor(tray, criteria.map( _(word) ):_* ) 
15     }).map(_.trim)
16   }
17  }

Scrabble defines its own criteria functions - only_letters_in_tray, all_letters_in_tray, and any_letters_in_tray. But they are essentially just wrappers around the String criteria functions. This is a testament to how nice and reusable those original functions were, and why I luck out and don't have to explain them :)

The find here simply takes N criteria, and passes wrapped functions onto the String searchFor method. Line 14 is pretty insane, especially criteria.map( _(word) ):_*. It certainly takes some experience before being able to read (or write that line). Fortunately, as a user, the code is absurdly simple, so it doesn't really matter.

That's all for now. I hope this helped.

Anyone want to play me in Scrabble?

Ruby over Scala

2008-12-20T12:55:00.000-08:00

As promised, here is where I'll be maintaining the things I like about Ruby better than Scala. In general, I do think I prefer programming in Scala, but certainly some of the things I can do in Ruby are much easier. If you're looking the other post, its here: Scala over Ruby.

This list is my no means complete and as with the other list, I'll be appending to it here as I learn more.

Pimp My Library

I'll dive into some general theory about this first, but for those who just want to see the code, just scroll down.

There's been so many times when I've needed to add methods to classes, for good reasons. Well, I suppose I didn't "need" to, but the main good reason of course is readability. Having your data and operations on that data in one place is nice. Calling those operations consistently is very important.

Let's use an example in Scala. I couldn't find a "compact" method on List. It like seems it should be there. It's certainly useful. I could just create a method called compact, which takes a List, like so:


  def compact[T]( list: List[T] ) = l.filter( _ != null )

But as I just said, calling operations on your data consistently is important for readability. Having this method forces me to call my operations differently. It's confusing calling some methods as infix, and some as prefix. Sometimes I say myList.whatever, and other times I say whatever(myList). The situation is even worse if that method takes arguments. myList.whatever(x), or whatever(myList, x). Inconsistent, confusing, ugly.

One solution is to simply add that method to the class you're operating on. Scala and Ruby both provide mechanisms for doing so, but they differ greatly. In Scala, I have to provide an implicit conversion from the class I'm operating on to a class that has a the method that I want to call. Here is the code:


  class Compactable[T](l: List[T]){
    def compact = l.filter( _ != null )
  }

  implicit def compactableList[T]( l: List[T] ) = new Compactable(l)

  val list = List( 1, null, 2, null, 3, null )
  
  println(list) // prints all values including the nulls
  println(l.compact) // prints just the values 1, 2, and 3

This isn't terrible, but it really clouds my actual intent: I just want to add a compact method to List. Why should I have to convert it to something else, only to have the compiler figure out what I really wanted? While there are some other great uses for implicit conversions, in this particular case something that should be very simple has been made overly complex. Maybe there is a better way of doing this in Scala but I haven't seen it. In addition, I've seen this pattern so many times in Scala code written by other people, so I don't think there is a different way. This code is really just boilerplate.

In Ruby things are much more straight forward.


  module Enumerable
    def collect_with_index
      idx = -1
      collect{|elm| idx = idx + 1; yield(idx, elm)}
    end
  end

(Note: I've used a different method because the compact method already exists. I couldn't find a collect_with_index method.)

Here, I essentially just open up Enumerable and add the method to it. Done. The intent is preserved. Everything is clear, and simple. So simple in fact, that I don't even think I need to explain it.

I could imagine something very similar existing in Scala.


  extend trait List[T]{
    def compact = filter( _ != null )
  }

This doesn't violate encapsulation because I'm not accessing any internals of List that aren't available to me otherwise. This could just be syntactic sugar for the Scala code above. Maybe someday.

Also, I think C# has similar mechanisms, but I'm admitting my inexperience. I'd love to see replies on how this is done in other languages.

Classes are Objects

In Scala, and Java, classes aren't really objects, at least the way they should be. Ruby (and I'm sure Smalltalk, and other languages) gets this right.

I had a discussion with my friend the other day and he asked, "what do you mean? I can call getClass on an object, and call methods on that class...". Eh, you can, but its still a weird fabrication. To a Rubyist, its laughable. So, without further ado, here's an example for Java programmers (in Java because Scala doesn't have static methods)

Let's say I have a simple little interface for a factory that creates Connection objects, and an implementation.


interface ConnectionFactory{
  Connection createConnection( String user, String pass );
}

class ConnectionFactoryImpl implements ConnectionFactory{
  Connection createConnection( String user, String pass ){
    return new WhateverConnection( user, pass );
  }
}

Then I have a client that uses a ConnectionFactory:


class ConnectionFactoryClient{

  ConnectionFactory factory;

  ConnectionFactoryClient( ConnectionFactory factory ){
    this.factory = factory;
  }

  void doIt(){
    Connection c = factory.createConnection( "dood", "secret" );
    c.connect();
  }
}

Now, imagine I had a class that had createConnection as a static method like so:


class ConnectionFactoryClass{
  static Connection createConnection( String user, String pass ){
    return new OtherConnection( user, pass )
  }
}

You can see that the class itself seems like an object that implements the ConnectionFactory interface. If classes were really first class objects, and the class objects themselves could implement interfaces, then I could pass this class into the client like so:


new ConnectionFactoryClient( ConnectionFactoryClass )

You can do this easily in Ruby. This is because classes in Ruby are objects that respond to messages. They aren't really much different than the instances they create, just that the instances respond to a different set of messages the class.

I'm not advocating static methods here. This is something different entirely. Because the class is an object, and can be swapped out for a different object, you're not really statically bound to using that class the same way you would be in Java.

If classes could implement interfaces, you wouldn't have to go through the pain of creating a Factory instance, and passing that in, like this:


ConnectionFactory cf = new ConnectionFactoryImpl()
new ConnectionFactoryClient( cf )

Why go through the pain of creating a new class, and a new instance of a class, when you could use the class object itself. For the most part, classes are factories anyway.

Consider the following common pattern:


class MySQLConnection{
  static public void createConnection( String user, String pass ){
    new MySQLConnection( user, pass );
  }

  private MySQLConnection( String user, String pass ){ ... }
}

All the create logic is in one place, and the class is the factory. This, I think, is a good thing.

How could this be done you ask? To make this work with static typing, the language would have to have some construct that allows class objects to implement interfaces. It could look something like so (purpose any syntax you wish):


class MySQLConnection 
 (class implements ConnectionFactory) 
 (instances implement Connection){
 
  static public void createConnection( String user, String pass ){
    new MySQLConnection( user, pass );
  }

  private MySQLConnection( String user, String pass ){ ... }
}

We could probably take this even further to allow the constructors to serve as the implementations of the interface methods (maybe by giving constructors aliases).

One final note, in Scala, this would eliminate the need for the top level object that gets created when you define a case class. The class itself could be the object, and it would contain the apply method.

Anyway, that got long. I need to do something to structure this list a bit better.

Scala over Ruby

2008-12-17T09:54:00.001-08:00

In this post, I'll be maintaining a list of things I like more about Scala, over Ruby. I am also maintaining a similar, opposite list - Ruby over Scala. I plan on maintaining this list here and adding more to it over time, as opposed to several posts. I'm not exactly sure how that works with feeds and things, but oh well.

Also, if at any point I'm totally wrong (which is very possible because I'm new to Ruby), please let me know! It's likely that I just didn't know I could do something in Ruby. I'm eager to learn, and for new ideas, and I'll be more than happy to update the post. Anyway, Onward...

1. Scala doesn't make you use the "." operator when calling methods.

This one I'll try to explain using some simple examples. Here is some Ruby code:


x = 5
y = 6
z = x + y
z2 = x.+y

class ClassWithPlusMethod
  def +(other)
   # do something, doesnt matter what...
   return "whatever"
  end
end

x = ClassWithPlusMethod.new
y = ClassWithPlusMethod.new
z = x + y
z2 = x.+y

class SomeOtherClass
  def plus(other)
   # do something, doesnt matter what...
   return "whatever"
  end
end

x = SomeOtherClass.new
y = SomeOtherClass.new
z = x plus y

(irb):25: warning: parenthesize argument(s) for future version
NoMethodError: undefined method `plus' for main:Object
from (irb):25

z2 = x.plus y # this is ok!

As you can see, Ruby has magic handling of + mathematical "operator" (and others). "+" is a simple method call, but since it's name is +, Ruby doesn't require the dot, its interpreter handles it differently. This magic is built into the language, and does not extend to methods with regular names, as shown above with "plus".

In Scala, the . operator is not mandatory on any method call. This may seem trivial, but it is not. It helps in creating cleaner DSL's. Take for example, my post on Equalizer.

In Scala, I was able to add the mustBe method to Any, and call it very nicely. But, in Ruby, I had to put in the dot. Contrast these examples:


x mustBe 5

vs

x.must_be 5

2. Method overloading is good.

I use method overloading a lot. An awful lot. I love it. I don't think I need to explain it however.

3. Scala's apply method.

Scala's apply method is something that I'm pretty sure just doesn't exist at all in Ruby, and I'm not sure it can be done easily. For those who don't know what it is, I'll explain, and maybe some Rubyists can show some similar examples. Given that I'm still not a Ruby expert, I could be totally wrong. If so, I would like to know.

For any method called apply, ".apply" can be omitted from the method call. For example given the following definition of the class Array:


class Array{
  def get(index:Int) = { ...some code to get from the array... }  
  def apply(index:Int) = get(index)
}

And an instance of that class:


val a = new Array(whatever)

Then the following calls are essentially equivalent:


a.get(7) // though only because apply calls get
a.apply(7)
a(7)

This is really useful in cleaning up syntax. However, the real beauty of it is hidden below the surface, and will be the subject of a future post.

4. Ruby faking keyword parameters to methods

Calling methods with keyword params is nice for client code readability. For example:


c = httpConnection( :host => "google.com", :port => 80 )

However, in Ruby the niceness ends at the client code. The library code to support this is abysmal. The reason being, for the method using those parameters, its not at all obvious what the method requires. You have to dig down into the implementation to find out what it actually pulls out of params. This is not ok with me. When I look at a method signature, I should be able to understand what dependencies the method has. Example:


def httpConnection(params)
  ...
  ...
  port = params[:port]
  ...
  ...
  host = params[:host]
end

5. 1 vs. 3 line method defs.

I run into this one a lot, and find that Ruby code ends up being a lot larger than Scala code for this reason. In Ruby, I can't define a method on one line without it looking simply terrible. Example:


def add7(x)
  x + 7
end


def add7(x); x + 7; end

The first version is 3 lines when it doesn't need to be. The second version is one line littered with noise.

Here's the much simpler Scala version:


def add7(x:Int) = x + 7

While this entire point might sound trivial, its not. Functional style encourages us to write many small methods. Ruby code grows larger than Scala code quickly. The problem also becomes bad when using nested functions. Ruby:


def add7(x)
  def add3
    x + 3
  end
  add3 + 4
end

Scala:


def add7(x:Int) = {
  def add3 = x + 3
  add3 + 4
}

All of this might seem rather trivial, but in practice it definitely adds up.

Coming Soon

2008-12-16T19:35:00.000-08:00

For people that care (probably just myself, but I hold out hope), I'm going to spew out a list of the things I'm working on, posts that can be expected in the near future, and other random crap.

The project I was working on was indeed cancelled, as predicted. In hindsight, I'm coming out looking pretty smart. I expect to write some more of my true feelings on this situation. One sad thing of course is that my good friends and old coworkers may soon have to look for new jobs. I hope not.
Ruby is nice. I won't say that it's not as nice as Scala, as I may be attacked by the very vocal Ruby community. But I will say that I enjoy writing Scala much more (I do plan to expand on why, but this isn't the right time). However, some of the dynamic things you can do with Ruby are fascinating.
Rails is nice as well, though I think it has its flaws. I hope to learn Lift very soon and do a nice comparison. We'll see if I have enough time.
Today I started reading about building Facebook apps in Rails. This is something I'll likely dedicate a lot of time to.
Yesterday I learned a bunch about iPhone development. I haven't written anything yet, just had a big walk-through of a pretty popular application. At first glance it seemed fantastic as Apple has made creating views quite simple. This is great because I'm terrible at any visual stuff. Anyway, this is the thing that I will probably end up dedicating the most time to; mostly because I still hold out hope for entrepreneurship.
I am loving my new job. Leaving NYSE has turned out to be a fantastic decision. My new team is great. I'm re-energized. I'm challenged. I'm actually learning at work, instead of just at home. Learning is encouraged, not shunned. I love it.
Lastly, I told myself about a year ago that I wouldn't be getting back into web development. This has changed for a few reasons:
1. I will still never ever ever try to make things look nice.
2. It seems like the frameworks available today eliminate most of the rest of the crap that I didn't want to do before.
3. Having immediate access to millions of users on Facebook seems really exciting, eliminating more crap that I was never any good at - getting people to come to my site.
4. Most importantly, I have an opportunity to learn new languages, and obviously that's what I really care about

foldLeft in Scala, Little Schemer style

2008-11-28T21:37:00.000-08:00

I'm going to write up a Scala version of foldLeft in the style of The Little Schemer.

What is 0 + (1 + 2 + 3)?

>6

What is 0 + (1 + 2 + 3)?

>0 + 1 + (2 + 3)

What is 0 + 1?

>1

What is 1 + (2 + 3) ?

>1 + 2 + (3)

What is 1 + 2?

>3

What is 3 + (3)?

>3 + 3

What is 3 + 3?

>6

Are we done?

>No, we still haven't found out what foldLeft is.

What is foldLeft?

def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = {
    as match {
      case Nil => z
      case x :: xs => foldLeft( xs, f(z, x) )( f )
    }
  }

But that doesn't tell us much does it? Let's walk through an example.

What is List( 1, 2, 3 )?

>List( 1, 2, 3 )

What is foldLeft(a, 0){ (x,y) => x + y } when a is List( 1, 2, 3 )

>6 ... but why? Let's step through it together.

What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>No, it's List( 1, 2, 3 ), so we ask the next question.

What is the next question?

>case x :: xs

What is the value of case x :: xs?

>true, because the list is not Nil, it contains one element x which is 1, followed by a list xs which is List(2,3).

So what is the next step?

> foldLeft( xs, f(z, x) )( f )

What is f( z, x )?

> Well, remember, we called foldLeft like so: foldLeft(a, 0){ (x,y) => x + y }

And what is f?

> { (x,y) => x + y }

Again, what is f( z, x )?

> f( 0, 1 )
> (0,1) => 0 + 1
> 1

So what has foldLeft( xs, f(z, x) )( f ) become?

> foldLeft( List(2,3), 1 )( f )

Now we recur into foldLeft. What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>No, it's List( 2, 3 ), so we ask the next question.

What is the next question?

>case x :: xs

What is the value of case x :: xs?

>true, because the list is not Nil, it contains one element x which is 2, followed by a list xs which is List(3).

So what is the next step?

> foldLeft( xs, f(z, x) )( f )

What is f( z, x )? Remember that z is now 1.

> f( 1, 2 )
> (1,2) => 1 + 3
> 3

So what has foldLeft( xs, f(z, x) )( f ) become?

> foldLeft( List(3), 3 )( f )

Now we recur into foldLeft. What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>No, it's List(3), so we ask the next question.

What is the next question?

>case x :: xs

What is the value of case x :: xs?

>true, because the list is not Nil, it contains one element x which is 3, followed by a list xs which is Nil.

So what is the next step?

> foldLeft( xs, f(z, x) )( f )

What is f( z, x )? Remember that z is now 3.

> f( 3, 3 )
> (3,3) => 3 + 3
> 6

So what has foldLeft( xs, f(z, x) )( f ) become?

> foldLeft( Nil, 6 )( f )

Now we recur into foldLeft. What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>Yes

So what do we do?

> case Nil => z

And what is z?

6!

So what is foldLeft(a, 0){ (x,y) => x + y } when a is List( 1, 2, 3 )

6!

Are we done?

Yes! Now foldLeft a taco right into your mouth.

Refactoring Imperative Code To Functional Code

2008-11-24T23:01:00.000-08:00

I've been refactoring Scala literally for days. It's fantastic how much I've learned over the last year. I knew a little bit about functional programming from doing Lisp in college, but a year and a half ago I couldn't have given you the definition of it.

I decided to tackle some of the most obvious (and ugly) imperative/procedural code in my CPU simulator and turn it into an elegant, functional style.

I'll paste the original code here, then explain it a bit, then show the refactorings one step at a time. In explaining, I will assume that you know at least a bit about how anonymous functions work in Scala.

class EightBitAdder( a: EightBitNumber,
b: EightBitNumber,
carryIn: PowerSource ) {

private val fullAdders: Array[FullAdder] = createFullAdders( a, b, carryIn )
private val output: EightBitNumber = createOutput()

def getOutput: EightBitNumber = output
def getCarryOut: PowerSource = fullAdders(7).getCarryOut

private def createFullAdders( a: EightBitNumber,
b: EightBitNumber,
carryIn: PowerSource ): Array[FullAdder] = {
val fullAdders = new Array[FullAdder](8)
fullAdders(0) = new FullAdder( a(0), b(0), carryIn );
for( i <- 1 until 8 ){
fullAdders(i) = new FullAdder(a(i),b(i), fullAdders(i-1).getCarryOut);
}
fullAdders
}

private def createOutput(): EightBitNumber = {
val out = new Array[PowerSource](8)

var count = 0;
fullAdders.foreach( p => {
out(count) = p.getSumOut
count = count + 1
}
)
new EightBitNumber(out)
}
}

This code was designed to build an 8 bit adder out of two 8 bit numbers (numbers in this particular case aren't much more than arrays of bits) and a carry in bit. This is your typical, ordinary, everyday 8 bit adder that you much have seen in 1950. The adders job is simple, output the result of the two input numbers added up. As with any 8 bit adder, there are 9 outputs, 8 standard output bits, and the carry out/overflow bit.

The adder accomplishes addition in a standard fashion, by chaining 8 full adders (one bit adders) together. The first full adder in the chain uses the given carry in bit as its carry in bit, and subsequent adders in the chain use the carry out of the previous full adder as the carry in. The carry out of the entire adder is simply the carry out of the last full adder in the chain. Here is a picture of one:

Now that we have all the background out of the way, I'll start the refactorings. I'm actually going to go a little bit in reverse order, refactoring the createOutput() method first, because it is substantially easier to refactor than the createFullAdders method.

Simple Refactoring

Lets take another look at createOutput:

private def createOutput(): EightBitNumber = {
val out = new Array[PowerSource](8)

var count = 0;
fullAdders.foreach( p => {
out(count) = p.getSumOut
count = count + 1
}
)
new EightBitNumber(out)
}

This method is returning an EightBitNumber, which is really just an array holding the 8 output bits. The code is terribly imperative, and terribly terrible. The sad thing is, I actually wrote this code, and I'm not just making up a bad example :( Anyway, its overall strategy is pretty clear.

Create an empty, length 8 array
Create a counter object for indexing into the array
Loop over all the full adders (those are already create by the time this method gets called, and well see that in a bit)
For each adder: Put each full adders sum out into the array, and increment the counter.
Finally, create an 8 bit number object using the array.

The first 4 steps above are there simply to create the array to pass to the EightBitNumber object. Now lets take a look at the refactored code:

private val output = new EightBitNumber(fullAdders.map(fa => fa.getSumOut))

Wow! That looks a lot easier - 12 lines down to 1! But...some people might not know what it does, so I'll do my best to explain. The map method, which is a method on all Seq objects (short for Sequence; Array is a subclass), "Returns the list resulting from applying the given function f to each element of this list." An example should help.

Given a=List(1,2,3,4,5) then a.map( i => i * 10 ) returns List(10,20,30,40,50). i * 10 was applied to each element "i" in the list.

In the cpu simulator code above, the call to map has built an Array containing the sumOut of each full adder using the function fa => fa.getSumOut.

Slightly More Difficult Refactoring

With the easier part out of the way, I tackled the more difficult createFullAdders. Let's review the original implementation again.

private def createFullAdders( a: EightBitNumber,
b: EightBitNumber,
carryIn: PowerSource ): Array[FullAdder] = {
val fullAdders = new Array[FullAdder](8)
fullAdders(0) = new FullAdder( a(0), b(0), carryIn );
for( i <- 1 until 8 ){
fullAdders(i) = new FullAdder(a(i),b(i), fullAdders(i-1).getCarryOut);
}
fullAdders
}

This method is responsible for creating all the full adders, and chaining them together. The createOutputs method was only responsible for getting all the outputs off of the full adders created here.

Similar to the last method, this method uses an imperative style, creating an array, populating it, and finally returning it. It's quite a bit trickier though because of the chaining. You can't simply use the map function because there's no context in map. Here, each new full adder needs to know about the preceding full adder. This guy is going to be a bear to explain, but let me just go ahead and dump the code on you:

val (fullAdders, carryOut) =
(as zip bs).foldLeft((List[FullAdder](),carryIn)){
case ((current, carry), (a, b)) =>
val adder = new FullAdder(a, b, carry)
(current ::: List(adder),adder.carryOut)
}

With James Iry's help, we've made this code about as simple as possible. With the first pass, I wasn't sure if the functional code was more readable than the imperative, but after he helped me clean it up, I'm positive. Now, if you aren't familiar with some of the concepts contained in that code, you might be thinking, "What are you $%^&ing nuts?" But, I'm convinced that after you get used to reading this, it's so much easier to read, and so much less error prone, and so much more natural, that you'll never go back. Honestly, after leaving this project alone for almost a year and coming back to it and finding the imperative code, I almost threw up in my mouth a little.

Okay, now I'll try to explain these concepts, and most likely fail miserably.

First, and simplest, is zip. This one is pretty easy. Taken right from the Scaladoc - zip:
"Returns a list formed from this list and the specified list 'that' by associating each element of the former with the element at the same position in the latter. If one of the two lists is longer than the other, its remaining elements are ignored."

I think a few examples will explain perfectly.

Given a=List(1,2,3) and b=List(a,b,c) then a.zip(b) will return List((1,a), (2,b), (3,c)).
Given a=List(1,2,3) and b=List(a,b,c,x,y,x) then a.zip(b) will return List((1,a), (2,b), (3,c)), as the remaining elements in b are ignored.

The code in the cpu simulator zips as and bs, which associates the appropriate input bits together. Take a quick look back at the picture to see that this returns ((a0,b0),(a1,b1),(a2,b2),(a3,b3),(a4,b4),(a5,b5),(a6,b6),(a7,b7)).

Next is foldLeft, which is a bit more complicated. Once again, from the Scaladoc - foldLeft:
Combines the elements of this list together using the binary function f, from left to right, and starting with the value z.

This one I've written up separately, because it was so long. You can find it at http://jackcoughonsoftware.blogspot.com/2008/11/foldleft-in-scala-little-schemer-style.html

Next is pattern matching, but I have to go to bed again! At least I've made some progress :)

Revised Code

Here is the finshed product, which no longer uses 8, but instead creates adder chains of N, depending on the length of the inputs. Overall, I think it's a vast improvement over the original.

class AdderChain(as: Number, bs: Number, carryIn: PowerSource) {

if( as.size != bs.size ) error("numbers must be the same size")

val (fullAdders, carryOut) =
(as zip bs).foldLeft((List[FullAdder](),carryIn)){
case ((current, carry), (a, b)) =>
val adder = new FullAdder(a, b, carry)
(current ::: List(adder),adder.carryOut)
}

val output = new Number(fullAdders.map(fa => fa.sumOut))
}

Using Scala Implicits to Replace Mindless Delegation

2008-11-24T15:39:00.000-08:00

I'm still refactoring my Scala CPU Simulator code, as I keep finding ways to just lop off piles of unneeded code. In this latest example, I was using pretty standard Java style delegation - having my class implement an interface, having a member variable of that interface, and delegating all method calls on that interface to the member variable.

There are several problems with this:

The main problem: if I add a method to the interface I then have to add it to everyone implementing the interface. But, what If I'm not actually writing the implementation of the interface? Client code won't compile. Adding an implicit doesn't remove this problem entirely, but it certainly works for plain old delegates.

It's error prone. Maybe the method was a void, and my IDE added the signature for the method, so the code compiles, but I forgot to actually delegate to the member.
It's just plain wordy and ugly.

To remove the boilerplate, all I needed to do was add an implicit conversion from my class to the interface, using the member variable. I'll show this below.

First, here is an example of the old, more wordy style:

trait PowerSource{
def connect( p: PowerSource ): Unit
def disconnect( p: PowerSource ): Unit
def reconnect( p: PowerSource ): Unit
}

class DelegateToPowerSource( in: PowerSource ) extends PowerSource {
def connect( p: PowerSource ) = in connect p
def disconnect( p: PowerSource ) = in disconnect p
def reconnect( p: PowerSource ) = in reconnect p
}

DelegateToPowerSource has a member, "p", and implements the PowerSource interface by delegating to that member for each of the methods on the PowerSource interface. The more methods that PowerSource has, the longer DelegateToPowerSource gets, and yet the code is just boilerplate. Even if the IDE does this for you, its still wordy and potentially error prone.

Now for the new version:

trait PowerSource{
def connect( p: PowerSource ): Unit
def disconnect( p: PowerSource ): Unit
def reconnect( p: PowerSource ): Unit
}

object DelegateToPowerSource{
implicit def delegateToPowerSource( d: DelegateToPowerSource ) = d.p
}

class DelegateToPowerSource( p: PowerSource )

That's it. Now, any time I add a method to the PowerSource interface (I should probably start calling it trait), DelegateToPowerSource simply has that method; via the conversion. I never have to change DelegateToPowerSource because of a change to PowerSource. DelegateToPowerSource can simply have whatever code in it that it was originally intended to have, obviously augmenting PowerSource in some way.

For completeness, I'll post the actual code where I did exactly this. But, it's pretty much the same, so if you get the point, no need to keep reading.


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

abstract class BaseLogicGate(val inputA: PowerSource, inputB: PowerSource) extends LogicGate {

  def state = output.state
  
  def -->( p: PowerSource ): PowerSource = output --> p 
  def <--( p: PowerSource ): PowerSource = output <-- p 
  
  def disconnectFrom( p: PowerSource ): PowerSource = output disconnectFrom p 
  def disconnectedFrom( p: PowerSource ): PowerSource = output disconnectedFrom p 

  def handleStateChanged( p: PowerSource ) = {}
  def notifyConnections = {} 
}

class AndGate(a: PowerSource, b: PowerSource) 
  extends BaseLogicGate(a: PowerSource, b: PowerSource){
  val output = new Relay(a, new Relay(b))
}

Of course there were several other LogicGates (or, nor, nand, etc). All of this was condensed down to:


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

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

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

BaseLogicGate is now removed entirely. This is great because BaseLogicGate was really weird, it didn't even use its inputs. The only reason it was there was to decouple the delegation logic from the actual trait.

Now things have become MUCH more clear. AndGate is a LogicGate with inputs A and B, and one output, made from Relays.

Equalizer

2008-11-18T21:04:00.000-08:00

I wrote a cool Equalizer class in Scala that allows me to do assertions that are more readable than traditional assertions.

Quick side note: (Equalizer is really an idea shamelessly stolen from Bill Venners Equalizer in ScalaTest. Hopefully we'll add my methods in as well.)

My Equalizer lets me do things like:

val x = 5
x mustBe 5

This replaces the more common assertEquals( x, 5 ), and I think it does so nicely.

You can also do a few more sophisticated things with it, like so:

val x = 5
x mustBe ( 3 or 4 or 5 )

I probably could have used "in" here, such as x mustBe in( 3, 4, 5 ) ... what do you think?

Additionally:

val x = 5
x cantBe 6

For whatever this one is worth (I've actually found use cases for it):

val x = false
x canBeNullOr false

val y = 6
y canBeNullOr ( 5 or 6 )

This works by implicitly converting Any to Equalizer, which contains the methods above. The code can be found below.


import org.testng.Assert._

case object Equalizer {
  implicit def anyToCompare(a: Any) = new Equalizer(a)
}

class Equalizer(a: Any) {

  def mustBe(bs: Any*): Unit = {
    bs(0) match {
      case x:MyTuple => x mustBe a
      case _ => {
        val message = "In Equalizer: expecting one of=" + bs + "\nIn Equalizer: actual  =" + a
        println(message)
        bs size match {
          case 1 => assertEquals(a, bs(0), message)
          case _ => assertTrue(bs.contains(a), message)
        }
      }
    }
  }

  def canBeNullOr(bs: Any*) = {
    if (a != null) mustBe(bs: _*)
    else println("In Equalizer: expecting one of=" + bs + " or null\nIn Equalizer: actual  =" + a)
  }

  def cantBe(b: Any) = assertFalse(a == b)

  def is(b: Any) = a equals b

  def or(b: Any) = {
    a match {
      case x:MyTuple => x + b
      case _ => MyTuple2(a, b)
    }
  }

  import Equalizer._

  trait MyTuple{
    def +(b: Any): MyTuple
    def mustBe(a: Any): Unit
  }
  case class MyTuple2(y: Any, z: Any) extends MyTuple{
    def +(b: Any): MyTuple = MyTuple3(y, z, b)
    def mustBe(a: Any): Unit = a mustBe (y,z)
  }
  case class MyTuple3(x: Any, y: Any, z: Any) extends MyTuple{
    def +(b: Any): MyTuple = MyTuple4(x, y, z, b)
    def mustBe(a: Any): Unit = a mustBe (x,y,z)
  }
  case class MyTuple4(w: Any, x: Any, y: Any, z: Any) extends MyTuple{
    def +(b: Any): MyTuple = MyTuple5(w, x, y, z, b)
    def mustBe(a: Any): Unit = a mustBe (w,x,y,z)
  }
  case class MyTuple5(v: Any, w: Any, x: Any, y: Any, z: Any) extends MyTuple{
    def +(b: Any): MyTuple = MyTuple6(v, w, x, y, z, b)
    def mustBe(a: Any): Unit = a mustBe (v,w,x,y,z)
  }
  case class MyTuple6(u: Any, v: Any, w: Any, x: Any, y: Any, z: Any) extends MyTuple{
    def +(b: Any): MyTuple = throw new IllegalArgumentException("too many ors")
    def mustBe(a: Any): Unit = a mustBe (u,v,w,x,y,z)
  }
}

Sorry about MyTuple...I wanted people to be able to use Tuples as arguments in their mustBe statements, so I had to make sure I didn't pass in a Tuple into mustBe, via the "or" method. Anyway, Tuples don't even appear to be working so....ugh... If anyone can help me clean this up, that would be awesome.

Regardless, what do you think? I really like using the code in tests, even if the Equalizer class itself is a bit hairy.

Refactoring Scala: My CPU Simulator Revisited

2008-11-17T21:55:00.000-08:00

I'm preparing to learn Ruby (though I've already tinkered with it some), and to do so, I'm going to revisit my CPU Simulator project that helped me learn Scala so well. I'm going to write it again in Ruby.

So today, I took up revisiting it, with the goal in mind of writing some Ruby. Turned out that didn't actually happen. What did happen was a lot of refactoring of the original Scala code. I hadn't touched that code in several months, and in between then and now I've written a LOT of Scala. Here's some of the things I've learned (and refactored).

I used to use way too much redundant type information. This was a natural habit from writing Java for so long (in fact, pretty much all my bad habits stem from too much Java). I rigorously removed ALL the obviously redundant type declarations. I did find that in some cases it helped to have it there, that the code wasn't exactly clear without it, and so I left it. I'm very interested to see what happens here when I slide over to Ruby.
Out of habit, I used a lot of unneeded semi-colons. I removed all of them. I hate semi-colons. It's official.
I got a lot better at functional programming. There were a lot of areas where I should have used functions, and I refactored the code to do so. My line of code cound is down considerably.
Finally, I removed all the Hamcrest matchers. This one I'll explain in more detail in my post tomorrow. I'm basically using my own assert library that allows me to say things like: x mustBe 5 I prefer this style to any other assertions I've come across.

Back

2008-11-16T22:05:00.000-08:00

For the past several months I've been giving my life to a cause that I now believe will fail miserably. I've decided to leave the NYSE. I wasn't being challenged technically, and management was simply not up to snuff. They actually asked me to, "just drink the kool-aid". I swear.

I haven't been writing, and I haven't even been coding much, all to work on this Death March project. Basically, its been terrible, and I feel like I went into a coma and I've just come out. I'm going to start writing again passionately.

I've accepted a new position where I'll be writing IPhone applications, Facebook apps with Rails, other web work with Rails, etc. I'm very excited about it. I get to learn two languages that I have little experience with (Ruby and Objective C). I get to work with a team that is much more in line with my way of thinking - adopting new technology, open-minded, agile, lots of tests, curious. It feels like a giant weight has been lifted off of my back. I'm very excited.

Additionally, I won't have to work in Java anymore. I'm convinced at this point that java is a dying language. I heard Neal Gafter left Google to work on languages at Microsoft.

I feel his situation parallels mine. He worked tirelessly on closures for Java 7, which he truly believed (as do many) were right for the language. But, the JCP is so damned conservative, that not only will his closures probably not make it into Java 7, but come on...will Java 7 ever actually come out?

I worked tirelessly for NYSE, trying to introduce new technology and exciting ideas. I tried to bring in Scala, and was shot down. I tried to bring in a test first attitude and stress that we really needed time to work on the testing framework there in general, only to be shot down at every suggestion. I felt the same as I imagine Neal felt, "This is impossible".

I believe NYSE ATS software projects will continue to fail until management is replaced.

This was a bit of a rant, but it was a long time coming.

Language Feature Request

2008-09-13T16:53:00.000-07:00

Maybe this feature exists in some language, I'm not sure. My inexperience is letting me down. :( Here is what I want, as demonstrated in Scala.

I want to be able to use the name of my variable programmatically. So, instead of having to give my objects names like this:


case class Server( name: String )
val server = Server("Altair")
println(server)

Which yields: Server("Altair")

or like this:


class Server( name: String ){ override def toString = name }
val server = new Server("Altair")
println(server)

Which yields simply: Altair

I would like something like this:


case class Server extends VariableName
val Altair = new Server
println(Altair)

Which yields simply: Altair

That example shows it as simply a library. It probably can't be done as a library, so it seems like it would have to be a language feature. Something like this.


varname case class Server
val Altair = new Server
println(Altair)

Which yields simply: Altair

Does anything like this exist? Would it be terribly difficult to build into a compiler? Things would probably be tricky if you said something like...


varname case class Server
val Altair = new Server
val Moxy = Altair
println(Moxy)

Would you want to get Altair, or Moxy?

Can anyone give any opinions on this at all?

Using Scala Actors

2008-07-06T15:47:00.000-07:00

I'm assuming (maybe incorrectly) that most of the Actors that will be written will simply want to react to messages, forever. Something like this:


val reactor = new Actor(){ 
  def act() { 
    loop{ 
      react{
        case msg => ...
      } 
    } 
  } 
}

Given that assumption, it seems like it would be nice just to define whats in the react portion of the code. The rest is redundant. This is pretty simple. First, I created a simple little factory called Actors.


object Actors{
  def newReactor( f: PartialFunction[Any,Unit] ): Actor = { 
    new Actor(){ def act() { loop{ react(f) } } }
  }
}

and then I simply used it:


val reactor = Actors.newReactor {
  case msg => println( "Got something: " + msg )
}

This consolidated the code outside the actual reaction from 4 lines (and 4 right brackets) to a single line (and a single right bracket).

You can also do some other interesting which allow you to keep your reaction code separate from the actual actors (you can do this using the original approach as well). You can define partial functions, and pass them into the newReactor method like this:


def normalReaction : PartialFunction[Any,Unit] = {
  case x: int => println( "Got int: " + x )
  case msg => println( "Got something else: " + msg )
}
  
def abnormalReaction : PartialFunction[Any,Unit] = {
  case msg => println("eruhewiurhqweihu!!!!")
}

val normalReactor = Actors.newReactor { normalReaction } 
val abnormalReactor = Actors.newReactor { abnormalReaction }

I know this is all rather simple and trivial, but I'm crazy about reducing redundancy and improving readability.

Scala and Enums

2008-06-15T21:45:00.000-07:00

Scala doesn't have language level support for enumerations, but I think its fairly easy to argue that its a good thing. First, something isn't quite right about Java enums. Sometime soon I'll post more about that. Scala is such a nice language that you can do things cleanly without needing built in support for extra things like enum. Extra features in a language clutter it up.

As an example, I lovingly ripped off the Planets example from the Java tutorial itself, and implemented it in Scala. Here is the Scala code.


case object MERCURY extends Planet(3.303e+23, 2.4397e6)
case object VENUS extends Planet(4.869e+24, 6.0518e6)
case object EARTH extends Planet(5.976e+24, 6.37814e6)
case object MARS extends Planet(6.421e+23, 3.3972e6)
case object JUPITER extends Planet(1.9e+27,   7.1492e7)
case object SATURN extends Planet(5.688e+26, 6.0268e7)
case object URANUS extends Planet(8.686e+25, 2.5559e7)
case object NEPTUNE extends Planet(1.024e+26, 2.4746e7)
case object PLUTO extends Planet(1.27e+22,  1.137e6)

// mass in kilograms, radius in meters
sealed case class Planet( mass: double, radius: double ){
    // universal gravitational constant  (m3 kg-1 s-2)
    val G = 6.67300E-11      
    def surfaceGravity = G * mass / (radius * radius)
    def surfaceWeight(otherMass: double) = otherMass * surfaceGravity
}

And here is the original Java code.


public enum Planet {
    MERCURY (3.303e+23, 2.4397e6),
    VENUS   (4.869e+24, 6.0518e6),
    EARTH   (5.976e+24, 6.37814e6),
    MARS    (6.421e+23, 3.3972e6),
    JUPITER (1.9e+27,   7.1492e7),
    SATURN  (5.688e+26, 6.0268e7),
    URANUS  (8.686e+25, 2.5559e7),
    NEPTUNE (1.024e+26, 2.4746e7),
    PLUTO   (1.27e+22,  1.137e6);

    private final double mass;   // in kilograms
    private final double radius; // in meters
    Planet(double mass, double radius) {
        this.mass = mass;
        this.radius = radius;
    }
    public double mass()   { return mass; }
    public double radius() { return radius; }

    // universal gravitational constant  (m3 kg-1 s-2)
    public static final double G = 6.67300E-11;

    public double surfaceGravity() {
        return G * mass / (radius * radius);
    }
    public double surfaceWeight(double otherMass) {
        return otherMass * surfaceGravity();
    }
}

The Scala code is nicer, though its unfortunate that you have to say "extends Planet" for each Planet. Each planet is defined as a Scala "object" which is really nothing more than a singleton, which is what enum values are in Java.

I could and should go into more detail on all of this, but I'm mostly posting it for my own reference.

When To Call a Constructor Part 1

2008-05-17T08:50:00.000-07:00

I've it said before (and people a lot smarter than me like Gilad Bracha), and I'll say it again: Constructors are Evil. Unfortunately, in most common situations, they are impossible to avoid. Rather than beating a dead horse, I'm going to take a slightly different approach. In this post I'll focus on when it is ok to call a constructor, and how to do so effectively. This information can be applied to any number of OO languages.

(Note: It is of course sometimes possible to get away from calling constructors by using a DIF like Guice. Sometimes its just not possible. For example, you have a legacy code base that you are maintaining/extending. It may be possible to switch it over to a DIF, but its unlikely to happen all at once and you probably don't want to end up with a code base that is somewhere halfway between. That can make code even more difficult to reason about. Regardless, even if you are using a DIF you still want to call new sometimes, which I'll explain later.)

I'll start with a simple example.


public class PersonCache {

  private final Map<Name, Person> storage;
  
  public PersonCache(){
    storage = new HashMap<Name, Person>();
  }
  
  public void addPerson(Person p){
    storage.put(p.getName(), p);
  }

  public Person getPerson(Name name) {
    return storage.get(name);
  }
  
  public void removePerson(Person p){
    storage.remove(p.getName());
  }
}

This class looks reasonable, and in fact it is. But as you'll see later, simple classes like this lull developers into a false sense of security with the "new" statement. Here, calling new on HashMap is ok because:

It is a trusted/tested class
It has no significant dependencies

It doesn't reference any static state
It doesn't do any IO

Theres a bit of a theme here. If you are going to call a constructor, you need to have a solid understanding of the class you're instantiating. Because it's so well documented, we know HashMap is safe to instantiate. Unfortunately, most code isn't so well documented. Most developers don't understand each class they instantiate.

So why isn't it ok to instantiate an unknown, untrusted class, or a class with dependencies?

To answer that lets first briefly look at the design forces. There are at least four (and probably more) design forces at play here.

Encapsulation
Readability
Static Dependencies
Testability

The forces certainly push and pull on each other a bit. As encapsulation goes up so do readability and static dependencies, while and testability goes down. While we can't always have the best of each, it's important to understand when to choose one over the other.

Consider the following example.


public class PersonCacheWithDatabase {

  private final Database storage;
  
  public PersonCacheWithDatabase(){
    storage = new Database();
  }
  
  public void addPerson(Person p){
    storage.put(p.getName(), p);
  }

  public Person getPerson(Name name) {
    return storage.get(name);
  }
  
  public void removePerson(Person p){
    storage.remove(p.getName());
  }  
}

This certainly doesn't look a whole lot different than the first example. But, its infinitely worse. Doubly do because it cleverly tricks you into thinking that its ok by looking so similar.

First, DatabasePersonCache may appear to be encapsulated, but in reality its not. It forces you to know about the database whether you like it or not. If you're going to call this constructor, you had better have a database set up somewhere. Otherwise, try to use it and you're going to get exceptions left and right. For the exact same reason, its difficult to read and test this code. Reading it alone is simply not enough. You need to understand the database class as well. Additionally, this class is forever statically bound to the Database class. If you somehow want to store your people in a more convenient way, well, you just can't. If you want to test a class that uses PersonCache, good luck.

There is a way around this - pass in a StorageStrategy into PersonCache.


public interface StorageStrategy {

  public void put(Name name, Person p);
 
  public Person get(Name name);
 
  public void remove(Name name);
}


public class PersonCacheWithStorageStrategy {

  private final StorageStrategy storage;
  
  public PersonCacheWithStorageStrategy(StorageStrategy storage){
    this.storage = storage;
  }
  
  public void addPerson(Person p){
    storage.put(p.getName(), p);
  }

  public Person getPerson(Name name) {
    return storage.get(name);
  }
  
  public void removePerson(Person p){
    storage.remove(p.getName());
  }
}

PersonCacheWithStorageStrategy is much better than the PersonCacheWithDatabase. As long as StorageStrategy is an interface, PersonCache is now nice and reusable, it can be used with a HashMap, a Database, anything. It isn't statically bound to any implementation. It's definitely more readable as you are safe assume that the StorageStrategy passed in works fine. It's far more testable on the whole - you don't have to set up a database to test it.

However, even though its better than the second example, it does suffer problems that the original PersonCacheWithHashMap does not suffer - poor encapsulation. You have to know something about StorageStrategy in order to use it. What if you only ever want to use this as a quick in-memory helper object? The first example would be far better. What if you only ever needed the in-memory storage capability while using PersonCache? A client is still forced to create a StorageStrategy. Ick.

This is the point where it would be really nice to have a forth example and say this is how to do it. Unfortunately there isn't one magic scenario that solves every problem. Developers need to understand the design forces and the code objects they are clients of in order to make reasonable decisions about their code. If its not entirely safe to call new, based on the rules above, then you must pass your dependencies in. You trade some encapsulation for another design force: sanity.

Now, you may be thinking, well great, in the example 3 you just deflected the problem of calling new upward, but that doesn't help me much, since I still have to call new in the clients of PersonCache. You would be correct. I haven't addressed that issue just yet. But for that you'll have to stay tuned for part two of this mini series.

My First Scala Presentation

2008-05-17T05:35:00.000-07:00

I gave my first talk on Scala today, to my team at NYSE. It was an entirely informal, BYOL (Bring your own lunch) talk that I hadn't prepared for at all (I was hoping someone else would speak, but since no one else ever does, its always me, prepared or not). Anyway, there are some lessons learned from the talk.

The talk didn't really go over that well, and mostly because I didn't hit them hard with a great example up front. Next time I will. I finally won them over when I showed a List example, which I'll show here.

Say you want to create a List of integers containing the elements 1, 2, and 3. In Java there are a few ways to go about it, none of them very easy. I'll start with the most common example.


List<Integer> ints = new ArrayList<Integer>();
ints.add(1);
ints.add(2);
ints.add(3);

Like I said, there may be easier ways to do this, but I don't think many people will argue that this would be by far the most commonly used approach. There are several things wrong with it.

It's about a billion characters long.
The redundant type information in the first line is so frustrating.
The next three lines of code are almost identical.
The semi colons are pretty much pointless.

Here's how you do the same thing in Scala.


val ints = List(1,2,3)

Thats it.

Its 20 characters total (not including the unneeded spaces). 20 characters vs. A Billion! I pick 20.
There is no need whatsoever to put an absurd amount of type information. The compiler is perfectly capable of figuring that out thank you. As are humans; any second year college student could tell that thats a list of integers. Heck, any 7 year old could too.
There is absolutely no redundant code here.
There are no semi colons.

This example has probably been posted on the internet about a million times by now, and its not the point of this post. The point is this: If you want to give a talk on a language, hit the audience hard with a solid example immediately. Don't dilly-dally and give examples that are only slightly different than their current language and then give them the good stuff. You'll meet too much opposition up front. I thought I was doing them a favor by easing them into Scala but what really happened was quite the opposite. For some terrible reason Java developers are quite territorial. I was providing fuel for them to say, "I'll stick with Java."

Next time, I give the good example up front, then transition to the easy stuff once I've peaked their interest, and then make sure to finish up with a solid example too. And of course next time I'll be quite a bit more prepared.

Ok. Thats the gist of what I was wanting to talk about, now some sideline commentary.

One particularly odd complaint IMO was that most of this was just syntactic sugar. First off, I whole-heartedly disagree, but I can see why some people could incorrectly think that way. My colleague happily responded:

If you think it's just syntactic sugar, then I have a perfect language for you. It only contains 2 characters, 1, and 0. Using anything else, well thats just syntactic sugar.

Of course anyone can think that higher level languages are just prettier syntax, but they would be entirely missing the point. The point is to not have our primitive human minds bombarded with useless information so that we can better and more easily understand the meaning of each line of code. Thats not sugar, thats evolution, baby.

ScalaTest and TestNG

2008-04-04T09:36:00.000-07:00

THIS IS AN INCOMPLETE DRAFT, POSTED FOR REVIEW. I UNDERSTAND SOME SECTIONS NEED WORK AND SOME SECTIONS ARE EMPTY OR MISSING ENTIRELY, AND THAT THE FORMAT MIGHT BE MESSED UP.

ScalaTest has two important goals.

Allow tests to be written in Scala easily, and concisely.
Allow Java developers to transition to ScalaTest with minimal effort.

With these two goals in mind I'm happy to announce ScalaTest's integration with TestNG. This integration offers two features that meet the goals of ScalaTest.

TestNG tests can be written in Scala, and run in both ScalaTest and TestNG runners.
Existing TestNG tests can be run in ScalaTest.

By being able to write new TestNG tests in Scala, a developer doesn't have the overhead of learning a new test framework and a new language at once. And more importantly, by being able to run existing test suites in ScalaTest developers can feel confident that all their code is working without the overhead of running two test frameworks at once.

This article will show you how to use ScalaTest to do both, with the help of an example (available for download from the ScalaTest Subversion repository). The example has been tested against Scala 2.7.0, and TestNG 5.7. To use the example you'll also need to download the latest version of ScalaTest.

After downloading everything, you'll need to place the jars into the lib directories of the example. Place the TestNG jar into the java/lib, and place the Scala related jars into the scala/lib folder. You should end up with the following directory structure (as shown here in Eclipse).

About the Example

The example contains what we'll refer to as "existing" code (Java), and "new" code (Scala). The thinking here is that you are working on an existing project in Java, you have a Java code base complete with unit tests (you do have unit tests, don't you?), and that you're interested in exploring Scala. If you're Java code isn't covered with tests the content here is still relevant; you can learn how to write TestNG tests in Scala.

The existing code lives in the java folder where you'll find:

VolumeKnob.java - An interface for volume knobs
BoringVolumeKnob.java - A boring implementation of VolumeKnob
BoringVolumeKnobTest.java - A boring test for BoringVolumeKnob
volume-tests.xml - A TestNG XML suite to run BoringVolumeKnobTest
build.xml - Ant file that builds the code and runs the tests

The new code is in the scala folder, and it builds upon the existing Java code. In the scala folder you'll find:

AwesomeVolumeKnob.java - A totally awesome implementation of VolumeKnob
AwesomeVolumeKnobTest.java - An awesome test for AwesomeVolumeKnob
build.xml - Ant file that builds the code and has targets to

Run just the existing Java tests in ScalaTest
Run just the Scala tests in ScalaTest
Run both the Java and Scala tests in ScalaTest

Quick Look At What Needs To Be Tested

In the next section we're going to learn how to write TestNG tests in ScalaTest. But before we do, lets take a quick look at what we're going to test. Recall in the java folder the interface VolumeKnob. It's very simple:


public interface VolumeKnob {
    public abstract int currentVolume();
    public abstract int maxVolume();
    public abstract void turnUp();
    public abstract void turnDown();
}

VolumeKnob has two implementations that need testing. The first is a rather boring Java implementation - BoringVolumeKnob. It's too boring to show here, and it can't be turned up beyond 10. It has a corresponding TestNG test class also written in Java - BoringVolumeKnobTest. That won't be shown here either, since we'll assume you know TestNG.

There is also a Scala implementation of that interface, AwesomeVolumeKnob. AwesomeVolumeKnob's have three amazing qualities:

They always go to at least 11 (of course)
They can never be turned down
They can always be turned up, regardless of the max volume.


import org.scalatest.legacy.VolumeKnob

class AwesomeVolumeKnob( val maxVolume: int ) extends VolumeKnob {
  if( maxVolume < 11 ) 
    throw new IllegalArgumentException("...These go to eleven.");
  
  var currentVolume = maxVolume;
  
  def turnDown = 
    throw new IllegalAccessError("AwesomeVolumeKnobs cannot be turned down");
  
  // AwesomeVolumeKnobs don't care about max volume
  def turnUp = currentVolume = currentVolume + 1;
}

AwesomeVolumeKnob is accompanied by AwesomeVolumeKnobTest, which is a TestNG test written in Scala. We'll cover that next.

Writing TestNG tests in ScalaTest

Because Scala allows you to use Java's annotations, TestNG tests can be written in Scala at least as easily as they can in Java. Here is a quick example:


import org.scalatest.legacy.VolumeKnob

class AwesomeVolumeKnobTest{
  @Test
  def awesomeVolumeKnobsCanBeTurnedUpReallyHigh(){
    val v = new AwesomeVolumeKnob(10000)
    for( i <- 1 to 1000 ) v.turnUp
  }
}

There's really nothing to it. This class can be compiled by the Scala compiler and run in any TestNG runner.

To enable your test to be run in ScalaTest, simply extend the ScalaTest trait org.scalatest.testng.TestNGSuite. That's it. Here is the full implementation of AwesomeVolumeKnobTest in all its glory.


import org.scalatest.testng.TestNGSuite
import org.testng.annotations._

class AwesomeVolumeKnobTest extends TestNGSuite{

  @Test{ val description=
         "create AVK's with max volume < 11 and ensure IllegalArg is thrown" 
         val dataProvider="low volumes", 
         val expectedExceptions = Array( classOf[IllegalArgumentException] )}
  def awesomeVolumeKnobsAlwaysGoToAtLeastEleven(maxVolume: int){
    new AwesomeVolumeKnob(maxVolume);  
  }  
  
  @Test{ val description=
         "try to turn down some AVK's and ensure IllegalAccess is thrown"
         val dataProvider="high volumes", 
         val expectedExceptions = Array( classOf[IllegalAccessError] )}
  def awesomeVolumeKnobsCanNeverBeTurnedDown(maxVolume: int){
    new AwesomeVolumeKnob(maxVolume).turnDown();
  } 
  
  @Test{ val description="crank it up" }
  def awesomeVolumeKnobsCanBeTurnedUpReallyHigh(){
    val v = new AwesomeVolumeKnob(10000)
    for( i <- 1 to 1000 ) v.turnUp
  }
  
  @DataProvider{val name="high volumes"}
  def goodVolumes = 
    Array(v(11), v(20),v(30),v(40),v(50),v(60),v(70),v(80),v(90),v(100))
  
  @DataProvider{val name="low volumes"}
  def lowVolumes = 
    Array(v(1), v(2),v(3),v(4),v(5),v(6),v(7),v(8),v(9),v(10))
  
  def v( i: Integer ) = Array(i)
}

There are a few things to notice with this implementation.

Running Scala TestNG Tests in ScalaTest

Running TestNGSuite's in ScalaTest is no different than running any other ScalaTest Suite - simply use the Ant task. In scala/build.xml in the example, you'll find a target called "test-scala-only":


 <target name="test-scala-only" depends="compile">
  <taskdef name="scalatest" classname="org.scalatest.tools.ScalaTestTask" 
   classpathref="test.classpath"/>
  
  <scalatest>
   <runpath>
    <pathelement path="test.classpath"/>
    <pathelement location="${test.jar.file}"/>
   </runpath>
   
   <suite classname="org.scalatest.testng.AwesomeVolumeKnobTest"/>
   
   <reporter type="stdout" />
   <reporter type="graphic" />
   
  </scalatest>
 </target>

In this case we have just one Suite to run:

<suite classname="org.scalatest.testng.AwesomeVolumeKnobTest"/>

Running this task brings up the ScalaTest UI:

Running the Java Tests

If you're a TestNG user, you're likely to be familiar with running test suites from the IDE. There are a couple of different ways to do it, and whichever you choose, you're sure to end up like something like this (as shown in Eclipse):

While this is great, and familiar, and comfortable, it would be a pain to have to run your Java tests through TestNG's UI and then have to switch over to ScalaTests UI to run your Scala tests.

Running Java Tests in ScalaTest

ScalaTest provides a simple way to run TestNG xml suites in its Ant task. In scala/build.xml in the example, you'll find a target called "test-java-only":


 <target name="test-java-only" depends="compile">
  <taskdef name="scalatest" classname="org.scalatest.tools.ScalaTestTask" 
   classpathref="test.classpath"/>
  
  <scalatest>
   <runpath>
    <pathelement path="test.classpath"/>
    <pathelement location="${test.jar.file}"/>
   </runpath>
   
   <testNGSuites>
    <pathelement location="${java.dir}/src/test/volume-tests.xml"/>
   </testNGSuites>
   
   <reporter type="stdout" />
   <reporter type="graphic" />
   
  </scalatest>
 </target>

Inside the testNGSuites block, simply put the location of the xml suite.


  <testNGSuites>
    <pathelement location="${java.dir}/src/test/volume-tests.xml"/>
  </testNGSuites>

While in this case there's one xml suite only, ScalaTest supports multiple xml suites. All suites get run in the same TestNG instance. Running ScalaTest via Ant with the graphic reporter option brings up the ScalaTest UI:

As you can see, ScalaTest reported the exact same results as the TestNG Eclipse plugin. (But...notice that our green bar is much brighter!)

Running All The Tests Together

Finally, for the moment of truth...though being so easy, it's likely a bit of a letdown. To run all the tests together, simply use both options in the Ant task, as in the "test" target in scala/build.xml.


 <target name="test-java-only" depends="compile">
  <taskdef name="scalatest" classname="org.scalatest.tools.ScalaTestTask" 
   classpathref="test.classpath"/>
  
  <scalatest>
   <runpath>
    <pathelement path="test.classpath"/>
    <pathelement location="${test.jar.file}"/>
   </runpath>
   
   <suite classname="org.scalatest.testng.AwesomeVolumeKnobTest"/>

   <testNGSuites>
    <pathelement location="${java.dir}/src/test/volume-tests.xml"/>
   </testNGSuites>
   
   <reporter type="stdout" />
   <reporter type="graphic" />
   
  </scalatest>
 </target>

Running this task brings up the ScalaTest UI:

Problems

Summary

ScalaTest and Mocking

2008-02-14T09:53:00.000-08:00

I've added in some mocking into ScalaTest thanks to specs integration. I've done it in a BDD style, kind of like rspec's given/when/then. rspec is much further along and I still need to learn a lot more about it, but thats okay. I'm hoping just to get some peoples opinions on readability and such. Here are a couple very quick examples.



 mockTest( "Report should be generated for each invocation" ){
       
   val reporter = mock(classOf[Reporter])

   expecting( "reporter gets 10 passing reports because invocationCount=10" ) {
     nTestsToPass( 10, reporter )
   }

   when ( "run the suite with method that has invocationCount=10" ){
     new TestNGSuiteWithInvocationCount().runTestNG(reporter)
   }
 }
     
 mockTest( "Reporter should be notified when test is skipped" ){
       
   val reporter = mock(classOf[Reporter])

   expecting ( "a single test should fail, followed by a single test being skipped" ){ 
     one(reporter).runStarting(0) 
     one(reporter).testStarting(any(classOf[Report])) 
     one(reporter).testFailed(any(classOf[Report])) 
     one(reporter).testIgnored(any(classOf[Report]))
     one(reporter).runCompleted()
   }

   when ( "run the suite with a test that should fail and a test that should be skipped" ){
     new SuiteWithSkippedTest().runTestNG(reporter)
   }
 }

As you can see, I've added expecting and when blocks, which optionally take a String (that is currently just used for readability). The simple idea here is that I have grouped chunks of my test into places that make sense, hopefully making it easier for someone reading the test. Do you like it? Do you hate it? Any other opinions that could help?

Which Style Is More Readable?

2008-01-31T19:02:00.000-08:00

I've been writing ScalaTest tests for the ScalaTest TestNG integration (say that five times fast). I used a couple of different styles and I was hoping to get some input on which style people thought was more readable, more clear. Both styles are functional, one merely masks it a bit while the other flaunts it.

The first style I'll show is the discrete style. Here I call a test method which takes a function and executes it.


     test( "Reporter Should Be Notified When Test Passes" ){
    
       val testReporter = new TestReporter

       // when
       new SuccessTestNGSuite().runTestNG(testReporter)

       // then
       assert( testReporter.successCount === 1 )
     }
  

     test( "Reporter Should Be Notified When Test Fails" ){
    
       val testReporter = new TestReporter

       // when
       new FailureTestNGSuite().runTestNG(testReporter)

       // then
       assert( testReporter.failureCount === 1 )
     }

The I'm showing only two examples of calling the test function but in actuality I have many more tests. Notice that in each test the first line is always the same:


       val testReporter = new TestReporter

There are benefits to this. All the code is right there and you can read the test method without looking anywhere else. There are also some negatives as well. I have the same line of code in several places.

Now I'll show the even more functional style. It takes a little more explaining. Here I declare a withFixture method that accepts a function that takes a TestReporter as its input. The withFixture method creates the TestReporter (so each test call doesn't have to) and calls the input function passing it the TestReporter. To create tests I call the testWithFixture function which takes a function and passes it to the withFixture function I just wrote.


     override def withFixture(f: (TestReporter) => Unit): Unit = {
       f(new TestReporter) 
     }
     
     
     testWithFixture( "Reporter Should Be Notified When Test Passes" ){ 
       t: TestReporter =>

       // when
       new SuccessTestNGSuite().runTestNG(t)
       // then
       assertThat( t.successCount, is(1) )
     }
  

     testWithFixture( "Reporter Should Be Notified When Test Fails" ){ 
       t: TestReporter =>

       // when
       new FailureTestNGSuite().runTestNG(t)
       // then
       assert( t.failureCount === 1 )
     }

I'm realizing as I'm writing this that all the extra explaining I had to do is because the code is more complicated. There are definite negatives here. Code is being passed around to other code, you might now be sure how things are actually running, you might not be sure where the TestReporter object is coming from. On the upside the methods are slightly shorter and I've removed the most obvious duplication by moving it to the withFixture function. There's still plenty of duplication (in each example) that could be removed but you can definitely push duplication removal too far. Especially in tests, you must balance duplication and indirection. They are in direct opposition.

Does this code push it too far?

Is this just a setup method in disguise? I'm of the opinion that setup methods are bad, but at least here everything is immutable.

If people were to get used to this style would it become more readable in the long run?

Please please let me know your thoughts.

Scala and TestNG in Far Greater Detail

2008-01-23T19:36:00.000-08:00

I wrote before on running TestNG in Scala and due to popular demand I'm going to go into much greater detail. My goal is to show that running TestNG in Scala is as easy as it is in Java. I've thrown in Hamcrest to show that that integrates seamlessly as well. Hopefully along the way you'll learn a couple of Scala nuggets too. And, be warned I'm assuming you know a bit about TestNG so I'm not going to explain it much. If you don't...www.testng.org

I created a new Scala class for testing my AndGate class. The idea is that I want to make sure that my AndGate is on or off according to the standard And boolean logic table:


x y | output
------------
0 0 |   0
0 1 |   0
1 0 |   0
1 1 |   1

The testing class is called ScalaTestNGExampleTest, and it looks like this:


import org.testng.annotations._
import org.hamcrest.MatcherAssert._
import org.hamcrest.Matchers._;
import org.testng.annotations.DataProvider;
import com.joshcough.cpu.gates._

class ScalaTestNGExample {
  
  @DataProvider{val name="generators"}
  def createGenerators = { 
    val gens = Array(off, on)
    for( x <- gens; y <- gens ) yield Array(x,y)
  }
  
  private def on = new Generator(true)
  private def off = new Generator(false)
 
 
  @Test{ val dataProvider="generators" }
  def testAndGateStates(genA: Generator, genB: Generator){
    val and: AndGate = new AndGate(genA, genB);
    val whatItShouldBe = genA.on && genB.on
    assertThat( and.on, is(whatItShouldBe) );
    println( and.on + "==" + genA.on + "&&" + genB.on )
  }  
  
  @BeforeMethod def printLineBefore = println("------entering test------")
  @AfterMethod  def printLineAfter  = println("------exiting  test------")
  
}

If you aren't familiar with Scala that might look a bit like magic, so I'll explain one step at a time.

Data Provider

The first thing I did was set up a data provider for my logic table:

The annotation declaration is obviously different than in Java. Instead of parentheses, you have to use curly brackets. Instead of simply name/value pairs, you have to declare vars. I could explain why, but instead you could just go to http://www.scala-lang.org/intro/annotations.html.
DataProvider methods are supposed to return Object[][], but...what the heck is this one returning? Well, before I explain what that funky for statement is actually doing I'll just announce that this method is actually returning Array[Array[Generator]]. I could have made it more explicit by saying def createGenerators(): Array[Array[Generator]] but Scala's type inference lets me get away with leaving it off. Does leaving it off hamper readability? In most leaving it off is just eliminating some redundancy. Maybe in this case I should have left it on, but I wanted to show type inference a little bit.
Wait a second...Array[Array[Generator]] isn't Object[][]...or is it? Actually, yes. Scala's typed array class (Array[T]) actually compiles down to Java arrays. In this case, Array[Array[Generator]] compiles down to Generator[][] in Java.
What is Array(on, off)? The type of Array(on, off) is Array[Generator] and it contains two elements, Generator(true) and Generator(false) which are returned from the on and off methods respectively. It may be confusing for a Java programmer to see simply "on" with no parens. In most cases (for reasons far beyond the scope of this post) Scala doesn't force you to use parens on method calls with no arguments.
Ok finally, what is that funky for loop looking thing doing? Rather than explain, why don't I just give the equivalent code in Java for the createGenerators method?


public Generator[][] createGenerators() {

Generator[] onAndOff = new Generator[]{ on(), off() };

Generator[][] gensToReturn = new Generator[4][2];
for( int i = 0; i<onAndOff.length; i++ ){
for( int j = 0; i<onAndOff.length; j++ ){
 gensToReturn[i+j] = new Generator[]{ onAndOff[i], onAndOff[j] };
}
}
return gensToReturn;
}

Honestly? Those three lines of code are doing all of that...? Yes. Honestly. Rather than me trying to explain it though, James Iry does an excellent job in part 2 of his four part series on monads called Monads are Elephants. That is the link to part two, but I recommend reading all four.

So now we have a data provider and we have a reasonable idea how it works. But quickly before I move on, heres another way I could have done it which is arguably more readable but not nearly as much fun. Once again, the idea here is that this data provider is essentially creating the And logic table for us.


def createGenerators = {
Array(Array(on, on),Array(on, off),Array(off, on),Array(off, off))
}

Test Method

At this point I think everything else is really straight forward. Despite that, I'll go over the test method in detail.

The @Test annotation is defined in the same fashion as I described above for @DataProvider. In this case I define which data provider to use. Done.

The method takes two Generator parameters which come from createGenerators method.

The first line simply instantiates an AndGate object using the two Generator parameters.

The second and third lines simply assert that the AndGate is what it should be! It should be on only when both generators are on, according to the logic table. The third line uses Hamcrest matchers for asserting. I'm not going to bother explaining them here.

Finally I throw in a print statement.

BeforeMethod And AfterMethod Annotations

Before each test method is called, TestNG will call any methods annotated with @BeforeMethod. In my case before each method I just print a nice message. The same goes for @AfterMethod, but after each test method, of course.

Results

Here is my output from the console:


 [testng] -----------entering test-----------
 [testng] true==true&&true
 [testng] -----------exiting  test-----------
 [testng] -----------entering test-----------
 [testng] false==true&&false
 [testng] -----------exiting  test-----------
 [testng] -----------entering test-----------
 [testng] false==false&&true
 [testng] -----------exiting  test-----------
 [testng] -----------entering test-----------
 [testng] false==false&&false
 [testng] -----------exiting  test-----------

Problems

I did run into a few problems.

FIXED: ~~Unfortunately, I couldn't use @Test{expectedExceptions = {SomeException.class}} because Scala doesn't you say Anything.class.~~
Running the tests through Eclipse is not as easy as it is in Java, and needs some work. I ended up mostly running through Ant, but sometimes through Eclipse.

Conclusion

I hope I've convinced you that running TestNG in Scala is simple. I didn't test all the features, but most of what I have tested works great. I plan to use it for most of my Scala development. I personally think its pretty far ahead of the pack, but if you want to see for yourself they are: ScalaTest, ScUnit, Rehersal, JUnit, and specs. I've tried the last four, and of those I thought specs was really nice. It seems like a reasonable alternative.

I am very open to hear ideas on why I should switch to an xUnit test framework built in Scala. Are there any advantages? What are they?

My Small Problem with the Scala Actor Model

2008-01-20T20:39:00.000-08:00

Something seems wrong to with the whole send/! idea. The Scala guys say ! apparently means "send", but it really means "add message to actors mailbox", or "put". Take this example:

actor ! message
actor send message

If ! means "send", then it certainly seems like the actor is sending the message. Of course, you have no idea who its sending it to, so by that logic it must be getting the message, but it still just seems confusing. I think the API might be more readable if it used one of the following:

actor <-- message
message --> actor

I've demonstrated that you can use --> and <-- as method names already, so, why not use them here?

Scala: Fold Left Question

2008-01-20T19:16:00.000-08:00

I recently realized that I could make a piece of code I posted in a recent blog much cleaner using foldLeft. I have a bit of a problem however, the code is in a very performance sensitive area and I should break out of the fold whenever I encounter a certain condition. To the best of my knowledge foldLeft has no way to break out. It just folds all the way and you get your result at the finish. This is a bit unfortunate. Is there a way to break out and still keep the code clean?

Here is my example, old code first. A PowerSource is on if any of its incoming power sources are on.


 private def updateOnOff = {
   def calculateOnOff: boolean = {
     incomingPowerSources.foreach( p => {if( p.isOn ) return true; })
     return false;
   }
   val newOnOff = calculateOnOff
   if( cachedOnOffBoolean != newOnOff ){
     cachedOnOffBoolean = newOnOff
     notifyConnections;
   }
 }

Here is the new code using foldLeft.


  private def updateOnOff = {
    val newOnOff = incomingPowerSources.foldLeft( false )(_||_.isOn);
    if( cachedOnOffBoolean != newOnOff ){
      cachedOnOffBoolean = newOnOff
      notifyConnections;
    }
  }

The new code is far nicer than the old code. I've decided I'm going to go with it. In most cases PowerSources have only one direct input. Some have two, like OrGate, but for now I'm going to see what kind of performance hit I get.

Now, if only I had a performance testing framework in Scala. Does anyone know of one?

Closures Non Local Return - Scala And Java

2007-12-30T16:12:00.000-08:00

I've heard a lot of people bickering about Java Closures. One of the many reasons they are fighting with each other is that in the BGGA proposal changes the semantics of return. In BGGA there can be local and non local returns (I'll explain those in a second). Bloch says it going to be too prone to bugs. Gafter says we need to do it before the language becomes a dinosaur. I tend to go with Neal on this one, maybe thats because I'm more adventurous and not quite as worried about bugs since I do extensive unit testing.

Anyway, I wanted to demonstrate the problem in Scala. It did bite me today a little bit. I caught it quickly in my tests. The following two bits of code have different meanings:


private def updateOnOff = {
 def calculateOnOff: boolean = {
   incomingPowerSources.foreach( p => {if( p.isOn ) true; })
   return false;
 }
 cachedOnOffBoolean = calculateOnOff;
}

private def updateOnOff = {
 def calculateOnOff: boolean = {
   incomingPowerSources.foreach( p => {if( p.isOn ) return true; })
   return false;
 }
 cachedOnOffBoolean = calculateOnOff;
}

The purpose of the updateOnOff function is to simply set the cachedOnOffBoolean to true if any incoming power sources are on. If none of them are on, the boolean is set to false. The inner function, calculateOnOff is responsible for looping through the incoming power sources to see if any are on. If one is on the function should return true to the outer function which sets the boolean.

To be honest, I'm not sure which one is the local and which one isn't. I'm in the process of trying to figure it out. It seems natural to me though to assume that the first one is the local return. If anyone knows better, please let me know.

The first example is an example of local return. Local return returns from the most local block of code, and in this case its the closure function itself, not the calculateOnOff function. The closure here is what's inside the foreach call:

( p => {if( p.isOn ) true; } )

This is the function that will be returned from. It simply returns back to the loop, which goes on to the next item. Finally, when the loop is finshed, false is returned. So, in the first example false will always be returned! This is certainly not correct.

The second example is and example of non local return. Specifying "return" before false means that you intend to return from the enclosing method, not just the closure itself. You intend to break out of the loop. You've found what you were looking for, and you were done. The return returns true from the calculateOnOff, and the boolean is set to true, just as you wanted.

Its pretty straight forward when you know it but I'm sure Bloch is right, there are going to be lots of bugs. Developers who don't use unit testing religiously are going to get it. A simply copy past from a refactoring, and boom.

So what does this tell us? Well, at the least it says be careful, and write lots of unit tests. At the most it might mean that lots of idiots just stay in Java and the cool kids move on to Scala, and thats all right now baby, yeah.

Coolest Code I've Ever Written

2007-12-30T10:56:00.001-08:00

Because Scala lets you name methods pretty much whatever you want, I got the chain wires together like this:


 @Test
 def lastPowerSourceInChainShouldBeNotifiedWhenFirstInChainIsTurnedOff() = {
   //given
   val first = new Generator
   val secondToLast = new Wire
  
   first-->new Wire-->new Wire-->new Wire-->secondToLast
  
   val last = createMockWithConnectionTo(secondToLast)
  
   // when
   first.turnOff
  
   // then
   verify(Array(last))
 }

 private def createMockWithConnectionTo( p: PowerSource ): PowerSource = {
   val mockPowerSource: PowerSource = createStrictMock(classOf[PowerSource]).asInstanceOf[PowerSource];
   expect( mockPowerSource <-- p ).andReturn( p )     expect( mockPowerSource.handleStateChanged( p ) )     replay(Array(mockPowerSource))     p --> mockPowerSource
   mockPowerSource
 }

The -->'s are actually methods on any PowerSource that connects the two together. So, the code can actually look like a chain of wires connected together. This is totally the coolest thing ever.

Using TestNG in Scala: By Example

2007-12-28T17:09:00.001-08:00

Here is a very, very simple example of some TestNG stuff that I wrote the other day in Scala (it can also be found here):

package com.joshcough.cpu.electric;

import org.testng.annotations._
import org.testng.Assert_


package com.joshcough.cpu.electric;

import org.testng.annotations._
import org.testng.Assert._

class GeneratorTest {

  @Test
  def expectNewGeneratorToBeOn() = {
     val gen: Generator = new Generator
        assertTrue(gen.isOn);
    }
  
  @Test
  def expectTurnedOffGeneratorIsOff() = {
        val gen: Generator = new Generator
        gen.turnOff
        assertTrue(gen.isOff);
    }  
}

This might not be the prettiest code in the world, but:

It works (which is more than I could accomplish with others)
I can run it in my IDE
I can run it in Ant
I only have to do exactly what I ever did with Java
Its still way better than JUnit

There were a few things I had to do to make this work:

When compiling in Ant, I had to add this to my scalac call:

target="jvm-1.5" ...

When compiling in Eclipse I had to do this:

Project -> Properties -> Scala Compiler Properties -> target = jvm-1.5

I could give a more detailed example, but I haven't tried it yet. I'm pretty sure that things like @BeforeMethod, @AfterClass, @DataProvider and what not all just work the same. I'll try to come up with a better example though.

Reading Scala

2007-12-28T05:34:00.000-08:00

After working a bunch in Scala the other day, and continuing to obsess over it, I've realized something.

Reading the code Scala language source code is perfect code reading material.

I had said that I needed some good code to read. Scala is perfect for this. Here are the reasons its good for me.

It's really good code
Its easy to read (I guess these two go together nomally)
It has a really nice mix of OO and Functional Programming (which I need to get better at anyway)
Its got a compiler written in Scala compiling to Java bytecode. :)
Its a langauge for god sakes, and I want to do language design so I should look at more language implementations

But, are those the same reasons its good for someone else to read? Maybe not, but I think Scala is still great for other people to read, beginners, professionals, and Ph.d's alike.

The first two points hold true: Its really good code, and its easy to read.
Beginners could easily read the data structures code in Scala collections. They could learn their data structures, learn FP, and learn OOP better all at once.
Theres a wealth of stuff for more advanced people to read.

The Actor Model for instance, which is Scalas concurrency stuff built on top of Doug Lea's fork join.

Langauge Designers could read it and learn a bit.

Compiler writers could read it and learn a bit.
Software Engineers could read it, and read the examples to learn a few things:

How to do things better in their own language
What they are missing stuck in an ancient language.

As I said before, It's probably helpful to read java.util.concurrent and the java collections stuff, and I'm sure theres a whole lot of other code thats great to read too. But, I'm getting worn out when it comes to Java. I'm ready to move on. Scala is new and fresh and exciting, and, I'll learn more by doing it.

Unit Testing in Scala and in IDE's in General

2007-12-26T20:02:00.000-08:00

I reviewed a few Scala unit testing frameworks today: SCUnit, and Rehersal. When all was said and done I determined something that I found rather remarkable - TestNG is the best unit testing framework for Scala. For an example click here. To listen to my mind numbing justification of that radical statement, read on...

Why aren't new Unit Testing frameworks up to snuff?

The problem with any new unit testing framework in a new language is that it doesn't have IDE support. This is a huge pain in the ass for someone who relies on their IDE for everything (like me). TestNG already has IDE support, and you can use Java Annotations in Scala, so you can use TestNG just fine in Scala as well.

Does that mean the test frameworks themselves are bad? No, they are fine. But to be entirely honest, its probably not all that worthwhile for someone to build a xUnit framework in Scala other than the fact that its probably really fun. And I say all this knowing full well that could be horse shit - I don't enough about Scala. There may be some nice syntactic stuff that makes testing in Scala just better, more readable, easier to write - I'm not sure. Its my gut feeling. Anyway...

There is still a fundamental underlying problem here.

The main problem with this whole thing is (well there actually might be a couple, but one at a time) that if you want to write an xUnit framework for a language you have write the IDE support for it too. You shouldn't have to do this.

So what can we do to fix this?

IDE's should provide xUnit framework plugin points. All you have to do is plug in your particular framework, and boom instant IDE suppport for your xUnit framework. I've been saying this for a while about languages themselves. All you need to do is plug-in the compiler and boom, you have everything. Maybe thats too much to bite off...but I don't think plugging in your own xUnit is.

The JUnit and TestNG Eclipse plug-ins are nearly identical. They both look damn near the same as the test runner for NUnit. The patterns are clearly obvious. I haven't looked at the implementations at all, so I don't yet have any concrete ideas on how to make this happen, but its so worth it. Someone should do it. It could be me.

Finally...

This could be the first step towards instant IDE support for new languages. Maybe we identify several areas like this that are similar across languages and provide plug-in points for each. What would those features be? I'm not sure I still need to think. And, maybe more languages should just use the support of Java like Scala does.

But, I have to say this was a great day. In my opinion realizing this was a real breakthrough in what I know about well, everything. Additionally, I think I am finally saying things that I haven't really heard other people saying. Maybe they are and I haven't read it, but I feel like I might actually be making some progress.

Things are coming together (and Scala is awesome)

2007-12-26T19:52:00.000-08:00

I did a ton of reading on Scala today, and I did a lot of writing code and using Scala today. This makes me really happy. The best idea that I had today was to throw out any Java code on the CPU Simulator project, and do it all again in Scala. Why? Because if I write it in Java I won't learn as much. So, that is started, and a bunch of the new code is checked in.

Oh man I have a lot to talk about with Scala. I wonder if I should break it into many posts... I think I will.

But let me just say that I what I did today ties together everything I've been working on over the last four months. Doing the CPU Simulator in Scala helps me with languages, language design, IDE's, unit testing, compilers, reading code, preparing to teach classes, everything...

I was sick today, yet able to do work. I didn't have much energy, but sitting here was fine. Mostly I didn't want to get other people sick so I didn't go to work. Anyway, I did some of my best work today, and I was able to come up with a lot of really good ideas and I want to write them down before they are gone forever.

CPU Simulator on Google Code

2007-12-09T19:04:00.000-08:00

No one might actually contribute, except myself, but I put my CPU Simulator project up on http://code.google.com/p/cpusimulator.

This wasn't just for the purpose of generating interest in this project, which is likely uninteresting to most people, but it was my first venture into creating/hosting my own project somewhere in the world. This is something that any self respecting developer should do at some point.

Overall I think Google Code is fabulous. I had my project up in minutes, with my code in Subversion. You get a wiki, downloads, administration, and a number of other things automatically.

Also, and awesomely, this helps me solve a major problem. I've been bitching that I have no way to easily link to code that I've written. Well, now, see this: http://cpusimulator.googlecode.com/svn/trunk/src/main/com/joshcough/cpu/gates/NorGate.java. Totally awesome.

I was disappointed that you only get 10 projects lifetime, but I guess I'll have to choose them wisely. Maybe if I get to be a teacher, and I'm using several projects for teaching, they will lift that limit.

Anyway, I'm really happy. Great day.

Reading Code

2007-12-08T19:43:00.000-08:00

I haven't written and songs in a while. Way too long. Like, maybe a year. Terrible. It dawned on me just now (though I'm sure I knew it a long time ago) - I write more songs, and better songs, when I'm playing other peoples music. This is especially true when the music is difficult for me to play in some way (maybe the guitar part is hard, maybe the vocals are hard, maybe the rhythm is weird).

Notice I said "playing" other peoples music and not "listening" to. However, when I'm listening to more music, I still write more than I do when I'm not. Its just that playing is even better.

I not sure if I tie playing and listening to music to two different actions in code reading. I might try here, but the real point is that I need to read more code. And, it has to be good code of course. I need to read good code, and a lot of it. If I do my, code will become better and better.

I suppose listening to music is like glancing over code once. You want to see it to know what it does, but you don't really care to understand the thought process behind it. I guess you don't have to do that when you are playing someone else's song, but I usually do. So playing someone else's music is like, reading code really hard. Getting into the head of the coder, like getting into the head of the song writer. You can just glance at code, and just listen to a song. But, if you want to get better, you have to really concentrate on it. The better the song, the better the code, the more work put in, the better the results.

At Oswego I don't think they did enough to say that we should always be reading good code. I think most schools probably don't stress this enough unfortunately. And, even more unfortunately, most of my professional career has been filled with terrible code. Because of those two things, I didn't read much code that was any good. I didn't even know that I should.

When I struggled for a few years after college, it wasn't really obvious what the problem was. I was far and away the most talented guy in my class (I'm not even ashamed to act arrogant about this anymore, its just plain true), yet it didn't seem to translate to professional success. Finally I started reading books. Not so much reading code, but lots and lots of books. Things started looking up.

I still haven't read good code though. Well, not that much of it. I need to read more. I'm certain that when I do my code will improve, maybe even dramatically. So, I plan to attempt to find some books on code reading, potentially this one: http://www.spinellis.gr/codereading/. But, thats obviously not enough. I need choose some good code to read.

What are some good OSS projects to start reading? I read through CruiseControl Java a bit, and it was ok. But it was a little bit boring. I suppose it helps to pick something I'm familiar with. I think the java.util.concurrent that Dr. Lea wrote is the best place to start. It might be Java, which I'm getting sick of, but I'm certain its some of the most well written code there is.

But here is something else important. I'd like to attempt to put together a bunch of code, somehow ordered by increasing difficulty. Why? So I could develop my own college course in code reading. It would be so fun to have a bunch of stuff in a bunch of different languages that gets more and more difficult to read, and have the students have to tell you what it does. And, add features to it. Oh man, what a good course. Its so practical too, thats what most of my development has been (though I wish it wasn't that way). Its been mostly - here is this code base, and I need you to add this feature to it.

I think this is an essential class probably missing from most CS or SE programs. Maybe I'm wrong and just talking out of my ass, but I know it was missing at Oswego, and I consider Oswego to be one of the finest CS schools.

Testability vs. Encapsulation

2007-11-21T08:16:00.000-08:00

I'm always on the side of Testability, but I'd like to hear some other peoples opinions on the subject. I think (in most situations) its totally OK to relax encapsulation in favor of testability, but some people at my work do not. Let me give a rather long example of something I came across that bothered me a bit.

I was trying to test a class - well call it G, with a Logger - LOG , which was declared like this:

static final Logger LOG = Logger.instance();

Later on in G, I found a method shutdown, which called LOG.logAndExit() and logAndExit was final and called System.exit().

G:
public void shutdown(){ LOG.logAndExit( "shutting down" ); }

Logger:
public final void logAndExit( String message ){
System.out.println(message);
System.exit(0);
}

If my tests wanted to test the shutdown method on G, the entire JVM would shutdown which simply shutdown my tests. Brilliant. I had to find some way to Mock or override the LOG variable. But there were several problems with that.

It was private
It was final
It was static
The logAndExit method was final

All of these things make difficult testing. I tried to get around the "private" by writing my PrivateFieldHelper Class. But, as it turns out, you cannot change the accessibility of static final variables at Runtime. It only works for instance fields of all types, and non final static variables. So I was stuck with the LOG object that I had.

Unless of course I relaxed encapsulation and removed the final from LOG. Then I could use my PrivateFieldHelper to set it to a new Logger of some kind. BUT...I still had a problem.
The logAndExit method was final. So even if I extended our Logger class and tried to override logAndExit so that it wouldn't call System.exit(), I still could not do so. Even when I created a Mock Logger object using JMock I had the same problem. It appears that even mock objects can't override final methods.

So once again I decided it was best to relax encapsulation. I removed the final keyword from Logger logAndExit, and created a new class - SafeLog - that overrode the logAndExit method. I used my PrivateFieldHelper to set the (now only static private) LOG field on G, and I was able to safely call the shutdown method from my test code.

What a pain.

I understand that you can go way too far on this. Some people say you should never relax encapsulation for testability, because in doing so you relax intent and readability which later creates more of a maintenance problem. In some ways I do agree with this. On public API's and Libraries you most certainly will have higher maintenance costs. But, I do think removing a final here and a final there is ok, especially if its documented. I also think removing private in favor of default (package private) is ok.

What do you think? Does anyone know of any good articles or books explaining the trade-offs?

God this post is about to get long....

Some say you shouldn't relax private for package private, and all testing should be done through public methods. This is another one I just don't agree with. Lets say you have a reasonably complicated class that only exposes one public method. People reading the class later on might not know what inputs are valid for and what outputs are expected for each of the private methods in the class. You certainly can, and should get 100% code coverage through testing public methods, but it still might not be immediately obvious to someone reading the code later on what those private methods are doing.

Testing private (or package private) methods extensively should make it immediately obvious. Once again, What do you think? Does anyone know of any good articles or books explaining the trade-offs?

I think there can and should be things built into the languages themselves to expose hidden members to testing. Something like a test keyword. Or like JSR 294, superpackages, which define what classes in a package are accessible, and to whom. If it things like this were built right into the language, exposing members to testing, then we wouldn't even be having these debates.

How would it work? Maybe a lot like Generics. All the type information is removed at compile time, and so could any test availability information. You could turn this off. You could say, produce a jar for testing, and produce a jar for delivery. Its not that hard. Just ideas...You have any?

CPU Simulator Library in Progress

2007-11-16T19:22:00.000-08:00

I've been working on a lot of stuff lately and not writing. For that I apologize. I want to keep everyone updated on what I'm doing, but mostly I want to keep myself update for tracking progress and what not.

I'm still wanting to design languages, write compilers, write IDE thingies, and all of that. If you recall, I decided that in order to do that I should become a compiler master. In reading a lot about compilers I decided I should take yet another step back to refresh my memory on Computer Architecture.

So I've been reading about that a LOT. Really low level, as low as possible. When I say as low as possible I even mean Quantum Physics. But, I don't intend to become a master in Quantum Physics. Its so fascinating but it also really almost drove me to insanity about 6 years ago. A simple refresher was all I needed.

After that I read a bunch about the history of computers, mixed in with some history of philosophy, and mathematics. All really great stuff. Once again I don't intend to become an expert in it but I want solid foundations in all this stuff, which I feel I don't quite have. I'm close.

So heres where the fun part begins. I started writing this cool little CPU simulator in Java. I don't have much yet but I'll keep the world informed. What I plan to do is - write classes that represent pretty much everything you'll find in a computer hardware. So far I have a MemoryModule class and things like that. You can imagine this pretty easily.

We can start with a Computer class which has CPU, Memory, IO, and a Bus. We can then break the CPU down into ControlUnit, ALU, Registers, and maybe Connections. The ControlUnit can be broken down further into SequencingLogic, Registers, Decoders, ControlMemory, etc...

This process of drilling down can probably go down to the atomic level. I'm not sure how low I'd go, where I'd draw the line. But the point is by doing all this, by actually writing the code, ensures that I understand each part. I could take some parts down further than others, and in doing so I'd learn more about that component. This is fine. I probably don't need to know things down to the atomic level on say, video. But going down to FullAdders and HalfAdders in the ALU, or even down to LogicGates is probably a useful thing to do.

Maybe I can invent my own instruction set for my "Hardware", or reuse an existing one. Either way, once all of this is done it would be nice to write a little OperatingSystem class that makes use of that instruction set. I would learn a lot in doing so I imagine. Then once my OperatingSystem is in a reasonable state (I don't have any idea what that would look like yet), I could attempt to write a little compiler that compiles some random language down to an Assembly Language that runs on my hardware.

This is a long way off but I think its a damn good goal. Yes its reproducing things that people have done 50 years ago in a way that most certainly won't be reusable, but whatever, it will get me towards my goal of language writing.

PrivateFieldHelper Class

2007-11-16T17:00:00.000-08:00

Heres a little class I wrote to set private fields. I plan to use it a little for testing, but only when I'm backed into a corner, and can't change code otherwise.


/**
 * 
 * @author Josh Cough
 * 
 */
public class PrivateFieldHelperImpl implements PrivateFieldHelper {

 Class clazz;

 /**
  * 
  * @param c
  */
 public PrivateFieldHelperImpl(Class c) { this.clazz = c; }

 /*
  * (non-Javadoc)
  * @see com.joshcough.reflect.PrivateFieldHelper#setStaticFieldValue(java.lang.String, java.lang.Object)
  */
 public void setStaticFieldValue(String fieldName, Object newValue)
   throws IllegalArgumentException, NoSuchFieldException {
  setPrivateFieldValue(findPrivateStaticField(fieldName), null, newValue);
 }

 /*
  * (non-Javadoc)
  * @see com.joshcough.reflect.PrivateFieldHelper#getStaticFieldValue(java.lang.String)
  */
 public Object getStaticFieldValue(String fieldName) 
  throws NoSuchFieldException, IllegalArgumentException  {
  return getPrivateFieldValue(null, findPrivateStaticField(fieldName));
 }

 /*
  * (non-Javadoc)
  * @see com.joshcough.reflect.PrivateFieldHelper#getInstanceFieldValue(java.lang.Object, java.lang.String)
  */
 public Object getInstanceFieldValue(Object instance, String fieldName) 
  throws NoSuchFieldException, IllegalArgumentException  {
  return getPrivateFieldValue(instance, findPrivateInstanceField(fieldName));
 }
 
 /*
  * (non-Javadoc)
  * @see com.joshcough.reflect.PrivateFieldHelper#setInstanceFieldValue(java.lang.Object, java.lang.String, java.lang.Object)
  */
 public void setInstanceFieldValue(Object instance, String fieldName, Object newValue)
   throws IllegalArgumentException, NoSuchFieldException {
  setPrivateFieldValue(findPrivateInstanceField(fieldName), instance, newValue);
 }
 
 /**
  * 
  * @param f
  * @return
  * @throws 
  */
 private Object getPrivateFieldValue(Object instance, Field f) {
  f.setAccessible(true);
  Object o;
  try {
   o = f.get(instance);
  }  catch (IllegalAccessException e) {
   throw new PrivateFieldException(e);
  }
  f.setAccessible(false);
  return o;
 }

 /**
  * 
  * @param f
  * @param newValue
  * @throws 
  */
 private void setPrivateFieldValue(Field f, Object instance, Object newValue){
  f.setAccessible(true);
  try {
   f.set(instance, newValue);
  } catch (IllegalAccessException e) {
   throw new PrivateFieldException(e);
  }
  f.setAccessible(false);
 }

 /**
  * 
  * @param fieldName
  * @return
  * @throws NoSuchFieldException
  */
 private Field findPrivateStaticField(String fieldName) throws NoSuchFieldException {
  for (Field f : clazz.getDeclaredFields()) {
   if (f.getName().equals(fieldName)) {
    if (Modifier.isStatic(f.getModifiers()))
     return f;
   }
  }
  throw new NoSuchFieldException();
 }

 /**
  * 
  * @param fieldName
  * @return
  * @throws NoSuchFieldException
  */
 private Field findPrivateInstanceField(String fieldName) throws NoSuchFieldException {
  for (Field f : clazz.getDeclaredFields()) {
   if (f.getName().equals(fieldName)) {
    if (! Modifier.isStatic(f.getModifiers()))
     return f;
   }
  }
  throw new NoSuchFieldException();
 }
 
}

Cruise Control Remote Management API

2007-11-16T07:38:00.000-08:00

I've never contributed to an OSS project before. Why that is I'm not quite sure. Looking through the CruiseControl Java code its pretty clear to me that I have the skills. I understand the code and I understand ways that I could refactor and improve it. I understand that I probably had those skills years ago. So why I haven't is beyond me; maybe I just never had the confidence.

Anyway, I've finally submitted something. I wrote a CruiseControl Remote Management library that wraps the exposed JMX attributes and operations for a server and its projects. You can do nice things like getting a reference to a server, getting all its projects, force builds on projects, set labels on projects, lots of nice stuff. Here's a simple example that forces a build on all projects:

CruiseServer server = new Server("localhost");
List projects = server.getProjects();
for( CruiseProject p: projects ){ p.forceBuild(); }

You could do nice things with Build Pipelining like trigger builds in other CruiseControl instances on different servers after a project on your server builds. Indeed, thats actually what I've done.

I think that this code could be used to clean up a lot of the code in their current tree. Maybe I'm wrong, or maybe they already have something like this, but I didn't see it.

Hopefully they will take this and add it in. Maybe they will ask me to add it in. Maybe I'll get to refactor a bunch of their Dashboard code. I'm almost certain it would be cleaner using this.

We'll see what happens.

Closures

2007-10-30T19:58:00.000-07:00

Can anyone tell me how closures are implemented?

Scala has closures, and it compiles to Java bytecode, but, Java doesn't have closures. This is not to say that it can't be done, of course. I'm sure the implementation is probably not that hard. I'm just really curious to know how its done... I could go look at the source code for the Scala compiler of course. But I have been working on a number of other things.

I wrote a library for remote management of CruiseControl that seems to be much easier to use than the one they are using in the new Dashboard. I'm going to try to get that submitted here shortly. I'm starting to feel pretty confident in my development skills. Finally. I'm also starting to feel confident in my code reading skills too. I was able to look through the CC Java code with ease. Of course it helps that its mostly nice clean code, but still, I'm doing well.

Well enough, I suppose, that I could figure out how closures are implemented. And, since no one reads my blog anyway, I think I'm on my own.

But Thats How It Was When I Got Here

2007-10-18T18:24:00.000-07:00

Companies typically let their build system go to shit.

Why is that? Does anyone have an answer to this? The first thing I ever do on new projects is make sure I have a consistent build process. ThoughtWorks was the same way. The first thing I look at when joining a new company is the build process, and how to fix it. Why don't most companies do this themselves? I have some ideas, here they are:

They don't know how.
They somehow (wrongly) think its not as valuable as developing the next features
They get comfortable with the fact that it takes an hour to build, because it works
They suffer from "But Thats How It Was When I Got Here" syndrome

All of these are BAD BAD BAD reasons, and all make me very offended. Those might not be the only reasons, and they might not be the best reasons, but regardless, I'm going to tear them apart. My intention is not to make my coworkers feel bad, but to wake them up to the reality that theres a lot of new technology out there that they need to be learning and leveraging.

They don't know how.

If you don't know how to do something entirely modern, then you need to start learning. Everyone knows this, but so few people do it. Why? (Topic for a whole new blog posting). If you don't do it you're going to be passed by. This will occur first on the individual level, people will start to pass you making more money and you'll wonder why. Well, knowledge is why.

Worse though, if this is somehow your corporate culture, not learning new technology, eventually your whole company is going to stagnate. I refuse to let this happen at my group. Fortunately we have some great people who are eager to learn.

They somehow (wrongly) think its not as valuable as developing the next features

If you think its not valuable, you're dead wrong. If you don't have a repeatable build process someone will end up making a mistake and you'll deliver something broken to a client. Maybe that never happens, but you WILL end up slowly adding to your awful build process until you get something that is a total pile of nonsense. With this pile, any change takes days or weeks to figure out. You have to figure out all the side effects, you have to somehow verify that a updated build process produces the same results as the old process.

They get comfortable with the fact that it takes an hour to build, because it works

Believe it or not, if you are comfortable with your build process this is actually a sign that something might be wrong. I am never comfortable with my build process. I'm always tweaking it, trying to make it run faster, trying to remove duplication from it, trying this trying that...I think a good build should be less than 5 minutes. Some people say ten. I don't agree. If you have an hour build, you're likely doing a bunch of manual steps and will run into the problems I pointed out in the last step. If you have an hour long build and its completely automated then you have other issues that aren't quite as serious, but are still very bad.

But Thats How It Was When I Got Here

This one is troublesome to me. I HATE legacy software. I feel like. I don't know, some kind of Vigilante on a mission to KILL it. Unfortunately, even I find myself saying, "But thats how it was when I got here" from time to time. This is not a good excuse. If you're saying that now, you'll probably go on saying this until you end up in a situation like the last two items. This is almost an excuse for all the other items rolled up into one. Its like saying, "Yeah I know its bad, but what can you do?" And on top of that, its like, a way out, a way of saying, "I'm not going to deal with that problem." Well, guess what? You are going to deal with it, the hard way.

So is this all avoidable? Of course. "But how?" One simple way, READ. DAMN YOU. READ MORE. Thats it. Really. Just read what people are writing and you'll learn how to do things right. Now, if only we could get everyone to read. I smell a post.

Agitar Examples

2007-10-18T06:13:00.000-07:00

I finally have a chance to post some examples of code generated by Agitar. I promised them in comments to the original post, but it turns out this is easier. First, I'll give a little background on the code that I wanted to test, and then I'll show the tests generated by Agitar. This example is designed to show the readability of Agitar. If a test fails after a change and its difficult to read, what approach should a developer take - read the test and see why it failed, or regenerate the test?

I wrote a simple interface for returning all the files under a directory:

(By the way I lost all my formatting and I apologize. Formatting on Blogger is a PITA.)

public interface ListFilesStrategy {
public List listFiles(File dir);
}

I have a two classes implementing this interface, RecursiveListFilesStrategy and NonRecursiveListFilesStrategy, which both extend AbstractListFilesStrategy.Here are the listings for AbstractListFilesStrategy and NonRecursiveListFilesStrategy:

public abstract class AbstractListFilesStrategy {

public void assertFileIsDirectory(File dir) {
if( dir == null )
throw new IllegalArgumentException("directory is null");

if( ! dir.isDirectory() )
throw new IllegalArgumentException("file is not directory");
}

}

public class NonRecursiveListFilesStrategy extends AbstractListFilesStrategy
implements ListFilesStrategy{

public List listFiles(File dir){
assertFileIsDirectory(dir);

List files = new ArrayList();

List directories = new ArrayList();
directories.add(dir);

while(! directories.isEmpty()){
File currentDir = directories.remove(0);
for( File f: currentDir.listFiles()){
if (f.isFile()) files.add(f);
else directories.add(f);
}
}
return files;
}
}

Now the test Agitar generated that was difficult to read. This test tested the listFiles method on my NonRecursiveListFilesStrategy:

public void testListFilesWithAggressiveMocks1() throws Throwable {
NonRecursiveListFilesStrategy nonRecursiveListFilesStrategy = new NonRecursiveListFilesStrategy();
File file = (File) Mockingbird.getProxyObject(File.class);
File file2 = (File) Mockingbird.getProxyObject(File.class);
File[] files = new File[0];
File file3 = (File) Mockingbird.getProxyObject(File.class);
File[] files2 = new File[2];
File file4 = (File) Mockingbird.getProxyObject(File.class);
File file5 = (File) Mockingbird.getProxyObject(File.class);
files2[0] = file4;
files2[1] = file5;
Mockingbird.enterRecordingMode();
Boolean boolean2 = Boolean.TRUE;
Mockingbird.setReturnValue(false, file, "isDirectory", "()boolean", new Object[] {}, boolean2, 1);
ArrayList arrayList = (ArrayList) Mockingbird.getProxyObject(ArrayList.class);
Mockingbird.replaceObjectForRecording(ArrayList.class, "()", arrayList);
ArrayList arrayList2 = (ArrayList) Mockingbird.getProxyObject(ArrayList.class);
Mockingbird.replaceObjectForRecording(ArrayList.class, "()", arrayList2);
Boolean boolean3 = Boolean.FALSE;
Mockingbird.setReturnValue(false, arrayList2, "add", "(java.lang.Object)boolean", new Object[] {file}, boolean3, 1);
Mockingbird.setReturnValue(arrayList2.isEmpty(), false);
Mockingbird.setReturnValue(arrayList2.remove(0), file2);
Mockingbird.setReturnValue(false, file2, "listFiles", "()java.io.File[]", new Object[] {}, files, 1);
Mockingbird.setReturnValue(arrayList2.isEmpty(), false);
Mockingbird.setReturnValue(arrayList2.remove(0), file3);
Mockingbird.setReturnValue(false, file3, "listFiles", "()java.io.File[]", new Object[] {}, files2, 1);
Mockingbird.setReturnValue(false, file4, "isFile", "()boolean", boolean2, 1);
Mockingbird.setReturnValue(false, arrayList, "add", "(java.lang.Object)boolean", boolean3, 1);
Mockingbird.setReturnValue(false, file5, "isFile", "()boolean", boolean3, 1);
Mockingbird.setReturnValue(false, arrayList2, "add", "(java.lang.Object)boolean", boolean3, 1);
Mockingbird.setReturnValue(arrayList2.isEmpty(), true);
Mockingbird.enterTestMode(NonRecursiveListFilesStrategy.class);
List result = nonRecursiveListFilesStrategy.listFiles(file);
assertNotNull("result", result);
}

This is certainly difficult to read. I'm pretty sure I could explain what its doing, but I'm more well read in testing and mocks than most developers. There are a few things they could do to clean it up however. They could try to be more in line with Behavior Driven Development and they have a few options in doing so. The method doesn't have an intent revealing name, I know what method its testing, but I don't know exactly what its doing. They could put in "given, when, then comments". The could use the extract method refactoring to seperate out the setup, the action, and the assertions, but maybe at least the setup portion.

All these things could be done, but even so there is a lot of setup happening here, and Most developers aren't ready, or aren't willing to read through it, and will likely start to ignore Agitar errors.

Now, I was told by Barry at Agitar that I could put in a test helper class, which would basically provide the setup portion of the test, and then it would generate more meaningful results. Here is an example:

public class FileTestHelper implements ScopedTestHelper {

public static File createFile() {
return new File("./src/main");
}
}

Should result in something like this …

public void testListFiles() throws Throwable {
ArrayList result = (ArrayList) new NonRecursiveListFilesStrategy().listFiles(FileTestHelper.createFile());
assertEquals("result.size()", 5, result.size());
}

Indeed, I could do something like this. But, there is a big problem with this. We have 5000+ classes that we want to generate tests for! How do we know which tests are meaningful, which ones need test helpers, yada yada?

I do promise more examples of simple methods that don't seem to be giving meaninful results. Mostly just checking to make sure methods catch NullPointerException. I do think the product will work wonderfully for green development, but will likely be ignored during legacy developement. Please let me know your thoughts.

IDE's vs vi

2007-10-14T17:42:00.000-07:00

I just told my friend that instant IDE support for new languages is the place to be (I truly believe this can happen). In response he told me, "I love vi."

I know vi, and I can get around in it OK, but I'm not a hardcore vi guy. I know there are some things you can do in vi that are really nice and allow you to do some things very quickly and powerfully. But, I don't know what they are. The real question here is, can vi do things that modern IDE's cant do? Can someone explain to me this?

I do think that vi is ancient technology, and I'm sure thats old news anyway. I don't know very many people who use vi or emacs anymore. I'm sure a lot of people would look at my friend funny for that comment. But I'm a little different. I'm curious.

What features do retired editors have that modern IDE's lack?

Questions on Blogger

2007-10-14T06:26:00.000-07:00

So I like the look and feel of Blogger, but I have some problems with it.

I really need to be able to upload files as attachments to my blog.

Is there a way to do this?
Is there another site that allows you to do this?
If I host my own site can is there on OSS blog that I can put up that allows me to upload files?
Should I just use a wiki?
Should I just host my own site and link to files from Blogger to my site?

Whats the best way to go about all this? Seems like the easiest is to go with the last option. But, I don't want to host at home anymore. Does anyone know the easiest way to do hosting these days? I used to host at home a few years back but I'm now out of touch with hosting.