LINQ与DLR的Expression tree（5）：用lambda表达式表示常见控制结构

（Disclaimer：如果需要转载请先与我联系
作者：RednaxelaFX at rednaxelafx.iteye.com）

系列文章：
LINQ与DLR的Expression tree（1）：简介LINQ与Expression tree
LINQ与DLR的Expression tree（2）：简介DLR
LINQ与DLR的Expression tree（3）：LINQ与DLR及另外两个库的AST对比
LINQ与DLR的Expression tree（4）：创建静态类型的LINQ表达式树节点
LINQ与DLR的Expression tree（5）：用lambda表达式表示常见控制结构


LINQ Expression tree能直接表示的语法结构在上一篇中已经详细的列了出来，包括算术、按位、逻辑等运算符的表达式、条件表达式、方法调用表达式、对象创建表达式等。要表示一般的命令式程序，需要支持3中基本控制流语法结构：顺序、分支、循环。在C#中这三种结构能很自然的用语句来表示，但有语句的lambda表达式无法用LINQ Expression tree表示。下面就让我们来看看这三种结构如何转换成只用表达式的方式来表示。

需要事先说明三点：
1、只要避免使用赋值相关的表达式，一个只包含表达式的lambda表达式既可以转换为委托也可以转换为Expression tree；手工创建Expression tree比较麻烦，本文的例子无特别说明都将通过转换为委托的lambda表达式来表示，转换为Expression tree的版本留待后续文章再详细给出。
2、能够用Expression tree表示的东西不一定能被所有LINQ provider接受。这点必须注意。也就是说即使能把一个语句块变成一个表达式，也未必能用在LINQ to SQL等场景里。
3、下面演示的转换方式绝对不代表任何best practice；.NET中方法调用的开销是不可忽视的，因而转换后的表达式肯定会比原本的语句慢。本文只是着重说明转换的可能性。

局部变量的模拟

局部变量，顾名思义，在方法外是看不到的；方法调用结束后局部变量也就随即消失（如果不涉及闭包）。它们的作用主要是保存一些中间的计算结果，将很长的表达式分割成一些比较短的表达式，使得程序代码更为清晰。一般在C#中使用局部变量需要声明语句和赋值表达式，而这两种结构LINQ Expression tree都无法支持。怎么办呢？

许多情况下可以把局部变量去掉，把短表达式拼接回到长的表达式，避免使用语句。一个简单的例子：

( int x, int y ) => {
    var strX = x.ToString( "X" );
    var strY = y.ToString( "x" );
    Console.WriteLine( "x = {0}, y = {1}", strX, strY );
}

可以很顺利的变成：

( int x, int y ) =>
    Console.WriteLine( "x = {0}, y = {1}", x.ToString( "X" ), y.ToString( "x" ) )

但这是不是唯一的选择呢？或许计算某个中间结果的开销很大，而后面的计算中要多次用到它；或许计算某个中间结果会对产生副作用，而我们只希望副作用发生一次；有许多情况下我们还是需要局部变量的。怎么办呢？

注意到，LINQ Expression tree虽然不支持声明局部变量，却允许声明和调用嵌套的lambda表达式。将中间的计算结果以参数的形式传给一个嵌套的lambda表达式，也就等同于使用了局部变量。例子：

( ) => {
    var input = Console.ReadLine( );
    var lowerCase = input.ToLower( );
    var upperCase = input.ToUpper( );
    Console.WriteLine( "lower case: {0}\nupper case: {1}", lowerCase, upperCase );
}

变成：

( ) => ( ( Action<string> ) ( s =>
        Console.WriteLine( "lower case: {0}\nupper case: {1}",
            s.ToLower( ), s.ToUpper( ) )
    ) )( Console.ReadLine( ) )

注意到Console.ReadLine()是有副作用的，这个方法调用会消耗掉输入流里的一行，显然我们不希望调用它两次。
将语句转换为表达式之后，原本写在前面的语句变成写在后面的表达式了，不习惯的话看起来或许很不自然，但注意到C#采用了严格求值，要先把参数的值求出来之后才执行方法调用，所以转换后的写法的执行顺序与转换前是一致的。
例子中的强制类型转换（(Action<string>)）是必要的，编译器需要它才知道该生成委托还是Expression tree。实际上只要最外层的lambda表达式是赋值给Expression<TDelegate>类型的变量，整个lambda表达式（包括内层嵌套的）都会生成为Expression tree，像这样：

Expression<Action> expr = ( ) => ( ( Action<string> ) ( s =>
    Console.WriteLine( "lower case: {0}\nupper case: {1}",
        s.ToLower( ), s.ToUpper( ) )
) )( Console.ReadLine( ) );

会由编译器生成为：

var s = Expression.Parameter( typeof( string ), "s" );
Expression<Action> expr = Expression.Lambda<Action>(
    Expression.Invoke(
        Expression.Convert(
            Expression.Lambda<Action<string>>(
                Expression.Call(
                    null,
                    typeof( Console ).GetMethod(
                        "WriteLine",
                        new Type[ ] {
                            typeof( string ),
                            typeof( object ),
                            typeof( object )
                        }
                    ),
                    new Expression[ ] {
                        Expression.Constant(
                            "lower case: {0}\nupper case: {1}",
                            typeof( string )
                        ),
                        Expression.Call(
                            s,
                            typeof( string ).GetMethod( "ToLower", Type.EmptyTypes ),
                            new Expression[ 0 ]
                        ),
                        Expression.Call(
                            s,
                            typeof( string ).GetMethod( "ToUpper", Type.EmptyTypes ),
                            new Expression[ 0 ]
                        )
                    }
                ),
                new [ ] { s }
            ),
            typeof( Action<string> )
        ),
        new Expression[] {
            Expression.Call(
                null,
                typeof( Console ).GetMethod( "ReadLine", Type.EmptyTypes ),
                new Expression[ 0 ]
            )
        }
    ),
    new ParameterExpression[ 0 ]
);

注意到里面嵌套的lambda表达式也被编译为Expression tree而不是一个委托。如果手工创建这棵Expression tree则可以省去类型转换的那步，也就是等同于将上述代码的第4、35、36这三行注释掉，因为那个类型转换本身并没有意义，只是为了让编译器得到足够的类型信息来转换lambda表达式而已。

顺序结构的模拟

语句与表达式最大的区别就是前者一般没有值或忽略值，而后者一定有值。因而语句只能通过分隔符一个个按顺序写，而不能像表达式可以用运算符结合起来或作为参数传递。在用表达式模拟顺序结构时，最大的障碍就是返回值类型为void的方法——它们不返回任何值，无法放在表达式里与表达式的其它部分组合起来。如果能有办法把void变成null也好……所谓“遇到问题的时候只要增加一个间接层就能解决”

而.NET就提供了这么一种办法。所有委托的基类，Delegate类上有一个DynamicInvoke()方法，参数类型是params object[]，返回值类型是object，正好满足我们的需要。于是像Console.WriteLine()这种返回void的方法，可以包装为一个lambda表达式，然后用DynamicInvoke()包装起来：

( ( Action ) ( ( ) => Console.WriteLine( ) ) ).DynamicInvoke( )

这样的调用将总是返回null，因为Action系的委托忽略返回值，而Delegate.DynamicInvoke()对返回值类型为void的委托类型总是返回null。这样就有机会用到C#里方便的??运算符把语句变成表达式串起来了——??运算符是一个具有短路求值性质的运算符，语义是：当左操作数不为null时值为左操作数的值，否则为右操作数的值。举例来说，把这两个语句：

Console.WriteLine( "1" );
Console.WriteLine( "2" );

变成：

( ( Action ) ( ( ) => Console.WriteLine( "1" ) ) ).DynamicInvoke( ) ??
( ( Action ) ( ( ) => Console.WriteLine( "2" ) ) ).DynamicInvoke( )

把这种转换方式应用在lambda表达式里，就可以把这个带有语句块的lambda表达式：

( ) => {
    var s = Console.ReadLine( );
    Console.WriteLine( s.ToLower( ) );
    Console.WriteLine( s.ToUpper( ) );
}

（注意这里的s是一个局部变量）
变成一个只有表达式的lambda表达式：

( ) =>
    ( ( Func<string, object> ) ( s => (
        ( ( Action ) ( ( ) => Console.WriteLine( s.ToLower( ) ) ) ).DynamicInvoke( ) ??
        ( ( Action ) ( ( ) => Console.WriteLine( s.ToUpper( ) ) ) ).DynamicInvoke( ) )
    ) )( Console.ReadLine( ) )

这个lambda表达式就能够被LINQ Expression tree所表示了。
留意一下这个例子里的s，在最内层的lambda表达式里是不是参数也不是局部变量，而是自由变量，体现了C#的lambda表达式具有闭包的功能。如果没有闭包的功能，s就得出现在每个最内层lambda表达式的参数表里，那就麻烦了。
把这里闭包的实现简单的说明一下。微软的C# 3.0编译器在遇到使用了自由变量的lambda表达式时，会根据赋值目标是委托还是Expression<TDelegate>来决定如何处理这些自由变量。当赋值目标是委托时，被用到的自由变量会被“提升”（lift）为一个编译器生成的匿名类的成员变量，而lambda表达式则对应提升为那个类的成员方法。当赋值目标是Expression<TDelegate>时，C# 3.0编译器并不会做什么特别的处理，就照样把Expression tree生成出来；但在调用Expression<TDelegate>.Compile()时，负责编译expression tree的内部编译器会检查是否存在自由变量，存在的话同样会将自由变量“提升”；不过实现细节与C# 3.0编译器的不同，可以看到带有自由变量的expression tree编译出来的委托的参数列表会比原本指定的TDelegate多了一个参数，ExecutionScope（.NET Framework 3.5: System.Runtime.CompilerServices）或者CompilerScope（.NET Framework 4.0）。对此有兴趣的，可以到DLR的官网下载一份DLR的源码来阅读，里面的Microsoft.Scripting.Core里就有LambdaCompiler的实现，也就是将会用在.NET Framework 4.0里的实现。

分支结构的模拟

最基本的分支结构是if-else语句，对应的有?:运算符表示的条件表达式。这两者看似能直接对应，但语句与表达式的区别再次体现了出来：语句没有或忽略值，而表达式必须有值。因而，if语句可以没有else子句，也不关心返回值的问题；但条件表达式必须同时有true和false的分支，且两个分支的值的类型必须匹配。举例来说：

static int Abs( int x ) {
    if ( 0 > x ) return -x;
    else return x;
}

很容易变为表达式：

( int x ) => ( 0 > x ) ? -x : x

但这个函数就无法直接表示为表达式了：

static void PrintIfEven( int x ) {
    if ( 0 == x % 2 ) Console.WriteLine( x );
}

要转换，就需要应用到上一节提到的包装技巧：

( int x ) => ( 0 == x % 2 ) ?
    ( ( Action ) ( ( ) => Console.WriteLine( x ) ) ).DynamicInvoke( ) :
    null

再次注意到闭包的应用：最内层的lambda表达式使用了自由变量x。

switch语句可以看作是if-else串起来，转换为表达式的话，串联使用条件表达式就行，有需要的时候加上包装。例如：

static string Grade( int point ) {
    switch ( point / 10 ) {
    case 10:
    case 9:
        return "A";
    case 8:
        return "B";
    case 7:
        return "C";
    case 6:
        return "D";
    default:
        return "F";
    }
}

简单的变成：

( int point ) => ( ( Func<int, string> ) ( i =>
    ( 9 == i || 10 == i ) ? "A" :
    ( 8 == i ) ? "B" :
    ( 7 == i ) ? "C" :
    ( 6 == i ) ? "D" :
    /* else */   "F"

循环结构的模拟

用命令式语言的思维方式，循环语句无法转换为表达式。但我们可以一步步来寻找突破口。
首先找出循环本质上需要怎样的支持。有两点：1、需要有终止条件；2、需要能够在一轮循环结束后让控制流跳转回到循环体的开始处。另外，大多循环还需要用到循环变量，要能够更新循环变量的值。
假如不能使用局部变量来做循环变量，回想到本文开头提到的转换局部变量的方法，可以把循环变量放在参数里，把循环体变成一个函数。这样，循环就变成递归的形式了，这也正好解决了控制流跳转的问题。事实上在函数式语言里，迭代（iteration）就是用这样的递归来实现的。或者，从计算模型理论来说，循环不过是递归的一种语法糖而已；从函数的角度来看，递归才是本质性的概念。
于是，如何把循环语句转换为表达式的问题就变成了如何用lambda表达式表示递归函数的问题。问题是，lambda表达式没有名字——它就是匿名函数。没有名字的话，如何递归呢？肯定会有人想到这种做法：

Func<int, int> factorial = null;
factorial = x => ( 0 == x ) ? 1 : x * factorial( x - 1 );

在C#里这是可行的，但不彻底。这里我们要用的办法，是通过找到一个函数的不动点（fix-point）来实现lambda表达式的递归。具体的原理留待以后的文章再详细讨论，这里先给出结果来满足一下眼球。通过这样一个辅助类：

delegate T SelfApplicable<T>( SelfApplicable<T> func );

public static class Functional<T, TR> {
    private static readonly
        SelfApplicable<Func<Func<Func<T, TR>, Func<T, TR>>, Func<T, TR>>> _yCombinator =
            y => f => x => f( y( y )( f ) )( x );
    private static readonly
        Func<Func<Func<T, TR>, Func<T, TR>>, Func<T, TR>> _fixPointGenerator =
            _yCombinator( _yCombinator );

    public static Func<Func<Func<T, TR>, Func<T, TR>>, Func<T, TR>> Fix {
        get { return _fixPointGenerator; }
    }
}

我们可以做到这种效果：

Func<int, int> factorial = Functional<int, int>.Fix(
    fac => x => ( 0 == x ) ? 1 : x * fac( x - 1) );
factorial( 5 ); // 120

注意到这种做法只用了lambda表达式，所以也可以转换为使用Expression tree来完成整个过程。把上述辅助类里有效的内容提取出来，我们来看看只用Expression tree实现的版本：

using System;
using System.Linq.Expressions;

static class TestRecursiveExpressionTree {
    static void Main( string[ ] args ) {
        ExpressionTreeTest( 5 ); // prints 120
        LambdaTest( 4 );         // prints 24
    }

    delegate T SelfApplicableExpr<T>( Expression<SelfApplicableExpr<T>> self );

    static void ExpressionTreeTest( int num ) {
        // parameters
        var y = Expression.Parameter(
            typeof(
                Expression<SelfApplicableExpr<
                    Expression<Func<
                        Expression<Func<
                            Expression<Func<int, int>>,
                            Expression<Func<int, int>>
                        >>,
                        Expression<Func<int, int>>
                    >>
                >>
            ),
            "y"
        );
        var f = Expression.Parameter(
            typeof(
                Expression<Func<
                    Expression<Func<int, int>>,
                    Expression<Func<int, int>>
                >>
            ),
            "f"
        );
        var x = Expression.Parameter( typeof( int ), "x" );
        var fac = Expression.Parameter( typeof( Expression<Func<int, int>> ), "fac" );

        // Y Combinator
        var Y = Expression.Lambda<SelfApplicableExpr<
            Expression<Func<
                Expression<Func<
                    Expression<Func<int, int>>,
                    Expression<Func<int, int>>
                >>,
                Expression<Func<int, int>>
            >>
        >>(
            Expression.Quote(
                Expression.Lambda<
                    Func<
                        Expression<Func<
                            Expression<Func<int, int>>,
                            Expression<Func<int, int>>
                        >>,
                        Expression<Func<int, int>>
                    >
                >(
                    Expression.Quote(
                        Expression.Lambda<Func<int, int>>(
                            Expression.Invoke(
                                Expression.Call(
                                    Expression.Invoke(
                                        Expression.Call(
                                            f,
                                            typeof(
                                                Expression<Func<
                                                    Expression<Func<int, int>>,
                                                    Expression<Func<int, int>>
                                                >>
                                            ).GetMethod( "Compile" ),
                                            new Expression[ ] { }
                                        ),
                                        new Expression[ ] {
                                            Expression.Invoke(
                                                Expression.Call(
                                                    Expression.Invoke(
                                                        Expression.Call(
                                                            y,
                                                            typeof(
                                                                Expression<SelfApplicableExpr<
                                                                    Expression<Func<
                                                                        Expression<Func<
                                                                            Expression<Func<int, int>>,
                                                                            Expression<Func<int, int>>
                                                                        >>,
                                                                        Expression<Func<int, int>>
                                                                    >>
                                                                >>
                                                            ).GetMethod( "Compile" ),
                                                            new Expression[ ] { }
                                                        ),
                                                        new Expression[ ] { y }
                                                    ),
                                                    typeof(
                                                        Expression<Func<
                                                            Expression<Func<
                                                                Expression<Func<int, int>>,
                                                                Expression<Func<int, int>>
                                                            >>,
                                                            Expression<Func<int, int>>
                                                        >>
                                                    ).GetMethod( "Compile" ),
                                                    new Expression[ ] { }
                                                ),
                                                new Expression[ ] { f }
                                            )
                                        }
                                    ),
                                    typeof(
                                        Expression<Func<int, int>>
                                    ).GetMethod( "Compile" ),
                                    new Expression[ ] { }
                                ),
                                new Expression[ ] { x }
                            ),
                            new ParameterExpression[ ] { x }
                        )
                    ),
                    new ParameterExpression[ ] { f }
                )
            ),
            new ParameterExpression[ ] { y }
        );

        // Fix-point finder
        var Fix = Y.Compile( )( Y );

        // Factorial helper
        var F = Expression.Lambda<
            Func<
                Expression<Func<int, int>>,
                Expression<Func<int, int>>
            >
        >(
            Expression.Quote(
                Expression.Lambda<Func<int, int>>(
                    Expression.Condition(
                        Expression.Equal(    // test
                            x,
                            Expression.Constant(
                                0,
                                typeof( int )
                            )
                        ),
                        Expression.Constant( // if true
                            1,
                            typeof( int )
                        ),
                        Expression.Multiply( // if false
                            x,
                            Expression.Invoke(
                                Expression.Call(
                                    fac,
                                    typeof( Expression<Func<int, int>> ).GetMethod( "Compile" ),
                                    new Expression[ ] { }
                                ),
                                new Expression[ ] {
                                    Expression.Subtract(
                                        x,
                                        Expression.Constant(
                                            1,
                                            typeof( int )
                                        )
                                    )
                                }
                            )
                        )
                    ),
                    new ParameterExpression[ ] { x }
                )
            ),
            new ParameterExpression[ ] { fac }
        );

        // Factorial expression tree
        var factorial = Fix.Compile( )( F );

        // call the expression tree
        Console.WriteLine( factorial.Compile( )( num ) );
    }

    static void LambdaTest( int num ) {
        // Y Combinator
        Expression<SelfApplicableExpr<
            Expression<Func<
                Expression<Func<
                    Expression<Func<int, int>>,
                    Expression<Func<int, int>>
                >>,
                Expression<Func<int, int>>
            >>
        >> Y =
            y => f => x => f.Compile( )( y.Compile( )( y ).Compile( )( f ) ).Compile( )( x );

        // Fix-point finder
        Expression<Func<
            Expression<Func<
                Expression<Func<int, int>>,
                Expression<Func<int, int>>
            >>,
            Expression<Func<int, int>>
        >> Fix = Y.Compile( )( Y );
        // or just: var Fix = Y.Compile( )( Y );

        // Factorial helper
        Expression<Func<
            Expression<Func<int, int>>,
            Expression<Func<int, int>>
        >> F = fac => x => x == 0 ? 1 : x * fac.Compile( )( x - 1 );

        // Factorial expression tree
        Expression<Func<int, int>> factorial = Fix.Compile( )( F );
        // or just: var factorial = Fix.Compile( )( F );

        // call the expression tree
        Console.WriteLine( factorial.Compile( )( num ) );
    }
}

上面的例子里，前一个版本的Expression tree是手工创建的，后一个版本的是由编译器从lambda表达式转换来的。原理另外再解释，有兴趣的话先运行上面的例子看看吧。
上面这个例子如果把整个递归函数写在一个lambda表达式里的话，类型和内容都会简单些，不用Compile()那么多次……嘛，不管了，总之现在这样也能运行。

再看顺序结构的模拟

既然能模拟出循环的效果，让我们回头看看前面的一个例子：

( ) =>
    ( ( Func<string, object> ) ( s => (
        ( ( Action ) ( ( ) => Console.WriteLine( s.ToLower( ) ) ) ).DynamicInvoke( ) ??
        ( ( Action ) ( ( ) => Console.WriteLine( s.ToUpper( ) ) ) ).DynamicInvoke( ) )
    ) )( Console.ReadLine( ) )

很明显，DynamicInvoke()与??的包装部分是重复的。能把它抽象出来么？

为了方便，先定义一个辅助类：

delegate T SelfApplicable<T>( SelfApplicable<T> func );

public static class Functional<T1, T2, TR> {
    private static readonly
        SelfApplicable<Func<Func<Func<T1, T2, TR>, Func<T1, T2, TR>>, Func<T1, T2, TR>>>
            _yCombinator =
                y => f => ( a, b ) => f( y( y )( f ) )( a, b );
    private static readonly
        Func<Func<Func<T1, T2, TR>, Func<T1, T2, TR>>, Func<T1, T2, TR>>
            _fixPointGenerator =
                _yCombinator( _yCombinator );

    public static Func<Func<Func<T1, T2, TR>, Func<T1, T2, TR>>, Func<T1, T2, TR>> Fix {
        get { return _fixPointGenerator; }
    }
}

可以看出这个Functional<T1,T2,TR>跟前面的Functional<T,TR>内容几乎是一样的（也就是Y组合子的实现而已，见过“(Y F) = (F (Y F))”么？），只是参数的个数不一样而已；很可惜这种变化很难进一步封装，只能用到多少个参数的时候就定义一个对应的泛型类。

然后通过lambda表达式定义一个辅助用的委托：

Func<Func<Action[ ], int, object>, Func<Action[ ], int, object>> invokeAll =
    invokeIter => ( actions, index ) =>
        index < actions.Length ?
        actions[ index ].DynamicInvoke( ) ?? invokeIter( actions, index + 1 ) :
        null;

这个委托所做的就是遍历一个Action[]并调用其中的每个Action；结合Y组合子使用，其作用类似下面这个for循环：

for ( int index = 0; index < actions.Length; ++index ) {
    actions[ index ].DynamicInvoke( );
}

这样我们就能把下面这个带有语句块的lambda表达式：

( int x, int y ) => {
    Console.WriteLine( "x = {0}", x );
    Console.WriteLine( "y = {0}", y );
    Console.WriteLine( "x+y = {0}", x + y );
}

转换成这样：

( x, y ) =>
    Functional<Action[ ], int, object>.Fix( invokeAll )( new Action[ ] {
        ( ) => Console.WriteLine( "x = {0}", x ),
        ( ) => Console.WriteLine( "y = {0}", y ),
        ( ) => Console.WriteLine( "x+y = {0}", x + y )
    }, 0 )

当然还有办法进一步抽象，不过这个样子已经比前面的版本要简洁了，不是么？
顺带一提，把那些辅助类和委托的有效部分直接写在这个lambda表达式里也可以，不过这里为了代码简洁还是分开写了。如果把所有东西合在一起的话……（SelfApplicable的定义还是得在别处声明）

Expression<Action<int, int>> expr = ( arg1, arg2 ) =>
    ( ( SelfApplicable<
            Func<
                Func<
                    Func<Action[ ], int, object>,
                    Func<Action[ ], int, object>
                >,
                Func<Action[ ], int, object>>> ) (
        y => f => ( a, b ) => f( y( y )( f ) )( a, b ) )
    )( y => f => ( a, b ) => f( y( y )( f ) )( a, b )
    )( invokeIter => ( actions, index ) =>
        index < actions.Length ?
        actions[ index ].DynamicInvoke( ) ?? invokeIter( actions, index + 1 ) :
        null
    )( new Action[ ] {
        ( ) => Console.WriteLine( "x = {0}", arg1 ),
        ( ) => Console.WriteLine( "y = {0}", arg2 ),
        ( ) => Console.WriteLine( "x+y = {0}", arg1 + arg2 )
    }, 0 );

（顺便赋值给Expression<Action<int,int>>来让编译器生成Expression tree。很明显把几个lambda表达式合成一个之后，要显式指定的类型就没那么多了，都集中在开始的那个类型转换上。）
这样调用就行：

expr.Compile( )( 1, 2 );
// x = 1
// y = 2
// x+y = 3

要是上面给绕得太晕了，那还是直接在一个可以编译执行的文件上玩玩吧：
把前一节里的例子稍微简化一下合在一起就是这样一个文件：

using System;
using System.Linq.Expressions;

delegate T SelfApplicable<T>( SelfApplicable<T> func );

sealed class Program {
    static void Main( string[ ] args ) {
        Expression<Action<int, int>> expr = ( m, n ) =>
            ( ( Func<
                    SelfApplicable<
                        Func<
                            Func<
                                Func<Action[ ], int, object>,
                                Func<Action[ ], int, object>
                            >,
                            Func<Action[ ], int, object>>>,
                    Func<
                        Func<
                            Func<Action[ ], int, object>,
                            Func<Action[ ], int, object>
                        >,
                        Func<Action[ ], int, object>>> ) (
                y => y( y ) )
            )( y => f => ( a, b ) => f( y( y )( f ) )( a, b )
            )( invokeIter => ( actions, index ) =>
                index < actions.Length ?
                actions[ index ].DynamicInvoke( ) ?? invokeIter( actions, index + 1 ) :
                null
            )( new Action[ ] {

                // NOTE:
                // Begin of statement block

                ( ) => Console.WriteLine( "m = {0}", m ),
                ( ) => Console.WriteLine( "n = {0}", n ),
                ( ) => Console.WriteLine( "m+n = {0}", m + n )

                // End of statement block

            }, 0 );

        expr.Compile( )( 1, 2 );
    }
}

注意到一个细微的区别：我把Y组合子的实现稍微改了下，所以lambda表达式看起来简洁了一些，但相对的，前面的类型转换部分则变长了一些。

嗯相应的手工构造Expression tree的版本：

using System;
using System.Linq.Expressions;

delegate T SelfApplicable<T>( SelfApplicable<T> func );

static class Program {
  private static void Main(string[] args) {
    var mParam              = Expression.Parameter(typeof(int), "m");
    var nParam              = Expression.Parameter(typeof(int), "n");
    var yParam              = Expression.Parameter(typeof(SelfApplicable<Func<Func<Func<Action[], int, object>, Func<Action[], int, object>>, Func<Action[], int, object>>>), "y");
    var fParam              = Expression.Parameter(typeof(Func<Func<Action[], int, object>, Func<Action[], int, object>>), "f");
    var aParam              = Expression.Parameter(typeof(Action[]), "a");
    var bParam              = Expression.Parameter(typeof(int), "b");
    var indexParam          = Expression.Parameter(typeof(int), "index");
    var actionsParam        = Expression.Parameter(typeof(Action[]), "actions");
    var invokeIterParam     = Expression.Parameter(typeof(Func<Action[], int, object>), "invokeIter");
  
    var dynamicInvokeMethod = typeof(Delegate).GetMethod("DynamicInvoke");
    var writeLineMethod     = typeof(Console).GetMethod("WriteLine", new Type[] { typeof(string), typeof(object)});
    
    var expr =
      Expression.Lambda<Action<int, int>>(
        Expression.Invoke(
          Expression.Invoke(
            Expression.Invoke(
              Expression.Lambda<Func<SelfApplicable<Func<Func<Func<Action[], int, object>, Func<Action[], int, object>>, Func<Action[], int, object>>>, Func<Func<Func<Action[], int, object>, Func<Action[], int, object>>, Func<Action[], int, object>>>>(
                Expression.Invoke(
                  yParam,
                  new Expression[] { yParam }
                ),
                new ParameterExpression[] { yParam }
              ),
              new Expression[] {
                Expression.Lambda<SelfApplicable<Func<Func<Func<Action[], int, object>, Func<Action[], int, object>>, Func<Action[], int, object>>>>(
                  Expression.Lambda<Func<Func<Func<Action[], int, object>, Func<Action[], int, object>>, Func<Action[], int, object>>>(
                    Expression.Lambda<Func<Action[], int, object>>(
                      Expression.Invoke(
                        Expression.Invoke(
                          fParam,
                          new Expression[] {
                            Expression.Invoke(
                              Expression.Invoke( // invoke the Y-combinator
                                yParam,
                                new Expression[] { yParam }
                              ),
                              new Expression[] { fParam }
                            )
                          }
                        ),
                        new Expression[] { aParam, bParam }
                      ),
                      new ParameterExpression[] { aParam, bParam }
                    ),
                    new ParameterExpression[] { fParam }
                  ),
                  new ParameterExpression[] { yParam }
                )
              }
            ),
            new Expression[] {
              Expression.Lambda<Func<Func<Action[], int, object>, Func<Action[], int, object>>>(
                Expression.Lambda<Func<Action[], int, object>>(
                  Expression.Condition(
                    Expression.LessThan(
                      indexParam,
                      Expression.ArrayLength(
                        actionsParam
                      )
                    ),
                    Expression.Coalesce(
                      Expression.Call(
                        Expression.ArrayIndex(
                          actionsParam,
                          indexParam
                        ),
                        dynamicInvokeMethod,
                        new Expression[] {
                          Expression.NewArrayInit(
                            typeof(object),
                            new Expression[0]
                          )
                        }
                      ),
                      Expression.Invoke(
                        invokeIterParam,
                        new Expression[] {
                          actionsParam,
                          Expression.Add(
                            indexParam,
                            Expression.Constant(
                              1,
                              typeof(int)
                            )
                          )
                        }
                      )
                    ),
                    Expression.Constant(
                      null,
                      typeof(object)
                    )
                  ),
                  new ParameterExpression[] { actionsParam, indexParam }
                ),
                new ParameterExpression[] { invokeIterParam }
              )
            }
          ),
          new Expression[] {
            Expression.NewArrayInit(
              typeof(Action),
              new Expression[] {
                Expression.Lambda<Action>(
                  Expression.Call(
                    null, 
                    writeLineMethod,
                    new Expression[] {
                      Expression.Constant(
                        "m = {0}",
                        typeof(string)
                      ),
                      Expression.Convert(
                        mParam,
                        typeof(object)
                      )
                    }
                  ),
                  new ParameterExpression[0]
                ),
                Expression.Lambda<Action>(
                  Expression.Call(
                    null,
                    writeLineMethod,
                    new Expression[] {
                      Expression.Constant(
                        "n = {0}",
                        typeof(string)
                      ),
                      Expression.Convert(
                        nParam,
                        typeof(object)
                      )
                    }
                  ),
                  new ParameterExpression[0]
                ),
                Expression.Lambda<Action>(
                  Expression.Call(
                    null,
                    writeLineMethod,
                    new Expression[] {
                      Expression.Constant(
                        "m+n = {0}",
                        typeof(string)
                      ),
                      Expression.Convert(
                        Expression.Add(
                          mParam,
                          nParam
                        ),
                        typeof(object)
                      )
                    }
                  ),
                  new ParameterExpression[0]
                )
              }
            ),
            Expression.Constant(
              0,
              typeof(int)
            )
          }
        ),
        new ParameterExpression[] { mParam, nParam }
      );
    expr.Compile()(1, 2);
  }
}

敬请期待后续文章。
Have fun with Expression trees!

评论

1 楼 cajon 2008-10-09  

Wow, 看到了函数式编程的影子。