IO und funktionale Programmierung in C#

Zusammenfassung
Das seiteneffektfreie Programmieren ist in der funktionalen Programmierung ein wichtiger Grundsatz, welcher in der imperativen Programmierung (z.B C#) oft vernachlässigt wird obwohl dadurch höhere Nachvollziehbarkeit, Wiederverwendbarkeit und Testbarkeit erreicht werden kann. Im folgenden wird Anhand eines Beispiels gezeigt wie eine Konsolenausgabe seiteneffektfrei realisiert werden kann.

Einleitung
In der funktionalen Programmierung werden Seiteneffekte und Zustände wie der Teufel das Weihwasser gescheut. Leicht passiert es dass durch Seiteneffekte Methoden und Klassen, bei entsprechend ungeeignetem Design, ein nicht deterministisches Verhalten zeigen, was Zuverlässigkeit, Stabilität und Fehleranalyse von Programmen umgemein behindert. IO-Operationen können als Beispiel für Funktionalitäten dienen welche gezwungenermassen Seiteneffekte aufweisen.

string line = System.Console.ReadLine();

Wartet das Programm im Methodenaufruf ReadLine() auf eine Benutzereingabe, so ist nicht sicher ob der Aufruf jemals einen Wert zurückliefert (z.B falls der Benutzer am Bildschirm eingeschlafen ist und somit keine Eingabe macht). Weiter liefert der Aufruf ReadLine() bei jedem Aufruf unter Umständen einen anderen Wert zurück, obwohl aus Sicht des Programmes nichts geändert hat. Dieses Verhalten ist in der imperativen Programmierung (C#) normal, in der funktionalen Programmierung aber verpönnt da in dem darunterliegenden mathematischen Verständnis der Programmierung kein Platz für Nichtdeterminismus und Zufall ist. Auch die Methode System.Console.WriteLine() macht aus mathematischer Sicht wenig Sinn da sie keinen Rückgabewert hat und den Zustand des Programmes nicht verändert.

Beispiel
Wie könnte man nun die Seiteneffekte für folgendes Beispiel beheben?

static void Main(string[] args)
{
    int index = 0;
    var numbers = new int[] { 1, 3, 7, 10 };
    foreach (var number in numbers)
    {
        System.Console.WriteLine("Index {0}: {1}", index++, number);
    }
    System.Console.ReadLine();
}

Lösung

Die Seiteneffekte können zwar nicht ganz eliminiert werden da eine Ausgabe auf die Console nun mal erwünscht ist. Die Idee ist es den Seiteneffekt an eine unkritische Stelle zu verschieben und den Zustand der gewünschten Ausgabe explizit abzubilden (wie dies ein Monad in der funktionalen Programmierung macht).

static void Main(string[] args)
{
    System.Console.Write(
        new int[]{1,3,7,10}
            .Select( (number,index)=> string.Format("Index {0}: {1}{2}", index,number,Environment.NewLine))
                .Aggregate( (lines,line) => lines + line));
    System.Console.ReadLine();
}

Unter Verwendung von LINQ wird mit Select und string.Format() jedes Listenelement in eine Ausgabenzeile projiziert. Danach werden alle Zeilen mit Aggregate und 'lines + line' in einen einzigen String aggregiert welcher am Schluss auf die Konsole ausgegeben werden kann.

Da unsere Funktion nun die Ausgabe explizit abbildet, können wir Tests schreiben und prüfen ob die Ausgabe korrekt ist:

[TestMethod]
public void TestOutput()
{
    string output = new int[]{1,3,7,10}
                    .Select( (number,index)=> string.Format("Index {0}: {1}{2}", index,number,Environment.NewLine))
                        .Aggregate( (lines,line) => lines + line);
    Assert.AreEqual( "Index 0: 1" + Environment.NewLine +
                     "Index 1: 3" + Environment.NewLine +
                     "Index 2: 7" + Environment.NewLine +
                     "Index 3: 10" + Environment.NewLine , output);
}

C# 3.0 vs. Haskell und das 'Countdown-Problem'

In 'Programming in Haskell' wird eine Lösung für das Countdown-Problem in Haskell vorgestellt. Im folgenden wurde diese Lösung in C# 3.0 übersetzt und der Unterschied zwischen Haskell und C# 3.0 analysiert.

Das Countdown Problem
Das Countdown Problem lautet wie folgt: Gegeben seien eine Folge positiver ganzer Zahlen, die Quellzahlen, und eine positive ganze Zahl, die Zielzahl. Gesucht wird ein arithmetischer Ausdruck, in dem jede der Quellzahlen höchstens einmal auftritt und der als Ergebnis die Zielzahl liefert. Als Operatoren können in dem Ausdruck +, -, * und / verwendet werden, wobei jedes Zwischenergebnis ebenfalls eine positive ganze Zahl sein muss. Zum Beispiel löst für die Quellzahlen [1; 3; 7; 10; 25; 50] und die Zielzahl 765 der Ausdruck (1 + 50) * (25 - 10) das Problem. [Referenz: http://www.mathematik.uni-marburg.de/~loogen/Lehre/ws06/Konzepte/Uebungen/u6.pdf]

Unter diesem Link kann die Lösung in C# heruntergeladen werden.
Die C#-Lösung unterscheidet sich zu der Haskell-Lösung vorallem dadurch, dass in C# objektorientierte Konstrukte eingeführt wurden. Nachfolgend eine Auflistung der Haskell-Features welche nur erschwert in C# abgebildet werden konnten

• Rekursive Typen wurden als Klassenhierarchien abgebildet. Folgender Haskell-Code
  

  data Expr = Val Int  App Op Expr Expr
  

  
  wurde in C# zu
  

  public interface IExpression{}
  public struct Value : IExpression
  {
      public Value(int value){}
  }
  public abstract class Operation : IExpression
  {
      protected Operation(IExpression l, IExpression r){}
  }
  public class Add : Operation
  {
      public Add(IExpression l, IExpression r) : base(l, r) { }
  }
  public class Sub : Operation
  {
      public Sub(IExpression l, IExpression r) : base(l, r) { }
  }
  public class Mul : Operation
  {
      public Mul(IExpression l, IExpression r) : base(l, r) { }
  }
  public class Div : Operation
  {
      public Div(IExpression l, IExpression r) : base(l, r) { }
  }
  
  

  
  Während der Haskellausdruck an Produktionsregeln erinneren und somit eine internal DSL bilden, fehlt in C# 3.0 eine solche Möglichkeit. In C# wurde der dieser Ausdruck als ein Expression-Tree abgebildet. Die Anwendung des rekursiven Typs sieht in Haskell wie folgt aus:
  

  evaluate( App Add( Val 2 ) ( Val 3 ))
  

  
  während in C# der Expression-Tree wie folgt instanziert und evaluiert würde:
  

  new Add(new Value(2), new Value(3)).Eval();
  

  
  Das Problem an der objektorientierten Lösung in C# ist, dass in der Anwendung immer Objekte erzeugt werden müssen. Dies verlangt das Schlüsselwort 'new' welches im Gegensatz zum Haskell-Beispiel, den Ausdruck verschleiert. Auch ein FluentInterface bringt in diesem Fall nichts, da damit keine Ausdrücke verschachtelt werden könnten.
  


• Lazy-Evaluation wird für die Lösung des Countdown-Problem benötigt, ansonsten alle Lösungskandidaten am Anfang der Berechnung in den Speicher geladen werden müssten. Lazy-Evaluation ermöglicht die Berechnungsfunktionen so zu kaskadieren, dass nur immer die gerade benötigten Resultat ermittelt werden und dass nicht mehr benötigte Zwischenresultat sofort im Speicher freigegeben werden können.
  Während in Haskell diesbezüglich keine Vorkehrungen nötig sind muss in C# explizit jede Berechnung und Berechnungsschlaufe über IEnumerable erfolgen. Verwendet man LINQ und Extension-Methods so können alle Haskell-Lösungen in die entsprechende LINQ-Lösung übersetzt werden. Aus der Haskell-Funktion
  

  
  solutions :: [Int] -> Int -> [Expr]
  solutions ns n = [e  ns' <- choises ns,
                        e <- exprs ns',
                        evaluate e == [n]]
  

  
  wird in C# 3.0 zu
  

  public static IEnumerable<IExpression> GetSolutions(IEnumerable<int> values, int result)
  {
      return values.Choises().SelectMany(choise => choise.Exprs()).Where( exp => exp.IsValid() && exp.Eval() == result);
  }
  

  
  


• Pattern-Matching ist ein Konstrukt um die Komplexität pro Funktion oder Methode zu reduzieren. Die Haskell-Funktion
  

  perms :: [a] -> [[a]]
  perms []     = [[]]
  perms (x:xs) = concat (map (interleave x)(perms xs))
  

  
  behandelt den Fall der leeren Liste und den Fall der nicht leeren Liste in zwei getrennten Funktionsimplementionen. Da C# Pattern-Matching nicht kennt müssen dort die beiden Fälle in der Methodenimplementation durch eine if-Anweisung explizit behandelt werden:
  

  public static IEnumerable<IEnumerable<int>> Perms(this IEnumerable<int> list)
  {
      if (list.Count() == 0)
      {
          return new int[][] { new int[] { } };
      }
      else
      {
          return list.Skip(1).Perms().SelectMany(subList => subList.Interleave(list.First()));
      }
  }
  

  
  


• Listen sind in Haskell tief in die Sprache eingebettet. Folgendes Beispiel
  

  perms :: [a] -> [[a]]
  perms []     = [[]]
  perms (x:xs) = concat (map (interleave x)(perms xs))
  

  
  ist im starken Kontrast mit C# 3.0:
  

  public static IEnumerable<IEnumerable<int>> Perms(this IEnumerable<int> list)
  {
       if (list.Count() == 0)
       {
           return new int[][] { new int[] { } };
       }
       else
       {
           return list.Skip(1).Perms().SelectMany(subList => subList.Interleave(list.First()));
       }
  }
  

  
  Folgendes kann beobachtet werden:
  - x in Haskell entspricht list.First() in C#
  - xs in Haskell entspricht list.Skip(1) in C#
  
  Listen haben unter C# einen langen Leidensweg hinter sich:
  - .NET 1.0 kennt untypisierten Listen aus System.Collections
  - .NET 2.0 unterstützte typisierte Listen aus System.Collections.Generic
  - ab Visual Studio 2008 wird nun LINQ eingeführt
  
  LINQ ist grossartig doch leider kommt es sehr spät. Eine grosse Erneuerung ist die Erkenntnis dass man anstellen von Listen nun mit IEnumerable's arbeitet. Während Listen (z.B List) in .NET die Eigenschaft der Eager Evaluation haben, wird mit IEnumerable Lazy-Evaluation erreicht (siehe auch oben). Leider muss man sich in Zukunft immer explizit für 'Eager' oder 'Lazy'-Evaluation entscheiden und es wird immer einen konzeptionellen Bruch zwischen den beiden Ansätzen geben. Die Verwendung von IEnumerable (Lazy-Evaluation) ist auf jeden Fall der Verwendung von IList,ICollection usw. (Eager-Evaluation) vorzuziehen.

Zusammenfassung
Mit C# 3.0 lassen sich einige Konzepte aus der funktionalen Programmierung anwenden. Diese Konzepte sind allerdings in einer funktionalen Sprache wie Haskell eleganter umgesetzt. Dagegen steht im Kontrast dass in Haksell objektorientierte Konzepte fehlen, welche vorallem für den Bau von grossen und komplexen Softwaresystemen benötigt werden (z.B Abstrakte Datentypen)

Programming in Haskell (durch die C#-Brille gesehen)

Während des letzten Monats habe ich das Buch 'Programming in Haskell' durchgearbeitet. Es hat mir einen guten Einblick in die Welt der funktionalen Programmierung ermöglicht. Obwohl ich mir nicht die Zeit nahm jedes Beispiel und jede Übung bis ins letzte Detail zu verstehen, habe ich doch einige Konzepte verstanden welche meine Arbeit als Softwareentwickler in Zukunft beeinflussen werden. Folgende Punkte waren für mich neu und haben mich beeindruckt:

Abstraktion auf Ebene von einzelnen Funktionen und Operationen
Folgender C#-Code berechnet die laufende Summe über einen Array von Integers:

 public static int[] GetLaufendeSumme(int[] values)
 {
    int[] summierung = new int[values.Count()];
    int sum = 0;
    for( int i=0; i<values.Count(); i++ )
    {
       sum = values[i] + sum;
       summierung[i] = sum;
    }
    return summierung;
 }

In Haskell habe ich nun mit Hilfe der Funktion foldl folgende Lösung gefunden:

getLaufendeSumme :: [Int]->[Int]
getLaufendeSumme = foldl (
                    \summen wert -> case summen of
                         []        -> [wert]
                         otherwise -> summen++[wert + last summen] ) []

Da foldl das Iterieren und Berechnen von neuen Werten aufgrund der iterierten Werten abstrahiert ist der Haskellcode im Vergleich zum C#-Beispiel ausdruckstärker. foldl ist somit ein Pattern welches in ähnlichen Situation wieder angewendet werden kann. Im Gegensatz zu einer for-Schleife in C# ist mit foldl die Absicht und das Funktionieren des Codes klar.

Lazy Evaluation
Mit Layz Evaluation sorgt der Intepreter dafür, dass ein Ausdruck erst dann ausgewertet wird wenn der Wert des Ausdrucks benötigt wird. Bei Haskell werden alle Ausdrücke standardmässig mit 'Lazy Evaluation' aufgelöst. Nur Dank dieser Technik ist es möglich mit unendlichen Listen zu arbeiten. Im folgenden Bespiel definiert die Funktion fibs alle Fibonacci-Zahlen. Mit der Funktion fibGT kann dann die erste Fibonacci-Zahl, welche grösser als ein bestimmter Wert ist, gefunden werden.

fibs :: [Integer]
fibs = [0,1]++[ a+b  (a,b) <- zip fibs (tail fibs) ]

fibGT :: Integer -> Integer
fibGT n = head (dropWhile (\a->a<n) fibs)

Bei C# werden standardmässig alle Ausdrücke sofort evaluiert und das Arbeiten mit z.B unendlichen Listen ist nur durch die explitzite Verwendung eines Iterators (IEnumerable, IEnumerator, etc.) möglich.

Pattern Matching
'Pattern Matching' hilft dabei, eine Funktion für verschiedene Fälle getrennt zu implementieren. So entscheidet der Haskell-Interpreter aufgrund der Argumente welche Funktionsimplementation für den aktuellen Fall herbeigezogen werden muss. So sind zum Bespiel folgende Funktionsdefinitionen für sumInt und sumInt2 gleichwertig:

sumInt :: [Integer] -> Integer
sumInt (n:ms) = n + sumInt ms
sumInt [] = 0

sumInt2 :: [Integer] -> Integer
sumInt2 ns = if ns == [] then 0
             else (head ns) + sumInt2 (tail ns)

Während in der Funktion sumInt für den Fall '(n:ms)' und den Fall '[]' zwei Implementationen gemacht wurden, wird in der Funktion sumInt2 alles innerhalb einer Implementation mit Hilfe von if-Entscheidungen behandelt.



Induktives Denken
Folgender Haskell-Code berechnet die Fibonacci-Zahlen (0,1,1,2,3,5,8,13,21...)

fibs :: [Integer]
fibs = [0,1]++[ a+b  (a,b) <- zip fibs (tail fibs) ]

Mich fasziniert an dieser Lösung, dass der Code nicht 'imperativ' als Anweisung verstanden werden kann. Der Haskell-Code oben lässt mich folgendes denken:

1. fibs liefert mir alle Fibonacci-Zahlen
2. Die Fibonacci-Zahlen beginnen mit 0 und 1
3. Die weiteren Zahlen berechne ich indem ich die Fibonacci-Reihe mit der um eins verschobenen Fibonacci-Reihe pro Zahl kombinieren und pro Kombination die Zahlen zusammenzähle.

Für mich ist diese Denkweise ungewohnt, da die Definition der Funktion fibs davon ausgeht dass fibs (bereits) die korrekten Fibonacci-Zahlen zurückliefert. Auch hat die Funktion deklarativen Charakter. Es werden nämlich nur die Berechnungsregeln beschrieben. Wie und wann welche Berechnung erfolgt ist nicht ersichtlich.