Functional Programming with Groovy
I have recently started the Coursera Functional Programming with Scala course (taught by Martin Odersky - the creator of Scala) - which is actually serving as an introduction to both FP and Scala at the same time having done neither before. The course itself is great, however, trying to watch the videos and take in both the new Scala syntax and the FP concepts at the same time can take a bit of effort. I wanted to work through some of the core FP concepts in a more familiar context, so am going to apply some of the lessons/principles/exercises in Groovy. Functions: If you have done any Groovy programming then you will have come across Groovy functions/closures. As Groovy is dynamically typed (compared to Scala's static typing), you can play it fairly fast and loose. For example, if we take the square root function that is demonstrated in the Scala course, it is defined as follows: def sqrt(x: Double): Double = ... As you can see, Scala expects the values to be typed (aside, you don't actually always need to provide a return type in Scala). But in the Groovy function it is: def sqrt = {x-> ... } A groovy function can be defined and assigned to any variable, thereby allowing it to be passed around as a first class object. If we look at the complete solution for calculating the square root of a number (using Newton's method - To compute the square root of "x" we start with an estimate of the square root, "y" and continue to improve the the guess by taking the mean of x and x/y ) def sqrtIter(guess: Double, x: Double): Double = if (isGoodEnough(guess, x)) guess else sqrtIter(improve(guess, x), x) def improve(guess: Double, x: Double) = (guess + x / guess) / 2 def isGoodEnough(guess: Double, x: Double) = abs(guess * guess - x) < 0.001 def sqrt(x: Double) = srqtIter(1.0, x) So that's in Scala, if we try Groovy we will see we can achieve pretty much the same thing easily: //Improve the guess using Newton's method def improve = { guess, x -> (guess + x / guess) / 2 } //Check if our guess is good enough, within a chosen threshold def isGoodEnough = {guess, x -> abs(guess * guess - x) < 0.001 } //iterate over guesses until our guess is good enough def sqrtIter = { guess, x -> if (isGoodEnough(guess, x)) guess else sqrtIter(improve(guess, x), x) } //wrap everythin in the square root function call def sqrt = {x -> srqtIter(1.0, x)} Recursion (and tail-recursion): As FP avoids having mutable state, the most common approach to solve problems is to break the problem down in to simple functions and call them recursively - This avoids having to maintain state whilst iterating through loops, and each function call is given its input and produces an output. If we again consider an example from the Scala course, with the example of a simple function that calculates the factorial for a given number. def factorial ={ n -> if (n == 0) 1 else n * factorial(n - 1) } factorial(4) This simple function recursively calculates the factorial, continuing to call itself until all numbers to zero have been considered. As you can see, there is no mutable state - every call to the factorial function simply takes the input and returns an output (the value of n is never changed or re-assigned, n is simply used to calculate output values) There is a problem here, and that is as soon as you attempt to calculate the factorial of a significantly large enough number you will encounter a StackOverflow exception - this is because in the JVM every time a function is called, a frame is added to the stack, so working recursively its pretty easy to hit upon the limit of the stack and encounter this problem. The common way to solve this is by using Tail-Call recursion. This trick is simply to have the last code that is evaluated in the function to be the recursive call - normally in FP languages the compiler/interpreter will recognise this pattern and under the hood, it will really just run the code as a loop (e.g. if we know the very last piece of code in the block of code is calling itself, its really not that different to just having the block of code/function inside a loop construct) In the previous factorial example, it might look like the last code to be executed is the recursive callfactorial(n-1) - however, the value of that call is actually returned to the function and THENmultiplied by n - so actually the last piece of code to be evaluated in the function call is actually n * return value of factorial(n-1). Let's have a look at re-writing the function so it is tail-recursive. def factorial ={ n, accumulator=1 -> if (n == 1) accumulator else factorial(n-1, n*accumulator) } factorial(4) Now, using an accumulator, the last code to be evaluated in the function is our recursive function call. In most FP languages, including Scala, this is enough - however, the JVM doesn't automatically support tail-call recursion, so you actually need to use a rather clunkier approach in Groovy: def factorial ={ n, accumulator=1 -> if (n == 1) accumulator else factorial.trampoline(n-1, n*accumulator) }.trampoline() factorial(4) The use of the trampoline() method means that the function will now be called using tail-call recursion, so there should never be a StackOverflow exception. It's not as nice as in Scala or other languages, but the support is there so we can continue. Currying: This is like function composition - the idea being you take a generic function, and then you curry it with some value to make a more specific application of the function. For example, if we look at a function that given values x and y, it returns z which is the value x percent of y (e.g. given x=10, y=100, it returns the 10 percent of 100, z=10) def percentage = { percentage, x -> x/100 * percentage } The above simple function is a generic mechanism to get a percentage value of another, but if we consider that we wanted a common application of this function was to always calculate 10% of a given value - rather than write a slightly modified version of the function we can simply curry the function as follows: def tenPercent = percentage.curry(10) Now, if the function tenPercent(x) is called, it uses the original percentage() function, but curries the value 10 as the first argument. (If you need to curry other argument positions you can also use the rcurry() function to curry the right most argument, or ncurry() which also takes an argument position - check the Groovy docs on currying for more info) Immutability: Immutability is partially supported in Java normally with use of the final keyword (meaning variables can't be changed after being initially set on object instantiation). Groovy also provides a quick and easy @Immutable annotation that can be added to a class to easily make it immutable. But really, there is more to avoiding immutable state than just having classes as immutable - As we have functions as first class objects, we can easily assign variables and mutate them within a function - so this is more of a mindset or philosophy that you have to get used to. For example: def list = ['groovy', 'functional'] //This mutates the original list list.add('programming') //This creates a new list leaving the original unchanged def newList = list.plus(2, 'programming') The first example is probably more like the Groovy/Java code we are used to writing, but that is mutating the state of the list - where as the second approach leaves the original list unchanged. Map Reduce: As a final note, there are some functions in FP that are pretty common techniques - the most famous of which these days (in part thanks to Google) is Map-Reduce, but the trio of functions are actually Map, Reduce(also known as Fold) & Filter - you can read more about the functions here (or just google them!), but these functions actually correlate pretty nicely to core Groovy functions that you probably use a lot of (assuming you are groovy programmers). Map map is the easiest to understand of the three. It takes in two inputs - a function, and a list. It then applies this function to every element in the list. You can basically do the same thing with a list comprehension however. Sound familiar? This is basically the .collect{} function in Groovy Reduce/Fold fold takes in a function and folds it in between the elements of a list. It's a bit hard to understand at first This one is a bit more complicated to descibe, but is the same as the .inject{} function in groovy Filter filter is easy. It takes in a 'test' and a list, and it chucks out any elements of the list which don't satisfy that test. And another simple one - filtering out a list for desired elements, this is Groovy's .findAll{} function As I said at the start, I am new to FP and coming from an OO background, but hopefully the above isn't too far from the truth! As I get further through the Coursera course I will try to post again, maybe with some of the assignments attempted in Groovy to see how it really stands up. Some useful references: Groovy docs on FP: http://groovy.codehaus.org/Functional+Programming+with+Groovy Coursera Scala course: https://www.coursera.org/course/progfun
October 14, 2013
·
37,818 Views
·
2 Likes
CORE
