Notes of Python interpreter

by thinker

關鍵字:

本文是$研究$ $Python$-2.4.3c1 的 source 時，所紀錄的筆記。

列出 source tree 的 root directory，可以看到下面的 sub-directory:
{{{
thinker@cowboy$$ ls -l|egrep '^d.*'
drwxr-xr-x  23 thinker  users      512 Mar 23 10:55 Demo
drwxr-xr-x  22 thinker  users      512 Mar 23 10:56 Doc
drwxr-xr-x   2 thinker  users      512 Mar 23 10:55 Grammar
drwxr-xr-x   2 thinker  users     2048 Mar 25 17:20 Include
drwxr-xr-x  37 thinker  users     5632 Mar 25 10:31 Lib
drwxr-xr-x  11 thinker  users      512 Mar 25 10:27 Mac
drwxr-xr-x   3 thinker  users     1024 Mar 23 10:55 Misc
drwxr-xr-x   4 thinker  users     3072 Mar 25 10:31 Modules
drwxr-xr-x   2 thinker  users     2048 Mar 25 10:29 Objects
drwxr-xr-x   7 thinker  users     1024 Mar 23 10:56 PC
drwxr-xr-x   2 thinker  users     1024 Mar 23 10:55 PCbuild
drwxr-xr-x   2 thinker  users     1024 Mar 25 10:29 Parser
drwxr-xr-x   2 thinker  users     2560 Mar 26 14:28 $Python$
drwxr-xr-x   5 thinker  users      512 Mar 23 10:56 RISCOS
drwxr-xr-x  18 thinker  users      512 Mar 23 10:56 Tools
drwxr-xr-x   5 thinker  users      512 Mar 25 10:34 build
thinker@cowboy$$ 
}}}
* $Python$/ 這個 directory，是 $Python$ VM 和 compiler 最核心的部分。
* Objects/ 則實作 built-in types，如 list、tuple、dictionary ... 等。

== $Python$ VM ==
$Python$ 的 VM，其實是 implement 一個 stack machine ( http://en.wikipedia.org/wiki/Stack_machine )。opcode 的 operand 通常來自 stack，但有時 opcode 會帶一個 index。

=== $Python$/ceval.c ===
{{{
PyObject *
PyEval_EvalCodeEx(PyCodeObject *co, PyObject *globals, PyObject *locals,
           PyObject **args, int argcount, PyObject **kws, int kwcount,
           PyObject **defs, int defcount, PyObject *closure);
}}}
執行 PyCodeObject 物件。$Python$ 的任何可執行的程式片段，都是 PyCodeObject 的 instance。你可以想成，任何一段程式碼，如 lambda、function、或 module 的 inital code，都是一個 PyCodeObject 的 instance。每次執行 PyCodeObject ，都必需先配置好一個 PyFrameObject 的 instance，然後以 PyEval_EvalFrame() 執行該 instance 對映的程式碼片段 PyCodeObject instance。

PyFrameObject，簡稱為 frame，用來儲存任何一次執行程式碼片段時的狀態。如 variable 的內容、local/global symbol table、program counter (PC) 等。程式碼片段的執行，有時會暫時中斷，以便執行其它的片段，如 lambda 或 function。呼叫其它程式碼片段時，會配置一個新的 frame，以執行被呼叫的片段。在被呼叫的片段執行結束後 (return)，則會回到前一個 frame，繼續執行被中斷的片斷。而 frame 則會完整的保存被中斷的狀況，以便之後可以恢復執行。

{{{
typedef struct _frame {                                                         
    PyObject_VAR_HEAD                                                           
    struct _frame *f_back;      /* previous frame, or NULL */                   
    PyCodeObject *f_code;       /* code segment */                              
    PyObject *f_builtins;       /* builtin symbol table (PyDictObject) */       
    PyObject *f_globals;        /* global symbol table (PyDictObject) */        
    PyObject *f_locals;         /* local symbol table (any mapping) */          
    PyObject **f_valuestack;    /* points after the last local */               
    /* Next free slot in f_valuestack.  Frame creation sets to f_valuestack.    
       Frame evaluation usually NULLs it, but a frame that yields sets it       
       to the current stack top. */                                             
    PyObject **f_stacktop;                                                      
    PyObject *f_trace;          /* Trace function */                            
    PyObject *f_exc_type, *f_exc_value, *f_exc_traceback;                       
    PyThreadState *f_tstate;                                                    
    int f_lasti;                /* Last instruction if called */                
    /* As of 2.3 f_lineno is only valid when tracing is active (i.e. when       
       f_trace is set) -- at other times use PyCode_Addr2Line instead. */       
    int f_lineno;               /* Current line number */                       
    int f_restricted;           /* Flag set if restricted operations            
                                   in this scope */                             
    int f_iblock;               /* index in f_blockstack */                     
    PyTryBlock f_blockstack[CO_MAXBLOCKS]; /* for try and loop blocks */        
    int f_nlocals;              /* number of locals */                          
    int f_ncells;                                                               
    int f_nfreevars;                                                            
    int f_stacksize;            /* size of value stack */                       
    PyObject *f_localsplus[1];  /* locals+stack, dynamically sized */           
} PyFrameObject;                                                                
}}}

* f_nlocals = co->co_argcount + (co->co_flags & CO_VARARGS? 1: 0) + (co->co_flags & CO_VARKEYWORDS? 1: 0) + other local defined variables
* f_valuestack = f_localsplus + f_nlocals + f_ncells + f_nfreevars
* f_localsplus[0:f_nlocals] = arg0~argn + *args + **kws + other non-shared local variables
* f_localsplus[0:co->co_argcount] = [arg0..arg(co->co_argcount)]
* stack 用以儲存 opcode 的 operand 和計算結果
* freevars 是 closure 的 reference
* closure 文件: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474122
* cell 文件: http://www.python.org/doc/api/cell-objects.html

[attach:python-f_localsplus.png]

{{{
PyObject *
PyEval_EvalFrame(PyFrameObject *f);
}}}
PyEval_EvalFrame() 是 bytecode 的 interpreter，伊執行 frame (instance of PyFrameObject) 對映的程式碼片段 (f->f_code)。其內部是一個迴圈，讀取 PyCodeObject 內的 opcode，並依據 opcode 執行相對映的流程。

== Compile ==
{{{
/* Bytecode object */                                                           
typedef struct {                                                                
    PyObject_HEAD                                                               
    int co_argcount;            /* #arguments, except *args */                  
    int co_nlocals;             /* #local variables */                          
    int co_stacksize;           /* #entries needed for evaluation stack */      
    int co_flags;               /* CO_..., see below */                         
    PyObject *co_code;          /* instruction opcodes */                       
    PyObject *co_consts;        /* list (constants used) */                     
    PyObject *co_names;         /* list of strings (names used) */              
    PyObject *co_varnames;      /* tuple of strings (local variable names) */   
    PyObject *co_freevars;      /* tuple of strings (free variable names) */    
    PyObject *co_cellvars;      /* tuple of strings (cell variable names) */    
    /* The rest doesn't count for hash/cmp */                                   
    PyObject *co_filename;      /* string (where it was loaded from) */         
    PyObject *co_name;          /* string (name, for reference) */              
    int co_firstlineno;         /* first source line number */                  
    PyObject *co_lnotab;        /* string (encoding addr<->lineno mapping) */   
} PyCodeObject;                                                                 
                                                                                
/* Masks for co_flags above */                                                  
#define CO_OPTIMIZED    0x0001                                                  
#define CO_NEWLOCALS    0x0002                                                  
#define CO_VARARGS      0x0004                                                  
#define CO_VARKEYWORDS  0x0008                                                  
#define CO_NESTED       0x0010                                                  
#define CO_GENERATOR    0x0020                                                  
/* The CO_NOFREE flag is set if there are no free or cell variables.            
   This information is redundant, but it allows a single flag $test$              
   to determine whether there is any extra work to be done when the             
   call frame it setup.                                                         
*/                                                                              
#define CO_NOFREE       0x0040                                                  
/* XXX Temporary hack.  Until generators are a permanent part of the            
   language, we need a way for a code object to record that generators          
   were *possible* when it was compiled.  This is so code dynamically           
   compiled *by* a code object knows whether to allow yield stmts.  In          
   effect, this passes on the "from __future__ import generators" state         
   in effect when the code block was compiled. */                               
#define CO_GENERATOR_ALLOWED    0x1000 /* no longer used in an essential way */ 
#define CO_FUTURE_DIVISION      0x2000                                          
}}}
以下的部分還沒確定。$Python$ 所有的 opcode 都是一個 byte 加上一個 index (2 bytes)，index 是可有可無的。index 的對像，還依 opcode 而無同，可能是 co_consts、co_names、co_varnames、co_freevars、co_cellvars 等。opcode 的部分，純粹是指令和 index，沒有任何 data。所有的 constant 和名稱，都有各獨立的 table 存於，透過 opcode 和 index 指定。

== cell、free 和 closure ==
cell、free 和 closure，這三個名$詞$有相當強烈的關係，用來處理 variable 的 scope 問題。其實這三者都是指涉同一件事，也就是在不同 scope 共用一個變數。多個 scope 共用一個變數會出現在 nested/recursive 定義 function、class 或 lambda。
{{{
def outter():
    shared = 1
    inner = lambda x: shared + x
    print inner(7)
    shared = 3
    print inner(7)

outter()
==>
8
10 
}}}
上面的例子，outter 和 lambda 定義的 inner 是不同的 scope，但是他們共用變數 shared。只要 outter 改變了 shared 的值，inner 也馬上會看到。在 $Python$ compiler 編譯 lambda 這段 code 時，compiler 發覺 shared 在這個 scope 並沒有定義，也就是沒有設定值給 shared 的動作。因此，compiler 就將之視為這個 scope 的 free variable；未定義的變數，留給外面一層的 scope 去定義。於是 compiler 在外面一層 scope，也就是 outter() 這個 scope，找尋這個變數的定義。由於有 shared=1 和 shared=2 這兩行，因此 shared 這個變數算是在這個 scope 定義了，是這個 scope 的 local 變數。當內層 scope 的 free variable，為外層 scope 的 local 變數時，compiler 就會用 cell object 來儲存這個變數的值。因此，在外層 scope，該變數就被視為 cell variable。

[attach:closure.png]

上圖是非 cell 和 cell 的差別，當非 cell；也就是一般狀況，variable 儲存 value object 的 reference，改變 variable 的值，就是將 variable 從指向 A value object，改成指向 B value object。如果是 cell variable，variable 是指向一個 cell object，而 cell object 再指向 value object。改變 cell variable，就是將 cell object 從指向 A value object，改成指向 B value object，而非改變 variable 本身。

[attach:py-shared-var.png]

上圖就是變數共用的情況，兩個 scope 的 variable 都指向同一個 cell object。因此，任何一個 scope 改變 variable 的值時，都是改變同一個 cell object，以指向不同的 value。不論從 scope 1 或者 scope 2，只要改變 variable 的值，另外一個 scope 都可以透過共同的 cell object 讀取到新的 value。

當外層程式執行到定義內層 code object 那一行時，外層程式會將所有內層會用到的 cell object，包成一個 list，稱之為 closure。closure 被指定給內層 code object，所有內層的 freevar 都將透過 closure，找到對映的 cell object，並指向它。在上面的$範例$裡，就是在 lambda 這一行，產生 closure，並將之指定給 code object。所謂 closure，就是用來傳遞外層的 cells 至內層的 list，以達到共用變數之目的。

code object 被執行前，會先 create 一個 frame，而 create 的過程 free variable 的來源，就是給定給 code object 的 closure。而該 code object 所代表之 scope 內的 cells，則是那些被內層 scope 當作 free 的變數。$Python$ 會為每個 cell variable，建立一個 cell object，以並透過 closure 和內層的 code object 共用這些 variable。

== Performance ==
$Python$ 在 compile 階段，會將程式碼中用到的變數找出來，並將這些變數名稱存放在 CodeObject::co_names 這個 list。這讓 bytecode 在引用變數時，只需要指定一個 index，VM 就可以自 co_names 找到相對的字串。因此，bytecode 的內容，除了 opcode 之外，就是充作 operand 的 index。常數也是如此，存放在 CodeObject::co_consts。VM 從 opcode 可以知道指令附帶參數的種類，從而決定是引用 co_names 或 co_consts。

任何一段 code，都有所謂 local、global 和 builtins 三個 namespace。$Python$ 以 dictionary 存放 namespace 的內容，需要用到任何變數時，都可以自 dictionary 查詢。這讓 $Python$ 充滿了彈性，可 runtime 動態的將變數引入 namespace。但，查詢 dictionary 讓 $Python$ 花更多 CPU time，使的 performance 下降。

CodeObject::co_varnames 存放的是，在 co_names 裡，而且只在這個 scope 使用的變數。這些變數只會在這個 scope 被用到。為了改善 dictionary 所帶來的效能下降，VM 在為 code object 建立 stack frame 時，配置一個 (PyObject*) 型類的 $C$ array -- PyFrameObject::f_localsplus。f_localsplus 的第 i 個位置，就是在 co_varnames 第 i 個位置的變數。每一個記錄在 co_names 的變數，都會在 f_localsplus 有一個相對映的位置。當執行某些特別的 opcode 時，VM 就利用附帶的 index，直接存取 f_localsplus 的內容；這 index 同時也索引 co_varnames。讀取時，從 f_localsplus 讀取。改變變數值時，也直接改變 f_localsplus，以指向另一個 object。這使的 VM 不用再查詢 dictionary，直接引用 f_localsplus 的內容，使速度有效改善。

[attach:varnames.png]

CodeObject::co_freevars 和 CodeObject::co_cells 則分別記錄 free 和 cell 變數的名稱。這些變數，一也同時記錄在 co_names 裡。free 和 cell 變數，也透過一樣的技術，改善存取效率。

雖然如此，但 array 並不能提供 runtime 動態引入變數的能力。因此，dictionary 還是不能癈除。但是，只有在變數不在 co_locals 時，才會查詢 dictionary。

== $Python$ VS Java ==
曾經想過，$Python$ 是否有可能取代 Java，或與其競爭？兩者都採用 bytecode
這種 hybrid 的設計，進行 interpreter。如果有適當的配合，$Python$ 應該有
機會可以取代 Java。這似乎很美好!

深入瞭解 $Python$ 的設計後，發覺 $Python$ 的效能，離 Java 有很大一
段距離。以最簡單的加、減、乘、除，由於 Java 在 compile 階段，就可以判
斷 operands 是否為 primitive type，而且 Java 只有針對 primitive type
進行四則運算，因此針對 primitive type 的四則運算，比 $Python$ 有效率多
。另外空間的配置，也因為 Java 在 compile 階段就能辨視出 primitive type
的外觀，以進行分辨。這使的 $Python$ 需要更多的 memory。
{{{
def foo():
    return 1

def boo():
    return "1"

print foo() + boo()
}}}
以這段 $Python$ 的 code 而言，foo() + boo() 這個加法，我們就必需等
到執行完 foo() 和 boo() 之後，才能知道是否為 primitive 的加法。
而 foo() 和 boo() return 的 data，也不確定是哪一種 type，因此
都必需要包一層外衣，存放 type 的資訊，這樣呼叫者才能判斷出正確
的 type。這層外衣，就是 object。也就是，不論是否為 primitive type，
都要包成 object。這會使的 $Python$，在 memory 使用上，較沒有效率。

我們知道，$Python$ 幾乎所有的物件都是以 dictionary 當作 symbol table。
因此，所有進入 name space 的 symbol 和其資料，都會存在 dictionary。
而 dictionary 本身並不能判斷存在面的資料是什麼 type。因此，就像是儲
存一個 integer 整數，也需要包裝成 Int object，才能放進 dictionary。
這使的 primitive type 無時無刻，皆以較佔空間的 object 形態存在。

以加法為例， $Python$ 的加法就整數、浮點數、字串等三類加法。因此，單
單是判斷用哪一種加法，也就花到不少時間。其它的四則運算，也至少有
整數和浮點的差別，而 Java 則可以在 compile 時就判斷整數和浮點數
的不同，而直接選用不同的 opcode，$Python$ 則只有一種 opcode，直到
run time 時，才判斷出要執行哪一種。

基於上面的論點，$Python$ 要在效能上和 Java 競爭，應該是不可能的。
這是語言設計上的先天缺陷。

== Compiler ==
=== code generator ===
pycodegen.py 這個 module，implement $Python$ 的 compiler。client 透過呼叫 compile() 或 compileFile() 編譯 $Python$ source code。由於，source code 的來原有很多種，可能是一個 module，或僅是一個 $Python$ code 的片斷。因此，有 Module、Interactive 或其它的 class，以應付不同的 compile mode。

AbstractCompileCode 是所有 compile mode 的 base class，其呼叫 transformer module 的 parse() function，將 $Python$ source code parse 成 AST (abstract syntax tree) parse tree。然後才使用 visitor module 的 walk() function 來遊覽整個 parse tree，並產生 bytecode。walk() 遊覽 parse tree 時，會反過來呼叫以參數傳入 function 的 CodeGenerator object 的 method。當 walk() 遇到一個 class name 為 FOO 的 node 時，就會執行 CodeGenerator object 的 visitFOO() method。而 visitFOO() 則決定產生的 bytecode 內容，並決定 sub-tree 的遊覽順序。當 visitFOO() 希望 walk() 遊覽 child_a 時，就呼叫 self.visit(), 將 child_a 當成參數，使 walk() 進入 child_a 以下的 sub-tree。而 visit() 是由 walk() mix-in 進 CodeGenerator object 的。visitFOO() 透過呼叫 self.visit()，使 walk() 以 recursive 的方式，進入 sub-tree，最後遊覽整個 tree。

事實上 walk() 會產生一個 walker object (ASTVisitor)，使用這個 walker 來遊覽 parse tree。當 visitFOO() 呼叫 self.visit() 時，實際上是呼叫 walker 的 method。這時，walker 會繼續遊覽完整個 sub-tree 之後，才由 self.visit() return 回 visitFOO()。

[attach:pycodegen.png]

=== parse sources ===
Transformer 實際上是使用 parser 這個 module，來 parse source code。再呼叫 ast2tuple，將之轉成以 tuple 組成的 parse tree。透過 travel 這個 parse tree，建立以 ast module 內定義的 class 為基礎的 AST parse tree。最後才傳回這個 AST tree。 http://docs.python.org/lib/module-parser.html 告訴我們，parser module 的 suite() 或 expr() 傳回的就是 AST object，但這裡卻又轉了一次，宣稱是 AST tree。我並不確定這是什麼情形，可能是 parse module 所傳回的 AST object，如 document 所說，有版本的問題。所以，才重新轉一便。

[attach:transformer.png]

=== walk out parse tree ===
[attach:visitor.png]

Scope (symbols.py) 也 implement real visitor 的介面，透過 walk travel 整個 parse tree。記錄下每一個 scope 下的變數名稱，並分析其種類(local、cell 和 free)。

最後更新時間: 2006-04-10 14:29:11 CST | 引用

查詢:

COMMENTS: