Monday, May 9, 2011

Lambdas and expression trees in Delphi

Ever wanted to write something like this in Delphi?

for cust in customers.Where(c => c.CustomerId = 'ALFKI') do ...

Actually in Delphi you have to write it like this.

for cust in customers.Where(
  function(c: TCustomer): Boolean
  begin
    Result := c.CustomerId = 'ALFKI';
  end) do ... 

Ugh, lots of code just to declare the anonymous method. Well, we are used to writing more letters in Delphi so that is not really the problem. Another thing is more interesting: expression trees. What can you do with it? Lots of cool stuff. The most interesting for me at least was the ability to create SQL statements with their help. Above for in loop generates adds a where clause to the select statement when using Linq to SQL in .Net. But Delphi does not have such expression trees for anonymous methods... Until now!

Since I have been working with delphi-coll the first time I was wondering if I can actually use them to create something similar to the ADO Entity Framework. The biggest problem was to translate for in loops like above to proper SQL that only fetched the wanted data from the database instead of doing client side filtering. After looking into how .Net does it was obvious to me. I need some kind of support for lambda expressions or more specific the possibility to create some expression tree that I can use to create my SQL statements. But how to inject some kind of expression into a function (in our case the where function) without writing an anonymous function or at least without writing a super complicated one that only works when using some SQL queryable?

When I googled "Delphi lambda linq" the second hit brought me to the first idea. Basically a combination of records with operator overloading containing interfaces. You can do some funny stuff with them but there is some limitation. As soon as you want to access a property of some object you are lost (like we want to do in our example). So how to make a property or function call without actually calling it. I know that sounds weird but what I want to achieve is to record the complete expression. This brings us to invokable custom variant types. I am not going to explain how they work but if you want to know more you can read some articles about it here and there.

The important thing is: We can have calls to a property or method like in our example (c.CustomerId) without actually calling and getting a return value. Well we get a return value but it will be a variant which encapsulates the expression object for this property or method. So we have the information now but can invoke it later. Let's look at our anonymous method we use for filtering our customer list. It gets one parameter of the type TCustomer and returns a boolean. So how to write our expression now?

for cust in customers.Where(
  TLambda.From<TCustomer, Boolean>(Arg1.Customer = 'ALFKI')) do ...

Oh wow, whats this TLambda and that Arg1?! TLambda is a record with some static methods like From which supports all kinds of TFunc defined in SysUtils (well not all so far but they will get added). This methods creates some anonymous method and returns it.
Arg1 is a function (there are 3 more) to create an expression that takes care of the first parameter of the anonymous method. So in our case the TCustomer object we pass in when we call the method.

So what about that expression tree? We actually can get that out of the method reference. Wait what? Yes, as we know they are just objects hidden behind some interface. Which means: you can get RTTI for them. And getting RTTI means you can extract information and even modify them. TLambda has 2 methods to get and set the expression that is executed inside the method when its called.

So now we can inspect and iterate our expression tree and generate where clauses and other funny things. So if you want to access a parameter of the method just use the ArgX functions. If you want to use variable capturing put them into Arg function so you can use the current value when actually executing the method (just supported for objects so far).
One thing you have to remember is: You cannot use normal functions inside that expression because that results in direct execution. But you can write wrappers for them as shown in one of the samples.

All in all this is a very early prototype but it works pretty well so far in a single threaded application.

To make this work in your program just use System.Lambda (and System.Expressions when you want to create your own expression tree).

You can also see how it works in the 2 new demos (Sample6 and Sample7). For the second sample you need delphi-coll to make it work.

8 comments:

  1. OK, this is sweet. I ran across this article a just a couple weeks ago, and then today I had a problem that could be solved best with expression trees.

    Keep up the good work! :)

    ReplyDelete
  2. I am very curious to know what that was, how you solved it and if you ran into any problems or bugs :)

    ReplyDelete
  3. Kind of a long story. Short version: I've been working on converting the storage for my game engine from flat files to a Firebird embedded database. This lets me load stuff into memory a lot faster, because I can use lazy loading instead of reading in the entire file all at once.

    The downside is, I don't have everything loaded into memory all at once. I used to hold all my data in generic TList containers, ordered by ID. Now I can't do that, so I'm using TDictionary<integer, data object> descendants instead, backed by datasets.

    I had a method on the list class called FirstWhere, which takes an anonymous method and returns the first item that matches the criteria. (See FirstWhere in Alex Ciobanu's Enex; I'm the one who gave him the idea for that method.)

    But you can't exactly do that on a TDictionary, especially one without all the elements populated. And you can't use a normal anonymous method to query the dataset that's backing the dictionary, so I reimplemented FirstWhere as taking a TLambda-style expression, then generating SQL from it to apply to the dataset as a Filter, and it worked.

    ReplyDelete
  4. Nice, so basically what I was planning to do with those expressions. No wonder lambda expressions were basically one of the things they implemented to make LinQ work.

    I wonder if it is possible to create some IDE plugin that fakes code completion for custom variant types because Delphi does not have that type safety on dynamic (i.e custom variant types) types.

    ReplyDelete
  5. Similar stuff :)
    http://www.delphi-forum.de/viewtopic.php?t=103194

    ReplyDelete
  6. Same here, I linked to your original post.

    ReplyDelete
  7. I was looking at this a little bit more. Looks to me like this wouldn't be thread-safe, with the expression stack being a global variable...

    ReplyDelete
  8. That is true. And actually I don't like that global variable thing anyway. I will see if I can solve this in some simple way because this whole thing is more of a proof of concept anyway.

    ReplyDelete