The last time I had occasion to work my way through SICP I found myself reading the first edition… because that’s all there was. So when some of my fellow developers at my day job started up a technical book club and led off with the second edition of SICP I was quite intrigued. This post reflects the first of (hopefully) several observations on re-reading a classic.

At a recent meetup for this book club one of the exercises in the book gathered a fair share of attention. That exercise, 1.11, can be found in the HTML version of the second edition and reads as follows:

Exercise 1.11.  A function f is defined by the rule that f(n) = n if n<3 and 
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3.   Write a procedure that 
computes f by means of a recursive process. Write a procedure that computes 
f by means of an iterative process.

We consider this problem from the perspective of Haskell, Scheme and Clojure. The sample code below was known to run correctly on GHC 6.12.1, Chicken Scheme 4.5.0 and Clojure 1.5.1 via Leiningen [1].

A Haskell version of the recursive process is almost a literal transcription of the problem statement:

1
2
3
4
5
6
7

recurFn :: Int -> Int
recurFn x
  | x < 3 = x
  | otherwise = a + (2 * b) + (3 * c)
  where a = recurFn (x - 1)
        b = recurFn (x - 2)
        c = recurFn (x - 3)

This translates into some fairly straightforward Scheme:

1
2
3
4
5
6
7
8

(define recur-fn
  (lambda (x)
    ;(printf "recur-fn, x=~s\n" x)
    (if (< x 3)
  x
  (+ (recur-fn (- x 1))
     (* 2 (recur-fn (- x 2)))
     (* 3 (recur-fn (- x 3)))))))

The problem is that we’ve also got a straightforward instance of tree recursion here. To highlight this fact uncomment the printf statement in the above code and compute the value of (recur-fn 4):

@stravinsky:~/git/sicp/1-11/scheme$ grep printf 1-11.scm 
    (printf "recur-fn, x=~s\n" x)
(printf "recur-fn for 4: ~s\n" (recur-fn 4))
@stravinsky:~/git/sicp/1-11/scheme$ csc 1-11.scm 
@stravinsky:~/git/sicp/1-11/scheme$ ./1-11 
recur-fn for 4: recur-fn, x=4
recur-fn, x=3
recur-fn, x=2
recur-fn, x=1
recur-fn, x=0
recur-fn, x=2
recur-fn, x=1
11

A moment of reflection should make it clear that this is exactly the behaviour you’d expect to see from tree recursion.

So what might an iterative solution look like? The base case of our recursive definition is f(0), f(1) and f(2) and larger values of f(x) build on smaller values so it seems fairly obvious that we want an ascending iteration from the values that make up our base case. At each iteration we might add the newly-computed value to a list of observed values, returning the last value from this list once we’ve iterated up to our input value [2]. Another moment of reflection allows us to see that what we’re describing is a fold which produces a list as it’s value. Fold (sometimes called reduce or, in really odd languages, inject… for no obvious reason [3]) is a higher-order function, a topic which will be covered in the next chapter.

One might object that a list of values, one for each index in our iteration, sounds a lot more like a map operation than a fold/reduce. And you’d be correct… so long as you don’t consider the inputs. A map operation is allowed a single input, in this case the index of an item in the list, and that input isn’t sufficient to compute values of f(x) for x >= 3; the history we need to consider is simply lost. But a fold/reduce operation introduces the notion of an accumulator (of some arbitrary type) which is also made available to our computation as a parameter. So long as that accumulator has access to the history of our computation our function has all the inputs it needs. And if our accumulator is nothing more than a repository of previously-computed values (in the form of, say, a list) we have exactly that history.

The key here is the realization that fold/reduce is isomorphic onto a recursive procedure which is also an iterative process:

1
2
3
4
5

(define my-fold
  (lambda (fn acc idxs)
    (if (= 0 (length idxs))
        acc
        (my-fold fn (fn (car idxs) acc) (cdr idxs)))))

So we crank out an implementation based on fold, using a few of the methods from SRFI-1 to simplify things just a little bit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(use srfi-1)

; Use some of the list manipulation methods from SRFI-1 to make our lives easier                                                                                                 (define iter-fn
  (lambda (x)
    (define compute-value
      (lambda (prevs)
        (letrec ((prevs-last (take-right prevs 3))
                 (c (car prevs-last))
                 (b (cadr prevs-last))
                 (a (caddr prevs-last)))
        (+ a (* 2 b) (* 3 c)))))
    (if (< x 3)
        x
        (letrec ((range (iota (- x 2) 3))
                 (fold-fn (lambda (x prevs) (append prevs (list (compute-value prevs)))))
                 (vals (fold fold-fn '(0 1 2) range)))
          (last vals)))))

For kicks we do a quick translation of the iterative process into Clojure, and don’t tell the Scheme people but there’s something to this “syntactic sugar” stuff. The use of destructuring here makes the function much more concise:

1
2
3
4
5
6
7
8
9

(defn iter-fn [x]
  (if (< x 3)
    x
    (let [compute-fn (fn [prevs]
                       (let [[c b a] (take-last 3 prevs)]
                         (+ a (* 2 b) (* 3 c))))
          reduce-fn (fn [col val] (conj col (compute-fn col)))
          vals (reduce reduce-fn [0 1 2] (range 3 (+ x 1)))]
            (last vals))))

Unfortunately the same can’t be said of the recursive process. Clojure can’t do much to save us here. Be forewarned; the code that follows is intended for mature audiences only. The multiple instances of recursion outside of the loop/recur forms is very likely to induce eye bleeding in any seasoned Clojure programmer:

1
2
3
4
5
6
7

; Recursive version... with sufficient eye bleeding
(defn recur-fn [x]
    (if (< x 3)
  x
  (+ (recur-fn (- x 1))
     (* 2 (recur-fn (- x 2)))
     (* 3 (recur-fn (- x 3))))))

[1] I’m finally starting to come around when it comes to Leiningen. Language-specific builders still irritate me, but at least this one seems sensible.

[2] We really only need to preserve three values in our list at any given time in order to maintain enough state to define the computation at every point. We could move to something like this in the future if necessary, but doing it now doesn’t do anything to enhance the logic of our solution.

[3] Ruby gets a pass here (but just barely) since it offers both inject and reduce. That said, I expect better from you, Ruby!

Originally published at Heuristic Fencepost

In an attempt to make my Ruby code a bit more idiomatic I’ve been spending a bit of time recently with Russ Olsen’s excellent Eloquent Ruby. There are many reasons to love writing Ruby code, not least of which is that Ruby deploys the same terse but expressive power of Perl while employing better overall principles of programming. The effect isn’t universal; on occasion my problems with Ruby look quite a bit like my problems with Perl. Given the overall elegance of the language it seems likely that there’s a “better” (or at least more idiomatic) way to accomplish my goal. And so I turn to Eloquent Ruby.

As an example of this tension consider the following example.

Perl has a well-deserved reputation for efficiently processing text files with regular expressions. We’ll consider an example from another text I’ve been spending a bit of time with: Hofstadter’s seminal Godel, Escher, Bach. A simple implementation of the productions of the MIU system in Perl [1] might look like the following:

1
2
3
4
5
6
7
8
9
10
11

# Simple implementation of the productions for the MIU system
open INFILE,"<",$ARGV[0];
while(<INFILE>) {

    chomp;
    next if $_ =~ /#.*/;
    print "$1IU\n" if $_ =~ /^(.+?)I$/;
    print "M$1$1\n" if $_ =~ /^M(.+)$/;
    print "$1U$2\n" if $_ =~ /^(.*)III(.*)$/;
    print "$1$2\n" if $_ =~ /^(.*)UU(.*)$/;
}

Reasonable enough, but there’s a lot of magic going on here. We’re relying on the “magic” variable $_ to access the current line, and to make things worse we have to obtain those lines using the INFILE identifier that only has meaning due to a side effect of the open() call [2]. There’s also those “magic” $1 and $2 variables for accessing capture groups in a regex.

The Ruby version is both slightly shorter and a bit cleaner:

1
2
3
4
5
6
7
8
9

# Simple implementation of the productions for the MIU system
File.new(ARGV[0]).readlines.each do |line |

  next if line =~ /#.*/
  puts "#{$1}IU\n" if line =~ /^(.+)I$/
  puts "M#{$1}#{$1}\n" if line =~ /^M(.+)$/
  puts "#{$1}U#{$2}\n" if line =~ /^(.*)III(.*)$/
  puts "#{$1}#{$2}\n" if line =~ /^(.*)UU(.*)$/
end

We’ve made some nice strides here. The use of File.new() allows us to avoid open() and it’s side effects. The use of a code block allows us to remove the global $_ in favor of a scoped variable line.

But we’re still stuck with $1 and $2 for those capture groups.

One can imagine an elegant object-oriented solution based on match objects. Any such implementation would have to accomplish three things:

• The match object will be used as the condition of an if/unless expression so nil should be returned if there’s no match
• The match object should be bound to a variable name in scope
• References to capture groups in the if-clause should use the scoped variable rather than the $1,$2, etc.

But remember, this exercise is only useful if we don’t have to compromise on elegance. If all we’re after is an explicit object-oriented solution we could go with the Python version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Simple implementation of the productions for the MIU system
from sys import argv
import re

re_c = re.compile("#.*")
re1 = re.compile("^(.+?)I$")
re2 = re.compile("^M(.+)$")
re3 = re.compile("^(.*)III(.*)$")
re4 = re.compile("^(.*)UU(.*)$")

for line in [line.strip() for line in open(argv[1])]:
    if re_c.match(line):
        continue
    m1 = re1.match(line)
    if m1:
        print m1.group(1) + "IU"
    m2 = re2.match(line)
    if m2:
        print "M" + m2.group(1) + m2.group(1)
    m3 = re3.match(line)
    if m3:
        print m3.group(1) + "U" + m3.group(2)
    m4 = re4.match(line)
    if m4:
        print m4.group(1) + m4.group(2)

That’s probably not what we want. [3]

After pondering this question for a bit we realize we may not be in such a bad spot. /regex/.match(str) already returns nil if there is no match so our first requirement is satisfied. Assignment is just another expression, so our match object (or nil) will be returned to the if-expression test, helping us with our second goal. And match objects provide access to capture groups using []. So long as the assigned variable is in scope we should have everything we need. A bit of scuffling [4] brings us to the following:

1
2
3
4
5
6
7
8
9
10
11

# Implementation of the productions for the MIU system with match objects
File.new(ARGV[0]).readlines.each do |line |

  next if line =~ /#.*/

  foo = nil
  puts "#{foo[1]}IU\n" if foo = /^(.+)I$/.match(line)
  puts "M#{foo[1]}#{foo[1]}\n" if foo = /^M(.+)$/.match(line)
  puts "#{foo[1]}U#{foo[2]}\n" if foo = /^(.*)III(.*)$/.match(line)
  puts "#{foo[1]}#{foo[2]}\n" if foo = /^(.*)UU(.*)$/.match(line)
end

This example is free of any “magic” variables, although we have sacrificed a bit on the clarity front. It’s also worth noting that we could have accomplished something very similar in Perl:

1
2
3
4
5
6
7
8
9
10
11

# Implementation of the productions for the MIU system with match objects
open INFILE,"<",$ARGV[0];
while(<INFILE>) {

    chomp;
    next if $_ =~ /#.*/;
    print "$foo[0]IU\n" if (@foo = ($_ =~ /^(.+?)I$/));
    print "M$foo[0]$foo[0]\n" if (@foo = ($_ =~ /^M(.+)$/));
    print "$foo[0]U$foo[1]\n" if (@foo = ($_ =~ /^(.*)III(.*)$/));
    print "$foo[0]$foo[1]\n" if (@foo = ($_ =~ /^(.*)UU(.*)$/));
}

This implementation is hardly idiomatic. It’s also quite a bit less clear than our earlier efforts in the language.

Where does this leave us? Do we keep in touch with our Perl roots and live with $1 in order to keep things terse and expressive? Do we sacrifice a bit of clarity and go with an object-oriented approach? Or do we do something else entirely?

Answers to this question (and others like it) are what I’m hoping to get out of Eloquent Ruby.

[1] We’re ignoring nasty things like error handling and complex edge cases in order to keep the conversation focused.

[2] We could use lexical file handles here but that doesn’t really change the underlying point. Even in that case we still have to call open() in order for $fh to be useful.

[3] Python does a lot of things very, very well, but this solution to this problem seems unnecessarily verbose.

[4] The requirement to declare foo in advance with this conditional modifier form was a bit surprising. Shifting to a more conventional if-test-end form removed this requirement, although this isn’t too surprising since you have an explicit assignment in the if test. The Perl version also didn’t require this advance declaration when using the conditional modifier form. An MRI quirk, perhaps?

Originally published at Heuristic Fencepost

In a semi-recent post we looked at how we might define actors in JRuby using a combination of Akka and code blocks. That post was very focused on the process of creating actors; we didn’t necessarily consider how to build systems with actors and/or whether Ruby might be helpful in doing so. There are plenty of issues to ponder here, but before we dig in let’s take a step back and talk briefly about some of the characteristics of actors.

Actors implement a shared-nothing model for concurrency. Mutable system state should be contained by one or more actors in the system. This state is not exposed to external entities directly; it can only be accessed or modified via messages sent to the actor. Since the actor is the only player in this drama that can access the state it contains there is no need to lock or synchronize state access. It should be fairly clear that an actor consists of some amount of mutable system state and some logic for handling incoming messages… and not much more.

Okay, sounds great… but how does it work in practice? We’ll consider this question by way of an alogrithm that by now should be pretty familiar: prime number generation using the Sieve of Eratosthenes. We considered this chestnut (or perhaps you prefer “war horse” at this point) in a previous post discussing an implementation of this algorithm in the Go language. Let’s review that implementation and see what else we can do with it.

The support of lightweight goroutines in Go encouraged a pipeline implementation with one goroutine per discovered prime. We can think of the “state” of this system as the total set of discovered primes. Each goroutine knows only about the prime it contains and the channel where candidates should be sent if they “pass” (i.e. do not divide evenly into it’s prime number). Once the goroutine is created it’s state doesn’t change. New state is added by creating a new goroutine for a newly-discovered prime. State is never deleted; once a prime is discovered removing it from consideration is non-sensical. As a consequence state is completely distributed; no entity in the system knows about all discovered primes.

We also note that the algorithm described here isn’t very friendly to parallel decomposition [1]. Candidate values are compared to previously discovered primes one at a time: if the candidate passes the test it’s allowed to move on, otherwise no further evaluation occurs. This technique is referred to as “fail-fast” behaviour; if a value fails a test it doesn’t lead to any wasteful extra work. The concurrent approach is quite different: compare the candidate to all discovered primes at once and return success only if all tests pass. Comparisons are done independently, so even if the “first” [2] comparison fails all other comparisons still execute. We lose our fail-fast behaviour but gain the ability to decompose the entire process into smaller jobs that can execute in parallel. A trade-off in engineering… surprising, I know.

We’ll set out to implement the Sieve of Eratosthenes in Ruby using JRuby and Akka. Our new implementation will have more of a bias towards parallelism; this time we’re okay with throwing away some work. Clearly we’ll need an actor to compare a candidate to one or more discovered primes; that is, after all, why we’re here. We can think of these actors as maintaining the state of our system (just like the goroutines in the Go implementation) so we’ll borrow a term from MVC and call these “model” actors. Concurrently evaluating candidates against these models implies an organizing actor that is aware of all models; it seems natural to call this the “controller” actor. To keep things simple we don’t want to support an unlimited number of models so we create a fixed-size “pool” and distribute system state (i.e. the set of discovered primes) between these models. When a new prime is discovered the controller will be responsible for adding that prime to an existing model.

The implementation in Ruby looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

require 'java'
require 'lib/akka-actor-1.2.jar'
require 'lib/scala-library.jar'

java_import 'akka.actor.Actors'
java_import 'akka.actor.UntypedActor'
java_import 'akka.actor.UntypedActorFactory'

module Sieve

  # Basic Enumerable wrapper for a Controller actor... just a convenience thing really
  class Primes
    include Enumerable

    def initialize(controller)
      @controller = controller
    end

    def each
      loop do
        yield @controller.sendRequestReply(:next)
      end
    end
  end

  # Enumerable implementation representing the set of prime number candidates > 10.  Use of an
  # enumerable here allows us to isolate the state associated with candidate selection to this
  # class, freeing up the model and controller actors to focus on other parts of the computation
  class Candidates
    include Enumerable

    def initialize
      # Note that this initial value is never actually returned; we're only setting the stage for the
      # first increment to generate the first candidate
      @next = 9
    end

    # Primes must be a number ending in 1, 3, 7 or 9... a bit of reflection will make it clear why
    def each
      loop do
        @next += (@next % 10 == 3) ? 4 : 2
        yield @next
      end
    end
  end

  class Controller < UntypedActor

    def initialize
      @models = 0.upto(3).map do |idx|
        model = Actors.actorOf { Sieve::Model.new }
        model.start
        model
      end

      # Seed models with a few initial values... just to get things going
      @seeds = [2,3,5,7]
      0.upto(3).each { |idx| @models[idx].tell [:add,@seeds[idx]] }

      @candidates = Candidates.new
    end

    # Part of the lifecycle for an Akka actor.  When this actor is shut down
    # we'll want to shut down all the models we're aware of as well
    def postStop
      @models.each { |m| m.stop }
    end

    def onReceive(msg)

      case msg
      when :next

        # If we still have seeds to return do so up front
        seed = @seeds.shift
        if seed
          self.getContext.replySafe(seed)
          return
        end

        # If we're still here then we need to evaluate candidates against our models.  Each
        # candidate value is fed into the models in parallel.  The first value that all models
        # agree is prime is returned as the value
        val = @candidates.find do |candidate|
          @models.map { |m| m.sendRequestReplyFuture [:isprime,candidate] }.all? do |f|
            f.await
            return false if not f.result.isDefined
            f.result.get
          end
        end

        # Now that we have a prime value we need to update the state of one of our models to
        # include this new value.  For now we just choose a model at random
        @models[(rand @models.size)].tell [:add,val]

        # Finally, send a response back to the caller
        self.getContext.replySafe val
      end
    end
  end

  # A model represents a fragment of the state of our sieve, specifically some subset
  # of the primes discovered so far.
  class Model < UntypedActor

    def initialize
      @primes = []
    end

    def onReceive(msg)

      # It's times like this that one really does miss Scala's pattern matching
      # but case fills in nicely enough
      (type,data) = msg
      case type
      when :add
        @primes << data
      when :isprime

        # If we haven't been fed any primes yet we can't say much...
        if @primes.empty?
          self.getContext.replySafe nil
          return
        end

        # This model only considers a value prime if it doesn't divide evenly into any
        # prime it already knows about.  Of course we have to make an exception if we're
        # testing one of the primes we already know about
        resp = @primes.none? do |prime|
          data != prime and data % prime == 0
        end
        self.getContext.replySafe resp
      else
        puts "Unknown type #{type}"
      end
    end
  end
end

Ruby offers a number of features which help us out here. As shown in this implementation messages can be as simple as a list with a leading symbol (used to indicate the message “type”) and a payload contained in the remainder of the list. This follows a similar convention found in Erlang, although that language uses tuples rather than lists. Support for destructuring/multiple assignment makes working with these messages quite simple.

Our previous work building actors from code blocks doesn’t apply here due to an implementation detail so we define both the controller and model actors as distinct classes. As it turns out this change isn’t much of a problem; we’re able to implement both classes, a helper Enumerable and a second Enumerable wrapping the controller in less than 140 lines with comments. Full code (including tests) can be found on github.

Spend a little time with JRuby and Akka and it becomes clear that they work well together and form a good basis for building concurrent applications in Ruby.

[1] This is a bit of a loaded statement; you will get some parallelism as multiple candidates move through the “stages” (i.e. goroutines) of the pipeline. That said, this notion of parallelism applies to the system as a whole. The process of determining whether a single candidate is or is not a prime number is still very sequential.

[2] “First” here means nothing more than “whichever test happens to complete and return a value first”

Originally published at Heuristic Fencepost

For simplicity and elegance in your programming constructs the list comprehension is hard to beat. [1] A list comprehension can filter an input list, transform it or do both, all in a single expression and with very readable syntax. At it’s best a list comprehension is “beautiful code” distilled: very clear and expressive with no unnecessary noise. You can, of course, make list comprehensions “ugly” but at least you have to try a bit to do so.

List comprehensions have their roots in functional programming and several modern functional languages include support for them. We’ll see comprehensions in Haskell, Clojure and Scala. [2] Python also includes support for comprehensions; in fact the basis for Guido’s argument to remove the map and filter functions from py3k was that expressions using these functions could be easily re-written as comprehensions. We also consider comprehensions in Python, including differences between the Python implementation and those in other languages and what effect those differences may have.

Let’s consider a fairly straightforward problem problem: given a list of (x,y) coordinates in some two-dimensional space provide a list of the coordinates that are within some fixed distance of the origin of (0,0). Our application also requires that results be displayed in polar coordinates, so for extra bonus points we should return our results in that notation. We can solve the problem quite easily in Haskell and Clojure using list comprehensions:

1
2
3
4
5
6
7
8
9
10

toDegrees :: Floating a => a -> a
toDegrees rad = rad * 180 / pi

euclidean :: Floating a => a -> a -> a
euclidean x y = let foo = x ^^ 2
                  bar = y ^^ 2
              in sqrt (foo + bar)

main = do
     print [(euclidean x y,(toDegrees . atan) (y / x))|(x,y)<-[(1,2),(2,3),(3,4)],(euclidean x y) > 3.0]

1
2
3
4
5
6

(defn euclidean [x y] (Math/sqrt (+ (Math/pow x 2) (Math/pow y 2))))
(println (for [
    [x,y]
     [[1,2],[2,3],[3,4]]
      :when (> (euclidean x y) 3.0)]
       [(euclidean x y),(Math/toDegrees (Math/atan (/ y x)))]))

In Scala we use for expressions to accomplish something very similar:

1
2
3
4
5
6
7
8

import scala.math.{atan,pow,sqrt,toDegrees}

val result =
  for {
    (x,y) <- List((1,2),(2,3),(3,4))
    if sqrt((pow(x,2)) + (pow(y,2))) > 3.0 }
  yield (sqrt((pow(x,2)) + (pow(y,2))),toDegrees(atan(y.toFloat/x)))
println(result)

And finally, a straightforward solution in Python:

1
2
3

from math import sqrt, atan, degrees
data=[(1,2),(2,3),(3,4)]
print [(sqrt(x**2 + y**2),degrees(atan(float(y)/x))) for (x,y) in data if sqrt(x**2 + y**2) > 3.0]

Note that in each of these solutions we’re doing a bit more work than we need to. Our implementation computes the distance from the origin twice, once when filtering values and again when generating the final output of the transformation process. This seems unnecessary; a better option would be to somehow define this value as intermediate state. This state could then be available to both filter and transform expressions. Haskell and Clojure support the introduction of intermediate bindings in their comprehension syntax:

1
2
3
4
5
6
7
8
9
10

toDegrees :: Floating a => a -> a
toDegrees rad = rad * 180 / pi

euclidean :: Floating a => a -> a -> a
euclidean x y = let foo = x ^^ 2
                  bar = y ^^ 2
              in sqrt (foo + bar)

main = do
     print [(dist,(toDegrees . atan) (y / x))|(x,y)<-[(1,2),(2,3),(3,4)],let dist=euclidean x y,dist > 3.0]

1
2
3
4
5
6
7
8

(defn euclidean [x y] (Math/sqrt (+ (Math/pow x 2) (Math/pow y 2))))

(println (for [
    [x,y]
     [[1,2],[2,3],[3,4]]
      :let [dist (euclidean x y)]
       :when (> dist 3.0)]
        [dist,(Math/toDegrees (Math/atan (/ y x)))]))

Scala also allows for intermediate bindings within a for expression:

1
2
3
4
5
6
7
8
9

import scala.math.{atan,pow,sqrt,toDegrees}

val result =
  for {
    (x,y) <- List((1,2),(2,3),(3,4))
    dist = sqrt((pow(x,2)) + (pow(y,2)))
    if dist > 3.0 }
  yield (dist,toDegrees(atan(y.toFloat/x)))
println(result)

What about Python? It turns out we cannot solve this problem in Python using a single comprehension; the syntax doesn’t allow for the introduction of intermediate state which can be used in either the predicate or transform expression. On the face of it this seems a bit odd; the language encourages the use of comprehensions for filtering and/or transformation while providing a less robust version of that very construct. To some degree this discrepancy reflects differing language goals. Guido’s post on the history of list comprehensions seems to indicate that the motivation for adding these features was pragmatic; the syntax is an elegant way to express most filter and transform operations. Functional languages use list comprehensions as “syntactic sugar” for monadic effects [3] that don’t really have an equivalent in standard Python usage. The syntax may look the same, but if you’re coming from a functional perspective they can feel just a bit off. The same is true for a few other common functional idioms:

• Lazy evaluation - List comprehensions in Python are not lazily evaluated. Generator expressions, which look very similar to list comprehensions, are lazily evaluated.
• Higher-order functions - Anonymous functions are supported in Python but these functions are famously limited to a single expression. Functions can return functions but for non-trivial functions a named function must be declared and returned.

A couple things should be noted here. First, let us clearly state that Python is not and does not claim to be a functional programming language. While absolutely true, this fact doesn’t change the underlying point. Moving from functional concepts back into Python can be a bit jarring; some things look similar but don’t behave quite like you’d expect.

It’s also worth noting that the inability to solve this problem with list comprehensions in Python doesn’t mean that this problem cannot be solved in idiomatic Python. We wish to return our intermediate state as well as filter results based on it’s value; this dual use allows us to solve the problem with nested comprehensions. The inner comprehension will generate the final representation (including the intermediate state) and the outer comprehension will filter results based on that representation. In Python this looks something like:

1
2
3

from math import sqrt, atan, degrees
data=[(1,2),(2,3),(3,4)]
print [(dist,degrees) for (dist,degrees) in [(sqrt(x**2 + y**2),degrees(atan(float(y)/x))) for (x,y) in data] if dist > 3.0]

This works only because the intermediate state is also returned in the final result. If that state were not explicitly returned (i.e. if it’s values were used as input to a conditional expression which returned, say, a string value describing the distance) this solution would not apply.

We can also solve this problem using generators. Using the state maintained by the generator we can iterate through the list, compute the intermediate state and yield a value only when we’ve satisfied our predicate. A generator-based solution would look something like:

1
2
3
4
5
6
7
8

from math import sqrt, atan, degrees
data=[(1,2),(2,3),(3,4)]
def somefunc(alist):
    for (x,y) in alist:
    dist = sqrt(x**2 + y**2)
    if (dist > 3.0):
            yield (dist,degrees(atan(float(y)/x)))
print list(somefunc(data))

Finally, none of these comments should be construed as a criticism of Python, the design choices that went into the language or the inclusion of list comprehensions generally. The pragmatic case for inclusion of this feature seems very strong. This post is interested only in the interplay between these features and similar features in other languages.

[1] Some languages (perhaps most notably Scala) use the term “for comprehension” or “for expression”, and in some of these languages (Scala again) these constructs are more flexible than a list comprehension. That said, it’s fairly straightforward to make Scala’s for expressions behave like conventional list comprehensions.

[2] A purist might object that Scala is designed to mix features of object-oriented and functional languages, but the bias in favor of functional constructs justifies Scala’s inclusion here.

[3] As an example, note that in Haskell list comprehensions can be replaced with do-notation. See the Haskell wiki for details.

Originally published at Heuristic Fencepost

I’m interested in concurrency. I’m also interested in Ruby. There doesn’t seem to be much reason to keep these two guys apart anymore.

This post marks the beginning of an occasional series on the topic of using Ruby to write concurrent code. Ruby doesn’t yet have a big reputation in the world of concurrent and/or parallel applications, but there is some interesting work being done in this space. And since problems in concurrency are notoriously difficult to reason about we could probably do a lot worse than attempt to address those problems in a language designed to make life easier for the developer.

We begin with Akka, an excellent library designed to bring actors, actor coordination and STM to Scala and, to a slightly lesser degree, the JVM generally. Our initial task is simple: we wish to be able to define an Akka actor by providing a message handler as a code block. We’ll start by attempting to implement the actor as a standalone class and then abstract that solution into code which requires the input block and nothing else.

A simple initial implementation looks something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

require 'java'
require 'akka-actor-1.2-RC6.jar'
require 'scala-library.jar'

java_import 'akka.actor.UntypedActor'
java_import 'akka.actor.Actors'

# Start with something simple.  Implement the actor as a distinct
# class and start it up within the Akka runtime.

# Look, I've implemented the actor API!
class SomeActor < UntypedActor

  def onReceive msg
    puts "Received message: #{msg.to_s}"
  end
end

# So we should be fine then, right?
ref = Actors.actorOf SomeActor.new
ref.start
ref.tell "foo"

[@varese ruby]$ ruby --version
jruby 1.6.2 (ruby-1.8.7-p330) (2011-05-23 e2ea975) (OpenJDK Client VM 1.6.0_22) [linux-i386-java]
[@varese ruby]$ ruby akka_sample1.rb 
ArgumentError: Constructor invocation failed: ActorRef for instance of actor [org.jruby.proxy.akka.actor.UntypedActor$Proxy0] is not in scope.
 You can not create an instance of an actor explicitly using 'new MyActor'.
 You have to use one of the factory methods in the 'Actor' object to create a new actor.
 Either use:
  'val actor = Actor.actorOf[MyActor]', or
  'val actor = Actor.actorOf(new MyActor(..))'
  (root) at akka_sample1.rb:20

Well, that didn’t work very well. Apparently the class we defined in JRuby is being exposed to the Java lib as a proxy object and that proxy’s class is unknown to the Akka runtime. No problem; Akka supports a factory model for actor creation, and by using that approach the underlying class of our actor should become a non-issue. With a few simple changes we’re ready to try again:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

require 'java'
require 'akka-actor-1.2-RC6.jar'
require 'scala-library.jar'

java_import 'akka.actor.UntypedActor'
java_import 'akka.actor.Actors'

# A second attempt.  Define our actor in a standlone class again
# but this time use an ActorFactory (via closure coercion) to
# interact with Akka.

# Define our actor in a class again...
class SomeActor < UntypedActor

  def onReceive msg
    puts "Received message: #{msg.to_s}"
  end
end

# ... and then provide an UntypedActorFactory to instantiate
# the actor.  The factory interface qualifies as a SAM so
# we only need to provide a closure to generate the actor and
# let JRuby's closure coercion handle the rest.
ref = Actors.actorOf do
  SomeActor.new
end

ref.start
ref.tell "foo"

[@varese ruby]$ ruby akka_sample2.rb
Received message: foo

We now have a working actor, but we still have some work to do; remember, we want to be able to define arbitrary actors by supplying just a code block. We need a few additional pieces to make this work:

• A generic actor implementation whose state includes a block or Proc instance. The onReceive method of this actor could then simply call the contained block/Proc, passing the input message as an arg.
• An ActorFactory implementation which takes a code block as an arg, stores it in internal state and then uses that block to build an instance of the generic actor described above on demand.

A first cut at this concept might look something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

require 'java'
require 'akka-actor-1.2-RC6.jar'
require 'scala-library.jar'

java_import 'akka.actor.UntypedActor'
java_import 'akka.actor.UntypedActorFactory'
java_import 'akka.actor.Actors'

# Shift to working with code blocks via a generic actor and a simple
# factory for creating them.

class SomeActor < UntypedActor

  # Look, I've got a constructor... but it'll get ignored!
  def initialize(proc)
    @proc = proc
  end

  def onReceive(msg)
    @proc.call msg
  end
end

class SomeActorFactory
  include UntypedActorFactory

  def initialize(&b)
    @proc = b
  end

  def create
    SomeActor.new @proc
  end
end

# Create a factory for an actor that uses the input block to pass incoming messages.
factory = SomeActorFactory.new do |msg|
  puts "Message recieved: #{msg.to_s}"
end
ref = Actors.actorOf factory

ref.start
ref.tell "foo"

[@varese ruby]$ ruby akka_sample3.rb 
ArgumentError: wrong number of arguments for constructor
  create at akka_sample3.rb:29
  (root) at akka_sample3.rb:37

What went wrong here? UntypedActor is a concrete class with a defined no-arg constructor. That constructor is being called in favor of the one we’ve provided, and as a consequence our block never gets into the mix. There’s almost certainly a cleaner way to solve this using JRuby, but for the moment we can get around the problem (in an admittedly ugly way) by providing a setter on our generic actor class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

require 'java'
require 'akka-actor-1.2-RC6.jar'
require 'scala-library.jar'

java_import 'akka.actor.UntypedActor'
java_import 'akka.actor.UntypedActorFactory'
java_import 'akka.actor.Actors'

# Continue with the generic actor implementation, but shift to using a setter
# for passing in the Proc to which we'll delegate message handling.

class SomeActor < UntypedActor

  def proc=(b)
    @proc = b
  end

  def onReceive(msg)
    @proc.call msg
  end
end

class SomeActorFactory
  include UntypedActorFactory

  def initialize(&b)
    @proc = b
  end

  def create
    rv = SomeActor.new
    rv.proc = @proc
    rv
  end
end

# Create a factory for an actor that uses the input block to pass incoming messages.
factory = SomeActorFactory.new do |msg|
  puts "Message recieved: #{msg.to_s}"
end
ref = Actors.actorOf factory

ref.start
ref.tell "foo"

[@varese ruby]$ ruby akka_sample4.rb 
Message recieved: foo

We now have what we wanted.

If you’re interested in this topic note that Nick Sieger has covered similar ground (including the interaction between JRuby and Akka) here. Nick’s article draws on some very good work done by Daniel Ribeiro late last year. The code referenced in Daniel’s article is available on Github. I didn’t come across Daniel’s post until my own was nearly done but there is quite a bit of overlap between his code and mine. That said, I recommend taking a look at both articles, if for no other reason than the fact that both authors are much better at writing Ruby code than I am.

Originally published at Heuristic Fencepost

In a previous post we briefly discussed the idea of using idiomatic Clojure to access data contained in a Cassandra instance, including transparent conversion to and from Clojure data. We’ll explore an implementation of this idea, although we won’t address the question of laziness, in part because there are sizable trade-offs to consider. For example, any solution that provides lazy evaluation must do so while also attempting to minimize the number of trips to the underlying data store. This question may be picked up in yet more future work, but for now we’ll continue on. We’ve upgraded to Cassandra 0.8.2 and Clojure 1.2, and we’re using a new data model (see below), but for the most part we’ll try to pick up where we left off.

At the core the Cassandra data model is centered around columns. Each of these columns contains both a name and a value, both of which are represented as binary data. This model is very simple, and while it may appear limiting it is in reality quite flexible. The lack of any pre-defined data types avoids any “impedance mismatch” resulting from structured data being shoehorned into data types that don’t really fit. We’re free to represent column values in any way we see fit; if we can convert it into bytes it’s fair game. Our problem thus devolves into a question of serialization, and suddenly there are many suitors vying for our attention. Among the set of well-known serialization packages we find Google’s Protocol Buffers, Thrift and Avro. And since we’re working in a language with good Java interop we can always have Java’s built-in serialization (or something similar like Kryo) available. Finally we’re always free to roll our own.

Let’s begin by ruling out that last idea. There are already well-tested third-party serialization libraries so unless we believe that all of them suffer from some fatal error it’s difficult to justify the risk and expense of creating something new. We’d also like our approach to have some level of cross-platform support so native Java serialization is excluded (along with Kryo). We also need to be able to encode and decode arbitrary data without defining message types or their payload(s) in advance, a limitation that rules out Protocol Buffers and Thrift. The last man standing is Avro, and fortunately for us he’s a good candidate. Avro is schema-based but the library includes facilities for generating schemas on the fly by inspecting objects via Java reflection. Also included is a notion of storing schemas with data, allowing the original object to be easily reconstructed as needed. The Avro data model includes a rich set of basic types as well as support for “complex” types such as arrays and maps.

We’ll need to implement a Clojure interface into the Avro functionality; this can be as simple as methods to encode and decode data and schemas. At least some implementations of Avro data files use a pre-defined “meta-schema” (consisting of the schema for the embedded data and that data itself) for storing both items. Consumers of these files first decode the meta-schema then use the discovered schema to decode the underlying data. We’ll follow a similar path for our library. We’ll also extend our Cassandra support a bit in order to support the insertion of new columns for a given key and column family.

We wind up with the following for our Avro library:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

(ns fencepost.avro)

; Dependencies
; avro 1.5.2
; paranamer 2.0 (required by Avro)
; jackson 1.8.5 (required by Avro)

(import '(org.apache.avro Schema)
  '(org.apache.avro.generic GenericDatumReader)
  '(org.apache.avro.io BufferedBinaryEncoder EncoderFactory DecoderFactory)
  '(org.apache.avro.reflect ReflectData ReflectDatumWriter)
  '(java.io ByteArrayOutputStream ByteArrayInputStream)
        )

(defn get_meta_schema []
      ; Ideally we'd use a record for this sort of thing but doing so would require setX()
      ; accessors for all fields.  Use of a map here is less precise but quite a bit easier
      ; to code.
      "{\"type\": \"map\", \"values\": \"bytes\"}"
)

(defn encode_with_schema [target]
      "Use Java reflection to generate a schema for the input object and return that schema along with encoded data"
      (let [targetschema (.getSchema (ReflectData/get) (.getClass target))
              targetwriter (ReflectDatumWriter. targetschema)
      buffer (ByteArrayOutputStream.)
              encoder (.binaryEncoder (EncoderFactory.) buffer nil)]

      ; Populate the buffer with Avro data for the target.  Note that we can't bundle the
      ; whole thing up into a single let expression because of our reliance on side effects.
      (.write targetwriter target encoder)
      (.flush encoder)

      (let [targetdata (.toByteArray buffer)
            metawriter (ReflectDatumWriter. (Schema/parse (get_meta_schema)))]
        (.reset buffer)
        (.write metawriter
            {"schema" (.getBytes (.toString targetschema)) "data" targetdata}
            encoder)
        (.flush encoder)
        (.toByteArray buffer)
        )
      )
)

(defn decode_from_schema [indata]
      "Use the meta_schema to extract data and schema and then extract raw data"
      (let [metareader (GenericDatumReader. (Schema/parse (get_meta_schema)))
              buffer (ByteArrayInputStream. indata)
              decoder (.binaryDecoder (DecoderFactory.) buffer nil)
      middata (.read metareader nil decoder)

      ; The data type returned from the underlying Avro Java code needs a bit
      ; of massaging before we can move forward.  Avro decoders return strings
      ; as instances of Utf8 objects so we have to apply "str" to them directly
      ; in order to get back something we can work with.
      {schema "schema" data "data"} (zipmap (map str (keys middata)) (vals middata))
      schemabytes (byte-array (.capacity schema))
      databytes (byte-array (.capacity data))]

      ; Ah, more side effects.  The Java Avro implementation makes heavy use of
      ; NIO ByteBuffers, so we're forced to convert them into byte arrays before
      ; continuing. 
      (.get schema schemabytes)
      (.get data databytes)

      (let [targetreader (GenericDatumReader. (Schema/parse (String. schemabytes)))
           targetdecoder (.binaryDecoder (DecoderFactory.) databytes nil)]
           (.read targetreader nil targetdecoder)
       )
  )
)

After the improvements described above our Cassandra library now looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

(ns fencepost.cassandra)

; Dependencies
; apache-cassandra-thrift-0.8.2.jar
; libthrift-0.6.jar
; slf4j-api-1.6.1.jar
; slf4j-log4j12-1.6.1.jar
; log4j-1.2.16.jar

(import '(org.apache.cassandra.thrift Cassandra$Client SliceRange SlicePredicate ColumnParent KeyRange ConsistencyLevel ColumnPath Column)
  '(org.apache.thrift.transport TFramedTransport TSocket)
        '(org.apache.thrift.protocol TBinaryProtocol)
  '(java.nio ByteBuffer)
        )

; A quick note on usage.  The Cassandra Java API returns "this" for many of the setX() methods on the setters of core objects in the Thrift
; API.  Our usage here consistently employs the doto syntax rather than relying on these return values.  This is largely a matter of 
; convention, but in this case it appears to make the code a bit clearer to read.  Your mileage may vary.
(defn connect [host port keyspace]
  "Connect to a Cassandra instance on the specified host and port.  Set things up to use the specified key space."
  (let [transport (TFramedTransport. (TSocket. host port))
        protocol (TBinaryProtocol. transport)
        client (Cassandra$Client. protocol)]
    (.open transport)
    (.set_keyspace client keyspace)
    client
    )
  )

(defn get_range_slices [client cf start end]
  "Get a list of KeySlices for every key in the range beginning with start and ending with end"
  (let [slice_range
        (doto (SliceRange.)
          (.setStart (byte-array 0))
          (.setFinish (byte-array 0))
          (.setReversed false)
          (.setCount 100)
          )
        slice_predicate
        (doto (SlicePredicate.)
          (.setSlice_range slice_range))
        column_parent (ColumnParent. cf)
        key_range
        (doto (KeyRange.)
          (.setStart_key (.getBytes start))
          (.setEnd_key (.getBytes end)))
        ]
    (.get_range_slices client column_parent slice_predicate key_range ConsistencyLevel/ONE)
    )
  )

(defn range_slices_keys [slices]
  "Retrieve the set of keys in a list of KeySlices"
  (map #(String. (.getKey %)) slices)
  )

(defn range_slices_columns [slices key]
  "Given a list of KeySlices retrieve a map of the columns associated with the specified key"
  (let [match (first (filter #(= key (String. (.getKey %))) slices))]
    (cond (nil? match) nil
          (true? true)
          (let [urcols (.getColumns match)
                cols (map #(.getColumn %) urcols)]
            (zipmap (map #(keyword (String. (.getName %))) cols)
                    (map #(.getValue %) cols))
            )
          )
    )
  )

(defn insert [client key cf colname colval_bytes]
  "Insert the specified column into the specified column family.  At present we don't support super columns"
  (let [key_bytes (.getBytes key)
       key_buffer (ByteBuffer/allocate (alength key_bytes))
       column_parent
        (doto (ColumnParent.)
    (.setColumn_family cf)
  )
       colname_bytes (.getBytes colname)
       column
  (doto (Column.)
    (.setName colname_bytes)
    (.setValue colval_bytes)
    (.setTimestamp (System/currentTimeMillis))
  )]

       ; Populate the built ByteBuffer with the contents of the input key
       (.put key_buffer key_bytes)
       (.flip key_buffer)

       (.insert client key_buffer column_parent column ConsistencyLevel/ONE)
       )
)

Our core example will be built around a collection of employee records. We want to create a report on these employees using attributes defined in various well-known columns. We’d like to access the values in these columns as simple data types (booleans, integers, perhaps even an array or a map) but we’d like to do so through a uniform interface. We don’t want to access certain columns in certain ways, as if we “knew” that a specific column contained data of a specific type. Any such approach is by definition brittle if the underlying data model should shift in flight (as data models are known to do).

After finishing up with our Clojure libraries we implement a simple app for populating our Cassandra instance with randomly-generated employee information:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

; Populate data for a set of random users to a Cassandra instance.
;
; Users consist of the following set of data:
; - a username [String]
; - a user ID [integer]
; - a flag indicating whether the user is "active" [boolean]
; - a list of location IDs for each user [list of integer]
;
; User records are keyed by username rather than user IDs, mainly because at the moment 
; we only support strings for key values.  The Cassandra API exposes keys as byte arrays 
; so we could extend our Cassandra support to include other datatypes.

(use '[fencepost.avro])
(use '[fencepost.cassandra])

(import '(org.apache.commons.lang3 RandomStringUtils)
  '(java.util Random)
        )


; Utility function to combine our Avro lib with our Cassandra lib
(defn add_user [client username userid active locationids]
      (let [userid_data (encode_with_schema userid)
              active_data (encode_with_schema active)
      locationids_data (encode_with_schema locationids)]
          (insert client username "employee" "userid" userid_data)
      (insert client username "employee" "active" active_data)
              (insert client username "employee" "locationids" locationids_data)
      )
)

; Generate a list of random usernames
(let [client (connect "localhost" 9160 "employees")]
      (dotimes [n 10]
                 (let [username (RandomStringUtils/randomAlphanumeric 16)
               random (Random.)
           userid (.nextInt random 1000)
           active (.nextBoolean random)
           locationids (into [] (repeatedly 10 #(.nextInt random 100)))]
                      (add_user client username userid active locationids)
          (println (format "Added user %s: [%s %s %s]" username userid active locationids))
          )
      )
)

[varese clojure]$ ~/local/bin/clojure add_employee_data.clj 
Added user gFc0pVnLKPnjrrLx: [158 true [77 73 99 58 31 64 1 37 70 69]]
Added user 5gGh9anHwFINpr5t: [459 true [34 71 28 1 2 84 11 33 37 28]]
Added user pGRMeXBTFoBIWhud: [945 true [45 83 51 45 11 4 80 68 73 27]]
...

We’re now ready to create our reporting application. Using Avro and a consistent meta-schema this comes off fairly easily:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

; Retrieve information from the Cassandra database about one of our employees

(use '[fencepost.avro])
(use '[fencepost.cassandra])

(defn evaluate_user [slices username]
      "Gather information for the specified user and display a minimal report about them"

      ; Note that the code below says nothing about types.  We specify the column names we
      ; wish to access but whatever Cassandra + Avro supplies for the value of that column
      ; is what we get.
     (let [user_data (range_slices_columns slices username)
             userid (decode_from_schema (user_data :userid))
             active (decode_from_schema (user_data :active))
             locationids (decode_from_schema (user_data :locationids))]
      (println (format "Username: %s" username))
      (println (format "Userid: %s" userid))
      (println (if (> userid 0) "Userid is greater than zero" "Userid is not greater than zero"))
      (println (format "Active: %s" active))
      (println (if active "User is active" "User is not active"))

      ; Every user should have at least one location ID.
      ;
      ; Well, they would if we were able to successfully handle an Avro record.
      ;(assert (> (count locationids) 0))
      )
)

(let [client (connect "localhost" 9160 "employees")
      key_slices (get_range_slices client "employee" "!" "~")
      keys (range_slices_keys key_slices)]
      (println (format "Found %d users" (count keys)))
      (dotimes [n (count keys)]
                 (evaluate_user key_slices (nth keys n))
      )
    )

[varese clojure]$ ~/local/bin/clojure get_employee_data.clj 
Found 10 users
Username: 5gGh9anHwFINpr5t
Userid: 459
Userid is greater than zero
Active: true
User is active
...

And in order to verify our assumptions about simple cross-platform support we create a Ruby version of something very much like our reporting application:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

require 'rubygems'
require 'avro'
require 'cassandra'

def evaluate_avro_data bytes

  # Define the meta-schema
  meta_schema = Avro::Schema.parse("{\"type\": \"map\", \"values\": \"bytes\"}")

  # Read the meta source and extract the contained data and schema
  meta_datum_reader = Avro::IO::DatumReader.new(meta_schema)
  meta_val = meta_datum_reader.read(Avro::IO::BinaryDecoder.new(StringIO.new(bytes)))

  # Build a new reader which can handle the indicated schema
  schema = Avro::Schema.parse(meta_val["schema"])
  datum_reader = Avro::IO::DatumReader.new(schema)
  val = datum_reader.read(Avro::IO::BinaryDecoder.new(StringIO.new(meta_val["data"])))
end

client = Cassandra.new('employees', '127.0.0.1:9160')
client.get_range(:employee,{:start_key => "!",:finish_key => "~"}).each do |k,v|
  userid = evaluate_avro_data v["userid"]
  active = evaluate_avro_data v["active"]
  locationids = evaluate_avro_data v["locationids"]
  puts "Username: #{k}, user ID: #{userid}, active: #{active}"
  puts "User ID #{(userid > 0) ? "is" : "is not"} greater than zero"
  puts "User #{active ? "is" : "is not"} active"

  # Ruby's much more flexible notion of truthiness makes the tests above somewhat less
  # compelling.  For extra validation we add the following
  "Oops, it's not a number" unless userid.is_a? Fixnum
end

[varese 1.8]$ ruby get_employee_data.rb
Username: 5gGh9anHwFINpr5t, user ID: 459, active: true
User ID is greater than zero
User is active
Username: 76v8iEJcc79Huj9L, user ID: 469, active: false
User ID is greater than zero
User is not active
...

This code meets our basic requirement, but as always there were a few stumbling blocks along the way. Avro includes strings as a primitive type, but unfortunately the Java API (which we leverage for our Clojure code) returns string instances as a Utf8 type. We can get a java.lang.String from these objects, but unfortunately we need another toString() method call that (logically) is completely unnecessary. We also don’t fully support complex types. The Avro code maps the Clojure classes representing arrays and maps onto a “record” type that includes the various fields exposed via getters. Supporting these types requires the ability to reconstruct the underlying object based on these fields, and doing so reliably is beyond the scope of this work. Finally, we were forced to use Ruby 1.8.x for the Ruby examples since the Avro gem apparently doesn’t yet support 1.9.

Originally published at Heuristic Fencepost

Soon after I began working with Cassandra it became clear to me that if you were in the market for a platform for creating applications that interact with this database you could do a lot worse than Clojure. The lack of a query language [1] suggests that filtering and slicing lists of keys and columns might be a fairly common activity for apps powered by Cassandra. And while many languages support the map/filter/reduce paradigm Clojure’s use of sequences throughout the core suggest a natural means to integrate this data into the rest of your application.

Cassandra itself provides an API that uses the Thrift protocol for manipulating data. We’ll use this interface to implement a simple proof-of-concept application that might serve as a testbed for manipulating data managed by Cassandra in idiomatic Clojure. Note that the Clojure ecosystem already includes several open-source projects that connect Clojure to Cassandra: these include clj-cassandra and clj-hector, the latter leveraging the Hector Java client to do it’s work. In order to keep things simple we choose to avoid any of these third-party libraries; it’s not as if the Thrift interface imposes a heavy burden on us. Let’s see how far we can get with what’s already in the packaging.

That sounds great… so what exactly are we trying to do? Beginning with the database generated during our previous work with Cassandra we should be able to access sets of keys within a keyspace and a set of columns for any specific key. These structures should be available for manipulation in idiomatic Clojure as sequences. Ideally these sequences would be at least somewhat lazy and transparently support multiple datatypes. [2]

Using the Thrift interface requires working with a fair number of Java objects representing return types and/or arguments to the various exposed functions. My Clojure isn’t yet solid enough to hash out Java interop code without flailing a bit so we kick things off with a Scala implementation. This approach allows us to simplify the interop problem without sacrificing the functional approach, all within a language that is by now fairly familiar.

The Scala code includes a fair number of intermediate objects but is otherwise fairly clean:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

package org.fencepost.cassandra

import scala.collection.JavaConversions

import org.apache.thrift.protocol.TBinaryProtocol
import org.apache.thrift.transport._
import org.apache.cassandra.service._
import org.apache.cassandra.thrift._

object ThriftCassandraClient {

  def connect(host:String,port:Int,keyspace:String):Cassandra.Client = {

    val transport = new TFramedTransport(new TSocket(host, port))
    val protocol = new TBinaryProtocol(transport)
    val client = new Cassandra.Client(protocol)
    transport.open()
    client set_keyspace keyspace
    client
  }

  // Execute a range slice query against the specified Cassandra instance.  Method returns
  // an object suitable for later interrogation by range_slices_keys() or range_slices_columns()
  def get_range_slices(client:Cassandra.Client,cf:String,start:String,end:String):Iterable[KeySlice] = {

    val sliceRange = new SliceRange()
    sliceRange setStart new Array[Byte](0)
    sliceRange setFinish new Array[Byte](0)
    sliceRange setReversed false
    sliceRange setCount 100
    val slicePredicate = new SlicePredicate()
    slicePredicate setSlice_range sliceRange
    val columnParent = new ColumnParent(cf)
    val keyRange = new KeyRange()
    keyRange setStart_key (start getBytes)
    keyRange setEnd_key (end getBytes)

    val javakeys = client.get_range_slices(columnParent,slicePredicate,keyRange,ConsistencyLevel.ONE)

    // Return from Thrift Java client is List<KeySlice> so we have to explicitly convert it here
    JavaConversions asScalaIterable javakeys
  }

  // Return an Iterable for all keys in an input query state object
  def range_slices_keys(slices:Iterable[KeySlice]) = slices map { c => new String(c.getKey) }

  // Return an Option containing column information for the specified key in the input query
  // state object.  If the key isn't found None is returned, otherwise the Option contains a
  // map of column names to column values.
  def range_slices_columns(slices:Iterable[KeySlice], key:String):Option[Map[String,String]] = {

    slices find { c => new String(c.getKey()) == key } match {
      case None => None
      case Some(keyval) =>

        val urcols = JavaConversions asScalaIterable (keyval getColumns)
        val cols:Seq[Column] = (urcols map (_ getColumn)).toSeq
        Some(Map(cols map { c => (new String(c.getName())) -> (new String(c.getValue())) }:_*))
    }
  }

  def main(args: Array[String]): Unit = {

    val client = connect("localhost", 9160,"twitter")
    val slices = get_range_slices(client,"authors","!","~")
    val fivekeys = range_slices_keys(slices) take 5
    println("fivekeys: " + fivekeys)
    for (key <- fivekeys) {
      range_slices_columns(slices,key) match {
        case None =>
        case Some(cols) =>
          println(
            "Key " + key +
            ": name => " + (cols getOrElse ("name","")) +
            ", following => " + (cols getOrElse ("following",""))
          )
      }
    }
  }
}

Translating this code into Clojure is more straightforward than expected:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

(import '(org.apache.thrift.transport TFramedTransport TSocket)
        '(org.apache.thrift.protocol TBinaryProtocol)
        '(org.apache.cassandra.thrift Cassandra$Client SliceRange SlicePredicate ColumnParent KeyRange ConsistencyLevel)
        )

(defn connect [host port keyspace]
  "Connect to a Cassandra instance on the specified host and port.  Set things up to use the specified key space."
  (let [transport (TFramedTransport. (TSocket. host port))
        protocol (TBinaryProtocol. transport)
        client (Cassandra$Client. protocol)]
    (.open transport)
    (.set_keyspace client keyspace)
    client
    )
  )

(defn get_range_slices [client cf start end]
  "Simple front end into the get_range_slices function exposed via Thrift"
  (let [slice_range
        (doto (SliceRange.)
          (.setStart (byte-array 0))
          (.setFinish (byte-array 0))
          (.setReversed false)
          (.setCount 100)
          )
        slice_predicate
        (doto (SlicePredicate.)
          (.setSlice_range slice_range))
        column_parent (ColumnParent. cf)
        key_range
        (doto (KeyRange.)
          (.setStart_key (.getBytes start))
          (.setEnd_key (.getBytes end)))
        ]
    (.get_range_slices client column_parent slice_predicate key_range ConsistencyLevel/ONE)
    )
  )

(defn range_slices_keys [slices]
  "Retrieve the set of keys in a get_range_slices result"
  (map #(String. (.getKey %)) slices)
  )

(defn range_slices_columns [slices key]
  "Retrieve a map of the columns associated with the specified key in a get_range_slices result"
  (let [match (first (filter #(= key (String. (.getKey %))) slices))]
    (cond (nil? match) nil
          (true? true)
          (let [urcols (.getColumns match)
                cols (map #(.getColumn %) urcols)]
            (zipmap (map #(keyword (String. (.getName %))) cols)
                    (map #(String. (.getValue %)) cols))
            )
          )
    )
  )

(let [client (connect "localhost" 9160 "twitter")
      key_slices (get_range_slices client "authors" "!" "~")
      five_keys (take 5 (range_slices_keys key_slices))]

  (print five_keys)

  (let [formatfn
        (fn [key]
          (let [cols (range_slices_columns key_slices key)]
            (format "Key %s: name => %s, following => %s\n" key (cols :name) (cols :following))
            )
          )]
    (print (reduce str (map formatfn five_keys)))
    )
  )

These results seem fairly promising, although we’re nowhere near done. This code assumes that all column names and values are strings, a perfectly ridiculous assumption. We also don’t offer any support for nested data types, although in fairness this was a failing of our earlier work as well. Finally we haven’t built in much support for lazy evaluation; we lazily convert column names to Clojure keywords but that’s about it. But fear not, gentle reader; we’ll revisit some or all of these points in future work.

[1] At least until CQL arrives in Cassandra 0.8

[2] We won’t be able to meet these last two goals in our initial implementation, but with any luck we’ll be able to revisit them in future work

Originally published at Heuristic Fencepost

Cassandra implements a data model built on ColumnFamilies which differs from both SQL and document-oriented databases such as CouchDB. We want to spend a little time with this data model, get to know it a bit, so we setup a simple but quasi-realistic problem space: given a database of tweets, tweet authors and tweet followers attempt to answer a sequence of questions about that data. The questions should increase in complexity and each new question should explore a different facet of the data model.

The examples below are implemented in Python with a little help from a few excellent libraries:

• Pycassa for interacting with Cassandra.
• Twitter tools when we have to interact with Twitter via their REST API

We’ll begin by looking at how we might query an Cassandra instance populated with data in order to find the answers to the questions in our problem space. We’ll close by briefly discussing how to get the data into Cassandra.

We should be all set; bring on the questions!

FOR EACH AUTHOR: WHAT LANGUAGE DO THEY WRITE THEIR TWEETS IN AND HOW MANY FOLLOWERS DO THEY HAVE?

The organizing structure of the Cassandra data model is the column family defined within a keyspace. The keyspace is exactly what it sounds like: a collection of keys, each identifying a distinct entity in your data model. Each column family represents a logical grouping of data about these keys. This data is represented by one or more columns, which are really not much more than a tuple containing a name, value and timestamp. A column family can contain one or more columns for a key in the keyspace, and as it turns out you have a great deal of flexibility here; columns in a column family don’t have to be defined in advance and do not have to be the same for all keys.

We begin by imagining a column family named “authors” in a keyspace defined by the user’s Twitter handle or screen name. Assume that for each of these keys the “authors” column family contains a set of columns, one for each property returned by the “user/show” resource found in the Twitter REST API. Let’s further assume that included in this data are fields named “lang” and “followers_count” and that these fields correspond to exactly the data we’re looking for. We can satisfy our requirement by using a range query to identify all keys that fall within a specified range. In our case we want to include all alphanumeric screen names so we query across the range of printable ASCII characters. The Pycassa API makes this very easy [1]:

1
2
3
4
5
6

import pycassa

cassandra = pycassa.connect("twitter")
authors_cf = pycassa.ColumnFamily(cassandra,"authors")
for (k,values) in authors_cf.get_range('!','~',["lang","followers_count"]):
    print "Key: %s, language: %s, followers: %s" % (k,values["lang"],values["followers_count"])

The result is exactly what we wanted:

[@varese src]$ python Query1.py 
Key: Alanfbrum, language: en, followers: 73
Key: AloisBelaska, language: en, followers: 8
Key: DASHmiami3, language: en, followers: 11
Key: DFW_BigData, language: en, followers: 21
...

HOW MANY TWEETS DID EACH AUTHOR WRITE?

Okay, so we’ve got the idea of a column family; we can use them to define a set of information for keys in our keyspace. Clearly this is a useful organizing principle, but in some cases we need a hierarchy that goes a bit deeper. The set of tweets written by an author illustrates just such a case: tweets are written by a specific author, but each tweet has data of it’s own (the actual content of the tweet, a timestamp indicating when it’s written, perhaps some geo-location info, etc.). How can we represent this additional level of hierarchy?

We could define a new keyspace consisting of some combination of the author’s screen name and the tweet ID but this doesn’t seem terribly efficient; identifying all tweets written by an author is now unnecessarily complicated. Fortunately Cassandra provides a super column family which meets our needs exactly. The value of each column in a super column family is itself a collection of regular columns.

Let’s apply this structure to the problem at hand. Assume that we also have a super column family named “tweets” within our keyspace. For each key we define one or more super columns, one for each tweet written by the author identified by the key. The value of any given super column is a collection of columns, one for each field contained in the results we get when we search for tweets using Twitter’s search API. Once again we utilize a range query to access the relevant keys:

1
2
3
4
5
6
7
8
9
10
11

import pycassa

cassandra = pycassa.connect("twitter")
tweets_cf = pycassa.ColumnFamily(cassandra,"tweets")

# Key in return value from "tweets" super column family is the
# tweet ID, value is a map of per-tweet data. We're only interested
# in the number of tweets so we only need to compute the size
# of the returned hash.
for (k,values) in tweets_cf.get_range('!','~'):
    print "Authors: %s, tweets written: %d" % (k,len(values))

Running this script gives us the following:

[@varese src]$ python Query2.py
Authors: Alanfbrum, tweets written: 1
Authors: AloisBelaska, tweets written: 1
Authors: DASHmiami3, tweets written: 1
Authors: DFW_BigData, tweets written: 1
...
Authors: LaariPimenteel, tweets written: 2
Authors: MeqqSmile, tweets written: 1
Authors: Mesoziinha, tweets written: 2

HOW MANY TWEET AUTHORS ARE ALSO FOLLOWERS OF @SPYCED?

We’re now attempting to replicate functionality that looks very much like a join in a relational database. Somehow we have to relate one type of resource (the set of followers for a Twitter user) to the set of authors defined in our “authors” column family. The Twitter REST API exposes the set of user IDs that follow a given user, so one approach to this problem might be to obtain these IDs and, for each of them, query the “authors” table to see if we have an author with a matching ID. As for the user to search for… well, Jonathan Ellis (@spyced) seemed like the obvious choice.

Newer versions of Cassandra provide support for indexed slices on a column family. The database maintains an index for a named column within a column family, enabling very efficient lookups for rows in which the column matches a simple query. Query terms can test for equality or whether a column value is greater than or less than an input value [2]. Multiple search clauses can be combined within a single query, but in our case we’re interested in strict equality only. Our solution to this problem looks something like the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from twitter.api import Twitter
import pycassa
from pycassa.index import *

cassandra = pycassa.connect("twitter")
authors_cf = pycassa.ColumnFamily(cassandra,"authors")
tweets_cf = pycassa.ColumnFamily(cassandra,"tweets")

twitter = Twitter()

# Iterate through the set of IDs returned by the Twitter API and execute
# an index search against each ID. The Pycassa API will return a generator
# for each query so we make use of the for expression to determine when
# we should increment the total count.
count = 0
for authorid in twitter.followers.ids(id="spyced"):
    author_expr = create_index_expression('id_str',str(authorid))
    author_clause = create_index_clause([author_expr])
    for (authorkey,authorprops) in authors_cf.get_indexed_slices(author_clause):
        print authorkey
        count += 1
print count

The result looks pretty promising:

[@varese src]$ python Query3.py
tlberglund
evidentsoftware
sreeix
...
joealex
cassandra
21

Some spot checking of these results using the Twitter Web interface seems to confirm the results.

POPULATING THE DATA

So far we’ve talked about accessing data from a Cassandra instance that has already been populated with the data we need. But how do we get it in there in the first place? The answer to this question is a two-step process; first we create the relevant structures within Cassandra and then we use our Python tools to gather and add the actual data.

My preferred tool for managing my Cassandra instance is the pycassaShell that comes with Pycassa. This tool makes it’s easy to create the column families and indexes we’ve been working with:

1
2
3
4

SYSTEM_MANAGER.create_keyspace('twitter',replication_factor=1)
SYSTEM_MANAGER.create_column_family('twitter','authors',comparator_type=UTF8_TYPE)
SYSTEM_MANAGER.create_column_family('twitter','tweets',super=True,comparator_type=UTF8_TYPE)
SYSTEM_MANAGER.create_index('twitter','authors','id_str',UTF8_TYPE)

There are plenty of similar tools around; your mileage may vary.

When it comes to the heavy lifting, we combine Pycassa and Twitter tools into a simple script that does everything we need:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

from twitter.api import Twitter
import pycassa

from itertools import ifilterfalse

# Query to use when finding tweets.
searchquery = "#cassandra"

# Borrowed from the itertools docs
def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

def populate():

    cassandra = pycassa.connect("twitter")
    authors_cf = pycassa.ColumnFamily(cassandra,"authors")
    tweets_cf = pycassa.ColumnFamily(cassandra,"tweets")

    # The Twitter API returns Unicode vals for all string results.  In addition
    # Pycassa appears to complain when we give it a string encoded in something
    # other than UTF-8 or a non-string value.  To get around this we perform
    # an intelligent string conversion; if we get a Unicode type return the
    # UTF-8 encoding of that string, otherwise return the standard string
    # representation.
    def smart_str(val):
        if isinstance(val,unicode):
            return val.encode('utf-8')
        else:
            return str(val)

    search = Twitter(domain="search.twitter.com")
    twitter = Twitter()

    search_results = search.search(q=searchquery,rpp=100)
    tweets = search_results["results"]

    print tweets[0]
    for tweet in tweets:
        tweet_str = dict([(k,smart_str(v)) for (k,v) in tweet.iteritems()])
        tweets_cf.insert(tweet["from_user"],{tweet["id_str"]:tweet_str})

    print "Found %d tweets" % len(tweets)
    author_names = list(unique_everseen([t["from_user"] for t in tweets]))
    print "Found %d distinct authors" % len(author_names)

    # Convert everything into strings; in Cassandra name and values of a column
    # are apparently normally converted into strings
    for author_info in (twitter.users.show(id=name) for name in author_names):

        author_name = author_info['screen_name']
        author_info_str = dict([(k,smart_str(v)) for (k,v) in author_info.iteritems()])
        authors_cf.insert(author_name,author_info_str)
        print "Added data for author %s" % author_name

if __name__ == "__main__":
    populate()

[1] For sake of brevity this discussion omits a few details, including the configuration of a partitioner and tokens in order to use range queries effectively and how keys are ordered. Consult the project documentation and wiki for additional details.

[2] Here “greater than” and “less than” are defined in terms of the type provided at index creation time.

Originally published at Heuristic Fencepost

A short while ago Alex Miller (aka puredanger) wrote up a blog entry detailing how to use Clojure to interact with the new fork/join concurrency framework to be included with Java7 (and already available from Doug Lea’s site). The meat of Alex’s solution is a Java wrapper for Clojure’s IFn type which integrates nicely with the fork/join framework. At the time there was some discussion about whether a Scala implementation would require an equivalent amount of scaffolding. It turns out that supporting this functionality in Scala requires a bit more effort than one might expect, although the problems one faces are quite different than what Alex worked through in Clojure. We review the steps to a working Scala implementation and see what we can learn from them.

Before we move on, a few notes about fork/join itself. A full overview is outside the scope of this post, however details can be found in the jsr166y section of Doug Lea’s site. A solid (although slightly out-of-date) review can be found in a developerWorks article by Brian Goetz.

We begin as simply as possible; a straight port of Alex’s code (in this case an implementation of Fibonacci using fork/join) to Scala. We create a named function fib that will be recursively called by our RecursiveTasks. We also use an implicit conversion to map no-arg anonymous functions onto RecursiveTask instances using the technique for supporting SAM interfaces discussed in an earlier post. The resulting code looks pretty good:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

package org.fencepost.forkjoin

import jsr166y._

import org.scalatest.Suite

class ForkJoinTestFailOne extends Suite {

  implicit def fn2wrapper(fn:()=>Int):RecursiveTask[Int] = {

    return new RecursiveTask[Int] { override def compute = fn.apply }
  }

  def testFibonacci() = {

    def fib(n:Int):Int = {

      if (n <= 1)
        return n
      val f1 = { ()=> fib(n - 1) }
      f1 fork
      val f2 = { ()=> fib(n - 2) }
      (f2 compute) + (f1 join)
    }

    val pool = new ForkJoinPool()
    assert ((pool invoke { ()=> fib(1) }) == 1)
    assert ((pool invoke { ()=> fib(2) }) == 1)
    assert ((pool invoke { ()=> fib(3) }) == 2)
    assert ((pool invoke { ()=> fib(4) }) == 3)
    assert ((pool invoke { ()=> fib(5) }) == 5)
    assert ((pool invoke { ()=> fib(6) }) == 8)
    assert ((pool invoke { ()=> fib(7) }) == 13)
  }
}

Unfortunately an attempt to build with sbt gives an unexpected error:

[info] == test-compile ==
[info]   Source analysis: 2 new/modified, 0 indirectly invalidated, 0 removed.
[info] Compiling test sources...
[error] .../src/test/scala/org/fencepost/forkjoin/ForkJoinTestFailOne.scala:23: method compute cannot be accessed in jsr166y.RecursiveTask[Int]
[error]       (f2 compute) + (f1 join)
[error]           ^
[error] one error found

A bit of investigation reveals the problem; RecursiveTask.compute() is a protected abstract method in the fork/join framework. The compute method in the class returned by our implicit conversion consists of nothing more than a call to fib.apply() but there’s no way to know this when fib is defined. It follows that an attempt to access RecursiveTask.compute() from within the body of fib is (correctly) understood as an attempt to access a protected method.

How does Alex get around this problem in Clojure? He doesn’t; the problem is actually resolved via the Java wrapper. Note that in his Java code compute() has been “elevated” to be a public method. He’s thus able to call this method without issue from his “fib-task” function. Without this modification his code fails with similar errors [1].

Strangely, there’s no obvious way to resolve this issue within Scala itself. The language provides protected and private keywords to restrict access to certain methods but there is no public keyword; methods are assumed to be public if not annotated otherwise. As a consequence there’s no obvious way to “raise” the access level of a method in a subclass. We work around this constraint by way of an egregious hack; we define a new subclass of RecursiveTask containing a surrogate method that provides public access to compute. We then return this subclass from our implicit conversion.

Our new implementation looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

package org.fencepost.forkjoin

import jsr166y._

import org.scalatest.Suite

class ForkJoinTestFailTwo extends Suite {

  class Wrapper[T](somefunc:()=>T) extends RecursiveTask[T] {

    override def compute = somefunc.apply

    // RecursiveTask.compute() is protected and there's no obvious way to
    // elevate it's access level within a Scala class definition.  The type
    // system (very correctly) doesn't allow a random function access to
    // protected methods of a class even when that method is invoked by
    // a method within the class itself.  Defining a new method with standard
    // access resolves the issue.
    def surrogate = compute
  }

  implicit def fn2wrapper(fn:()=>Int):Wrapper[Int] = {

    return new Wrapper[Int](fn)
  }

  def testFibonacci() = {

    def fib(n:Int):Int = {

      if (n <= 1)
        return n
      val f1 = { ()=> fib(n - 1) }
      f1 fork
      val f2 = { ()=> fib(n - 2) }
      (f2 compute) + (f1 join)
    }

    val pool = new ForkJoinPool()
    assert ((pool invoke { ()=> fib(1) }) == 1)
    assert ((pool invoke { ()=> fib(2) }) == 1)
    assert ((pool invoke { ()=> fib(3) }) == 2)
    assert ((pool invoke { ()=> fib(4) }) == 3)
    assert ((pool invoke { ()=> fib(5) }) == 5)
    assert ((pool invoke { ()=> fib(6) }) == 8)
    assert ((pool invoke { ()=> fib(7) }) == 13)
  }
}