2005年12月17日

[ 绝对原创,谢绝转载]

注意 :第一部分Python总体架构采用了网络文档The Architecture of Python》,这是网络上唯一可见的以剖析Python实现为己任的文档。可惜是作为一门课程的作业的结果,太简略了,有点“食之无味,弃之可惜”的感觉。这里借用其介绍Python总体架构的部分,比较简略,以后我会再充实。


Python源码剖析

——编译Python

本文作者: Robert Chen(search.pythoner@gmail.com)


1.      Python总体架构

在最高的层次上,Python的整体架构可以分为四个主要的部分,整个架构如图1所示。在左边,是Python提供的大量的模块,库以及用户自定义的模块。比如在执行import os时,这个os就是Python内建的模块,当然用户还可以通过自定义模块来扩展Python系统。在本系列文章中,我们不会对这一部分进行过多的考察。

   

在图的右边,是Python的运行时环境,包括对象/类型系统(Object/Type structures),内存分配器(Memory Allocator)和运行时状态(Current State of Python)。运行时状态维护了解释器在执行字节码时在不同的状态之间切换的动作,我们可以将它视为一个巨大而复杂的有穷状态机。内存分配器则全权负责Python中创建对象时对内存的申请工作,实际上它就是Python运行时与Cmalloc的一层接口。而对象/类型系统则包含了Python中存在的各种内建对象,比如整数,listdict等等

   

在中间的部分,可以看到Python的核心,解释器(interpreter)。在解释器中,箭头的方向指示了Python运行时的数据流方向。其中Scanner对应词法分析,将文件输入的Python源代码或从命令行输入的一行行Python代码切分为一个一个的tokenParser对应语法分析部分,在Scanner的分析结果上进行语法分析,建立抽象语法树(AST);Compiler是根据建立的AST生成指令集合——Python字节码(byte code),就像Java编译器和C#编译器所做的那样;最后由Code Evaluator来解释并执行这些字节码。因此,Code Evaluator又可以被称为执行引擎。

   

图中,在Interpreter与右边的对象/类型系统,内存分配器之间的箭头表示“使用”关系;而与运行时状态之间的箭头表示修改关系,即Python在执行的过程中会不断地修改当前解释器所处的状态,在不同的状态之间切换。

   



2.      Python源代码的组织

中国有句老话,巧妇难为无米之炊。要分析Python源码,首先当然要获得Python源码。Python源码可以从Python的官方网站http://www.python.org自由下载。当前Python的最新版本是2.4.2,在本书中,我采用的是Python2.4.1

   

下载了Python的源代码压缩包并解压后,可以看到如图3所示的目录结构。

Include :该目录下包含了Python提供的所有头文件,如果用户需要自己用CC++来编写自定义模块扩展Python,那么就需要用到这里提供的头文件。

Lib :该目录包含了Python自带的所有标准库,Lib中的库都是用Python语言编写的。

Modules :该文件夹中包含了所有用C语言编写的模块,比如ramdomcStringIO等,Modules中的模块是那些对速度要求非常严格的模块。而有一些对速度没有太严格要求的模块,比如os,就是用Python编写,并且放在Lib目录下。

Parser Parser目录中包含了Python解释器中的ScannerParser部分,即对Python源代码进行词法分析和语法分析的部分。除了这些,Parser目录下还包含了一些有用的工具,这些工具能够根据Python语言的语法自动生成Python语言的词法和语法分析器,与YACC非常类似。

Objects :该目录中包含了所有Python的内建对象,包括整数,listdict等;同时,该目录还包括了Python在运行时需要的所有的内部使用对象的实现

Python :该目录下包含了Python解释器中的Compiler和执行引擎部分,是Python运行的核心所在。

PCBuild :包含了Visual Studio 2003工程文件,研究Python源代码就从这里开始。

3.      编译Python

好了,下载了Python的源代码之后,我们就可以走出剖析Python源码的第一步——编译Python——了:)

   

Python2.4.1是在Visual Studio 2003环境下开发的,在PCBuild目录下可以看到VS2003的工程文件,打开工程后,还需要进行一些设置,才能成功编译。

   

首先,我们需要激活VS2003的配置对话框:

   

在配置对话框中,首先要做的就是更改Startup ProjectPython2.4.1中默认设置的是_bsddb,我们需要将其改为Python   

   

   

由于我们剖析的只是Python的核心部分,不会涉及到工程中的一些标准库和其他的模块,所以我们需要将它们从编译的列表中删除。点击配置对话框左边列表框中的“Configuration Properties”后,会出现当前配置为需要编译的子工程,取消多余的子工程的选中状态,只保留pythoncorepython的选中状态。

    需要进行的改动就是这么多了,但是完成这些改动后,如果马上开始编译,那么编译还是会失败:

原因是我们还需要一个pythonnt_rc_d.h,这个文件在Python2.4.1的源码包中没有提供,必须要通过一个编译make_versioninfo子工程才能自动生成:               

               

好了,现在再编译,一切都会顺利完成了。

2005年12月16日
Spy是我正在开发的一个Python的实现,作为对这段时间剖析Python源码的副产品。
                                                  
当然,我还是有点野心的,希望在这个Spy中能利用C++的一些东西来实现,速度不一定要有CPython那么快,但是要足够清晰,易理解,实际上,我希望这个小东西能够成为对动态语言实现感兴趣的人的起点,所以这个东西对于教育的意义要大于实用的目的 :)
                                                  
当然,我还有更大的野心,通过对Python代码的分析,我发现其实Python的对象体系,比如int, dict,list等的实现真的是殚精竭虑,榨尽了系统的最后一点效率;但是字节码解释器中还有很多地方可以进行优化,而且对Python编译器生成的字节码本身的优化也有很大的空间。国外有Pysco就是致力于这方面的研究,不过其作者的兴趣已经转移,到了Python界正在崛起pypy上,在pypy中,优化是一个重要的话题。我希望在开发Spy的过程中,同时学习pypy,研究Python的执行效率优化。
                                                  
当前Spy只实现了字节码解释器,而这个解释器也只是初具雏形。Spy的前端编译是利用Python来实现的,调用Python本身编译.py源文件,得到.pyc文件,然后解析.pyc文件,继而解释.pyc文件中包含的字节码。
                                                  
现在的Spy已经可以处理如下的简单Python文件了:
a = 456
b = 123
c = a – b
print c
                                                  

对于Spy,你可以叫它“Small Python”,“Simple Python”,或者“Smile Python”,甚至“So fast Python”(当然,这是我的梦想 :)
                                                  
Spy的输出结果如下。Spy会按照执行顺序输出字节码,并在执行完一条字节码后输出当前运行时栈中的内容,一个方格表示栈中一个元素,方格个数为栈的大小,而右边的箭头指向当前栈顶。呵呵就算不了解Python的内部实现,仔细看一看,是不是对Python解释器的工作原理有那么一点点的心得了呢 :)
                                                  
LOAD_CONST 0
——————————————–
| <int 456>
——————————————–  <—
|
——————————————–
                                                  
STORE_NAME 0
——————————————–  <—
|
——————————————–
|
——————————————–
                                                  
LOAD_CONST 1
——————————————–
| <int 123>
——————————————–  <—
|
——————————————–
                                                  
STORE_NAME 1
——————————————–  <—
|
——————————————–
|
——————————————–
                                                  
LOAD_NAME 0
a
——————————————–
| <int 456>
——————————————–  <—
|
——————————————–
                                                  
LOAD_NAME 1
b
——————————————–
| <int 456>
——————————————–
| <int 123>
——————————————–  <—
                                                  
BINARY_SUBTRACT 1
——————————————–
| <int 333>
——————————————–  <—
|
——————————————–
                                                  
STORE_NAME 2
——————————————–  <—
|
——————————————–
|
——————————————–
                                                  
LOAD_NAME 2
c
——————————————–
| <int 333>
——————————————–  <—
|
——————————————–
                                                  
PRINT_ITEM
333
                                                  
PRINT_NEWITEM
                               
                                                  
LOAD_CONST 2
——————————————–
| <none>
——————————————–  <—
|
——————————————–
                                                  
RETURN_VALUE
2005年12月14日

在limodou的blog中,提到了一个有趣的问题:if 0 in [True, False]:是什么?这里是从Python的source code出发,对这个问题的解答。limodou用了个0,我用了个1,不过没有关系,原理都是一样的。

Python语句 if 1 in [Ture, False],在编译后,最后有一条关键的字节码

COMPARE_OP 6

后面的6表明了比较操作的类型,在Python中,定义为常量PyCmp_IN。在Python的解释器执行COMPARE_OP 6的过程中,会通过cmp_outcome进入判断一个元素是否在list中的函数:

[ceval.c]

static PyObject *



cmp_outcome(int op, register PyObject *v, register PyObject *w)



{



    int res = 0;



    switch (op) {



    ……


    case PyCmp_IN:



        res = PySequence_Contains(w, v);



        if (res < 0)



            return NULL;



        break;



    ……


    }



    ……



}



PySequence_Contains中,会逐个检查list中的元素,判断每个元素是否与1相等。最终的检查路径会进入到try_3way_compare

[object.c]


static int try_3way_compare(PyObject *v, PyObject *w)



{



    int c;



    cmpfunc f;





 

    f = v->ob_type->tp_compare;



    ……


    /* If both have the same (non-NULL) tp_compare, use it. */



    if (f != NULL && f == w->ob_type->tp_compare) {



        c = (*f)(v, w);



        return adjust_tp_compare(c);



    }



    ……


}



在这里,会检查v1)的类型对象(ob_type)中所定义的比较操作(tp_compare)是否与wTrue)的一致,如果一致,则利用这个比较操作进行比较。1True正是在这里比较成功的。

那么这个tp_compare究竟是什么呢,我们需要看一看1TruePython中分别对应何种对象。

Python中,1对应一个PyIntObject对象,其类型对象ob_typePyInt_Type,在其中,tp_compareint_compare

[intobject.c]


PyTypeObject PyInt_Type = {



    PyObject_HEAD_INIT(&PyType_Type)



    0,


    "int",


    sizeof(PyIntObject),


    ……



    (cmpfunc)int_compare,           /* tp_compare */



    ……



};

有趣的是,在Python中,True也会对应一个PyIntObject对象:

[boolobject.h]


PyIntObject _Py_ZeroStruct, _Py_TrueStruct;





 

/* Use these macros */



#define Py_False ((PyObject *) &_Py_ZeroStruct)



#define Py_True ((PyObject *) &_Py_TrueStruct)





 

[boolobject.c]


PyIntObject _Py_TrueStruct = {



    PyObject_HEAD_INIT(&PyBool_Type)



    1



};

可以看到,这时的类型对象不再是PyInt_Type,而变成了PyBool_Type。也就是说,在try_3way_compare中将比较PyInt_Type中的tp_comparePyBool_Type中的tp_compare是否一致。我们来近距离观察一下PyBool_Type

[boolobject.c]


PyTypeObject PyBool_Type = {



    PyObject_HEAD_INIT(&PyType_Type)



    0,


    "bool",


    sizeof(PyIntObject),


    ……



    0,                  /* tp_compare */



    ……



    &PyInt_Type,                /* tp_base */



    ……



};

很显然,PyBool_Type中的tp_compare根本没有设置,但在try_3way_comapre中的那个比较为什么能成功呢?关键就在PyBool_Type中的tp_base域,这个tp_base表示PyBool_TypePyInt_Type有一种继承的关系。

在启动Python,进行初始化时,会通过inherit_slotsPyBool_Type中的tp_compare设置为PyInt_Type中的tp_compare:

[typeobject.c]

static void inherit_slots(PyTypeObject *type, PyTypeObject *base)



{



    ……



    if (type->tp_flags & base->tp_flags & Py_TPFLAGS_HAVE_RICHCOMPARE) {



        if (type->tp_compare == NULL &&



            type->tp_richcompare == NULL &&



            type->tp_hash == NULL)



        {



            type->tp_compare = base->tp_compare;



            type->tp_richcompare = base->tp_richcompare;



            type->tp_hash = base->tp_hash;



        }



    }



    ……


}

而在那个关键的int_compare中,判断的动作异常简单:

[intobject.c]

static int


int_compare(PyIntObject *v, PyIntObject *w)



{



    register long i = v->ob_ival;



    register long j = w->ob_ival;



    return (i < j) ? -1 : (i > j) ? 1 : 0;



}



回头看看那个_Py_TureStruct,由于它也是一个ob_ival1PyIntObject对象,所以判断成立。

所以if 1 in [True, False]判断成立的根本原因在于1True都是属于PyInt_Type的对象,尽管True是一个间接的PyInt_Type的对象,正是这种联系使得判断得以进行。

Python中,判断两个对象是否equal的操作及其繁复,有的比较操作甚至会引起十几个函数调用,这样的开销是否值得呢?不管如何,在比较时,尽力保证参与比较操作的两个对象的类型相同,这样对Python代码的效率提升是有帮助的

2005年11月19日

VCF真是个好东西,真是个好东西啊~~

最开始用VC和MFC,一开始就觉得不舒服,总感觉编程象在受罪,没有一点舒畅的感觉。自然MFC也是不错的,还能做出很炫的UI,哦,是超炫的UI。可是有什么用呢,我又不是靠MFC混饭吃的。我既然拿编程做一种兴趣,那这玩意儿就要给我带来乐趣,MFC不能,它只能让我郁闷。

后来使用了一段时间Delphi,感觉这家伙好啊,编起代码来很流畅,不过对Object Pascal一直不感冒,这都怪俺肚子里那莫名其妙的C++情结,于是后来连使用VCL的C++ Builder也敬而远之了。

然后是WTL,这个东西从MS诞生,充分证明MFC从美的角度看是个失败的东西,当然市场是不管美不美的,可是一个好的程序员是在乎的。这里说的好的程序员是那种对编程带有某种宗教情结的,视编程为无尚光荣的创造性活动的程序员,而不是那种以捞钱为己任的程序员。当然这仅仅是我对“好”的理解,自然有人会认为生产效率高的程序员或者能解决实际问题大把大把捞钱的程序员才是好的程序员,毫无疑问,这些看法都是正确的,所以罗素说,参差多态是幸福的本源。

对于WTL,我曾经花费了很多的时间和精力,确实比较喜欢它,可惜这玩意只以UI为己任,只以Win32为己任,这让我觉得很不爽,况且我对UI的热情也是间歇性的,后来就慢慢疏远了。

等到对UI的热情再次升起,就想找一个跨平台的库玩玩,很自然,第一个就是大名鼎鼎的wxWidget,这家伙历史悠久,所以包袱也特别沉重,玩了一段时间,觉得编程的时候也不是很痛快,尤其是和STL,Boost等混合的时候,总感觉一手拿着石器时代的武器,一手拿着冲锋枪,很别扭。当然,这只是个人体验,就好像当年笛卡尔曾经被自己冥想时的宗教体验感激得痛哭流涕一样,仅仅对于我自己有意义。

所以我要找一个最近诞生的C++的Framework,它的库没有wxWidget丰富也没有关系,我是拿它来玩的,并不是来赚钱的。于是Win32 GUI Generic出现在我的视野中,是个好东西,对template的应用出神入化,不过现在只关注Win32,所以这点让我不太爽,不过我对它还是大有兴趣的。这一点,我承认,多多少少有点虚荣心在作祟,你知道,在当前的C++界,template这玩意儿简直就是评价智商的标准,你把template玩得越溜,就越会有一点虚荣的满足:)

在我下定决心研究Win32 GUI Generic之前,VCF出现了,这东西诞生也好几年了,我居然现在才知道,这充分说明我的孤陋寡闻,也充分说明互联网对信息的传递的局限性,信息能够自由发布了,可是如何使有用的信息到达真正需要的人的手里,这个是现在的技术不能解决的,这也正是新一代的信息检索系统面临的任务。这种个性化的信息检索系统一旦诞生,Google就玩完了,不过极大的可能性是这种技术在Google诞生,于是Google成功进化,将什么Baidu,Yahoo远远抛在后面。哦,扯远了,扯远了,又扯到自己专业去了 :)

现在我是横下一条心了,要好好玩玩VCF,用这东西编程,就感觉像在用Delphi,Java和C#一样,不光是UI的库,还有很多其他的组件,比如Event,Reflection,Thread等等,可它确确实实是C++的Framework,这不正是我梦寐以求的吗。MMD,终于让我遇上了。

VCF究竟是什么,俺就不介绍了,感兴趣的可以访问它的官方网站:http://www.vcf-online.org/

最后,我还是忍不住,再为VCF做做广告吧:

 "You know how when someone sees something very good they exclaim ‘WOW!’? Then when they see something that is truly inspiring, they say it in a very low, respectful tone? Looking at the quality and breadth of what you have here definitely puts me in the latter category."

Tom Archer Author of: Inside C#, Visual C++ .NET Bible, and Extending MFC Applications with the .NET Framework.

2005年09月05日

发现一篇好东西,关于Python进行文件处理的,不过好像对字符串的操作没有什么介绍。有一本电子书Text Processing in Python》,非常好,专攻Python中的文本处理,作者也是Python社区的牛人,在IBM的developerWorks开有Charming Python专栏,可惜更新太慢。

对于做文本处理方面的朋友,Text Processing in Python尤其对口,以前还打算翻译过来了,贡献给IR Lab,可惜如今身在江湖,有心杀敌,无力回天啊 :)

2005年09月02日

2005年8月28日,安德鲁.怀尔斯访问中国北京大学。怀尔斯是我们这个时代最伟大的数学家之一,关于他,我们只需要知道一件事就会对他深怀敬意:1994年10月,怀尔斯完美地解决了费马大定理。自费马以来,这个猜想在我们的星球上已经延续了358年。

我认为中国的年轻人工作非常努力,希望他们勇于追求自己所挚爱的东西,因为对事业的投入和热爱将使他们在前进的途中所向披靡。 ”这是怀尔斯对中国青年报读者的赠言,非常平实,却是怀尔斯一生的写照。

2005年09月01日

今天看了Python中的符号表的实现,大致很清晰了。Python虽然是动态语言,但在作用域规则上,它选用的是静态作用域,这一点跟C++等其他主流的语言是一样的。

对照《程序设计语言——实践之路》来看Python,呵呵,果然获益匪浅。下一个目标是:字节码的生成。

2005年08月27日

                           新闻会客厅:一夜创富的百度老总李彦宏

开场白有些肉麻呵呵,互联网的泡沫才破了没几年,仅仅是因为咱们中国人也在纳斯达克High了一把,又有人在亢奋地高呼“奇迹,神化”了。李彦宏是个厉害的主,不过那个什么“会客厅”就弱了许多,还非常八卦地几次提及那个前台接线员,没问出什么有价值的东西。路还很长,baidu未来如何,还是要骑驴看唱本——走着瞧的……

2005年08月26日

                                                   传周鸿祎秘密造访中国搜索

互联网永远有创新和功成名就的机会,不过“个人信息门户”真的还是一个遥远的梦想。个性化信息服务的概念并不是什么新鲜货,像Google早就开始新闻定制,现在各大搜索引擎基本都提供这样的服务。然而从技术上将,个性化信息服务实在是比较难的,学术界的研究从很早就起步,至今仍是进展不大。真正的个性化信息服务的底层必须要有对文本的理解,对语义的分析,对内容的判断,这些都是超级难题,现在的研究成果离实用还是很远的。不过这些领域的研究中有一些技术还是比较成熟了,这些技术的加入能够给用户更好的搜索体验,但是离真正的个性化信息服务还是遥远的。在各大力量方在技术上都没有明显领先的情况下,市场策略就显得尤为重要了。可以预见,互联网上的搜索服务会越来越好,有时甚至会给你一点惊喜,然而真正的“个人信息门户”,在未来的几年,我想,还是一个梦想……

2005年08月25日

The Harry Potter Theory of Programming Language Design


Guido把哈里波特的写作和Python的发展联系起来,似乎是在为Python的变革铺路了。向后兼容是个问题,但是Python的变革也势在必行。看看新的Python,interface,static type,变化真的蛮大的。但是跟贴的几位老兄似乎不太喜欢Python变化太大,认为应该语言保持稳定,要把精力放在库上,这跟当前C++社区的精神也是一致的。哈哈不过Guido在Python社区享有“仁慈的独裁者”美誉,后果嘛,嘿嘿。。。。。。