LINQ与DLR的Expression tree（3）：LINQ与DLR及另外两个库的AST对比

（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表达式表示常见控制结构

（为节约带宽和版面，文中缩小图片请点击放大）

语言特定的AST与DLR tree

在介绍DLR tree之前，先看看它的原点，IronPython 1.x中的AST（抽象语法树）类层次。使用先前写的类型层次查看工具，截得此图：

以上的类层次除System.Object外都位于IronPython.Compiler.Ast命名空间中。
IronPython 1.0系列与1.1系列中的AST类层次是一样的。注意到表达式（Expression）与语句（Statement）的节点都是继承自Node，也就是说IronPython 1.x是区分表达式与语句的。在许多语言中，表达式与语句最大的区别就是是否有值：表达式有值，可以组合在一起；而语句没有值，不能组合在一起，只能按顺序写下来。

再看看使用了DLR tree之后的IronPython 2.x的类层次（右边）与1.x的类层次的比较。IronPython 2.x的AST类层次也在IronPython.Compiler.Ast命名空间里。还是用那个类型层次查看工具，这次使用文本模式，方便比较：

可以看到，从类型层次的角度看，大多数变化都只是重命名，新增的比较显著的就是Parameter相关的3个类和DottedName的两个派生类。换句话说，使用DLR tree与否对IronPython的词法/语法分析器并没有带来多少影响。

为什么呢？IronPython自己的AST也是抽象语法树，DLR tree也是抽象语法树，既然用了DLR为何不在语法分析的时候跳过生成自己的AST，而直接生成DLR tree呢？

在MIX 08上，John Lam在一个问答环节中特别提到：在DLR上实现语言时，最好不要直接从parser生成DLR tree，而应该维护自己一套特定的AST，然后再转换到DLR tree。这是因为DLR tree与实际的“语法”几乎没有联系了，为了让调试器等功能更好的工作，最好还是有一套更贴近语法的表现。这是IronPython小组在实现IronPython过程中得到的经验教训。

回顾一下使用DLR的语言实现中编译器的工作流程：
词法分析->语法分析->语义分析->（...中间的优化过程...）->DLR tree生成
不使用DLR tree作为目标，一般的编译器的工作流程会像这样：
词法分析->语法分析->语义分析->（...中间的优化过程...）->代码生成

虽然DLR是CLR上的一个库，但从某种意义上说DLR自己也是一个虚拟机，而它的指令集就是DLR tree。比起CLR上的MSIL，DLR tree的抽象层次自然是高一些，更容易操纵一些；但它相对某种具体语言的语法树还是更靠近底层，虽然保留了所有与执行相关的语义，但与“运行”本身不相关的细节却损失了，如代码的位置信息等。要提供流畅的调试体验，代码的位置信息还是很重要的。
另外，DLR tree对其上的语言实现所使用的类型系统一无所知；它只能对CLR类型做检查，如果其上的语言实现有自己的类型系统，就需要自己先做一些处理，再交给DLR tree完成编译过程。由于DLR tree是不可改变（immutable）的，诸如补丁（backpatch）等的技巧无法用于DLR tree上。一般来说，如果语法分析器无法在一趟（1 pass）内分析到足够的信息，可以把已经收集到的信息保存在AST里，后面再继续遍历这个AST来分析并添加新的信息；但DLR tree一旦生成就无法改变，要“改变”只能再生成一棵新的DLR tree，开销实在是太大。这也是语言特定AST应该与DLR tree分离开的一个原因。

不在语法分析器里直接生成DLR tree还有一个好处，就是代码会更整洁更容易维护一些。就像多数编译器不会在语法分析器里直接生成机器码一样。

5月份Channel 8放出了Martin Maly关于DLR与LOLCode的一段访谈。这个基于DLR的LOLCode是Martin Maly用了不到2天时间制作的一个实际存在的语言（LOLCODE）的实现。访谈中Martin展示了整合到Visual Studio中的LOLCode的调试支持：调试器能准确的高亮显示出断点所在的语句，也能够显示出变量的值；这些功能与语言特定的AST有密切关系。

（当然，需要说明的是，Martin Maly的LOLCode是基于比较早期DLR来实现的，而当时的DLR tree仍然带有代码位置的信息。当时创建一个DLR tree节点需要传一个SourceSpan参数进去，而现在的DLR tree已经不带有这种信息了。）

然而在7月中旬的RubyFringe上，IronRuby项目的John Lam提到DLR遇到了一些性能问题，DLR tree则在这个问题的中心：
1、启动速度的问题。DLR的主要工作模式是编译模式，将DLR tree编译为MSIL之后由CLR来执行。在长时间运行重复度比较高的程序时，这种方式的性能不错。但许多时候开发者可能只是很短时间的运行某个小程序，例如交互式解释器、小项目的自动化单元测试等。将只运行一次的代码完整的编译一次带来了许多额外开销，严重影响程序的启动速度。用过IronPython 2.0的任意一个alpha或beta都会发现：它的交互式解释器ipy，在执行第一组输入的代码时会特别慢，几乎是停顿了一小下才有反应，然后后续的相应速度就好很多。可以看出启动速度方面有多糟糕……在这一点上现在的DLR还无法与用C实现的解释器相比。
为此，DLR也有解释模式，可以由一个DLR自带的解释器来解释执行DLR tree。不过这个解释器为了照顾到不同语言的需求而无法做某些特定的优化，所以速度并不很快。还好，DLR的模块化设计允许语言实现提供自己的解释器插到DLR上。这样，对启动速度有很高要求的语言实现仍然可以使用DLR的其它组件，而其它语言实现则能够依靠DLR的默认实现来缩短开发时间。
2、内存占用量（memory footprint）的问题。一个使用DLR的语言实现在编译过程中要创建大量的对象，其中包括自身的AST，对应的DLR tree，最后生成的含有MSIL的DynamicMethod等。DLR tree占用的空间比语言特定的AST和MSIL都要大，它或许有语言特定的AST的10倍大。这个问题现在是如何解决的，我没有看到明确的资料，这里也就没办法深入了。

DLR tree的演变

先放一张图，从IronPython 2.0 Alpha 1到Beta 5中DLR tree的类层次：


有兴趣的话可以看看DLR tree的类层次是如何发展变化的。特别是可以注意一下图中越靠近左边的部分就越像IronPython自身的AST，越靠近右边就越像LINQ的Expression tree。中间的过程下面慢慢道来。

去年4月底，IronPython 2.0的第一个Alpha发布了。这也算是DLR首次以代码的形式亮相吧。

5月份，Jim Hugunin在他的blog上介绍了DLR Trees。文中提到，在构建DLR之初，他们已经意识到LINQ使用抽象语法树作为数据结构来表示代码与他们想要做的事情有共通之处。虽然他们想要一种共享的抽象语法树，但他们要的树中应该包含无类型、迟绑定的节点，并总是使用动态的操作。既然是无类型的树，与C# 3和VB9中强类型的LINQ Expression tree的相似度似乎不大，所以他们独自开展了DLR tree的设计工作。可以想像，整个DLR都是以IronPython 1.0的核心为基础来设计的，DLR tree自然与IronPython的AST有着许多相似的地方。所以在早期的IronPython 2.0 Alpha 1里，很容易看到这样的代码：
IronPython.Compiler.Ast.AndExpression:

internal override MSAst.Expression Transform(AstGenerator ag) {
    return new MSAst.AndExpression(
        ag.Transform(_left),
        ag.Transform(_right),
        Span
    );
}

所谓“转换”在这里只是分别转换左子树和右子树，然后调用了一个DLR tree对应的类的构造器而已。这个版本里IronPython AST到DLR tree的转换相对来说都比较直接，从侧面反映出当时的DLR tree受到IronPython AST多大影响。

当他们开始在DLR上实现Managed JavaScript和IronRuby等其它语言之后，很快发现当时的DLR tree难以表现各个语言独特的语言概念。像是Python的print语句，JavaScript的正则表达式字面量等，每种语言都有独特的概念。如果概念相同而只是语法不一样（例如许多C#和VB.NET的语法结构），那问题很好解决：抽象语法树不关心具体语法，只要概念相同就能用同样的AST节点来表示。但如果概念本身就不同那就不好办了：如果DLR tree的设计缺乏弹性，那么一个语言就无法将缺乏DLR对应物的语言结构表示出来了。虽然DLR可以添加大量不同的节点来尽量对不同语言提供直接支持，但那是没有尽头的。关键还是要找到一种抽象的方法来有弹性的支持各种语言概念。

他们也注意到，IronPython中许多特别的语言结构都是通过调用静态的辅助方法或者访问静态变量来实现的。例如print语句就是调用IronPython.Runtime.PythonOps这个静态类上的几个静态方法来实现的。这些辅助方法和辅助变量显然是静态类型的（CLR意义上），DLR tree要支持它们只需要添加表示CLR类型的方法调用/变量访问的节点就行。而这正是LINQ Expression tree已经做了的事情。意识到这点之后，他们决定将DLR tree逐步与LINQ Expression tree合并到一起。

这样，其实在外界第一次看到DLR代码的时候，DLR tree向LINQ Expression tree的合并就已经开始了。刚把从IronPython 1.0提取出DLR的元素时，DLR tree位于Microsoft.Scripting.Internal.Ast命名空间中（IronPython 2.0 Alpha 1）。后来，早期的DLR tree在Microsoft.Scripting.Ast命名空间中（Alpha 2 - Beta 3）。当DLR tree已经完整覆盖了原本LINQ Expression tree的功能，并拥有共通的API时，DLR tree就被移动到了System.Linq.Expressions命名空间中（Beta 4）。

过程中有几个我觉得值得注意的点，以IronPython 2.0的各早期版本为参考：

Alpha 1 - Alpha 7：这个阶段的DLR tree经历了来回振荡，类型个数时有增减，反映寻找对多种语言支持的平衡点的过程。许多节点可以说带有过多的语言细节，并不是件好事。也可以发现，DLR tree已经包含了LINQ Expression tree中各节点的对应物，多出来的是动态操作、变量、名字绑定、控制流等相关节点；只不过类的名字以及具体API与LINQ的还不一样，这是初期设计留下的痕迹。还有一个特点，那就是代码块（CodeBlock）、表达式（Expression）与语句（Statement）都直接继承DLR tree类层次中的根类型Node，也就是说它们之间是相互独立的。这与IronPython AST以及其它许多严格区分表达式和语句的语言的做法一样；IronPython比较特别的地方是把类定义与方法定义也看作语句来处理。
值得一提的细节：从Alpha 2开始，创建DLR tree的节点就不再是通过直接调用构造器，而是通过调用一个静态工厂类——Microsoft.Scripting.Ast上的工厂方法来进行的。熟悉LINQ Expression tree的话，会发现这个类的主要功能与LINQ的System.Linq.Expressions.Expression类一样。
早期的DLR一直在Microsoft.Scripting.dll里。

Alpha 8：从这个版本开始，DLR tree下的所有节点都变成了Expression的子类，原先作为DLR tree根类型的Node随之消失。也就是说，DLR tree不再严格区分代码块、表达式与语句；所有节点都是“表达式”节点，可以参与到表达式组合中。对某些语言来说这可能有点奇怪，因为语句本来应该是不可组合的。从DLR的弹性来讲这倒可以理解：尽量让节点变得可组合，以满足不同语言潜在的需要；“不可组合”的语句可以看作是“可组合”的表达式的特例，只要具体的语言实现在语法分析的时候做好检查就行。话是这么说，这个改变背后更大的推动力恐怕还是与LINQ “Expression” tree的整合吧。

Beta 1（Changeset 31679）：到IronPython Beta 1发布的时候，原本叫做CodeBlock的表示语句块的类型被重命名为LambdaExpression。但不巧的是Beta 1里的代码正巧截取在LambdaExpression成为Expression的派生类之前。所以在这一节开头的那张图里，Beta 1中DLR tree的类层次与Alpha 8看起来是一样的，因为LambdaExpression还没加到这个类层次中。Beta 1发布一周多之后，Changeset 31679里的代码就反映了这个变化。可以留意这个LambdaExpression与LINQ的对应类的关系。

Beta 2 - Beta 3：就DLR tree本身来看可值得注意的不多，主要是新增的CodeContext*的节点，把GeneratorLambdaExpression重构为Expression<TDelegate>，以及有更多的节点类型的名字从Statement过渡到Expression。这个阶段的DLR tree越来越接近与LINQ Expression tree兼容了。
从DLR整体看有一个重要变化：DLR不再存在于单一的DLL中，而是拆分成作为核心的Microsoft.Scripting.Core.dll与作为辅助的Microsoft.Scripting.dll这两个程序集。我的猜测是在Core里的代码有很大机会进入下一个版本的.NET Framework标准库中，而不在Core里的则会继续独立在标准库之外。

Beta 4：DLR tree终于正式与LINQ Expression tree合并到一起了。DLR tree所在的命名空间变为System.Linq.Expressions，而Microsoft.Scripting.Core.dll里的其它部分多数也进入以System.Scripting开头的命名空间。这更加明确的表现出DLR的核心将进入下个版本的.NET标准库。
关于命名空间的一系列的变化是在6月的Beta 3之后8月的Beta 4之前的某个时候发生的。中间IronPython与IronRuby曾经有好几个星期都没有放出过新的代码，最早能看到这些变化的是7月12日的Changeset 34286。

Beta 5：一个星期前才发布的最新版本。这是IronPython 2.0的最后一个beta，下一个版本就会是Release Candidate了。相应的，DLR的API也应该接近冻结了，但……
实际看来远非如此。如同SapphireSteel的总架构师Dermot Hogan所说，

Dermot Hogan 写道

I’ve no objection to things being changed in the DLR - but it does seem odd to me that a beta of IronPython is being implemented on what is still essentially an alpha version of the DLR.

主要是每个版本间的API差别太大了，给人一种完成度很低的感觉。事实上这也有许多因素在影响着。很明显要是能在正式发布前能尽量重构出一个比较干净、富有弹性的API会比较好，而不是等到匆忙发布之后受困于向后兼容的问题而无法随意改变API。在Beta 3到Beta 5之间，DLR经历了重大的重新设计，原本作为动态类型对象基础的IDynamicObject与动态方法分发核心的ActionBinder等一系列类型都被重新设计了。取代ActionBinder的就是上一篇提到的MetaObject。
对DLR tree来说，Beta 5最大的变化就是原本以System开头的命名空间几乎都改回以Microsoft开头。这并不是简单的退回到Beta 4之前的状态，而是为了解决命名空间冲突的问题。IronPython小组的PM，Harry Pierson在一篇blog中讲述了这个变动的原因：IronPython（和DLR）是以.NET Framework 2.0为目标平台的。在.NET 2.0中，System.Core.dll尚不存在，里面许多相关设施也就无法使用，包括LINQ、扩展方法的标记ExtensionAttribute、一些标准委托定义Func<>与Action<>系列等。DLR需要这些设施，而为了能在.NET 2.0上运行，他们不得不把System.Core.dll里的一些类型搬到Microsoft.Scripting.Core.dll中。但这给.NET 3.5的用户带来了麻烦，特别是在命名空间转到System下之后，System.Core.dll与Microsoft.Scripting.Core.dll到处都是类型冲突。对一般的C#开发者来说这问题还不至于无法解决，可以用程序集别名来绕开，但还是很麻烦；对ASP.NET和VB.NET开发者来说麻烦就大了，这两个程序集几乎无法相容。无奈之下，从Beta 5（具体来说是之前的Changeset 39648）开始DLR核心的命名空间就从System改回到了Microsoft。
不过，在IronPython 2.0 Beta 5发布之后才放出来的IronRuby代码里，DLR的核心仍然在System.Scripting命名空间下。这有点奇怪，两个项目应该是共用一套DLR代码才对的，为什么现在只有IronPython的做了修改呢？让时间告诉我们答案吧。希望下个版本的.NET Framework快点出现，DLR的核心快点整合到标准库里去，那样冲突肯定都能解决掉。


与这一节开头介绍的早期DLR对比，让我们看看最新的（IronPython Beta 5）中的IronPython.Compiler.Ast.AndExpression里的Transform()方法是什么样的：

internal override MSAst.Expression Transform(AstGenerator ag, Type type) {
    MSAst.Expression left = ag.Transform(_left);
    MSAst.Expression right = ag.Transform(_right);

    Type t = left.Type == right.Type ? left.Type : typeof(object);
    MSAst.VariableExpression tmp = ag.GetTemporary("__all__", t);
    
    return Ast.Condition(
        Binders.Convert(
            ag.BinderState,
            typeof(bool),
            ConversionResultKind.ExplicitCast,
            Ast.Assign(
                tmp,
                Ast.ConvertHelper(
                    left,
                    t
                )
            )
        ),
        Ast.ConvertHelper(
            right,
            t
        ),
        tmp
    );            
}

与初期的IronPython 2.0 Alpha 1有不少差别。最明显的是出现了静态类型信息，而且DLR tree与IronPython AST的抽象层次明显不同了，不像早期的DLR与IronPython那么相似。


DLR tree与LINQ Expression tree

上一节所描述的DLR tree演变过程应该能充分表现DLR与LINQ Expression tree的关系这一节具体从类层次和API来观察两者。两者的类层次对比图：

（黑色字体的是两者皆有的类型，红色的是DLR新增的类型。图片反映的是IronPython 2.0 Beta 5/IronRuby revision 149的状况。）

7月21日，IronPython的Changeset 34421出了。当时我也写了个小程序来看其中的DLR tree与LINQ Expression tree的差异。其实观察这两者最直观的方式并不是看AST有哪些类，而是观察System.Linq.Expressions.Expression上的静态工厂方法——LINQ Expression tree中的节点全都是通过这些静态工厂方法而不是直接调用构造器来创建的，而现在的DLR tree也是一样。

最近几天又再关注到LINQ这边来，所以又做了次对比。由于上一节提到的类型冲突问题，之前我为了得到两者的Expression类上的工厂方法名，是分开写了两个小程序，其中DLR的那个是设置到以.NET Framework 2.0为目标来避免引入System.Core.dll，避开命名空间的冲突。刚才准备再做比对的时候对原来的程序不满了，所以改了下，对程序集引用使用别名来解决冲突问题。代码如下：
extract_factory_methods.cs:

extern alias dlr;

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using Ast = dlr::System.Linq.Expressions.Expression; 

static class Program {
    static IEnumerable<string> GetPublicStaticMethodsAndWriteToLog(
        Type objType, string logFileName ) {
        var methods = from method in objType.GetMethods(
                          BindingFlags.Public | BindingFlags.Static )
                      where method.ReturnType.IsSubclassOf( objType )
                      group method by method.Name into methodGroup
                      orderby methodGroup.Key
                      select methodGroup.Key;
        using ( var log = File.CreateText( logFileName ) ) {
            foreach ( var name in methods ) {
                log.WriteLine( name );
            }
        }
        return methods;
    }

    [STAThread]
    static void Main( string[ ] args ) {
        var linqFactories = GetPublicStaticMethodsAndWriteToLog(
            typeof( Expression ), "LINQ_Expression.txt" );
        var dlrFactories = GetPublicStaticMethodsAndWriteToLog(
            typeof( Ast ), "DLR_Expression.txt" );
        
        var allFactories = from method in dlrFactories.Union( linqFactories )
                           let isInLinq = linqFactories.Contains( method )
                           let isInDlr = dlrFactories.Contains( method )
                           select ( isInLinq && !isInDlr ) ?
                                   "- " + method :
                                  ( !isInLinq && isInDlr ) ?
                                   "+ " + method :
                                   "  " + method;
        foreach ( var method in allFactories ) {
            Console.WriteLine( method );
        }
    }
}

这个程序会提取LINQ与DLR的Expression类上的工厂方法，分别写入文件记录下来，并将结果进行比对，显示在标准输出上。这段代码本身就充分使用了LINQ，以一致而便捷的方式获取到了需要的数据。
比对的格式是：
·LINQ与DLR都含有的方法在名字前加两个空格；
·DLR比LINQ少的方法在名字前加"- "；
·DLR比LINQ多的方法在名字前加"+ "。

注意：编译该文件的时候要指定引用的程序集的别名：

引用

csc /r:dlr=Microsoft.Scripting.Core.dll extract_factory_methods.cs

对9月23号出的IronRuby revision 149做测试，得到的输出结果如下（*）：

+ ActionExpression   : DynamicExpression
  Add                : BinaryExpression
  AddChecked         : BinaryExpression
+ AllVariables       : LocalScopeExpression
  And                : BinaryExpression
  AndAlso            : BinaryExpression
+ ArrayAccess        : IndexExpression
  ArrayIndex         : BinaryExpression
  ArrayLength        : UnaryExpression
+ Assign             : AssignmentExpression
+ AssignArrayIndex   : AssignmentExpression
+ AssignField        : AssignmentExpression
+ AssignProperty     : AssignmentExpression
+ Block              : Block
+ Break              : BreakStatement
  Call               : MethodCallExpression
  Coalesce           : BinaryExpression
+ Comma              : Block
  Condition          : ConditionalExpression
  Constant           : ConstantExpression
+ Continue           : ContinueStatement
  Convert            : UnaryExpression
  ConvertChecked     : UnaryExpression
  Divide             : BinaryExpression
+ DoWhile            : DoStatement
+ Dynamic            : DynamicExpression
+ Empty              : EmptyStatement
  Equal              : BinaryExpression
  ExclusiveOr        : BinaryExpression
+ False              : ConstantExpression
  Field              : MemberExpression
+ Generator          : LambdaExpression or Expression<TDelegate>
  GreaterThan        : BinaryExpression
  GreaterThanOrEqual : BinaryExpression
  Invoke             : InvocationExpression
+ Labeled            : LabeledStatement
  Lambda             : LambdaExpression or Expression<TDelegate>
  LeftShift          : BinaryExpression
  LessThan           : BinaryExpression
  LessThanOrEqual    : BinaryExpression
  ListInit           : ListInitExpression
+ Loop               : LoopStatement
  MakeBinary         : BinaryExpression
+ MakeDynamic        : DynamicExpression
+ MakeIndex          : IndexExpression
  MakeMemberAccess   : MemberExpression
+ MakeTry            : TryStatement
  MakeUnary          : UnaryExpression
  MemberInit         : MemberInitExpression
  Modulo             : BinaryExpression
  Multiply           : BinaryExpression
  MultiplyChecked    : BinaryExpression
  Negate             : UnaryExpression
  NegateChecked      : UnaryExpression
  New                : NewExpression
  NewArrayBounds     : NewArrayExpression
+ NewArrayHelper     : NewArrayExpression
  NewArrayInit       : NewArrayExpression
  Not                : UnaryExpression
  NotEqual           : BinaryExpression
+ Null               : ConstantExpression
  Or                 : BinaryExpression
  OrElse             : BinaryExpression
  Parameter          : ParameterExpression
  Power              : BinaryExpression
  Property           : IndexExpression
  PropertyOrField    : MemberExpression
  Quote              : UnaryExpression
+ Rethrow            : ThrowStatement
+ Return             : ReturnStatement
  RightShift         : BinaryExpression
+ RuntimeConstant    : ConstantExpression
+ Scope              : ScopeExpression
+ SimpleCallHelper   : MethodCallExpression
+ SimpleNewHelper    : NewExpression
  Subtract           : BinaryExpression
  SubtractChecked    : BinaryExpression
+ Switch             : SwitchStatement
+ Throw              : ThrowStatement
+ True               : ConstantExpression
+ TryCatch           : TryStatement
+ TryCatchFault      : TryStatement
+ TryCatchFinally    : TryStatement
+ TryFault           : TryStatement
+ TryFinally         : TryStatement
  TypeAs             : UnaryExpression
  TypeIs             : TypeBinaryExpression
  UnaryPlus          : UnaryExpression
+ Unbox              : UnaryExpression
+ Variable           : VariableExpression
+ WeakConstant       : MemberExpression
+ Yield              : YieldStatement
+ Zero               : ConstantExpression

由比对结果可以看到DLR中的Expression类是LINQ中的同一个对应类的超集，也反映了DLR tree是LINQ Expression tree的超集。两者最大不同在于，LINQ Expression tree只能用来表式不包括赋值在内的表达式，而DLR tree则可以表示各种语言常见的各种语法结构，包括赋值表达式、语句、代码块等。为了保证其灵活性，DLR tree被设计成语言中立的避免与某种特定语言有过多耦合。也因为这样，不是每种语言的每种语法结构都能够在DLR tree中找到直接对应物，有时候需要进行一些组装和自定义才能映射过来。

LINQ Expression tree与C# 3/VB9的非赋值表达式有着明显的一一对应的关系，下一篇将会详细讨论。也要注意到，使用现在的LINQ Expression tree来表示表达式时，如果出现了运行时错误，我们是看不到具体出错位置的行号的。
举例来说，如果通过lambda表达式得到一个Func委托，然后故意引发异常，将能够看到出错的实际行号：

using System;

static class Program {
    static void Main( string[ ] args ) {
        Func<int, int, int> div =
          ( x, y ) => x / y;
        div( 2, 0 );
    }
}

运行得到：

引用

未处理的异常:  System.DivideByZeroException: 试图除以零。
   在 Program.<Main>b__0(Int32 x, Int32 y) 位置 h:\test_linq_div0.cs:行号 6
   在 Program.Main(String[] args) 位置 h:\test_linq_div0.cs:行号 7

注意到行号6是lambda表达式所在的行，也就是最具体的出错位置。之所以还能看到这个行号是因为C#编译器为我们在Program类里生成了一个静态方法，调试符号则依附在这个类所在的程序集中。

但如果改用Expression tree，出错的行号就看不到了，无论是通过lambda表达式由编译器来生成Expression tree还是手工创建都不行：

using System;
using System.Linq.Expressions;
  
static class Program {
    static void Main( string[ ] args ) {
        Expression<Func<int, int, int>> divExpr =
          ( x, y ) => x / y;
        Func<int, int, int> div = divExpr.Compile( );
        div( 2, 0 );
    }
}

运行得到：

引用

未处理的异常:  System.DivideByZeroException: 试图除以零。
   在 lambda_method(ExecutionScope , Int32 , Int32 )
   在 Program.Main(String[] args) 位置 h:\testdbg.cs:行号 9

using System;
using System.Linq.Expressions;

static class Program {
    static void Main( string[ ] args ) {
        ParameterExpression x = Expression.Parameter( typeof( int ), "x" );
        ParameterExpression y = Expression.Parameter( typeof( int ), "y" );
        Expression<Func<int, int, int>> divExpr =
          Expression.Lambda<Func<int, int, int>>(
              Expression.Divide(
                  x,
                  y
              ),
              new [ ] { x, y }
          );
        Func<int, int, int> div = divExpr.Compile( );
        div( 2, 0 );
    }
}

运行得到：

引用

未处理的异常:  System.DivideByZeroException: 试图除以零。
   在 lambda_method(ExecutionScope , Int32 , Int32 )
   在 Program.Main(String[] args) 位置 h:\test_linq_div0.cs:行号 17

这个错误发生在一个动态生成的方法中。虽然出错的方法是由一棵Expression tree编译得到的，但编译器无法判断一棵Expression tree到底是从哪里来的，自然也无法为这个动态生成的方法提供行号信息。说起来，利用LCG生成代码也不保存这些信息的。在.NET Framework 3.5的System.Reflection.Emit.DynamicMethod的文档里有这么一句：

MSDN 写道

在 .NET Framework 2.0 中，动态方法不支持符号信息，即本地变量名和行号映射。在未来版本中可能会移除该限制。

当前的DLR tree既然已经跟LINQ Expression tree合并到一起，显然也会有一样的问题。还是用同一个例子，换成IronRuby revision 149的DLR来测试：

extern alias dlr;

using System;
using dlr::System.Linq.Expressions;

static class Program {
    static void Main( string[ ] args ) {
        ParameterExpression x = Expression.Parameter( typeof( int ), "x" );
        ParameterExpression y = Expression.Parameter( typeof( int ), "y" );
        Expression<Func<int, int, int>> divExpr =
            Expression.Lambda<Func<int, int, int>>(
                Expression.Divide(
                    x,
                    y
                ),
                new [ ] { x, y }
            );
        Func<int, int, int> div = divExpr.Compile( true ); // note!
        div( 2, 0 );
    }
}

运行得到：

引用

未处理的异常:  System.DivideByZeroException: 试图除以零。
   在 lambda_method$1$1.lambda_method$1(Closure , Int32 , Int32 )
   在 Program.Main(String[] args) 位置 h:\test_linq_div0.cs:行号 19

注意到调用栈记录的细微差异。另外，我在Compile()的时候传了一个额外的参数进去，这是指定DLR在编译的时候生成调试符号信息，就像在命令行调用csc.exe时指定/debug开关一样。但仍然看不到行号——那是当然，因为DLR tree根本没记录这个信息！
一般来说，一个C# 3或者VB9程序中Expression tree只会占很少的分量，所以即便调试时看不到行号问题似乎也还不太大。但基于DLR实现的语言呢？它们全靠DLR tree来运行，如果调试的时候看不到行号问题就大了。正好印证了本文第一节里所讲的语言特定的AST与DLR tree的关系：我们需要语言特定的AST来保存某些信息，例如调试符号信息。

目前的LINQ Query Provider都是针对纯表达式子集的，以后的版本会不会为更丰富范围的Expression tree节点提供支持呢？这也还是个未知数。

DLR tree与CodeDom

说到抽象语法树，.NET平台的标准库里还有另外一套使用AST的库，叫做代码文档对象模型（CodeDOM，Code Document Object Model）。那么LINQ Expression tree、DLR tree与CodeDOM的关系是怎样的呢？

先来了解一下CodeDOM是什么。引用MSDN上的说明：

MSDN 写道

.NET Framework 开发人员指南
动态源代码生成和编译
.NET Framework 中包含一个名为“代码文档对象模型”(CodeDOM) 的机制，该机制使编写源代码的程序的开发人员可以在运行时，根据表示所呈现代码的单一模型，用多种编程语言生成源代码。

为表示源代码，CodeDOM 元素相互链接以形成一个数据结构（称为 CodeDOM 图），它以某种源代码的结构为模型。

System.CodeDom 命名空间定义可表示源代码逻辑结构（与具体的编程语言无关）的类型。System.CodeDom.Compiler 命名空间定义从 CodeDOM 图生成源代码的类型，以及在受支持的语言中管理源代码编译的类型。编译器供应商或开发人员可以扩展受支持语言的集合。

当程序需要用多种语言为程序模型或者为不确定的目标语言生成源代码时，与语言无关的源代码建模很有价值。例如，如果语言的 CodeDOM 支持可用，则一些设计器将 CodeDOM 用作语言抽象接口，以用正确的编程语言生成源代码。

.NET Framework 中包含 C#、JScript 和 Visual Basic 的代码生成器和代码编译器。

还有这一段：

MSDN 写道

.NET Framework 开发人员指南
使用 CodeDOM
CodeDOM 提供了表示许多常见的源代码元素类型的类型。您可以设计一个生成源代码模型的程序，使用 CodeDOM 元素构成一个对象图。可以使用受支持的编程语言的 CodeDOM 代码生成器，将该对象图呈现为源代码。CodeDOM 也可以用于将源代码编译成二进制程序集。

CodeDOM 的一些一般用途包括：

• 模板化代码生成：生成 ASP.NET、XML Web 服务客户端代理、代码向导、设计器或其他代码发出机制的代码。
• 动态编译：支持以一种或多种语言进行代码编译。

CodeDOM分为两部分：“CodeDOM tree”和“provider”。所谓CodeDOM tree就是一棵语言中性的AST，用于表示欲生成的源代码；所谓provider则是语言特定的、将CodeDOM tree转换为实际源代码或者编译为二进制程序集的程序。

CodeDOM tree的类层次图：


CodeDOM在.NET Framework中有重要的作用，许多.NET开发者或许在不知不觉当中已经使用了CodeDOM。WinForms设计器、WPF设计器、WF设计器、AST.NET、wsdl.exe、xsd.exe、resgen.exe、LINQPad等程序都使用CodeDOM来做代码生成和/或编译。事实上IronPython 1.x也实现了一个CodeDOM provider来支持WinForms和WPF设计器（还有一定程度的ASP.NET支持）。

如上面引用的文档所述，CodeDOM是用于动态生成代码的。这个“代码”既可以是人可阅读的源代码，也可以是CLR可以执行的二进制程序集。在LINQ出现前，有许多人通过.NET Framework自带的CodeDOM代码编译器来动态编译C#或VB.NET的源代码，省去了自行解析源代码然后用System.Reflection.Emit来生成程序集的麻烦。我的blog上之前也有一个简陋的计算器的例子是用这个方法的。

从动态生成可执行代码的角度看，CodeDOM与LINQ和DLR有交集，实际上却有非常大的差异：CodeDOM的首要目标是生成人可阅读的源代码，生成可执行的程序集只是副产品；而LINQ与DLR的Expression tree都是用于执行的，即便LINQ查询最终实现为Web Service调用或者SQL查询也好，那也是“执行”用的。这就造成CodeDOM tree的设计与LINQ/DLR tree有根本的不同。
无论从哪方面来看，CodeDOM tree都比Expression tree更接近源代码；CodeDOM甚至包括了表示注释的节点类型，显然与生成可执行代码无关。
CodeDOM支持的语言结构的范围也与LINQ/DLR tree大有差异。CodeDOM支持命名空间、类型、成员域、方法、属性、事件的声明，支持语句和表达式；但有明显的C#倾向，而且每种语言结构的支持都很有限，例如它甚至不支持按位操作、不等关系运算符和一元运算符。当前的LINQ Expression tree只支持非赋值的表达式，有明显的C# 3与VB9的影子。当前的DLR在LINQ Expression tree的基础上扩充了许多，原则上能支持任何语言的任何语法结构，但默认情况下它不支持生成CLR类。
CodeDOM用于生成可执行代码时，只能生成完整的程序集，即便你要的只是里面的一个方法；LINQ Expression tree会被转换为许多不同的形式，或在本地或远程执行；DLR tree默认会被编译为MSIL在本地执行，也可以通过解释器来解释执行。

就动态生成人可阅读的源代码而言，CodeDOM在.NET Framework中的地位还是不可动摇的。而在动态生成一小段可执行的代码方面，相信LINQ/DLR tree能提供更便捷的支持。

相关链接：
MSDN的CodeDOM文档：
.NET Framework 常规参考 - CodeDOM 快速参考
BCL Team Blog：
An intro to CodeDom [David Gutierrez]
Language features which can’t be expressed using CodeDOM in Whidbey. [Vinaya Bhushana Gattam Reddy]
MSDN Forums：
CODEDOM: Limitations of Codedom
Don McCrady：
CodeDom Quirks
CodeProject：
C# CodeDOM parser


DLR tree与Common Compiler Infrastructure（CCI）

Project 7与CCI

事实上，除了CodeDOM和LINQ/DLR tree外，.NET Framework标准库里还应该有一个库是与编译器、AST等内容相关的。说“应该”，是因为确实有这么一个库，出自微软研究院，而且主命名空间在System.Compiler；但实际上它却没有跟随.NET Framework一起发布，外界却对它十分陌生。

这个神秘的库叫做Common Compiler Infrastructure（CCI）。
既然CLR是“公共语言运行时”，不只应该支持微软自己实现的语言（Managed C++、C#、VB.NET、JScript.NET、J#），还应该能支持多种第三方实现的语言。为了证明这是可行的，应该是在.NET还没正式发布的时候（1999年？），微软就与一些合作伙伴开始研究在CLR上实现各种风格迥异的语言，静态/动态类型、过程式、面向对象、函数式，等等。这就是传说中的Project 7。许多现在被外界熟知的语言实现相关项目都与这个计划相关，包括微软研究院的F#、澳洲昆士兰大学的GPPG、GPLEX、VSX的Managed Babel、ETH Zurich的Zonnon等许多项目在内。后来还有Project 7+作为后续计划。这两个计划的对外没怎么宣传过，外界只能看到一些零星的消息来得知计划的存在。

在这些项目中，有一个项目是以“如何让.NET和Visual Studio成为语言创新的平台”为题的。这就是微软研究院的CCI。概念上说它应该是.NET Framework的一部分。
CCI有两大目标：
1、为语言实现提供公共基础设施；
2、简化语言实现与Visual Studio的整合。
公共基础设施方面，CCI提供了一套丰富的AST类层次作为中间表示（Intermediate Representation），可以表示现代语言中的常见语法结构，当然还是以C#为原型来设计的；同时还提供了一组转换器（Transformer），以visitor的形式将IR转换为MSIL。通过这些转换器，语言实现者在写编译器的时候就不需要直接面对System.Reflection和System.Reflection.Emit了。有没有留意到跟前面介绍的几个库的相似性？直接使用System.Reflection.Emit来操纵IL是件痛苦的事，不然也不会出现这么多库来对它封装。

早期CCI的功能分布在System.Compiler.dll、System.Compiler.Framework.dll和babelservice.dll三个程序集里。

这似乎是个很好的库，但为什么没有发布出来呢？我不理解。现在要得到CCI基本上就是两个途径：从FxCop里获取Microsoft.Cci.dll，或者从Zonnon获取System.Compiler.dll系列。要注意的是微软不允许Microsoft.Cci.dll的再发布。所以如果要在自己的程序中使用它的话，多半只能让用户装FxCop来获得这个程序集了。

虽然没有被发布出来，它的许多内容现在还存在于发布了出来的库之中。例如，CCI的System.Compiler.Framework.dll里有一个System.Compiler.IScanner接口，里面有个方法的名字很长，叫做ScanTokenAndProvideInfoAboutIt()。留意Visual Studio 2008 SDK中Managed Package Framework（MPF）的Microsoft.VisualStudio.Package.IScanner接口，可以看到一模一样名字的方法。要是这只是巧合那也真是太巧了。我是看到这个方法名才发觉CCI与MPF有关联，然后发现它们之间有许多部分都十分相似。

LINQ Expression tree与CCI也有那么点相似的地方，主要是在visitor的设计方式上。
在C++、Java和C#等面向对象的语言中，visitor模式一般是以double-dispatch的方式来实现的。简单来说，visitor对象对每个可能访问到的类都有一个对应的visit()方法，而所有可能被访问的类上则有一个接受访问的accept()方法。在使用时，外部调用obj.accept(visitor)，在这个accept()方法里再调用visitor.visit(this)。要做得这么麻烦是因为这些语言的函数多态都只支持single-dispatch，也就是只对方法的接收者（“.”之前的那个对象……）的实际类型多态，而不对其它参数的实际类型多态。这样当我们用一个基类型的变量指向一个派生类型的对象，然后把这个变量作为参数直接传给visitor的visit()方法的话，实际调用的visit()方法就会是对应基类型而不是对象的实际类型的版本。如果语言支持multiple-dispatch/multimethod的话就完全省去了这个麻烦。
但是CCI的visitor却不是这样设计的。CCI的IR类上都有一个NodeType属性来表明自己的节点类型。Visitor上有一个总的Visit()方法，通过switch-case判断出节点类型后，再分发给具体的VisitXXX()方法。这也是实现double-dispatch的一种办法。与一般做法相比，这种方法将double-dispatch的逻辑集中在了一个地方；是好是坏就见仁见智了。
巧合的是，LINQ Expression tree与CCI采取了十分相似的方式来实现visitor，同样是在让节点带有NodeType属性，通过switch-case来分发到具体的visit方法。DLR tree与LINQ Expression tree合并后，自然也采取了同样的做法。注意到早期的DLR tree并不是这样设计的，而是与IronPython AST一样采取了常规做法，在每个AST类上都有Walk()方法（对应accept()）。
这个设计的相似点不知道是巧合还是LINQ确实受到过CCI的影响；它们在其它方面的设计的差异还是挺大的。

CCI IR的类层次图：（对应Zonnon 1.0.89里的CCI）

（这个缩略图比较窄……没办法，图的高度太大。看不见缩略图的话点这里看原尺寸的图。）

多么庞大的类层次。与DLR tree的类层次形成了鲜明的对比；CCI走的路就是尽可能直接覆盖更多的语言结构，在没有合适的对应物时也留下没那么直接的解决办法。从Zonnon的实现来看，CCI IR的这种设计似乎并没有带来显著的好处——Zonnon编译器会先解析生成一个Zonnon自身的AST，进行一系列检查和处理后再转换为CCI IR。结果这流程跟DLR推荐的流程是一样的。如果DLR能添加一些用于声明CLR类、接口等的辅助函数，或许就能以十分精简的AST类层次达到CCI的功能水平。

至于CCI与CodeDOM，CCI是可以完全替代掉CodeDOM的，只要有人肯为CCI写provider。引用一个关于VSTS的介绍的资料：

引用

The Microsoft.Cci assembly, or Common Compiler Infrastructure, originated from Microsoft Research and contains classes that provide features for language-based tools, such as compilers. This assembly is especially helpful for code analysis because it offers many classes that map directly to common programming constructs such as classes, fields, members, and methods. You’ll use these classes to inspect target assemblies to identify the places where your rule applies.

You may be familiar with the System.CodeDom namespace. It is very useful for creating intermediate representations of programming constructs and then using a language provider to generate code in a desired language, such as VB.NET. Microsoft.Cci, conversely, offers additional features for reading and inspecting existing code, exactly the task we face when creating a code analysis rule.

相关链接：
一个介绍CCI的演示稿（PPT）：Common Compiler Infrastructure

===========================================================================

（*） Generator<TDelegate>()与Lambda<TDelegate>返回的类型是Expression<TDelegate>。这段小程序没有处理泛型类型的名字，所以会显示Expression`1。上面我稍微编辑了一下。

前面版本的代码生成出来的信息本来没那么多，我只写了显示方法名的逻辑，没显示返回值类型的部分。我一边写这篇东西一边觉得有点郁闷，干脆改了改，变成这样：
extract_factory_methods.cs:

extern alias dlr;

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using Ast = dlr::System.Linq.Expressions.Expression; 

static class Program {
    static IEnumerable<string> GetPublicStaticMethodsAndWriteToLog(
        Type objType, string logFileName ) {
        var methods = from method in objType.GetMethods(
                          BindingFlags.Public | BindingFlags.Static )
                      where method.ReturnType.IsSubclassOf( objType )
                      group method by method.Name into methodGroup
                      orderby methodGroup.Key
                      select methodGroup.Key;
        using ( var log = File.CreateText( logFileName ) ) {
            foreach ( var name in methods ) {
                log.WriteLine( name );
            }
        }
        return methods;
    }

    [STAThread]
    static void Main( string[ ] args ) {
        var linqFactories = GetPublicStaticMethodsAndWriteToLog(
            typeof( Expression ), "LINQ_Expression.txt" );
        var dlrFactories = GetPublicStaticMethodsAndWriteToLog(
            typeof( Ast ), "DLR_Expression.txt" );
        
        var allFactories = from method in dlrFactories.Union( linqFactories )
                           let isInLinq = linqFactories.Contains( method )
                           let isInDlr = dlrFactories.Contains( method )
                           let retType = ( from m in typeof( Ast ).GetMethods(
                                             BindingFlags.Public | BindingFlags.Static )
                                           where m.Name == method
                                           select m ).First( ).ReturnType.Name
                           select ( isInLinq && !isInDlr ) ?
                                   string.Format( "- {0,-19}: {1}", method, retType ) :
                                  ( !isInLinq && isInDlr ) ?
                                   string.Format( "+ {0,-19}: {1}", method, retType ) :
                                   string.Format( "  {0,-19}: {1}", method, retType );
        foreach ( var method in allFactories ) {
            Console.WriteLine( method );
        }
    }
}

评论

3 楼 cajon 2008-09-27  

@FX
你要迁移到博客园去了，确实很高兴。前几天第一次看到你的文章的时候，我就想建议你迁移的。但是，当时，JavaEye不允许我发表评论。等三天期限到了的时候，就把这事忘掉了。呵呵。

但是，最近博客园的一些调整导致RSS全文输出似乎有问题（不知道你在意不在意，我是很在意），我觉的JavaEye的注册三天不孕评论实在太烂了，但是他的RSS全文输出以及其中的那个“>有0人评论过×猛击×这里发表你的评论<”的功能我很喜欢。如果没有那个链接，也许我们的互动就建立不起来了:)

呵呵，关于我的项目，并不像你想想的那么高深。可能我的能力有限吧。:)更多的细节不能在这里讨论了。如果可以，请在我的博客上留言，留下邮箱，我们通过邮件讨论。

2 楼 RednaxelaFX 2008-09-27  

@Colin
谢谢阅读！文字方面我一直很虚，有些地方自己读都觉得不通顺，但又想不出更好的写法。要是能有什么建议的话就好了 ^ ^
现在DLR的API还比较不稳定，包括hosting API在内都还在变，我觉得现在很难有效的做具体开发。但是现在摸索概念性的东西还是适合的，毕竟DLR的内涵概念已经成形了。

先前在博客园读过您的文章，不过还没能深入理解您在做的尝试在实际项目应用的目的。我觉得您所要实现的实际上就是一个DLR的动态类型系统，虽然没有IronPython和IronRuby等采用的那么复杂，但确实是朝着那个方向在发展。如果您准备自己管理自己的对象的动态特性（也就是实现一个基于DLR的动态类型系统），那么实现IDynamicObject接口是最好的办法。DLR会通过IDynamicObject得到一个对象的MetaObject，然后在每个调用点调用MetaObject上的对应方法（例如说GetMemberAction）。实现了这个接口的话DLR的所有语言都能以你希望的方式使用你的对象。

我刚在博客园申请了帐号，过段时间会开始迁移吧。不过那边的编辑器我用得很不习惯，对UBB代码支持的好弱……还需要请教请教

- RednaxelaFX

1 楼 cajon 2008-09-26  

老大的文字功夫真是了得（当然，不能和你对AST方面的了解相比较）

学到了很多东西。最佩服的是你能够将所有相关的东西综合起来讨论。

我最近正打算将DLR嵌入到我们的产品中去。同时，我希望能够同时支持C#和VB.NET。呵呵，思绪还很乱。有时间我们讨论讨论。

Colin Han (http://cajon.cnblogs.com)