Category Theory

A category consists of three parts:

• A collection of objects.
• A collection of morphisms, each of which map one object to another.
• A composition operator of these morphisms, i.e. morphisms can be composed. If f: A -> B and g: B -> C are morphisms, f.g generates a new morphism A -> C.

Note that a morphism has no specific semantics of mapping, but simply links two objects together. Morphisms are also called Arrows.

Examples

Set Category: Set

All sets and standard functions form a category. Functions need not to be surjective, since morphisms have no mapping semantics.

Group Category: Grp

All groups and homomorphisms between groups form a category. A group has specific algebaric structure, which morphisms should preserve.

Laws

Three laws that a category should obey:

• Composition should be associative.
• Composition operation should be enclosed in the category, i.e. if f: A -> B and g: B -> C, there must be a h: A -> C satisfying h = f . g.
• For each object A, there should exist an identity morphism id(A): A -> A s.t. for every f: A -> B, f = id(A) . f = f . id(B).

Note that:

• There may exist serveral morphisms between A and B.
• An identity has type A -> A, but a morphism with such type needs not to be an identity.

Functors in Category Theory

A functor maps a category to another category. It should contains two mappings for objects and for morphisms, with composition operation and category laws preserved.

There’s a trivial functor from Grp to Set, which maps groups to their underlying sets, and group morphisms to functions with same behavior but defined on sets instead of groups.

Paramateric Types in Haskell

It’s common to create new types that hold values of other types. List[a] type constructor creates types that holds sequential values of same type; Maybe[a] creates types that hold operation states (failure, or success with returned values).

Usually we expect derived types to inherit functions from types being wrapped. For example, List[Int] should have element-wise addition as Int does, and Maybe[Int] should have similar operations with no burden of re-wrapping and unwrapping. Such ‘inheritance’ should be done automatically if possible, since it is only concerned with the structure of types instead of specific functions.

Hask Category

Haskell language itself forms a category, with all types being objects, and functions being morphisms. Such category is called Hask.

Hask Functors

class Functor m where
    fmap :: (a -> b) -> m a -> m b

A parameteric type implementing class Functor is a category functor, mapping Hask to one of its sub-category, where types m a are the object collection. The type constructor m maps objects, and specific fmap defined on m maps corresponding functions.

It’s worth noted that (a -> b) -> m a -> m b can also read as (a -> b) -> (m a -> m b), as -> is right-associative. This may provide a clearer view of fmap, which takes a regular function in Hask and returns the corresponding function in sub-category.

Examples:

fmap (+) :: List[Int] -> List[Int] generates element-wise addition in List[Int].

fmap (+) :: Maybe Int -> Maybe Int generates such function:

maybePlus :: Maybe Int -> Maybe Int
maybePlus _        Nothing  = Nothing
maybePlus Nothing  _        = Nothing
maybePlut (Just x) (Just y) = Maybe (x + y)

新类型有自己的 data constructor（literals 可以看成特殊的 data constructor），由这一点来区分是否创建了新类型。

• data 创建了新类型，可以有多个 data constructor。
• newtype 创建了新类型，只能有一个 data constructor，同时新类型的内存布局与原来的类型相同。
• type 没有创建新类型，只是建立了 alias，没有新的 data constructor。

type

常用于语义化类型，是业务逻辑层的概念。

type ID = Int

a = 1 :: ID
b = a + 2 -- legal

showID :: ID -> IO ()
showID x = print x -- legal, since Int has already been an instance of class Show

-- illegal, since Int has already been instantiated
instance Show ID where
    -- ...

newtype

在编译期创建新类型，但差异在运行期被抹去。带有一个构造器。

newtype ID' = ID' Int

a = ID' 1
b = a + 2 -- illegal, since Int and ID' are totally different types

showID' :: ID' -> IO ()
showID' x = print x -- illegal, since ID' is not an instance of Show

-- either
showID' (ID' x) = print x
-- or
instance Show ID' where
    show (ID' x) = show x

Prelude.foldl

foldl 为 left-associative folding。

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

foldl (+) 0 [1..3] 等价于 (((0 + 1) + 2) + 3)。

• 尾递归，因此有 strict 版本 foldl'
• 求值时必须先到达栈底，遍历完列表，因此无法处理无穷列表

Data.List.foldl’

foldl' 为 foldl 的 TRO 版本。

Prelude.foldr

foldr 为 right-associative folding。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

foldr (+) 0 [1..3] 等价于 (0 + (1 + (2 + 3)))

• 没有尾递归，有爆栈的危险。
• 有向右展开的特点，而 Haskell 中许多数据结构都有向右递归的特点（如 Cons），因此可以很好地处理无穷递归的数据，从而更加通用。

Prelude.foldl1 && Prelude.foldr1

Helper functions。将 operator 限制为同一种类型，同时约去 accumulator。

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error

foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f (x:xs) = foldr f x xs
foldr1 _ [] = error

即，foldr1 将列表的第一个值作为 accumulator，将剩余部分作为 list，传给 foldr。foldl 同理。

实践

用 folds 实现 reverse

reversel, reverser :: [a] -> [a]
reversel list = foldl (\acc x -> x : acc) [] list

reverser list = foldr (\x acc -> acc ++ [x]) [] list

用 foldr 实现 foldl

先归纳出 foldr 的泛性质。如果一个函数 g s.t.

g [] = v
g (x:xs) = f x (g xs)

则 g list === foldr f v list.

再看 foldl 的定义：

foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

===>

foldl f v list = g list v
    where
        g [] v = v
        g (x:xs) v = g xs (f v x)
        -- 从左到右依次更新 v

===>

foldl f v list = g list v
    where
        g [] = id
        g (x:xs) = \v -> g xs (f v x)

应有 g (x:xs) === k x (g xs)，我们计算 k：

g (x:xs)       === k x (g xs)
g (x:xs) v     === k x (g xs) v
g xs (f v x)   === k x (g xs) v
(g xs) (f v x) === k x (g xs) v
g' (f v x)     === k x g' v
k              === \x g' v -> g' (f v x)

所以

foldl f v xs =
    (foldr
        (\x g' v -> g' (f v x))
        id
        xs
    ) v

写在前面

• 作者电脑 CPU 为 4 核，因此使用 4 个线程测试是合理的
• 本文使用的 cpython 版本为 3.6.4
• 本文使用的 pypy 版本为 5.9.0-beta0，兼容 Python 3.5 语法
• 本文使用的 jython 版本为 2.7.0，兼容 Python 2.7 语法
• 若无特殊说明，作语言解时，python 指 Python 语言；作解释器解时，python 指 cpython

写在前面

前几天工作时遇到了一个匪夷所思的问题。经过几次尝试后问题得以解决，但问题产生的原因却仍令人费解。查找 SO 无果，我决定翻看 Python 的源码。断断续续地研究了几天，终于恍然大悟。撰此文以记。

概念

Linux 中的每一个文件都有其 所属用户 及 所属用户组，根据这两个属性可将文件访问者分为三类：所属用户自己、所属用户组中的用户 和 其他用户，我们可以针对不同的访问者设置不同的用户权限。

“访问”可分为三类：读、写 与 执行。我们可以用 ls -l 命令查看一个文件的权限：

$ touch test
$ ls -l test
-rw-rw-r-- 1 hsfzxjy hsfzxjy 0 Jul  3 23:44 test

首部的 -rw-rw-r-- 即为文件的权限位。权限应该分为四部分来看：-/rw-/rw-/r--。第一部分标志文件的类型，如 普通文件（-）、目录（d）、UNIX 套接字（s）、符号链接（l）、块设备（b）等等。接下来的三个部分依次代表 所属用户、所属用户组、其他用户 的权限，每部分由三个标志位组成：读标志位、写标志位、执行标志位。

目录的权限

目录是一种特殊的文件，因此也拥有文件权限的概念，但权限的语义与普通文件稍有差异：

• 读：读取目录下文件列表，相关命令如 ls
• 写：创建、删除目录下的文件，相关命令如 touch（当文件不存在时）、rm 等
• 执行：进入目录，相关命令如 cd

特殊权限

出于某些特殊目的，Linux 中存在两个特殊的权限位：粘滞位（t）、Set Id（s）。这两个权限可以 叠加 在执行权限位上，其中 Set Id 可以置于 所属用户 和 所属用户组 的权限组上，而 粘滞位 只能置于 其他用户 权限组上。当特殊权限被设置时，执行权限位上即会显示 s/t （已有 x 权限）或 S/T （尚未有 x 权限）。

粘滞位

粘滞位的作用是 防止他人误删自己的文件。当某个目录的其他用户权限组有 w 权限时，系统中的其他用户即可随意删除目录中的文件。而一旦叠加上 t 权限，只有文件的所有者方能删除文件。一个经典的例子是 /tmp：

$ ls -l /
drwxrwxrwt  13 root root 12288 Jul  4 00:15 tmp/

Set Id

Linux 中的进程也有自己所属用户与用户组。一般而言，进程的所属用户即为其发起者，但这会引起一些麻烦。一个例子是 passwd 命令，该命令需要修改属于 root 用户的系统文件以保存密码，倘若进程所属用户即为所属者，此功能则无法实现。

Set Id 权限的作用是：在文件被执行时，将其有效用户/用户组设置为文件的用户/用户组，而不是当前执行者。下面是一个演示：

设当前用户为 hsfzxjy，我们在 /tmp 下创建一个 test 文件，并删去其他用户的 r 权限：

$ cd /tmp
$ echo test text > test
$ chmod o-r test
$ ll test
-rw-rw---- 1 hsfzxjy hsfzxjy 0 Jul  4 00:28 test

由于 test 文件的所属用户是 hsfzxjy，其他用户没有权限读取其中的内容：

$ sudo -u mysql cat test
cat: test: Permission denied

现在我们修改一下 cat 命令的权限，为了不影响系统文件，我们拷贝一份 cat 副本至当前目录：

$ cp /bin/cat .
$ chmod u+s cat
$ ll cat
-rwsr-xr-x 1 hsfzxjy hsfzxjy 52080 Jul  4 00:34 cat*

再以 mysql 的身份执行命令：

$ sudo -u mysql ./cat test
test text

可见 ./cat 在执行时所属用户是 hsfzxjy。我们可以使用 ps 命令更清楚地看到这点：

$ sudo -u mysql cat
# 在另一个终端中
$ ps -eo euser,ruser,comm | grep cat
mysql    mysql    cat

# -----------

$ sudo -u mysql ./cat
# 在另一个终端中
$ ps -eo euser,ruser,comm | grep cat
hsfzxjy  mysql    cat

技术流水账一篇，记录踩过的坑

Channels 异构

Django Channels 官方文档宣称 channels 的最佳配置是使用其自带的服务器组件 Daphne，但在开发中我发现 daphne 处理普通请求比在 WSGI 架构下慢了好几倍，更何况使用 daphne 派发静态文件是十分不切实际的。于是我将 http.request 和 websocket.* 两个 channel 解耦，前者使用 nginx 配合 uwsgi 处理，后者使用 nginx 反向代理至 daphne 处理。这样一来便可充分利用两种架构的优势。

旧架构：

新架构：

神的时代已离去 神的故事却化为传说 流落凡间 供凡人传颂、膜拜

这是什么

在上世纪 90 年代，出现过一款不可思议的游戏——雷神之锤（Quake series）。除了优秀的情节设定和精美的画面，最让人称道的莫过于它的运行效率——要知道在那个计算机配置低下的时代，一段小动画都是一个奇迹，但 Quake 却能流畅地运行于各种配置的电脑上。

直至 2005 年，当 Quake Engine 开源时，Quake 系列的秘密才被揭开。在代码库中，人们发现了许多堪称神来之笔的算法。它们以极其变态的高效率，压榨着计算机的性能，进而才支撑起了 90 年代 3D 游戏的传奇。其中的某些算法，甚至比系统原生的实现还要快！

我们今天的主角——快速平方根倒数算法（Fast Inverse Square Root）就是其中一个。

《神坑》系列将会不定期更新一些可遇而不可求的坑 防止他人入坑，也防止自己再次入坑

简化版问题

现有两个 View 类：

class View(object):

    def method(self):
        # Do something...
        pass

class ChildView(View):

    def method(self):
        # Do something else ...
        super(ChildView, self).method()

以及一个用于修饰该类的装饰器函数 register——用于装饰类的装饰器很常见（如 django.contrib.admin 的 register），通常可极大地减少定义相似类时的工作量：

class Mixin(object):
    pass

def register(cls):

    return type(
        'DecoratedView',
        (Mixin, cls),
        {}
    )

这个装饰器为被装饰类附加上一个额外的父类 Mixin，以增添自定义的功能。

完整的代码如下：

class Mixin(object):
    pass

def register(cls):

    return type(
        cls.__name__,
        (Mixin, cls),
        {}
    )

class View(object):

    def method(self):
        # Do something...
        pass

@register
class ChildView(View):

    def method(self):
        # Do something else ...
        super(ChildView, self).method()

看上去似乎没什么问题。然而一旦调用 View().method()，却会报出诡异的 无限递归 错误：

# ...
File "test.py", line 23, in method
  super(ChildView, self).method()
File "test.py", line 23, in method
  super(ChildView, self).method()
File "test.py", line 23, in method
  super(ChildView, self).method()
RuntimeError: maximum recursion depth exceeded while calling a Python object

【一脸懵逼】

猜想 & 验证

从 Traceback 中可以发现：是 super(ChildView, self).method() 在不停地调用自己——这着实让我吃了一惊，因为 按理说 super 应该沿着继承链查找父类，可为什么在这里 super 神秘地失效了呢？

为了验证 super(...).method 的指向，可以尝试将该语句改为 print(super(ChildView, self).method)，并观察结果：

<bound method ChildView.method of <__main__.ChildView object at 0xb70fec6c>>

输出表明： method 的指向确实有误，此处本应为 View.method。

super 是 python 内置方法，肯定不会出错。那，会不会是 super 的参数有误呢？

super 的签名为 super(cls, instance)，宏观效果为 遍历 cls 的继承链查找父类方法，并以 instance 作为 self 进行调用。如今查找结果有误，说明 继承链是错误的，因而极有可能是 cls 出错。

因此，有必要探测一下 ChildView 的指向。在 method 中加上一句： print(ChildView)：

<class '__main__.DecoratedView'>

原来，作用域中的 ChildView 已经被改变了。

真相

一切都源于装饰器语法糖。我们回忆一下装饰器的等价语法：

@decorator
class Class:
    pass

等价于

class Class:
    pass

Class = decorator(Class)

这说明：装饰器会更改该作用域内被装饰名称的指向。

这本来没什么，但和 super 一起使用时却会出问题。通常情况下我们会将本类的名称传给 super（在这里为 ChildView），而本类名称和装饰器语法存在于同一作用域中，从而在装饰时被一同修改了（在本例中指向了子类 DecoratedView），进而使 super(...).method 指向了 DecoratedView 的最近祖先也就是 ChildView 自身的 method 方法，导致递归调用。

解决方案

找到了病因，就不难想到解决方法了。核心思路就是：不要更改被装饰名称的引用。

如果你只是想在内部使用装饰后的新类，可以在装饰器方法中使用 DecoratedView，而在装饰器返回时 return cls，以保持引用不变：

def register(cls):

    decorated = type(
        'DecoratedView',
        (Mixin, cls),
        {}
    )

    # Do something with decorated

    return cls

这种方法的缺点是：从外部无法使用 ChildView.another_method 调用 Mixin 上的方法。可如果真的有这样的需求，可以采用另一个解决方案：

def register(cls):

    cls.another_method = Mixin.another_method
    return cls

即通过赋值的方式为 cls 添加 Mixin 上的新方法，缺点是较为繁琐。

两种方法各有利弊，要根据实际场景权衡使用。

写在前面

• 本文为科普文
• 本文中的例子在 Ubuntu 14.04 / Python 2.7.11 下运行成功，Python 3+ 的接口有些许不同，需要读者自行转换

引子

先看一段代码：

example.py：

# -*- conding=yi -*-

从 math 导入 sin, pi

打印 'sin(pi) =', sin(pi)

这是什么？！是 Python 吗？可以运行吗？——想必你会问。

我可以明确告诉你：这不是 Python，但它可以用 Python 解释器运行。当然，如果你愿意，可以叫它“Yython” （易语言 + Python）。

怎么做到的？也许你已经注意到第一行的奇怪注释——没错，秘密全在这里。

这种黑魔法，还要从 PEP 263 说起。