Expression trees for dummies?

Question

I am the dummy in this scenario.

I've tried to read on Google what these are but I just don't get it. Can someone give me a simple explanation of what they are and why they're useful?

edit: I'm talking about the LINQ feature in .Net.

Answer 1

Is the expression tree that you are refering is Expression Evaluation tree?

If yes then it is tree constructed by the parser. Parser used the Lexer/Tokenizer to identify the Tokens from the program. Parser constructs the Binary tree from the tokens.

Here is the detailed explanation

Answer 2

IIUC, an expression tree is similar to an Abstract Syntax Tree, but an expression usually yiels a single value, whereas an AST can represent an entire program (with classes, packages, function, statements, etc.)

Anyway, for an the expression (2 + 3) * 5, the tree is:

    *
   / \ 
  +   5
 / \
2   3

Evaluate each node recursively (bottom-up) to get the value at the root node, i.e. the value of the expression.

You can of course have unary (negation) or trinary (if-then-else) operators too, and functions (n-ary, i.e. any number of ops) if your expression language allows it.

Evaluating types and doing type-control is done over similar trees.

Answer 3

Expression trees are an in-memory representation of an expression, e.g. an arithmetic or boolean expression. For example, consider the arithmetic expression

a + b*2

Since * has a higher operator precedence than +, the expression tree is built like that:

    [+]
  /    \
 a     [*]
      /   \
     b     2

Having this tree, it can be evaluated for any values of a and b. Additionally, you can transform it into other expression trees, for example to derive the expression.

When you implement an expression tree, I would suggest to create a base class Expression. Derived from that, the class BinaryExpression would be used for all binary expressions, such as + and * . Then you could introduce a VariableReferenceExpression to reference variables (such as a and b), and another class ConstantExpression (for the 2 from the example).

The expression tree is in many cases built as the result of parsing an input (from the user directly, or from a file). For evaluating the expression tree, I would suggest to use the Visitor pattern.

Answer 4

An expression tree is a mechanism to translate executable code into data. Using an expression tree, you can produce a data structure that represents your program.

In C#, you can work with the expression tree produced by lambda expressions by using the Expression<T> class.

---

In a traditional program, you write code like this:

double hypotenuse = Math.Sqrt(a*a + b*b);

This code causes the compiler to generate an assignment, and that's it. In most cases, that's all you care about.

With conventional code, your application can't go retroactively back and look at hypotenuse to determine that it was produced by performing a Math.Sqrt() call; this information is simply not part of what is included.

Now, consider a lambda expression like the following:

Func<int, int, int> hypotenuse = (a, b) => Math.Sqrt(a*a + b*b);

This is a little different than before. Now hypotenuse is actually a reference to a block of executable code. If you call

hypotenuse(3, 4);

you will get the value 5 returned.

We can use expression trees to explore the block of executable code that was produced. Try this instead:

Expression<Func<int, int, int>> addTwoNumbersExpression = (x, y) => x + y;
BinaryExpression body = (BinaryExpression) addTwoNumbersExpression.Body;
Console.WriteLine(body);

This produces:

(x + y)

More advanced techniques and manipulations are possible with expression trees.

Answer 5

Short answer: It's nice to be able to write the same kind of LINQ query and point it at any data source. You couldn't have a "Language Integrated" query without it.

Long answer: As you probably know, when you compile source code, you're transforming it from one language to another. Usually from a high level language (C#) to a lower lever on (IL).

There are basically two ways you can do this:

1. You can translate the code using find and replace
2. You parse the code and get a parse tree.

The latter is what all the programs we know as 'compilers' do.

Once you have a parse tree you can easily translate it into any other language and this is what expression trees allow us to do. Since the code is stored as data you can do anything you want to it but probably you'll just want to translate it into some other language.

Now, in LINQ to SQL the expression trees get turned into a SQL command and then are sent over the wire to the database server. As far as I know they don't do anything really fancy when translating the code but they could. For instance, the query provider could create different SQL code depending on the network conditions.

Answer 6

a better explanation here http://www.jot.fm/issues/issue_2008_03/column4.pdf