乍听之下,不无道理;仔细揣摩,胡说八道

0%

在 Common Lisp 中,打印整数一般用函数format。例如,上面的代码会往标准输出中打印出233这个数字:

1
(format t "~D" 233)

除此之外,format还可以控制打印内容的宽度、填充字符、是否打印正负号等方面。例如,要控制打印的内容至少占据6列的话,可以用如下代码

1
(format t "~6D" 233)

如果不使用字符串形式的 DSL,而是以关键字参数的方式来实现一个能够达到同样效果的函数format-decimal,代码可能如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(defun format-decimal (n
&key
mincol)
"打印整数 N 到标准输出。

MINCOL 如果不为 NIL,则表示所打印的内容至少要占据的列数。"
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits '()))
(cond ((zerop n)
(push 0 digits))
(t
(do ((n n (truncate n 10)))
((zerop n))
(push (rem n 10) digits))))
;; 打印出填充用的空格。
(when (and (integerp mincol) (> mincol (length digits)))
(dotimes (i (- mincol (length digits)))
(declare (ignorable i))
(princ #\Space)))

(dolist (digit digits)
(princ (code-char (+ digit (char-code #\0)))))))

(format-decimal 233 :mincol 6)

如果要求用数字0而不是空格来填充左侧的列,用format的写法如下:

1
(format t "~6,'0D" 233)

format-decimal想要做到同样的事情,可以这么写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
(defun format-decimal (n
&key
mincol
(padchar #\Space))
"打印整数 N 到标准输出。

MINCOL 如果不为 NIL,则表示所打印的内容至少要占据的列数。
PADCHAR 表达式为了填充多余的列时所用的字符。"
(check-type mincol (or integer null))
(check-type padchar character)
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits '()))
(cond ((zerop n)
(push 0 digits))
(t
(do ((n n (truncate n 10)))
((zerop n))
(push (rem n 10) digits))))
;; 打印出填充用的空格。
(when (and (integerp mincol) (> mincol (length digits)))
(dotimes (i (- mincol (length digits)))
(declare (ignorable i))
(princ padchar)))

(dolist (digit digits)
(princ (code-char (+ digit (char-code #\0)))))))

(format-decimal 233 :mincol 6 :padchar #\0)

-D默认是不会打印非负整数的符号的,可以用修饰符@来修改这个行为。例如,(format t "~6,'0@D" 233)会打印出00+233。稍微修改一下就可以在format-decimal中实现同样的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(defun format-decimal (n
&key
mincol
(padchar #\Space)
signed)
"打印整数 N 到标准输出。

MINCOL 如果不为 NIL,则表示所打印的内容至少要占据的列数。
PADCHAR 表达式为了填充多余的列时所用的字符。"
(check-type mincol (or integer null))
(check-type padchar character)
(flet ((to-digits (n)
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits '()))
(cond ((zerop n)
(push #\0 digits))
(t
(do ((n n (truncate n 10)))
((zerop n))
(push (code-char (+ (rem n 10) (char-code #\0))) digits))))
digits)))
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits (to-digits (abs n))))
(when (or signed (< n 0))
(push (if (< n 0) #\- #\+) digits))
;; 打印出填充用的空格。
(when (and (integerp mincol) (> mincol (length digits)))
(dotimes (i (- mincol (length digits)))
(declare (ignorable i))
(princ padchar)))

(dolist (digit digits)
(princ digit)))))

(format-decimal 233 :mincol 6 :padchar #\0 :signed t)

除了@之外,:也是一个~D的修饰符,它可以让format每隔3个数字就打印出一个逗号,方便阅读比较长的数字。例如,下列代码会打印出00+23,333

1
(format t "~9,'0@:D" 23333)

为此,给format-decimal新增一个关键字参数comma-separated来控制这一行为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
(defun format-decimal (n
&key
comma-separated
mincol
(padchar #\Space)
signed)
"打印整数 N 到标准输出。

COMMA-SEPARATED 如果为 T,则每打印3个字符就打印一个逗号。
MINCOL 如果不为 NIL,则表示所打印的内容至少要占据的列数。
PADCHAR 表示填充多余的列时所用的字符。
SIGNED 控制是否显示非负整数的加号。"
(check-type comma-separated boolean)
(check-type mincol (or integer null))
(check-type padchar character)
(check-type signed boolean)
(flet ((to-digits (n)
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits '()))
(cond ((zerop n)
(push #\0 digits))
(t
(do ((count 0 (1+ count))
(n n (truncate n 10)))
((zerop n))
(when (and comma-separated (> count 0) (zerop (rem count 3)))
(push #\, digits))
(push (code-char (+ (rem n 10) (char-code #\0))) digits))))
digits)))
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits (to-digits (abs n))))
(when (or signed (< n 0))
(push (if (< n 0) #\- #\+) digits))
;; 打印出填充用的空格。
(when (and (integerp mincol) (> mincol (length digits)))
(dotimes (i (- mincol (length digits)))
(declare (ignorable i))
(princ padchar)))

(dolist (digit digits)
(princ digit)))))

(format-decimal -23333 :comma-separated t :mincol 9 :padchar #\0 :signed t)

事实上,打印分隔符的步长,以及作为分隔符的逗号都是可以定制的。例如,可以改为每隔4个数字打印一个连字符

1
(format t "~9,'0,'-,4@:D" 23333)

对于format-decimal来说这个修改现在很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
(defun format-decimal (n
&key
(commachar #\,)
(comma-interval 3)
comma-separated
mincol
(padchar #\Space)
signed)
"打印整数 N 到标准输出。

COMMACHAR 表示当需要打印分隔符时的分隔符。
COMMA-INTERVAL 表示当需要打印分隔符时需要间隔的步长。
COMMA-SEPARATED 如果为 T,则每打印3个字符就打印一个逗号。
MINCOL 如果不为 NIL,则表示所打印的内容至少要占据的列数。
PADCHAR 表示填充多余的列时所用的字符。
SIGNED 控制是否显示非负整数的加号。"
(check-type commachar character)
(check-type comma-interval integer)
(check-type comma-separated boolean)
(check-type mincol (or integer null))
(check-type padchar character)
(check-type signed boolean)
(flet ((to-digits (n)
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits '()))
(cond ((zerop n)
(push #\0 digits))
(t
(do ((count 0 (1+ count))
(n n (truncate n 10)))
((zerop n))
(when (and comma-separated (> count 0) (zerop (rem count comma-interval)))
(push commachar digits))
(push (code-char (+ (rem n 10) (char-code #\0))) digits))))
digits)))
;; 通过取余的方式得到 N 的每一位并逐个入栈,之后出栈的顺序就是从左到右打印的顺序了。
(let ((digits (to-digits (abs n))))
(when (or signed (< n 0))
(push (if (< n 0) #\- #\+) digits))
;; 打印出填充用的空格。
(when (and (integerp mincol) (> mincol (length digits)))
(dotimes (i (- mincol (length digits)))
(declare (ignorable i))
(princ padchar)))

(dolist (digit digits)
(princ digit)))))


(format-decimal -23333 :commachar #\- :comma-interval 4 :comma-separated t :mincol 9 :padchar #\0 :signed t)

全文完。

众所周知,在 Java 语言中支持基于子类型的多态,例如某百科全书中就给了一个基于Animal及其两个子类的例子(代码经过我微微调整)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
abstract class Animal {
abstract String talk();
}

class Cat extends Animal {
String talk() {
return "Meow!";
}
}

class Dog extends Animal {
String talk() {
return "Woof!";
}
}

public class Example {
static void letsHear(final Animal a) {
System.out.println(a.talk());
}

public static void main(String[] args) {
letsHear(new Cat());
letsHear(new Dog());
}
}

基于子类型的多态要求在程序的运行期根据参数的类型,选择不同的具体方法——例如在上述例子中,当方法letsHear中调用了参数a的方法talk时,是依照变量a在运行期的类型(第一次为Cat,第二次为Dog)来选择对应的talk方法的实例的,而不是依照编译期的类型Animal

但在不同的语言中,在运行期查找方法时,所选择的参数的个数是不同的。对于 Java 而言,它只取方法的第一个参数(即接收者),这个策略被称为 single dispatch。

Java 的 single dispatch

要演示为什么 Java 是 single dispatch 的,必须让示例代码中的方法接收两个参数(除了方法的接收者之外再来一个参数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 演示 Java 是 single dispatch 的。
abstract class Shape {}

class Circle extends Shape {}

class Rectangle extends Shape {}

class Triangle extends Shape {}

abstract class AbstractResizer
{
public abstract void resize(Circle c);
public abstract void resize(Rectangle r);
public abstract void resize(Shape s);
public abstract void resize(Triangle t);
}

class Resizer extends AbstractResizer
{
public void resize(Circle c) { System.out.println("缩放圆形"); }
public void resize(Rectangle r) { System.out.println("缩放矩形"); }
public void resize(Shape s) { System.out.println("缩放任意图形"); }
public void resize(Triangle t) { System.out.println("缩放三角形"); }
}

public class Trial1
{
public static void main(String[] args)
{
AbstractResizer resizer = new Resizer();
Shape[] shapes = {new Circle(), new Rectangle(), new Triangle()};
for (Shape shape : shapes)
{
resizer.resize(shape);
}
}
}

显然,类Resizer的实例方法resize就是接收两个参数的——第一个为Resizer类的实例对象,第二个则可能是Shape及其三个子类中的一种类的实例对象。假如 Java 的多态策略是 multiple dispatch 的,那么应当分别调用不同的三个版本的resize方法,但实际上并不是

通过 JDK 中提供的程序javap可以看到在main方法中调用resize方法时究竟用的是类Resizer中的哪一个版本,运行命令javap -c -l -s -v Trial1,可以看到调用resize方法对应的 JVM 字节码为invokevirtual

翻阅 JVM 规格文档可以找到对invokevirtual 指令的解释

显然,由于在 JVM 的字节码中,invokevirtual所调用的方法的参数类型已经解析完毕——LShape表示是一个叫做Shape的类,因此在方法接收者,即类Resizer中查找的时候,也只会命中resize(Shape s)这个版本的方法。变量s的运行期类型在查找方法的时候,丝毫没有派上用场,因此 Java 的多态是 single dispatch 的。

想要依据参数的运行期类型来打印不同内容也不难,简单粗暴的办法可以选择instanceOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
abstract class AbstractResizer 
{
public abstract void resize(Shape s);
}

class Resizer extends AbstractResizer
{
public void resize(Shape s) {
if (s instanceof Circle) {
System.out.println("缩放圆形");
} else if (s instanceof Rectangle) {
System.out.println("缩放矩形");
} else if (s instanceof Triangle) {
System.out.println("缩放三角形");
} else {
System.out.println("缩放任意图形");
}
}
}

或者动用 Visitor 模式。

什么是 multiple dispatch?

我第一次知道 multiple dispatch 这个词语,其实就是在偶然间查找 CLOS 的相关资料时看到的。在 Common Lisp 中,定义类和方法的语法与常见的语言画风不太一样。例如,下列代码跟 Java 一样定义了四个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(defclass shape ()
())

(defclass circle (shape)
())

(defclass rectangle (shape)
())

(defclass triangle (shape)
())

(defclass abstract-resizer ()
())

(defclass resizer (abstract-resizer)
())

(defgeneric resize (resizer shape))

(defmethod resize ((resizer resizer) (shape circle))
(format t "缩放圆形~%"))

(defmethod resize ((resizer resizer) (shape rectangle))
(format t "缩放矩形~%"))

(defmethod resize ((resizer resizer) (shape shape))
(format t "缩放任意图形~%"))

(defmethod resize ((resizer resizer) (shape triangle))
(format t "缩放三角形~%"))

(let ((resizer (make-instance 'resizer))
(shapes (list
(make-instance 'circle)
(make-instance 'rectangle)
(make-instance 'triangle))))
(dolist (shape shapes)
(resize resizer shape)))

执行上述代码会调用不同版本的resize方法来打印内容

由于defmethod支持给每一个参数都声明对应的类这一做法是在太符合直觉了,以至于我丝毫没有意识到它有一个专门的名字叫做 multiple dispatch,并且在大多数语言中是不支持的。

后记

聪明的你应该已经发现了,在上面的 Common Lisp 代码中,其实与 Java 中的抽象类AbstractResizer对应的类abstract-resizer是完全没有必要的,defgeneric本身就是一种用来定义抽象接口的手段。

此外,在第三个版本的resize方法中,可以看到标识符shape同时作为了参数的名字和该参数所属的类的名字——没错,在 Common Lisp 中,一个符号不仅仅可以同时代表一个变量和一个函数,同时还可以兼任一个类型,它不仅仅是一门通常所说的 Lisp-2 的语言。

众所周知,我用Emacsledger-mode来记账(参见以前的文章《程序员的记账工具——ledger与ledger-mode》)。作为一个出色的命令行报表工具,ledger的命令balanceregister足以涵盖大部分的使用场景:

  • balance可以生成所有帐号的余额的报表,用于每天与各个账户中的真实余额进行比较;
  • register可以生成给定帐号的交易明细,用于在余额不一致时与真实账户的流水一条条核对;

美中不足的是,ledger的报表不够直观,因为它们是冷冰冰的文字信息,而不是振奋人心的统计图形。好在,正如ledger不存储数据,而只是一份份.ledger文件中的交易记录的搬运工一样,gnuplot也是这样的工具——它不存储数据,它只负责将存储在文本文件的数据以图形的形态呈现出来。

如何运用gnuplot

gnuplot是很容易使用的。以最简单的情况为例,首先将如下内容保存到文件/tmp/data.csv

1
2
3
-1 -1
0 0
1 1

然后在命令行中启动gnuplot,进入它的 REPL 中,并执行如下命令

1
plot "/tmp/data.csv"

即可得到这三组数据的展示

三组数据分别是坐标为(-1, -1)(0, 0),以及(1, 1)的点。

因此要让gnuplot绘制开销的图形,首先就是从账本中提取出要绘制的数据,再决定如何用gnuplot绘制即可。

ledger提取开销记录

尽管ledger的子命令register可以打印出给定帐号的交易明细,但此处更适合使用csv子命令。例如,下列的命令可以将最早的10条、吃的方面的支出记录,都以 CSV 格式打印出来

1
2
3
4
5
6
7
8
9
10
11
➜  Accounting ledger --anon --head 10 -f 2021.ledger csv 'Expense:Food'
"2019/09/10","","32034acc","efe2a5b9:c720f278:58a3cd91:0dc07b7b","A","20","",""
"2019/09/11","","a61b6164","5d45e249:fe84ca06:778d1855:daf61ede","A","5","",""
"2019/09/11","","674ec19f","5d018df1:ebf020db:29d43aba:d0c84127","A","15","",""
"2019/09/11","","e55ff018","370ca545:7d3aa2d0:86f5f330:1379261b","A","20","",""
"2019/09/12","","f6aa675c","08315491:4c8f1ee7:5eeaddf3:f879914e","A","10.5","",""
"2019/09/12","","139b790f","a137e4ee:9bc8ee49:7d7ccd8b:472d6007","A","23.9","",""
"2019/09/12","","b24b716d","de348971:5364622c:b2144d94:01e74ff3","A","148","",""
"2019/09/13","","e7c066fa","b418a3b2:a3e21e87:a32ee8ac:8716a847","A","3","",""
"2019/09/13","","9eb044fe","702a13e9:3de7f1bd:9b20a278:1d20668d","A","24","",""
"2019/09/13","","ba301270","d2b7eeb3:381f9473:54f86a33:391a8662","A","36","",""

--anon选项可以将交易明细中的敏感信息(如收款方、帐号)等匿名处理。

尽管ledger打印出的内容有很多列,但只有第一列的日期,以及第六列的金额是我所需要的。同时,由于一天中可能会有多次吃的方面的开销,因此同一天的交易也会有多笔,在绘图之前,需要将同一天之中的开销累加起来,只留下一个数字。这两个需求,都可以用csvsql来满足。

csvsql聚合数据

以前文中的10条记录为例,用如下的命令可以将它们按天聚合在一起

1
ledger --anon --head 10 -f 2021.ledger csv 'Expense:Food' | csvsql -H --query 'SELECT `a`, SUM(`f`) FROM `expense` GROUP BY `a` ORDER BY `a` ASC' --tables 'expense'

其中:

  • 选项-Hcsvsql知道从管道中输入的数据没有标题行。后续处理时,csvsql会默认使用abc等作为列名;
  • 选项--query用于提交要执行的 SQL 语句;
  • 选项--tables用于指定表的名字,这样在--query中才能用 SQL 对其进行处理;

结果如下

1
2
3
4
5
6
➜  Accounting ledger --anon --head 10 -f 2021.ledger csv 'Expense:Food' | csvsql -H --query 'SELECT `a`, SUM(`f`) FROM `expense` GROUP BY `a` ORDER BY `a` ASC' --tables 'expense'
a,SUM(`f`)
2019-09-10,20
2019-09-11,40
2019-09-12,182.4
2019-09-13,63

gnuplot读取数据并绘图

用重定向将csvsql的输出结果保存到文件/tmp/data.csv中,然后就可以用gnuplot将它们画出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
➜  Accounting ledger --anon --head 10 -f 2021.ledger csv 'Expense:Food' | csvsql -H --query 'SELECT `a`, SUM(`f`) FROM `expense` GROUP BY `a` ORDER BY `a` ASC' --tables 'expense' | tail -n '+2' > /tmp/data.csv
➜ Accounting cat /tmp/plot_expense.gplot
set format x '%y-%m-%d'
set style data boxes
set terminal png font '/System/Library/Fonts/Hiragino Sans GB.ttc'
set title '吃的开销'
set output '/tmp/xyz.png'
set timefmt '%Y-%m-%d'
set xdata time
set xlabel '日期'
set xrange ['2019-09-10':'2019-09-13']
set ylabel '金额(¥)'
set yrange [0:200]
set datafile separator comma
plot '/tmp/data.csv' using 1:2
➜ Accounting gnuplot /tmp/plot_expense.gplot

生成的图片文件/tmp/xyz.png如下

在脚本文件/tmp/plot_expense.gplot中用到的命令都可以通过gnuplot在线手册查阅到:

  • set format命令用于设置坐标轴的刻度的格式。set format x "%y-%m-%d"意味着设置 X 轴的刻度为形如19-09-10的格式;
  • set style data命令设置数据的绘制风格。set style data box表示采用空心柱状图;
  • set terminal命令用于告诉gnuplot该生成什么样的输出。set terminal png font '/System/Library/Fonts/Hiragino Sans GB.ttc'表示输出结果为 PNG 格式的图片,并且采用给定的字体;
  • set title命令控制输出结果顶部中间位置的标题文案;
  • set output命令用于将原本输出到屏幕上的内容重定向到文件中;
  • set timefmt命令用于指定输入的日期时间数据的格式。set timefmt '%Y-%m-%d'意味着输入的日期时间数据的为形如2019-09-10的格式;
  • set xdata命令控制gnuplot如何理解属于 X 轴的数据。set xdata time表示 X 轴上的均为时间型数据;
  • set xlabel命令控制 X 轴的含义的文案。set ylabel与其类似,只是作用在 Y 轴上;
  • set xrange命令控制gnuplot所绘制的图形中 X 轴上的展示范围;
  • set datafile separator命令控制gnuplot读取数据文件时各列间的分隔符,comma表示分隔符为逗号。

想要按周统计怎么办

假设我要查看的是2021年每一周在吃的方面的总开支,那么需要在csvsql中将数据按所处的是第几周进行聚合

1
2
3
4
5
6
7
8
9
10
11
12
➜  Accounting ledger -b '2021-01-01' -f 2021.ledger csv 'Expense:Food' | csvsql -H --query 'SELECT strftime("%W", `a`) AS `week`, SUM(`f`) FROM `expense` GROUP BY `week` ORDER BY `a` ASC' --tables 'expense' | tail -n '+2' > /tmp/expense_dow.csv
➜ Accounting head /tmp/expense_dow.csv
00,633.6
01,437.3
02,337.5
03,428.4
04,191.5
05,330.4
06,154.6
07,621.4
08,485.6
09,375.73

同时也需要调整gnuplot的脚本

1
2
3
4
5
6
7
8
9
set terminal png font '/System/Library/Fonts/Hiragino Sans GB.ttc'
set title '吃的开销'
set output '/tmp/xyz2.png'
set xlabel '第几周'
set xrange [0:54]
set ylabel '金额(¥)'
set yrange [0:1000]
set datafile separator comma
plot '/tmp/expense_dow.csv' using 1:2 with lines

结果如下

想要同时查看两年的图形怎么办

gnuplot支持同时绘制多条曲线,只要使用数据文件中不同的列作为纵坐标即可。假设我要对比的是2020年和2021年,那么先分别统计两年的开支到不同的文件中

1
2
➜  Accounting ledger -b '2020-01-01' -e '2021-01-01' -f 2021.ledger csv 'Expense:Food' | csvsql -H --query 'SELECT strftime("%W", `a`) AS `week`, SUM(`f`) FROM `expense` GROUP BY `week` ORDER BY `a` ASC' --tables 'expense' | tail -n '+2' > /tmp/expense_2020.csv
➜ Accounting ledger -b '2021-01-01' -f 2021.ledger csv 'Expense:Food' | csvsql -H --query 'SELECT strftime("%W", `a`) AS `week`, SUM(`f`) FROM `expense` GROUP BY `week` ORDER BY `a` ASC' --tables 'expense' | tail -n '+2' > /tmp/expense_2021.csv

再将处于同一周的数据合并在一起

1
➜  Accounting csvjoin -H -c a /tmp/expense_2020.csv /tmp/expense_2021.csv | tail -n '+2' > /tmp/expense_2years.csv

最后,再让gnuplot一次性绘制两条折线

1
2
3
4
5
6
7
8
9
set terminal png font '/System/Library/Fonts/Hiragino Sans GB.ttc'
set title '吃的开销'
set output '/tmp/xyz2years.png'
set xlabel '第几周'
set xrange [0:54]
set ylabel '金额(¥)'
set yrange [0:1000]
set datafile separator comma
plot '/tmp/expense_2years.csv' using 1:2 with lines title "2020", '/tmp/expense_2years.csv' using 1:3 with lines title "2021"

结果如下

后记

其实仍然是非常不直观的,因为最终生成的是一张静态的图片,并不能做到将鼠标挪到曲线上时就给出所在位置的纵坐标的效果。

序言

作为一个天天都在用的工具,各位同行想必都非常熟悉 Git 的基本用法,例如:

  • git-blame找出某一行 bug 是哪一位同事引入的,由他背锅;
  • git-merge把别人的代码合进自己完美无瑕的分支中,然后发现单元测试无法跑通;
  • git-push -f把团队里其他人的提交通通覆盖掉。

除此之外,Git 其实还是一个带版本功能的键值数据库:

  • 所有提交的内容都存储在目录.git/objects/下;
  • 有存储文件内容的blob对象、存储文件元数据的tree对象,还有存储提交记录的commit对象等;
  • Git 提供了键值风格的读写命令git-cat-filegit-hash-object

读过我以前的文章《当我们git merge的时候到底在merge什么》的朋友们应该都知道,如果一次合并不是fast-forward的,那么会产生一个新的commit类型的对象,并且它有两个父级commit对象。以知名的 Go 语言 Web 框架gin的仓库为例,它的哈希值为e38955615a14e567811e390c87afe705df957f3a的提交是一次合并产生的,这个提交的内容中有两行parent

1
2
3
4
5
6
7
8
➜  gin git:(master) git cat-file -p 'e38955615a14e567811e390c87afe705df957f3a'
tree 93e5046e502847a6355ed26223a902b4de2de7c7
parent ad087650e9881c93a19fd8db75a86968aa998cac
parent ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c
author Javier Provecho Fernandez <javiertitan@gmail.com> 1499534953 +0200
committer Javier Provecho Fernandez <javiertitan@gmail.com> 1499535020 +0200

Merge pull request #520 from 178inaba/travis-import_path

通过一个提交的parent属性,所有的提交对象组成了一个有向无环图。但聪明的你应该发现了,git-log的输出结果是线性的,所以 Git 用到了某种图的遍历算法。

查阅man git-log,可以在Commit Ordering一节中看到

By default, the commits are shown in reverse chronological order.

聪明的你想必已经知道该如何实现这个图的遍历算法了。

自己动手写一个git-log

解析commit对象

要想以正确的顺序打印commit对象的信息,得先解析它。我们不需要从零开始自己打开文件、读取字节流,以及解压文件内容,只需要像上文那样调用git-cat-file即可。git-cat-file打印的内容中,有一些是需要提取备用的:

  • parent开头的行。这一行的哈希值要用于定位到有向无环图中的一个节点;
  • committer开头的行。这一行的 UNIX 时间戳将会作为决定谁是“下一个节点”的排序依据。

可以随手写一个 Python 中的类来解析一个commit对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class CommitObject:
"""一个Git中的commit类型的对象解析后的结果。"""
def __init__(self, *, commit_id: str) -> None:
self.commit_id = commit_id

file_content = self._cat_file(commit_id)
self.parents = self._parse_parents(file_content)
self.timestamp = self._parse_commit_timestamp(file_content)

def _cat_file(self, commit_id: str) -> str:
cmd = ['git', 'cat-file', '-p', commit_id]
return subprocess.check_output(cmd).decode('utf-8')

def _parse_commit_timestamp(self, file_content: str) -> int:
"""解析出提交的UNIX时间戳。"""
lines = file_content.split('\n')
for line in lines:
if line.startswith('committer '):
m = re.search('committer .+ <[^ ]+> ([0-9]+)', line.strip())
return int(m.group(1))

def _parse_parents(self, file_content: str) -> List[str]:
lines = file_content.split('\n')
parents: List[str] = []
for line in lines:
if line.startswith('parent '):
m = re.search('parent (.*)', line.strip())
parent_id = m.group(1)
parents.append(parent_id)
return parents

遍历commit组成的有向无环图——大根堆

恭喜你,你学过的数据结构可以派上用场了。

假设用上面的类CommitObject解析了gin中哈希值为e38955615a14e567811e390c87afe705df957f3a的提交,那么它的parents属性中会有两个字符串:

  • ad087650e9881c93a19fd8db75a86968aa998cac
  • ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c

其中:

  • 哈希值为ad087650e9881c93a19fd8db75a86968aa998cac的提交的时间为Sat Jul 8 12:31:44
  • 哈希值为ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c的提交时间为Jan 28 02:32:44

显然,按照反转的时间先后顺序(reverse chronological)打印日志的话,下一个打印的节点应当是是ad087650e9881c93a19fd8db75a86968aa998cac——用git-log命令可以确认这一点。

打印完ad087650e9881c93a19fd8db75a86968aa998cac之后,又要从它的父级提交和ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c中,挑选出下一个要打印的提交对象。显然,这是一个循环往复的过程:

  1. 从待打印的commit对象中,找出提交时间戳最大的一个;
  2. 打印它的消息;
  3. commit的所有父级提交加入到待打印的对象池中,回到第1个步骤;

这个过程一直持续到没有待打印的commit对象为止,而所有待打印的commit对象组成了一个优先级队列——可以用一个大根堆来实现。

然而,我并不打算在这短短的演示当中真的去实现一个堆数据结构——我用插入排序来代替它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MyGitLogPrinter():
def __init__(self, *, commit_id: str, n: int) -> None:
self.commits: List[CommitObject] = []
self.times = n

commit = CommitObject(commit_id=commit_id)
self._enqueue(commit)

def run(self):
i = 0
while len(self.commits) > 0 and i < self.times:
commit = self.commits.pop(0)

for parent_id in commit.parents:
parent = CommitObject(commit_id=parent_id)
self._enqueue(parent)

print('{} {}'.format(commit.commit_id, commit.timestamp))
i += 1

def _enqueue(self, commit: CommitObject):
for comm in self.commits:
if commit.commit_id == comm.commit_id:
return
# 插入排序,先找到一个待插入的下标,然后将从i到最后一个元素都往尾部移动,再将新节点插入下标i的位置。
i = 0
while i < len(self.commits):
if commit.timestamp > self.commits[i].timestamp:
break
i += 1
self.commits = self.commits[0:i] + [commit] + self.commits[i:]

最后再提供一个启动函数就可以体验一番了

1
2
3
4
5
6
7
8
9
@click.command()
@click.option('--commit-id', required=True)
@click.option('-n', default=20)
def cli(commit_id: str, n: int):
MyGitLogPrinter(commit_id=commit_id, n=n).run()


if __name__ == '__main__':
cli()

真假美猴王对比

为了看看上面的代码所打印出来的commit对象的顺序是否正确,我先将它的输出内容重定向到一个文件中

1
➜  gin git:(master) python3 ~/SourceCode/python/my_git_log/my_git_log.py --commit-id 'e38955615a14e567811e390c87afe705df957f3a' -n 20 > /tmp/my_git_log.txt

再用git-log以同样的格式打印出来

1
➜  gin git:(master) git log --pretty='format:%H %ct' 'e38955615a14e567811e390c87afe705df957f3a' -n 20 > /tmp/git_log.txt

最后让diff命令告诉我们这两个文件是否有差异

1
2
3
4
5
6
➜  gin git:(master) diff /tmp/git_log.txt /tmp/my_git_log.txt
20c20
< 2521d8246d9813d65700650b29e278a08823e3ae 1499266911
\ No newline at end of file
---
> 2521d8246d9813d65700650b29e278a08823e3ae 1499266911

可以说是一模一样了。

序言

众所周知,Python 支持向函数传递关键字参数。比如 Python 的内置函数max就接受名为key的关键字参数,以决定如何获取比较两个参数时的依据

1
max({'v': 1}, {'v': 3}, {'v': 2}, key=lambda o: o['v'])  # 返回值为{'v': 3}

自定义一个运用了关键字参数特性的函数当然也不在话下。例如模仿一下 Common Lisp 中的函数string-equal

1
2
3
4
5
6
7
8
9
10
def string_equal(string1, string2, *, start1=None, end1=None, start2=None, end2=None):
if not start1:
start1 = 0
if not end1:
end1 = len(string1) - 1
if not start2:
start2 = 0
if not end2:
end2 = len(string2) - 1
return string1[start1:end1 + 1] == string2[start2:end2 + 1]

再以关键字参数的形式向它传参

1
string_equal("Hello, world!", "ello", start1=1, end1=4)  # 返回值为True

秉承 Python 之禅中的There should be one-- and preferably only one --obvious way to do it.理念, 我甚至可以花里胡哨地、用关键字参数的语法向string1string2传参

1
string_equal(string1='Goodbye, world!', string2='ello')  # 返回值为False

但瑜不掩瑕,Python 的关键字参数也有其不足。

Python 的不足

Python 的关键字参数特性的缺点在于,同一个参数无法同时以:

  1. 具有自身的参数名,以及;
  2. 可以从**kwargs中取得,

两种形态存在于参数列表中。

举个例子,我们都知道 Python 有一个知名的第三方库叫做 requests,提供了用于开发爬虫牢底坐穿的发起 HTTP 请求的功能。它的类requests.Session的实例方法request有着让人忍不住运用 Long Parameter List 对其重构的、长达 16 个参数的参数列表。(你可以移步request方法的文档观摩)

为了便于使用,requests 的作者贴心地提供了requests.request,这样只需要一次简单的函数调用即可

1
requests.request('GET', 'http://example.com')

requests.request函数支持与requests.Session#request(请允许我借用 Ruby 对于实例方法的写法)相同的参数列表,这一切都是通过在参数列表中声明**kwargs变量,并在函数体中用相同的语法向后者传参来实现的。(你可以移步request 函数的源代码观摩)

这样的缺陷在于,requests.request函数的参数列表丢失了大量的信息。要想知道使用者能往kwargs中传入什么参数,必须:

  1. 先知道requests.request是如何往requests.Session#request中传参的——将kwargs完全展开传入是最简单的情况;
  2. 再查看requests.Session#request的参数列表中排除掉methodurl的部分剩下哪些参数。

如果想在requests.request的参数列表中使用参数自身的名字(例如paramsdatajson等),那么调用requests.Session#request则变得繁琐起来,不得不写成

1
2
with sessions.Session() as session:
return session.request(method=method, url=url, params=params, data=data, json=data, **kwargs)

的形式——果然人类的本质是复读机。

一个优雅的解决方案,可以参考隔壁的 Common Lisp。

Common Lisp 的优越性

Common Lisp 第一次面世是在1984年,比 Python 的1991年要足足早了7年。但据悉,Python 的关键字参数特性借鉴自 Modula-3,而不是万物起源的 Lisp。Common Lisp 中的关键字参数特性与 Python 有诸多不同。例如,根据 Python 官方手册中的说法,**kwargs中只有多出来的关键字参数

If the form “**identifier” is present, it is initialized to a new ordered mapping receiving any excess keyword arguments

而在 Common Lisp 中,与**kwargs对应的是&rest args,它必须放置在关键字参数之前(即左边),并且根据 CLHS 中《A specifier for a rest parameter》的说法,args中含有所有未经处理的参数——也包含了位于其后的关键字参数

1
2
3
4
(defun foobar (&rest args &key k1 k2)
(list args k1 k2))

(foobar :k1 1 :k2 3) ;; 返回值为((:K1 1 :K2 3) 1 3)

如果我还有另一个函数与foobar有着相似的参数列表,那么也可以轻松将所有参数传递给它

1
2
3
4
5
6
(defun foobaz (a &rest args &key k1 k2)
(declare (ignorable k1 k2))
(cons a
(apply #'foobar args)))

(foobaz 1 :k1 2 :k2 3) ;; 返回值为(1 (:K1 2 :K2 3) 2 3)

甚至于,即使在foobaz中支持的关键字参数比foobar要多,也能轻松地处理,因为 Common Lisp 支持向被调用的函数传入一个特殊的关键字参数:allow-other-keys即可

1
2
3
4
5
6
7
(defun foobaz (a &rest args &key k1 k2 my-key)
(declare (ignorable k1 k2))
(format t "my-key is ~S~%" my-key)
(cons a
(apply #'foobar :allow-other-keys t args)))

(foobaz 1 :k1 2 :k2 3 :my-key 4) ;; 打印my-key is 4,并返回(1 (:ALLOW-OTHER-KEYS T :K1 2 :K2 3 :MY-KEY 4) 2 3)

回到 HTTP 客户端的例子。在 Common Lisp 中我一般用drakma这个第三方库来发起 HTTP 请求,它导出了一个http-request函数,用法与requests.request差不多

1
(drakma:http-request "http://example.com" :method :get)

如果我想要基于它来封装一个便捷地发出 GET 请求的函数http-get的话,可以这样写

1
2
(defun http-get (uri &rest args)
(apply #'drakma:http-request uri :method :get args))

如果我希望在http-get的参数列表中直接暴露出一部分http-request支持的关键字参数的话,可以这样写

1
2
3
(defun http-get (uri &rest args &key content)
(declare (ignorable content))
(apply #'drakma:http-request uri :method :get args))

更进一步,如果我想在http-get中支持解析Content-Typeapplication/json的响应结果的话,还可以这样写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(ql:quickload 'jonathan)
(ql:quickload 'str)
(defun http-get (uri &rest args &key content (decode-json t))
;; http-request并不支持decode-json这个参数,但依然可以将整个args传给它。
(declare (ignorable content))
(multiple-value-bind (bytes code headers)
(apply #'drakma:http-request uri
:allow-other-keys t
:method :get
args)
(declare (ignorable code))
(let ((content-type (cdr (assoc :content-type headers)))
(text (flexi-streams:octets-to-string bytes)))
(if (and decode-json
(str:starts-with-p "application/json" content-type))
(jonathan:parse text)
text))))

不愧是Dio Common Lisp,轻易就做到了我们做不到的事情。

题外话

曾几何时,Python 程序员还会津津乐道于 Python 之禅中的There should be one-- and preferably only one --obvious way to do it.,但其实 Python 光是在定义一个函数的参数方面就有五花八门的写法了。甚至在写这篇文章的过程中,我才知道原来 Python 的参数列表中可以通过写上/来使其左侧的参数都成为 positional-only 的参数。

1
2
3
4
5
6
def foo1(a, b): pass
def foo2(a, /, b): pass


foo1(a=1, b=2)
foo2(a=1, b=2) # 会抛出异常,因为a只能按位置来传参。