Behind the scences of LINQ

I always knew that LINQ was founded on the idea of monads but even trying hard I couldn't understand how LINQ and monads are related to each other.

But fortunately there is Wes Deyer and he describes in The Marvels of Monads what I always wanted to know. It's a pity that LINQ was always described and documented as query language rather than as a monad extensions. When I look to the msdn-documentation there is no hint that I could implement query operators on other types than IEnumerable and IQueryable.

But that's exactly what Wes is doing. He sees a more general concept and he shows a way to implement the query operators on any type. In fact this is for me a huge step and leads us to a new level of abstraction where LINQ (as a list-monad) seems to be a specific case of a monad.

My preferred way to use LINQ was the method syntax as I thought this is the more general case. But now, after knowing that the query syntax is something like a monad extension I start to like it.

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)

LinqToSql vs. NHibernate

Im folgenden vergleiche ich 'LINQ to SQL' mit NHibernate und Stelle die Unterschiede und Gemeinsamkeiten dieser beiden O/R-Mapper dar.

Sessions
Was in 'LINQ to SQL' der DataContext ist in NHibernate die Session. Beide Implementationen realisieren UnitOfWork und IdentityMap was uns ein sicheres und bequemes Arbeiten mit einem DomainModel ermöglicht.


Transaktionen und Locking
Da beide O/R-Mapper UnitOfWork implementieren, unterstützen uns beide auf ähnliche Weise beim optimistischen Locking. Beide O/R-Mapper halten den für das optimistische Locking nötigen Ursprungszustand der Objekte intern, also im DataContext oder in der Session.

Für das pessimistische Locking ermöglichen beide O/R-Mapper den Zugriff auf die Transaktion auf welcher der Transaktionsbeginn und -ende, sowie der Isolationslevel gesteuert werden kann.


Persistence Ignorance (PI)
Nur NHibernate ermöglicht das Persistieren von beliebigen Objekten. Bei 'LINQ to SQL' (in Orcas Beta1) muss INotifyPropertyChanging und INotifyPropertyChanged implementiert werden. In 'LINQ to SQL' kann wahlweise die Mapping-Information auf der Klasse als Attribute oder in einem externen XML abgelegt werden.

Eliminierung O/R Impedance-Mismatch
Hier zeigt sicher der größte Unterschied zwischen den beiden O/R-Mappern. Folgende nicht abgeschlossene Liste zeigt Features welche NHibernate unterstützt, 'LINQ to SQL' aber nicht:

1. Abfragen berücksichtigen unpersistierte Änderungen
2. Unterstützung mehrerer Abbildungsarten für die Vererbung ( table-per-class / table-per-subclasss / table-per-concrete-class )
3. Mapping von n-m Beziehung

Da 'LINQ to SQL' den Punkt 1. nicht unterstützt müsste zum Beispiel mit Aggregates (Eric Evans: Domain Driven Design) gearbeitet werden. Diese würden die unpersistierten Änderungen in ihrem Aggregate berücksichtigen und verwalten.

Abfragesprache
'LINQ to SQL' ist mit der Abfragesprache LINQ zur Zeit hier im Vorteil. Eine LINQ-Implementation für NHibernate ist aber in Bearbeitung und danach wird es unter diesem Punkte keine nennenswerte Unterschiede geben.


Wartung
Hier sehe ich keine grossen Unterschiede, da das Warten der Mapping-Informationen immer eine mühsame Angelegenheit ist. Mit dem 'LINQ to SQL' -Designer (Beta1) kann sehr schnell eine erste Version eines Mapping-Schemas erstellen werden. Die Wartung und Pflege des Schemas erfolgt danach aber manuell.

Falls jemand schon praktische Erfahrungen in einem grösseren Projekt mit 'LINQ to SQL' hat, würde ich mich über einen Erfahrungsbericht sehr freuen.

So nun muss ich mir noch LINQ To Entities anschauen!