Expression Trees - Please explain! | Tech Off

alexmac

Hi,
I am struggling with the concept of what expression trees are (as related to LINQ).

Does any one have any good links or a good explanation?

Thanks,

Alex

stevo_
Human after all

Its just an expression of "code".. it lets you evaluate what the code is expressing in order to translate it appropriate to what you need.. is there something specific you don't understand? you wouldn't really need to touch expression trees unless you're looking to do a query provider of some kind.

alexmac

In reply to stevo_

#Aug 6th, 2008 @ 11:41 AM

I am working my way through a book on LINQ (linq in action) and just trying to understand what they are and what you would use them for (which might be answered by the 1st question!)

figuerres
???

In reply to alexmac

#Aug 6th, 2008 @ 12:06 PM

you know how to do Algebra Yes?

then you do Expression Trees in your head or on paper when you solve a problem.

that's the very quick way to explain it.

you know, things in "()" happen before ....
and the order of + - * and /

you can take an equation and draw it as a graph of nodes where the node at the end has the result of the problem

simple case

                                             25
                                               |
                                               *
                                            /     \
                                         5          5

or
5*5 = 25

Get it?

if you read a book on how to build a compiler or a parser or an interperted language you will spend months of time on them.
and how they get transformed in to code.

stevo_
Human after all

In reply to figuerres

#Aug 6th, 2008 @ 1:59 PM

The basic concept of it.. is that rather than getting a delegate you can invoke.. you get a much more complicated object that has more than the ability be invoked.. but you can actually traverse through the tree of code, or modify the tree (add edit etc), each element of the tree is like figuerres says.. its a node within the code (ha!).. so you'll see if condition statements and be able to see see what the condition is, and what nodes should happen if its true or false..

Linq to Sql uses this to look at your query expression, and evaluate what they would be if it were sql (at least thats what it tries, its pretty good at it for v1).. linq to xml again is looking at the expression and evaluating that as xpath or whatever it uses..

You don't have to explicitely create expressions either, they mostly get handled for you.. if the lambda is ultimately getting cast to an expression then the compiler will create the lambda as an expression instead of a delegate.

alexmac

In reply to stevo_

#Aug 6th, 2008 @ 2:10 PM

I found this page which helped me understand it better:
http://blogs.msdn.com/charlie/archive/2008/01/31/expression-tree-basics.aspx

So my understanding is an expression tree is a bit like a delegate however it is also a structure which can be modified.

So in figuerres example you could change one of the 5's to a 4 or create a more complex tree by for example saying if the result was more than 20 then subtract 15 etc

You can create Expression trees from scratch to create dynamic queries etc.

stevo_
Human after all

In reply to alexmac

#Aug 7th, 2008 @ 2:20 PM

The expression can compile into a delegate, you'll have an object something like this:

Expression<Func<string>> expr = () => "hello world";
Func<string> func = expr.Compile();

But yes, the basics of it are that you can create, modify, evaluate or compile the expression..

figuerres
???

In reply to alexmac

#Aug 7th, 2008 @ 2:20 PM

Yes, it's all about having a way to store, manage, process, parse and execute an expression of any arbitrary complexity.

in fact a flow-chart is a "kind of" expression tree at a high level / with a lot of abstraction.

in part this is also how compilers can optimize code they generate.

one class of compile opt. is called "CSE" Common Sub Expression, say in 3 or more places in a class the same exact for(; Wink

{} loop is in the code, in different methods but in the same class....
the tree gets built for the whole class and the compiler looks at it and find that in n places the same tree of nodes is found...
then it can pull one out and set it aside and make each of the others point to it and when that goes to code generation it only emits code for one for loop but say 4 places (or however many) each call that loop like a function.

very general / abstract overview of one way you have used this and never saw it under the hood.

another thing that happens to most (but not all) trees is they get transformed from Algebraic expression format to stack oriented format.
a CPU always does it's processing based on a stack, local variables, intermidiate values and returns from subroutines all use a stack with Push and Pop operators.
in old 6502 assembly you might do:
LDA $1234
ADD 100
PUSH A,Y

Load the accumulator with location $1234
add 100 to that value
Push that to the Y register.

stuff like that
for another example a stack version of 5 * 5
Push 5
Push 5
*

the "*" op pops 2 values from the stack and then pushes the result backon the stack.

I used to have to think that way for some stuff I worked on in a language based on SmallTalk
nasty stuff to edit, but if you could wrap your head around it you could see a lot of how things work at a low level.