COMP 130
Elements of Algorithms and Computation
Spring 2012
![[Rice University]](http://www.staff.rice.edu/images/staff/branding/shield.jpg)
As much as the name sounds like a South Asian dish, "currying" is actually a reference to Haskell Curry, a famous pioneer in computer science as one of the founders of the functional programming paradigm. The programming language, "Haskell", bears his name. However, once you understand currying and its associated concepts, you may agree that it is one of hte hottest and spiciest topics in CS!
First, and experiment: Consider the following bit of rather odd, but perfectly legal Python code:
def curry(x):
def aFunc(y):
return x*y
return aFunc
f1 = curry(42)
f2 = curry(-10)
print f1(2)
print f2(2)
print f1(-1)
print f2(-1)
What do you think will print? Don't peek below--Try it first!
print f1(2) --> 84 print f2(2) --> -20 print f1(-1) --> -42 print f2(-1) --> 10
What's going on here?
A word of explanation of the syntax first: Remember that in Python, functions are considered "first class" entities, that is, they can be passed around like any other variables or values. We can define local variables for a function to use internally or for a function to use as a return value, so why not a function? That's all that aFunc() is in the above code, a locally defined function that the curry() function uses as a return value, which we assigned to the variable f1 in one case and to f2 in the other. f1 and f2 are functions of one input parameter, since that is what curry() returns, so it's perfectly legal to call them with an input parameter value.
But here's the kicker: aFunc() uses not only its own input parameter, y, but also the input parameter, x, of its enclosing function, curry()! But input parameters are just local variables, which means that after any call to curry() is finished, won't the value of its input parameter be discarded, as is normally done with local variables? But the experimental evidence contadicts that idea; the functions f1 and f2 clearly seem to "remember" that the input parameter to curry() was 42 and -1 respectively when they were made.
The key notion here is the concept of a "closure" which in simple terms is the environment, i.e. all the accessible entities, in which an entity was constructed. The key point here is that an entity can always access everything in its closure for its entire lifetime.
In this case, the key point is that since the curry() function creates the aFunc() function internally, the closure for aFunc() includes the curry() function's input parameter. Thus when curry() creates aFunc(), it permanently binds its input parameter, x, to Func(). That is, f1 is bound to the value x=42, while f2 is bound to the value x=-1.
So why isn't the input parameter discarded as normal? The Python compiler recognizes that the local aFunc() function is being created which needs permanent access to everything in its closure and thus, in response, moves the input parameter, x, from the local variable storage location, the "stack", to the permanent/global variable storage location, the "heap". The compiler doesn't have to worry about global variables because they are already permanently stored in the heap.
A function's behavior depends on its closure, e.g. the values of entities in its closure, and thus by creating using the same function code but with different closures, we can create functions that behave differently.
Technically, if we look at the curry() function and its returned function together, we see a single function of 2 input parameters:
print curry(3)(2) # --> 6 print curry(-4)(2) # --> -8 print curry(3)(-5) # --> -15
The output of curry() is a function of one parameter, however. Thus, we can think of this process as one that converts a function of two parameters into a function of one parameter by "currying" in one of the parameters, x, into the resultant function. Generalizing, the currying process reduces a function of n parameters to a function of m paramters, where m<n.
Currying is a example of a larger concept called the Factory Method Design Pattern, which an abstraction of the construction process for entities (see also the Abstract Factory Design Pattern)). Factories are used in all programming paradigms, especially in object-oriented programming.
The notion of closure and currying as one of its rammifications, is part of the core of theoretical computer science and show up in various forms in many, many different aspects of the study and practice of computer science. For instance, the indentations in Python are what the Python compiler uses determine the scope of the closures it creates. In many libraries, you must pass an "environment" variable to functions that perform various services because what one is effectively doing is manually passing a closure reference to the function. "Skins" on media player applications are possible because factories are used to create tailored user interfaces.
Currying and closures are part of the larger theoretical computer science topic called "lambda calculus" which, simplistically, says that all of programs can be described in terms of functions ("lambdas" -- refers to functions with no specific names) and their closures.
CS majors will see much more about lambda calculus, currying, closures and factories in Comp310 and Comp411.