Thursday, May 17, 2012

function(groovy) #3


function(groovy) #3

If all you have is a hammer, everything looks like a nail.

Abstract: The Groovy closure can be the return value from a method or another closure. This idea eases us into the world of higher order functions: functions that accept functions as parameters or return functions as their result. Functions as parameters is the key feature of the next blog. Functions as return values introduces the notion of currying and increasing the adoption of functions with only a single parameter.

Ken Barclay
kenbarc@googlemail.com

Previous:           The Groovy closure
Resources:        Chapter 12 Higher Order Functions

Advanced closures

A single function definition can effectively define a complete family of functions. Having defined the parent function, we are able to specialize from this single parent a number of related functions. To achieve this we use the notion of currying, named after the mathematician Haskell Curry. This idea is generally unfamiliar to the imperative programmer but is one worth getting acquainted with.

Example 3.1 demonstrates how the Closure class method curry is used to achieve the effect of currying. Closure multiply expects two parameters and returns their product. If we curry this function with the value 2, then we have created a new function which doubles its single parameter. Sensibly we choose to refer to this as twice. Equally, if we curry multiply with the value 4, then we have the closure quadruple. Both are functions of one parameter and can be used directly, or are candidates for use with any other function.

Example 3.1: Curried closure

    // multiply:: Integer * Integer -> Integer
final multiply = { final int x, final int y -> x * y }

    // twice:: Integer -> Integer
final twice = multiply.curry(2)
    // quadruple:: Integer -> Integer
final quadruple = multiply.curry(4)


assert twice(5) == 10
assert quadruple(5) == 20

The type signature informs us that multiply is a function which when given a pair of integers will return their product. If then we were able to call function multiply and give only one actual parameter, then we would get a result which is itself another function. For example, if we could call multiply with the parameter 2, then effectively the first formal parameter x is replaced throughout the definition for multiply with this value. Further, since the value for the parameter x is now specified, then this formal parameter can be removed from the definition. We then effectively produce the function:

{ final int y -> return 2 + y }

one that takes a single numeric parameter and returns 2 times its value. This function is the value bound to the identifier twice.

Since a Groovy closure is an object and a Groovy closure can return a closure, then currying can be achieved through another route. In Example 3.2 we have defined a closure add which takes a single parameter x and returns a closure. The returned closure is defined both in terms of its own parameter (y) as well as x, sometimes described as a free variable when used in this manner.

Example 3.2: Alternative currying

    // add:: Integer -> Integer -> Integer
final add = { final int x ->
  return { final int y -> x + y }
}

    // successor:: Integer -> Integer
final successor = add(1)

assert successor(5) == 6
assert successor(successor(5)) == 7

In Example 3.2 the call add(1) delivers a closure that is bound to the successor identifier. In that closure the free variable x has been fixed as the value 1.

Interestingly function add expects a single parameter and delivers a function. That function also expects a single parameter and delivers some result. As shown we are able to support currying without using the curry method. It also moves us to adopting the notion of functions only ever taking one parameter.

Why? Well first we get currying for free. Second, it greatly enhances our capacity to compose functions. Function composition in the previous blog expected them to operate with only a single parameter.

Suppose we want to develop a curried version of a binary function f which is uncurried and of the type A * B -> C. This binary function f expects its parameters as a pair but its curried version will apply them sequentially. We therefore have to form them into a pair before applying f to them. The function C does exactly this:

    // C:: (A * B -> C) -> A -> B -> C
final C = { f -> { a -> { b -> f(a, b) }}}

Again, the signature reveals what is happening. Function C expects a function as its first parameter. That parameter function has the signature A * B -> C, an uncurried binary function. Function C returns the curried function with the signature A -> B -> C, as required. We can use C where we need to transform an uncurried binary function into its curried form.

            Example 3.3 introduces function C and its complementary function U. Using U we convert the curried mul function into it uncurried equivalent, mulU. Using C we transform the uncurried mulU function into its curried equivalent, mulC.

Example 3.3: Curried/uncurried transformation

    // mul:: Integer -> Integer -> Integer
final mul = { final int x -> { final int y -> x * y }}

    // U:: (A -> B -> C) -> (A * B) -> C
final U = { final f -> { final a, final b -> f(a)(b) }}

    // mulU:: (Integer * Integer) -> Integer
final mulU = U(mul)

assert mul(3)(4) == 12
assert mulU(3, 4) == 12
assert U(mul)(3, 4) == 12


    // C:: (A * B -> C) -> A -> B -> C
final C = { final f -> { final a -> { final b -> f(a, b) }}}

    // mulC:: Integer -> Integer -> Integer
final mulC = C(mulU)

assert mulC(3)(4) == 12

Various factory design patterns are used throughout OO-land. The earlier examples showed currying as a mechanism for developing a family of functions from a single definition. In effect currying is a form of factory for functions.

Many of the emerging examples do not exploit Groovy meta-programming capabilities. They also make ever greater demands on the types of quantities, including our function parameter and return types. This work makes a strong case for a Groovy static type checker.




Friday, May 11, 2012

function(groovy) #2


function(groovy) #2

If all you have is a hammer, everything looks like a nail.

Abstract: The Groovy closure is central to making my coding more declarative. Different ways of employing the Groovy closure have all contributed to a more declarative style. The ability to combine simple closures into more complex closures encourages a compositional style not used in OO-land. Method bodies can be simplified by defining simple and complex closures that provide the required logic, often without recourse to any local method state variables.

Ken Barclay
kenbarc@googlemail.com

Previous:           Introduction
Resources:        Chapter 11 Closures
                        Chapter 12Higher Order Functions

The Groovy closure

Fundamental to this work is the Groovy closure. A closure is an object that represents an executable block of code. Like other objects, a closure can be presented with a literal, can be  referenced by an identifier, have a method invoked on it, passed as a parameter in a method call or closure call, can be the property of some other object, or be a member of a collection such as a list. The closure was probably what first attracted me to Groovy.

A closure carries an implicit binding to all the variables referenced within it. In other words, the closure encloses a context around what it references. This means that any variables in scope when the closure is defined can be used and modified by the closure. This will prove very important in the next and following blogs.

Groovy supports writing anonymous closures that can be used in our programming when there is no requirement to define an identifier for it. Anonymous closures are expressed as closure literals. Since a closure literal is an instance of the class Closure, then to obtain some behavior from it, we invoke one of the class methods. For the moment we are principally interested in the method call that executes the closure. Example 2.1 illustrates.

Example 2.1: Closure literals

assert { int x -> return x * x }.call(2) == 4   // explicit return
assert { int x -> return x * x }(2) == 4           // implicit call
assert { int x -> 1 + x }(2) == 3                     // implicit return
assert { x -> 1 + x }(2) == 3                           // optional types

The closure maximum3 in Example 2.2 finds the larger of its three integer parameters. It defines the identifier maximum and binds it to a local closure. This is referred to as a nested closure since it is introduced in the body of the enclosing closure. Nested closures have the enclosing closure body in which they are defined as their scope. This means that they can only be referenced in their scope and have no existence outside of this scope. We will use this in what follows.

The context for the nested closure maximum includes those identifiers in the scope of the enclosing closure maximum3. This means that within the body of maximum we could refer directly to the identifiers x, y and z. It also means that the definition of maximum may not include definitions for these identifiers otherwise an error reporting that the current scope already includes the variable definition. As shown, we have had to name the formal parameters of maximum as anything other than x, y or z.

Example 2.2: Scope

    // maximum3:: Integer * Integer * Integer -> Integer
final Closure<Integer> maximum3 = { final int x, final int y, final int z ->

        // maximum:: Integer * Integer -> Integer
  final Closure<Integer> maximum = { final int a, final int b ->
    (a > b) ? a : b
  }
   
  maximum(x, maximum(y, z))
}

assert maximum3(12, 34, 56) == 56
assert maximum3(56, 34, 12) == 56
assert maximum3(12, 34, 34) == 34
assert maximum3(12, 12, 12) == 12

A recursive closure is one that calls or invokes itself. What we cannot do is make a direct recursive call through the name of the closure as suggested by:

final factorial = { final int n ->
    return (n == 0) ? 1 : n * factorial(n - 1)                   // ERROR
}

The problem is that the identifier factorial is not bound to the closure literal until the closure definition is complete. Hence the recursive call in the closure body refers to the, as yet, unknown identifier factorial.

Examples 2.3 and 2.4 show alternative strategies. In Example 2.3 the identifier recFactorial is defined but uninitialized. On the next statament it is assigned to the closure literal. This time the recursive call is accepted since the recFactorial identifier is known to the compiler. The approach, of course, is dependent on assignment in which an identifier is bound once to its default null value, then assigned a closure reference.

Example 2.3: Recursive closures

    // factorial:: Integer -> Integer
final Closure<Integer> factorial = { final int n ->
  def recFactorial
  recFactorial = { final int m ->                     // recFactorial:: Integer -> Integer
    (m == 0) ? 1 : m * recFactorial(m - 1)
  }
  recFactorial(n)
}

assert factorial(5) == 120
assert factorial(1) == 1
assert factorial(0) == 1

In Example 2.4 we avoid this problem by defining recFactorial to have an additional formal parameter, self, that when the closure is called is bound to the closure itself. Within the closure body we can use this identifier to make the recursive call. The enclosing closure factorial calls recFactorial and passes recFactorial as the first actual parameter.

Example 2.4: Recursive closures

    // factorial:: Integer -> Integer
final Closure<Integer> factorial = { final int n ->
  final recFactorial = { final self, final int m ->          // recFactorial:: Closure * Integer -> Integer
    (m == 0) ? 1 : m * self(self, m - 1)
  }
  recFactorial(recFactorial, n)
}

assert factorial(5) == 120
assert factorial(1) == 1
assert factorial(0) == 1

Closures that call themselves as their last action are called tail recursive. Closure recFactorial is made tail recursive by introducing a second accumulating parameter. We see in Example 2.5 how Groovy's trampoline method is then used to make calls sequentially using only a single stack frame until the result (a very, very, very large number) is delivered.

Example 2.5: Tail recursive factorial closure

    // factorial:: BigInteger -> BigInteger
final factorial = { final BigInteger n ->
  def recFactorial
  recFactorial = { final BigInteger m, final BigInteger acc ->   // recFactorial:: BigInteger -> BigInteger
    (m == 0) ? acc : recFactorial.trampoline(m - 1, m * acc)
  }
  recFactorial = recFactorial.trampoline()
  recFactorial(n, 1G)
}

println factorial(500G)

Recursive functions generally bring one of our declarative features to the table, namely the absence, or at least a reduction, of state. One could imagine an implementation for factorial in terms of a program loop with a control variable as well as a local variable to accumulate the result. So where has the state gone in the recursive solutions? In effect, the state is conveyed through the actual parameter values. Tagging the formal parameters as final further emphasizes our intention not to vary these references. Further, it is generally easier to reason about a recursive function than an imperative one since it is expressed in terms of use-cases ─ a base case and one or more than recursive cases.

Closures can also be parameters to methods and to other closures. As we will shortly demonstrate, closures can also be the return value from a method/closure call. Invariably the closures have one or more parameters and deliver a result value. In effect they operate like mathematical functions. As a consequence we shall consider the terms closure and closure function (or simply function) as synonyms. We will use the term function when describing a transformation of inputs into an output. The term closure will be reserved for when we are discussing some technical aspect of the Groovy constructs.

Through closure functions as parameters and closure functions as results we are able to fully exploit the machinery of these general functions, such as function composition. The resulting closure function definitions can be both more concise and more readable than traditional approaches. This can sometime prove  a difficult and alien concept for the imperative, object-oriented programmer, but one worth learning.

In Example 2.6 function twice is a higher order function as it expects a function as its first parameter. The interpretation of the signature for twice is that it returns an Integer as its value. Two parameters are required, the second of which is an Integer. The first parameter is the function parameter. Its signature is Integer -> Integer showing that we expect a function of this type as the first actual parameter. The effect of twice is to repeatedly apply the function to the numeric parameter.

Example 2.6: Simple higher order closure function

    // triple:: Integer -> Integer
final Closure<Integer> triple = { final Integer x -> 3 * x }

    // quadruple:: Integer -> Integer
final Closure<Integer> quadruple = { final Integer x -> 4 * x }

assert triple(2) == 6
assert quadruple(3) == 12

    // twice:: (Integer -> Integer) * Integer -> Integer
final Closure<Integer> twice = { final Closure<Integer> f, final Integer x ->
  return f(f(x))
}

assert twice(triple, 2) == 18
assert twice(quadruple, 3) == 48

Perhaps one of the more important characteristics of functions is composition, wherein you can define one function whose purpose is to combine other functions. Using composition, two or more simple functions can be combined to produce a more elaborate one. For example, suppose we have two arithmetic functions f and g, as in z = f(t) and y = g(t). One way of composing these two functions would be to first compute y, and then to compute z from y, as in y = g(x) followed by z = f(y). One could get the same result with the single composition written z = f(g(x)). We write this as f g, meaning function f composed with function g.

Function composition lets us compose a solution by combining separately designed and implemented functions. Structuring a large solution into separate functions simplifies the programming activity. The functions can be defined, implemented and tested separately. Simple functions can be used to construct more elaborate functions, reducing the burden and complexity of a system. The functions can also be defined for one application and re-used in other applications.

The latest compiler releases for Groovy now includes overloaded versions of the leftShift operator (<<) and the rightShift operator (>>) that apply to closures. The << operator acts exactly as function composition as described above. The expression c1 << c2 first applies the function c2 to its argument then function c1 to the result. Equally c1 >> c2 is the forward composition operator, applying c1 to its argument then c2 to the result. Example 2.7 illustrates.

Example 2.7: Function composition

final successor = { final int x -> return 1 + x }
final triple = { final int x -> return 3 * x }
final quadruple = { final int x -> return 4 * x }

assert successor(5) == 6
assert triple(5) == 15
assert quadruple(5) == 20

final twelveTimes = triple << quadruple
final threePlusOne = triple >> successor

assert twelveTimes(5) == 60
assert threePlusOne(5) == 16

Since a closure is an object it can be an element in a list. A list of closures could then act as the list of handlers for a menu. A dynamically changing menu could be mirrored by a dynamically changing list of closures. Anyone of these closures might be assembled dynamically as we have presented here.

The command design pattern provides a way to encapsulate behavior into a class. But wrapping the behavior I want in a command class is an artifact of OO programming. The command design pattern can be achieved with little ceremony using Groovy functions.

Various factory design patterns are used throughout OO-land. The earlier examples showed currying as a mechanism for developing a family of functions from a single definition. In effect currying is a form of factory for functions.

Monday, May 7, 2012

function(groovy) #1


function(groovy) #1

If all you have is a hammer, everything looks like a nail.

Abstract: If my Groovy builder code is described as declarative then why is the remainder of my code not declarative? If declarative programming means I can put more emphasis on what I wish to achieve and less emphasis on how it is achieved then I should follow this principle throughout all my code. But I don't. Why not?

Ken Barclay
kenbarc@googlemail.com

Introduction

In this series of blogs I describe my experience of fusing a functional programming style with the object oriented features of Groovy. Incorporating functional programming constructs into Groovy arose from a disappointing experience I had when developing a range of applications originally intended to showcase some of Groovy's great features.

The applications had two major features in common. They all processed information from web services and they all presented that data in a GUI. For example applications might obtain meteorological data from Google's weather service, financial data from Yahoo, photographs from Flickr, videos from Youtube, or music data from iTunes. GUIs allowed the user to interact with that data.

Groovy's builder technology was an obvious choice for developing the UIs. Initially SwingBuilder was adopted, but later a custom FXBuilder was developed so I could leverage the richer components of JavaFX. Either way, the satisfaction of adopting a Groovy builder is the declarative nature of the resulting code. Declarative code places more emphasis on the what rather than the how. Example 1.1 reminds us how this would appear.

Example 1.1: GUI builder

def mainStage = builder.stage(title: "Example 01", x: 100, y: 100, width: 400, height: 300) {
  scene(stylesheets: "file:///C:/css/glib.css") {
    borderPane() {
      top(alignment: CENTER, margin: [10.0, 10.0, 10.0, 10.0]) {
        text(text: 'Example 01', id: 'text20')
      }
      center(margin: [10.0, 10.0, 10.0, 10.0]) {
        gridPane(hgap: 4, vgap: 4) {
          text(text: 'Please enter your name:', id: 'text16')
          textField(ID: 'locationTF', text: '', onAction: controller.onName)
         
          // ...
        }
      }
      bottom(alignment: CENTER, margin: [10.0, 10.0, 10.0, 10.0]) {
        button(text: 'Close', onAction: controller.onClose)
      }
    }
  }
}

In Example 1.1 factory methods, such as button and textField, are used to define the JavaFX components while nested closures define the structure and hence the appearance of the UI. The factory method calls are decorated with named parameters that set the various properties on the components. The builder aims to do as much of the heavy lifting, reducing the effort required by the developer. For example, the builder translates the factory method calls and their parameters into code that creates and initializes the components. The builder also arranges for the UI components defined in a closure to be added as child components of the enclosing container component.

That was the good part. What followed was the disappointment. The applications were completed by developing the supporting classes. They were anything but declarative, especially the method bodies that were assembled from the usual control flow statements. If statements within while statements and for statements within switch statements. I never thought of myself as a sloppy programmer but the implementation of these methods seemed to stand in sharp contrast with the declarative builder code.

Decomposing complex methods and providing private support methods or other support classes helped a little but still the code had a smell about it. I seemed to be operating at too low a level of abstraction when compared with Groovy's builders. Interestingly the implementation for the Groovy builders were themselves not especially declarative. Hmmm!

Using a search engine for declarative programming picked out many interesting articles often with attempts at informal definitions. Usually the what versus the how was cited. Declarative systems such as Yacc and SQL were compared to imperative programming languages. Maybe an imperative language like Groovy is not expected to be declarative because the programmer has to spell out the actions and their order.

When looking for actual illustrations most articles referred the reader to functional programming. Some characterized functional programming languages as examples of declarative programming along with logic programming languages and constraint programming languages.

So what is it that makes these languages declarative and what lessons might be learnt? The builder code above gives some pointers. First, state does not seem to play a major part in this code. There is state in the code. The named parameters on the factory method calls are initializing the state properties of the UI components. But, significantly, there is no explicit state transitions.

Second, there are no binding of results to variables. The builder code is like a single expression which, at the top level, delivers a Stage object. Expressions in the sub-levels deliver the various sub-components that form the UI. The sub-expressions are used to support assembly of the enclosing expression.

Perhaps then I should aim to make my Groovy coding much less dependent on state and state transitions. What place then for my use of control flow such as if statements and for loops? Usually they manipulate some state. Perhaps finding a solution for this will address my concern that I was operating at too low a level of abstraction.

All this may seem at odds with an imperative programming language such as Groovy. However, I can see immediately that if I have less state transitions I will have less testing to do since a significant part of testing is to ensure the transitions are correct.

What other aspects of functional programming might make a contribution to a more declarative style. What contribution might Groovy's closures make? How will my use of control flow statements such as for loops change? What can be done to reduce my use of state? Let's see where this takes us...