Funktionaler Programmierstil

Ein Mix folgender Ideen.

Funktionen als elementares Programmiermittel
- Funktionsparameter
- Funktionen als Rückgabewerte
- Anonyme Funktionen (“lambdas”)
Reine versus Seiten-effekt behaftete Funktionen (Monaden, …)
Algebraische Datentypen und Pattern-matching
Ausdrucksstarke Typen (in der Regel statische Typisierung)
Typinferenz

…

Unser Fokus hier ist auf dem ersten und letztem Punkt. Wir betrachten diesen Punkt aus Sichtweise von C++.

C++11/14 unterstützt

auto (und decltype)
- Typinferenz für lokale Variablen
lambdas (anonyme Funktionen)
- Funktionalen Programmierstil

Refs:

http://www.drdobbs.com/cpp/lambdas-in-c11/240168241
https://www.cprogramming.com/c++11/c++11-auto-decltype-return-value-after-function.html
https://www.learncpp.com/cpp-tutorial/4-8-the-auto-keyword/
https://www.cprogramming.com/c++11/c++11-lambda-closures.html

Nochmal Funktionspointer (in C)

#include <stdio.h>

typedef int (*intFunc)(int);

// void mapInt(int* p, int len, int (*f)(int)) {
void mapInt(int* p, int len, intFunc f) {
 int i;
 for(i=0; i<len; i++)
   p[i] = (*f)(p[i]);
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };
   mapInt(x,5,&inc);
   mapInt(x,5,&square);

   printf("%d", x[1]);

   return 0;
}

Implizite Konversion (in neustem Standard).

#include <stdio.h>


void mapInt(int* p, int len, int f(int)) {
 int i;
 for(i=0; i<len; i++)
   p[i] = f(p[i]);
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };
   mapInt(x,5,inc);
   mapInt(x,5,square);

   printf("%d",x[0]);
   return 0;
}

auto - Typinferenz in C++

Neues Schlüsselwort auto = “Automatic inference of type of local variables based on defining right-hand side”.

Bisher.

int x;
x = 1;

Jetzt.

auto x = 1;

Weiteres Beispiel.

Bisher.

 for(int i=0; i<len; i++)
    p[i] = f(p[i]);

Jetzt.

 for(auto i=0; i<len; i++)
    p[i] = f(p[i]);

Hier spart man sich nicht viel (weil die Typen sehr einfach sind).

Automatische Typinferenz ist sehr hilfreich, sobald die Typen komplexer werden.

   int x[5] = { 1,2,3,4,5 };
   int (*f)(int);

   f = inc;
   auto g = inc;

   mapInt(x,5,g);
   mapInt(x,5,f);
   mapInt(x,5,inc);

Komplettes Beispiel


#include <stdio.h>


void mapInt(int* p, int len, int f(int)) {
 for(auto i=0; i<len; i++)
   p[i] = f(p[i]);
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };
   int (*f)(int);

   f = inc;
   auto g = inc;

   mapInt(x,5,g);
   mapInt(x,5,f);
   mapInt(x,5,inc);
   mapInt(x,5,square);

   printf("%d",x[0]);
   return 0;
}

Lambdas in C++11

Lambda = Anonyme Funktion

Lambdas aus der Mathematik

$\lambda x. x$

Identitätsfunktion.

$\lambda x$ = Anonyme Funktion mit Parameter $x$

$.x$ = Funktionsrumpf mit Rückgabeausdruck.

Weitere Beispiele in Ascii Notation.

Wir schreiben

\ x -> x

anstatt $\lambda x.x$ .

f = \x -> x + 1

f(1) liefert 2

y = 1

f = \ x -> x + y

Beachte, freie Variable y!
Variable x gebunden durch lambda.

f(1) liefert 2


y = 2


f(1) liefert ????

(a) capture by copy

    Werte von freien Variable werden kopiert

    f(1) liefert 2

(b) capture by reference

   Merke Referenz auf freie Variable.

   f(1) liefert 3

C++11 Beispiel

Anwendung. Funktion welche nur einmal benutzt wird. Definition an der Stelle wo verwendet wird. …

   // Funktionen mit Namen
   mapInt(x,5,inc);
   mapInt(x,5,square);

   // Lambdas
   mapInt(x,5, [](int x) -> int { return x+1; });
   mapInt(x,5, [](int x) -> int { return x*x; });

   // Kombination mit auto
   auto f = [](int x) -> int { return x+1; };
   mapInt(x,5,f);

Allgemein.

[capture](paramters) -> return_type { function_body }

Kompletter Code

// Usage: g++ -std=c++11

#include <stdio.h>


void mapInt(int* p, int len, int f(int)) {
 for(auto i=0; i<len; i++)
   p[i] = f(p[i]);
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };

   // Funktionen mit Namen
   mapInt(x,5,inc);
   mapInt(x,5,square);

   // Lambdas
   mapInt(x,5, [](int x) -> int { return x+1; });
   mapInt(x,5, [](int x) -> int { return x*x; });

   // Kombination mit auto
   auto f = [](int x) -> int { return x+1; };
   mapInt(x,5,f);

   printf("%d",x[0]);
   return 0;
}

Lambdas und “captures”

Freie Variablen müssen in der “capture” List vermerkt werden. Zwei Arten möglich:

capture by copy oder
capture by reference.

  x = 1;
  auto f = [x] (int y) -> int { return x + y; };

  cout << f(1);
  x = 3;
  cout << f(1);

  auto g = [&x] (int y) -> int { return x + y; };

  x = 1;
  cout << g(1);
  x = 3;
  cout << g(1);

Ausgabe liefert.

Lambdas versus Funktionspointer

void execute(int f(int), int x) {
  cout << f(x);
}

void execute2(std::function<int(int)> f, int x) {
  cout << f(x);
}

...


  auto h = [] (int x) -> int { return x+1; };

  execute(h,1);
  execute2(h,1);       // Konvertierung von Funktionspointer

  x = 1;
  auto f = [x] (int y) -> int { return x + y; };

  execute2(f,1);
  // execute(f,1); // Konvertierung in Funktionspointer nicht moeglich
  // Unterschied wegen lambda + captures, da captures implizite Argumente werden

Komplettes Beispiel



// Usage: g++ -std=c++11

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

void execute(int f(int), int x) {
  cout << f(x);
}

void execute2(std::function<int(int)> f, int x) {
  cout << f(x);
}


int main() {
  int x = 1;


  x = 1;
  auto f = [x] (int y) -> int { return x + y; };

  cout << f(1);
  x = 3;
  cout << f(1);

  auto g = [&x] (int y) -> int { return x + y; };

  x = 1;
  cout << g(1);
  x = 3;
  cout << g(1);


  auto h = [] (int x) -> int { return x+1; };

  execute(h,1);
  execute2(h,1);       // Konvertierung von Funtkionspointer

  execute2(f,1);
  // execute(f,1); // Konvertierung in Funktionspointer nicht moeglich
  // Unterschied wegen lambda + captures, da captures implizite Argumente werden
}

Lambdas und partielle Funktionsanwendung.

Beispiel für Funktion welche eine Funktion als Rückgabe liefert.

// Usage: g++ -std=c++11

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


int sum(int x, int y) { return x + y; }
void sumEx() {
      cout << sum(5, 2) << endl;
      cout << sum(10, 5) << endl;
}

// Mit lambdas.
void sumEx1() {
      auto sum = [](int x, int y) -> int { return x + y; };

      cout << sum(5, 2) << endl;
      cout << sum(10, 5) << endl;


      // Beachte. Inferenz von Rueckgabe Typ ist moeglich.

      auto sum2 = [](int x, int y) /* -> int */ { return x + y; };

      cout << sum2(5, 2) << endl;
      cout << sum2(10, 5) << endl;

}

// Partial function application.
// Uncurried form. See https://wiki.haskell.org/Currying
// The lambda bound variable x appears in the capture list of the inner lambda.
void sumEx2() {

      // Funktion welche eine Funktion hat Rueckgabewert hat!
      auto sum = [](int x) -> std::function<int(int)> { return [x](int y) { return x + y; }; };


     // Beachte. Funktionsanwending ist links-assoziativ.

      cout << (sum(5))(2) << endl;
      cout << sum(5)(2) << endl;
}

// Spielereien.
void sumEx3() {

      auto sum = [](int x) -> std::function<int(int)> { return [x](int y) { return x + y; }; };

      auto inc = sum(1);

      cout << inc(2) << endl;

}

int main() {
  sumEx();
  sumEx1();
  sumEx2();
  sumEx3();

}

Funktionaler Programmierstil oft gepaart mit “generics”

Betrachte folgende “generische” map Funktion.

template<typename A,typename B>
B* map(A* p, int len, B f(A)) {
  B* q = new B[len];
 for(auto i=0; i<len; i++)
   q[i] = f(p[i]);

 return q;
}

Zwei Dimensionen von Generizität

“Mapper” ist generisch
Typen sind generisch

Funktionale Definition (kein “in-place update”).

Naive Implementierung (wir sollten “smart pointers” verwenden).

Komplettes Beispiel


// Usage: g++ -std=c++11

#include <stdio.h>


// Abstraktion mit Hilfe von Templates und "higher-order" functions.
template<typename A,typename B>
B* map(A* p, int len, B f(A)) {
  B* q = new B[len];
 for(auto i=0; i<len; i++)
   q[i] = f(p[i]);

 return q;
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };


   auto y = map<int,int>(x,5, [](int x) -> int { return x+1; });

   auto f = [](int x) -> int { return x+1; };
   auto y2 = map<int,int>(x,5,f);

   printf("%d %d",y[0], y2[0]);


   bool b[3] = { true, false, false };

   auto g = [](bool x) -> int { return x ? 1 : 0; };
   auto b2 = map<bool,int>(b,3,g);

   printf("%d",b2[0]);

   // We don't care about cleaning about the heap memory.
   return 0;
}

“count” Beispiel


#include <cstdlib>
#include <iostream>
#include <string>
#include <functional>

using namespace std;


// Recall

char* skipB(char* input) {
  while(*input == ' ')
    input++;
  return input;
}

char* scanW(char* input) {
  while(*input != '\0' && *input != ' ')
    input++;
  return input;
}


int count(char* input) {
  int cnt = 0;

  while(*input != '\0') {
    input = skipB(input);
    if(*input != '\0') {
      cnt++;
      input = scanW(input);
    }
  }
  return cnt;
}

int countString(string s) {
 char cString[s.size() + 1];

 s.copy(cString, s.size() + 1);
 cString[s.size()] = '\0';

 return count(cString);
}


// Version 1
// Counting words in a string using some "lambdas".

string skip( bool p(char), string s) {
  if(s.size() == 0) {
    return "";
  }
  if(p(s[0])) {
    auto s2 = s.erase(0,1); // drop first character;
    return skip(p, s2);
  }
  return s;
}

string skipBlanks(string s) {
  return skip([](char c) -> bool { return c == ' '; },
          s);
}

string skipWord(string s) {
  return skip([](char c) -> bool { return c != ' '; },
          s);
}


int count(string s) {

  if(s.size() == 0) {
    return 0;
  }

  if(s[0] == ' ') {
    return count(skipBlanks(s));
  }

  return 1 + count(skipWord(s));
}



// Version 2
// Counting words in a string
// The "skip" function returns now a function.
// Thus, we can more elegantly define skipBlanks and skipWord.


function<string(string)> skip2(bool p(char))  {

  return [p](string s) -> string {
            if(s.size() == 0) {
              return "";
            }
            if(p(s[0])) {
              auto s2 = s.erase(0,1); // drop first character;
              return skip2(p)(s2);
            }
            return s;
  };

}


int count2(string s) {

  auto skipBlanks = skip2([](char c) -> bool { return c == ' '; });

  auto skipWord = skip2([](char c) -> bool { return c != ' '; });

  if(s.size() == 0) {
    return 0;
  }

  if(s[0] == ' ') {
    return count2(skipBlanks(s));
  }

  return 1 + count2(skipWord(s));
}


// Testing

void testCount(int count(string)) {

  auto test = [count](string s) {
    cout << "\n" << s << " => " << count(s);
  };

  test("");

  test("hallo");

  test(" hallo");

  test(" hal lo");


}



int main() {

  cout << "\ncountString:";
  testCount(countString);

  cout << "\ncount:";
  testCount(count);

  cout << "\ncount2:";
  testCount(count2);


}

Einführung in C++ - Teil 4 (Funktionaler Programmierstil)

Funktionaler Programmierstil

Nochmal Funktionspointer (in C)

auto - Typinferenz in C++

Komplettes Beispiel

Lambdas in C++11

Lambdas aus der Mathematik

C++11 Beispiel

Kompletter Code

Lambdas und “captures”

Lambdas versus Funktionspointer

Komplettes Beispiel

Lambdas und partielle Funktionsanwendung.

Funktionaler Programmierstil oft gepaart mit “generics”

Komplettes Beispiel

“count” Beispiel

Zusammenfassung