Mixing dynamic and static code in Groovy

This article continues story started in two previous articles of me:

• On static compilation of Groovy
• Static Groovy and concurrency: type inference in action

One of the main promises of staticly typed Groovy is ability to easily mix dynamic and static code together. Today I am going to show how it is done and what's going on during compilation.

As usually we will work with some example, which should help us to see everything in action. As additional bonuses we will talk about tail recursion and concurrency.

Task: for given range of integers generate XML report containing for each number that either it is prime or all divisors of the number

Here is report we want to generate

<numbers>
  <number value='2' prime='true' />
  <number value='3' prime='true' />
  <number value='4' prime='false'>
    <divisor value='2' />
    <divisor value='2' />
  </number>
  <number value='5' prime='true' />
  <number value='6' prime='false'>
    <divisor value='2' />
    <divisor value='3' />
  </number>
  <number value='7' prime='true' />
  <number value='8' prime='false'>
    <divisor value='2' />
    <divisor value='2' />
    <divisor value='2' />
  </number>
<numbers>

Here is solution of the problem

              new MarkupBuilder ().numbers {
                  def divisors = { int n, Collection alreadyFound = [] ->
                      if (n > 3)
                          for(candidate in 2..<n)
                             if (n % candidate == 0)
                                return doCall (n / candidate, alreadyFound << candidate)

                      alreadyFound << n
                  }

                  (2..1500).each {
                    def divs = divisors(it) ]
                    if (divs.size () == 1)
                        number ([value: it, prime:true ])
                    else {
                        number ([value: it, prime:false]) {
                          divs.each { div ->
                            divisor([value: div])
                          }
                        }
                    }
                  }
              }

 Yes, that's true - 23 lines above is really it. Thanks to expressiveness of Groovy and powerful standard libraries.

Let us analize what's going on here. First of all our main tool is wonderful groovy.xml.MarkupBuilder, which takes care for generating XML output. Everyone familiar with Groovy will recognize following code. 

            new MarkupBuilder ().numbers {
                ...................
                  (2..1500).each {
                    def divs = divisors(it)
                    if (divs.size () == 1)
                        number ([value: it, prime:true ])
                    else {
                        number ([value: it, prime:false]) {
                          divs.each { div ->
                            divisor([value: div])
                          }
                        }
                    }
                }
            }

But what is interesting here is that there are only four calls, which dispatched dynamically (or slowly if you wish). And this is exactly the calls we wat to be dynamic (to allow MarkupBuilder to do his job)

1. numbers - line 1
2. number - lins 6 & 8
3. divisor - line 10

All the rest don't need to introduce any dynamic overhead, so it does not. We will see in a second that it is obviously for compiler that divisors(it) is java.util.Collection and the rest follows from simple type inference.

NB: Method each used above is a little bit different from the standard one used in Groovy runtime. It does exactly the same but without dynamic calls to Iterator and Closure. Compiler recognise when it is not necessary and use optimized version.

Let us now have a look on calculation of divisors. Our algorithm is next to trivial

• check candidates while we found divisor
• when found put it in to result java.lang.Collection
• apply the same procedure to original number divided to found divisor

                  def divisors = { int n, Collection alreadyFound = [] ->
                      if (n > 3)
                          for(candidate in 2..<n)
                             if (n % candidate == 0)
                                return doCall (n / candidate, alreadyFound << candidate)

                      alreadyFound << n
                  }

Here is all power of tail recursion meets together with type inference and default parameters. All type information we had to provide was types of parameters of our closure. Compiler is able to deduct the rest including return type of the calculation (java.util.Collection). Seems like killer combination.

Call to method doCall seems a little bit magical but not to ones, who familiar with anatomy of Groovy closures. It is conventional name for methods implemented by closures.

So in fact, what we see above is the method doCall calling itself recursively. Exactly the case, which can be optimized by the compiler.

We are done with our basic task.

Let us now add a little bit of concurrency in to the mix.

What we want to do is to generate our divisors by several threads (using java.util.concurrent.Executor) and build markup in the main thread.

 Modifications required by our code is minimal.

              new MarkupBuilder ().numbers {
                  def divisors = { int n, Collection alreadyFound = [] ->
                      if (n > 3)
                          for(candidate in 2..<n)
                             if (n % candidate == 0)
                                return doCall (n / candidate, alreadyFound << candidate)

                      alreadyFound << n
                  }

                  (2..1500).iterator().mapConcurrently(Executors.newFixedThreadPool(10), false, 50) {
                     new Pair(it, divisors(it))
                  }.each { pair ->
                    if (pair.second.size () == 1)
                        number ([value: pair.first, prime:true ])
                    else {
                        number ([value: pair.first, prime:false]) {
                          pair.second.each { div ->
                            divisor([value: div])
                          }
                        }
                    }
                  }
              }

First of all, we change a little bit our main each-loop. Now, it doesn't calculate divisors but deals with pairs (integer, collection of divisors). Thease pairs represented using Iterator<Pair<Integer,Collection>>. Class Pair is part of standard library, which is under development together with static Groovy. I hope it is easy to imagine what does it do.

Secondly, and more interesting, we use another standard method, which maps Iterator to Iterator (in our case Iterator<Integer> mapped to Iterator<Pair<Integer,Collection>) by executing given mapping function on given java.util.concurrent.Executor and making sure that no more than given number of mappings (50 in our case) are executed concurrently. This method also has way to control if we need to keep order of elements or nor (false in our case)

It sounds like pretty complicated algorithm but in fact it doesn't. Here is a bit simplified code (no order control, no handling of default values for parameters)

  static <T, R> Iterator<R> mapConcurrently(Iterator<T> self,
                                            Executor executor,
                                            int maxConcurrentTasks,
                                            Function1<T, R> op) {
        [ pending: new AtomicInteger(),
          ready: new LinkedBlockingQueue<R>(),

          scheduleIfNeeded: {->
            while (self && ready.size() + pending.get() < maxConcurrentTasks) {
              pending.incrementAndGet()
              def nextElement = self.next()
              executor.execute {-> ready << op.apply(nextElement); pending.decrementAndGet() }
            }
          },

          next: {->
            def res = ready.take()
            scheduleIfNeeded()
            res
          }, 

          hasNext: {-> scheduleIfNeeded(); !ready.empty || pending.get() > 0 },

          remove: {-> throw new UnsupportedOperationException("remove () is unsupported by the iterator") },
        ]
  }

What really impresses me is how expressivness of Groovy allows to write non-trivial concurrent algorithm in just several lines of code. I leave for curious reader to implement the same with Java.

 Thank you for reading and till next time.