Archive

Archive for the ‘scala’ Category

Java Concurrency Pitfalls (in Scala) Answers

May 10th, 2011 3 comments

Recently, Cay Horstmann posted a dozen Java concurrency pitfalls ported to Scala for extra pitfalliness. I had fun figuring them out. Here’s what I came up with.

I won’t copy all the code here, just provide my answers.

  1. The var stop isn’t synchronized in any way (synchronized, AtomicBoolean, etc) so there’s a chance that when it’s set to false, the change won’t be seen in the thread.
  2. Here, stop is an AtomicBoolean, fixing the issue in problem #1. That’s good. However, if doSomething() throws an exception done.put("DONE") will never execute and done.take() will wait forever.
  3. Here, Thread.run() is called rather than Thread.start(). The so-called “BackgroundTask” will actually run in the “foreground”
  4. ConcurrentHashMap.keySet().toArray will give a “weakly consistent” snapshot of the keyset at the time of the call. By the time it returns, the keys in the map may have changed completely.
  5. Oops. A string literal is used for the lock meaning that all instances of Stack will most likely share the same lock.
  6. Oops. A new “lock” is created every time push() is called, which is just as good as no lock.
  7. Here values is mercifully synchronized, but the var size isn’t. That is, if size is used in any other methods it may not be synchronized correctly.
  8. A do/while is used for the condition variable rather than just while. If cond is in a signaled state initially, the condition that size is zero may not be checked.
  9. If out.close() throws an exception, the myLock.unlock() will not be executed.
  10. Here, a string is being added to a blocking queue within a UI event handler. If the queue is full, queue.put() will block causing the UI to become unresponsive.
  11. I’m not totally sure with this one. I can think of a few things that could go wrong. First, if a listener is added or removed while fireListeners() is executing, you could get a ConcurrentModificationException. I think so anyway. I wasn’t able to find any indication of how ArrayBuffer iteration handles this. Second, since the listeners are notified with the lock held, you’ll almost certainly get a deadlock eventually, usually a lock inversion with some other thread that’s calling SwingUtilities.invokeAndWait().
  12. Ridiculously, SimpleDateFormat is NOT THREADSAFE! So using the same formatter from multiple threads is a recipe for sadness.

I wonder what I missed.

Cheers!

Remedial Scala: Interpreting Scala from Scala

January 25th, 2009 1 comment

For my “learning Scala” project, rooscaloo, I needed to dynamically generate and compile Scala code as rules are loaded into the engine. I had initially intended to do this as an internal DSL, but I honestly couldn’t think of a way to handle the fact that variables are bound at match time in the rete network. This is a learning project anyway, so I decided to just generate code and compile it.  Now, I could have sworn I had seen a Scala scripting example using JSR-223 in a blog somewhere, but couldn’t find it again.  I only found one very basic example of how to do this, in the Scala bug tracker. So I figured I’d write down what I came up with.

Note that this code makes use of the scala.tools.nsc package which is not part of the standard Scala library. Thus, it may change in future versions of Scala. Also note that after the fact, I was able to track down two partial JSR-223 implementations here and here. It’s comforting that I ended up in basically the same place.

The example given in the bug tracker works, but it’s very simple and there are two things it doesn’t do. First, it prints all its output to stdout, including error information. Second, it doesn’t show how to retrieve results from executing scripts. That is, code goes in, but nothing comes out. These are both solved pretty easily.  In the first case, we simply supply our own PrintWriter when instantiating the internal Scala interpreter:

  private val writer = new java.io.StringWriter()
  private val interpreter = new ScalaInterpreter(new Settings(), 
                                                 new PrintWriter(writer));

  ...

  def exec(code : String) {
    // Clear the previous output buffer
    writer.getBuffer.setLength(0)

    // Execute the code and catch the result
    val ir = interpreter.interpret(code);

    // Return value or throw an exception based on result
    ir match {
      case Success => ()
      case Error => throw new ScriptException("error in: '" +
                                              code + "'\n" + writer toString)
      case Incomplete => throw new ScriptException("incomplete in :'" + 
                                                   code + "'\n" + writer toString)
    }
  }

For the second issue, returning results, I had to think a little longer, probably longer than necessary. scala.tools.nsc.Interpreter doesn’t return anything besides Success, Error, or Incomplete as seen above. But, you can pass objects in, so I ended up creating a container object to hold the result:

class ResultHolder(var value : Any)

  ...

  def eval(code : String) : Any = {
    // Clear the previous output buffer
    writer.getBuffer.setLength(0)

    // Create an object to hold the result and bind in the interpreter
    val holder = new ResultHolder(null)
    bind("$result__", holder);

    // Execute the code and catch the result
    val ir = interpreter.interpret("$result__.value = " + code);

    // Return value or throw an exception based on result
    ir match {
      case Success => holder.value
      case Error => throw new ScriptException("error in: '" + 
                                              code + "'\n" + writer toString)
      case Incomplete => throw new ScriptException("incomplete in :'" + 
                                                   code + "'\n" + writer toString)
    }
  }

As you can see, I ended up with two separate routines. exec executes a Scala statement, ignoring its return value. This is useful for imports, class declarations, anything that does not evaluate to a value.  eval executes a Scala statement, catches the result and returns it.

Anyway, that’s about it. It seems that full JSR-223 support is in the plan for Scala. Until then, what I have here works for me and it was a good learning experience. Here’s the full source for my solution.

Categories: scala Tags: ,

Remedial Scala: XML

January 21st, 2009 2 comments

Tonight I finally got to the XML chapter of Programming in Scala. I was excited because I had seen a few examples on the web and wanted to try something out that wasn’t jdom or jax-b or whatever. So, I read the chapter and it was … short. The authors even admit in the conclusion that it barely scratches the surface and I have to agree :)

Anyway, my exercise for Scala’s XML support was adding an XML encoding of rules to rooscaloo. My plan is to eventually write a parser with parser combinators, but that’s not until chapter 31.

Overall, Scala’s XML support is a dream compared to anything I’ve done in Java before. I began by creating some case classes for my AST:

  case class RuleAST(name : String,
                     fireCode : String, unfireCode : String,
                     conditions : ConditionAST*)

  case class ConditionAST

  case class ObjectConditionAST(typeName : String,
                                binding : String,
                                testCode : String) extends ConditionAST

  case class NotAST(children : ConditionAST*) extends ConditionAST

really simple stuff.  Here’s what a rule looks like in XML:

    <rule name="bob-is-not-a-cat-lover">
      <if>
        <object type="Person" binding="p"> p.name == "bob" </object>
        <not>
            <object type="Cat" binding="c"> c.owner == p </object>
        </not>
      </if>
      <then>println("bob does not fancy cats")</then>
      <unfire>Tprintln("bob now owns a cat!")</unfire>
    </rule>

(I couldn’t think of a better name for rule retraction than unfire…)

and here’s the satisfyingly compact code to convert an XML node to a RuleAST object:

  def parseRule(node: scala.xml.Node) : RuleAST =
    RuleAST(node \ "@name" text,
            node \ "then" text,
            node \ "unfire" text,
            parseConditionList(node \ "if" \ "_") : _*)

  def parseConditionList(xml : scala.xml.NodeSeq) : Seq[ConditionAST] =
    for(e <- xml)
      yield e match {
        case <object>{ _* }</object> => parseObjectCondition(e)
        case <not>{ _* }</not> => parseNot(e)
      }

  def parseObjectCondition(xml : scala.xml.Node) : ObjectConditionAST =
    ObjectConditionAST(xml \ "@type" text, xml \ "@binding" text, xml.text)

  def parseNot(xml : scala.xml.Node) : NotAST =
    NotAST(parseConditionList(xml \ "_") : _*)

This could actually be much more compact but I chose to break it up into methods so I could test each construct individually. Still, I’m fairly certain there’s an even better way to do this, but this represents 45 minutes of work including unit tests, so I’m still pretty happy. One thing I discovered that wasn’t covered in the book was the use of the “_” wildcard to get all sub-elements of a node. For example we can see above that I use:

   node \ "if" \ "_"

to get the list of all child elements of the <if> node.

The match statement in parseConditionList is a little irritating to me and I feel like there’s probably a better way to do that.

Just like the book, I’ve obviously only started to scratch the surface of  Scala’s XML support. Since I also just read the chapter on extractors, it seems like it might be interesting to define extractors to automatically convert XML to an AST. Of course, there’s also XPath, transforms, etc.

Maybe tomorrow night. It’s time to sleep.

p.s. here are some more Scala XML resources I’ve found useful:

Categories: scala Tags: ,

Remedial Scala: Emulating C# Extension Methods

January 17th, 2009 4 comments

I admit that, as a Java programmer, I’ve been jealous of C#’s extension methods for a while. Java’s getting pretty long in the tooth. While C# is adding lots of cool new features, Sun doesn’t have the balls to even add closures despite three working implementations to choose from.  I get bimonthly reports from a former co-worker and C# aficionado of this or that cool feature that Java will never have.  He loves to rub it in.

I know that extension methods are just syntactic sugar and any Lisp adherent will tell you they’re really just a poor man’s version of generic functions.  But I want them nonetheless.

So, forget about Java. I’m pleased to say that in Scala it is easy to emulate extension methods. Here’s Microsoft’s example code in C#:

namespace ExtensionMethods
{
    public static class MyExtensions
    {
        public static int WordCount(this String str)
        {
            return str.Split(new char[] { ' ', '.', '?' },
                             StringSplitOptions.RemoveEmptyEntries).Length;
        }
    }
}

this just adds a WordCount method to the built in string class. Here’s the equivalent code in Scala, with a main method for good measure:

object Main {

  implicit def stringToWordCounter(s : String) = {
    new {
      def wordCounts : Int = {
        s.split(Array(' ', '.', '?')).map(_ trim).filter(! _.isEmpty).size
      }
    }
  }

  def main(args: Array[String]) {
    println("Hello Extension Methods".wordCounts)
  }

}

This makes use of Scala’s support for implicit conversions. If a method is called on an object that doesn’t exist on that object’s base type, the compiler searches for an implicit method (stringToWordCounter in this case) that converts to a type that does have that method. stringToWordCounter converts implicitly to a anonymous class that just happens to have a wordCount method. Cool. Note that the returned type can have any number of methods and may also implement traits (interfaces).

One thing I don’t know about is performance. Implicit conversions mean constructing a new intermediary object to call the method on. Maybe the compiler is smart? Anyway, this is remedial Scala, so I’ll worry about that later.

Also of note in this example is how much nicer the code to split, trim, and filter the input string is. I’m assuming there’s some other, more functional way to do this in C# without resorting to the long-winded StringSplitOptions.RemoveEmptyEntries flag.

That’s it for today’s installment of Remedial Scala. See you next time.

Categories: scala Tags: , ,

Remedial Scala : Repeated Parameters and Initializing Collections

January 13th, 2009 2 comments

I  only recently began to learn Scala (rooscaloo is coming along nicely, btw). I’m having a great time and the scala-user mailing list has been a great resource for learning more idiomatic ways to express myself in Scala. Every couple of days I ask a dumb question which ends up teaching me a lot about the language. So I figured I’d write about what I learn, even if it’s at a much lower plane of existence than a lot of other Scala commentary that’s out there.  Hopefully another neophyte may someday find this informative.

Repeated Parameters

Today’s lesson is about two things that I didn’t initially know were related. First, I wanted to know how to initialize a map with a list of pairs. The Scala Map constructor take a variable list of pairs (a repeated parameter) to initialize the map. For example:

   scala> val map = Map((1, 2), (3, 4))
   map: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

But, I have a list of pairs, not a parameter list.  So, here’s what I was doing:

   val map = Map() ++ listOfPairs

which worked fine. Basically, it takes an empty map and adds the pairs in the list. It smells a little though and I was sure this wasn’t idiomatic. So I asked. The correct answer is the _* operator of course:

   scala> val args = List((1, 2), (3, 4))
   args: List[(Int, Int)] = List((1,2), (3,4))

   scala> val map = Map(args : _*)
   map: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

When a parameter is followed by “: _*”, this tells Scala to expand the argument to a variable argument list rather than a single argument.  Funny enough, I actually knew this from chapter 8 of the Programming in Scala book, but sometimes I forget things…

So, this explains why all of the Scala collection types take just a repeated parameter list for initialization rather than another collection like the Java collections library.

Turning an Option into a Set

The revelation above led directly to the solution for my other problem. In particular, I wanted a nice way to convert an Option (think of it as a collection with exactly 0 or 1 elements) to a Set. I had this code:

  def toSet[T](o : Option[T]) : Set[T] = {
    o match {
      case Some(some) => Set(some)
      case None => Set()
    }
  }

which works fine, but …

It turns out that Option has a toList method so I can pass it to a repeated parameter list to initialize a collection from an Option:

   scala> val s = Set(Some(1).toList : _*)
   s: scala.collection.immutable.Set[Int] = Set(1)

and:

   scala> val s = Set(None.toList : _*)
   s: scala.collection.immutable.Set[Nothing] = Set()

Pretty cool … Ok, so it isn’t exactly pretty and I stayed with my utility function just for readability, but it’s nice when a language has this kind of consistency where the solution to one problem crops up over and over again.

Remedial, eh?

Categories: scala Tags:

Getting to know Scala

January 10th, 2009 3 comments

It’s conventional wisdom that a programmer should probably learn one new language every year. By my count, in my 10 years as a “professional” programmer I’ve done non-trivial projects in eight languages (chronologically: Matlab, C, C++, Visual Basic, Lisp, Tcl, Python, Java). So, I’ve got a pretty good average, but a lot of that was concentrated in the first several years. For that last few years, I’ve been in a mostly Java rut for better or worse.  In an attempt to break the monotony, I started learning Scala shortly before the New Year. From the web site:

Scala is a general purpose programming language designed to express common programming patterns in a concise, elegant, and type-safe way. It smoothly integrates features of object-oriented and functional languages. It is also fully interoperable with Java.

Scala appeals to me on a few fronts. First, it’s functional aspects are an area I really haven’t had much experience with other than a brief stint in Lisp many years ago and an occasional lambda in Python. Second, because it runs on the JVM, there’s a somewhat compelling case that I could actually use it on a project someday without throwing out all of my Java work from the past few years.

Getting Started

I started out by reading Ted Neward’s excellent series of articles on Scala. I read them just to get a feel for the language, but never actually tried running any code. After reading that series, I decided to take the plunge and bought the brand new Programming in Scala book in both digital and analog forms.  It’s really a pretty good book. It’s well written and doesn’t gloss over technical details. The book is technically a tutorial which means it introduces the language in stages. Overall, this is a good approach, but there were a few points that were teasers for later chapters that I wish they would have covered immediately. Two examples:

  • The idea of companion objects for “new-free” constructors like List() and Map() is mentioned early on, but they don’t say how to actually do it until much later. I wanted to know right then!
  • They briefly discuss val vs. var. vs. def and the UniformAccess Principle, without giving an example. I had to hunt through the rest of the book to find out how to implement it.

So now I had the book, time to write some code…

The Project

Oh, first I guess I should say what my “learning Scala” project is. I’m building a very simple, very naive rules engine, rooscaloo, in the spirit of Drools or Ruleby. In a nutshell, users write rules that match patterns in memory and do something interesting when a match occurs.  Memory is populated by facts, which in my case are just plain old Scala objects. The matcher is a simple implementation of a rete network which has a lot of list manipulation and traversal which I hoped would map nicely onto Scala’s functional capabilities.

Choosing an IDE

First I had to decide on an IDE. The Scala compiler, scalac, is a command-line tool, so of course, vim + ant or something was always an option. But, I’m old and lazy now, so if I can transfer my [ctrl + space] programming habits from Java to Scala, you better believe I will.

Since I’m generally partial to Eclipse, I first tried out the Scala Eclipse plugin. A somewhat sad trend I’ve noticed in the Eclipse universe is that the core Java tools, the JDT, are generally rock solid and everything else (including the several Eclipse plugins I’ve built myself) just doesn’t work that well.  The complexity of the Eclipse API, especially the threading model, can’t help much.

Anyway, I installed the plugin, created a test project and things seemed to work pretty well.  I started coding and went to add my first unit test. Since I know JUnit, and like Eclipse’s green bar, I went with that. I added the JUnit library to the project in the usual way and … my unit test code wouldn’t compile, couldn’t find JUnit. I fiddled around with manually adding the JUnit jar, restarting Eclipse and some other stuff and eventually got it to work, but wasn’t that confident. As a test, I tried creating a fresh Scala project and immediately adding JUnit support and that worked flawlessly.  These are the little details of Eclipse plugin development that really kill you.

Finally, I continued coding, and at some point decided to rename a file. This was a mistake. It basically killed Eclipse, flooding it with errors and leaving the project in a really weird state when I restarted. That ended it for me. I really need to be able to rename files.

My next stop was the NetBeans Scala plugin. For most Java development, I’ve generally found NetBeans pretty inferior to Eclipse. The editor is more clunky, and having to manually build my code just seems prehistoric.  Anyway, I gave the Scala plugin a try and so far, I’ve been pretty happy with it. JUnit support “just worked”. Code completion works about as much as I’d expect it to (maybe 50%, so worse than Java, but better than a lot of dynamic languages), the editor is bearable, and the debugger seems to work fine.

The only issue I’ve had is that one of my source files seems to give the editor (or compiler, or whatever is behind the editor) fits. I’ll type a character (any character) and the whole UI will freeze for a few seconds.  I’ve seen similar issues reported on the scala-tools mailing list, so maybe it’s a more general problem.

I’ll stick with NetBeans I guess until something better comes along.

Language Highlights

I’ve only scratched the surface of Scala (and actually only gotten through the first 16 chapters of the Scala book), so here I’ll just present my favorite parts of the language that I’ve actually used.

Now that I’ve written it, this is a pretty haphazard list. I’m going to leave it though mostly because I’m too tired to rethink what I want to say…

Option[T]

Option[T] is a Scala datatype that encapsulates the sentinel value role usually filled by null in Java. For example, in Java, Map.get() returns null if the value isn’t present. This is an incredibly common pattern.  Because of it, I spend my programming time trying to decide whether a method can return null or whether it is safe to pass null as an argument to a method, etc. Sometimes it’s documented, others I have to guess or just test and see what happens. Option[T] has two possible values: Some and None. Some holds a non-null instance of a type T. By consistently using Option[T] in APIs, client code is forced to check for null return values and knows when a parameter accepts a null value. Testing for null (None, actually) is done with Scala’s really cool pattern matching construct:

    val name = getUserName()
    name match {
        case Some(n) => println("User name is " + n)
        case None =>    // Do nothing
    }

This can get a little tedious, but Scala has a nice solution. First, I’ve found it useful to think of a Option[T] as a collection of T that can hold exactly 0 or 1 values. Each collection in Scala has a foreach that takes a function to execute on the members of the collection. So, Option[T] has a foreach method as well. The pattern match above translates to the following foreach call:

    getUserName().foreach(println("User name is " + _))

foreach, map, and friends

Scala collections support functional iteration, that is you pass a function to the collection and it is called for each member in the collection. This is such an improvement over Java, even Java’s kinda new for-each construct. Here’s an example of rete left activation from my project:

    val nt = newToken(Some(token), item)
    children.foreach(_.leftActivate(nt))

In Java this would look something like:

    final Token nt = newToken(token, item);
    for(BetaMemoryChild child : children)
    {
        child.leftActivate(nt);
    }

which isn’t that bad, but it really adds up, especially when the body of the loop is more complicated, or if the member type is something like Map.Entry<String, Person>.

Type Inferencing

As indicated in the examples above, Scala uses type inferencing which means it figures out the types of variables based on what’s assigned to them.  This really cuts down on all the Java boilerplate while maintaining static typing. There’s a pretty good explanation here.

mkString()

This is a really stupid little thing, but every Scala collection has a mkString() method that takes a string delimiter and joins the values in the collection:

  scala> val r = List(1, 2, 3, 4, 5)
  r: List[Int] = List(1, 2, 3, 4, 5)

  scala> r.mkString(", ")
  res0: String = 1, 2, 3, 4, 5

If I had a nickel for every time I’ve written StringUtils.join() in a Java project …

Conclusion

Overall, after 10 days of use, I’m loving Scala. I think I’ve barely scratched the surface of what it can do. My little rules engine, rooscaloo, has been a pretty good driver for learning the language so far. It has enough algorithmic and data structure variety that I’ve been able to find ways to apply Scala constructs in many areas. It’s probably not going to be very efficient or powerful, but it will have served its purpose.

I’m looking forward to trying out parser combinators to define the rule language. Right now, I’m just building rules programmatically, which is still far easier and more readable than the equivalent Java code.  I initially thought I might be able to encode the rules as an embedded DSL in Scala with it’s incredibly flexible syntax, but I’m not sure I’ll be able to get the affect I want and I need an excuse to try out the parser stuff :)

Links

Below are some links to information on Scala that I’ve found particularly helpful:

I’ve also spent a little time on the Scala mailing lists and have found the community responsive and friendly.

Categories: scala Tags: , , ,