随笔-341  评论-2670  文章-0  trackbacks-0

C#或者Haskell这样的先进的语言都有一个跟语法分不开的最核心的库。譬如说C#int,是mscorlib.dll里面的System.SInt32Haskell(x:xs)则定义在了prelude里面。Vczh Library++ 3.0ManagedX语言也有一个类似mscorlib.dll的东西。之前的NativeX提供了一个核心的函数库叫System.CoreNative (syscrnat.assembly),因此ManagedX的就命名为System.CoreManaged (syscrman.assembly)System.CoreManaged里面的预定义对象都是一些基本的、不可缺少的类型,例如System.SInt32System.IEnumerable<T>或者System.Reflection.Type。昨天晚上我的未完成的语义分析器的完成程度已经足以完全分析System.CoreManaged里面的托管代码了,因此符号表里面的类型系统也基本上是一个完整的类型系统。在开发的过程中得到的心得体会便是写着一篇文章的来源。

 

如今,先进的面向对象语言的类型都离不开下面的几个特征:对象类型、函数类型和接口类型。修饰类型的工具则有泛型和延迟绑定等等。譬如说C#,对象类型便是object,函数类型则有.net framework支持的很好,但是不是核心类型的FuncAction,接口类型则类似IEnumerable。泛型大家都很熟悉,延迟绑定则类似于dynamic关键字。var关键字是编译期绑定的,因此不计算在内。Javaint是魔法类型,其设计的错误已经严重影响到了类库的优美程度,其使用“类型擦除”的泛型系统也为今后的发展留下了一些祸根,因此这些旁门左道本文章就不去详细讨论了。这篇文章讲针对重要的那三个类型和两个修饰进行讨论,并解释他们之间互相换算的方法。

 

C#里面,函数类型也是对象类型的一部分,但是由于C#可以在编译过程中把一个不完整的函数类型推导为一个完整的函数类型,因此在这里将它和对象类型区分开来。Haskell则在推导上做得更加彻底,这都是先进的有类型语言所不可缺少的一个特征。由于类型之间的互相换算是本文所关心的内容,因此下面先给出几个定义。当然这些定义在数学上是不严谨的,而我也并不追求这个。namespace在这里也不是非常重要,因为存在namespace和不存在namespace所带来的区别仅仅是一个对象被如何解释(黑话称之为Resolving),并不影响推导过程。

 

我们可以将一个类型命名为T,它是不带泛型的。一般来说,因为类型存在成员函数,所以类型便有几个基本的属性,称之为this类型和base类型(在C#,代表自己的关键字分别是thisbase)。this指的是类型T的成员函数所看到的自己的类型。而base类型则是父类的类型。在这里有必要做出一点解释。只有对象类型才具有base类型,而且其base类型指的是所有父类中唯一一个不是接口类型的那个。函数类型和接口类型都有this类型。

 

因此对于任何一个具有下面描述的类型T

class T : U, I1, I2, I3{}

this(T) == T

base(T) == U

 

现在让我们来考察一个带泛型的类型声明T[U, V],和他的实例化类型T<A, B>之间的关系。我们知道,一个带泛型的类型声明T[U, V]实际上是一个不完整的类型,因为这个类型还有UV两个参数待填,正如下面的代码所示:

class T<U, V>{}

而当你实例化他之后,令U==AV==B,则T类型被AB实例化成了T<A, B>。这就有点象我们把一个Dictionary[K, V]给实例化成Dictionary<int, string>一样。一个实例化后的类型才可以被当成另一个泛型类型的类型参数,或者直接使用它来定义一些符号,或者创建一个它的实例等等。但是不完整的泛型类型T[U, V]和它的实例化类型T<A, B>都具有共同的属性——this类型和base类型。按照上面的定义,this类型是该类型的成员函数所看到的自己的类型。

 

因此对于任何一个具有下面描述的类型T[U, V]

class T<U, V> : W<U, V>{}

this(T[U, V]) == T<U, V>

base(T[U, V]) == W<U, V>

 

当然,对于T<A, B>来说,它也具有this类型T<A, B>base类型W<A, B>。一般情况下,非泛型类型T的声明可以被处理成T[],我们令T[]等于T<>,就可以将所有泛型类型的规则实例化到一个带有0个泛型参数的泛型类型——也就是非泛型类型上面了。因此下面的讨论将不作区分。

 

现在我们考虑如何获得一个泛型类型的所有成员的类型。我们考虑下面的一组类型:

 

interface IEnumerable<T>

{

    IEnumerator<T> GetEnumerator();

}

 

class Base<T> : IEnumerable<T>

{

    public T Value{get; set;}

}

 

class Derived<T, U> : Base<U>

{

}

 

我们来考虑一个问题:如何知道Derived<int, string>GetEnumerator函数的返回值类型是什么呢?乍一看似乎很简单,其实对于人类来说这个问题的确是仅靠直觉就可以瞬间回答出来的、根本没有任何障碍的问题了。这里我一直佩服大自然可以将人类进化到如此牛逼的地步。不过这个问题困扰了我很久,主要是在开发语义分析器的时候,安排各种各样的类型运算、符号表的结构和其它的一些相关问题的时候,这个问题的难度就提高了。

 

不过在这里我并不想多说什么废话,我们仅需要给类型对增加几个属性和运算规则,就可以很容易的将这个问题组合成一个表达式了。

 

首先,我们需要有一个replace操作。replace操作很难一下子严谨的定义出来,不过可以给一个直观的定义,就是:

replace(Derived<T, U>, {T=>int, U=>string}) == Derived<int, string>

相信大家已经可以很轻松的理解了,因此对于一个类型映射tm={T=>string}来说,replace(Derived<IEnumerable<T>>, tk)的结果就是Derived<IEnumerable<string>>了。

 

其次,我们需要一个decl操作,这个操作返回一个泛型类型的实例类型的定义:

decl(T<A, B>) == T[U, V]

 

然后,我们还需要一个params操作。这个操作将一个泛型类型的实例类型和他的泛型定义相比较,提取出可以从泛型定义replace到实例类型的那个类型映射:

params(T<A, B>) == {T=>A, U=>B}

 

因此一般来说,我们有下面的规则。只要类型T是一个泛型类型的实例类型,那么总是有:

replace(this(decl(T)), params(T)) == T

 

现在我们就可以开始回答上面提到的那个问题了。

首先对于类型Derived<int, string>,我们需要找到他的父类。因此我们可以做如下几步操作:

tm = params(Derived<int, string>) = {T=>int, U=>string}

tb = base(decl(Derived<int, string>)) = base(Derived[T, U]) = Base<U>

result = replace(tb, tm) = replace(Base<U>, {T=>int, U=>string}) = Base<string>

这样我们就成功求出T=Derived<int, string>的父类B=replace(base(decl(T)), params(T))=Base<string>

 

其次,我们指定要计算类型Base<string>所继承的那个接口Base[T]=>IEnumerable<T>,我们可以使用

tm = params(Base<string>) = {T=>string}

result = replace(IEnumerable<T>, tm) = IEnumerable<string>

因此对于一个泛型声明decl(T)所继承的一个接口Id,泛型声明D的实例类型T所对应的接口It等于replace(Td, params(T))

 

因此对于IEnumerable[T]的函数GetEnumerator的返回值类型IEnumerator<T>,聪明的读者肯定想到,IEnumerable<string>所对应的类型就是replace(IEnumerator<T>, params(IEnumerable<string>)) == IEnumerator<string>了。这个结果跟求实例类型所继承的接口类型的方法一样。

 

我们可以知道,在计算泛型类型的实例类型的成员类型中,我们总是不断地在计算replace(A, params(B))的结果。因此在我实现的带泛型的面向对象托管语言:Vczh Library++ 3.0ManagedX语言的语义分析器的符号表的代码里面,真实出现了使用C++所完成的thisbasedeclparamsreplacereplace_by_type = replace(A, params(B))这样的六个函数。因为在C++里面,一个类型的实例只能被表示为一个带有复杂结构的对象的指针。因此只要符号表在计算类型的过程中,把所有产生出来的类型保存下来,建立索引,并且使得“只要类型A和类型B是同一个类型则有他们的指针P(A)P(B)相等”的这个条件恒成立的话,类型系统的计算速度将直接提高。

 

至于函数类型的推导法则(主要是应用于lambda表达式的缩写语法),则等到我开发到那里的时候再写后续的文章了。System.CoreManaged有幸不需要使用lambda表达式,使得我的第一个里程碑提前到来。

posted on 2011-09-27 21:54 陈梓瀚(vczh) 阅读(5906) 评论(4)  编辑 收藏 引用 所属分类: VL++3.0开发纪事

评论:
# re: 浅谈面向对象语言的类型运算 2011-09-28 15:48 | DiryBoy
Orz!! 貌似C#对Open Generic Type的写法是T<,>,而不是用中括号  回复  更多评论
  
# re: 浅谈面向对象语言的类型运算 2011-09-29 02:26 | 陈梓瀚(vczh)
@DiryBoy
为了把参数名也一起写出来没办法了  回复  更多评论
  
# re: 浅谈面向对象语言的类型运算 2011-09-29 08:51 | 空明流转
OK,这个不错。。。。  回复  更多评论
  
# re: 浅谈面向对象语言的类型运算 2012-06-13 09:06 | 我的大名
真有这么麻烦啊?!  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理