Seit C# 3.0 gehören Lambda Expressions zum Alltag eines Entwicklers. Im ersten Teil wurden die Grundlagen von Statement Lambdas und Expression Lambdas wiederholt. Etwas weniger bekannt sind Expression Trees. Diesem Defizit will ich durch den folgenden Post entgegenwirken und die Grundlagen von Expression Trees vorstellen.

Lambda Expressions lassen sich in zwei Arten aufteilen. Zum einen die Lambda Statements, die Delegates und anonyme Methoden erzeugen und zum anderen die Expression Lambdas, die Instanzen von System.Linq.Expressions.Expression<T> zurückliefern. Expression Lambdas und die Klasse Expression<T> finden Anwendung bei den Expression Trees.

Expression Tree per Expression Lambda erzeugen

Als Beispiel soll die Geradengleichung y = m * x + b dienen. Hierbei soll die Steigung m als Integer und b als Konstante abgebildet werden. Somit sieht die Formel als Lambda Expression wie folgt aus:

Func<int, double, double> f = (m, x) => m * x + 10;

Die Variable f ist ein Delegate mit dessen Hilfe der Programmcode ausgeführt werden kann.

double y = f(2, 7.5);       // Ausgabe: 25.0

Mit Hilfe der Klasse Expression<T> kann aus dem Lambda Expression recht einfach ein Expression Tree erzeugt werden.

Expression<Func<int, double, double>> expression = (m, x) => m * x + 10;

Wichtig an dieser Stelle ist die Tatsache, dass nur Expression Lambdas und keine Statement Lambdas in Expression Trees umgewandelt werden können. Die folgende Anweisung erzeugt beim Compilieren einen Fehler.

Expression<Func<int, double, double>> expression = (m, x) => { return m * x + 10; };   // Fehler

Die gleiche Lambda Expression wurde mit der Klasse Expression<T> in ein Expression Tree umgewandelt. Mit der Variable expression kann kein Programmcode direkt ausgeführt werden. Die Variable expression ist vielmehr eine Datenstruktur (binärer Baum) in der die Lambda Expression abgebildet wird.

Um den Expression Tree wieder in Programm Code umzuwandeln, wird dieser zur Laufzeit compiliert. Die Methode Compile() liefert einen Delegate zurück, der wie gewohnt eingesetzt werden kann.

Func<int, double, double> f = expression.Compile();
double y = f(2, 7.5);

Oder auch etwas kürzer:

double y = expression.Compile()(2, 7.5);

Somit liefert die Klasse Expression<T> die Möglichkeit, ausführbaren Code in eine Datenstruktur umzuwandeln.

Eingesetzt werden Expression Trees immer dann, wenn der Code vor der Ausführung geändert oder in einem anderen Prozessraum ausgeführt werden soll. Der dort ausgeführte Programmcode ist nicht zwangsläufig IL Code. So wird bei LINQ to SQL eine Lambda Expression in ein Expression Tree umgewandelt. Dieser wird zum SQL-Server übertragen, dort in SQL umgewandelt und ausgeführt.

Expression Tree in Visual Studio analysieren

Visual Studio bietet Unterstützung bei der Analyse von Expression Trees. So liefert die Klasse Expression<T> über die Eigenschaft DebugName einen String zurück, der in einer Art Metasprache den Ausdruck näher beschreibt.

Mit dem Text Visualizer von Visual Studio kann der String formatiert angezeigt werden.

Im MSDN werden unter Debugging Expression Trees die einzelnen Elemente genauer beschrieben. In Expression Trees, in denen Elemente wie Schleifen, Sprünge oder Methodenaufrufe enthalten sind, ist diese Art der Darstellung sehr hilfreich. Weiter unten werde ich entsprechende Beispiele zeigen.

Nach einigem Suchen im Internet bin ich auf einen speziellen Expression Tree Visualizer gestoßen. Es handelt sich hierbei um ein C# Beispiel, das mit Visual Studio 2008 ausgeliefert wurde. Scheinbar ist dieses Beispiel bei Visual Studio 2010 nicht mehr enthalten. Auch konnte ich die DLL nicht direkt mit Visual Studio 2010 einsetzen. Sacha Barber stellt in seinem Blog eine angepasste Variante für Visual Studio 2010 zur Verfügung. Genauere Infos findet ihr in seinem Post Expression Tree Visualizer. Die Sourcen habe ich ebenfalls hier abgelegt:

ExpressionTreeVisualizer.zip (Visual Studio 2010) auf GitHub

Die erzeugte DLL muss in das Verzeichnis C:\Users\<Name>\My Documents\Visual Studio 2010\Visualizers kopiert werden. Anschließend wird im Debugger von Visual Studio für den Datentyp Expression<T> der Expression Tree Visualizer angeboten.

Diese Darstellung entspricht schon mehr meinen Vorstellungen. Der Aufbau des Expression Trees wird als Baum dargestellt. Die Eigenschaften der einzelnen Knoten werden in einer leicht verständlichen Darstellung beschrieben.

Mit dem Expression Tree Visualizer wird einem ein Hilfsmittel an die Hand gegeben, mit dem man sich schnell und einfach einen Überblick über den Aufbau eines Expression Trees verschaffen kann.

Es besteht natürlich auch die Möglichkeit, den Aufbau eines Expression Trees per Hand auszugeben.

Expression<Func<int, double, double>> expression = (m, x) => m * x + 10;
double y = expression.Compile()(2, 7.5);

Console.WriteLine("Body: {0}", expression.Body);
Console.WriteLine("NodeType: {0}", expression.NodeType);
Console.WriteLine("Type: {0}", expression.Type);
Console.WriteLine("ReturnType: {0}", expression.ReturnType);
Console.WriteLine("Parameters:");
foreach (ParameterExpression param in expression.Parameters)
    Console.WriteLine("Parameter '{0}' Typ: {1}", param.Name, param.Type);
Console.WriteLine("-");

Die resultierende Konsolenausgabe des Beispiels:

Die Klassen Expression und Expression<T>

Da beide Klassen eine zentrale Rolle bei den Expression Trees haben, wollen wir uns diese etwas genauer anschauen.

Wie zu erkennen ist, erbt die Klasse Expression<T> von LambdaExpression und diese von der Klasse Expression. Die Klasse Expression spielt später beim Erzeugen eines Expression Trees noch eine wichtige Rolle. Die Klasse Expression hat einige Eigenschaften, die wiederum andere Expressions enthalten. Diese führt zu einer baumartigen Struktur. Es gibt keine (bis auf eine Ausnahme) Collections. So ist es recht einfach durch die Struktur zu navigieren.

Die wichtigsten Eigenschaften erbt Expression<T> von der Klasse Expression:

Eigenschaft	Bedeutung
Body	Ist von Typ Expression und liefert den eigentlichen Ausdruck zurück. Über diese Eigenschaft kann tiefer in den Expression Tree ‘eingetaucht’ werden.
Parameters	Die Eigenschaft Parameters enthält eine Auflistung vom Typ ReadOnlyCollection<ParameterExpression>. In dieser sind alle Parameter enthalten, die an den Ausdruck übergeben werden. Bei dem obigen Beispiel sind das die Variablen m und x.
NodeType	NodeType ist vom Typ ExpressionType. ExpressionType ist eine Aufzählung mit ca. 50 Elementen und beschreibt die Eigenschaft Body genauer. Für das Root-Element des Expression Trees ist der Wert i.d.R. ExpressionType.Lambda.
Type	Während NodeType den Typ eines Elements im Expression Tree beschreibt, z. B. den Typ eines Operators, so liefert Type den CLR-Typ zurück. Für das obige Beispiel ist das Root-Element der Delegate Func<Int32, Double, Double>. Für einzelne Parameter könnte diese Variable aber auch Double oder Int32 zurückliefern.

Jeder mögliche Knoten innerhalb eines Expression Trees wird durch die Klasse Expression, bzw. einer der Ableitungen, abgebildet. So gibt es z. B. eine Klasse, die einen Parameter repräsentiert oder einen binären Operator. Hier eine Übersicht der Klassen, die für unser Beispiel von Bedeutung sind:

Klasse	Bedeutung
ConstantExpression	Eine Konstante wird durch die Klasse ConstantExpression abgebildet. Die Eigenschaft NodeType hat in diesem Fall den Wert ExpressionType.Constant. Der eigentliche Wert ist in Value abgespeichert (vom Typ Object). Der genaue CLR-Datentyp kann durch die Eigenschaft Type ermittelt werden.
ParameterExpression	Jeder Parameter, der an den Expression Tree übergeben wird, wird durch ein Objekt der Klasse ParameterExpression näher spezifiziert. Damit ist nicht der Wert gemeint, sondern in erster Linie der Name und der Datentyp.
UnaryExpression	Operatoren mit einem Operanden, z. B. der Inkrementoperator (++) oder explizites Konvertieren, werden als unäre Operatoren bezeichnet und durch die Klasse UnaryExpression abgebildet.
BinaryExpression	Operatoren mit zwei Operanden, z. B. arithmetische Operatoren (+, -, *, /), werden als binäre Operatoren bezeichnet. Deshalb hat die Klasse BinaryExpression je eine Eigenschaft für den linken und den rechten Operanden.
MethodCallExpression	Methodenaufrufe werden in einem Expression Tree durch die Klasse MethodCallExpression dargestellt.

Unser Beispiel von Oben

Expression<Func<int, double, double>> expression = (m, x) => m * x + 10;

hat als Expression Tree folgende vereinfachte Struktur:

Wie zu erkennen ist, hat die Klasse Expression<T> eine Eigenschaft mit dem Namen body. Diese hält die Top Level Expression des Expression Trees. In meinem Beispiel ist dieses die Expression BinaryExpression. Bei dieser hat die Eigenschaft NodeType den Wert Add. Die Klasse BinaryExpression hat, wie bei einer Addition üblich, zwei Operanden, einen Linken und einen Rechten. Der rechte Operand enthält die Konstante 10.0, der linke eine Multiplikation mit den Parametern x und m. Parameter werden durch ParameterExpression bekanntgegeben. Der Parameter m muss vor der Multiplikation noch von Int32 in Double konvertiert werden. Hierzu dient die Klasse UnaryExpression mit NodeType = Convert.

Expression Tree per Expression API erzeugen

Der Ursprung eines Expression Trees muss nicht immer eine Lambda Expression sein. Ein Expression Tree kann auch mittels der Expression API zur Laufzeit komplett erzeugt werden. So könnte z.B. ein Formel-Parser realisiert werden. Aus einem String werden die Operanden und Operatoren ausgelesen und daraus ein Expression Tree erzeugt. Dieser wird zum Abschluss compiliert und aufgerufen.

Hierzu bietet die Klasse Expression einige Hundert von Fabrikmethoden an. Jede dieser Methoden dient zur Erzeugung eines bestimmten Knotentyps. Hier ein kleiner Ausschnitt:

Methode	Erzeugter Knotentyp
Expression.Add() Expression.Subtract() Expression.Multiply() Expression.Divide()	System.Linq.Expressions.BinaryExpression
Expression.Convert() Expression.Increment() Expression.Decrement()	System.Linq.Expressions.UnaryExpression
Expression.Constant()	System.Linq.Expressions.ConstantExpression
Expression.Parameter()	System.Linq.Expressions.ParameterExpression
Expression.Lambda()	System.Linq.Expressions.LambdaExpression

einfaches Beispiel

Das folgende Beispiel erzeugt den oben dargestellten Expression Tree (m, x) => m * x + 10 per Expression API:

ParameterExpression paraM = Expression.Parameter(typeof(int), "m");
ParameterExpression paraX = Expression.Parameter(typeof(double), "x");
ConstantExpression const10 = Expression.Constant(10.0, typeof(double));

UnaryExpression paraMDouble = Expression.Convert(paraM, typeof(double));
BinaryExpression multiply = Expression.Multiply(paraMDouble, paraX);
BinaryExpression add = Expression.Add(multiply, const10);

Expression<Func<int, double, double>> expression =
            Expression.Lambda<Func<int, double, double>>(add, paraM, paraX);
double y = expression.Compile()(2, 7.5);

// oder wer es etwas dynamischer mag
var expressionDynamic = Expression.Lambda(add, paraM, paraX).Compile();
var y = expressionDynamic.DynamicInvoke(2, 7.5);

Ich denke, dass das Programm selbsterklärend ist. Zuerst werden die Parameter und die Konstante angelegt. Anschließend werden der Reihe nach die einzelnen Operatoren ausgeführt und zum Schluss wird mit der Methode Lambda() die Expression Lambda erzeugt. Durch die Klasse Expression<T> wird aus der Expression Lambda ein Expression Tree. Mit der Methode Compile() wird dieser in ausführbaren Code umgewandelt.

Das Erstellen von Expression Trees per Expression API geht weit über die Möglichkeiten der Expression Lambdas hinaus. So gibt es Fabrikmethoden für Sprünge, Methodenaufrufe oder bedingte Abfragen. Hiermit lassen sich auch komplexe Algorithmen umsetzen, die mit Expression Lambdas nicht abgebildet werden können.

Methodenaufrufe und bedingte Abfragen

Das folgende Beispiel erzeugt ein Expression Tree, mit einem Methodenaufruf und einer bedingten Abfrage. Eine Variable vom Typ Int32 wird an die Routine übergeben. Je nachdem ob diese Variable positiv oder negativ ist, werden unterschiedliche Meldungen auf die Console ausgegeben.

ParameterExpression number = Expression.Variable(typeof(int));
System.Reflection.MethodInfo methodInfo =
    typeof(Console).GetMethod("WriteLine", new Type[] { typeof(string) });

BinaryExpression ifCondition =
    Expression.LessThan(number, Expression.Constant(0));
MethodCallExpression ifTrue =
    Expression.Call(methodInfo, Expression.Constant("< 0"));
MethodCallExpression ifFalse =
    Expression.Call(methodInfo, Expression.Constant(">= 0"));
ConditionalExpression conditional =
    Expression.IfThenElse(ifCondition, ifTrue, ifFalse);

Expression<Action<int>> expression =
    Expression.Lambda<Action<int>>(conditional, number);
expression.Compile()(9);

Bei der Analyse ist die Eigenschaft DebugView der Klasse Expression<T> sehr hilfreich. Gut zu erkennen sind die If-Abfrage und die Aufrufe der Methode Console.WriteLine().

Schleifen

Die Aufgabenstellung ist recht einfach: Eine Schleife soll ein Array durchlaufen und für jedes Element eine Expression Lambda aufrufen. Somit behandelt das folgende Beispiel eigentlich zwei Themen. Zum einen Schleifen, zum anderen aber auch das Injizieren von Expression Lambdas in einen Expression Tree.

ParameterExpression paraFrom =
    Expression.Parameter(typeof(int), "paraFrom");
ParameterExpression paraTo =
    Expression.Parameter(typeof(int), "paraTo");
ParameterExpression paraBodyAction =
    Expression.Parameter(typeof(Expression<Action<int>>), "paraBodyAction");

ParameterExpression fromExpression =
    Expression.Variable(typeof(int), "fromExpression");
ParameterExpression toExpression =
    Expression.Variable(typeof(int), "toExpression");

LabelTarget breakLabel =
    Expression.Label("breakLabel");

ConditionalExpression ifThenElseExpression =
    Expression.IfThenElse(Expression.LessThan(fromExpression, toExpression),
                          Expression.Block
                              (
                              Expression.Invoke(paraBodyAction, fromExpression),
                              Expression.PostIncrementAssign(fromExpression)
                              ),
                          Expression.Break(breakLabel));

Expression body =
    Expression.Block(new ParameterExpression[] { fromExpression, toExpression },
                     Expression.Assign(fromExpression, paraFrom),
                     Expression.Assign(toExpression, paraTo),
                     Expression.Loop(ifThenElseExpression, breakLabel));

Expression<Action<int, int, Expression<Action<int>>>> expression =
    Expression.Lambda<Action<int, int, Expression<Action<int>>>>(body,
                                            paraFrom, paraTo, paraBodyAction);

int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
expression.Compile()(1, 10, n => Console.WriteLine(numbers[n]));

For-Schleifen werden von Expression Trees nicht direkt unterstützt. Es gibt aber die Klasse LoopExpression. Diese wird mit der Fabrikmethode Expression.Loop() angelegt (Zeile 29). Der erste Parameter legt die Expression fest, die sich innerhalb der Schleife befindet, während der zweite Parameter eine Marke angibt, zu der gesprungen wird, sobald die Methode Expression.Break() aufgerufen wird.

Innerhalb der Schleife wird mit einer If-Abfrage verglichen, ob die Variable fromExpression kleiner ist als toExpression. Ist dieses der Fall, wird mit Expression.Invoke() die übergebene Expression Lambda aufgerufen. Anschließend wird die Variable fromExpression inkrementiert. Ist die Variable fromExpression größer/gleich als toExpression, so wird die Marke breakLabel angesprungen (Zeile 16 – 23).

In den Zeilen 1 – 14 werden die notwendigen Variablen, Parameter und Sprungmarken angelegt.

Das endgültige Zusammenbauen des Expression Trees geschieht in den Zeilen 31 – 33. Zugegeben, auf den ersten Blick recht verwirrend.

Für etwas mehr Transparenz sorgt auch hier die Eigenschaft DebugView. Die Struktur des Programms ist sehr deutlich zu erkennen.

IQueryable und IEnumerable<T>

LINQ to SQL

Ausgangspunkt ist folgende LINQ to SQL Abfrage:

var query = from c in db.Customers
            where c.City == "Nantes"
            select new { c.City, c.CompanyName };

Die Variable query, die zurückgeliefert wird, ist vom Datentyp IQueryable. IQueryable hat folgenden Aufbau:

public interface IQueryable : IEnumerable
{
  Type ElementType { get; }
  Expression Expression { get; }
  IQueryProvider Provider { get; }
}

IQueryable enthält eine Eigenschaft vom Typ Expression. Wie weiter oben schon gezeigt, erbt Expression<T> von Expression. In dieser Eigenschaft wird ein Expression Tree abgespeichert, der die LINQ to SQL Abfrage als Datenstruktur abbildet. Diese Datenstruktur wird an den SQL-Provider weitergegeben und dort in ausführbaren Code umgewandelt.

LINQ to Object

LINQ to Object Abfragen liefern Variablen von IEnumberable<T> zurück.

List<int> list = new List<int>() { 1, 2, 3, 4, 5 };

var query = from number in list
            where number < 5
            select number;

Die Schnittstelle IEnumberable<T> hat nur die Methode GetEnumerator():

public interface IEnumerable<T> : IEnumerable
{
   IEnumerator<T> GetEnumerator();
}

Bei LINQ to Object sind Expression Trees nicht notwendig. Die Abfrage kann direkt in IL umgewandelt werden. Ein Transformieren in Expression Trees, um das Übertragen in einen anderen Prozess zu ermöglichen, wird nicht benötigt.

Abfragen, die IEnumerable<T> zurückliefern, benötigen keine Expression Trees. Muss die Abfrage in einen anderen Prozess übertragen werden, so kommen Expression Trees zum Einsatz und ebenfalls die Schnittstelle IQueryable.