Funktionale Programmierung (FP) in C++

Martin Sulzmann

Übersicht

Funktionale Programmierung (FP)
- Lambdas in C++ (capture by copy or by reference)
- Partielle Funktionsanwendung (Funktionsanwendung ist links-assoziativ)
- Lokale Typinferenz via “auto”
- Spielereien
Nochmal stack machines
- Anwendung von funktionaler Abstraktion (Spielereien)
- Methoden run und exp als Instanzen der exec Methoden
C-Funktionen versus C++ closures (function template)

Ist das was neues?

Nein! Siehe Lisp aus den 50er/60er Jahren.

Funktionale Programmierung (FP) war immer da. War aber nie “main stream”. Findet sich aber jetzt in den meisten Programmiersprachen (z.B. Java, Python, …).

Motivation

Mapper int Array

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; }

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

   mapInt(x,5,inc);
   mapInt(x,5,square);
}

Mapper float Array

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

float incF(float x) { return x+1; }
float squareF(float x) { return x*x; }

void beispiel2() {
   float y[5] = { 1.0,2.0,3.0,4.0,5.0 };

   mapFloat(y,5,incF);
   mapFloat(y,5,squareF);
}

(Funktionale) Abstraktion über die “map” Funktion.

Effektiv identisch zur “int” Version.

Generische Variante

template<typename T>
void map(T* p, int len, T f(T)) {
 for(auto i=0; i<len; i++)
   p[i] = f(p[i]);
}

void beispiel3() {
   int x[5] = { 1,2,3,4,5 };
   float y[5] = { 1.0,2.0,3.0,4.0,5.0 };

   // Instanziierung der generischen Funktion.
   map<int>(x,5,inc);
   map<float>(y,5,squareF);


   // Mit anonymen Funktionen (aka "lambdas")
   map<int>(x,5,[](int i) -> int { return i+1; });
   map<float>(y,5,[](float f) -> float { return f*f; });
}

Funktionale Abstraktionen kommen oft in Kombination mit “generics”.

“map” Funktionen werden als anonyme Funktion (aka “lambda” Notation) dargestellt.

Lambda notation

Bevor wir uns FP in C++ anschauen, zuerst ein paar Beispiele in Lambda Notation.

Betrachte

f = \x -> x + 1

Wir verwenden hier die Lambda Notation zur Darstellung von anonymen Funktionen.

Betrachte folgende Lambda Funktion zur Inkrementierung einer beliebigen Zahl.

\x -> x + 1

Beschreibung der Syntax

\x

Lambda Funktion mit Parameter x in “griechischer” Schreibweise $\lambda x$

->

Trennt Funktionsparamter from Funktionsrumpf

x + 1

Funktionsrumpf ist hier ein Ausdruck

Zusammengefasst.

f = \x -> x + 1

    ^^^^^^^^^^^^

    Lambda Funktion = anonyme Funktion (Funktion ohne Namen)

Die Lambda Funktion ist gebunden an die Variable f.

Funktionsauswertung

Auswertung von f(1).

Wir schreiben “=>” fuer einen Auswertungsschritt.

    f(1)
=> (\x -> x + 1)   (1)
   ^^^^^^^^^^^^    ^^^^^
    Funktion       Argument

=> (Ersetze Parameter x durch das Argument 1)

   1 + 1

=> 2

Weiteres Beispiel.

y = 1

f = \ x -> x + y

Beachte. Die Lambda Funktion \ x -> x + y hat Paramter x und verweist auf die “freie” Variable y.

D.h. im Funktionsrumpf können wir auf Variable verweisen, welche in einem äusseren Sichtbarkeitsbereicht definiert sind.

f(1) liefert 2

weil

       f(1) =>  x + y wobei gilt x = 1
            =>  1 + y
            =>  1 + 1 weil in y der Wert 1 gespeichert ist
            => 2

Partielle Funktionsanwendung

Betrachte

sum1 = \(x,y) -> x + y


 sum1(3,4) => 7

Parameter von sum1 ist ein Paar von Werten.

Betrachte

sum2 = \x -> (\y -> x + y)

(sum2(3))(4)

sum2(3) liefert eine Funktion! Dies wird auch partielle Funktionsanwendung (“partial application” genannt.

sum2(3) => \y -> 3 + y

Deshalb

(sum2(3))(4) => (\y -> 3 + y)(4) => 3 + 4 => 7

Funktionsanwendung ist links-assoziativ

Anstatt

(sum2(3))(4)

können wir kürzer schreiben

sum2(3)(4)

Klammern können “links” weggelassen werden. Die Annhame ist das Funtionsanwendung links-assoziativ ist.

Methodenverkettung ist ebenfalls links-assoziativ

Betrachte folgendes Java Beispiel.

(obj1.meth1()).meth2()

Auf Objekt obj1 wenden wir die Methode meth1 an.
Das Ergebnis ist wiederum ein Objekt.
Auf dieses Objekt wenden wir die Methode meth2 an.

In Java ist dies als Methodenverkettung (method chaining).

Methodenverkettung ist links-assoziativ. Deshalb können wir obigen Programmcode wie folgt schreiben.

obj1.meth1().meth2()

Capture by copy versus capture by reference

Betrachte

y = 1

f = \ x -> x + y

y = 2

z = f(1)

Wir definieren zuerst y dann f. Danach überschreiben wir den Wert gespeichert in y mit 2.

Welchen Wert liefert die Auswertung von f(1)? Was ist der Wert von z?

Es kommt darauf an wie wir die “freie” Variable y in der Definition von f behandeln.

Es gibt hier 2 Möglichkeiten.

capture by copy oder
capture by reference.

Der Unterschied zwischen capture by copy und capture by reference bezieht sich auf die Behandlung von freien Variablen.

Capture by copy

capture by copy, bedeutet Werte von freien Variable werden kopiert.

Betrachte

    y = 1
    f = \ x -> x + y   // An der Stelle wir ersetzen effektiv y durch den Wert 1.
                       // Aus der Sicht des Compilers gilt:
                       // f = \x -> x + 1

    y = 2
    z = f(1)

f(1) liefert 2 weil

           f(1) => x + y wobei x = 1
                => 1 + y wobei die Annahme capture by copy gilt, der kopierte Wert von y ist hier 1
                => 1 + 1
                => 2

Frage: Weshalb benutzt man capture by copy, anstatt direkt einen konstanten Wert einzugtragen? Also warum der Umweg über die Variable y?

Antwort: Siehe Konstanten. Besser Platzhalter (Variablen) zu verwenden als konkrete Zahlen.

Capture by reference

capture by reference, bedeutet bei der Auswertung des Lambda Ausdrucks, holen wir uns immer den aktuellen Wert der freien Variablen.

Betrachte

    y = 1
    f = \ x -> x + y   // An der Stelle merken wir uns die Referenz auf die freie Variable y
                       // Aus der Sicht des Compilers, mehr Arbeit ist notwendig.
                       // Wir muessen uns alle freien Variablen merken.

    y = 2
    z = f(1)

f(1) liefert 3 weil

             f(1) => x + y wobei x = 1
                  => 1 + y wegen Annahme (b), gilt y ausgewertet liefert 2
                  => 1 + 2
                  => 3

C++

C++ unterstützt capture by copy und capture by reference

Deshalb ist die C++ Lambda Notation “kompliziert”.

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

In den meisten anderen Programmiersprachen wird immer capture by reference verwendet.

Einfache FP Beispiele in C++

// --std=c++14

#include <functional>
#include <stdio.h>
#include <iostream>
using namespace std;



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 test1() {
   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;
}

void test2() {

  // Entweder
  // int x = 1;
  // oder wir verwenden "auto".
  auto x = 1;
  auto f = [x] (int y) -> int { return x + y; };

  cout << f(1) << " ";
  x = 5;
  cout << f(1) << " ";

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

  x = 2;
  cout << g(1) << " ";
  x = 3;
  cout << g(1);
}



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 Rueckgabewerthat!

      // Betrachte std::function<int(int).
      // Beschreibt eine Funktion mit Argumenttyp int und Rueckgabetyp int.
      // In der Mathematik geschrieben als "int -> int".
      // In C++, ist "function" ein Template zur Beschreibung solcher Funktionsraeume.
      // Das ganze ist definiert im Name space "std".

      function<function<int(int)>(int)> sum;
      //         int -> int
      //  int -> (int -> int) ist der Typ von sum !!!
      // Im allgemeinen gilt:
      //  function<B(A)>  beschreibt den Funktionstyp "A -> B".

      sum = [](int x) -> function<int(int)> { return [x](int y) -> int { return x + y; }; };
      // 1.   Auesserer Lambda-Ausdruck, hat Parameter x vom Typ int
      // 2.                     Rueckgabetyp ist ein Lambda Funktionstyp!
      // 3.                                                    Innerer Lambda-Ausdruck!
      // 4.                                                    Parameter y vom Typ int.




      // Liefert Fehler!
      // Weil sum, d.h. der aeussere Lambda-Ausdruck erwartet "int x" als Parameter!
      // cout << sum(5,2) << endl;

      // cout << sum(5) << endl;
      // Beachte:
      //  Welchen Wert liefert sum(5) ???
      // sum(5) liefert eine Funktion zurueck!
      // Deshalb liefert "cout << sum(5);" einen Compilerfehler.

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

      // Wieso erhalten wir 7?
      // 1. sum(5) liefert effektiv den Lambda-Ausdruck "\y -> 5 + y".
      // 2. sum(5) ist eine Funktion, wir fuettern diese Funktion mit einem weiteren Argument.
      // 3.     (sum(5))      (2)
      //        ^^^^^^^^      ^^^^^
      //        Funktion      Argument
      // 4. Deshalb erhalten wir 7 als Ergebnis!

      // Beispiel einer partiellen Funktionsanwendung.

      // ZWISCHENDURCH: In C++/Java gilt folgendes.
      // Im Fall von Methodenaufrufen, betrachte z.B.
      //  (obj.m1()).m2()
      //   obj unterstuert die Methode m1 und liefert ein Objekt zurueck
      //   auf welches wir Methode m2 anwenden.
      //  Abkuerzendende Schreibweise: obj.m1().m2()
      //  Annahme ist, dass Methodenaufrufe sind links-assoziativ.

      //  Obige Annahme fuer Methodenaufrufe wird auch angewandt
      //  fuer Funktionsanwendungen.
      //  Annahme ist, dass Funktionsanwendung sind links-assoziativ.
      //  Deshalb anstatt (sum(5))(2) koennen wir kuerzer schreiben:

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

}

// Spielereien.
void sumEx3() {

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

  auto inc = sum(1);

  cout << inc(2) << endl;
  // Effektiv das gleiche wie
  // cout << sum(1)(2) << endl;

}

void test3() {
  // sumEx();
  // sumEx1();
  // sumEx2();
  // sumEx3();

}


int main() {
  // test1();
  // test2();
  // test3();

}

FP Version von `count`

#include <functional>
#include <stdio.h>
#include <iostream>
using namespace std;

////////////////////////////////////
// Zaehlen von Woertern.
// Wort = Sequenz von Zeichen welche nicht ' ' (Leerzeichen/Blank) entaehlt.



// C Version


char* skipBlanks(char* input) {
  while(input[0] == ' ')
    input++;
  return input;
}

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


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

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

// C++ strings

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

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

 return count(cString);
}


////////////////////////////////////
// Funktionale Version


std::function<string(string)> skip(std::function<bool(char)> p)  {
  return [p](string s) -> string  {
    if (s.length() == 0) {
      return s;
    } else if(p(s[0])) {
    string s2 = s.substr(1);
    return skip(p)(s2);
    } else {
    return s;
    }
  };
}


int countFP(string input) {
  int cnt = 0;

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

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

  while(input.length() != 0) {
    input = skipBlanks(input);
    if(input.length() != 0) {
      cnt++;
      input = scanWord(input);
    }
  }
  return cnt;
}

void testCount(std::function<int(string)> countFunc) {
  string tests[3] = { "", "dfd ", " dfjkd .s22?? " };

  for(int i=0; i <3; i++) {
    cout << "\n" << countFunc(tests[i]);
  }
}

int main() {
  testCount(countString);
  testCount(countFP);
}

FP Version und C Strings

std::function<char*(char*)> skip(std::function<bool(char)> p)  {
  return [p](char* s) -> char*  {
    if (*s == '\0') {
      return s;
    } else if(p(s[0])) {
    return skip(p)(s+1);
    } else {
    return s;
    }
  };
}


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

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

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

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

Nochmal Stack Machines

Anwendung von funktionaler Abstraktion (Spielereien)
Methoden run und exp als Instanzen der exec Methoden

// Simple stack-based VM.

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

// VM code
typedef enum {
  PLUS,
  MULT,
  ONE,
  TWO
} Code_t;

string show(Code_t c) {
  switch(c) {
  case ONE: return "1";
  case TWO: return "2";
  case PLUS: return "+";
  case MULT: return "*";
  }
}

string show(vector<Code_t> cs) {
  string s;
  for(int i=0; i < cs.size(); i++) {
    s = s + show(cs[i]);
    if(i < cs.size() - 1) {
      s = s + " ";
    }
  }
  return s;
}

class VM {
    vector<Code_t> code;
  public:
    VM(vector<Code_t> c) : code(c) {}

  void showAndRun() {
    cout << "\n Exp: " << exp();
    cout << "\n VM code: " << show(code);
    cout << "\n => " << run();
  }

  void showAndRun2() {
    cout << "\n Exp: "
     << exec<string>(
         [](Code_t x) -> string {
           return show(x);
         },
         [](string x, Code_t op, string y) -> string {
           switch(op) {
               case PLUS: return ("(" + x + " + " + y + ")");
               case MULT: return ("(" + x + " * " + y + ")");
           default: return ""; // should never apply
           }
             });
    cout << "\n VM code: " << show(code);
    cout << "\n => "
     << exec<int>(
         [](Code_t x) -> int {
               switch(x) {
               case ONE: return 1;
           case TWO: return 2;
           default: return -1; // should never apply
           }
         },
         [](int x, Code_t op, int y) -> int {
           switch(op) {
               case PLUS: return (x+y);
               case MULT: return (x*y);
           default: return -1; // should never apply
           }
             });
  }

/*

Methoden run sind exp sind von der Struktur sehr aehnlich.

Wir abstrahieren den gemeinsamen Kern in der exec Methode
welche in einer apply Funktion parameterisiert ist.

Durch geeignet Wahl der apply Funktion erhalten wir run und exp.

*/

  int run() {
    stack<int> s;

    for(int i = 0; i < code.size(); i++) {
    switch(code[i]) {
    case ONE:
      s.push(1);
        break;
    case TWO:
      s.push(2);
        break;
    case MULT: {
      auto right = s.top();
      s.pop();
      auto left = s.top();
      s.pop();
      s.push(left * right);
      break;
    }
    case PLUS: {
      auto right = s.top();
      s.pop();
      auto left = s.top();
      s.pop();
      s.push(left + right);
      break;
    }
    } // switch
      } // for

      return s.top();
  } // run

  string exp() {
    stack<string> s;

      for(int i = 0; i < code.size(); i++) {
    switch(code[i]) {
    case ONE:
      s.push("1");
        break;
    case TWO:
      s.push("2");
        break;
    case MULT: {
      auto right = s.top();
      s.pop();
      auto left = s.top();
      s.pop();
      s.push("(" + left + " * " + right + ")");
      break;
    }
    case PLUS: {
      auto right = s.top();
      s.pop();
      auto left = s.top();
      s.pop();
      s.push("(" + left + " + " + right + ")");
      break;
    }
    } // switch
      } // for

      return s.top();
  } // run

  template<typename T>
  T exec(std::function<T(Code_t)> convert, std::function<T(T,Code_t,T)> apply) {
    stack<T> s;

      for(int i = 0; i < code.size(); i++) {
    switch(code[i]) {
    case ONE:
      s.push(convert(ONE));
        break;
    case TWO:
      s.push(convert(TWO));
        break;
    case MULT: {
      auto right = s.top();
      s.pop();
      auto left = s.top();
      s.pop();
      s.push(apply(left,MULT,right));
      break;
    }
    case PLUS: {
      auto right = s.top();
      s.pop();
      auto left = s.top();
      s.pop();
      s.push(apply(left,PLUS,right));
      break;
    }
    } // switch
      } // for

      return s.top();
  } // run

};


// Examples

void testVM() {

  {
    vector<Code_t> cs{
      ONE, TWO, TWO, PLUS, MULT
    };


    VM(cs).showAndRun();
  }

  {
    vector<Code_t> cs{
      ONE, TWO, PLUS, TWO, MULT
    };


    VM(cs).showAndRun();
  }


}



int main() {

  testVM();
}

C-Funktionen versus C++ closures (function template)

Online version

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

// C-style functions versus C++ closures (function template)
// int f(int)  versus  function<int(int)> f


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

typedef int (*intToint)(int); // A bit of a Hack to define local variables that have a C-style function type.

int main()
{

    intToint f1;

    function<int(int)> f2;

    // OK
    // C-style functions can be converted to C++ closures ("function").
    f1 = inc;
    f2 = inc;

    // OK
    int y = 1;
    f2 = [y](int x) -> int { return x+y; };

    // Not OK
    // C++ closures cannot be converted C-style functions.
    //f1 = [y](int x) -> int { return x+y; };

    // OK
    // Special case.
    // If the capture list is empty, C++ closures can be converted to C-style functions.
    f1 = [](int x) -> int { return x+1; };

    function<int(int)> g;
    g = [](int x) -> int { return x+1; };

    // Not OK
    // The capture list of g is empty.
    // But based on g's type, function<int(int)>, the compiler assumes the assigment could be to C++ closure
    // with a non-empty capture list. Hence, the assignment is rejected.
    // f1 = g;

    return 0;
}

Funktionale Programmierung (FP) in C++

Übersicht

Motivation

Mapper int Array

Mapper float Array

Generische Variante

Lambda notation

Beschreibung der Syntax

Funktionsauswertung

Partielle Funktionsanwendung

Funktionsanwendung ist links-assoziativ

Methodenverkettung ist ebenfalls links-assoziativ

Capture by copy versus capture by reference

Capture by copy

Capture by reference

C++

Einfache FP Beispiele in C++

FP Version von count

FP Version und C Strings

Nochmal Stack Machines

C-Funktionen versus C++ closures (function template)

FP Version von `count`