Metaprogramming and Lambda Expressions

Subjects

• auto show in cppinsights

• Templates with constants (fib,sum,array)

• Template specialization

• Template Metaprogramming (TMP) Physics

• Lambdas

auto

vector example

list example

Fixed vector example

Lets make up a new container called fixed_vector

#include <iostream>
using std::cout;

template <typename T, int I>
class fixed_vector{
    T arr[I];
    int size;
public:
    fixed_vector() : size(0) {}

    void push_back(T t){
        if (size<I){
            arr[size] = t;
            ++size;
        }
    }

    //TODO change to T&, was lazy :)
    T operator[] (int index){
        if (index<size && index>=0)
            return arr[index];
        else // was lazy :)
            return -1;
    }
};

int main(){
    fixed_vector<int,3> fv;
    for (int i = 1; i < 10; ++i)
        fv.push_back(i);

    for (int i = 0; i < 6; ++i)
        cout << fv[i] << " ";

    return 0;
}

1 2 3 -1 -1 -1

TODO add iterators

Specialization

Sometimes we just want to feel special 😂

#include <iostream>
using std::cout,std::endl;

template <typename T>
struct SpecializedStruct{
    SpecializedStruct() {cout << "I'm not special :(\n";}
    void foo(){cout << "something stupid :(\n";}
};

template <>
struct SpecializedStruct<double>{
    SpecializedStruct() {
        cout << "I'm a special struct :)\n";
    }
    void foo(){cout << "something funny :)\n";}
};


int main(){
    SpecializedStruct<std::string> sp_stru;
    sp_stru.foo();
    cout << endl;

    SpecializedStruct<double> not_sp_stru;
    not_sp_stru.foo();
    return 0;
}

I'm not special :(
something stupid :(

I'm a special struct :)
something funny :)

notice the emty <> in template<> on then the struct SpecializedStruct<double>

There are 2 types of c++ developers:

• those who like TMP

• and those who don't

Template metaprogramming

Template metaprogramming (TMP) in C++ is a technique for expressing and executing arbitrary algorithms in compile-time using C++ templates.

TMP is a form of declarative programming in which the logic of computation is expressed without the use of explicit control flow statements (if, else, for). Some of these languages include SQL,cypher and sparql

So remember:

• no mutability

• no virtual functions

• no RTTI,etc.

Sum recursion

#include <iostream>
#include <string>
using namespace std;

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

template <>
struct Sum<1>{ //template class specialization
    static const int value = 1;
};

int main () {
    cout << Sum<4>::value << endl;
    return 0;
}

10

The run-time isn't the run-time but rather the compiler is the run-time.

Fibonacci recursion

//@author: nissan goldberg
#include <iostream>
using namespace std;

template <int N>
struct Fib{
    static const int value = Fib<N-2>::value + Fib<N-1>::value;
};

template <>
struct Fib<1>{ //template class specialization
    static const int value = 1;
};

template <>
struct Fib<0>{
    static const int value = 0;
};

int main () {
    cout << Fib<5>::value << endl;
    return 0;
}

8

VS

int fib(int n) { 
    if (n <= 1) 
        return n; 
    return fib(n-1) + fib(n-2); 
}

int main () {
    //0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
    return fib(40);
}

Show C++ Insights

more than 700x speedup (the compilation took 2x the amout so really 350x)

The entire recursion is done by the compiler, while the final program just contain a constant.

Fib with tail recursion (skip this)

//@author: nissan goldberg, was really cool :)
#include <iostream>
using namespace std;

template <long N,long prev ,long next>
struct Fib_tr{
    static const long value = Fib_tr<N-1,next,next+prev>::value;
};

template <long prev, long next>
struct Fib_tr<1, prev, next>{ //template class specialization
    static const long value = next;
};

template <long prev ,long next>
struct Fib_tr<0,prev, next>{
    static const long value = prev;
};

template <int N>
struct Fib{
    static const long value = Fib_tr<N-1,0,1>::value;
};


int main () {
    cout << Fib<90>::value << endl;
    return 0;
}

1779979416004714189

The first 300 Fibonacci numbers, factored to check :)

Physics example

$Velocity=\frac{meter}{sec^1},$ $Acceleration=\frac{meter}{sec^2},$ $Energy=J=\frac{kg^2*meter}{sec^2}$

//@author: Dr. Erel Segel Halevi
#include <cassert>
#include <iostream>
using std::cout;
using std::endl;
using std::ostream;
using std::string;

template <int m, int k, int s>
struct mks {
    double val;
public:
    mks(double val): val(val) {}
};

template <int m, int k, int s>
auto operator+(mks<m,k,s> a, mks<m,k,s> b) {
    return mks<m,k,s>(a.val+b.val);
}

template <int ma, int ka, int sa, int mb, int kb, int sb>
auto operator*(mks<ma,ka,sa> a, mks<mb,kb,sb> b) {
    return mks<ma+mb,ka+kb,sa+sb>(a.val*b.val);
}

template <int ma, int ka, int sa, int mb, int kb, int sb>
auto operator/(mks<ma,ka,sa> a, mks<mb,kb,sb> b) {
    return mks<ma-mb,ka-kb,sa-sb>(a.val/b.val);
}

template <int m, int k, int s>
ostream& operator<<(ostream& out, mks<m,k,s> a) {
    return (out << a.val);
}

using Meters=mks<1,0,0>;  // meter
using Seconds=mks<0,0,1>;    // second
using Kilograms=mks<0,1,0>;    // kilogram
using Velocity=mks<1,0,-1>;  // meter*(second)^(-1)
using Acceleration=mks<1,0,-2>;  // meter*(second)^(-2)
using Energy=mks<2,1,-2>;  // kg^2*meter*(second)^(-2)

mks<0,0,1> operator"" _sec(long double x) { return mks<0,0,1>(x); }
mks<0,0,1> operator"" _min(long double x) { return mks<0,0,1>(x*60); }
mks<0,0,1> operator"" _hour(long double x) { return mks<0,0,1>(x*3600); }

int main() {
    //double time=5;   // seconds
    //double length = 7;  // meters
    //
    //cout << time+length;   // logic error

    Meters length = 15; // 15 meters
    cout << "length = " << length << endl;
    Seconds time   = 3;  // 3 seconds
    cout << "time = " << time << endl;
    //cout << time+length;   // compilation error

    Seconds time1 = 1.0_hour + 2.0_min + 50.0_sec;
    cout << "time1 = " << time1 << endl;

    //mks<0,0,2> time2 = 5;
    //cout << time+time2;

    auto velocity = length/time;
    cout << "velocity = " << velocity << endl;

    Velocity velocity2 = 4;
    cout << "velocity2 = " << velocity2 << endl;

    auto velocity_sum = velocity+velocity2;
    cout << "velocity_sum = " << velocity_sum << endl;
    //auto v_plus_l = velocity+length; // won't compile

    Velocity c = 3e8;  // speed of light (m/s)
    Kilograms m = 5; // 5 kg uranium
    auto mc = m*c;
    auto mc2 = m*c*c;
    Energy E(0);
    E = m*c*c;
    cout << "energy = " << E << endl;
}

length = 15
time = 3
time1 = 3770
velocity = 5
velocity2 = 4
velocity_sum = 9
energy = 4.5e+17

The code above allows us to only add + the same units.This is because they have the same m,k and s

auto operator+(mks<m,k,s> a, mks<m,k,s> b)

But we can divide / and multiply * different unit

template <int ma, int ka, int sa, int mb, int kb, int sb>
auto operator/(mks<ma,ka,sa> a, mks<mb,kb,sb> b) {

Use TMP (Template Meta-Programming) when:

• A macro is not enough. You need something more complex than a macro, and you need it expanded before compiled.

• Using recursive function with a predetermined number of loops. In this case the overhead of function calls and setting up stack variables can be avoided and runtime will significantly decrease.

• Using loops that can be unrolled at compile time. For example hash-algorithms like MD5 and SHA1 contains well-defined block processing loops that can be unrolled with TMP.

• When calculating constant values. If you have constants that depend on other constants in your program, they might be a candidate for TMP.

• When the program should be portable to other platforms. In this case TMP might be an alternative to macros.

  Don't use TMP when:

• When a macro will do. In most cases a macro will be enough. And a macro is often easier to understand than TMP.

• You want a small executable. Templates in general, and TMP in particular will in often increase the code size.

• Your program already takes a long time to compile. TMP might significantly increase compile time.

• You are on a strict deadline. As noted above the complier will be very unfriendly when working with Template Metaprograms. Unless the changes you intend to make are very simple, you might want to save yourself a few hours of banging your head in the wall.

source

Functors - Overriding Function call operator

#include <iostream>

struct Multiply{
    double operator()( const double v1, const double v2 ) const{
        return v1 * v2;
    }
};

int main (){
    const double v1 = 3.3;
    const double v2 = 2.0;
    Multiply m;

    std::cout << v1 << " * " << v2 << " = "
              << m( v1, v2 )
              << std::endl;
}

3.3 * 2 = 6.6

Understanding Lambdas

What does a lambda really look like?

int main(){
    auto l = []() { return 5;};
    cout << typeid(l).name() << endl;
}

Z4mainEUlvE_

main- is the function, v- is void.

Here the lambda l is similar to the following struct:

struct __main_lambda_0{
    auto operator()() const {
        return 5;
    }
};

Remove the double underscores to compile

Now if we were to add a int param like this

[](int i) { return 5+i;};

It would be similar to this

struct __main_lambda_0{
    auto operator()(int i) const {
        return 5+i;
    }
};

int main(){
    auto l = [](int i) { return 5+i;};
    cout << typeid(l).name() << endl;

    cout << l(3) << endl;
}

Z4mainEUliE_
8

If we add a capture it would look like this:

[val](int i) { return 5+i+val; };

It is similar to this:

//The same as the lambda l
struct __main_lambda_0{
    int val;

    __main_lambda_0(int v):val(v){} //ctor

    auto operator()(int i) const {
        return 5 + i + val;
    }
};

int main(){
    int val = 10;
    auto l = [val](int i) { return 5+i+val; };

    //auto l = __main_lambda_0{val}; 

    cout << l(3) << endl;
}

First call the ctor with val, then call the functor with 3.

Now if we replace val with ++val wouldn't work, here is why

int val = 10;
auto l = [val](int i) { return 5+i+ ++val; };
//cout << l(3) << endl;

this is because our structs () operater is const in auto operator()(int i) const {

mutable

Now If we add the mutable specifier we would remove the const

int val = 10;
auto l = [val](int i) mutable { return 5+i+ ++val; };
cout << l(1) << endl;

lets use the cpp insights to see what is really happening here.

auto in param

Using auto i:

int val = 10;
auto l = [val](auto i) mutable { return 5+i+ ++val; };

Would result to this:

struct __main_lambda_0{
    int val;

    template<typename T>
    constexpr auto operator()(T i) const {
        return 5 + i + val;
    }
};

Lets Review

• Basically a lamba is an object.

• The capture list is init list of the ctor.

• The params are a functor that is by default const unless we use the keyword mutable

Lambda syntaxes:

• [ captures ] ( params ) -> ret { body }

• [ captures ] ( params ) { body }

• [ captures ] { body }

Added C++20 syntax

• [ captures ] <tparams>( params ) specifiers exception-> { body }

// generic lambda, operator() is a template with two parameters
auto glambda = []<class T>(T a, auto&& b) { return a < b; };

// generic lambda, operator() is a template with one parameter pack
auto f = []<typename ...Ts>(Ts&& ...ts) {
   return foo(std::forward<Ts>(ts)...);
};

Lambda capture

Capture Many

• & : by reference

• = : by value

Capture individual:

• &var_name: by-reference capture

• this : by-reference capture of the current object

Mixing up captures:

[&]{};          // OK: by-reference capture default
[&, i]{};       // OK: by-reference capture, except i is captured by copy

More about lambdas

Examples of Lambdas

#include <iostream>
#include <vector>
#include <algorithm>
using std::vector; using std::endl; using std::cout;

int main(){
    cout << "Starting Lambdas examples \n";
    std::vector<int> v1 = { 3, 1, 7, 9 };
    std::vector<int> v2 = { 10, 2, 7, 16, 9 };

    // access v1 and v2 by reference
    auto pushinto = [&v1,&v2](const int& m){
        v1.push_back(m);
        v2.push_back(m);
    };
    // it pushes 20 in both v1 and v2
    pushinto(20);

    // access v1 by copy
    [v1]() {
        cout << "printing values, access v1 by copy\n";
        for (auto p = v1.begin(); p != v1.end(); p++)
            cout << *p << " ";
    }();
}

Starting Lambdas examples 
printing values, access v1 by copy
3 1 7 9 20

Next we'll use the find_if function

InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate predicate); Returns: an iterator to the first element in the range [first, last] for which pred(function) returns true

explanation

Lets change our main function to find first number greater than N. [N] denotes, can access only N by value

int main(){
  std::vector<int> v1 = { 3, 1, 7, 9,20 };
  std::vector<int> v2 = { 10, 2, 7, 16, 9,20 };

  int N = 5;
  int k = 0;
  auto p = find_if(v1.begin(), v1.end(), [N](int& i){
          //i++; this works
          return i > N;
  });
  cout << "First number greater than 5 is : " << *p << endl;
  return 0;
}

First number greater than 5 is : 7

if we were to change it to this we would get an error

auto p = find_if(v1.begin(), v1.end(), [N](int& i){
        k++;
        return i > N;
    });
    cout << "K is " << k << endl;

Because k cannot be implicitly captured because no default capture mode has been specified.

Finally, lets use the count_if function in our main, which will count numbers greater than or equal to N.

int main(){
    std::vector<int> v1 = { 3, 1, 7, 9, 20 };
    std::vector<int> v2 = { 10, 2, 7, 16, 9,20 };

    int count_N = count_if(v1.begin(), v1.end(),
                           [&N](int a)->bool{
                               return (a >= N);
                           });

    cout << "The number of elements greater than or equal to 5 is : "
         << count_N << endl;

    return 0;
  }

This code also works without spefically defining the return type ->bool on line 6.

We could clean this up to be one line:

    int count_N = count_if(v1.begin(), v1.end(),[=](int a){ return (a >= N);});

Here we also used [=] to access all the variables by value