In software development there are no silver bullets, but I am always looking out for the next bronze one.

Friday, October 29, 2010

Code Kata for Parallel Programming

    One of the keynote presentations at the Strange Loop 2010 conference in St. Louis was
Guy Steele's "How to Think about Parallel Programming: Not!."


    One of the examples in the presentation was counting words in a presumably large text file. He showed example code in Fortress of how one could go about taking a "divide-and-conquer" approach to the problem. This approach would divide the work into chunks that could be processed in parallel and then the outputs would be aggregated to form the solution.


    Noticing some of the syntactic similarities between Fortress and Scala, I had the impulse to implement a solution in Scala. During Dean Wampler's "Scalable Concurrent Applications with Akka and Scala" talk, I got the idea that that would make a good code kata to use and learn Akka.


    My final idea for the kata modifies the problem from counting words to finding sequences of digits where the last digit is the sum of its immediately preceding digits of any length. The input would be stream of non-zero digits. For example, the content below contains sequences "1326", "415", "246" and "617".


8745648184845171326578518184151512461752149647129746915414816354846454

    Such "sum sequences" should be listed only once in the solution and in the order they are found in the input. Limiting the input to non-zero digits simplifies the problem a little bit since many consecutive zeros would produce a solution that will grow exponentially.


    My initial implementations for this will use Scala and Akka including one using remote actors. Over the coming months, I hope to have time to implement solutions in other languages, such as F#, Clojure and Erlang, using their various parallel programming / concurrency libraries. Hopefully others will find this problem compelling and implement such solutions as well.

No comments: