Wednesday, February 18, 2009

[Python]可变长参数

Python支持可变长参数,函数参数中形如*arg这样的就是可变长参数。如果定义了def func(*arg),则可以让接受不同个数的函数,比如func()以及 func("hello", "world")均为合法的函数调用。

下面这个例子用可变长参数调用func并将可变长参数*arg传递给func。比如test(sleep, 1)就相当于 sleep(1);test(max, 1, -1)就相当于调用max(1,-1)。
def test(func, *args, **kargs):
    if not callable(func):
        raise RuntimeError, str(func) + ' not a callable object'
    else:
        func(*args, **kargs)

[Python]Python线程简例

第一部分:最简单的用法


Python提供了非常简单的线程用法。最简单的用法只要遵循下面几步:
  1. 定义一个类(比如下面例子里的Job)继承threading.Thread
  2. 在该类中必须实现__init__(初始化)以及run函数(该线程需要执行的代码).注意在__init__当中要调用Thread.__init__。其他成员函数和变量可以自己根据需要添加。
  3. 用start函数启动线程。
  4. (可选)用join函数来阻塞线程直至线程结束。

若不理解join的作用,可以看如下例子:
import os
import time
from threading import Thread
class Job(Thread):
def __init__(self, cmd):
Thread.__init__(self)
self.cmd = cmd
self.starttime = time.time()
def run(self):
os.popen(self.cmd)
print "time %.2fs, job %s is done"%(time.time()-self.starttime,self.cmd)
jobs = []
for i in range(1, 5):
j = Job("sleep %d"%i)
jobs.append(j)
j.start()
for j in jobs:
j.join()
print "time %.2fs, job %s returned"%(time.time() - j.starttime, j.cmd)

运行得到结果:
time 1.00s, job sleep 1 is done
time 1.00s, job sleep 1 returned
time 2.00s, job sleep 2 is done
time 2.00s, job sleep 2 returned
time 3.00s, job sleep 3 is done
time 3.00s, job sleep 3 returned
time 4.00s, job sleep 4 is done
time 4.00s, job sleep 4 returned

如果我们把最后一个循环的顺序该一下,变成倒叙(如下),其余部分不变
for j in reversed(jobs):
j.join()
print "time %.2fs, job %s returned"%(time.time() - j.starttime, j.cmd)
得到结果:
time 1.00s, job sleep 1 is done
time 2.00s, job sleep 2 is done
time 3.00s, job sleep 3 is done
time 4.00s, job sleep 4 is done
time 4.00s, job sleep 4 returned
time 4.01s, job sleep 3 returned
time 4.01s, job sleep 2 returned
time 4.01s, job sleep 1 returned
所以当你调用join时,仅仅是检查该线程是否以及结束。如果结束则返回;否则阻塞直至结束。
再来作一点变换, 对join加上参数timeout。 timeout指定调用join后多久停止阻塞。如果没有指定该参数(就像我们前面做得这样),则一直阻塞到线程结束:
for j in reversed(jobs):
j.join(0.5)
print "time %.2fs, job %s returned"%(time.time() - j.starttime, j.cmd)

我们得到
time 0.52s, job sleep 1 returned
time 1.00s, job sleep 1 is done
time 1.02s, job sleep 2 returned
time 1.52s, job sleep 3 returned
time 2.00s, job sleep 2 is done
time 2.02s, job sleep 4 returned
time 3.00s, job sleep 3 is done
time 4.00s, job sleep 4 is done

第二部分: 一个例子

在这个例子里面,我们使用指定数目个线程来完成一批任务。就好比1000个矿要采,但我们就只用9个农民轮流去采。

在这个例子里我们定义了一个Jobs类(乔布斯?)和一个Worker类。Jobs类通过继承Queue来维护一个任务队列。如果要添加新任务,就调用newjob。newjob函数的参数决定了一个任务:它们包括一个名字(name),一个函数入口(func)以及相应的参数(args,kargs)。每个Worker类的实例对应一个线程,当线程开始执行或者idle的时候,就从任务队列中取一个任务,并执行这个任务。完成之后再接着做下一个,周而复始直至所有任务完成(任务队列为空)。
class Jobs(Queue.Queue):
def __init__(self):
Queue.Queue.__init__(self)
def newjob(self, name, func, *args, **kargs):
if not callable(func):
raise RuntimeError, str(func) + ' not a callable object'
self.put((name, func, args, kargs))
def do(self, numthreads = 1, debug = True):
threads = []
for i in range(numthreads):
t = Worker("thread%d"%i, self, debug)
threads.append(t)
t.start()
for t in threads:
t.join()

class Worker(threading.Thread):
def __init__(self, name, jobs, debug = False):
threading.Thread.__init__(self)
self.name = name
self.jobs = jobs
self.debug = debug
def run(self):
while not self.jobs.empty():
try:
job = self.jobs.get(True, 1)
(name, func, args, kargs) = job
except:
break
stime = time()
func(*args, **kargs)
if self.debug:
print "%s is done by %s, fin in %.2f s"%(name, self.name, time()-stime

Wednesday, February 11, 2009

[Python] Python中的类型与对象

读了一篇文章Python Types and Objects探讨Python当中的类型与对象。要说这篇文章也算是写的不错,图文并茂的。可是我还是看的迷迷糊糊的。于是又多花了一些时间搞清Python里的关系。

一切都是对象

先从简单的说起
>>>mylist = [1,2,3]
>>>type(mylist)
<type 'list'>
所以这里我们新建了一个list的实例叫mylist。通过内建的type()函数我们可以查看这个实例的类型,返回的结果告诉我们它的类型是list这种内建的类型。
>>>type(list)
<type 'type'>
>>>list.__bases__
(<type 'object'>,)
这里我们先查看了list的类型。我们得知list的类型是type,换言之list是type的一个实例。紧接着我们用__bases__属性查看它的父类,得知list其实继承了内建的object。再来
>>>type(type)
<type 'type'>
>>>type.__bases__
(<type 'object'>,)
好,现在我们知道type的类型还是type自己,它是自己的一个实例,同时它继承了object。最后:
>>>type(object)
<type 'type'>
>>>type.__bases__
()
从而我们得知,object也是type的一个实例,同时它没有父类。

总结一下目前的结论:
  • Python当中任何东西都是对象,它都要对应一个类型
  • 为了表达这个类型,Python仍然使用了对象。所以int, list这些类型同时也都是对象。比方你可以用id(int),id(list)得到这些类型的id(其实是这些对象的内存地址)
  • 为了得到统一的解释(每个对象都对应一个类型),便赋予int, list对象以一个type类型。type自己也是一个对象
  • type的类型是自己,这个游戏从而可以结束了。
  • object也是一种类型,可以类比于int, list。但是由于每样东西都是对象,所以int, list, type这些抽象的类型落实到instance以后又都是object派生出来的。
class 和 type 的统一

在Python2.2之前,class和type是阳关道和独木桥,互不相干。这种class也被称为老式类(old-style class)。从Python2.2之后开始,class可以被认为是一种用户自定义的类型,也被称为新式类(new-style class)。从地位上来说和list或者dict等类型一样。为兼容起见老式类依然被保留,并认为是一个类默认的类型。如果你要定义一个新式类,该类必须继承object,或者继承一个其他新式类。(注:Python3.0以后将不再支持老式类)

现在让我们作一下实验,分别定义一个老式类 oldclass和一个新式类 newclass:
>>>class oldclass:
...    def __init__(self):
...        pass
>>>class newclass(object):
...    def __init__(self):
...        pass

检验一下:
>>>oldobj = oldclass()
>>>newobj = newclass()
>>>print type(oldobj), oldobj.__class__
<type 'instance'> <class __main__.oldclass at 0x7f700714da10>
>>>print type(newobj), newobj.__class__
<class '__main__.newclass'> <class '__main__.newclass'>

这里我们可以看到新式类的类型和__class__是统一的。再来检验一下内建的dict:
>>>print type(dict), dict.__class__
<type 'type'> <type 'type'>
我们看到同样的结论。

本文参考:
Python Types and Objects
Data Model

Tuesday, February 10, 2009

[Python] CPython1.01源代码阅读笔记(1)

(未完结)
简介
CPython是官方的、使用最广的Python解释器。因为使用C语言实现而得名CPython。非官方的Python解释器还包括JPython(用Java实现)以及PyPy(用Python本身实现)。

关于CPython源码的阅读,网上我见到相关文章有:
这两篇侧重点各有不同。前者偏重CPython的词法语法分析,后者偏重解释器的执行机理。我的笔记会和前者重合度较高。事实上我也是参考着前者来的,有部分他略过或是简单提及的地方可能我这里会详细处理。

CPython 1.01是其官方网站上我能找到的最早的版本。这个版本应该是1994年左右release的。所以还是相当初期的时候,规模比较小,便于学习。
解压后我们可以看见它的目录结构包括:
Include/ C源代码的头文件(.h)
Lib/用Python自己写的Python库文件(.py)
Python/这里是"编译器"和解释器的源码,Python的核心所在
Grammar/包括一个Grammar文件,用BNF描述Python语言语法
Parser/生成pgen这个工具使用Grammar文件

一个编译器运作,必然离不开词法分析和语法分析,所以我们也从这里入手。
词法分析:
所谓词法分析是指将输入的字符流转变为token流。CPython中的token类型被定义在Include/token.h中。比如NAME就是一个token,它对应着关键字以及标识符。"a = b + 10"这个字符流对应的token流为"NAME EQUAL NAME PLUS NUMBER"。

从字符流到token流的转换在Python/tokenizer.c中完成。tokenizer的核心数据结构是tok_state。它的作用是记录当前tokenizer的状态,比如当前输入缓冲区的起始位置(buf)和终止位置(end)以及当前读取到的字符指针(cur)。

如果将tok_state看成tokenizer的成员变量们,你会看到tokenizer.c中还定义了下面这些tokenizer的成员函数:
  • tok_new: 创建并返回一个tokenizer实例tok,下面提到的tok都是该tokenizer的实例,可以看成是一个全局的变量。
  • tok_setups(str): 调用tok_new并将返回的tok绑定到一个字符串上。
  • tok_setupf(f): 调用tok_new并将返回的tok绑定到一个文件上(可以是标准输入stdin,以便互交模式)。
  • tok_free(tok): 将tok这个tokenizer实例释放。
  • tok_nextc(tok): 从tok绑定的输入中读取下一个字符并返回。
  • tok_backup(tok, c): 将c放回tok绑定的输入中(tok->cur--)
  • tok_1char(c): 根据单个字符c返回token,比如"<"返回 LESS

  • tok_2char(c1,c2): 根据连续两个字符c1, c2返回token, 比如 "<="返回LESSEQUAL

  • tok_get(tok, p_start, p_end): 根据tok->cur的返回输入的字符流当前位置的token,以供语法分析。

  • tok_dump(int type, char* start, char* end): 打印输出从start到end (均为字符指针)且类型为type的token,以供调试使用。
这些tok开头的函数当中,真正重要的其实就是tok_get--读取当前token。它会在语法分析中反复被调用。 语法分析: Python的语法分析需要借助Parser/目录下pgen这个工具。据Guido老师自己回忆,从Python release到现在,这个pgen是改动最小的部分了。这部分在我看来实现的很精彩。 先说一下python语法分析的基本原理。pgen实现了一个LL(1)的Parser。pgen的输入对象是Grammar/目录下的Grammar文件。 我们可以看一下Grammar文件里到底是如何定义Python语法的。比如其中最重要的几行包括:
stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
small_stmt: expr_stmt | print_stmt  | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | access_stmt | exec_stmt
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef
它表示每个stmt可以是一个simple_stmt也可以是一个compound_stmt。simple_stmt可以是几个small_stmt的同行并列用";"隔开。 small_stmt可以是expr_stmt, print_stmt, del_stmt等简单语句。而compound_stmt则包括if_stmt, while_stmt等需要跨越多行的复合语句。就这样Python用BNF范式定义了最基本的语法。 现在我们有了这个通俗易懂的Grammar文件以后,pgen负责把这个Grammar转换成NFA,然后再转换为相应的DFA,接着再化简这个DFA,最后保存在gramint.c 和gramint.h这两个文件中。如果你觉得很复杂,你只需要记住我们根据Grammar这个文件得到了一个语法规则就可以了。我们现在来看一下一个py交互模式的运作流程以便于理解:
  1. 在pythonmain.c 的realmain()函数中,执行run(stdin, "")
  2. 进入pythonrun.c的run(fp,filename)调用run_tty_loop
  3. 进入pythonrun.c的run_tty_loop(fp, filename),执行如下循环:
    run_tty_loop(fp,filename){
        for (;;) {
            run_tty_1(fp,filename); //不断执行一个“单行”语句
        }
    }
  4. 进入pythonrun.c的run_tty_1(fp, filename),主要执行如下:
    run_tty_1(fp, filename) {
    //gram <- graminit将已生成的Python语法规则放进gram,
    //其实不在这个函数里完成,为了理解的方便我就这样写在这里。     
    //根据语法gram以及输入文件fp生成语法树存放在n中     
    node* n = parsefile(fp, filename, &gram, single_input, ...)
    // 执行以n为根节点的语法树
    v = run_node(n, filename, ...) 
    }
给定以上的主要流程,我们来接触更加细节的部分。首先我们来看parsetok.c中的parsefile这个函数,它主要功能包括"
parsefile(fp,filename, g, ...) {
//初始化err_ret
//初始化一个tokenizer(词法分析器)tok
tok = tok_setupf(fp, ...);
return parsetok(tok, g, ...);
}
所以这个函数也相当简单,初始化一个词法分析器然后调用parsetok开始做词法分析。再来看parsetok:
parsetok(tok, g, ...) {
ps = newparser(g, start)
for (;;) {
    type = tok_get(tok, &a, &b);
    addtoken(ps, type, ...);
}
delparser(ps);
}
所以这里就是用一个for循环不停的调用tok_get抓取下一个token供语法分析使用。语法分析里的状态转移以及移进归约在addtoken中实现。