[Python] Class间大小比较（达到全序）

在Python 2.x中, 可以方便的使用 __cmp__ 方法来实现class object之间的大小比较.

class Foo:
    def __init__(self, key):
        self.key = key

    def __cmp__(self, other):
        return cmp(self.key, other.key)

如此Foo类型的object间的大小比较就可以用key这个域的值来实现.

在Python 3以后, __cmp__ 方法被移除了. 实现Foo object间的大小比较， 需要用functools.total_ordering修饰这个class以后, 实现__eq__方法以及__lt__(或者__lt__, __le__, __gt__, __ge__中的任意一个).

import functools

@functools.total_ordering
class Foo:
    def __init__(self, key):
        self.key = key

    def __eq__(self, other):
        return self.key == other.key

    def __lt__(self, other):
        return self.key < other.key

Sublime Text 3 插件开发 (未完)

Sublime Text (以下简称ST)提供了一个python的API接口. 在这个接口之上,用户可以开发自己的插件. 完整的ST3 API可以参见这里

http://www.sublimetext.com/docs/3/api_reference.html

如果你想仔细研究这些API的定义以及ST自带Python模块的细节, 可以在ST下找到这个python API的文件. MacOS上, 在/Applications/Sublime Text.app/Contents/MacOS/目录底下, 有2个文件 sublime.py和sublime_plugin.py.

从一个最简单的plugin开始

---

import sublime, sublime_plugin
class HelloWorldCommand(sublime_plugin.TextCommand):
    def run(self, edit):
        self.view.insert(edit, 0, "Hello, World!")

将其命名为"hello_world.py"以后, 存在Packages/User底下. 这个plugin就只干一件事儿, 当你在ST3自带的python console里(可以通过Ctrl+`呼出)运行

view.run_command("hello_world")

就会在你正在编辑的文件里添加一段"Hellow, World!". 这里注意ST的命名习惯. 这个类的名字叫HellowWorld, console中ST会将其命名为hellow_world, 从而使用run_command("hello_world")来运行之.

Currying in ML, Python, Javascript

ML

---

以SMLNJ为例.

- fun sum x y = x + y;
val sum = fn : int -> int -> int
- val sum2 = sum 2;
val sum2 = fn : int -> int
- sum2 10;
val it = 12 : int

Python

---

可以使用functools来实现curry

>>>from functools import partial
>>>def sum(x,y): return x + y
>>>sum2 = partial(sum, 2)
>>>sum2
<functools.partial object at 0x1f2de0>
>>>sum2(10)
12

JavaScript

---

http://www.svendtofte.com/code/curried_javascript/

[Python]Package的安装

1 使用python setup.py install来安装

使用python setup.py install的时候, 默认路径是 /usr/lib/python2.x/site-packages 这样的全局路径底下. 若是没有权限写,可以自己指定安装路径

python setup.py install --home=/your/fav/dir

比如

python setup.py install --home=~

2 使用easy_install来安装egg文件

easy_install foo.egg 

[Python]String的decode, encode

string的decode用法:

str.decode(encoding="gb2312",errors="strict"

在这里我们告诉python解释器用encoding参数所指定的来对str解码.标准的encoding可以查看这里

和简体中文相关的通常有gb2312,gb18030以及gbk(大多数BBS的中文encoding)

一篇参考http://hi.baidu.com/tornadory/blog/item/2fa5f0c36cf7bd5fb219a801.html

[Python]几个常用数据结构的高效实现

Python中最广为熟知的container就是list和dict了. 但是对于特定的用途, 这二者未必是最高效的.比如判断容器中是否包括x(x in container),如果容器是list就需要O(n)的时间.而使用set的话这个就只需要O(1)的时间. 我的血泪教训是:　在list很长的时候, x in list这个操作是非常非常低效的.一个好的主意是在另一个set容器来保存membership的信息.

集合(Set)

---

set是Python的built-in类型,对于membership testing,　removing duplicates 的操作非常高校(O(1)时间).另外对集合操作也非常方便.如果对容器元素的顺序没有要求,set是非常好的选择对象

>>>s= set()
>>>s.add(1)
>>>s.add(2)
>>>s.remove(1)  #throw exception if not in set
>>>s.discard(1) #remove if present
>>>print set([1,2,3]) | set([3,4,5]) #union
set([1, 2, 3, 4, 5])
>>>print set([1,2,3]) & set([3,4,5]) #intersection
set([1])
>>>print set([1,2,3]) - set([3,4,5]) #difference
set([1, 2])
>>>print set([1,2,3]) ^ set([3,4,5]) #symetric difference
set([1, 2, 4, 5])

栈(Stack)

---

栈的特点是先进后出(FILO).built-in的list用来实现栈非常合适.对于append和pop的实现非常高效.

FIFO队列(FIFO Queue)

---

队列的特点是先进先出(FIFO). list用来实现队列不够有效.collections.deque可以弥补这一缺点(fast appends and pops from both ends)

>>>from collections import deque
>>>queue = deque()
>>>queue.append(1)
>>>queue.append(2)
>>>queue.appendleft(3)
>>>print queue
deque([3, 1, 2])
>>>queue.pop()
2
>>>queue.popleft()
3

利用deque,我们可以实现一个时间上高效的FIFO queue:

class FIFOQueue():
    def __init__(self):
        self.queue = deque()
        self.counter = itertools.count(1)    # unique sequence count
        self.task_finder = {}                # mapping of tasks to entries

    def append(self, task):
        if debug:
            print "FIFOQueue.append "+repr(task)

        if task in self:
            return
        count = next(self.counter)

        entry = [count, task]
        self.task_finder[task] = entry
        self.queue.append(entry)
        if debug:
            print "FIFOQueue.append "+repr(task)+" done"

    def top(self):
        if debug:
            print "FIFOQueue.top "
        while self.queue:
            count, task  = self.queue[0]
            if count:
                if debug:
                    print "FIFOQueue.pop "+repr(task)+" done"
                return task
            else:
                self.queue.popleft()
        if debug:
            print "FIFOQueue.top none"
        return None

    def pop(self):
        if debug:
            print "FIFOQueue.pop "
        while not self.top():
            continue
        if self.queue:
            entry  = self.queue.popleft()
            count, task = entry
            assert(count != None)
            assert(self.task_finder[task] == entry)
            del self.task_finder[task]
            if debug:
                print "FIFOQueue.pop "+repr(task)+" done"
            return task
        if debug:
            print "FIFOQueue.pop none"
        return None

    def remove(self, task):
        if debug:
            print "FIFQueue.remove "+repr(task)
        if task not in self:
            return
        entry = self.task_finder[task]
        assert(entry[0] != None)
        entry[0] = None
        del self.task_finder[task]
        if debug:
            print "FIFOQueue.remove "+repr(task)+" done"

    def __len__(self):
        return len(self.task_finder)

    def __contains__(self, task):
        return self.task_finder.has_key(task)

    def __repr__(self):
        return repr(self.queue)

这个实现的好处在于可以常数时间删除一个元素以及在常数时间内判定一个元素是否属于这个queue

优先队列(Priority Queue)

---

使用堆(heap)实现的优先队列(priority queue)可以在O(1)时间内得到队列中最小元素,O(logn)时间内插入或者删除一个元素.我通常在simulator中会使用priority queue来管理所有事件.

Python提供了heapq来实现.值得注意的是heapq并不是一个容器,而是操作在list上的一系列的heap算法(包括heappush,heappop,heapify)等.http://docs.python.org/library/heapq.html给出了用这一些算法实现堆排序(heapsort)以及优先队列的. 不过在那个优先队列的例子里有一点小bug. 这里是我给出的代码

import itertools
from heapq import heappush, heappop
class PriorityQueue():
    def __init__(self):
        self.pq = []                         # the priority queue list
        self.counter = itertools.count(1)    # unique sequence count
        self.task_finder = {}                # mapping of tasks to entries
        self.size = 0
 
    def add_task(self, priority, task, count=None):
        if count is None:
            count = next(self.counter)
        entry = [priority, count, task]
        self.task_finder[task] = entry
        heappush(self.pq, entry)
        self.size  += 1

    def pop_task(self):
        while self.pq:
            entry = heappop(self.pq)
            priority, count, task = entry
            if self.task_finder[task] == entry:
                del self.task_finder[task]
            if count is not None:
                self.size -= 1
                return (priority, task)
        return None


    def del_task(self, task):
        entry = self.task_finder[task]
        if entry[1] != None:
            self.size -= 1
        entry[1] = None

    def reprioritize(self, priority, task):
        entry = self.task_finder[task]
        self.add_task(priority, task, entry[1])
        if entry[1] != None:
            self.size -= 1
        entry[1] = None

    def __len__(self):
        return self.size

[Python]glob

glob用于寻找符合pattern的文件名/目录名, 相当于shell下的ls, 很好用

>>import glob
>>glob.glob(”/path/to/me/*.txt”)
['./1.txt', './2.txt']

[Python]py2app:将python程序转换为Mac OS Application的工具

先安装py2app
安装完毕后会有一个叫py2applet的程序出现
接下来进入我们python程序的目录,比如我们的程序叫HelloWorld.py
第一步: 生成HelloWorld的setup.py

$ py2applet --make-setup HelloWorld.py

第二步: 生成HelloWorld.app的结构

$ python setup.py py2app -A

[Python]抓取豆瓣电台里被标记喜欢的歌曲名称

一段时间前开始使用豆瓣电台,很喜欢一个功能就是听到一个好听的歌就可以标记上.以后就可以从我的音乐里看到按标记时间排列出的所有曾经标记过的歌曲.但是有个功能豆瓣电台还不支持,就是按照专辑来对所有标记的歌曲分类.因为我想看一下哪一张专辑我标记的喜欢的歌曲最多. 所以就用python写了下面的脚本. 使用的时候不要忘记把下面源码里 current_url里面的apc字串换成你的用户名, 并且登录豆瓣.

#!/usr/bin/python
from urlparse import urlparse, urljoin
import urllib, sgmllib
from HTMLParser import HTMLParser
import re, sys

class MyParser(HTMLParser):
    def __init__(self):
        HTMLParser.__init__(self)
        self.num = 0
        self.albums = {}
        
    def parse(self, url):
        req = urllib.urlopen(url)
        self.state       = 0
        self.raw_text = req.read()
        self.feed(self.raw_text)
        
    def handle_starttag(self, tag, attrs):
        #print "Encountered the beginning of a %s tag" % tag
        try:
            if self.state == 0:
                if  tag == "table" and dict(attrs)["class"] =="olts":
                    self.state = 1
                    self.row = 0

            elif self.state == 1:
                if  tag == "tr":
                    self.row += 1
                    self.state = 2

            elif self.state == 2:
                if  tag == "td":
                    self.state = 3

            elif self.state == 3:
                if tag == "a":
                    self.state = 4
                else:
                    self.state = 1

            elif self.state == 4:
                self.state = 1
        except KeyError:
            pass

    def handle_endtag(self, tag):
        #print "Encountered the end of a %s tag" % tag
        if self.state >= 1 and tag == "table":
            self.state = 0

    def handle_data(self, data):
        if self.state == 3:
            if self.row > 1:
                print "%d title"%(self.num), data[:-2],
                self.num += 1
                self.title = data[:-2]
        elif self.state == 4:
            if data.strip():
                print "album", data
                try:
                    self.albums[data].append(self.title)
                except KeyError:
                    self.albums[data] =  [self.title]
            
        
numsongs   = int(raw_input("How many songs do you have?"))
myparser    = MyParser()
base = 0
while base < numsongs: 
    current_url = "http://www.douban.com/people/apc/songs?start=%d"%(base)
    print current_url
    myparser.parse(current_url)
    base += 20
print "done, all together %d songs"%(myparser.num)
al = myparser.albums.keys()[:]
al.sort(cmp= lambda x,y: len(myparser.albums[x]) - len(myparser.albums[y]))
for a  in al:
    print a, "%d songs"%(len(myparser.albums[a]))

我输出的结果是这两张专辑我标记的最多:
Schindler's List 6 songs
Le Fabuleux destin d'Amélie Poulain 9 songs
辛德勒的名单的OST以及天使爱美丽的OST. 我果然是个电影控.

[Python] Yaml与Json

Python2.6开始支持Json，见Json库。
Yaml的Python库见PyYaml

简单说起来:

1. Python的json库在默认设置下输出的是Yaml语言的子集
2. 两个库的语法基本一致。不同的是yaml的dump输出的直接为字符串，json的dump还需要指定一个stream object。如果要输出为字符串，得使用dumps
   

关于两者详细的关系和区别，这里有一片英文的文章讨论yaml与json的关系

[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

[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

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

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

关于CPython源码的阅读，网上我见到相关文章有:

• 张羿的Python源码分析
• Robert Chen的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中实现。

[Python]一个用ssh来远程登录多台机器并执行命令的脚本

功能类似于multissh。事实上我也抄了这个名字//grin。
要求安装了pexpect这个包先。
用法见usage:
Usage: ./multissh.py -f cmdfile -l username -c cmd -n nodesfile -v -r
execut cmd on remote hosts (all hosts in ./hosts.txt by default)
-v verbose
-r recording hosts on which mission succeeded and failed
-l username
-c cmd to be executed remotely
-n file containing the nodes
-f file conaining the cmd
-h show the usage
就是指定一个文件比如nodes.txt以及命令以后，它可以自动登录到nodes.txt包含的节点里执行命令。可以在源文件里替换进你自己的密码，也可以使用公钥密钥登录不需输入密码。指定了v选项的话得到在远端每台主机上的详细输出。指定了r选项的话记录下那些节点成功那些节点失败。
我前面的帖子里有关于ansi_color的一个脚本，拿过来可以配合使用得到彩色输出

使用前可能要根据情况修改prompt变量的定义. 这个变量是关于登录后提示符的正则表达.我根据我自己的几台机器随便写了两个.未必符合你的情况.

#!/usr/bin/python
import sys
import os
import getopt
import pexpect
import re
try:
    from ansi_color import *
except ImportError:
    def color_str(s, *args):
        return s
    fg_green = None
    fg_red = None
    fg_blue = None

prompt = "^.*\(.*\):|\[.*@.*\]|\$"
nl = open("/dev/null", "w")
    
def _print(s):
    if not single_mode:
        print s    

def do(cmds, hostname, username):
    global verbose, quiet, good_hosts
    #print "executing \"%s\""%(repr(cmds))
    ret = 0
    try:
        sshcmd = 'ssh %s'%(hostname)
        if username != None:
            sshcmd = sshcmd + " -l %s"%username
        s = pexpect.spawn(command=sshcmd, timeout=20)
        if verbose:
            s.logfile_read = sys.stdout
            s.setecho(False)
        else:
            s.logfile_read = s.logfile_send = nl 
            s.setecho(False)
        t = 0
        while t < 3:
            i = s.expect([prompt, pexpect.EOF, pexpect.TIMEOUT,\
                          "Are you sure you want to continue connecting (yes/no)?",\
                          "(P|p)assword:"])
            t += 1
            if i == 0:
                break
            elif i == 1:
                _print("End Of File")
                return 1
            elif i == 2:
                _print("time out")
                return 1
            elif i == 3:
                s.sendline("yes")
            elif i == 4:
                s.sendline(password)
        if t >= 3:
            return 1
        if cmds:
            for cmd in cmds:        
                s.sendline(cmd)
                s.expect(prompt)
        else:
            _print("\nEntering interactive mode, please ^] to escape")
            s.interact()
        s.sendline("exit")
        s.close()
        return 0
    except pexpect.ExceptionPexpect:
        return 1

def print_usage():
    print "Usage:\t ./multissh.py -f cmdfile -l username -c cmd -n nodesfile -v -r"
    print "execut cmd on remote hosts (all hosts in ./hosts.txt by default)"
    print "\t-v verbose"
    print "\t-r recording hosts on which mission succeeded and failed"
    print "\t-l username"
    print "\t-c cmd to be executed remotely"
    print "\t-n file containing the nodes"
    print "\t-f file conaining the cmd"
    print "\t-h show the usage"
    print "\t-p password"
    sys.exit(0)

if __name__ == "__main__":
    try:
        opts, args=getopt.getopt(sys.argv[1:], \
            "l:f:n:c:p:vhrq",["login_name", "cmdfile","nodesfile","command","password","verbose","help","recording","quiet"])
    except getopt.GetoptError, err:
        print str(err)
        print_usage()
    if opts == [] and args == []:
        print_usage()
    if args:
        hosts = [args[0]]
    else:
        hosts = []

    cmds = []
    verbose = False
    quiet = False
    username = None
    recording = False
    password = ""
    single_mode = True
    
    for o, ra in opts:
        a = ra.strip("\n")
        if o in ("-h", "--help"):
            print_usage()
        elif o in ("-n", "--nodesfile"):
            hosts = [l.strip(" \t\n") for l in open(a, 'r')]
            single_mode = False
        elif o in ("-c", "--command"):
            cmds = [a]
        elif o in ("-f", "--cmdfile"):
            cmds = [cmd.strip(' \n') for cmd in open(a, 'r')]
        elif o in ("-v",  "--verbose"):
            verbose = True
        elif o in ("-q", "--quiet"):
            quiet = True
        elif o in ("-r", "--recording"):
            recording = True
        elif o in ("-l", "--login_name"):
            username = a
        elif o in ("-p", "--password"):
            password = a

    if not hosts:
        _print("using default ./hosts.txt")
        h = open(os.path.join(os.path.expanduser("."), "hosts.txt"),'r')
        hosts = [dst.strip(' \n') for dst in h]
        
    if recording:
        f_good = open("good_hosts.txt","w")
        f_bad = open("bad_hosts.txt","w")

    good_hosts =[] 
    bad_hosts =[]
    
    for (i, hostname) in enumerate(hosts):
        _print ("%d/%d: ["%(i+1, len(hosts))+ color_str(hostname, fg_blue)+"]")
        ret = do(cmds, hostname, username)
        if verbose:
            print
        if ret == 1:
            bad_hosts.append(hostname)
            _print("["+color_str("Fail!", fg_red)+"]")
            if recording:
                print>>f_bad, hostname
                f_bad.flush()
        else:
            good_hosts.append(hostname) 
            _print ("["+color_str("OK!", fg_green)+"]")
            if recording:
                print>>f_good, hostname
                f_good.flush()
            

    _print ("%d hosts suceed!"%len(good_hosts))
    sys.exit(ret)

[Python]执行一个进程并监视是否超时

用到popen2 module当中的Popen3这个类。用法很简单，创建子进程并立即返回父进程。然后可以用poll()函数检查子进程是否已经结束(未结束的话返回值-1)。

import popen2
def _popen(cmd, timeout = 10, num_retry = 3, logfile = sys.stdout):
    i = 0
    is_timeout = False
    while i <= num_retry:
        print "%dth try"%i, cmd
        sys.stdout.flush()
        i += 1
        t0 = time()
        P = popen2.Popen3(cmd, True)
        prompt = False
        while time() < t0 + timeout and P.poll() == -1:
            sleep(0.1)
        sts = P.poll()
        if sts == -1:
            logfile.write(color_str("command [%s] timeout\n"%(cmd), fg_red))
            if i < num_retry:
                logfile.write(color_str("terminate and try again\n", fg_red))
            logfile.flush()
            is_timeout = True
            os.kill(P.pid, signal.SIGTERM)
        elif sts != 0:
            for l in P.childerr.readlines():
                logfile.write(l)
            if i < num_retry:
                logfile.write(color_str("try again\n", fg_red))
            logfile.flush()
            is_timeout = False
        else:
            is_timeout = False
            break
    logfile.write(color_str("return "+str(sts)+"\n", fg_red))
    sys.stdout.flush()
    if is_timeout:
        return (sts, open("/dev/null", "r"))
    else:
        return (sts, P.fromchild)

按说popen2这个module应该已经deprecated，被subprocess module所取代。不过subprocess.Popen的poll()函数似乎有bug，总是返回None。所以只好还用“古老”的module。

[Python]Python 3.0来了

经历了3年的开发，Python 3.0 (Py3k)在千呼万唤声中 ，终于在2008年12月3号正式发布了。用Guido同学(Python语言的缔造者)自己的话说，Python这些年经历了迅猛发展，已经开始有点违背了Python的"There's Only One Way To Do It"的哲学理念。Guido同学认为Python之所以有今天正是得益与这一与Perl "There is more than one way to do it"相反的理念。所以他需要做一些“清理门户”的事情。因此，我们就有了Python 3.0这一"里程碑"--Python 3.0不提供向下兼容性。换言之，你的2.x的库或者代码，可能会无法运行在Python 3.x当中。

Python 3.0当中有哪些变化呢？http://docs.python.org/3.0/whatsnew/3.0.html给出了官方的解释。首先映入眼帘的便是，print的语法被改变了。如今print降格为了普通一介函数，需要用print(file=xxx, str1, str2,...)来调用了。其实我很怀念原先print>>xxx, str1, str2 ...的语法，简洁而一目了然。

另外我觉得比较大的改变还有

• dict.keys() dict.values()以及dict.items()不再返回list类型的值。所以如果想要k=d.keys();k.sort() 就得写成 k=sorted(d)
• range现在像以前的xrange那样来工作（之前range直接返回一个list而xrange是返回一个可以yield同样结果的迭代器，以提高效率）。xrange下岗了。
• 1/2现在的结果是float了，如果要得到截尾的效果，需要用1//2。这个好，再也不用痛苦的写上a*1.0/b/c了
• <>下岗了。现在只能用!=了。这点不理解。
• list.sort()现在可以多一个key 参数。比如list.sort(key=myhash)，则myhash为一个1参数1返回的函数，list就依据这个myhash来对其包含的元素排序。乌拉！这点好，不用再去重载cmp函数了。早就盼着这一天了
• 支持如同ML当中的pattern matching: (a, *rest, b) = range(5)
  可以得到 a=0, rest=[1,2,3], b=4
• 终于到了我最关心的一点：Python 3.0里提供了函数参数以及返回值的注解功能。比如你可以 定义函数 def foo(para1: "the 1st input", para2: "the 2nd input") -> "final result" 这里使用了字符串作为参数和返回值的注解。或者你可以 def bar(para1: int, para2: list) -> float 这样来用类型定义。不过需要特别指出的是，python解释器本身不对注解做出任何反应。这里注解的作用是提供给第三方来infer参数意义或者做typechecking的。
  

说道这里，就稍微走题一下吧。Python是一种Dynamic Typing的语言。变量的类型是在运行期才infer出来，而不像C/C++/Java等Static Typing在编译期就已经决定了。Dynamic Typing的优点在于方便灵活，但如果程序规模一大，纠错就是一个很头疼的事情。Static Typing 很多错误可以在编译期就发现。我自己的一个感觉就是用Java写程序如果“编译”通过了，运行期出错的概率比Python小的多。所以一直都很希望Python能有可选的Static Typing 的功能。事实上，Boo 就是一种Static Typing的Python-like语言，而Cobra 则是提供了可选Static Typing的Python-like语言。关于Python是否需要这一功能，可以看一下Guido同学的帖子"Adding Optional Static Typing to Python"。总体而言可以说Guido同学是反对这一想法的。因为他觉得这会把Python简洁的语法弄的凌乱而丑陋并且对Python解释器的执行速度也是一大考验。回到Python 3.0的注解机制上来，这算是一种折中吧－－如果你需要typecheking, OK，我们提供场地，你请用第三方来完成吧，但是后果你自负。好吧，虽然这不是我想要的，但是总比没有强吧。

Python 3.0究竟会表现如何？时间会告诉我们，让我们拭目以待。

[Python]实现Console下路径输入的补全

因为要用脚本处理一些log，每次运行都要输入待处理的log的路径。可是我存放的log路径太复杂 log自己名字也很复杂，输入起来很麻烦。就想在python里借用shell的路径补全功能。Python里有readline这个module可以提供补全的基本功能，当然需要你自己给它一个completer(text, state)函数从而使它知道如何去补全。另外还有一个cmd module提供简单的命令行界面。用这两者就可以实现我们需要的功能。

import cmd
import string, sys
import os
import readline
class CLI(cmd.Cmd):
  def __init__(self):
      cmd.Cmd.__init__(self, "tab")
      self.prompt = 'input the path:'
      self.path = None
      readline.set_completer_delims('/\\')
  def onecmd(self, path):
      if os.path.exists(path):
          self.path = path
          return path
      else:
          print "%s not exists"%(path)
          return None
  def complete(self, text, state):
      if state == 0:
          origline = readline.get_line_buffer()
          line = origline.lstrip()
          stripped = len(origline) - len(line)
          begidx = readline.get_begidx() - stripped
          endidx = readline.get_endidx() - stripped
          self.completion_matches = self.completepaths(text, line, begidx, endidx)
      try:
          return self.completion_matches[state]
      except IndexError:
          return None
  def completepaths(self, text, line, *ignored):
      (head, tail) = os.path.split(line)
      matches = []
      if head == "":
          p = "."
      else:
          p = head
      if os.path.exists(p):
          filelist = os.listdir(p)
          matches = [f if os.path.isfile(os.path.join(head, f))\
                     else f+os.sep for f in filelist if f.startswith(tail)]
      return matches
  def get_path(self):
      self.cmdloop()
      return self.path
def get_path():
  cli = CLI()
  return cli.get_path()

这里我们继承了Cmd类。但是重载了complete这个函数。这个函数是在用户按下tab键呼叫补全的时候被调用。
使用这个小程序只要import这个文件以后直接调用get_path就可以了.
补充：后来发现了一个小bug已经做了修改。cmd module里面在cmdloop()这个函数里就设定了completer_delims (分隔符)。问题在于默认的分隔符里面有很多合法的linux文件名字符比如 “-”这样会导致tab补全的时候出一些问题。 所以我们需要在这之前设置好。这里我们就在__init__初始化的时候设置成/以及\。

[Python]使用ansi color code 让console五颜六色

写了一个Python小程序， 用于输出带ansi color code的字符串，使得在支持vt100的终端上能看见五颜六色的输出。

ESC = chr(27)
# 字体
a_default  = 0
a_bold     = 1
a_italic   = 3
a_underline= 4
# 前景颜色
fg_black   = 30
fg_red     = 31
fg_green   = 32
fg_yellow  = 33
fg_blue    = 34
fg_magenta = 35
fg_cyan    = 36
fg_white   = 37
# 后景颜色
bg_black   = 40
bg_red     = 41
bg_green   = 42
bg_yellow  = 43
bg_blue    = 44
bg_magenta = 45
bg_cyan    = 46
bg_white   = 47

def color_code(a):
    return ESC+"[%dm"%a
    
def color_str(s, *args):
    cs = ""
    for a in args:
        cs += color_code(a)
    cs += s
    cs += color_code(a_default)
    return cs  

用法
比如你可以用

print color_str("hello world", fg_red, bg_black, a_bold)

来生成黑底红字的加粗的hello world

[Python]Quine(自产生程式) in Python

Quine是指一个程序，它的输出为自身的源代码。这个学期的OS课里读到Ken Thompson的paper里说到了这样的一个程序。Ken Thompson在83年因为早年对Unix和C语言的贡献而得到了图灵奖。这篇paper 是他的图灵奖演讲文稿。在paper里他提到他在UC Berkeley念书的时候，同学们都热衷于写这样的程序并相互比赛谁的程序短。并且他还提到，如果你们自己没有写过这样的程序，他强烈建议自己来试一试写这个程序，会比由别人告诉你如何得到这个程序要有收获的多。于是我便没有接着往下读这个paper看Ken是如何完成的而是试图用Python来写一个这样的程序。最后得到了这样的程序：

M="print 'M='+repr(M)\nprint M"
print'M='+repr(M)
print M

Python来完成这个任务事实上是相当简洁的。因为repr()这个函数帮助我们完成了很多的工作。