Functional in C++98

Contents[Show]

C++ is not a functional programming language but you can program in a functional style. What are the functional features in C++? I will answer this question for C++98.

 

To be precise, I want to answer three questions in this and the following posts.

  • Which functional features does C++ support?
  • Which functional features do we get with C++17?
  • What functional features can we hope for with C++20?

The overview

To get an overview of all functional features in classical, modern, and future C++ a timeline helps a lot.

timeline.FunktionalEng

The story of functional programming began with the first C++standard C++98. So, C++98 is the topic of this post.

C++98

timeline.Funktional98Eng

Template metaprogramming

Template Metaprogramming is the programming with templates at compiletime. Template instantiation generated the temporary source code that the compiler uses to generate the executable. The graphic shows this process for the class template Factorial.

 TemplateInstanziierungEng

The Factorial class template is the Hello World of template metaprogramming and it must not be missing in a post which mentions template metaprogramming.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// factorial.cpp

#include <iostream>

template <int N>
struct Factorial{
  static int const value= N * Factorial<N-1>::value;
};

template <>
  struct Factorial<1>{
  static int const value = 1;
};

int main(){
    
  std::cout << std::endl;

  std::cout << "Factorial<4>::value: " << Factorial<4>::value << std::endl;
  std::cout << "Factorial<5>::value: " << Factorial<5>::value << std::endl;
  
  std::cout << std::endl;

}

 

The program gives the expected result:

factorial 

Right, it's not so thrilling that the program calculates the correct result. But it is thrilling, what is happening under the hood.

Template metaprogramming is a pure functional programming language, which is turing complete.  That means, template metaprogramming is in a strict sense a functional programming language (pure functional) and you can calculate all what is calculable (turing complete).

What is key for a pure functional programming language will be topic of a future post. Only that much. Because of the template instantiation Factorial<5>::value in line 20, the class template (line 5 - 8) will be invoked and therefore the class template Factorial<4>::value in line 7. This recursion ends with Factorial<0>::value. In this case the fully specialized class template in line 10 - 13 kicks in.

To show it in a graphic, the template instantiation of Factorial<5>::value starts at compiletime a recursive process in such a way that the result of the calculation in already available at compiletime.  From the perspective of the executable it will make no difference if I use Factorial<5>::value or 120 in std::cout.

factorialInstanziation

What are the functional characteristics of template metaprogramming, which you can observe in the class template Factorial.

Factorial has no state and no mutation, and uses recursion. That should be enough for template metaprogramming. 

STL algorithm

What have the algorithm of the standard template library (STL) with functional programming in common? A lot. At first, one of its fathers Alexander Stephanov was a fan of functional programming; at second, many of the algorithms of the STL are so called higher order functions. Higher order functions are one of the key characteristics for functional programming.

Higher order functions are functions that can get functions as argument or return functions.

In particular the property that the STL algorithm can get functions as arguments is the main reason for the power of the STL. Examples? For simplicity reason I use in the following lines the container and not ranges.

  • std::transform modifies the elements of its container with the help of a function, which needs exactly one argument.
  • std::remove_if remove all elements from the container fulfilling the property. The condition is defined by a predicate. A predicate is a function, which returns a boolean.
  • std::accumulate applies on all elements of the container a binary operation. The algorithm successively reduces the container to a final value.

Let's have a look at the three function in action.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// algorithm.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main(){

  std::cout << std::endl;

  std::vector<int> myVec{1,2,3,4,5,6,7,8,9};

  std::cout << "original:         ";
  for (auto a: myVec) { std::cout << a << " ";}

  std::cout << "\n\n";
  
  std::transform(myVec.begin(),myVec.end(),myVec.begin(), [](int i){ return i*i; });

  std::cout << "std::transform:   ";
  for (auto a: myVec) { std::cout << a << " ";}
  
  std::cout << "\n\n";
  
  myVec={1,2,3,4,5,6,7,8,9};
  
  auto logicalEnd= std::remove_if(myVec.begin(),myVec.end(), [](int i){ return !((i < 3) or (i > 8)); });
  myVec.erase(logicalEnd,myVec.end());
  
  std::cout << "std::remove_if:   ";
  for (auto a: myVec) { std::cout << a << " ";}
  
  std::cout << "\n\n";
  
  myVec={1,2,3,4,5,6,7,8,9};
  
  std::cout << "std::accumulate:  ";
  auto fak= std::accumulate(myVec.begin(),myVec.end(),1,[](int fir, int sec){ return fir * sec; });
  std::cout << "fak(10): " << fak << std::endl;
  
  std::cout << std::endl;

}

 

I fully intentionally used lambda-functions in the example. Although, the algorithm can accept all, what behaves like a function. But lambda-functions should be your first choice. C++ supports lambda-functions since C++11. That will also hold for the three additional features from C++11 that I used in the example: automatic type deduction with auto (line 22, 32, and 39), unified initialization (line 12, 26, and 36), and the range-based for-loop (line 22 and 32).

The program should in combination with the output be self explanatory. I will only mention one speciality of the STL algorithm in line 28. The std::remove_if does not remove - like all generic algorithm of the STL - the elements from the container. std::remove_if returns the logical end of the new container. This logical end is used by the myVec.erase method, which shortens the container to its correct length.

The method erase is not a generic algorithm of the STL, but a method of std::vector. 

algorithm

What's next?

I will write in the next post about the Technical Report 1 from 2005. I'm in particular interested in the two functions std::bind and std::function, which introduce a totally new technique in C++: partial function application. Partial function application is quite similar to the functional technique currying, also called schönfinkeln. Schönfinkeln, that sound extremely promising.

 

 

 

 

 

 

 

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

 

Comments   

0 #1 Noam ylgev 2017-01-21 07:50
Great post!
Quote

Add comment


My Newest E-Book

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 557

All 255862

Currently are 250 guests and no members online