There and Back Again - A Developer's Recursion Tale

Recursive functions are so 2009. All the cool kids are now scrambling to convert those legacy recursive functions into stack based iteration. Why would you ever need this, you ask? Maybe you’ve heard of my friend “StackOverflowError”, he likes to hang out on the JVM. Or maybe you’re a browser kinda guy and you’ve seen your alert messages say “Stack Overflow”. Or worst case (like me), you’re supporting IE6 and you finally figured out that the “Browser shows a blank screen” defect you can’t reproduce is IE’s way of overflowing (oh yes it really is). Well, stack based iteration is a way to leave your nice recursive function the way it is, yet still avoid the overflow errors. You just have to keep track of the function stack frames yourself by adding a little boilerplate around your method (and even that can be cleaned up fairly easily).

So here is the tale of taking the road now commonly traveled. Learning to program imperatively, writing some beautiful recursive functions, and then ripping it out again because of platform limitations. There and Back Again – A Developer’s Tale of Recursion...

Read the full article over on the Canoo blog. And if you want to be kind and vote, then head over to DZone first.

Groovy 1.7.2 - Three Features Worth the Upgrade

Groovy 1.7.2 was released 22 hours ago, so by now you have surely spent hours playing with the new bits and combing through the release notes looking for new nuggets of productivity.

Or maybe not.

For all those busier than me, here are the top 3 reasons to upgrade to the point release:

Convert GPathResults to XML - JIRA 1178

XmlSlurper is a great way to parse, manipulate, and generally tease XML. The problem is that once you start drilling into XML using the dynamic syntax, then you are working with GPathResults objects and not plain text or Strings. It was quite hard to pull out snippets of XML as text. No more! Now you can use XmlSlurper to pull out pieces of XML and then easily manipulate them as text by converting a GPathResult into a String.

Here is the classic XML structure from the XmlSlurper documentation:

def CAR_RECORDS = '''
   <records>
     <car name='HSV Maloo' make='Holden' year='2006' >
       <country>Australia</country>
       <record type='speed'>Production Pickup Truck with speed of 271kph</record>
     </car>
     <car name='P50' make='Peel' year='1962'>
       <country>Isle of Man</country>
       <record type='size'>Smallest Street-Legal Car at 99cm wide and 59 kg in weight</record>
     </car>
     <car name='Royale' make='Bugatti' year='1931'>
       <country>France</country>
       <record type='price'>Most Valuable Car at $15 million</record>
     </car>
   </records>
 '''

Hopefully Blogger hasn't totally destroyed the XML tags. Yet one more reason to hate on XML. So anyway, XmlSlurper makes it trivial to pull out the second car element from the example XML:

def records = new XmlSlurper().parseText(CAR_RECORDS)
def secondCar = records.car[1]
assert secondCar.getClass() == NodeChild
assert secondCar.toString() == 'Isle of ManSmallest Street-Legal Car at 99cm wide and 59 kg in weight'

There are a few problems with this example, and it isn't that the second car element has an index of 1. The secondCar variable is of type NodeChild. This is great if you want to perform more dynamic matching against NodeChild, but not so great if you want to get the full XML of the child and all descendants. The toString() is pretty meaningless, it's just a concatenation of all the child node values. In 1.7.2, StreamingMarkupBuilder lets you quickly get the child XML as a String. The assertion and code sample is messy, but the feature isn't:

def xmlString = new StreamingMarkupBuilder().bindNode(secondCar).toString()
assert xmlString == "<car name='P50' year='1962' make='Peel'><country>Isle of Man</country><record type='size'>Smallest Street-Legal Car at 99cm wide and 59 kg in weight</record></car>"

Nice. I understand you could somehow get the XML in previous Groovy versions, but I never figured it out. I'm lucky if I can just get something to pretty print.

Easier Map and Property Sorting - JIRA 2597

It is easier than ever to sort Maps and Properties objects. The first step is to create an unsorted Map:

def map = [c: 1, b: 2, a: 3]

In previous Groovy releases there were two options to sort a Map. One sort method took a closure that would be invoked like a Comparator, and the other way is just to wrap the Map in a TreeMap. Here are some assertions showing how they worked:

assert map.sort { Entry it -> it.key }*.key == ['a', 'b', 'c']
assert new TreeMap(map)*.key == ['a', 'b', 'c']

Not bad, but now the Map object has a no-arg sort that does default sorting and an API that lets you pass a real Comparator:

assert map.sort()*.key == ['a', 'b', 'c']
assert map.sort({ a, b -> a <=> b } as Comparator)*.key == ['a', 'b', 'c']

And remember, these methods return a new Map, they do not mutate the original. No Maps are harmed during the sorting of Maps.

ncurry and rcurry - JIRA 4144

The curry method has been around Groovy for a long time. It lets you bind variables into closures from left to right:

def multiply = { a, b -> a * b }
def doubler = multiply.curry(2)
assert doubler(4) == 8

In the above example, multiply has a type signature of "Object -> Object -> Object" (two Object parameters and an Object return type). When you curry multiply into doubler you get a type signature of "Object -> Object" (one Object parameter and an Object return type). Parameters are bound from left to right. Curry always bound the left most parameter in the parameter list. Until now.

rcurry will bind parameters from right to left. So a halver can now be made from a divider. Whee!

def divider = { a, b -> a / b }
def halver = divider.rcurry(2)
assert 5 == halver(10)

ncurry is the API sibling of curry and rcurry. It lets you bind parameters based on the integer index of the parameter in the signature. So you can bind parameter 2, 3, 4, or whatever. Check it out:

def operation = { int x, Closure f, int y -> f(x, y) }
def divider = operation.ncurry(1) { a, b -> a / b }
assert 5 == divider(10, 2)

Before you go too crazy with ncurry and rcurry, be warned that I think there is a bug when you try to mix them. Using ncurry and rcurry alone seems to work great, but rcurrying an ncurried closure does not currently work. I have a hunch that this does not effect a whole lot of people. I'll post a comment when I know what is wrong or when it is fixed.

Now go upgrade to 1.7.2!

Y-Combinator in Groovy

File under uselessly cool (for now at least).

A Y-Combinator in Groovy!

def Y = { le -> ({ f -> f(f) })({ f -> le { x -> f(f)(x) } }) }

Update: @mrdillon was kind enough to point out that my original Y used recursion. His revision is better.

And to prove it works, you can define a recursive factorial function without using recursion in the language.

def factorial = Y { fac ->
    { n -> n <= 2 ? n : n * fac(n - 1) }
}

assert 2432902008176640000 == factorial(20G)

The one-liner closure in the middle is the meat of the method definition and is a classic (i.e. horribly inefficient, known deficient) factorial implementation. I wouldn't write code this way but it makes a nice terse example when written in one line.

So is this useless? Not at all! But getting to an explanation of its use requires just a few examples.

Consider a recursive function that determines if an element is a member of a list. I guess you should also consider that List#contains(Object) does not exist. Here is a first draft of such function:

def isMember(element, list) {
    if (!list) false
    else
        if (list.head() == element) true
        else isMember(element, list.tail())
}

assert isMember(2, [1, 2, 3])

Let's just step through it briefly.

if (!list) false
... a simple terminating condition, an empty list never contains the element

if (list.head() == element) true
...if the first item in the list is the element then yes, we found it!

else isMember(element, list.tail())
....otherwise, check all the other items in the list for the same condition

Over time, the isMember will be recursively applied to each element in the list, and call stacks will build up in memory until the element is found, the list is fully checked, or you run out of stack space.

The problem with isMember is the redundancy. Notice how 'element' is always passed as a parameter? The value never changes over the life of the function application, so we shouldn't bother passing it every time. We have closures, so why don't we just 'close over' the value of element and remove the redundant data passing?

We can do it, but because of Groovy's limited recursion support, the implementation is kinda ugly. What I'd like to do is create a recursive closure that captures element once, but Groovy forces me into declaring an inner looping function on one line and defining it on another:

def isMember(element, list) {
    def inner
    inner = { lat ->
        if (!lat) false
        else
            if (lat.head() == element) true
            else inner(lat.tail())
    }
    inner(list)
}

assert isMember(2, [1, 2, 3])

This is where Y comes into play. I want a recursive closure and that is what Y does! Check out how Y allows me to define a recursive function locally within a method. No more split on declaration/definition.

def isMember = { element, list -> {
    def inner = Y { inner ->
        { lat ->
            if (!lat) false
            else
                if (lat.head() == element) true
               else inner(lat.tail())
        }
    }
    inner(list)
}

assert isMember(2, [1, 2, 3])

It's not uselessly cool any more is it? Oh wait, without tail call optimization on the JVM you will surely run out of stack space with a nasty StackOverflowException by writing code like this. So don't do it!

I guess it's pretty useless after all.

And if you're looking for a fun weekend project, why don't you do a different one of the Rosetta Code challenges
that are missing for Groovy: http://rosettacode.org/wiki/Tasks_not_implemented_in_Groovy

Tschüs!

How to Tell Your Co-Workers Have Discovered Functional Programming

Three ways to tell that your co-workers are learning a Functional Programming language at home:

1. You've found the number of .class file in your project quadrupled in the last month.

Here is an output directory with 17 .class files, only 2 of which are not inner classes, most of which are anonymous.



See all those dollar signs indicating inner/anonymous classes? Uh oh, looks like someone discovered shitty lambdas. Your chaos meter should be increasing... will your project be maintainable of it's not idiomatic Java?

2. You've found a class named Pair

public class Pair<T, U> {

   private final T left;
   private final U right;

   public Pair(T left, U right) {
       this.left = left;
       this.right = right;
   }

   T getLeft() { return left; }
   U getRight() { return right; }

   static <T, U> Pair from(T left, U right) {
       return new Pair<T, U>(left, right);
   }
}

It's not a tuple, but it's about 2/3 of the way there! There's already jfun.util.Pair in JFun and gnu.lists.Pair in Gnu Lists, and now you've got your own too. Hooray. But wait, how will you maintain your code base if the declared name of your data structures don't tell you how it's meant to be used? Chaos... level... rising...

3. You've found a widely implemented one-method highly generic interface

An interface like this has over 100 implementations, many of which are anonymous:

public interface Transformer<T, U> {
   U transform(T input);
}

This is equivalent to F in Functional Java and Transformer5 in JConch.

At this point your chaos meter should be off the chart. These functional programmers are surely ruining your system and livelihood. So, I'm hesitant to mention what happens when you combine all of them together:

Transformer identityfunction =
   new Transformer<Pair<String, String>, Pair<String, String>>() {
       public Pair<String, String> transform(Pair<String, String> input>) {
           return input;
       }
   }
}

Voila, an anonymous function object that uses the Pair class to make a 1-arity method into a 2-arity method, returning multiple values.

These are the trials and tribulations of finding the appropriate use of new programming paradigms in old languages. Looking at version control history, the person that committed all these sins was... me. Will this be the Java code I write in two years time? Certainly not. But which of these example is the growing pains of learning FP and which of these will still be with me in the future?

Comments are open!