09 Mar 2014
select 作用在 blocking 和 non-blocking socket 上的效果是一样.
blocking 和 non-blocking socket 的区别主要体现在 recv, send, accept,
connect 等这些函数上. 比如对于阻塞型的套接字,
recv 只在接收到至少一个字节的时候才返回.
那么是不是用 select 的时候就无所谓使用哪一种套接字呢?
Linux select man page
上有这么一段话:
Under Linux, select() may report a socket file descriptor as “ready
for reading”, while nevertheless a subsequent read blocks. This
could for example happen when data has arrived but upon examination
has wrong checksum and is discarded. There may be other
circumstances in which a file descriptor is spuriously reported as
ready. Thus it may be safer to use O_NONBLOCK on sockets that should
not block.
所以说, 在使用 select 的时候还是尽量使用 non-blocking socket 吧!
15 Oct 2013
写代码的时候, 写出了类似下面的一段代码:
int foo() {
return 0;
}
int bar = foo();
编译的时候, gcc 报错:
error: initializer element is not constant
在 The C Programming Language 中有这么一段话:
For external and static variables, the initializer must be a constant expression; the initialization is done once, conceptionally before the program begins execution.
先解释下几个名词:
-
External Variables
定义在函数外面的变量.
-
Static Variables
被 static 关键字修饰的变量, 这个变量可以是 External Variables 也可以是 Internal Variables (定义在函数里面的变量).
-
Constant Expression
简单来说就是在编译期间就能计算出值的表达式, 比如说, 常量的数学表达式 (1 + 1),
External 和 Static 的变量的取地址操作, 函数指针的赋值操作:
int foo() {
return 0;
}
int (*bar)() = foo;
具体的关于 Constant Expression 的定义可以参照 C99.
那么, 为什么 External 和 Static 的变量的初始化值要能在编译期间就确定呢?
因为编译完成后, External 和 Static 的变量是位于可执行文件的 data segment 中的,
这部分将和 code segment 一起载入到内存中, 所以他们的初始化值是在运行前就要确定的.
01 Sep 2013
重看了 “JavaScript: The Definitive Guide” 中的 Section 8.8: Function Scope and Closures, 略记录几点.
Scope
书中有这么一段话:
Functions in JavaScript are lexically rather than dynamically scoped.
This means that they run in the scope in which they are defined, not the scope from which they are executed.
一开始我对 define 产生了误解, 比如下面这段代码:
function foo() {
function bar() {
}
}
我本来对 define 的理解是, foo() 被 define 的时候, bar() 也被 define 了. 而事实是, 当 foo() 被调用的时候,
bar() 才被 define.
Closure
为什么要叫 Closure? 我印象中, 闭包应该是数学上的概念, 比如 Wiki 上对 Closure 的定义是:
A set has closure under an operation if performance of that operation on members of the set always produces a member of the same set.
再来看 “JavaScript: The Definitive Guide” 中对 Closure 的定义:
JavaScript functions are a combination of code to be executed and the scope in which to execute them.
This combination of code and scope is known as a closure in the computer science literature.
数学上对 Closure 的定义中有两个关键字: set 和 operation,
正好对应 JavsScript 对 Closure 的定义中的 scope 和 code. Code 对 scope 里的变量进行操作,
操作后的变量仍然是属于 scope 的. JavaScript 中 Closure 这个名字真的是取得再合适不过了!
27 Aug 2013
面向对象语言中, 为了找到一个方法的定义, 搜索继承图的顺序叫做 MRO (Method Resolution Order),
对于只支持单继承的语言, MRO 没什么好说的. 但对于支持多继承的语言, 比如 Python, MRO 就有搞头了.
在 Python 的发展过程中至少有三种 MRO 的算法: Classic, Python 2.2 new-style, Pyhon 2.3 new-style (a.k.a C3).
Classic
这是最简单的 MRO 算法了, 以子类为起点对继承图进行自左向右的深度优先遍历就行了.
比如下面这个例子:
class A: A
pass / \
/ \
class B(A): B C
pass \ /
\ /
class C(A): D
pass
class D(B, C):
pass
用 Classic 算法得到的顺序是 [D, B, A, C, A], 没错, A 出现了两次.
Python 2.2 new-style
Python 2.2 中 new-style class 的 MRO 算法有两个版本, 一种是在 PEP 253 中定义的,
另一种是 Python 2.2 中实际使用的. 所谓的 new-style class, 简单来说, 就是继承了 object 的类.
Documented
PEP 253 中的算法也很简单, 就是先对继承图做 Classic 算法得到可能有重复元素的 MRO, 然后将重复元素去掉,
仅保留最后一次出现的元素, 这样得到的就是最终的 MRO.
我们将上面一个例子修改下以使用 new-style class:
A = object
class A: A (object)
pass / \
/ \
class B(A): B C
pass \ /
\ /
class C(A): D
pass
class D(B, C):
pass
按照 PEP 253 的描述, 先用 Classic 算法得到 MRO, [D, B, A, C, A],
将重复元素去掉, 仅保留最后一次出现的元素, 这里我们去掉第一次出现的 A, 得到最终的 MRO, [D, B, C, A].
Implemented
按照 Guido van Rossum 的说法, 之所以 PEP 253 中的算法和实际中的算法不一样是因为,
他觉得实际中的算法描述起来比较繁琐, 并且他觉得两种算法没多大区别. 后来 Guido 自己也承认当时想法太天真了.
让我们用下面这个例子来说明两种算法之间的区别:
O = object
class A(O):
pass
class B(O):
pass
class X(A,B):
pass
class Y(B,A):
pass
继承图大概是这样的:
-----------
| |
| O |
| / \ |
- A B /
| / | /
| / |/
X Y
\ /
Z
你用 PEP 253 中的算法得到的 MRO 应该是这样的, [Z, X, Y, B, A, O]
但在 Python 2.2 中你会得到的是 [Z, X, Y, A, B, O] (可以用 Z.__mro__ 来得到)
网络上基本找不到与 Python 2.2 中实际采用的 MRO 算法相关的结果, 虽然 Guido 说这个算法是来源于 “Putting Metaclasses to Work” 这本书,
但我们是在研究实际中使用的算法, 还是看 Python 2.2 的源代码吧. 关于 new-style class 的 MRO 的算法在 Object/typeobject.c 中,
主要和下面这两个函数有关:
static int
conservative_merge(PyObject *left, PyObject *right)
{
int left_size;
int right_size;
int i, j, r, ok;
PyObject *temp, *rr;
assert(PyList_Check(left));
assert(PyList_Check(right));
again:
left_size = PyList_GET_SIZE(left);
right_size = PyList_GET_SIZE(right);
for (i = 0; i < left_size; i++) {
for (j = 0; j < right_size; j++) {
if (PyList_GET_ITEM(left, i) ==
PyList_GET_ITEM(right, j)) {
/* found a merge point */
temp = PyList_New(0);
if (temp == NULL)
return -1;
for (r = 0; r < j; r++) {
rr = PyList_GET_ITEM(right, r);
ok = PySequence_Contains(left, rr);
if (ok < 0) {
Py_DECREF(temp);
return -1;
}
if (!ok) {
ok = PyList_Append(temp, rr);
if (ok < 0) {
Py_DECREF(temp);
return -1;
}
}
}
ok = PyList_SetSlice(left, i, i, temp);
Py_DECREF(temp);
if (ok < 0)
return -1;
ok = PyList_SetSlice(right, 0, j+1, NULL);
if (ok < 0)
return -1;
goto again;
}
}
}
return PyList_SetSlice(left, left_size, left_size, right);
}
static PyObject *
mro_implementation(PyTypeObject *type)
{
int i, n, ok;
PyObject *bases, *result;
bases = type->tp_bases;
n = PyTuple_GET_SIZE(bases);
result = Py_BuildValue("[O]", (PyObject *)type);
if (result == NULL)
return NULL;
for (i = 0; i < n; i++) {
PyObject *base = PyTuple_GET_ITEM(bases, i);
PyObject *parentMRO;
if (PyType_Check(base))
parentMRO = PySequence_List(
((PyTypeObject*)base)->tp_mro);
else
parentMRO = classic_mro(base);
if (parentMRO == NULL) {
Py_DECREF(result);
return NULL;
}
if (serious_order_disagreements(result, parentMRO)) {
Py_DECREF(result);
return NULL;
}
ok = conservative_merge(result, parentMRO);
Py_DECREF(parentMRO);
if (ok < 0) {
Py_DECREF(result);
return NULL;
}
}
return result;
}
C 代码看起来比较繁琐, 用 Python 来描述大概就是这样的:
def conservative_merge(left, right):
for i in range(0, len(left)):
for j in range(0, len(right):
if left[i] == right[j]:
temp = []
for r in range(0, j):
rr = right[r]
if rr not in left:
temp.append(rr)
left[i:i] = temp
right[0:j+1] = []
return conservative_merge(left, right)
return left[len(left):len(left)] = right
def mro_implementation(cls):
bases = cls.bases
result = [cls]
for i in range(0, len(bases)):
base = bases[i]
parentMRO = base.mro
conservative_merge(result, parentMRO)
return result
关于上面的 Python 代码有如下说明:
- 假设 MRO 使用 List 来表示
- 假设每个 Class object 有两个属性 bases 和 mro, 分别表示这个类直接继承的类的列表和这个类的 MRO.
你可以试着用这个算法计算下面这个例子里 Z 的 MRO:
class A(object):
pass
class B(object):
pass
class C(object):
pass
class D(object):
pass
class E(object):
pass
class K1(A,B,C):
pass
class K2(D,B,E):
pass
class K3(D,A):
pass
class Z(K1,K2,K3):
pass
Python 2.2 给出的 MRO 是 [Z, K1, K3, A, K2, D, B, C, E, O]
Python 2.3 new-style
自从 Python 2.3 之后, Python new-style class 的 MRO 算法使用 C3 算法, 这里就不叙述了, 网上资料挺多的,
比如这里.
References
The Python 2.3 Method Resolution Order
Unifying types and classes in Python 2.2
PEP 253 – Subtyping Built-in Types
[Python-Dev] perplexed by mro
The History of Python: Method Resolution Order