Closures and Currying and Partials . . . oh my!

So we were having a discussion in the lab the other day about some of the more functional features of the Python language (and of course, I made sure to give Scala some love as well).  In particular, we were discussing some code where I’d made use of Python’s partials.  My lab mate made a comment to the effect of “this seems related to closures.”

Indeed, there are three functional programming concepts that came to the top of my head which are all related, but these relationships, and indeed  the tools themselves are often overlooked in most programming courses which do not  focus on the functional style.  These three concepts are:

1. Closures
2. Currying
3. Partials

Now, the wikipedia article on closures is pretty good, but alas, it has no scala example!  But before we get to the example, what is a closure?  Well, consider first a “normal” function.

[cc lang=’scala’ ]

def plus( x : Int, y : Int ) = { x + y }

[/cc]

Scala functions don’t get too much simpler than this.  The plus function takes two Ints and returns their sum.  What I want to draw your attention to here are the variables x and y.  These variables, as we are used to, are explicitly declared in an argument list.  When we call the plus function, we pass in two Ints, which the compiler takes as x and y, and we say that the values we pass in are bound to the variables x and y.  So, what if I defined the following function

[cc lang=’scala’]

def plus( x : Int, y : Int ) = { x + y + z }

[/cc]

Uh ohh; what is this z you might ask? It’s not defined in the body of the function; it’s not passed in as a variable, so what is it?  Well, in the context of closures, z is a free variable.  That is, given just the context I’ve shown you above it is unbound (and also undefined).  However, what if I showed you the following piece of code

[cc lang=’scala’]
def plusZ = {
val z = 3
def plus( x : Int, y : Int ) = { x + y + z }
plus(1, 2)
}
[/cc]

Ok, so this function is not very useful, but this is a pedagogical example. So, what’s the behavior of this function? In particular, what happens when I call “plusZ”? Take a wild guess . . . it returns 6. That free variable, z, in the plus function was bound to 3 in the enclosing lexical scope of the plusZ function. Essentially, a closure is this process; where free variables within functions are bound to values. The term comes from the proper terminology of referring to the free variables in the function; the function is said to be “closed over” its free variables. “Regular” functions, are just those with no free variables. The variables of which they make use are explicit arguments, and are, by construction, bound within the scope of the function.

Next, lets look at currying. The syntax for currying varies from language to language as does the syntax support. In Scala, a curried function may look something like this

[cc lang=’scala’]
def plus(x : Int)(y : Int) = { x + y }
[/cc]

Again, this is our good old plus example. Our normal plus function has the type (x:Int, y:Int)Int, or more readably, (Int, Int) => Int. We say plus is a function which takes two Ints as arguments and returns an Int. What’s the type of our curried plus function though? Well, it’s (Int)(Int)Int, or, again more readably, (Int) => (Int) => Int. That is, the new plus is a function which takes a single Int, and it returns another function which itself takes a single Int and returns an Int. Calling this new plus function as follows:

[cc lang=’scala’]
plus(3, 4)
[/cc]

results in the error “error: too many arguments for method plus: (x: Int)(y: Int)Int”. Rather, the proper way to call this function is

[cc lang=’scala’]
plus(3)(4)
[/cc]

This yields the expected result of “7.” However, the error we received before is rather telling. As we can see by the signature, the curried version of plus does not take two arguments (thus the error). What the second (successful) call really means is call the function plus with the argument 3 (i.e. plus(3) ), then apply the result of this function call ( remember the call plus(3) itself returns a function) to the argument 4. This can be extended to any number of arguments where:

[cc lang=’scala’]
def func(x_{0})(x_{1}) . . . (x_{k}) = { evaluate function }
[/cc]

Is a function which takes a single argument, and returns a function (let’s call it func_1, even though it doesn’t really have a name) which itself takes arguments. However, func_1, in turn, takes a single argument and returns a function func_2 which takes arguments. In a similar fashion, each func_ takes a single argument and returns a function taking arguments, until we get to func_; a function which takes a single argument and returns the result of whatever expression is evaluated in “evaluate function”. Currying takes a function of arguments, and returns a chain of function applications, where each function takes a single argument. Perhaps now it’s becoming clear the relation between bound and free variables, closures and currying. Each function application in the chain of curried functions is essentially binding one of the free variables used in the function body’s expression. Ok, time for a test; what if, given the curried definition of plus above, I wrote something like

[cc lang=’scala’]
val p9 = plus(9)_
p9(1)
[/cc]

What’s the result of the “p9(1)” expression? If you guessed 10, then you’re correct! Essentially, p9 is the result of a partial function application to the curried function. In the partially applied function, exists in a scope where the previously free variable “x”, has now been bound to 9. In fact, we could have achieved the same thing by writing the much more cumbersome (and much less intuitive) code:

[cc lang=’scala’]
val p9 = (y:Int) => 9 + y
[/cc]

Here, we’re assigning p9 directly as a function which takes a single integer, “y” and returns the sum of 9 and y. This is equivalent to binding the value 9 to the variable “x” in our curried function.

After all of this discussion, we come full circle, back to the notion of a partial, or “partially applied function.” All we mean by a partial is function, where some subset of the free variables are captured in a closure. When we partially apply a set of arguments to a function, we get back some function where some set of the free variables of the function are bound to those arguments, and the rest of the free variables will (presumably) be passed in at another point. Again, scala has some fairly nice syntax for this, let’s take our old friend, the original plus function, and look at partially applying each of its two arguments.

[cc lang=’scala’]
def plus(x : Int, y : Int) = { x + y }
val p9first = plus(9, _ : Int)
val res0 = p9first(1)

val p9second = plus(_ : Int, 9)
val res1 = p9second(1)
[/cc]

At the end of this little exercise, both res0 and res1 have the same value, 10. However, in the first case, p9first the free variable “x” is bound to the value 9 and the function call p9first(1) is interpreted as binding y to 1 and evaluating 9 + 1; thus returning 10. In the second case, p9second the free variable “y” is bound to the value 9, and the function call p9second(1) is interpreted as binding x to 1 and evaluating 9 + 1; thus returning 10. Now, the commutativity of plus ensures that these results were the same, but if we had instead considered the function minus (defined in the natural way), then the analogs m9first and m9second would have returned different results; namely 8 and -8 respectively.

Alright, enough with these examples. We’ve begun to explore the wonderful world of closures, currying and partially applied functions, and I hope that I’ve given you at least some idea about how these concepts are related (at least conceptually if not in terms of implementation). Though the concepts are distinct, they share a certain flavor and overlap in many meaningful ways. Together, closures, currying and partials provide a very powerful set of functional programming tools that you should remember next time you are faced with a programming problem where they apply . . . that is, assuming that you are programming in a language as awesome as scala which offers access to such functional constructs.