tag:blogger.com,1999:blog-349279532024-02-28T00:48:59.139-08:00Jack Cough on SoftwareThoughts about Languages.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.comBlogger93125tag:blogger.com,1999:blog-34927953.post-60577487850854383632011-07-16T16:18:00.001-07:002011-07-21T08:54:20.762-07:00Tail Calls, Tail Recursion, TCOI'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.<br /><br /><div><ul><li>Tail Call - When the last thing a function does is call another function, and then immediately returns the result of that call.</li><li>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.</li><li>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.)</li></ul><div><h4><span class="Apple-style-span" style="font-weight: bold; "><br /></span></h4><h4><span class="Apple-style-span" style="font-weight: bold; ">Regular Function Calls</span></h4></div></div><div><br /></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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." </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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). </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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').</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><h4><span class="Apple-style-span"><br /></span></h4><h4><span class="Apple-style-span">Tail Calls</span></h4></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Here is where we really demonstrate the difference between a regular function call and a tail call. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Those are tail calls. Remember the definition: "</span>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.</div><div><br /></div><div>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. </div><div><br /></div><div>Before I talk about TCO, let's talk about the <i>need </i>for TCO. </div><div><br /></div><div><h4><span class="Apple-style-span"><br /></span></h4><h4><span class="Apple-style-span">The Problem</span></h4></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Ok, fine. That might work. I guess it depends on how big your stack is. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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).</span></div><div><br /></div><div><h4><span class="Apple-style-span"><br /></span></h4><h4><span class="Apple-style-span">Tail Call Optimization</span></h4><span class="Apple-style-span"><div><span class="Apple-style-span"><br /></span></div>Okay. Now is the part where I change the story to describe TCO, and how it works. It's actually very easy.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><span class="Apple-style-span">Mr. Butter turns to Mr. Popper and says the same thing: </span><span class="Apple-style-span"> "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. </span></span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Mr. Popper gets a bucket of popcorn and simply hands it to Mr. Hungry Man. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">And that folks, is the end of the story. Case closed!</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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).</span></div><div><br /></div><div><h4><span class="Apple-style-span"><br /></span></h4><h4><span class="Apple-style-span">Conclusion</span></h4></div><div><br /></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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:</span></div><div><ul><li><span class="Apple-style-span">How the Scala compiler can turn tail recursive functions into while loops, and why it can't do so with non-final functions.</span></li><li><span class="Apple-style-span">What @tailrec does.</span></li><li><span class="Apple-style-span"><span class="Apple-style-span">Mutually recursive functions, trampolining and </span><span class="Apple-style-span" style="font-family: monospace; white-space: pre; ">scala.util.control.TailCalls.</span></span></li></ul></div><div><span class="Apple-style-span">I also think I could extend this story to explain continuations. Maybe someday I'll get the chance to do that as well.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><br /></span></div><div><h4><span class="Apple-style-span">References</span></h4></div><div><span class="Apple-style-span"><br /></span></div><div><ul><li>Lambda: the ultimate goto</li></ul><div><a href="http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf"> http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf</a></div><div><ul><li>Fortress Blog - ObjectOrientedTailRecursion</li></ul></div><div><a href="http://tinyurl.com/yjbgks3"> http://tinyurl.com/yjbgks3</a></div><div><ul><li>Rich Dougherty - Tail Calls, Tail Rec, Trampolines</li></ul></div><div><a href="http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html"> http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html</a></div><div><ul><li>John Rose - Tail Calls in the JVM</li></ul></div><div><a href="http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm"> http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm</a></div><div><ul><li>Matthias Felleisen - A Tail-Recursive Machine with Stack Inspection</li></ul></div><div><a href="http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf"> http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf</a></div><div><ul><li>Stack Overflow - @tailrec and non-final methods</li></ul><a href="http://bit.ly/stacko-tailrec">http://bit.ly/stacko-tailrec</a></div></div><div><br /></div>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com7tag:blogger.com,1999:blog-34927953.post-68352025488028624802010-12-14T14:08:00.000-08:002010-12-15T07:09:35.152-08:00Code Styles and ReadabilityToday 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.<br /><br />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.<br /><br />Before we begin, we need to understand a few things about the system.<br />One could imagine these simple classes:<br /><pre><br />case class Procedure_V1(name: String)<br />case class Activation_V1(procedure: Procedure, parent: Activation)<br /></pre><br />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:<br /><pre><br />case class Command_V2(name:String)<br />case class Procedure_V2(name: String, commands: List[Command])<br />case class Activation_V2(procedure: Procedure, parent: Activation)<br /></pre><br />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.<br /><br />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:<br /><pre><br />case class Command(name:String, callsOtherCode: Boolean)<br />case class Procedure(name: String, commands: List[Command])<br />case class Activation(procedure: Procedure, parent: Activation, returnAddress:Int)<br /></pre><br />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.<br /><pre><br />def callStack_V1(act: Activation): List[String] = {<br /> val parentCommandMaybe: Option[String] = Option(act.parent).flatMap(p => {<br /> val c = p.procedure.commands(act.returnAddress)<br /> if(c.callsOtherCode) Some(c.name) else None<br /> })<br /> List(Some(act.procedure.name), parentCommandMaybe).flatten :::<br /> callStack_V1(act.parent)<br />}<br /></pre><br />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.<br /><pre><br />def callStack_V2(act: Activation): List[String] = {<br /> val parentCommandMaybe: Option[String] = Option(act.parent).flatMap(p => {<br /> val c = p.procedure.commands(act.returnAddress)<br /> if(c.callsOtherCode) Some(c.name) else None<br /> })<br /> act.procedure.name :: parentCommandMaybe.toList ::: callStack_V1(act.parent)<br />}<br /></pre><br />Only slightly better. Maybe if we remove the recursion things will be nicer.<br /><pre><br />def callStack_V3(act: Activation): List[String] = {<br /> Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList.flatMap { a =><br /> val proc = act.procedure.name<br /> val parentCommandMaybe: Option[String] = Option(a.parent).flatMap(p => {<br /> val c = p.procedure.commands(a.returnAddress)<br /> if (c.callsOtherCode) Some(c.name) else None<br /> })<br /> act.procedure.name :: parentCommandMaybe.toList<br /> }<br />}<br /></pre><br />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.<br /><pre><br />def unfold(act: Activation) =<br /> Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList<br /><br />def callStack_V4(act: Activation): List[String] = {<br /> unfold(act).flatMap { a =><br /> val parentCommandMaybe: Option[String] = Option(a.parent).flatMap(p => {<br /> val c = p.procedure.commands(a.returnAddress)<br /> if (c.callsOtherCode) Some(c.name) else None<br /> })<br /> act.procedure.name :: parentCommandMaybe.toList<br /> }<br />}<br /></pre><br />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.<br /><pre><br />def callStackImperative(act: Activation): Seq[String] = {<br /> val buf = collection.mutable.ListBuffer[String]()<br /> for(a <- unfold(act)) {<br /> buf += a.procedure.name<br /> if (a.parent != null) {<br /> val c = a.parent.procedure.commands(a.returnAddress)<br /> if (c.callsOtherCode) buf += c.name<br /> }<br /> }<br /> buf<br />}<br /></pre><br />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.<br /><br />I still thought I could do better, so I continued. This time with a Racket friend.<br /><pre><br />def callStackSchemer(act: Activation): List[String] = {<br /> def callStackInner(act: Activation): List[String] = {<br /> if (act == null) Nil<br /> else {<br /> val rest = callStackInner(act.parent)<br /> def parCmd = act.parent.procedure.commands(act.returnAddress)<br /> act.procedure.name ::<br /> (if (act.parent != null && parCmd.callsOtherCode) parCmd.name :: rest<br /> else rest)<br /> }<br /> }<br /> callStackInner(act)<br />}<br /></pre><br />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.<br /><br />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..<br /><pre><br />def parentCommandMaybe_V1(act: Activation): Option[String] =<br /> Option(act.parent).flatMap(p => {<br /> val c = p.procedure.commands(act.returnAddress)<br /> if (c.callsOtherCode) Some(c.name) else None<br /> })<br /></pre><br />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.<br /><pre><br />def parentCommandMaybe_V2(act: Activation): Option[String] =<br /> if(act.parent == null) None<br /> else{<br /> val command = act.parent.procedure.commands(act.returnAddress)<br /> if(command.callsOtherCode) Some(command.name) else None<br /> }<br /><br />def parentCommandMaybe_V3(act: Activation): Option[String] =<br /> for{p <- Option(act.parent)<br /> c = p.procedure.commands(act.returnAddress)<br /> if c.callsOtherCode}<br /> yield c.name<br /></pre><br />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.<br /><br />Better solutions to this are most welcome.<br /><br />Now that we've pulled that out, we can rewrite our function.<br /><pre><br />def callStack_V7(act: Activation): List[String] = {<br /> unfold(act).flatMap { a => <br /> act.procedure.name :: parentCommandMaybe_V3(act).toList<br /> }<br />}<br /></pre><br />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.<br /><pre><br />def callStack_V8(act: Activation): List[String] = {<br /> def unfold(act: Activation) =<br /> Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList<br /> def parentCommandMaybe_V3(act: Activation): Option[String] =<br /> for{p <- Option(act.parent)<br /> c = p.procedure.commands(act.returnAddress)<br /> if c.callsOtherCode}<br /> yield c.name<br /> unfold(act).flatMap { a => <br /> a.procedure.name :: parentCommandMaybe(a).toList<br /> }<br />}<br /></pre><br />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.<br /><pre><br />/**<br /> * Return a List representing the call stack.<br /> * The list includes procedure names and any commands<br /> * that call other code.<br /> * @param act - the final call on the stack.<br /> **/<br />def callStack(act: Activation): List[String] = {<br /> // unfold turns an activation into<br /> // List(act, act.parent, act.parent.parent ... )<br /> def unfold(act: Activation) =<br /> Iterator.iterate(act)(_.parent).takeWhile(_ != null).toList<br /> // if an activations parent is executing a command that can trigger<br /> // other code, it also needs to be added to the stack trace.<br /> def parentCommandMaybe(act: Activation): Option[String] =<br /> for{p <- Option(act.parent)<br /> c = p.procedure.commands(act.returnAddress)<br /> if c.callsOtherCode}<br /> yield c.name<br /> // flatMap because each activation can result in 1 or 2 entries<br /> unfold(act).flatMap { a => <br /> a.procedure.name :: parentCommandMaybe(a).toList<br /> }<br />}<br /></pre><br /><br />If you can write this better, please do. Send it to me and I'll learn something.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-88208748240778242512010-11-27T19:12:00.001-08:002010-11-27T21:34:14.636-08:00App Inventor Review (plus some functional programming)<div style="text-align: center;"><span class="Apple-style-span"><u><br /></u></span></div>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. <div><br /></div><div>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.<br /><br />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 <a href="http://video.google.com/videoplay?docid=-8860158196198824415#">Growing a Language</a>. <div><br /></div><div>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. </div><div><br /></div><div>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. </div><div><br /></div><div>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, <i><b>every time</b></i> you need to name something, it becomes a global variable.</div><div><ul><li>When you need a temp, create a global.</li><li>Globals are event created for every procedure argument. </li></ul><div>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:</div><div><br /></div><div></div></div><blockquote><div><div>def head[A](aList:List[A]): A = ...</div></div><div>def tail[A](anotherList:List[A]): List[A] = ...</div><div>def toString(yetAnotherList:List[_]) = ...</div></blockquote><div></div><div><br /></div><div>And imagine further that these names followed you around wherever you go. </div><div><br /></div><div>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 <a href="http://groups.google.com/group/appinventor/browse_thread/thread/ef57034a9b075f57">this thread</a>, <blockquote><span class="Apple-style-span" style="font-size: medium;">"<span class="Apple-style-span" style="font-family: arial, sans-serif; ">We're planning on adding local variables (no ETA). We agree that these are </span><span class="Apple-style-span" style="font-family: arial, sans-serif; ">important for teaching programming."</span></span></blockquote></div>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.)<div><br /></div><div>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.<div><br /></div><div>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:</div></div><div><br /></div><div><span class="Apple-style-span" style="color: rgb(0, 0, 238); -webkit-text-decorations-in-effect: underline; "><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBz3IoxRUHvBVsZ3XdY8jY8A3Yv9CTFB2Gz6pehrc4rieS4a8XSkRIR3vKrVbCwYNgDcGgym_LBGc0OM4WP8Fk2zRBQIavU5lTPhi4SI_wWNSA8jk8YwK9sDK1t3VSANwnzXrRkA/s400/Screen+shot+2010-11-27+at+9.57.02+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544450037722656994" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 398px; height: 225px; " /></span></div><div><span class="Apple-style-span" style="font-size: medium;"><br /></span></div><div><span class="Apple-style-span" style="font-size: medium;">The first time I wrote the string_to_list function, I wrote it using globals in typical imperative style. Here it is:</span></div><div><span class="Apple-style-span" style="font-size: medium;"><br /></span></div><div><span class="Apple-style-span" style="color: rgb(0, 0, 238); -webkit-text-decorations-in-effect: underline; "><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-xukwkeMNtaoFvDqd7pO3YKVq40QKWmibMpia_autlxACOSdvCV2dSxG-sIl1Vk-MERhRqhQnETr0W3Jn6FSqvHqGBzDEcwLV_REjlf1A2JTVFYh_ueeiGGO86O_ClftadJH4Mw/s400/Screen+shot+2010-11-27+at+9.56.51+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544451133806002322" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 346px; " /></span></div><div><br /></div><div>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:</div><div><br /></div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiB2V9wGmJ3BZjBZJnqSwseD69FxXOi5jY1IQd0gZbap5j8VO2WYbO1jjiyfoUKFmpSgQVfD6Vn74-Qql6o6XCkmM9kahQHSx0vk5s2bQIGaObKGabOXUp24Az55Ityrt8KNtuG-w/s1600/Screen+shot+2010-11-27+at+10.11.11+PM.png"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiB2V9wGmJ3BZjBZJnqSwseD69FxXOi5jY1IQd0gZbap5j8VO2WYbO1jjiyfoUKFmpSgQVfD6Vn74-Qql6o6XCkmM9kahQHSx0vk5s2bQIGaObKGabOXUp24Az55Ityrt8KNtuG-w/s400/Screen+shot+2010-11-27+at+10.11.11+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544452174145388002" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 327px; " /></a></div><div><br /></div><div>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.</div><div><br /></div><div>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. </div><div><br /></div><div>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. </div><div><br /></div><div>Here are head and tail:</div><div><br /></div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEirndHj_tFPOMDVAkcpKQAk48lX8wTkrDwa8EbquYyljVrQ1d3mGC8jUzt5-YmCzYSewV2AJ7njR5XmUr_Y5yRO-vdBRD9-Xwtutlr-ADZXwFF-CD-PrmSyohVlY7TGBIZzGoG0Kg/s1600/Screen+shot+2010-11-27+at+10.34.19+PM.png"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEirndHj_tFPOMDVAkcpKQAk48lX8wTkrDwa8EbquYyljVrQ1d3mGC8jUzt5-YmCzYSewV2AJ7njR5XmUr_Y5yRO-vdBRD9-Xwtutlr-ADZXwFF-CD-PrmSyohVlY7TGBIZzGoG0Kg/s400/Screen+shot+2010-11-27+at+10.34.19+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544454975848676978" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 384px; height: 400px; " /></a></div><div><br /></div><div>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. </div><div><br /></div><div>Zip suffered from problems already discussed:</div><div><br /></div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwdyptD-fQbobZ9o2932ovFER5MPYvgs6mer3FZ09vr_grrDswt_R4tzqxPWq4ml9Y5PrFqhrYYXinDO_pM2gaVs8ETW8NZrgsRO6IpFhJsAqQ2OjCWxbQHWUz_cBTANvkod108g/s1600/Screen+shot+2010-11-27+at+10.37.41+PM.png"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwdyptD-fQbobZ9o2932ovFER5MPYvgs6mer3FZ09vr_grrDswt_R4tzqxPWq4ml9Y5PrFqhrYYXinDO_pM2gaVs8ETW8NZrgsRO6IpFhJsAqQ2OjCWxbQHWUz_cBTANvkod108g/s400/Screen+shot+2010-11-27+at+10.37.41+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544455779179437346" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 381px; " /></a></div><div><br /></div><div>Unzip also demonstrates nothing new:</div><div><br /></div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipplIkFPTbjzmIAAZoquzHKCv6AJPa2mtChCg-8Rb2OA58hPlCKCGi2cpLQSZ1UKw2u92e9t_Audv0jlN6Ze8SDHqDZpAMzh_qZCHG3H38VqPcJcK3I74GvpQDhSCV0lCcojSsFA/s1600/Screen+shot+2010-11-27+at+10.39.24+PM.png"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipplIkFPTbjzmIAAZoquzHKCv6AJPa2mtChCg-8Rb2OA58hPlCKCGi2cpLQSZ1UKw2u92e9t_Audv0jlN6Ze8SDHqDZpAMzh_qZCHG3H38VqPcJcK3I74GvpQDhSCV0lCcojSsFA/s400/Screen+shot+2010-11-27+at+10.39.24+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544456143529577250" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 325px; height: 400px; " /></a></div><div><br /></div><div>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:</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQ6uLkhfYbPv7n4ALKk3OyxcJwP2jgVZKXt4QhYBRzmm5uDq_NwBxgljEYk2c29w1q0k19jzzeWVQXVK-ERW8y6nw0_mxiBCB5KY45NTdEmbJ_B_0e82LPybY9Hc_MDpWADfA-_g/s1600/Screen+shot+2010-11-27+at+10.56.18+PM.png"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQ6uLkhfYbPv7n4ALKk3OyxcJwP2jgVZKXt4QhYBRzmm5uDq_NwBxgljEYk2c29w1q0k19jzzeWVQXVK-ERW8y6nw0_mxiBCB5KY45NTdEmbJ_B_0e82LPybY9Hc_MDpWADfA-_g/s400/Screen+shot+2010-11-27+at+10.56.18+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544460464203736562" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 369px; " /></a></div><div><br /></div><div>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:</div><div><br /></div><div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj57iOXo5Gzc4oigqG3OzmtEAN2S3thCvaF35sj_yF6onvc31S5N0coF9xQmQ12cZYsYaNHFHHIUA3_EIQf6VY_g4jnG7Y1-eey4KUtZJF0Ho0DTievq-uOW8LI8NFBIgzUFnA2QA/s1600/Screen+shot+2010-11-27+at+11.02.52+PM.png"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj57iOXo5Gzc4oigqG3OzmtEAN2S3thCvaF35sj_yF6onvc31S5N0coF9xQmQ12cZYsYaNHFHHIUA3_EIQf6VY_g4jnG7Y1-eey4KUtZJF0Ho0DTievq-uOW8LI8NFBIgzUFnA2QA/s400/Screen+shot+2010-11-27+at+11.02.52+PM.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5544462411402099234" style="display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; text-align: center; cursor: pointer; width: 400px; height: 389px; " /></a></div><div><br /></div><div>Some other remarks and random comments:</div><div><ul><li>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.</li><li>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.</li><li>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.</li><li>Sometimes it would say there was an error in a procedure, but it wouldnt tell me what the error was. </li><li>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.</li><li>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.</li><li>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?</li><li>I was pretty easily able to find things in the documentation the few times that I needed to look things up. That was nice. </li></ul></div><div>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. </div><div><br /></div><div><br /></div></div>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-23922089014395160752010-02-24T09:01:00.000-08:002010-03-14T09:55:58.976-07:00SBT and Test Arguments<br><br />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.<br /><br />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).<br /><br />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).<br /><br /><h4>Passing Args to ScalaTest from the Command Line</h4><br />Let's say you have this little ScalaTest class that uses both params and tags:<br /><pre><br />import org.scalatest.fixture.FixtureFunSuite<br />import org.scalatest.Tag<br /><br />class WickedCoolTest extends FixtureFunSuite{<br /> type FixtureParam = Map[String,Any]<br /> override def withFixture(test: OneArgTest) {<br /> test(test.configMap)<br /> }<br /> test("1", Tag("dood1")){ conf => println("dood1: " + conf) }<br /> test("2", Tag("dood2")){ conf => println("dood2: " + conf) }<br /> test("3", Tag("dood3")){ conf => println("dood3: " + conf) }<br />}</pre><br />To run all tests in in this class use:<br /><pre><br />test-only WickedCoolTest<br /></pre><br />To run only tests tagged with "dood1" use:<br /><pre><br />test-only WickedCoolTest -- -n dood1<br /></pre><br />To run tests tagged with dood1 or dood2, use:<br /><pre><br />test-only WickedCoolTest -- -n "dood1 dood2"<br /></pre><br />To run all tests except for tests tagged with dood2, run:<br /><pre><br />test-only WickedCoolTest -- -l dood2<br /></pre><br />To run all tests except for tests tagged with dood2 dood3, run:<br /><pre><br />test-only WickedCoolTest -- -l "dood2 dood3"<br /></pre><br />To pass configuration parameters to a test, use:<br /><pre><br />test-only WickedCoolTest -- -Danswer=42<br /></pre><br />To pass many config params, add more -D's:<br /><pre><br />test-only WickedCoolTest -- -Danswer=42 -DrealAnswer=54<br /></pre><br />Tags and parameters can be used in combination, like so:<br /><pre><br />test-only WickedCoolTest -- -n "dood dood2" -Dhey=you -Dm=f<br /></pre><br />This runs only tests tagged with dood or dood2 and produces the following output:<br /><br />dood: Map(hey -> you, m -> f)<br />dood2: Map(hey -> you, m -> f)<br /><br /><h4>Passing Args to ScalaCheck from the Command Line</h4><br />I'll spare you the entire example and just get to the point here.<br /><br />To set the minimum number of successful tests, use '-s'<br /><pre><br />> test-only *IntParallelArrayCheck -- -s 5000<br />...<br />[info] == scala.collection.parallel.mutable.IntParallelArrayCheck ==<br />[info] OK, passed 5000 tests.<br /></pre><br /><br />The rest of the examples are very similar. Consult ScalaCheck itself for further documentation. <br /><ul><br /><li>-s (minSuccessfulTests): Number of tests that must succeed in order to pass a property<br /><li>-d (maxDiscardedTests): Number of tests that can be discarded before ScalaCheck stops testing a property<br /><li>-n (minSize): Minimum data generation size<br /><li>-x (maxSize): Maximum data generation size<br /><li>-w (workers): Number of threads to execute in parallel for testing<br /><li>-z (wrkSize): Amount of work each thread should do at a time<br /></ul><br /><h4>Default Arguments</h4><br />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. <br /><br />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: <br /><pre><br />override def testOptions = <br /> super.testOptions ++ <br /> Seq(TestArgument(TestFrameworks.ScalaCheck, "-s", "5000")) <br /></pre><br /><br />Or maybe you only ever want to run your fast ScalaTest tests.<br /><pre><br />override def testOptions = <br /> super.testOptions ++ <br /> Seq(TestArgument(TestFrameworks.ScalaTest, "-n", "fast")) <br /></pre><br /><h4>Custom Test Tasks</h4><br />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.<br /><br />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. <br /><pre><br />lazy val blah = singleTestTask("blah.blah.Blah")<br /> <br />private def singleTestTask(className: String) = task { args =><br /> defaultTestTask(TestFilter(_ == className) :: <br /> testOptions.toList ::: ScalaTestArgs(args))<br />}<br /><br />private def newScalaTestArg(l: String*) = <br /> TestArgument(TestFrameworks.ScalaTest, l:_*)<br /><br />private def ScalaTestArgs(args: Seq[String]): List[TestArgument] = {<br /> def KVArgs(args: Seq[String]): TestArgument = <br /> newScalaTestArg(args.map("-D" + _):_*)<br /> def tagsFromArgs(tags: Seq[String]): List[TestArgument] = {<br /> if (tags.isEmpty) Nil else <br /> List(newScalaTestArg("-n", tags.mkString(" ")))<br /> }<br /> val (kvs, tags) = args.partition(_.contains("="))<br /> KVArgs(kvs.toSeq) :: tagsFromArgs(tags.toSeq)<br />}</pre><br /><h4>Subclasses</h4><br />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. <br /><br />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 :)<br /><pre><br />lazy val testSlow = <br /> runSubclassesOf("org.nlogo.util.SlowTest")<br />lazy val testFast = <br /> runEverythingButSubclassesOf("org.nlogo.util.SlowTest")<br /><br />private def runSubclassesOf(className: String) = {<br /> val subclass: Boolean => Boolean = x => x<br /> subclassTest(className, subclass)<br />}<br /> <br />private def runEverythingButSubclassesOf(className: String) = {<br /> val notSubclass: Boolean => Boolean = x => ! x<br /> subclassTest(className, notSubclass)<br />}<br /><br />private def subclassTest(className: String, <br /> subclassCheck: Boolean => Boolean) = task { <br /> args =><br /> lazy val jars = <br /> testClasspath.get.toList.map(_.asURL).toArray[java.net.URL]<br /> lazy val loader = <br /> new java.net.URLClassLoader(jars,buildScalaInstance.loader)<br /> def clazz(name: String) = Class.forName(name, false, loader)<br /> lazy val superClass = clazz(className)<br /> def filter = <br /> TestFilter(c => <br /> subclassCheck(superClass.isAssignableFrom(clazz(c))))<br /> defaultTestTask<br /> (filter :: testOptions.toList ::: ScalaTestArgs(args))<br />}</pre><br /><br /><h4>Yeah...</h4><br />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.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com4tag:blogger.com,1999:blog-34927953.post-88363497951619618762009-11-13T20:32:00.000-08:002009-11-13T22:20:27.192-08:00Introducing Sweet <br />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: <a href="http://github.com/joshcough/Sweet">http://github.com/joshcough/Sweet</a>. <br /><br /><h4> Your First Sweet </h4><br /><br />Sweets are just like ScalaTest's FunSuite, using the test("name"){ ... } style. The syntax is exactly the same:<br /><pre><br />class HelloWorldSweet extends Sweet {<br /><br /> test("hello, world!"){<br /> "hello, world!" mustBe "hello, world!"<br /> }<br />}<br /></pre><br />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. <br /><br /><h4> Assertions </h4><br /><br />Sweet currently offers only two assertions, in matchers style: mustBe and mustNotBe. Let's extend the hello world example to show usages of each:<br /><pre><br />class HelloWorldSweet2 extends Sweet {<br /><br /> test("hello, world! with mustBe"){<br /> "hello, world!" mustBe "hello, world!"<br /> }<br /> test("hello, world! with mustNotBe"){<br /> "hello, world!" mustNotBe "goodbye, world!"<br /> }<br />}<br /></pre><br />And while were at it, let's how a quick boolean example:<br /><pre><br />class BooleanAssertionExampleSweet extends Sweet {<br /><br /> test("hello, world!"){<br /> val b = imagaryCallThatReturnsABoolean()<br /> b mustBe true<br /> }<br />}<br /></pre><br />I know it's not much, but it probably covers 90% of common assertions, which are normally of the form:<br /><pre><br />assertEquals( 1, 1 )<br />assertTrue( something )<br /></pre><br />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".<br /><br /><h4> Running in the IDE </h4><br /><br />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:<br /><pre><br />class HelloWorldSweet extends Sweet with SweetTestNGAdapter {<br /><br /> test("hello, world!"){<br /> "hello, world!" mustBe "hello, world!"<br /> }<br />}<br /></pre><br />That's it!<br /><br />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.<br /><br /><h4> What's next for Sweet? </h4><br /><br />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.<br /><br /><ul><br /><li>Making use of my scala-parallel project, I've already added a Sweet that allows all tests to be run in parallel.<br /><li>I've added my concurrent programming test API in, so multi-threaded code can be testing very easily.<br /><li>I plan eventually to add Actor testing API here. <br /><li>Certain more as well.<br /></ul><br /><br /><h4> Why Sweet? </h4><br /><br />This is really two questions. Why did I write Sweet, and why should you use Sweet? <br /><br />As I explained, I want to use Sweet for experimental ideas. <br /><br />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! <br /><br /><h4> Implementation </h4><br /><br />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.<br /><br /><b>Sweet.scala</b><br /><pre><br />package sweet<br /><br />trait Sweet extends Assertions {<br /><br /> private[sweet] var tests = List[TestCase]()<br /><br /> case class TestCase(name: String, f: () => Unit) {<br /> def apply(reporter: SweetReporter) {<br /> try{<br /> reporter(TestStarting(name))<br /> f()<br /> reporter(TestSucceeded(name))<br /> }catch {<br /> case t: SourAssertionException => {<br /> reporter(TestFailed(name, t))<br /> }<br /> case t: Throwable => {<br /> reporter(TestErrored(name, t))<br /> }<br /> }<br /> }<br /> override def toString = name<br /> }<br /><br /> def test(name: String)(f: => Unit) {<br /> if (tests.map(_.name).contains(name)) println("duplicate test name: " + name)<br /> tests = tests ::: List(TestCase(name, f _))<br /> }<br /><br /> def run(reporter: SweetReporter) {<br /> tests.foreach(_(reporter))<br /> }<br />}<br /></pre><br /><b>Assertions.scala</b><br /><pre><br />package sweet<br /><br />trait Assertions {<br /><br /> case class Equalizer(a:Any){<br /><br /> def mustBe(b:Any){ <br /> if( ! a.equals(b) )toss(a + " did not equal " + b + " but should have") <br /> }<br /><br /> def mustNotBe(b:Any) { <br /> if( a.equals(b) ) toss(a + " must not equal " + b + ", but did") <br /> }<br /><br /> def toss(message: String){ throw new SourAssertionException(message) }<br /> }<br /><br /> implicit def Any2Equalizer(a: Any) = Equalizer(a)<br />}<br /></pre><br /><b>SourAssertionException.scala</b><br /><pre><br />package sweet<br /><br />class SourAssertionException(message: String) extends RuntimeException(message)<br /></pre><br /><b>SweetFramework.scala (implementation of Framework from test-interfaces)</b><br /><pre><br />package sweet<br /><br />import org.scalatools.testing._<br /><br />class SweetFramework extends Framework {<br /> def name = "Sweet"<br /> def tests = Array(new TestFingerprint { <br /> def superClassName = "sweet.Sweet"; def isModule = false<br /> })<br /> def testRunner(testLoader: ClassLoader, loggers: Array[Logger]) = { <br /> new SweetRunner(testLoader, loggers)<br /> }<br />}<br /></pre><br /><b>SweetRunner.scala (implementation of Runnerfrom test-interfaces)</b><br /><pre><br />package sweet<br /><br />import org.scalatools.testing._<br /><br />class SweetRunner(val classLoader: ClassLoader, <br /> loggers: Array[Logger]) extends Runner {<br /><br /> def run(testClassName: String, fingerprint: TestFingerprint, <br /> eventHandler: EventHandler, args: Array[String]){<br /> val testClass = Class.forName(testClassName, <br /> true, classLoader).asSubclass(classOf[Sweet])<br /> val sweet = testClass.newInstance<br /> val reporter = new MySweetReporter(eventHandler)<br /> sweet.run(reporter)<br /> }<br /><br /> class MySweetReporter(eventHandler: EventHandler) extends <br /> SweetReporter with NotNull{<br /><br /> def newEvent(tn: String, r: Result, e: Option[Throwable]) {<br /> class MyEvent(val testName:String, <br /> val description:String, <br /> val result:Result, val error:Throwable) extends Event<br /> eventHandler.handle(new MyEvent(tn, tn, r, e getOrElse null))<br /> }<br /><br /> def apply(event: SweetEvent) {<br /> event match {<br /> case t: TestStarting => <br /> loggers.foreach(_ info "Test Starting: " + t.testName)<br /> case t: TestFailed => <br /> newEvent(t.testName, Result.Failure, Some(t.reason))<br /> case t: TestErrored => <br /> newEvent(t.testName, Result.Failure, Some(t.reason))<br /> case t: TestSucceeded => <br /> newEvent(t.testName, Result.Success, None)<br /> }<br /> }<br /> }<br />}<br /></pre><br /><b>SweetReporter.scala</b><br /><pre><br />package sweet<br /><br />trait SweetReporter {<br /> def apply(event: SweetEvent) <br />}<br /></pre><br /><b>SweetEvent.scala</b><br /><pre><br />package sweet<br /><br />trait SweetEvent<br /><br />case class TestStarting(testName: String) extends SweetEvent<br />case class TestFailed(testName: String, <br /> reason:SourAssertionException) extends SweetEvent<br />case class TestErrored(testName: String, <br /> reason:Throwable) extends SweetEvent<br />case class TestSucceeded(testName: String) extends SweetEvent<br /></pre><br /><br /><h4> Proof </h4><br /><br />Here's proof that it's really just 99 lines:<pre><br />$ wc -l Assertions.scala \<br /> SourAssertionException.scala \<br /> Sweet.scala SweetEvent.scala \<br /> SweetFramework.scala \<br /> SweetReporter.scala \<br /> SweetRunner.scala \<br /> SweetTestNGAdapter.scala<br /> 14 Assertions.scala<br /> 2 SourAssertionException.scala<br /> 28 Sweet.scala<br /> 7 SweetEvent.scala<br /> 8 SweetFramework.scala<br /> 4 SweetReporter.scala<br /> 29 SweetRunner.scala<br /> 7 SweetTestNGAdapter.scala<br /> 99 total<br /></pre>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com6tag:blogger.com,1999:blog-34927953.post-80966415563789075342009-09-07T18:56:00.000-07:002009-09-07T20:09:34.341-07:00Teaching Kids To Read Programs <br />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. <br /><br />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:<br /><br /><pre><br />if x is 7 then jump<br />else sit down<br /></pre><br /><br />Then I say, "Simon Says x is 5!", and he would know to sit down.<br /><br />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.<br /><br />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 <b>pretending</b> to the mix. I started over with the following program:<br /><br /><pre><br />if color is red then PICK NOSE<br />else PUKE<br /></pre><br /><br />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. <br /><br />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. <br /><br />Now that I had his full attention I was easily able to add in an else if statement that I had failed on earlier:<br /><br /><pre><br />if color is red then PICK NOSE<br />else if color is black then DIE<br />else PUKE<br /></pre><br /><br />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.<br /><br />Now I was able to add in some more interesting boolean logic:<br /><br /><pre><br />if color is red or yellow then PICK NOSE<br />else if color is black or blue then DIE<br />else PUKE<br /></pre><br /><br />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. <br /><br /><pre><br />if x is 7 then PICK NOSE<br />else if x * 10 is 20 then DIE x times<br />else PUKE<br /></pre><br /><br />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:<br /><br /><pre><br />if x is 7 then PICK NOSE<br />else if x is 5 then DIE 5 times<br />else PUKE<br /></pre><br />followed by:<br /><pre><br />if x is 7 then PICK NOSE<br />else if x is 5 then DIE x times<br />else PUKE<br /></pre><br />then maybe something simpler than multiplication:<br /><pre><br />if x is 7 then PICK NOSE<br />else if x + 1 is 3 then DIE x times<br />else PUKE<br /></pre><br /><br />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. :( <br /><br />What's next? I'm not sure. Probably nested expressions. I think I could do that by introducing two colors like so:<br /><br /><pre><br />if first color is red then <br /> if second color is blue then PICK NOSE<br /> else THROW TANTRUM<br />else if first color is black or blue then DIE<br />else PUKE<br /></pre><br />Those of course could get far more complex. <br /><br /><br />A few final notes to those who actually intend to try this with their kids.<br /><ol><br /><li>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. <br /><li>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.<br /><li>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. <br /></ol><br />Please let me know what you think!Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com7tag:blogger.com,1999:blog-34927953.post-66162712888692784302009-09-01T10:41:00.000-07:002009-09-01T11:13:51.603-07:00ChangesBack in February I wrote that it was time for me to go back to <a href="http://jackcoughonsoftware.blogspot.com/2009/02/grad-school.html">grad school</a>. 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. <br /><br />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. <br /><br />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 <a href="http://jackcoughonsoftware.blogspot.com/2009/05/teaching-functional-programming-to-kids.html">teaching children</a>. 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.<br /><br />That's all. Bye.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-59467125055825642382009-07-22T21:21:00.000-07:002009-07-22T21:49:42.632-07:00What JVM Language Do You Write Tests In? <br />At a recent NYC Scala meetup, I got chatted up and basically was asked the following: <br /><br /><blockquote>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?</blockquote><br /><br />(As a matter of fact I do, but that's not the point of this post.)<br /><br />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. <br /><br /><h4>Random Ranting To Generate Ideas</h4><br />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! <br /><br />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. <br /><br />You might argue that now you have to maintain two different code bases, two different languages for your tests. Honestly, I say <a href="http://www.youtube.com/watch?v=0EcC3mj3oYw">Come On!</a>. 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. <br /><br />I think of more later.<br /><br /><h4>Poll</h4><br />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: <a href="http://jackcoughonsoftware.blogspot.com/">http://jackcoughonsoftware.blogspot.com/</a>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com2tag:blogger.com,1999:blog-34927953.post-30151662144058678502009-07-04T21:30:00.000-07:002009-07-04T23:07:20.029-07:00Testing Multi Threaded Scala Code <br />Recently I did a (somewhat brute force) port of <a herf="http://www.cs.umd.edu/projects/PL/multithreadedtc/overview.html">MultithreadedTC</a>. 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. <br /><ol><br /><li>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.<br /><li>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.<br /><li>This code will be in an upcoming release of ScalaTest, and (pending discussions) could make its way into Specs as well.<br /><li>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.<br /></ol><br /><br />Onward to an example! I'm going to dump it out, and explain after.<br /><pre><br />package scala.util.concurrent.locks<br /><br /><br />class PimpedReadWriteLockTest extends MultiThreadedSuite with <br /> MustMatchers with MustBeSugar {<br /> <br /> val lock = new java.util.concurrent.locks.ReentrantReadWriteLock<br /> import Implicits.RichReentrantReadWriteLock<br /><br /> thread("writer thread") {<br /> waitForTick(1)<br /> lock.write {tick mustBe 2}<br /> }<br /><br /> thread("reader thread") { <br /> lock.read { waitForTick(2) } }<br /> }<br /><br /> 5.threads("reader thread("+_+")") {<br /> lock.read { waitForTick(2) }<br /> }<br /><br /> 10 anonymousThreads {<br /> lock.read { waitForTick(2) }<br /> }<br />}<br /></pre><br />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.<br /><pre><br />class PimpedReadWriteLockTest extends MultiThreadedSuite with <br /> MustMatchers with MustBeSugar {<br /></pre><br />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. <br /><pre><br /> val lock = new java.util.concurrent.locks.ReentrantReadWriteLock<br /> import Implicits.RichReentrantReadWriteLock<br /></pre><br />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):<br /><pre><br /> readLock.lock()<br /> f()<br /> readLock.unlock()<br /></pre><br /><h3>Creating a test Thread</h3><pre><br /> thread("writer thread") {<br /> ...<br /> }<br /></pre><br />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.<br /><br /><h3>Wait For Tick</h3><br />Internally, MultiThreadedSuite maintains a clock. The clocks time starts at 0 and only advances when the following conditions hold:<br /><ol><br /><li><b><i>ALL</i></b> test threads are blocked.<br /><li>At least one of those threads is waiting for the clock to tick.<br /></ol><br />Why the last condition? If all threads are blocked, and no one is waiting for a clock tick, you have a deadlock! <br /><br /><code>waitForTick(n)</code> 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.<br /><br />Revisiting the code:<br /><pre><br /> thread("writer thread") {<br /> waitForTick(1)<br /> lock.write {tick mustBe 2}<br /> }<br /></pre><br />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.<br /><br />Next:<br /><pre><br /> thread("reader thread") { <br /> lock.read { waitForTick(2) } }<br /> }<br /></pre><br />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. :)<br /><br />Now, the curious reader might wonder, why waitForTick(<b>2</b>). 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.<br /><br />With that explained, you can see that waitForTick(<b>2</b>) is just shorthand for:<br /><pre><br />waitForTick(1)<br />waitForTick(2)<br /></pre><br />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.<br /><br /><h3>Creating LOTS of threads</h3><pre><br /> 5.threads("reader thread("+_+")") {<br /> lock.read { waitForTick(2) }<br /> }<br /></pre><br />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.<br /><br /><pre><br /> 10 anonymousThreads {<br /> lock.read { waitForTick(2) }<br /> }<br /></pre> <br />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.<br /><br />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:<br /><pre><br /> val readers: List[Thread] = 5.threads("reader thread("+_+")") {<br /> lock.read { waitForTick(2) }<br /> }<br /> val namelessReaders: List[Thread] = 10 anonymousThreads {<br /> lock.read { waitForTick(2) }<br /> }<br /></pre><br /><h3>Step by Step</h3><ol><br /><li>waitForTick(1) blocks the writer thread until tick 1 happens.<br /><li>The reader threads all get the read lock.<br /><li>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.<br /><li>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.<br /><li>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. <br /><li>After tick 2, all the reader threads wake up. The writer thread is still blocked, waiting for the read lock.<br /><li>The reader threads all give up the read lock in concert.<br /><li>The writer thread finally gets the write lock. When it does, it makes sure that the current tick is 2. Indeed, it is. <br /></ol> <br /><h3>Summary</h3><br />This should be the foundation of some really interesting work to come. I'll keep everyone informed.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com2tag:blogger.com,1999:blog-34927953.post-1860937831123325432009-06-24T19:00:00.000-07:002009-06-24T21:04:43.627-07:00Pimp vs Just Plain Fix my Library <br />I assume most people familiar with Scala are familiar with <a href="http://www.artima.com/weblogs/viewpost.jsp?thread=179766">Pimp My Library</a>. 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.<br /><br />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: <b>Pimping is most useful for fixing crappy, terrible, miserable API</b>. 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. <br /><br />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:<br /><br /><A NAME="enumerate(java.lang.Thread[])"><!-- --></A><H3>enumerate</H3><PRE>public int <B>enumerate</B>(<A HREF="../../java/lang/Thread.html" title="class in java.lang">Thread</A>[] list)</PRE><DL><DD>Copies into the specified array every active thread in this <br /> thread group and its subgroups. <br /> <p>First, the <code>checkAccess</code> method of this thread group is <br /> called with no arguments; this may result in a security exception. <br /> <p>An application might use the <code>activeCount</code> method to <br /> get an estimate of how big the array should be, however <i>if the<br /> array is too short to hold all the threads, the extra threads are<br /> silently ignored.</i> If it is critical to obtain every active<br /> thread in this thread group and its subgroups, the caller should<br /> verify that the returned int value is strictly less than the length<br /> of <tt>list</tt>.<br /> <p>Due to the inherent race condition in this method, it is recommended<br /> that the method only be used for informational purposes.<br /><DT><B>Parameters:</B><DD><CODE>list</CODE> - an array into which to place the list of threads.<br /><DT><B>Returns:</B><DD>the number of threads put into the array.<br /></DD><br /></DL><br />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. <br /><br />Not even that fun to fix to be honest, but the resulting code is far more manageable. But here's a solution. <br /><br /><pre><br />object PimpedThreadGroup {<br /> implicit def threadGroupToPimpedThreadGroup(tg: ThreadGroup) = {<br /> new PimpedThreadGroup(tg)<br /> }<br />}<br /><br />class PimpedThreadGroup(threadGroup: ThreadGroup) {<br /><br /> def getThreads: List[Thread] = getThreads(true)<br /><br /> def getThreads(recursive: Boolean): List[Thread] = {<br /> def getThreads(sizeEstimate: Int): Seq[Thread] = {<br /> val ths = new Array[Thread](sizeEstimate)<br /> if (threadGroup.enumerate(ths, recursive) == sizeEstimate) <br /> getThreads(sizeEstimate +10)<br /> else for (t <- ths; if (t != null)) yield t<br /> }<br /> getThreads(threadGroup.activeCount() + 10).toList<br /> }<br /><br /> def filter(state: State): List[Thread] = {<br /> getThreads.filter(_.getState == state)<br /> }<br /><br /> def exists(state: State): Boolean = {<br /> getThreads.exists(_.getState == state)<br /> }<br /><br /> def any_threads_alive_? = {<br /> getThreads.exists(t => t.getState != NEW && t.getState != TERMINATED)<br /> }<br /><br /> def any_threads_running_? = {<br /> getThreads.exists(_.getState == RUNNABLE)<br /> }<br /><br /> def any_threads_in_timed_waiting_? = {<br /> getThreads.exists(_.getState == TIMED_WAITING)<br /> }<br />}<br /></pre><br /><br />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?<br /><br />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. <br /><br /><pre><br /> implicit def ThreadGroupToList(tg:ThreadGroup): List[Thread] = {<br /> new PimpedThreadGroup(tg).getThreads<br /> }<br /></pre><br /><br />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.<br /><br />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.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-2717605903070830872009-06-14T21:12:00.000-07:002009-06-14T22:06:52.572-07:00Scala MultithreadedTC PortI 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 <a href="http://www.cs.umd.edu/projects/PL/multithreadedtc/overview.html">MultithreadedTC</a> to Scala.<br /><br />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.<br /><br />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.<br /><br />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. <br /><br /><pre><br />1 class MTCTimedOffer extends MultithreadedTestCase {<br />2 ArrayBlockingQueue<Object&rt; q;<br />3 <br />4 @Override public void initialize() {<br />5 q = new ArrayBlockingQueue<Object>(2);<br />6 }<br />7 <br />8 public void thread1() {<br />9 try {<br />10 q.put(new Object());<br />11 q.put(new Object());<br />12<br />13 freezeClock();<br />14 assertFalse(q.offer(new Object(), 25, TimeUnit.MILLISECONDS));<br />15 unfreezeClock();<br />16<br />17 q.offer(new Object(), 2500, TimeUnit.MILLISECONDS);<br />18 fail("should throw exception");<br />19 } catch (InterruptedException success){ assertTick(1); }<br />20 }<br />21<br />22 public void thread2() {<br />23 waitForTick(1);<br />24 getThread(1).interrupt();<br />25 }<br />26}<br /></pre><br /><br />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. <br /><br />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. <br /><br />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. <br /><br />Sort of...<br /><br />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). <br /><br /><ol><br /><li>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.<br /><li>When we freeze the clock we could easily forget to unfreeze it, leading to quite a bit of headache.<br /></ol><br />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. <br /><br /><pre><br />1 class MTCTimedOffer extends MultiThreadedSuite {<br />2<br />3 val q = new ArrayBlockingQueue[String](2)<br />4<br />5 val producer = thread{<br />6 q put "w"<br />7 q put "x"<br />8<br />9 withClockFrozen {<br />10 q.offer("y", 25, TimeUnit.MILLISECONDS) mustBe false<br />11 }<br />12<br />13 intercept[InterruptedException] {<br />14 q.offer("z", 2500, TimeUnit.MILLISECONDS)<br />15 }<br />16<br />17 tick mustBe 1<br />18 }<br />19<br />20 thread{<br />21 waitForTick(1)<br />22 producer.interrupt()<br />23 }<br />24}<br /></pre><br /><br />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.<br /><br /><ol><br /><li>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.<br /><br />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). <br /><li>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.<br /></ol><br /><br />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!Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-40327106926828065182009-06-01T08:51:00.000-07:002009-06-01T13:00:51.006-07:00Comedy: Scala vs. Ruby vs. Objective C <br />Please submit your favorite (or least favorite) language!<br /><br /><span style="color: rgb(255, 0, 0);">Added: <span style="color: rgb(255, 0, 0);">Java, Clojure, JavaScript</span></span><br /><br /><h3>Scala</h3><pre><br />this.computers = Array(<br /> Map("Name" -> "MacBook", "Color"->"White"),<br /> Map("Name" -> "MacBook Pro", "Color"->"Silver"),<br /> Map("Name" -> "iMac", "Color"->"White"))<br /></pre><br /><h3>Ruby</h3><pre><br />self.computers = [<br /> {:Name=>"MacBook", :Color=>"White"},<br /> {:Name=>"MacBook Pro", :Color=>"Silver"},<br /> {:Name=>"iMac", :Color=>"White"}]<br /></pre><br /><h3>Objective C</h3><pre><br />NSDictionary *row1 =<br /> [[NSDictionary alloc] initWithObjectsAndKeys:<br /> @"MacBook", @"Name", @"White", @"Color", nil];<br />NSDictionary *row2 =<br /> [[NSDictionary alloc] initWithObjectsAndKeys:<br /> @"MacBook Pro", @"Name", @"Silver", @"Color", nil];<br />NSDictionary *row3 =<br /> [[NSDictionary alloc] initWithObjectsAndKeys:<br /> @"iMac", @"Name", @"White", @"Color", nil];<br /><br />NSArray *array =<br /> [[NSArray alloc] initWithObjects: row1, row2, row3, nil];<br /><br />self.computers = array;<br /><br />[row1 release];<br />[row2 release];<br />[row3 release];<br />[array release];<br /></pre><br /><h3>Java</h3><br />Assuming this field:<br /><pre><br /> Map<String, String>[] computers;<br /></pre><br />Then:<br /><pre><br />Map[] maps = {<br /> new HashMap(){{<br /> put("Name", "MacBook"); <br /> put("Color", "White");<br /> }},<br /> new HashMap(){{<br /> put("Name", "MacBook Pro");<br /> put("Color", "Silver");<br /> }},<br /> new HashMap(){{<br /> put("Name", "iMac"); <br /> put("Color", "White");<br /> }}<br /> };<br /> this.computers = maps;<br /></pre><br />Notice you can't use generics with the array creation, and, 4 space indenting! Yeah!<br /><br /><h3>Clojure</h3><pre><br />(def computers [<br /> {:Name "MacBook"}<br /> {:Name "MacBook Pro" :Color "Silver"}<br /> {:Name "iMac" :Color "White"}])<br /><pre><br /><h3>JavaScript</h3><pre><br />this.computers =<br />[{'name':'MacBook', 'color':'White'},<br />{'name':'MacBook Pro', 'color':'Silver'},<br />{'name':'iMac', 'color':'White'}];<br /></pre></pre></pre>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com24tag:blogger.com,1999:blog-34927953.post-58524384694340947872009-05-31T07:30:00.000-07:002009-05-31T07:52:14.241-07:00Good Use Case for Named Arguments <br />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.<br /><br />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).<br /><pre><br /> val data = AllGeneratorNumber(8)<br /> val chain = FlipFlopChain(data, Generator.on)<br /> ...<br /></pre><br />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.<br /><br />So I changed the code to make it more explicit, by declaring a writeBit val.<br /><pre><br /> val data = AllGeneratorNumber(8)<br /> val writeBit = Generator.on<br /> val chain = FlipFlopChain(data, writeBit)<br /> ...<br /></pre><br />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.<br /><br />With keyword arguments, there is a much better solution:<br /><pre><br /> val data = AllGeneratorNumber(8)<br /> val chain = FlipFlopChain(data, writeBit=Generator.on)<br /> ...<br /></pre><br />Win!Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-55444354109310054902009-05-30T20:31:00.001-07:002009-06-01T12:58:33.342-07:00Some Simple Scala Refactorings <br />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). <br /><br />Anyway, I have a few refactorings that I wanted to mention.<br /><br /><h3>Refactoring to Case Classes</h3><br />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. <br /><br />Old Code:<br /><pre><br />class XorGate(inputA: PowerSource, inputB: PowerSource) <br /> extends LogicGate {<br /> val output: PowerSource = <br /> new AndGate(<br /> new OrGate(inputA, inputB), <br /> new NandGate(inputA, inputB))<br />}<br /></pre><br />New Code:<pre><br />case class XorGate(inputA: PowerSource, inputB: PowerSource) <br /> extends LogicGate {<br /> val output: PowerSource = <br /> AndGate(OrGate(inputA, inputB), NandGate(inputA, inputB))<br />}<br /></pre><br />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.<br /><br />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:<br /><pre><br />case class XorGate(private val inputA: PowerSource, <br /> private val inputB: PowerSource) <br /> extends LogicGate {<br /> val output: PowerSource = <br /> AndGate(OrGate(inputA, inputB), NandGate(inputA, inputB))<br />}<br /></pre><br />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.<br /><br /><h3>Refactoring to Fewer Files</h3><br />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. <br /><br />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.<br /><br /><pre><br />package com.joshcough.cpu.gates<br /><br />import electric.{Relay, Inverter, Wire, PowerSource}<br /><br />object LogicGate{<br /> implicit def logicGateToPowerSource( lg: LogicGate ): PowerSource = lg.output<br />}<br /><br />trait LogicGate{<br /> val inputA: PowerSource<br /> val inputB: PowerSource<br /> val output: PowerSource<br />}<br /><br />case class AndGate(val inputA: PowerSource, <br /> val inputB: PowerSource) extends LogicGate {<br /> val output: PowerSource = Relay(inputA, Relay(inputB))<br />}<br /><br />case class NandGate(val inputA: PowerSource, <br /> val inputB: PowerSource) extends LogicGate{<br /> val output = new Wire<br /> Inverter(inputA)-->output<br /> Inverter(inputB)-->output<br />}<br /><br />case class NorGate(val inputA: PowerSource, <br /> val inputB: PowerSource) extends LogicGate{<br /> val output: PowerSource = Inverter(inputB, Inverter(inputA))<br />}<br /><br />case class OrGate(val inputA: PowerSource, <br /> val inputB: PowerSource) extends LogicGate{<br /> val output = new Wire<br /> inputA-->output<br /> inputB-->output<br />}<br /><br />case class XorGate(val inputA: PowerSource, <br /> val inputB: PowerSource) extends LogicGate {<br /> val output: PowerSource = <br /> AndGate(OrGate(inputA, inputB), NandGate(inputA, inputB))<br />}<br /></pre><br /><br />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. <br /><br /><h3>More</h3><br />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.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com4tag:blogger.com,1999:blog-34927953.post-21228227961172357762009-05-30T14:25:00.000-07:002009-05-31T05:28:55.351-07:00Simple Scala Keyword ParametersEverything 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)<br /><br /><h3> Default Values</h3><ul><br /><li>Define a class that takes two keyword args, name and lives, and provide default values.<br /><pre><br />scala> case class Cat(name:String="kitty", lives:Int=9)<br />defined class Cat<br /></pre><br /></li><li>Instantiate the cat providing no arguments.<br /><pre><br />scala> new Cat<br />res1: Cat = Cat(kitty,9)<br /></pre><br /></li><li>Instantiate a cat providing both params, unnamed.<br /><pre><br />scala> Cat("Java", 1)<br />res2: Cat = Cat(Java,1)<br /></pre><br /></li><li>Instantiate a cat providing just the first param, unnamed.<br /><pre><br />scala> Cat("Scala")<br />res3: Cat = Cat(Scala,9)<br /></pre><br /></li><li>Instantiate a cat providing both params, named.<br /><pre><br />scala> new Cat(name="newspeak", lives=20)<br />res4: Cat = Cat(newspeak,20)<br /></pre><br /></li><li>Instantiate a cat providing both params in reverse order. (Only works if names the argument names are given.)<br /><pre><br />scala> new Cat(lives=20, name="newspeak")<br />res5: Cat = Cat(newspeak,20)<br /></pre><br /></li><li>Instantiate a cat providing the first param, named.<br /><pre><br />scala> new Cat(name="newspeak")<br />res6: Cat = Cat(newspeak,9)<br /></pre><br /></li><li>Instantiate a cat providing the second param, named.<br /><pre><br />scala> Cat(lives=4) <br />res7: Cat = Cat(kitty,4)<br /></pre><br /></li><li>Instantiate a cat providing the first argument unnamed, and the second argument named!<br /><pre><br />scala> new Cat("Lua", lives=1)<br />res8: Cat = Cat(Lua,1)<br /></pre><br /></li><li>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.<br /><pre><br />scala> new Cat(name="Lua", 1) <br /><console>:7: error: positional after named argument.<br /> new Cat(name="Lua", 1)<br /> ^<br /></console></pre></li></ul><h3>No Default Values</h3><ul><br /><li>Redefine class Cat without supplying default values. This means values <i>must</i> be provided when instantiating a cat (more generically, calling a function).<br /><pre><br />scala> case class Cat(name:String, lives:Int)<br />defined class Cat<br /></pre><br /></li><li>Instantiate a cat providing both params, unnamed.<br /><pre><br />scala> Cat("Java", 1)<br />res9: Cat = Cat(Java,1)<br /></pre><br /></li><li>Instantiate a cat providing both params, named.<br /><pre><br />scala> new Cat(name="Douglas", lives=42) <br />res10: Cat = Cat(Douglas,42)<br /></pre><br /></li><li>Attempt to instantiate a cat, not providing values for the arguments.<br /><pre><br /><console>:7: error: not enough arguments for constructor Cat:<br />(name: String,lives: Int)Cat, unspecified parameters:<br />value name, value lives<br /> new Cat<br /> ^<br /></console></pre></li></ul><h3>Overloading</h3><ul><br /><li>Redefine the class, overloading the constructor.<br /><pre><br />scala> case class Cat(name:String="kitty", lives:Int=9){<br /> | def this(name:String) = this(name, -54)<br /> | }<br /></pre><br /></li><li>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.<br /><pre><br />scala> new Cat("Martin")<br />res11: Cat = Cat(Martin,-54)<br /></pre><br /></li><li>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.<br /><pre><br />scala> case class Cat(name:String="kitty", lives:Int=9){<br /> | def this(x:Int) = this("hello", x+99) <br /> | }<br />defined class Cat<br /></pre><br /></li><li>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.<br /><pre><br />scala> new Cat(lives=8) <br />res12: Cat = Cat(kitty,8)<br /></pre><br /></li><li>Instantiate a cat - same as the String overloading case above.<br /><pre><br />scala> new Cat(8) <br />res13: Cat = Cat(hello,107)<br /></pre><br /></li></ul>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com1tag:blogger.com,1999:blog-34927953.post-27751413242039866292009-05-19T19:39:00.000-07:002009-05-20T07:20:25.015-07:00Teaching Functional Programming To KidsI 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.<br /><br />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.<br /><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjf3psUiD5Hov7ojZNMr8qLbr3Hcxw_1M_rhi3fLMUVY4eFASZ3wH3LcWFF67C8wG2YnovFvNBq4ip8uXOfufH9scdxr9jq3c2TkXRyZL8OX6jvmufEFkKxN9mU1ubi3t4yyVIMYQ/s1600-h/285_top_10_list.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 167px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjf3psUiD5Hov7ojZNMr8qLbr3Hcxw_1M_rhi3fLMUVY4eFASZ3wH3LcWFF67C8wG2YnovFvNBq4ip8uXOfufH9scdxr9jq3c2TkXRyZL8OX6jvmufEFkKxN9mU1ubi3t4yyVIMYQ/s400/285_top_10_list.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5337756099884422850" /></a><br /><br />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:<br /><pre><br /> -----------<br /> | | <br /> Sneetch ---> | * | ---> Star Bellied Sneetch<br /> | |<br /> -----------<br /></pre><br />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. <br /><br />In the Dr. Seuss book there is also the opposite machine that removes the star from a star bellied Sneetch.<br /><pre><br /> -----------<br /> Star Bellied | | <br /> Sneetch -> | -* | ---> Sneetch<br /> | |<br /> -----------<br /></pre><br />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):<br /><pre><br /> -----------<br /> | | <br /> 10 ---> | +5 | ---> 15<br /> | |<br /> -----------<br /></pre><br />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.<br /><br />After this one I followed up with another very easy one.<br /><pre><br /> -----------<br /> | | <br /> 10 ---> | -5 | ---> 5<br /> | |<br /> -----------<br /></pre><br />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.<br /><br />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.<br /><pre><br /> -----------<br /> 7 ---> | | <br /> | + | ---> 19<br /> 12 ---> | |<br /> -----------<br /></pre><pre><br /> -----------<br /> 12 ---> | | <br /> | - | ---> 5<br /> 7 ---> | |<br /> -----------<br /></pre><br />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).<br /><pre><br /> -----------<br /> 7 ---> | | <br /> | Biggest | ---> 12<br /> 12 ---> | |<br /> -----------<br /></pre><pre><br /> -----------<br /> 7 ---> | | <br /> | Smallest | ---> 7<br /> 12 ---> | |<br /> -----------<br /></pre><pre><br /> -----------<br /> 10 ---> | | <br /> | Smallest | ---> 10<br /> 10 ---> | |<br /> -----------<br /></pre><br />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.<br /><br />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.<br /><pre><br /> -----------<br /> 7 ---> | | <br /> | = | ---> NO!<br /> 12 ---> | |<br /> -----------<br /></pre><pre><br /> -----------<br /> 7 ---> | | <br /> | = | ---> YES!<br /> 7 ---> | |<br /> -----------<br /></pre><br />Simple, but effective.<br /><br />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. <br /><pre><br /> ------------<br /> ON ---> | | <br /> | AND GATE | ---> OFF<br /> OFF ---> | |<br /> ------------<br /></pre><pre><br /> ------------<br /> ON ---> | | <br /> | OR GATE | ---> ON<br /> OFF ---> | |<br /> ------------<br /></pre><pre><br /> ------------<br /> ON ---> | | <br /> | AND GATE | ---> ON<br /> ON ---> | |<br /> ------------<br /></pre><br />While the logic gate examples seem simple, it tied two worlds that we've been working on together very nicely.<br /><br /><h4>Fun</h4><br />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.<br /><br /><h4>Combining Machines</h4><br /><br />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:<br /><pre><br /> -----------<br /> 7 --> | | -------<br /> | + | --> 19 --> | |<br /> 12 --> | | | |<br /> ----------- | |<br /> | + | --> 39<br /> ----------- | |<br /> 10 --> | | | |<br /> | + | --> 20 --> | |<br /> 10 --> | | -------<br /> -----------<br /></pre><br />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:<br /><pre><br /> -----------<br /> 7 --> | | -------<br /> | + | --> 19 --> | |<br /> 12 --> | | | |<br /> ----------- | |<br /> | = | --> NO!<br /> ----------- | |<br /> 10 --> | | | |<br /> | + | --> 20 --> | |<br /> 10 --> | | -------<br /> -----------<br /></pre><br />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. <br /><br /><h4>Types</h4><br />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)?"<br /><pre><br /> -----------<br /> | | <br /> 10 ---> | +5 | ---> 15<br /> | |<br /> -----------<br /></pre><br />Answer: Number. I avoided Integer for now. What kind of thing does it spit out? Answer: Number.<br /><br />I then showed him this next example, which should arguably have a section of its own:<br /><pre><br /> -----------<br /> | | <br /> D ---> | +5 | ---> I<br /> | |<br /> -----------<br /></pre><br />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.<br /><br />Then I introduced a formal notation for types:<br /><pre><br /> -----------<br /> 7 ---> | | <br /> | + | ---> 19<br /> 12 ---> | |<br /> -----------<br /><br />(Number,Number) -> Number<br /></pre><br />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):<br /><pre><br /> -----------<br /> | | <br /> 5 ---> | To Letter | ---> E<br /> | |<br /> -----------<br /><br />Number -> Letter<br /></pre><br /><br />He understands the notation and can write it if I give him slots to fill in like this:<br /><br />______ -> ______<br /><br />or<br /><br />(______, ______) -> _______<br /><br /><br /><h4>Things I don't know how to teach, Yet</h4><br />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. <br /><br />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. <br /><br />Anyway, this was all really, really fun, for both of us.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com49tag:blogger.com,1999:blog-34927953.post-80925709958130028542009-05-14T19:49:00.000-07:002009-05-14T21:55:34.889-07:00Refactoring in ScalaAnother really long post, but why not!<br /><br />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:<br /><ul><br /><li>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.</li><br /><li>Better handling and testing of syntax errors.</li><br /><li>Separate Scala lexing from Lexer core, providing a reusable Lexer framework for Lexing any language.</li><br /></ul><br />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. <br /><br /><h4>Multi Line Support</h4><br />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. <br /><br />Old code:<br /><pre><br />trait Lexer extends SyntaxErrorHander {<br /> var chars: FunctionalCharArray<br /> var currentIndex = 0<br /></pre><br />New code:<br /><pre><br />trait Lexer extends CompilationUnitWalker with SyntaxErrorHander {<br /> var unit: CompilationUnit<br /></pre><br />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:<br /><pre><br />trait CompilationUnitWalkerInterface {<br /> var unit: CompilationUnit<br /> def skipChar: Unit<br /> def skipChars(i: Int): Unit<br /> def skipLine: Unit<br /> def currentLine: FunctionalCharArray<br /> def currentLineNumber: Int<br /> def currentOffset: Int<br /> def eofReached_? : Boolean<br />}<br /></pre><br />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. <br /><br />I'll show the remainder of the Lexer code in the next section. <br /><br /><h4>Syntax Error Handling</h4><br />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:<br /><br />Old code:<br /><pre><br />trait SyntaxErrorHander{<br /> def syntaxError(error:SyntaxError):Unit = {<br /> println(error)<br /> }<br />}<br /></pre><br />New code:<br /><pre><br />trait SyntaxErrorHander{<br /> def syntaxError(unit: CompilationUnit, <br /> lineNumber: Int, offset: Int):Unit = {<br /> println("Syntax Error(" + unit + ", line number:" + <br /> lineNumber + ", offset:" + offset + ")")<br /> }<br />}<br /></pre><br />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:<br /><pre><br />trait AddToCompilationUnitSyntaxErrorHander extends SyntaxErrorHander{<br /> override def syntaxError(unit: CompilationUnit, <br /> lineNumber: Int, offset: Int):Unit = {<br /> super.syntaxError(unit, lineNumber, offset)<br /> unit.syntaxError(lineNumber, offset)<br /> }<br />}<br /></pre><br />The code for calling into the syntax error handler in the Lexer actually shaped up nicely as well:<br /><pre><br />trait Lexer extends CompilationUnitWalker with SyntaxErrorHander {<br /> var unit: CompilationUnit<br /><br /> def finders: List[FunctionalCharArray => Option[Lexeme]]<br /><br /> def nextToken: Token = {<br /><br /> // if we've already lexed the whole file, get the f out.<br /> if (eofReached_?) return EOF(currentLineNumber)<br /><br /> // find all possible Lexemes<br /> val matches = <br /> finders.map(f => f(currentLine)).filter(_.isDefined).map(_.get)<br /><br /> // if we've found no lexemes, syntax error! adjust and try again.<br /> if (matches.isEmpty) {<br /> syntaxError(unit, currentLineNumber, currentOffset)<br /> skipChar<br /> return nextToken<br /> }<br /><br /> // the longest match found should be on top...i think...<br /> val longestMatch = matches.sort(_.size >= _.size).head<br /><br /> // deal with the best lexeme<br /> handleLexeme(longestMatch)<br /> }<br /><br /> def handleLexeme(lex: Lexeme) = lex match {<br /> case NewLine => {<br /> skipLine<br /> nextToken<br /> }<br /> case WhiteSpace(_) => {<br /> skipChar<br /> nextToken<br /> }<br /> case lex => {<br /> val indexOfLexeme = currentOffset<br /> skipChars(lex.data.length)<br /> Token(lex, currentLineNumber, indexOfLexeme)<br /> }<br /> }<br />}<br /></pre><br />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!<br /><br />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.<br /><br /><h4>Refactoring Towards Reuse</h4><br />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. <br /><br />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:<br /><pre><br />trait ScalaLexer extends Lexer with ScalaFinders with <br /> AddToCompilationUnitSyntaxErrorHander<br /><br />trait ScalaFinders extends<br /> ScalaCharFinders with NumberFinder with ScalaIdentifinder with<br /> WhiteSpaceFinder with CaseClassFinder with CaseObjectFinder<br /><br />case object CaseClass extends SimpleLexeme("case class")<br />case object CaseObject extends SimpleLexeme("case object")<br /><br />object ScalaIOLBuiler extends IdentifierOnlyLexerBuilder{<br /> def apply(cu: CompilationUnit) = {<br /> new ScalaIOL{ var unit: CompilationUnit = cu }<br /> }<br />}<br />trait ScalaIOL extends IdentifierOnlyLexer with ScalaIdentifinder<br /><br />case class ScalaTwoPartIdentifinder(<br /> w1: String, w2: String, l: Lexeme) extends<br /> TwoPartIdentifinder(ScalaIOLBuiler, w1,w2,l)<br /><br />trait CaseClassFinder extends LexemeFinder {<br /> override def finders =<br /> super.finders ::: <br /> List(ScalaTwoPartIdentifinder("case", "class", CaseClass).find _)<br />}<br /><br />trait CaseObjectFinder extends LexemeFinder {<br /> override def finders =<br /> super.finders ::: <br /> List(ScalaTwoPartIdentifinder("case", "object", CaseObject).find _)<br />}<br /><br />trait ScalaCharFinders extends LexemeFinder {<br /> override def finders = super.finders ::: CharFinders(<br /> Underscore, Comma, Dot, Eq, Semi, Colon, LeftParen,<br /> RightParen, LeftCurly, RightCurly, LeftBrace, RightBrace<br /> )<br />}<br /></pre><br />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. <br /><br />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. <br /><br />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).<br /><br />For now I'll give a quick snippit of the testing I did for handling multiple lines, but I'll wait to explain it:<br /><pre><br />trait NewLineTests extends LexerTest{<br /><br /> test("new lines") {<br /> checkCode("x,\ny",<br /> (0,0) -> Identifier("x"),<br /> (0,1) -> Comma,<br /> (1,0) -> Identifier("y"))<br /> }<br /><br /> test("more new lines"){<br /> checkCode("""x,<br /> y,<br /> z""",<br /> (0,0) -> Identifier("x"),<br /> (0,1) -> Comma,<br /> (1,4) -> Identifier("y"),<br /> (1,5) -> Comma,<br /> (2,6) -> Identifier("z"))<br /> } <br />}<br /></pre><br />That's all for now. It's late.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-21026372424054460212009-05-14T19:08:00.000-07:002009-05-14T19:49:58.680-07:00Scala over Ruby - My Debate EndsI'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.<br /><br />My main reason? Refactoring. Over the years I've become very good at refactoring; I've actually been called a refactoring machine. I have <i>a lot</i> of experience refactoring really, really terrible code. Yes, this sucks, I have a history of picking the wrong <a href="http://jackcoughonsoftware.blogspot.com/2008/11/back.html">job</a>. 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). <br /><br />I can refactor so easily in Scala with huge confidence and I can't do that in Ruby at all. In Ruby:<br /><ul><br /><li>It takes a long time to make major refactorings.</li><br /><li>I'm never fully confident in my refactorings and almost always get annoyed by runtime errors.</li><br /><li>Sometimes the stack traces are all messed up and I can't figure out where my actual error is.</li><br /><li>Most code you run into isn't going to have enough test coverage to help anyway.</li><br /><li>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.</li><br /><li>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.</li><br /><li>Ad infinitum...</li></ul><br />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.Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com5tag:blogger.com,1999:blog-34927953.post-80808126437418645672009-05-12T17:00:00.001-07:002009-05-12T21:07:00.940-07:00A Scala LexerThis is a really long post, but IM(not so)HO, its really fun!<br /><br />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. <i>And</i> 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.<br /><br />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.<br /><br />Before I get to the implementation, let me show how to use it. It can be done very simply at the command line. Example:<br /><pre><br />scala> import com.joshcough.compiler.lex._<br />import com.joshcough.compiler.lex._<br /><br />scala> val code = "x" <br />code: java.lang.String = x<br /><br />scala> val lexer = new SimpleLexer(code) with Identifinder<br />lexer: com.joshcough.compiler.lex.SimpleLexer with com.joshcough.compiler.lex.Identifinder = SimpleLexer(FunctionalCharArray([C@b6aea4))<br /><br />scala> lexer.nextToken <br />res0: com.joshcough.compiler.lex.Token = Token(Identifier(x),0)<br /><br />scala> lexer.nextToken <br />res1: com.joshcough.compiler.lex.Token = EOF(1)<br /></pre><br />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):<br /><pre><br />scala> lexer lexing "-->"<br /><br />scala> lexer.nextToken<br /> Token(Identifier(-->),0)<br /><br />scala> lexer.nextToken<br /> EOF(3)<br /><br />scala> lexer lexing "_ewrk_1212_adf435445_^^^"<br /><br />scala> lexer.nextToken<br /> Token(Identifier(_ewrk_1212_adf435445_^^^),0)<br /></pre><br />Much better. But what happens if I pass in something that the lexer shouldn't understand?<br /><pre><br />scala> lexer lexing "1"<br /><br />scala> lexer.nextToken<br /> SyntaxError(0)<br /> res4: com.joshcough.compiler.lex.Token = EOF(1)<br /></pre><br />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.<br /><br />The last lexer failed to recognize numbers. That's easy enough to fix. Simply mix in NumberFinder:<br /><pre><br />scala> val lexer = new SimpleLexer(code) with <br /> Identifinder with NumberFinder <br /><br />scala> lexer lexing "123" <br /><br />scala> lexer.nextToken<br /> Token(Number(123),0)<br /><br />scala> lexer lexing "-->"<br /><br />scala> lexer.nextToken <br /> Token(Identifier(-->),0)<br /></pre><br />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<br /><pre><br />scala>lexer lexing "(x,y);"<br /><br />scala> lexer.nextToken <br /> Token(LeftParen,0)<br /><br />scala> lexer.nextToken<br /> Token(Identifier(x),1)<br /><br />scala> lexer.nextToken<br /> Token(Comma,2)<br /><br />scala> lexer.nextToken<br /> Token(Identifier(y),3)<br /><br />scala> lexer.nextToken<br /> Token(RightParen,4)<br /><br />scala> lexer.nextToken<br /> Token(Semi,5)<br /></pre><br />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.<br /><pre><br />scala> val lexer = new SimpleLexer(code) with Identifinder with<br /> NumberFinder with CharFinders with WhiteSpaceFinder<br />lexer lexing "( x , y );"<br /><br />scala> lexer.nextToken <br /> Token(LeftParen,0)<br /><br />scala> lexer.nextToken<br /> Token(Identifier(x),2)<br /><br />scala> lexer.nextToken<br /> Token(Comma,4)<br /><br />scala> lexer.nextToken<br /> Token(Identifier(y),6)<br /><br />scala> lexer.nextToken<br /> Token(RightParen,8)<br /><br />scala> lexer.nextToken<br /> Token(Semi,9)<br /></pre><br />Notice that like any good lexer, this lexer simply skips over the white space, handing you the next actual token at its right location. <br /><br />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. <br /><br /><h4>Lexer Implementation</h4><br />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]. <br /><pre><br />case class FunctionalCharArray(chars: Array[Char]) {<br /> def skip(i: Int) = new FunctionalCharArray(chars.drop(i))<br /> def size = chars.size<br /> def nextChar: Option[Char] = get(0)<br /><br /> def get(index: Int): Option[Char] = {<br /> if (chars.size > index) Some(chars(index)) else None<br /> }<br />}<br /></pre><br />Taking a brief peek into the Lexer we find that its the FunctionCharArray that is mutated:<br /><pre><br />trait Lexer extends SyntaxErrorHander {<br /><br /> var chars: FunctionalCharArray<br /><br /> var currentIndex = 0<br /><br /> def finders: List[FunctionalCharArray => Option[Lexeme]]<br /><br /> ...<br /></pre><br />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 <i>finders</i>. <br /><br />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.<br /><ul><li>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.<li>The NumberFinder returns Some(Number(123)) when given this array: ['1', '2', '3', ' ', '+', ' ', '7']<li>The CharFinders only ever look at the first element in the array.<br /></ul><br />To fully demonstrate just how simple they are, we need to see some. Have at you!<br /><pre><br />trait WhiteSpaceFinder extends LexemeFinder {<br /> override def finders = super.finders ::: List(findWhiteSpace _)<br /><br /> def findWhiteSpace(chars: FunctionalCharArray): Option[Lexeme] = {<br /> chars.nextChar match {<br /> case Some(' ') | Some('\t') | Some('\n') => Some(WhiteSpaceLex)<br /> case _ => None<br /> }<br /> }<br />}<br /></pre><br />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. <br /><br />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. <br /><br />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. <br /><pre><br />class IdentifierOnlyLexer(var chars: FunctionalCharArray) extends<br /> Lexer with WhiteSpaceFinder with Identifinder<br /><br />trait CaseClassFinder extends LexemeFinder {<br /> override def finders = super.finders ::: List(findCaseClass _)<br /><br /> def findCaseClass(chars: FunctionalCharArray) = {<br /> if (chars.size < 10) None<br /> else {<br /> val lexer = new IdentifierOnlyLexer(chars)<br /><br /> (lexer.nextToken, lexer.nextToken) match {<br /> case (Token(Identifier("case"), _), <br /> Token(Identifier("class"), _)) => {<br /> Some(CaseClass)<br /> }<br /> case _ => None<br /> }<br /> }<br /> }<br />}<br /></pre><br />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:<br /><br />If a CaseClassFinder finds <i>the Identifier "case"</i> followed by <i>the Identifier "class"</i>, then it should return CaseClass. <br /><br />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!<br /><br />The Indentifinder and NumberFinder traits are too long to show here. I'll post a link to the codebase. <br /><br />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 <i>must</i> be the longer of the two. Simple as that. Now lets take a look at all of Lexer.<br /><br /><h4>Lexer Implementation (for real this time!)</h4><pre><br />1 trait Lexer extends SyntaxErrorHander {<br />2 <br />3 var chars: FunctionalCharArray<br />4 var currentIndex = 0<br />5<br />6 def finders: List[FunctionalCharArray => Option[Lexeme]]<br />7<br />8 def nextToken: Token = {<br />9 <br />10 def skip(i: Int) {currentIndex += i; chars = chars.skip(i)}<br />11<br />12 val token = nextToken_including_whitespace_and_syntaxerror<br />13<br />14 token match {<br />15 case SyntaxError(i) => {<br />16 syntaxError(SyntaxError(i))<br />17 skip(1)<br />18 nextToken<br />19 }<br />20 case EOF(_) => token<br />21 case Token(WhiteSpaceLex, _) => skip(1); nextToken<br />22 case Token(lex, _) => skip(lex.data.length); token<br />23 }<br />24 }<br />25<br />26 private def nextToken_including_whitespace_and_syntaxerror = {<br />27 if (chars.nextChar == None) EOF(currentIndex)<br />28 else {<br />29 val lexemesFound: List[Lexeme] = {<br />30 finders.map(f => f(chars)).filter(_ match {<br />31 case Some(t) => true<br />32 case _ => false<br />33 }).map(_.get)<br />34 }<br />35<br />36 if (lexemesFound.size == 0) return SyntaxError(currentIndex)<br />37 <br />38 val lexemesSorted = <br />39 lexemesFound.sort(_.data.size >= _.data.size)<br />40<br />41 Token(lexemesSorted(0), currentIndex)<br />42 }<br />43 }<br />44<br />45 def lexing(s: String): Lexer = {<br />46 lexing(new FunctionalCharArray(s.toCharArray))<br />47 }<br />48<br />49 def lexing(cs: FunctionalCharArray): Lexer = {<br />50 chars = cs; currentIndex = 0; this<br />51 }<br />52}<br /></pre><br />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. <br /><ol><br /><li>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).<br /><li>It then calls all of its finders with the current array: finders.map(f => f(chars))<br /><li>It then immediately filters the results, because its only interested in any finders that actually returned Some(Lexeme...), and not none. Of course.<br /><li>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!<br /><li>On line 38 it sorts the Lexemes by size, aiming to get the largest. <br /><li>Finally it returns the largest token (ignoring any other matches).<br /></ol><br />Now I'll explain the nextToken method, and then wrap up. <br /><br />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.<br /><ol><br /><li>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. <br /><li>If it receives an EOF, just hand it over to the Parser, it should know what to do with it.<br /><li>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.<br /><li>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.<br /></ol><br /><br />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. <br /><br /><br />If you're actually still reading, awesome! Thanks! I hope you've learned something. You can find all the actual source code <a href="http://code.google.com/p/compilerplayground/source/browse/#svn/trunk/src/main/scala/com/joshcough/compiler/lex">here</a>. Not bad for about 8 hours huh?<br /><br />Oh BTW, my only two references for this were the Dragon Book (2 ed), and the Scala compiler itself. <br /><br />Bye!Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com1tag:blogger.com,1999:blog-34927953.post-91736508683557211622009-05-04T20:13:00.000-07:002009-05-04T22:36:42.655-07:00Typed Lambda Calculus For Me (And Maybe You)I'm reading chapter 10 of <a href="http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521898850">Lambda-Calculus and Combinators</a> 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.<br /><br />In the book there is this nugget:<br /><pre><br />(λx:p->ø->t.<br /> (λy:p->ø.<br /> (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t<br /> ):A<br />):B<br /></pre><br />You (the reader) are supposed to solve this for A and B. <br /><br />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. <br /><br /><h3>Explicit Type Information</h3><br />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:<br /><ol><li>x:p->ø->t</li><br /><li>y:p->ø</li><br /><li>z:p</li></ol><br />In more detail:<br /><ol><li>x is a function that takes a p and returns a function that takes an ø and returns a t.</li><br /><li>y is a function that takes a p and returns an ø</li><br /><li>z is simply a p</li></ol><br />Or in Scala:<br /><ol><li>val x:p=>ø=>t</li><br /><li>val y:p=>ø</li><br /><li>val z:p</li></ol><br />How do we know this? Well, that's basic typed lambda calculus. Here are a couple of very basic notes:<br /><ol><li>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.</li> <br /><li>The return value of the function in this tiny example is M (above is much more complicated, but that's what were getting to).</li></ol><br /><h3>Function Application</h3><br />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. <br /><br />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.<br /><br />In the original statement, we had (x:p->ø->t z:p):ø->t, and this is correct, as I just explained. <br /><br />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 ø. <br /><br />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. <br /><br /><h3>Building Functions</h3><br />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<br /><br />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. <br /><br /><h3>Solving for A</h3><br />Lets take a look back to remember what were trying to solve. One thing we need to find is A:<br /><pre><br />(λy:p->ø.<br /> (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t<br /> ):A<br /></pre><br />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 ø. <br /><br />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). <br /><br />A is (p->ø)->(p->t).<br /><br /><h3>Solving for B</h3><br />To Solve for B, we do <i>exactly</i> what we did solving for A.<br /><br />Recall:<br /><pre>(λx:p->ø->t.<br /> (λy:p->ø.<br /> (λz:p.((x:p->ø->t z:p):ø->t (y:p->ø z:p):ø):t):p->t<br /> ):A<br />):B<br /></pre><br />Or:<br /><pre>(λx:p->ø->t.whatever:A):B</pre><br />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. <br /><br />So B is (p->ø->t)->A<br /><br />And fully expanded:<br /><br />B is (p->ø->t)->(p->ø)->(p->t)<br /><br /><h3>Formal Listing</h3><br />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.<br /><br /><pre><br />x:p->o->t z:p y:p->o z:p<br />----------------- ---------------<br /> (xz):o->t (yz):o<br />--------------------------------------------<br /> (xy(yz)):t <br /> -----------------------<br /> (λx:p.(xy(yz))t):p->t<br />-----------------------------------------------<br />(λy:p->o((λx:p.(xy(yz))t)p->t)): (p->o)->(p->t)<br />------------------------------------------------<br />(λx:p->o->t ((λy:p->o((λx:p.(xy(yz))t)p->t)): <br /> (p->o)->(p->t))): (p->o->t)->(p->o)->(p->t)<br /></pre><br /><h3>The Scala Code To Prove It</h3><pre><br />trait Lambda {<br /> type p<br /> type ø<br /> type t<br /> type A = (p=>ø)=>(p=>t)<br /> type B = (p=>ø=>t)=>A<br /><br /> val f:B = {(x: p => ø => t) => {(y: p => ø) => {(z: p) => {(x(z)(y(z)))}}}}<br />}<br /></pre>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com2tag:blogger.com,1999:blog-34927953.post-5239342062953138772009-04-25T22:53:00.000-07:002009-04-25T23:06:32.561-07:00Scala Testing Presentation OutlineHere'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.<br /><br />Without further ado:<br /><pre><br />1) The prereqs ... Just Java code<br /> a) "Production" code<br /> - A simple List interface<br /> - An ugly LinkedList implementation<br /> b) Testing Java with Java<br /> - JUnit<br /> - Testng<br /><br />2) The basics ... Testing Java code with Scala<br /> a) JUnit with Scala<br /> - JUnit3 (test, setup/teardown)<br /> - JUnit4 Annotations<br /> b) TestNG with Scala<br /> - @Test<br /> - @DateProviders<br /> - All Annotations available<br /><br />3) The basics ... More testing Java with Scala - Intro to ScalaTest<br /> a) Suite<br /> - test methods<br /> - assert with ===<br /> - expect(x){}<br /> - intercept<br /> b) BeforeAndAfter<br /> c) TimedTest (displays time information for each class and test ran)<br /> d) TestNGSuite<br /> - decorate original TestNG test from step 3, "with TestNGSuite"<br /> - run in both runners<br /><br />4) Scala extending/implementing Java classes/interfaces<br /> a) ScalaLinkedList (simple extention of Java LinkedList class)<br /> b) ScalaMutableList (ugly impementation of simple List interface)<br /><br />5) Testing Scala with Scala<br /> a) Briefly redo #4 - but by testing the new Scala code. <br /> b) minor intermission - Can we backtrack and test the new Scala code with Java?<br /><br />6) A nicer, Functional List implemention in Scala<br /><br />7) Testing Scala with Scala<br /> a) FunSuite<br /> -(including HOF's for those who don't know...maybe?)<br /> -explain how tests methods work<br /><br />8) Advanced ScalaTest<br /> a) ScalaTest matchers (in a FunSuite)<br /> b) Overview of OOTB matchers<br /> -String, List, Hash, Option matchers, etc.<br /> c) Combining matchers with and/or<br /> d) Extending ScalaTest matchers - Creating your own matchers<br /><br />9) Specs<br /> a) Specifications<br /> b) Matchers<br /> c) Extending Specs matchers - Creating your own matchers<br /><br />10) Mocking in Scala (via Specs)<br /> a) Mockito<br /> b) JMock<br /><br />11) ScalaCheck (via ScalaTest Checkers)<br /> a) Properties<br /> b) Generators<br /> c) Arbitrary Magic<br /><br />12) Ant<br /> a) ScalaTest<br /> b) JUnit Scala and Java run together<br /> c) Specs runs as JUnit<br /> d) TestNG Scala and Java run together<br /><br />13) Scala Frameworks Interoperability<br /> a) ScalaTest and Specs<br /> b) ScalaTest and ScalaCheck<br /> b) Specs and ScalaCheck<br /></pre>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com4tag:blogger.com,1999:blog-34927953.post-52608098632607646372009-04-19T18:18:00.001-07:002009-04-19T18:30:12.956-07:00IntelliJ Now Supports ScalaTestIntelliJ 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.<br /><br />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.<br /><ol><br /><li>Click "Edit Configurations" in the Run menu dropdown (right next to the green play arrow).</li><br /><li>Click the + button to add a new run configuration. This brings up a dropdown containing different runners.</li><br /><li>ScalaTest is in the list, choose it.</li><br /><li>Fill in the classname of your test by typing it, or selecting the "..." button to bring up the class finder dialog.</li><br /><li>Click ok.</li><br /><li>Run!</li><br /></ol>Thanks IntelliJ Scala guys! Now if you can only get that right click thing working...Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com3tag:blogger.com,1999:blog-34927953.post-67831524826043722852009-04-19T11:46:00.000-07:002009-04-19T13:08:23.646-07:00Quotes<h4>Quote from <a href="http://gbracha.blogspot.com/">Gilad Bracha</a></h4><blockquote><span style="font-style: italic;">"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."</span></blockquote><br />Gilad is one of my heroes. The work he's doing on Newspeak seems very, very promising.<br /><br />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 <a href="http://jackcoughonsoftware.blogspot.com/2009/02/nyse-new-york-scala-enthusiasts.html">something in common</a> with such a smart guy.<br /><br /><h4>Quote from <a href="http://www.microsoft.com/presspass/exec/techfellow/hejlsberg/default.mspx">Anders Hejlsberg</a></h4>From <a href="http://oreilly.com/catalog/9780596515171/">Masterminds of Programming</a>, which is (so far) an absolutely fabulous book: <blockquote><span style="font-style: italic;">"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.<br /><br />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."</span></blockquote><br />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.<br /><br /><h4>Quote from Bill Venners</h4><blockquote><span style="font-style: italic;">"I charge $1 for each paren, and $598 for knowing where to put them!"</span></blockquote><br />'Nuff said!Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com0tag:blogger.com,1999:blog-34927953.post-71435222624603114242009-04-17T12:07:00.000-07:002009-04-17T17:57:09.979-07:00Tests and Booleans and MatchersI 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:<br /><font color="#6698FF"><pre><br />Nil.empty must be(true)<br /></pre></font><br />This seems harmless enough, but when I made it fail intentionally the error message I got was something reasonably similar to:<br /><font color="#6698FF"><pre><br />Expected true but got false.<br /></pre></font><br />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:<br /><font color="#6698FF"><pre><br />Nil.empty must be(true, "expected Nil to be empty, but it wasn't!")<br /></pre></font><br />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:<br /><font color="#6698FF"><pre><br />Nil must be('empty)<br /></pre></font><br />If this fails, it will give a nice error message like:<br /><font color="#6698FF"><pre><br />Nil was not empty<br /></pre></font><br />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.<br /><br />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:<br /><font color="#6698FF"><pre><br />def surroundedBy( s: String ) = startsWith(s) && endsWith(s)<br /></pre></font><br />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.<br /><font color="#6698FF"><pre><br />"htth".surroundedBy( "h" ) must be (true)<br />"http".surroundedBy( "h" ) must be (false)<br /></pre></font><br />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:<br /><font color="#6698FF"><pre><br />"htth" must be surrounded by "h"<br />"http" must not be surrounded by "h"<br /></pre></font><br /><h3>Matchers</h3><br />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:<br /><font color="#6698FF"><pre><br />case class surroundedBy(r:String) extends BeMatcher[String] {<br /> def apply(l: String) =<br /> MatchResult(<br /> l.surroundedBy(r),<br /> l + " was not surrounded by " + r,<br /> l + " was surrounded by " + r<br /> )<br />}<br /></pre></font><br />And our client test code turns out to be pretty close to the English:<br /><font color="#6698FF"><pre><br />"htth" must be(surroundedBy("h"))<br />"http" must not be surroundedBy("h")<br /></pre></font><br />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:<br /><font color="#6698FF"><pre><br />assert( "htth".surroundedBy("h") === true,<br /> "expected http to be surrounded by h, but it wasnt." )<br />assert( "http".surroundedBy("h") === false,<br /> "expected http not to be surrounded by h, but it was!!!" )<br /></pre></font><br />This is less readable code, but it is <span style="font-style: italic;">less</span> 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:<br /><font color="#6698FF"><pre><br />"htth".surroundedBy("h") must be(true,<br /> "expected htth to be surrounded by h, but it wasnt.")<br /></pre></font><br />or better:<br /><font color="#6698FF"><pre><br />"htth" must be('surroundedBy, "h")<br /></pre></font><br />I could see this one existing easily. It's really nice, but not type safe.<br /><br />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:<br /><br />When testing methods that return booleans you can<br /><ul><br /><li>Use the symbol style ('empty) if the method takes no arguments and you aren't terrible concerned about type safety.</li><br /><li>Use old school assertions when the method takes arguments but you won't have a lot of repetitive tests for the method.</li><br /><li>Use a custom matcher otherwise</li><br /></ul><br />You'll also find that ScalaTest (and Specs which is unfortunately not covered here) provides many matchers that can use for many common types.<br /><br />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.<br /><br />In the meantime, you can look at <a href="http://www.artima.com/weblogs/viewpost.jsp?thread=246279">ScalaTest Matchers</a> and <a href="http://code.google.com/p/specs/wiki/MatchersGuide">Specs Matchers</a>.<br /><br />Here's all the custom matcher code:<br /><font color="#6698FF"><pre><br />package org.scalatest.examples<br /> <br />import org.scalatest.matchers.MustMatchers._ <br />import org.scalatest.matchers._<br /><br /><br />class MatcherTest extends FunSuite with MustMatchers{<br /> <br /> implicit def surroundable[T](l:String) = new {<br /> def surroundedBy(r:String) = l.startsWith(r) && l.endsWith(r)<br /> }<br /> <br /> case class surroundedBy(r:String) extends BeMatcher[String] {<br /> def apply(l: String) = <br /> MatchResult(<br /> l.surroundedBy(r), <br /> l + " was not surrounded by " + r, <br /> l + " was surrounded by " + r<br /> )<br /> }<br /> <br /> test("weve got the place surrounded"){<br /> "htth" must be(surroundedBy("h"))<br /> "http" must not be surroundedBy("t")<br /> }<br />}<br /></pre></font>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com13tag:blogger.com,1999:blog-34927953.post-13795193453184978752009-04-12T20:34:00.000-07:002009-04-12T20:51:34.697-07:00ScalaTest IDE Support coming soon.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.<br /><br />Until then, anyone using FunSuite can borrow this code and temporarily use MiniFunSuite instead. This all seems to work quite well.<br /><br />Here's the client/test code:<br /><font color="#6698FF"><pre><br />class FunSuiteExample extends FunSuiteTestNGAdapter{<br /> test("hey"){ println("hey") }<br /> test("fail"){ assert( 1 === 2 ) }<br />}<br /></pre></font><br />And here's the library code:<br /><font color="#6698FF"><pre><br />import org.scalatest.testng.TestNGSuite<br />import org.testng.annotations.{DataProvider, Test}<br /><br />trait MiniFunSuite{<br /> var testMap = Map[String, Function0[Unit]]()<br /> def test(name:String)(f: => Unit) = testMap += (name -> f _)<br />}<br /><br />trait FunSuiteTestNGAdapter extends MiniFunSuite with TestNGSuite{<br /><br /> @DataProvider{ val name="tests" }<br /> def tests = testMap.map{ case (s,f) => Array(s,f) }.toList.toArray<br /><br /> @Test{ val dataProvider = "tests" }<br /> def scalaTest(testName:String, f: => Unit) = { f }<br />}<br /></pre></font>Josh Coughhttp://www.blogger.com/profile/04509343962912103631noreply@blogger.com1