Introduction
C++ and Functional Programming???? It sounds quite strange and fascinating because most of us know C++ as Object Oriented Programming language. Well, yes! OOP was the actual purpose behind the development of C++ and so was known as C with classes. But C++ has become much more than that over the last few years. This article is all about showing you the much more part; the alternative way of using C++; How to write functional code in C++. In this way, you’ll be able to write concise, safer, readable, reasonable and I bet, more beautiful code than the usual practice in C++.
Please note that this article is not for absolute beginners rather I assume your understanding with C++ and OOP. We’ll start by having a brief introduction to what functional programming is all about and by the end of this article, you’ll be able to see how C++ supports functional style of writing code.
Functional Programming
On a broad spectrum, functional programming is just a style of programming which focuses more on functions (some might like to call it programming with functions, i.e., the main function would be defined in terms of other functions which are defined in terms of some other functions at lower level) rather than objects and procedures (as done in Object Oriented Programming Paradigm).
Strictly speaking, Functional programming is a programming paradigm in which we code the computer program as the evaluation of expressions same as mathematical functions (No changing-state and mutable data).
This could be a little overwhelming, but stick with me for the moment as I explain what this means.
Declarative programming means to describe the problem that is needed to be solved but not telling programming language how to solve it. Functional Programming adds to declarative style in the sense that you tell the computer what to solve but also without change of state or variable. This means value outputs in Functional Programming depend only on the arguments passed to the function.
Why Use it?
FP minimizes the moving parts of the code (as opposed to the Object Oriented paradigm which encapsulates the moving parts) and thus makes the code easier to understand, compressed and predictable. Also, the tools FP provides us are simple but expressive, not to mention the higher level of abstraction and so we don’t need to worry about the nitty gritty details. But these are just some general and superficial pros. FP is one of the oldest concepts in the Computer world, so why this hype all of a sudden? Well, FP exposes its true potential when it comes to parallel processing. The program will execute safely on multiple CPU(s) and you don’t need to worry about excessive locking because it doesn’t use or modify any global resources (Pure functions, we’ll discuss the details later in the article). And as we’re specifically talking about FP in C++, here’s the list of what it offers.
- More powerful, generic algorithms
- Reactions to the events, i.e., GUIs, IO/networking, tasking, parallelism
- Composition and transformation of new calling conventions from old ones
- Manipulation of execution flow
And this is just the start. Different concepts of functional programming offer different benefits. The following image shows the different concepts of FP.
Now instead of spilling the theory all over, let’s take a moment to discuss and implement these characteristics in C++ and don’t worry, you’ll get to see the beauty of FP eventually.
Environment Setup
You just need a text editor and C++ compiler supporting C++11 and C++14. The code is tested on Windows 10, Microsoft Visual Studio 2017 and also on Ubuntu with gcc compiler. It should work fine with any other platform and compiler supporting latest C++ functionality.
First Class Functions
First class functions behave like data. What this means is that you can pass the functions as argument to other functions or they can be returned from other functions. Also, the functions can be stored in data structures or passed to variables as well. An example of this is the lambda function which was introduced in C++11.
Lambdas
Lambdas are anonymous (without name) in-place functions. It wouldn’t be so wrong to say that lambdas are a companion of C++ when it comes to FP or more like Functional Programming is being made possible in C++ more or less because of lambdas.
Let’s create a simple lambda as follows:
[] () {
std::cout << "Hello from C++ Lambda!" << std::endl;}
();
You see four pairs of brackets. Let’s see what each of them means:
[] is lambda introducer or lambda closure() is for argument list (you can skip these parenthesis if lambda is not taking any argument){} contains the body of lambda() is used to call the lambda
These expressions have an implementation-defined type (which is Callable!), but they work with type deduction. (C++ functions are not first-class, but we have various ways of representing functions as first-class entities in C++. The Callable concept implies that we can invoke a type T by giving a suitable argument list to produce a return value, e.g., pointers to functions, pointers to member functions and all types with call operators.)
auto sum = [] (double A, double B) { return A + B; };
auto add = sum;
std::cout << add(3.25, 5.65) <<std::endl;
Here, auto is used for deducing type. By using auto, the compiler tries to infer the type by looking at the values. Also, check that this time, we provided arguments (double A, double B) to the lambda. Now if all return statements return the same type, then it will be determined implicitly. Otherwise, we need to explicitly specify the return type using → as:
[](double A, double B) → double { return A + B; };
But what if we want to use a variable from outer scope? That can be done using lambda introducer. See the following example:
double pi = 3.1416;
auto func = [pi] () {
std::cout << "The value of pi is "<< pi << std::endl;
};
This process of making outer scope variable available inside lambda is called capturing. By default, capturing is done by value but you can also do it by reference or a mix of both. For instance:
[] | captures nothing |
[&] | all captures done by reference |
[=] | all captures done by value |
[&A, =B] | captures A by reference, B by value |
[=, &A] | captures A by reference, everything else by value |
[*this] | captures ‘this’ (C++17 still not widely supported) |
C++14 allows you to create more generic lambdas in which you don’t need to specify the type but compiler can deduce it itself. (Please note that we’re not talking about templated lambdas, rather just a lambda provided no strict type but can be invoked with different types.)
auto gene_lambda = [] (auto arg) { return arg + arg; };
std::cout << gene_lambda(5) << std::endl;
std::cout << gene_lambda(3.1416) << std::endl;
The above code will compile without any errors and the compiler will infer the return type itself which is int and double respectively.
Polymorphic Function Wrapper (std::function):
Function is not a single construct, but a whole concept in C++. It can refer to a simple function, a functor (overloaded () operator) or to a lambda expression. Which takes me back to the concept of callable (anything than can be called as if was a function) and sometimes create confusion in the sense that what do we exactly mean when we are calling something a function; a simple function, functor or lambda? To solve this problem, C++ incorporated std::function in C++11 standard which is a convenient wrapper from STL template class. Have a look at the syntax.
std::function<signature(args)> f
Where signature is the function return type. It could be:
int(int, int)
or:
double(double, double)
and f can be any callable.
std::function<> has value semantics so any matching signature can be stored in it. Which means that std::function<> gives us a uniform syntax for invoking Callables and can be used in all cases, i.e., a simple function, functor or a lambda. Let’s try to implement our sum lambda expression this way.
std::function<double(double, double)> sum
= [](double A, double B) { return A + B; };
std::cout << sum(4.6, 5.9) << std::endl;
Here’s another way (using functor) to achieve the same functionality:
int sum (int x, int y) {
return x+ y;
}
class Add {
public:
int operator() (int x, int y) const {
return x+y;
}
};
int main() {
std::function<int(int, int)> func;
func = sum;
std::cout << func(5, 7) << std::endl;
return 0;
}
As we talked about earlier, functor uses the overloaded () operator. Our Add class defines the overloaded operator. We also defined sum function which; along with overloaded () operator; would be used to add the two integers. Well, this way is pretty much the combination of functional and object oriented way of doing things and it's fine if you didn’t like it. The only purpose to show it here is to show you how usage of lambdas makes our code compact and beautiful and also std::function<> makes our lives easy.
Higher Order Functions
Higher-order functions take other functions as parameter or return them. All the programming languages that supports FP offers map, filter and fold functions. Some examples of such functions in C++ are for_each, transform, remove_if. Let’s implement some of them and see how things work.
Let’s first try to see how transform works (map function).
std::vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::transform(v.begin(), v.end(), v.begin(),
[] (int n) {return n + (n*2);}
);
Here, we want to add double of values to our vector. We are starting our operation form the beginning of our vector to the end and we want our values to be transformed from the beginning. Last but not the least; see how beautifully lambda is working in our example.
Let’s try to print the values in our vector using for_each.
std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::for_each(v.begin(), v.end(),
[](const int&x) {std::cout << x << std::endl; });
Remember! You are not required to specify x to be int but you can also use auto keyword and the code will work fine. We can also filter out (filter function) the result based on the provided condition using remove_if. See the following example:
std::vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::remove_if (v.begin(), v.end (),
[] (int n) {return n%2 !=0; }
);
std::remove_if will remove the elements satisfying the condition. We can also copy the specified values as follows:
std::vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> v1;
std::copy_if (v.begin(), v.end (),
std::back_inserter(v1),
[] (int n) {return n%2 !=0; }
);
Now is the turn of fold. C++ accumulate is equivalent of FP fold.
std::vector<int> v = { 2, 9, -4, 2 };
auto sum = std::accumulate(begin(v), end(v), 0);
Forward Call Wrapper (std::bind):
Higher-order functions provide us with the ability to transform calling convention. Take a look at the following:
int func(int x, float y, std::string const& z);
We might want to transform the function argument list, i.e., binding certain parameters to a particular value. To make it easier for developers, C++ added std::bind to the standard library. std::bind is also a template function and it returns a std::function object that binds arguments to a function.
std::bind(f, args)
This is the syntax of std::bind in its simplest. The return type is unspecified but is callable and so this object is called binder.
Each argument to this function can be at most of four types:
- The first argument would be a reference or pointer to an instance of the class if
f is a member function.
std::bind(&x::f, this)
- Placeholders: denote the arguments passed to the binder.
_1, _2, _3, …
- Reference wrappers: bind the parameter by reference or const reference.
std::ref, std::cref
- Other arguments are passed using value semantics.
Following example explains the usage of std::bind():
int func(int x, float y, std::string const& z);
Binding the semantic value of argument:
auto f1 = std::bind(&func, 5, _1, _2);
f1(5.4, "some string");
The above expression is equivalent to func(5, 5.4, “string”) call to the function.
Binding the reference wrapper:
std::string input = "something"
auto f2 = std::bind(&func, _1, _2, std::cref(input));
f2(2, 2.3);
The above call evaluates to the func(2, 2.3, input).
Another interesting thing that can be done using std::bind()is reordering the parameter using placeholders and we’ll still be able to call the function successfully. Observe the following:
auto f3 = std::bind(&func, _3, _1, _2);
f3("something", 256, 3.1416);
And it will evaluate as f(256, 3.1416, “something”)
Pure Functions
Pure functions always produce the same result when given the same parameter meaning the return value only depends on the input. Also, they do not have any side-effect and immutability applies that there won’t be any change in the state. Pure functions do not communicate with the outside world. For example, mathematical functions like pow, abs, sqrt, etc. are examples of pure functions. Consider the following piece of code.
std::cout << "Absolute value of +0.025 is " << abs(+0.025) << std::endl;
std::cout << "Absolute value of -1.62 is " << abs(-1.62) << std::endl;
std::cout << "Square root of 25 is " << sqrt(25) << std::endl;
std::cout << "square of 10 is " << pow(10, 2) << std::endl;
These are just some pre-defined mathematical functions from standard library. C++ allows you to define your functions as well. Consider the following:
__attribute__ _((pure)) int square(int l)
{
return l*l;
}
See that output only depends on the values passed as arguments and does not depend on any global state so the function is pure.
Pure functions are of special importance for the reason that they are side effect free which makes unit testing easier (we won’t need any external setup for the purpose of testing). Code is much easier to understand and debug due to less or at times no dependencies. Also pure functions make parallel execution of the program possible without requiring any extra code (as to deal with locks, etc.).
Immutability
Immutability is a powerful yet a simple concept in FP with almost the same story as that of purity. Basically, immutability refers to the idea that the object state does not change one the object has been created. The same is true for a class as well. Immutable objects simplify the concurrent programming to a great extent. It solves the problem with synchronization as the state of the objects accessed by threads won’t change so there’s no more need for synchronization.
Now we come to the question of how C++ makes a field or a variable immutable. This is possible if:
- The
const keyword is used to ensure that the object or field won’t be assigned or changed. - The class of the object referenced is immutable (no
public fields, no method that can change internal data).
Well, I’m not going to dig deep into const because we have been using it everywhere. Take another look at the expression explained earlier in the article:
int func(int x, float y, std::string const& z);
Here, we made the string literal immutable by using const. Yet, there’s another keyword introduced in C++11 and improved in C++14 and that is constexpr. It means constant expression.
Let’s see how we can implement this concept.
constexpr int Fibonacci (int x)
{
return (x <= 1)? x : Fibonacci(x-1) + Fibonacci(x-2);
}
int main ()
{
const int series = Fibonacci(10);
std::cout << series << std::endl;
return 0;
}
Yet, there should be no confusion between const and constexpr. const is practically for objects to declare them immutable. Like const, constexpr can be applied to variables and the compiler will raise an error if any code attempts to modify the value. const can only be used with non-static member function but constexpr can also be applied to functions and class constructors as long as the argument and return type are literal. constexpr indicates that the value, or return value, is constant and will be computed at compile time which drastically improves the performance. A constexpr integral value can be used wherever a const integer is required, such as in template arguments and array declarations.
Recursion
As we talked earlier, FP calls for no mutable data so instead of regular loops there, most of the time they make use of recursion. Just as we did in the previous example (though it is indirect recursion):
constexpr int Fibonacci (int x)
{
return (x <= 1)? x : Fibonacci(x-1) + fibonacci(x-2);
}
The other and most common example of recursion (direct recursion; function calls itself) is factorial example.
int factorial(int x)
{
if (x == 0) return 1;
return x*factorial(x-1);
}
Well, recursion when used with lists and pattern matching, lets you create a powerful function but this holds only partially true for C++. The languages like C++, iteration is preferable for the reason that recursion comes at a cost of time and space. The very first step to call a function is to allocate the memory from stack for function’s arguments and local variables and this is exactly where we get to see the problem. Many programs, during start; allocate a huge single chunk of memory from the stack. They run out of memory at times (often, but not always) because of recursion (as it requires more space) so the program will crash due to stack overflow. I would encourage you to read this Wikipedia thread to know more about the issues.
However, there exists a solution to this problem as well called tail recursion. It is a special case of recursion where the calling function does no more computation after making a recursive call. Take a look here.
factorial_TR(int x, int y)
{
if (x == 0)
{return y;};
return Factorial_TR (x-1, x*y);
}
int factorial(int x)
{
return factorial_TR (x, 1);
}
The idea here is to accumulate the factorial value in provided extra argument and when reached zero, it will return the accumulated factorial value. This gets us closer to tail recursion (as final instruction is a recursive call) and is more efficient. Also now we know that we will return as soon as the recursive call is done so we don’t need the call stack to push the return address which saves us space and so avoids stack overflow.
Lazy Evaluation
Laziness is one of the common features among functional programming languages. It refers to the concept that expressions are evaluated if only and when necessary and not at the time of declaration which improves efficiency. Also it is a powerful tool for structuring the code as it lets you turn the code inside out and invert the flow of control. One of the most common and special case of laziness in C++ is that of short circuiting where second argument to || operator is not evaluated if first is true. Let's see how it works in C++.
#include <iostream>
void func1() {
std::cout << "This is an implemented function" << std::endl;
}
void func2();
int main(){
func1();
return 0;
}
Note that we just declared not defined the func2 and also not calling it which is completely fine. Compiler will accept the above program without any errors because as I'm not calling the func2 and so I don't need a definition.
Now if you’re interested in implementing a generic lazy evaluation, here is something for you.
Ending Note
C++ is just not an Object Oriented Programming Language but there is much more power to it. This article was meant to let you see the beauty of Functional Programming from the lens of C++. As John Carmack said:
“No matter what language you work in, programming in a functional style provides benefits.
You should do it whenever it is convenient, and you should think hard about the decision when it isn’t convenient.”
