Immutable Data

Contents[Show]

A key to pure functional languages is that their data are immutable. Therefore, assignments such as x= x+1 or ++x are not possible in the pure functional language Haskell. The consequence is that Haskell supports no loops like for, while, or until. They are based on the modification of a loop variable. Haskell does not modify existing data; Haskell creates new data when needed and reuses the old ones.

Immutable data

CharakteristikeImmutableDataEng

Immutable data has a nice property. They are implicit thread-save because they miss a necessary condition for a data race. A data race is a state, in which at least two threads access a shared data at the same time, and at least one of the threads is a writer.

Quicksort in Haskell

The quicksort algorithm in Haskell shows very nice the immutability of data.

qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

 

The quicksort algorithm qsort consist of two function definitions. In the first line, the quicksort will be applied on the empty list. Of course, the result is an empty list. In the second line, there is the general case in which the list consists of at least one element: x:xs. x is the first element in the list and xs the reminder by convention. 

The strategy of the quicksort algorithm can be directly applied in Haskell.

  • Use the first element of the list x, the so-called pivot element and make a list with one element out of it: ... [x] ...
  • Add (++) all elements before the list [x] that are smaller than x: qsort [y | y <- xs, y < x]++ [x] ...
  • Add (++) all elements after the list [x] that are equal or bigger than x: ...[x] ++ (qsort [y | y <- xs, y >= x])
  • The recursion will end if quicksort will be applied to the empty list.

Admittedly, the imperative eye is not used to the conciseness of Haskell.

The key point of the algorithm is that each recursion creates a new list. How does an implementation in C or C++ look like?

Quicksort in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void quickSort(int arr[], int left, int right) { 
  int i = left, j = right; 
  int tmp; 
  int pivot = arr[abs((left + right) / 2)]; 
  while (i <= j) { 
    while (arr[i] < pivot) i++; 
    while (arr[j] > pivot) j--; 
    if (i <= j) { 
      tmp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = tmp; 
      i++; j--; 
    }
  }
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
}

 

No worries. I will not try to explain the algorithm.  A simple observation is enough for me. The elements are overwritten in line 9 - 11. The algorithm works in-place and needs, therefore, mutable data. There exist a nice term in the functional programming for this overwriting:  destructive assignment.

To be honest that was an implementation of the quicksort algorithm in C. With C++ we can do better if I use the std::partition.

template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first,last)/2);
    ForwardIt middle1 = std::partition(first, last, 
                         [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last, 
                         [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
 }

 

But once more. The key point is that I use also destructive assignment in std::partition. If you look very carefully, the strategy of the C++ version is not so different from the Haskell version.

What is the story about immutability in C++?

Immutable data in C++

The usage of immutable data in C++ is based on the discipline of the programmer. You have with constant data, template metaprogramming, and constant expressions three ways to express the immutability. The options one and two are quite easy to present but constant expressions deserve more attention.

Constant data

By using the instruction const int value= 1; value becomes an immutable data.

Template metaprogramming

Template metaprogramming takes place at compile time. At compile time there is no mutation. Therefore all values that are calculated at compile time are immutable. Of course, that holds true for the calculation of Factorial::5 at compile time.

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

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

std::cout << Factorial<5>::value << std::endl;
std::cout << 120 << std::endl;

 

If the short notice to template programming was too short for you, please read the post Functional in C++98.

But now back into the future of C++: constant expressions.

Constant expressions

C++11 supports constant expressions. With C++14 you can declare functions as constant expressions that behave almost as usual functions.

C++ supports constant expressions in three variations: variables, user-defined types, and functions. The special about constant expressions is that they can be evaluated at compile time.

  1. By using constexpr double pi= 3.14  pi becomes a constant expression. pi is, therefore, implicit  const and has to be initialized by a constant expression:  3.14.
  2. There a few restrictions for a user-defined type so that the instances of the user-defined type become constant expressions. For example, the constructor has to be empty and a constant expression. The instance can only use methods that are constant expressions. Of course, you can not invoke a virtual method at compile time. If a user-defined type fulfils all requirements, you can instantiate and use its objects at compile time. 
  3. To execute functions in C++14 at compile time, the have to follow a few rules. Firstly, their arguments have to be constant expressions. Secondly, they can not use static or thread-local data.

 

The following example shows what power lies in constant expressions. I use user-defined literals to calculate all distances at compile time.

 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// userdefinedLiteralsConstexpr.cpp

#include <iostream>

namespace Distance{

  class MyDistance{
    public:
      constexpr MyDistance(double i):m(i){}

      friend constexpr MyDistance operator+(const MyDistance& a, const MyDistance& b){
        return MyDistance(a.m + b.m);
      }
      friend constexpr MyDistance operator-(const MyDistance& a,const MyDistance& b){
        return MyDistance(a.m - b.m);
      }
	  
      friend constexpr MyDistance operator*(double m, const MyDistance& a){
        return MyDistance(m*a.m);
      }
	  
      friend constexpr MyDistance operator/(const MyDistance& a, int n){
        return MyDistance(a.m/n);
      }
	  
      friend std::ostream& operator<< (std::ostream &out, const MyDistance& myDist){
        out << myDist.m << " m";
        return out;
      }
    private:
double m; }; namespace Unit{ constexpr MyDistance operator "" _km(long double d){ return MyDistance(1000*d); } constexpr MyDistance operator "" _m(long double m){ return MyDistance(m); } constexpr MyDistance operator "" _dm(long double d){ return MyDistance(d/10); } constexpr MyDistance operator "" _cm(long double c){ return MyDistance(c/100); } } } constexpr Distance::MyDistance getAverageDistance(std::initializer_list<Distance::MyDistance> inList){ auto sum= Distance::MyDistance{0.0}; for (auto i: inList) sum = sum + i ; return sum/inList.size(); } using namespace Distance::Unit; int main(){ std:: cout << std::endl; constexpr auto work= 63.0_km; constexpr auto workPerDay= 2 * work; constexpr auto abbrevationToWork= 5400.0_m; constexpr auto workout= 2 * 1600.0_m; constexpr auto shopping= 2 * 1200.0_m; constexpr auto distPerWeek1= 4*workPerDay-3*abbrevationToWork+ workout+ shopping; constexpr auto distPerWeek2= 4*workPerDay-3*abbrevationToWork+ 2*workout; constexpr auto distPerWeek3= 4*workout + 2*shopping; constexpr auto distPerWeek4= 5*workout + shopping; constexpr auto averageDistance= getAverageDistance({distPerWeek1,distPerWeek2,distPerWeek3,distPerWeek4}); std::cout << "averageDistance: " << averageDistance << std::endl; // 255900 m std::cout << std::endl; }

 

I will not repeat myself by explaining constant expressions and user-defined literals in detail. I have already done it in the posts to constexpr and user-defined literals. I want to make only two observations:

  1. By the declaration constexpr all variables, instances of the class MyDistance and functions become constant expressions. The compiler performs, therefore, the necessary operations at compile time.
  2. All variables, instances, and functions - excluding std::cout - are constant expressions. That means the entire program will be executed at compile time. Therefore, all used variables and instances are immutable. Only the output of the program 255900 m in line 77 is performed at run time.

What's next?

Pure functions are quite similar to mathematical functions. They are the reason why Haskell and template metaprogramming are called pure functional languages. But what are the restrictions that a pure functional language has to fight with? These will be my topic of the next post. 

Tags: constexpr

Comments   

0 #51 Adele 2017-07-29 14:48
It works very well for me
Quote
0 #52 Debra 2017-07-29 15:27
I enjoy the report
Quote
0 #53 Louanne 2017-07-29 16:49
I like the article
Quote
0 #54 Angelo 2017-07-29 18:25
This is actually useful, thanks.
Quote
0 #55 Chara 2017-07-30 00:56
It works very well for me
Quote
0 #56 Jonnie 2017-08-02 13:14
I enjoy the report
Quote

Add comment


My Newest E-Books

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 154

All 456536

Currently are 182 guests and no members online