Funktionale Programmierung in C#

Die Mathematiker entwickelten in Jahrhunderten eine eigene Sprache: die Sprache der Formeln und Funktionen. Diese Sprache besteht aus Operatoren wie z.B. + und *, Zahlendarstellungen und Symbolen für Konstanten (z.B. π) und Veränderliche (z.B. x, D). Beispiele sind die Formel zur Berechnung des Kreisumfanges:

U = π * D

Funktionen

Allgemeiner kann man den Zusammenhang zwischen Durchmesser D eines Kreises und seinem Umfang U durch eine Funktion darstellen:

f(D): D → π * D

Den Ausdruck kann man lesen als: die Funktion f(D) ordnet jedem Durchmesser D einen Kreisumfang f(D) = π * D zu. Diese Darstellung wurde in den 1930-er Jahren zu einem präzisen Formalismus ausgearbeitet (Alonzo Church, Stephen Kleene: Lambda- Kalkül), welcher die Grundlage für die Familie der funktionalen Programmiersprachen wie z.B. LISP oder F# bildet.

Während die Mathematiker Funktionen gerne mit einem einzigen Buchstaben bezeichnen, und dabei auch noch auf das griechische Alphabet zugreifen, bevorzugen die Programmierer lieber sprechende Namen wie:

Kreisumfang(D): D → π * D

Funktionen in C#

Eine Funktion wird in C# durch einen Funktionsblock dargestellt. Ein Funktionsblock gliedert sich in:

Der Funktionskopf legt einen Namen und den Typ des Rückgabewertes für die Funktion fest. Weiter wird im Funktionskopf die Parameterliste definiert. Diese listet alle Veränderlichen auf, von denen der Funktionswert abhängt. Im Funktionsblock wird der Funktionswert berechnet und zurückgegeben. Beispielsweise kann die Kreisumfangsfunktion in C# wie folgt dargestellt werden:

  // C#
double Kreisumfang(double D) {
    return Math.Pi * D;
}

Das return entspricht dabei dem Abbildungspfeil → in der mathematischen Darstellung Kreisumfang(D): D → π * D.

Die Funktion kann nun angewendet werden, indem sie mit einem Argument aufgerufen wird:

// Der Umfang eines Kreises mit 250 cm Durchmesser wird berechnet
Kreisumfang(250);

Übungen

Implementieren Sie eine Funktion in C#, die einen gemessene Länge in cm auf eine Länge in m abbildet:

  CmInMeter(x): x → x*0,01

Funktionen speichern und übergeben mittels Delegates

Jedes Unterprogramm, jede Funktion hat im Arbeitsspeicher einen Startadresse, auch Einsprungadresse genannt. Ein Unterprogramm startet, indem der Befehlszähler der CPU mit dieser Einsprungadresse geladen wird.

Wie alle Daten können auch Einsprungadressen gespeichert werden. Variablen, die Einsprungadressen speichern, werden Delegates genannt.

Anwendung finden Delegates in Callback- Methoden bzw. zur Implementierung von Ereignissen.

Basisklasse System.Delegate

Im .NET Framework sind Delegates nichts weiter als Objekte spezieller Klassen. Da jeder Delegate eine individuelle Parameterliste aufweisen kann, können die Delegates nicht alle Objekte einer gemeinsamen Klasse sein. Der C#- Compiler generiert für jeden Delegate automatisch eine versiegelte Klasse die von der Klasse System.Delegate abgeleitet ist.

delegate- Deklaration

Delegate- Klassen werden vom Compiler automatisch aus Deklarationen erzeugt, die mit dem Schlüsselwort d elegate beginnen, und die Signatur der Invoke- Methoden definieren :

[Zugriffsmodifikator] delegate Methodensignatur;

z.B.:

// Klasse erzeugen, in der eine Einsprungadresse einer 
// binären Funktion abgelegt werden kann
delegate double DGBinär(double a, double b);

Aus der delegate- Deklaration erzeugt der Compiler zur Übersetzungszeit eine Klasse folgender Art:

Die Invoke Methode dient zum synchronen Aufruf aller im Einsprungadressen, die in einer Delegate- Variablen gespeichert sind.

Konstruktion

Eine Delegate- Variable wird wie ein Objekt angelegt, wobei die Einsprungadresse dem Konstruktor als Parameter zu übergeben ist.

double Add(double a, double b) {
    return a + b;
}

double Subtract(double a, double b) {
    return a - b;
}

void Main() {

    DGBinär op = null;

    // Adresse von Add dem Delegate als Parameter übergeben
     op = new DGBinär(Add);

    // Aufrufen eines Unterprogrammes über die Einsprungadresse
    var Summe = op.Invoke(3, 9);

    // Compiler erlaubt auch folgende Kurzform für einen Aufruf:
    Summe = op.(3, 9);

    // Weitere Einsprungadressen können mit += hinzugefügt werden
    op += new DGBinär(Subtract);

    // Jetzt werden zwei Methoden mit einem Invoke- Aufruf gestartet
    // Der letzte gewinnt...
    var res = op.Invoke(3, 2);

    // Einsprungadressen können mit -= aus dem delegate wieder
    // entfernt werden
    op += new DGBinär(Subtract);

}

Vordefinierte Delegate- Typen

In der .NET Standardbibliothek System gibt es bereits eine reihe vordefinierter, generischer Delegate- Typen, so das heute die Deklaration eigener Delegate- Typen mittels delegate - Schlüsselwort entfallen kann:

// vordefinierte Delegates für Unterprogramme
delegate void Action<T1, … >(T1 p1, … );

// vordefinierte Delegates für Funktionen
delegate Tresult Func<T1, … , Tresult>(T1 p1, … );

// Beispiel für Einsatz
double Kreisumfang(double D) {
    return Math.Pi * D;
}
static void Main() {

  // Delegate anlegen und Einsprungadresse abspeichern
  var f = new Func<double, double>(Kreisumfang);

  // über Delegate die Funktion aufrufen
  double u = f.Invoke(10.0);  
}

Asynchroner Methodenstart

Delegates ermöglichen Methoden asynchron auszuführen. Dabei wird ein Thread aus dem Threadpool genommen, und in diesem die Methode gestartet. Die geschieht durch die BeginInvoke Methode

  delegate.BeginInvoke([Parameterliste der Methode], AsyncCallback DelegateDerCallBackMethode, object ParameterDerCallBackMethode)

BeginInvoke werden dabei die Parameter der asynchron aufzurufenden Methode, und zusätzlich ein Delegate einer Callback- Methode und deren Parameter übergeben. Die Callback- Methode wird aufgerufen, wenn die asynchron aufgerufene Methode endet. Sie ist vom Typ (Delegate) AsyncCallback:

delegate void AsyncCallback(IAsyncResult ar);

Über BeginInvoke kann der Programmierer an die Callback Methode einen Parameter übergeben (letzter Parameter). Dieser wird in einem Objekt vom Typ IAsyncResult im Feld AsyncState verpackt. Das Objekt vom Typ IAsyncResult wird schließlich an die CallBack- Methode übergeben.

Anonyme Methoden (ab NET 2.0)

Bisher wurde davon ausgegangen, dass einem Delegate eine gewöhnliche sog. benannte Methode zugewiesen wird. In Fällen, wo ein Stück ausführbarer Kode nur an einer Stelle im Programm zugewiesen werden muss, kann der Overhead einer kompletten Methodendeklaration durch sog. Anonyme Methoden eingespart werden.

Eine anonyme Methode wird wie folgt definiert:

delegate(Parameterliste) { /* Methodenrumpf */ }

Im folgenden Beispiel wird dem Ereignis Error der Klasse CLog zwei Ereignishandler als anonyme Methoden zugewiesen:

CLog log = new CLog();

public Form1()
{
   InitializeComponent();

   // Zuweisen von anonymen Methoden an das Ereignis Error
   // Hiedurch wird der Quelltext kompakter, da zwei explizite
   // Methodendeklarationen entfallen
   log.Error += delegate(string msg) 
                { 
                  statusStrip1.Items["toolStripStatusLabel1"].Text = msg; 
                };

   log.Error += delegate(string msg) 
                { 
                  MessageBox.Show(msg); 
                };
}   

private void btnFireEvent_Click(object sender, EventArgs e)
{
   log.LogError("Ein Ereignis");
}

Anonyme Methoden sind ein Vorläufer der wesentlich ausdrucksstärkeren Lambda- Ausdrücke, wie sie im nächsten Kapitel vorgestellt werden. Sie sollten in neuen Projekten nicht mehr eingesetzt werden.

Lambda- Ausdrücke (ab .NET 3.5)

Der Begriff Lambda Ausdruck wurde in einem Formalismus der Mathematiker Alonzo Church und Stephe Kleene in den 1930 Jahren geprägt (Lambda Kalkül ). Dieser Kalkül wird auch als der Urahn der Funktionalen Programmierung betrachtet.

Ein Lambda- Ausdruck ist die Deklaration einer anonymen (= unbenannten) Funktion/Prozedur in Form eines Ausdrucks innerhalb eines Funktions- oder Programmblockes.

  // Klassische Deklaration einer Funktion durch Funktionsblock
// Vorteil:  wiederverwendbar
// Nachteil: Deklaration erfolgt "weitab vom Einsatz"
double Kreisumfang(double D) {
    return Math.Pi * D;
}
static void Main() {
  
  //  Delegate anlegen und Einsprungadresse abspeichern
  var f = new Func<double, double>(Kreisumfang);

  // über Delegate die Funktion aufrufen
  double u = f.Invoke(10.0);  

  // Funktion zur Berechnung des Kreisumfanges "inline" als 
  // Lambda- Ausdruck definieren und einem Delegate zuweisen
  Func<double, double> L = (D) => { return Math.PI * D;};

  // Der Lambda- Ausdruck ist wie eine gewöhnliche Funktion aufrufbar
  u = L(10.0);

  // Syntaktische Vereinfachungen für Lambdaausdrücke:
  // I)
  // Besteht die Lambda- Anweisung nur aus einer return- Anweisung, 
  // dann kann das Schlüsselwort return, das Semikolon zum 
  // Abschluss von return und die Blockklammern {} entfallen:
  Func<double, double> LL = (D) => Math.PI * D;

  // II)
  // Wenn die Parameterliste nur aus einem Parameter besteht, dann 
  // können die () um die Parameterliste weggelassen werden
  Func<double, double> LLL = D => Math.PI * D;
}

Der Sinn von Lambdaausdrücken erschließt sich, wenn diese z.B. über Parameterlisten an Unterprogramme oder Funktionen übergeben werden, um diese "funktional" zu Parametrieren:

// 1) Liste erzeugen mit natürlichen Zahlen
var Liste = new int[]{23, 99, 78, 66, 55, 44, 76, 73};

// 2) Lambda- Ausdruck definieren, der entscheidet, ob eine Zahl durch 3 teilbar ist
Func<int, bool> kriterium = prüfling => prüfling % 3 == 0;

// 3) Lambda- Ausdruck als Filterkriterium einsetzen in einer LINQ- Listenverarbeitungsfunktion
//    Die Linq- Funktion Where(...) gibt alle Listenelemente zurück, die das Kriterium in Form
//    eines Lambda- Ausdruckes erfüllen.
var ListeDerDurchDreiTeilbaren = Liste.Where(kriterium).ToArray();

// 4)
// Lambda deklarieren und Filtern in einer Zeile:
var ListeDerDurchDreiTeilbaren = Liste.Where(z => z % 3 == 0).ToArray();

Fallunterscheidungen

Neben den Ausdrücken wie π * D können die Abbilder von Funktionen auch durch Fallunterscheidungen definiert werden. Z.B. kann die Funktion, die jeder Zahl ihren absoluten Betrag zuordnet, wie folgt beschrieben werden:

  Fallunterscheidungen
                     -z      z < 0
|z| = Abs(z): z → 0  für z = 0
                      z      z > 0

z.B. Abs(-5) = 5, Abs(5) = 5, Abs(0) = 0

Fallunterscheidungen in C#

Die Fallunterscheidung wird mit dem if( … ) { ...}- Block implementiert. Zwischen if( … ) wird die Bedingung definiert. Wenn sie zur Laufzeit erfüllt wird, dann werden die im Block definierten Berechnungen ausgeführt, sonst nicht.

  // C#
long ABS(long z) 
{
  if(z < 0)
    return -z;
  else if (z > 0)
    return z;
  else
    return 0;
}

Übung

Implementieren Sie eine Funktion in C# mit zwei Parametern, die den Preis eines Wirtschaftsgutes und der Warengruppe, zu der es gehört, auf einen Mehrwertsteuerbetrag abbildet:

  Mehrwertsteuerberechnung
                               preis * 0,07       wg = "ermäßigt"
MwSt(preis, wg): (preis, wg) →               für
                               preis * 0,19       wg = "normal"

Funktionen hintereinander schalten

In der Mathematik kann man mittels Funktionen eine Menge {x} auf eine Menge {y}, und die Menge {y} wiederum auf die Menge {z} abbilden. Formal wird dies wie folgt beschrieben:

Wenn f1(x): x → y und f2(y): y → z dann ist f2(f1(x)) : x → z

Damit kann man z.B. die Berechnungen des Kreisumfanges an Durchmesser anpassen, die in verschiedenen Maßeinheiten gemessen wurden:

  Funktionen hintereinanderschalten

MillimeterInMeter(x): x → x * 0,001
CentimeterInMeter(x): x → x * 0,01

Kreisumfang(D): D →  π * D

                     D                           D
            /--------+--------\             /----+----\   
Kreisumfang(MillimeterInMeter(x)): x →  π * (x * 0,001)
Kreisumfang(CentimeterInMeter(x)): x →  π * (x * 0,01)

z.B. Kreisumfang(CentimeterInMeter(100)) = 3,142..., Kreisumfang(MillimeterInMeter(100)) = 0,3142...

Funktionen hintereinanderschalten in C#

Die Syntax der Hintereinanderschaltung ist identisch mit der bereits eingeführten allgemeinen Syntax.

  var UmfangInMeter = Kreisumfang(MillimeterInMeter(x))

Übung

Zu einem Netto- Preis soll erst der Brutto- Preis (inkl. MwSt) und dann der Skonto (3%) berechnet werden. Implementieren Sie die Stufenweise Preisermittlung durch Hintereinanderschalten von Funktionen.

Rekursion

Mathematiker sind findige Menschen. Sie hatten schnell erkannt, dass mit der Hintereinaderschaltung von Funktionen ein mächtiges Instrument bereitsteht, mit dem man sich weit in die Tiefen mathematischer Probleme vorwagen kann. Eine besondere Form ist die Rekursion. Auf dieser basieren die funktionalen Beschreibungen vieler mächtiger Algorithmen.

Z.B. soll ein Vertreter 3 Kunden nacheinander besuchen, wobei die gewählte Reihenfolge die mit der kleinsten Gesamtstrecke ist (Problem der Rundreise mit minimaler Streckenlänge).

Die Lösung benötigt zunächst einen Graphen, dessen Knoten den Startpunkt und die Kunden darstellen, und dessen Kanten die Entfernungen zwischen den Knoten angeben. Dann sind für alle möglichen Reihenfolgen der Besuche die Summen der Wege zu berechnen. Am Ende ist die Reihenfolge mit der kleinsten Summe als Lösung auszuwählen. Folgendes Bild veranschaulicht das Vorgehen:

Wie viele Reihenfolgen über dem Graphen, und wie viele Summen damit gebildet werden müssen, gibt die aus der Kombinatorik bekannte Fakultät- Funktion an:

  Fakultät berechnen

                   1     n = 0             
N!(n): n →           für 
           n*N!(n-1)     n > 0

Die Funktion wird mittels einer Fallunterscheidung definiert, wobei für den Fall n > 0 der Funktionswert durch einen Term beschrieben wird, der N! wiederum enthält. Man erhält eine Lösung, indem man auf eine Lösung für den Vorgänger zurückgreift. Diese Art von Funktionsdefinition wird Rekursion genannt.

Aufgelöst wird die Rekursion von N! z.B. für n = 3 wie folgt:

  N!(3) = 3*N!(2) = 3*2*N!(1) = 3*2*1*N!(0) = 3*2*1*1 = 6

Die Fakultät wächst mit n extrem. Die exakte Lösung des Rundreiseproblem für große n praktisch unmöglich.

Rekursion in C#

  public static long Fact(long n)
{
  if (n == 0)
    return 1;
  else
    return n * Fact(n - 1);
}

Übung

Implementiere eine rekursive Funktion, die eine gegebene Zahlenpaar Basis, Exponent die Potenz berechnet wie folgt:

Potenz(Basis, Exponent): (Basis, Exponent) → Basis Exponent

Beachte dabei die Beziehung: b e = b * b e-1 = b * b * b e-2

Listenverarbeitung mittels Rekursion

In den Naturwissenschaften werden oft mehrere Messwerte einer Beobachtung zugeordnet werden. Es entstehen Paare von Messwerten. Ein Beispiel ist die Beobachtung eines beschleunigenden Fahrzeugs. Dabei wird in festen Zeitabständen die Momentangeschwindigkeit notiert.

  Messung: {(v, t)} := {(1 m/s, 1s), (2 m/s, 2s), …, (12 m/s, 5s)}

Ein anderes Beispiel sind die möglichen Folgen, in denen die Kunden A, B, C besucht werden (siehe vorausgegangener Abschnitt)

Besuchsreihenfolgen: {(K1, K2, K3)} := {(A, B, C), (B, A, C), (B, C, A), (C, B, A), (C, A, B), (A, C, B)}

Die Permutationen über der dreielementigen Menge {A, B, C} bilden hier alle möglichen Reihenfolgen. Jede Reihenfolge wird als ein Triple dargestellt.

Paare, Tripel oder allgemein Tupel sind spezielle Formen von Listen.

  Liste := (e1, e2, …., eN)

Mit Listenverarbeitung werden allgemein Funktionen bezeichnet, die Listen auf Listen oder Listen auf skalare Werte abbilden

  Listenverarbeitung := {f mit f(Liste X) : Liste X → Liste Y oder f(Liste X): Liste X → Y}

Grundlegende Operatoren der Listenverarbeitung

An dieser Stelle soll die Listenverarbeitung mit Mitteln der funktionalen Programmierung in C# eingeführt werden. Dazu wird eine Klassenbibliothek (mko.Algo) mit den notwendigen Funktionen bereitgestellt. Die Funktionen aus der Bibliothek verbergen die "technischen" Details (Arrays, IEnumerable<T> Schnittstelle, Linq) der Listenverarbeitung in .NET. Die Bibliothek führt damit die Listenverarbeitung auf einer sehr abstrakten, und damit allgemeingültigen Art und Weise ein.

In der mko.Algo Klassenbibliothek findet man die Listenverarbeitungsfunktionen unter folgendem Namensraum in der Klasse Fn :

  using mko.Algo.Listprocessing

Folgenden Tabelle beschreibt die Listenverarbeitungsfunktionen aus mko.Algo.Listprocessing

Spezielle Listenverarbeitungsfunktionen, rekursiv implementiert

Mittels der allgemeinen Listenverarbeitungsoperationen können spezielle, Anwendungsspezifische Listenoperationen bereitgestellt werden. Hier wird die Rekursion intensiv genutzt.

Bildet die Summe aller Werte in einer Liste

  /// <summary>
/// Summenbildung
/// Summe({a1, a2, …, aN}): {a1, a2, …, aN} → a1 + a2 + … + aN
/// </summary>
/// <param name="liste"></param>
/// <returns></returns>
public static double Sum(IEnumerable<double> liste)
{
  if (lisp.Fn.Count(liste) == 0)
    return 0;
  else if (lisp.Fn.Count(liste) == 1)
    return lisp.Fn.First(liste);
  else
    return lisp.Fn.First(liste) + Sum(lisp.Fn.Skip(liste, 1));
}

Sucht das Minimum in einer Liste

  Minima finden

Min({…}): {…} → min mit min ϵ {…} & Für alle x ϵ {…} gilt: min <= x

public static double Min(IEnumerable<int> list)
{
   if (lisp.Fn.Count(list) == 0)
      throw new Exception();
   else if (lisp.Fn.Count(list) == 1)
      return lisp.Fn.First(list);
   else if (lisp.Fn.First(list) < Min(lisp.Fn.Skip(list, 1)))
      return lisp.Fn.First(list);
   else
      return Min(lisp.Fn.Skip(list, 1));
}

Erzeugt eine Liste mit den Werten 1-N

  Liste mit Werten erzeugen

/// <summary>
/// Erste Permutation von n Elementen. Alle weiteren 
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static IEnumerable<long> FirstPermutation(long n)
{
   if (n == 1)
      return lisp.Fn.L(n);
   else
      return lisp.Fn.Concat(FirstPermutation(n - 1), lisp.Fn.L(n));
}

Prüft zwei Listen auf vollständige Übereinstimmung

  Gleichheit von Listen prüfen

Equal({a1,a2,…,aN}, {b1,b2,…,bM}): ({a1, a2, …, aN}, {b1, b2, …, bM}) → true für 
                                         Count({a1,a2,…,aN})  = Count({b1, b2, …, bM}) und
                                         a1 = b1, a2 = b2, …, aN = bM

public static bool EqualPureFn<T>(IEnumerable<T> listA, IEnumerable<T> listB) {

  if (Count(listA) != Count(listB))
     // Ungleich lange Listen können nie gleich sein
     return false;
  else if (Count(listA) > 0)
     // Rückführung auf die Prüfung, das der Anfang gleich ist, und der Rest auch
     return First(listA).Equals(First(listB)) && EqualPureFn(Skip(listA, 1), Skip(listB, 1));
  else
     // zwei leere Listen sind immer gleich
     return true;
}

Beispiel: Primzahlscanner funktional realisieren

Teilaufgabe 1 kann z.B. durch folgende Funktion dargestellt werden (Pseudokode):

  IstPrimzahl(z): z → z Mod 2 <> 0 AND TesteWeiterAufPrimzahl(z, 3)

TesteWeiterAufPrimzahl(z, t): z,t → z Mod t <> 0 AND
                                    Wenn t = z/2 
                                    dann true 
                                    sonst TesteWeiterAufPrimzahl(z, t + 1)

Wir setzen die Lösung in C# um:

  public static bool IsPrime(long z)
{
   // Entscheidungen für Sonderfälle wie 1 und 2 werden direkt getroffen
   // Für alle anderen werte wird mittels Rekursion die Probe auf Teilbarkeit 
   // mit allen möglichen Teilern durchgeführt
   return z == 2 || (z != 1) && (z % 2 != 0 && IsNotFactor(z, 3, z/2));
}

private static bool IsNotFactor(long z, long factor, long maxPossibleFactor)
{
   if (factor >= maxPossibleFactor)
      // Fall: alle möglichen Prüfungen auf Teilbarkeit blieben erfolglos
      return true;
   else
      // Fall: eine Prüfung wird durchgeführt und das Prüfergebnis mit
      // den Ergebnissen aus den restlichen noch anstehenden Prüfungen 
      // logisch UND verknüpft.
      return z % factor != 0 && IsNotFactor(z, factor + 2, maxPossibleFactor);
}

Auch für Teilaufgabe 2 gibt es eine funktionale Lösung (Pseudokode):

  AllePrimzahlenIn(a, b): a, b → Alle x in [a, b] für die gilt: IstPrimzahl(x)

Die Funktion bildet dabei das Paar a,b auf eine Menge mit allen Primzahlen zwischen a und b ab. Hier die Implementierung in C#:

/// <summary>
/// Erzeugt eine Liste aller Primzahlen im Intervall [a, b]
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static IEnumerable<long> Scan(long a, long b)
{
   if (a > b)
      return lisp.Fn.L<long>();
   else if (IsPrime(a))
      // Primzahliste besteht aus a und den restlichen Primzahlen zw. [a+1, b]
      return lisp.Fn.Concat(lisp.Fn.L(a), Scan(a + 1, b));
   else
      // Primzahliste besteht aus den restlichen Primzahlen zw. [a+1, b]
      return Scan(a + 1, b);
}