Thursday, June 20, 2013

Partial Applications using Currying & Function Compositions

C# introduced Func and Action delegates in .net framework 3.5. They are part of C# 2 language specification. It also introduced expression trees and lambda expression in the same framework version. It's amazing how technologies evolve and new technologies are built on top of the existing ones. They were built on top of Generics introduce in .net framework 2.0. In this post we are going to discuss how we can use these constructs to introduce currying, partial applications and functional composition.

Previously we have discussed how we can use dynamic call site to avoid compile time check for arithmetic operations in a generic type. You can find the discussion here [http://www.shujaat.net/2012/05/c-generics-arithmetic-operators.html]. We will be assuming that calculator has been provided to us as a third party library and we will be deriving more meaningful operations (functions) from the existing methods using functional approaches. Referential transparency is the essence of functional programming providing side-effect free operations. We discussed about purely functional approach here [http://www.shujaat.net/2012/07/design-guidelines-purely-functional.html]

Currying
Currying is a transformation technique in functional programming space. It is used to convert a function with multiple parameters to a set of functions with single parameter each. It can be used to create refined algorithms where partial list of arguments can be provided to create more sophisticated operations. The nomenclature is in the honor of Haskell Curry, the creator of Haskell functional programming language. It must be remembered that the end-result of a curried version of a function should exactly be the same as its non-curried counterpart.

C# 4.0 provided optional parameters. These are the parameters with default values. If the caller doesn't want to pass arguments to those parameters then the default value is used instead. They are always at the end of the parameter list. This is opposite to the partial application case as the fixed arguments here. They would be the first parameters to a function. You might want to use these two concepts together as well. We can introduce the support for currying a function using extension methods. We can introduce these extension methods for the required overloads of Func and Action delegates. The following is an example of currying where we are converting a method with two parameters to a set of methods with single parameters.

The above code uses the Closure and Captured variables. Being a captured variable, operand1 is available inside the inner lambda expression. The whole feature is available due to closure where the life time of the context of lambda expression declaration is upgraded to the life time of expression itself allowing the use of captured variables. Actually we have discussed about closures in the context of async code execution using Dispatcher in WPF applications.

Partial application is about fixing the arguments to a function. An application has historically been referred as a set of functions. So the remaining method with some fixed arguments is referred as partial application. So we first obtain the curried version of a function and then provide fixed arguments. Wikipedia has a quick reference about the concept.

Now let's see how we can use currying and partial applications to create more meaningful operations. In the example below we are using the methods provided by the above Calculator class to derive calculatePlusPlus, calculateAdditiveInverse and calculateMultiplicativeInverse functions. Here we are fixing first arguments to the curried versions of the delegates based appropriate to the operation e.g. for calculatePlusPlus we can fix the first argument to 1.

The output of the above code would be as follows:



We are certainly not restricted to use only Func delegates. We can also use Action delegates if needed. Lets' create an extension method which curries an Action delegate with two parameters to a set of Action delegates. Don't get confused with the combination of Func and Action delegates being used here. You can just be concerned about the last Action, which refers to the actual operation. The rest of the design is just to curry it.

Here we are introducing a lambda statement to print a message specified number of times. We are assigning the statement to an Action delegate. After currying the delegate, we are creating a partial application printThreeTimes by fixing the first argument to 3. This would cause the message to be printed three times.

I can understand you might be thinking if this is possible to UnCurry a curried function or not. Actually we can do that too. Below is the extension method accepting a curried Func delegate and returning an Un-Curried version of the delegate.

Here we are UnCurrying a curried version of divide operation from Calculator. We are then calling it using the specified arguments as follows:

Functional Composition to construct data / processing chains
Functional composition is the method where multiple functions are used in a serial fashion in such a way that the output of one method serves as the input of other method.This can be used to build processing chains. I am deliberately not calling it a pipeline because a pipeline should have producer / consumer based intermediate queues. We have discussed how we can implement processing pipelines during the discussion of TPL Dataflow. You can find the discussion here: [http://www.shujaat.net/2013/05/processing-pipelines-with-tpl-dataflow.html].

The processing chain created through functional composition can also be specified using extension methods. The following defines an extension method on a Func delegate with two parameters. After getting the result from the first, it just passes the results to the second Func delegate. Obviously the next element in the chain should have only one parameter. After the second element completes, it just returns the result to the caller.

In the following code we are providing support of calculating percentage using the available Divide and Multiply methods from Calculator. As we know percentage of a part in a total is computed as [ percentage = (part / total) * 100 ]. So we need to obtain a curried version of Multiply & fix the first argument to 100 and use it after dividing part by the total.

It is also possible that the processing chain is not returning any data back to the caller. In this case, all the elements in the chain do pass the required data to the next element in the chain. The last element just uses the data for its purpose and nothing returns back to the caller. We can implement this using chain of Func delegates with an Action delegate at the end.

Let's see how we can use it to print the percentage of a part. Here we are using the function composition created for calculating the percentage. We are adding an element to construct a message. At the end we are using a processing element to print the message to the console. For the last element, we are using the curried version of printMessage with first argument fixed as 1.

The output of the above code would be as follows:


No comments: