An Overview of elements of functional programming in C++ (ending)

Posted by on in Blogs

Part III

Where it is told about the technics to manipulate the call signatures of functional objects

 

Currying

There is not only a functional language named after Haskell Curry, but also a functional operation—converting a function from many arguments to a set of functions, each of which has one argument.

 

“This Is the House That Jack Built”

A World known British nursery rhyme  can give you an intuitive notion of currying concept. This cumulative tale  shows how the house is indirectly linked to other things and people, and through this method tells the story. A very entertaining!   

The longest couplet looks like this:

This is the horse and the hound and the horn

That belonged to the farmer sowing his corn

That kept the rooster that crowed in the morn

That woke the judge all shaven and shorn

That married the man all tattered and torn

That kissed the maiden all forlorn

That milked the cow with the crumpled horn

That tossed the dog that worried the cat

That killed the rat that ate the malt

That lay in the house that Jack built.

 

As we see, the characteristics of a horse, a dog and a horn are not limited to indicating their belonging to the farmer. It would be exhaustive if we knew exactly who is  a farmer which is talking about. And further there is this clarification. That is, the owner of the listed items is a farmer, but in this word "farmer" already contains the whole chain of refinements, which leads to Jack, whom, as implied, we know well.

Let's look to the  shown couplet again and rewrite it in a composition of semantic function-matryoshka view :

belonged to [...] (horse and the hound and the horn)

where [...] is " the farmer that [...] "

where [...] is " sowing his corn that [...]"

where [...] is " kept the rooster that [...]"

where [...] is " crowed in the morn that [...]"

where [...] is " woke the judge all shaven and shorn that [...]"

where [...] is " married the man all tattered and torn that [...]"

where [...] is " kissed the maiden all forlorn that [...]"

where [...] is " milked the cow  [...]"

where [...] is " with the crumpled horn that [...]"

where [...] is " tossed the dog that [...]"

where [...] is " worried the cat that [...]"

where [...] is " killed the rat that [...]"

where [...] is " ate the malt that [...]"

where [...] is " lay in the house that [...]"

where [...] is "Jack built"

 

Do not be confused by the argument horse and the hound and the horn: it's a set of three elements, but it's still the only argument. To it the semantic function "belonged to ..." is applied. We can not say for sure right now what exactly our horse and the hound and the horn belong to, at this point it is important for us just that they belong to somebody.

Note that they can belong to a wide variety of people. In the next step, the situation becomes somewhat clear: they belong to the farmer. Accordingly, we can rewrite our semantic function as

belonged to the farmer that [...] (horse and the hound and the horn)

The circle of potential hosts has narrowed considerably, but this is still not enough to determine what exactly subjects we are said now. In the next step we will understand that this farmer is sowing his corn, then - that this corn is kept the rooster:

belonged to the farmer that  sowing his corn that kept the rooster that[...] (horse and the hound and the horn)

Agree that it's just to belong to someone and belong to a farmer engaged in planting corn, and even having a rooster nearby - these are two different fates for our horse, hound and horn. But we can still confuse which of the farmers who are engaged in similar work is talking, and then there are some juicy details about the fate of the rooster... As we can see, this is a rather lengthy chain that finally leads us to the personality of Jack, who is well known to everyone (and he really is worldwide known thanking this fairy tale).

 

The purpose of such a chain of definitions is the development of thinking in children who begin to speak, but it works precisely because the brain learns to build associations.

 

By the way, most researchers agree that cumulative tales are examples of the oldest folklore and that such chainlike structures corresponded to an archaic type of thinking. May be, from the point of view of the primitive man, it is precisely our thinking that is "weird".

Our thoughts consist of chains of associations,  because our cerebral cortex operate with associations. But as soon as we begin to speak the strict language of mathematics,  we operate on maps on sets, so we have to deal with the associative property and, more generally, with the composition of functions.

 

A composition of functions is a sequence of functions, the first of which applies to an argument, and each of the subsequent applies to the result of the previous (the first function in the composition is h):

f(g(...h(x)...)) =  f ∘g ∘...∘h (x)

 

If we do not take into account the technical tricks of pipelining,  multicore parallelization of calculations and, even more so, quantum computations, we can assume that at each moment the classical processor core executes  a single primitive instruction. It means that any complex function must be broken down into some stages of computation.

Thus in order for the machine to calculate the value, the reverse operation is natural - decomposition. Within the framework of a functional paradigm, such a decomposition is not just a technical stage of computation - it is so important that it has its own name.

The function of many variables is reduced to a set of sequential operations on each of these arguments, that is, it turns into a composition of functions of a single argument:

f(x1, x2, .., xn) ={ [f1(x1)∘f2](x2)...∘fn}(xn)

This means that some additional function f1 is calculated from the first element. The form of this function depends on its argument x1.  It is applied to the result of the function f2 from the second element x2 and so on.

The last argument xn de-facto uses a function parametrized by all previous n-1 arguments:

f(x1, x2, .., xn) =fx1, ..,  xn-1(xn)

This is not just a mathematical trick, but one of the cornerstones of functional programming: all functions are treated as functions of one argument (while other arguments are parameterized), but the function sways its arguments one-by-one at each step turning into a slightly different function. This carries on until the set of the arguments becomes completed and the function can be calculated. The whole process is called currying, and you can think of this as the Tetris game "The Snake." Your current cube is the next target of the snake, and when it’s devoured it becomes a part of the snake and accompanies it to search for new prey.

 

When we are dealing with STL, everything is not so creepy and much more commonplace. We have the idea to rewrite the signature of a function call to make it more adequate for the situation. This is absolutely not the same as currying, because imperative programming is naturally different. I can offer you some semblance of this.

std::bind

You can think  about using of a std::bind simply as a pro forma of your function: You determine in advance the most inert parameters, save this pro form and only at the time of the call determine the most significant. In addition, it allows you to flexibly control the sequence of call parameters.

 

std::bind allows for predetermining the values of some parameters as if we fixed them in the process of currying, and we will see now how it looks.

syntax description

template< class F, class... Args > bind;

or

template< class R, class F, class... Args > bind( F&& f, Args&&... args );


f

-

callable object (function object, pointer to function, reference to function, pointer to member function, or pointer to data member) that will be bound to some arguments

args

-

list of arguments to bind, with the unbound arguments replaced by the placeholders _1, _2, _3... of namespace std::placeholders

 

Example

Let's go back to our example of counting the number of numbers in a given range. In the previous example we tried to define the predicate as a functor, pass borders of the range into its constructor or as lambda expression, and passing values of range borders into capture. But the question remains are these solutions ideal?

Generally speaking, the abuse of lambda expressions is fraught with lower code readability. At the same time, let's permit the functor to remain a functor only! Here it is not critical, but for some algorithms maintaining the internal state of a functor in a consistent state can be a problem affecting overall performance. Perhaps there is a way to make the code even more natural?

Let's look at our functor’s operator(): why don’t we pass the boundaries of the range right here? I said above that I do not want to remember these boundaries at every call! Moreover, the transfer of several parameters does not correspond to the signature of our predicate.

 

std::bind allows us to solve this dilemma. We simply assign values of bounds of the range and fix these values. Something like lambda’s capture, but only std::bind wrapper is used.  

predicate =  bind(prdobj, lowerBound, upperBound, _1);

Function variable predicate  here is assigned with the bind of our functional object prdobj and with the bounds of diapason. The remaining place occupied by the so-called placeholder _1. This syntax means mapping the first argument in the signature of the factual call with the third place in the signature of the function object prdobj that is explicitly passed, by the way, as an argument at zero position

In both cases we can use a binded predicate call not paying attention to the nature of this predicate:

count_if(v.begin(), v.end(), predicate);

 

In fact, std::bind provides almost unlimited possibilities for converting one function signature to another.

I do not comment on the use of some of the tools discussed above (such as Generator class). Don’t bother trying to guess the logic of the preferences of this or that variant - I just try to freely manipulate them. After execution, we see that the ways of implementation demonstrated here give completely identical results.

#pragma hdrstop

#pragma argsused

#ifdef _WIN32
#include <tchar.h>
#else
  typedef char _TCHAR;
  #define _tmain main
#endif

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

class Generator {
	private: int n = 0;
	public: int operator()(){return n++;}
};


class Predicator {
	public:
	bool operator()(int a, int b, int n)
	{
		return (a <= n) && (n < b);
	}
};


 int _tmain(int argc, _TCHAR* argv[])
 {

	using namespace std::placeholders;
	int m;
	cout << "Enter array size: ";
	cin >> m;
	vector<int> v(m);

	Generator gen;
	generate(v.begin(), v.end(), gen);



	cout << "Content of array: ";
	for_each(v.begin(), v.end(), [](int value){ cout << value << " "; });
    cout << endl;

	int lowerBound = 0, upperBound = 0;
	cout << "Enter the bounds of the range: ";
	cin >> lowerBound >> upperBound;

	function<bool(int)> predicate;
	int result;

	cout << "The number of elements in the interval [" << lowerBound << ", " << upperBound << ")" << endl;

	//using of the predicat based on the functional object bind
	Predicator prdobj;
	predicate =  bind(prdobj, lowerBound, upperBound, _1); //

	result = count_if(v.begin(), v.end(), predicate);
	cout << "Calculated with std::function predicate based on the functional object bind: " << result << endl;

	//using of the predicate based on lambda-function bind
	auto fn =  [](int a, int b, int n)->bool {	return (a <= n) && (n < b); };
	predicate = bind(fn, lowerBound, upperBound, _1);
	result = count_if(v.begin(), v.end(), predicate);
	cout << "Calculated with std::function predicate based on the lambda-function bind: " << result << endl;

	std::cin.ignore(2);
	return EXIT_SUCCESS;
 }

 

Conclusion

I hope that this material has allowed you to come in contact with the elegance provided to us by elements of functional programming in C++ 11.

The need for the ability to operate using class methods and global functions as objects has always existed in imperative languages.

However, now we have the ability to define a function right at the point of its call (the mechanism of lambda functions).

We can control the scope and ways of accessing external variables for this function (capturing). In addition, there is a way to implement access to the internal variables of the lambda function, and extend their life cycle even after returning from the function (closure).

If we need to use some internal state between function calls in a more transparent way, we have a technique for using functors in our disposal. To do this, it is enough to redefine the operator() of a class.

In order to bypass the problem of matching the signatures of calling your functions to some template signatures, use std::bind, which allows perform the mapping of the arguments of the functional object call. In functional programming, this technique corresponds to currying, but there it is one of the keystones of the entire paradigm.

Use the std::function variable to store any your functional objects - methods, lambdas and functors in the unified form.

But if you want to use the type-compatibility based on the method signature not the class type then instead your choise is a __closure type.

Functional elements are well applicated for STL, however, as we saw, the delegation mechanism also needs similar approaches, and you can come up with additional applications in your tasks.

Finally, you need to understand that C++ is an imperative language by its nature, and the application of functional elements has technical and not ideological significance here.

What's next?

If you want to go deeper into the study of functional programming, then it's worth trying to write real functional programs, for example, on Haskell.  Nevertheless, in order if you want to orient only and do not spend time on the professional study of the whole language, I recommend the following facile course which could be a good starting point:

http://learnyouahaskell.com/chapters

But staying within the boundaries of imperative C++ awaits a lot of interesting things. It would be interesting to look "under the hood" of functional elements and analyze their performance in combination with STL.

 

Moreover, Embarcadero announces the quickly appearance of C++17 support in C++ Builder, so soon we will use ranges more transparent way instead iterators. Life is getting more fun!

 





Comments

Check out more tips and tricks in this development video: