sdedit使用方法介绍(混沌向)

最近在寻找绘制时序图的过程中遇到了sdedit,感觉非常适合自己使用,故写这么篇文章向自己也向有同样需求的其它开发人员介绍一些这款软件

sdedit在macOS上安装还是非常容易的,只需要使用homebrew就可以轻松安装,命令如下

brew install sdedit

之后sdedit就会被安装到/usr/local/bin 这个目录下,在命令中输入sdedit就可以启动了。

输入sdedit后会启动一个Java Swing写的GUI程序,具体的外观和布局就不介绍了,这里主要讲解一下sdedit所支持的语法

sdedit中绘图的常用语法

PS:我对UML中的一些术语并不了解,下面的介绍是可能有错误的,具体请以sdedit的官方文档(http://sdedit.sourceforge.net/enter_text/)为准。同时,既然有官方文档了,我就不在此翻译一遍了,只记录一些常用的用法

如果需要输入整个时序图的标题(姑且叫做标题),那么可以使用下面的语法

#![一键获取手机号并登录的交互流程]

即以UNIX中的shebang开头,后面通过一对方括号包住标题内容即可

如果需要绘制一个参与时序图的节点,那么使用下面的语法(摘抄自官方文档)

<name>:<Type>[<flags>] "<label>"

其中,就是节点的唯一名字,之后当描述节点间的交互时需要这个字段,请给每一个节点都取一个独一无二的名字(就像取变量名那样);部分顾名思义就是类型,虽然我在使用的时候这个字段的值也是随心所欲地写的,但这个字段对sdedit而言似乎有特殊含义——例如,如果这个字段填入的是Actor,那么绘制出来的就会是一个人形的节点,在用来表示用户的时候特别有用;(flags我还没有用过就不介绍了);label可以理解为节点的文案,如果不填

定义好节点之后,就需要把各个节点在不同的时间用不同的消息联系起来了。描述节点间联系用的语法是(摘自官网)

<caller>[<s>]:<answer>=<callee>[m].<message>

其中的caller和callee都是写的节点的(所以name需要时独一无二的),这样就会绘制出两条线——一条实线从caller指向callee,以及一条虚线从callee指向caller,以及在callee的生命周期下绘制出一个纵向的矩形,表示callee的处理过程;是从caller发往callee的消息,例如参数的描述;如果需要同时描述从callee返回的结果,那么就需要填写在上述语法的的的位置——个人觉得这个语法是有点奇怪的

生成图片

上面的这些文本描述都需要输入到sdedit的文本框中(唯一UI上的右下角),之后点击保存就可以得到一个XXX.sdx的文件了。由于在我的电脑上,sdedit的GUI上的导出功能用起来非常有问题,所以我摸索出来的是在命令行导出图片文件的做法(并且可以导出的格式似乎更丰富)。总体的用法是

sdedit -t <类型> -o <输出文件名> <原始的.sdx文件>

输出文件名随性地取即可,其中类型对常用的都有支持(svg、png、jpg,和bmp),我一般常用的是png,然后就可以得到一张PNG图片了(便可以美美地用到设计文档里了)

配图什么的等我哪天特别闲了再补充上来吧

MacBook Pro使用体验

生平第一次有一台自己的MacBook,使用了一段时间之后也有了自己的一番感想,特此写下来留个纪念。感想主要分为硬件以及软件两个方面,本文不会有太多的条理性

硬件

上周四晚上第一次从收件的超市老板手里接过MacBook Pro的时候,第一感觉是意想不到的沉重。回到家拆开包装,拿起机体和电源适配器的时候,也是觉得非常的重。虽然经过几天的使用后发现并没有当初那般沉重的感觉了,但总体还是超过了我的预期。

接着是发现这台电脑居然没有开机键。老实说,其实这个是我在昨天才意识到的;同时,这台电脑只有四个Type-C的接口,不得不下单买了个外接的适配器。

触控板的面积很大,但正如传闻中所说的,触控板非常地好用,不像我之前用的电脑触控板是塑料材质的,当手出汗的时候非常地难用。

比较可惜的是,control键只在键盘的左侧有,对于使用Emacs来编码的人(指我自己)来说,是比较不方便的。虽然现在已经分别将左右的option设置成了(Windows上的)control,以及将command设置成了(Windows上的)Alt,但无名指在按键的时候还是难免误触。同时,没有独立的home/end/up/down,刚开始还真有点不习惯

touchbar毕竟是一块没有力反馈的触摸屏,所以每当需要按ESC的时候都忍不住要肉眼确认一下或者按两下。但用touchbar来控制音量则非常方便

散热有点糟糕。第一天晚上折腾的时候,安装完Visual Studio Code然后VSC自己卡死了,随后机器开始发热,尤其是touchbar上方靠近屏幕铰链的位置很烫——可千万不要轻易烧坏了呀

电池很给力,不需要每天下班都带着重重的电源适配器回家

软件

开机后的第一感觉就是界面新颖,虽然并不是第一次亲眼看见macOS了,但作为自己的机器来使用,认真一看确实觉得比Windows要美观,比起之前在虚拟机中使用的Mint也要更优雅统一。触控板非常地好用,尤其是三指上划用于在窗口间切换的功能非常地棒,两指点击表示右键单击的效果也非常地好,既轻盈又方便。字体很好看,就连在Emacs中展示的中文也变得可爱起来

摆脱了虚拟机,也就不用再把内存用在一起重复的功能上了(比如把内存分给虚拟机的操作系统),搭配上SSD现在开启软件都非常地快。不过大概是因为虚拟机用惯了,有时候总忍不住切换到调度中心,然后找一个看起来比较像虚拟机的应用来点一下,2333

以前在Mint里面用的搜狗输入法总觉得有什么欠缺,现在可以用上全功能的版本了感觉很爽快,连在Emacs中输入中文也变得畅快起来。更令人惊喜的是,不知道如何折腾,现在我居然可以在多个软件里用上Emacs的键绑定了,目前发现的包括但不限于Firefox的输入框、微信、QQ,以及有道云笔记。

Mac上的一些软件很有趣,比如Alfred、Timing等等,同时也是我第一次使用zsh+oh-my-zsh,的确是很强大的工具。这两天我也开始编写自己的Workflow了,打算接着学习一下Apple Script更好地帮助自己使用这个系统。

好了,就酱

cl-mongo用法入门

最近用Common Lisp开发一个个人项目,需要记录发出的HTTP请求的参数,包括了目标地址、HTTP body,以及HTTP头部等多种信息。为了可以结构化地存储这些数据(比如HTTP头部是由多个键值对组成的),我选择将它们保存到MongoDB中。Google一番后,我找到了cl-mongo这个库,可以在Common Lisp中读写MongoDB,尝试了一下也确实可以满足自己的需求。为了方便自己查阅,也为了方便有相同需求的人了解如何使用cl-mongo,于是写了这篇文章。

首先使用CL-MONGO:MONGO函数连接MongoDB的服务器程序(mongod)。因为在我的系统上mongod进程监听的是27017这个端口,并且我希望使用的数据库名为test,因此键入如下代码来连接数据库

1
2
3
(cl-mongo:mongo :db "test"
:host "127.0.0.1"
:port 27017)

连接上了数据库后,首先尝试往其中写入一个文档。假设现在要记录的是发出的HTTP请求的信息,那么一个可以写入的基本信息就是请求的目标地址。假设在命令行的mongo shell中输入的内容如下

1
db.http_request.insert({uri: 'http://example.com'});

那么使用cl-mongo提供的DB.INSERT函数达到上述效果的代码如下

1
2
(cl-mongo:db.insert "http_request"
(cl-mongo:kv "uri" "http://example.com"))

求值上述代码后返回值为NIL。为了将上述写入的文档重新查询出来,需要使用cl-mongo提供的DB.FIND函数。因为只有一个文档,所以直接查询就可以查看到结果了。在mongo shell中我们可以使用如下代码查询

1
db.http_request.find();

使用DB.FIND函数的话编写的代码可能会长得像下面这样

1
(cl-mongo:db.find "http_request" :all)

在我的系统上求值了上述代码后在REPL中输出的内容如下

1
2
3
4
5
6
((86 449 0 1 8 0 0 1 "http_request")
(<CL-MONGO:DOCUMENT> : {
_id : CL-MONGO::BSON-OID [#(89 52 26 160 109 156 254 71 184 115 102 30)]
elements : 1}

))

值得注意的是,DB.FIND的返回值不完全是文档组成的数组,而是在这个结果集的数组之外又多了一层列表,并且列表的第一个元素还是一个一看之下不知其所以然的子列表。由于cl-mongo的GitHub上没有提及这个玩意儿的来历,我也没有深入去了解DB.FIND函数的实现代码,因此这个元素就先忽略它吧。如果需要使用DB.FIND查询到的结果,那么开发者需要对DB.FIND的返回值应用一下函数SECOND才行,如下

1
(second (cl-mongo:db.find "http_request" :all))

返回值的列表中的每一个元素都是CL-MONGO:DOCUMENT这个类的实例对象,如果要直接使用还是稍微有点不方便的,因此我写了一个函数用来将DB.FIND函数查询到的CL-MONGO:DOCUMENT的实例对象都转换为较为熟悉,容易操作的数据类型——association list,函数的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun document-to-alist (doc)
"Convert a DOC of type CL-MONGO:DOCUMENT to a equivalent, serializable alist."
(check-type doc cl-mongo:document)
(labels ((aux (doc)
(cond ((typep doc 'cl-mongo:document)
(let ((keys (cl-mongo:get-keys doc)))
(mapcar #'(lambda (key)
(cons key
(aux (cl-mongo:get-element key doc))))
keys)))
(t doc))))
(let ((id (cl-mongo:doc-id doc)))
(append (aux doc) (list (cons "_id" id))))))

使用如下代码即可查看方才所写入的文档究竟长什么样子了

1
(document-to-alist (first (second (cl-mongo:db.find "http_request" :all))))

如果想要修改数据库中的文档,例如增加一个字段,那么可以使用cl-mongo提供的DB.UPDATE函数,用法如下

1
2
3
4
(cl-mongo:db.update "http_request"
(cl-mongo:kv "uri" "http://example.com")
(cl-mongo:kv "$set"
(cl-mongo:kv "method" "GET")))

最后如果要删除刚才所写入的这个文档,可以使用cl-mongo的DB.DELETE函数(我很好奇这个函数居然不是叫做DB.REMOVE),用法如下

1
2
(cl-mongo:db.delete "http_request"
(cl-mongo:kv "uri" "http://example.com"))

远程请求Squid

不久前在办公室抓取某网站S被对方发现,导致对方自动屏蔽了来自办公室网络的所有HTTP请求,连正儿八经地用浏览器打开也不行。为了可以摸索出“改头换面”(改HTTP头部)访问的方法,必须先成功访问至少一次,看看发出的HTTP头部是怎样的才行。恰好想起自己有一台腾讯云服务器,登上去用curl访问网站S,发现是成功的(也就是尚未被屏蔽)。既然如此,干脆在服务器上部署一套Squid作为正向代理,帮助办公网络的请求成功抵达网站S并拿到响应页面。

apt-get安装了squid软件包后启动并监听端口8321,在办公网络下将公网地址和8321端口作为代理配置传递给curl-x选项,访问网站S。不料Squid拒绝了我的请求,返回了如下内容(节选自curl -v命令的输出)

1
2
3
4
5
6
7
8
9
10
11
12
13
< HTTP/1.1 403 Forbidden
< Server: squid/3.5.12
< Mime-Version: 1.0
< Date: Wed, 17 May 2017 15:18:08 GMT
< Content-Type: text/html;charset=utf-8
< Content-Length: 3531
< X-Squid-Error: ERR_ACCESS_DENIED 0
< Vary: Accept-Language
< Content-Language: en
< X-Cache: MISS from VM-44-136-ubuntu
< X-Cache-Lookup: NONE from VM-44-136-ubuntu:8321
< Via: 1.1 VM-44-136-ubuntu (squid/3.5.12)
< Connection: keep-alive

经过一番Google,才知道原来是Squid的配置导致的。在Squid配置文件(/etc/squid/squid.conf)中,默认的acl和http_access指令的设置如下

1
2
3
4
5
6
7
8
9
10
11
12
acl SSL_ports port 443
acl Safe_ports port 80 # http
acl Safe_ports port 21 # ftp
acl Safe_ports port 443 # https
acl Safe_ports port 70 # gopher
acl Safe_ports port 210 # wais
acl Safe_ports port 1025-65535 # unregistered ports
acl Safe_ports port 280 # http-mgmt
acl Safe_ports port 488 # gss-http
acl Safe_ports port 591 # filemaker
acl Safe_ports port 777 # multiling http
acl CONNECT method CONNECT
1
2
3
4
5
6
http_access deny !Safe_ports
http_access deny CONNECT !SSL_ports
http_access allow localhost manager
http_access deny manager
http_access allow localhost
http_access deny all

由于Squid是按照第一条匹配的http_access指令来决定允许还是拒绝的,因为来自我办公网络的请求实际上命中的是

1
http_access deny all

因此被拒绝是必然的。为了可以接受来自办公网络发起的请求,首先需要新增一行acl指令。通过Squid的日志(/var/log/squid/access.log)可以查看到被拒绝的请求的IP地址是多少,此处假设IP地址为8.7.198.45,那么相应的acl指令如下

1
acl myclients src 8.7.198.45

此处的myclients为自定义的名称,顾名思义,它表示“我的客户端”;src是一种acl类型,表示客户端的IP地址;8.7.198.45是src类型下的参数,也就是我所使用的客户端发出的请求的来源IP地址。配置了acl后,还需要配置http_access指令。这个就简单多了,只要允许上面创建的这个acl的访问即可,内容如下

1
http_access allow myclients

之后再重启Squid服务即可

1
sudo service squid restart

这时候再从办公网络中以腾讯云服务器上的Squid为正向代理发出请求,就不会再被Squid拒绝了。

全文完

如何使用CL实现snowflake

TL;DR;

这是一篇为了完成写作KPI而写的博客,总结起来就是提供了一种用Common Lisp实现来自于Twitter的雪花算法的实现方案。成品在这里,本文只是简单地描述一下生成雪花ID的大致思路,详细内容请各位移步代码仓库查看。

上述代码仓库中的snowflake算法——如果我的实现确实可以称作snowflake算法的话——的思路来自于下列两个地方:

  1. http://www.lanindex.com/twitter-snowflake,64位自增id算法详解/
  2. https://github.com/sony/sonyflake

如何获取时间戳

Common Lisp本身提供了一个获取时间戳的函数,也就是get-universal-time,可惜的是,这个函数所返回的并不是通常意义上的Epoch时间戳,而是自己的一套计算时间的方式中的表示时间的整数。为了获得UNIX时间戳,需要借助于第三方库local-time。为了可以获取到毫秒精度的时间戳,一个可运行的函数如下

1
2
3
4
5
6
(defun now ()
"Returns the number of milliseconds elapsed since 1 January 1970 00:00:00 UTC."
(let* ((now (local-time:now))
(seconds (local-time:timestamp-to-unix now))
(milliseconds (local-time:timestamp-millisecond now)))
(+ (* 1000 seconds) milliseconds)))

如何获取机器ID

这里参考了Sony的雪花ID算法中的思路,基于机器的内网IP地址来生成机器ID。当然了,Common Lisp标准中是没有提供获取机器的内网IP地址的方法的,这一点也可以借助于第三方库实现,选用的是ip-interfaces。通过这个库提供的get-ip-interfaces函数可以获取到机器的所有“接口”,遍历这个接口的列表后即可找出其中的内网IP。一台机器可能会有多个内网IP,我的方法是选用了第一个找到的内网IP地址。当然了,还需要一个将向量转化为数值的函数,并取出转化为数值后的IP地址的低10位,作为机器ID。

序号

如果希望生成的ID是保持递增的,那么就需要维护一个可以原子递增的数值计数器。在真实的使用中可以通过Redis的INCR指令来生成这一个ID,但是因为这里的雪花ID算法是作为一个独立的库实现的,不需要依赖于数据库等外部组建,因此这里就直接使用了Common Lisp自带的random函数来生成这个序号了。

全文完

如何检查一组区间中是否存在两个区间有交集

假设有N个区间,将它们表达为,其中下标i位于区间

为了判定这组区间中是否存在两个区间是有重叠的,首先对这组区间进行排序,使得对于排序后的每一个区间而言,都有(这里的i小于N-1)。

为了说明要如何判定这些区间中是否存在重叠,首先我们假设这其中确实存在着至少两个这样的区间,假设分别是第j个和第k个(假设j小于k),它们必然会满足这样的关系

这是因为如果,那么所有位于区间中的数都将会小于 b_k,那么第j个区间与第k个区间就不可能有交集了,因此上述不等式一定成立。再加上这一组区间都是按照区间的下界递增排序的,那么必然有

假设,由于k和j都是正整数,这意味着在第j和第k个区间之间,必然还存在着一个区间l,那么这个区间的必然满足

这就意味着第j个区间和第l个区间也存在交集,它们的交集是子区间(这里假设)。这就说明了,如果可以在一组区间中找到两个不相邻的区间,它们存在重叠的部分,那么一定可以找到第三个区间,使得这个区间与其中的一个区间也存在重叠。

这表示如果我们要判定一组区间是否存在重叠,那么只需要先将它们基于区间的起点按照递增排序后,比较每一对相邻的两个区间是否存在重叠即可。

如何安装及使用Elastic Search

最近产品需要一个搜索商城中的商品的功能,于是接触了一下Elastic Search。虽然久仰它的大名,但一直都没有真正用过。这次稍微摸索了一下,顺便记录下来,说不定哪天就真的需要用上了。

安装

首先需要下载Elastic Search,我选择了.zip格式的安装包,下载地址在这里。下载完成后就拿到了一个5.2.2版本的Elastic Search的安装包,只需要解压即可使用。因为我喜欢把软件安装到主目录的app目录下,所以我用的命令是

1
2
cd /home/liutos/app
unzip ../installer/elasticsearch-5.2.2.zip

主目录下的installer是我习惯的用来存放软件的安装包的位置。解压后生成了一个名为elasticsearch-5.2.2的新目录。在这个目录下有一个名为bin的子目录,只需要进入该目录运行其中的elasticsearch文件即可,实例命令为

1
2
cd elasticsearch-5.2.2/bin
./elasticsearch -d

为了让Elastic Search可以不占用当前的终端,添加了-d选项,使其以后台进程(daemon)的方式运行。Elastic Search需要JVM才能运行,在执行上面的命令之前请各位自行准备好Java程序的运行环境。成功启动后,Elastic Search默认会监听9200端口,可以通过浏览器访问http://localhost:9200来确认Elastic Search是否正常启动了

使用

创建索引

遵照官方文档中的指导,先创建一个索引以便后续向这个索引中添加文档。假设要创建的索引是为商品准备的,取名为products,可以通过如下的命令创建出来

1
curl -X PUT 'http://localhost:9200/products'

创建成功后Elastic Search的响应结果为

1
{"acknowledged":true,"shards_acknowledged":true}

如果希望Elastic Search返回更可读的形式,可以添加?pretty参数到上面的URL的末尾。

文档的增删查改

索引已经创建了,就可以创建文档了。Elastic Search的文档是对象形式的,假设现在要创建的对象的类型为product,示例命令如下

1
2
3
4
5
curl -X POST 'http://localhost:9200/products/product' --data '
{
"id": 1,
"name": "Product 1"
}'

在我的机器上,Elastic Search的响应结果为

1
{"_index":"products","_type":"product","_id":"AVqpZHmVckriR6iVcbaW","_version":1,"result":"created","_shards":{"total":2,"successful":1,"failed":0},"created":true}

其中名为”_id”的字段的值为Elastic Search自动为这份新写入的文档分配的ID,通过这个ID可以从Elastic Search中取出这份文档,示例命令如下

1
curl 'http://localhost:9200/products/product/AVqpZHmVckriR6iVcbaW?pretty'

相当的RESTful的接口路径,也许你已经猜到了,删除一个文档的代码就是将请求的GET方法替换为DELETE。是的,示例代码如下

1
curl -X DELETE 'http://localhost:9200/products/product/AVqpZHmVckriR6iVcbaW?pretty'

再次查找刚才的ID的文档时,响应结果中的”_found”字段的值就已经变成了false了。关于修改文档的方法,请参考官方手册中的章节

搜索

准备数据

最简单的搜索接口的使用就是通过浏览器访问http://localhost:9200/products/_search这个地址了。在我的机器上,看到的页面内容为如下的JSON字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{

"took": 42,
"timed_out": false,
"_shards": {
"total": 5,
"successful": 5,
"failed": 0
},
"hits": {
"total": 0,
"max_score": null,
"hits": [ ]
}

}

为了方便接下来的演示,先通过Elastic Search的_bulk接口向其批量创建文档数据,示例代码如下

1
curl -X POST 'http://localhost:9200/_bulk?pretty' --data-binary '@docs'

其中docs文件中的内容为

1
2
3
4
5
6
7
8
{"create": {"_index": "products", "_type": "product", "_id": 1}}
{"name": "设计模式之禅"}
{"create": {"_index": "products", "_type": "product", "_id": 2}}
{"name": "失控:全人类的最终命运和结局"}
{"create": {"_index": "products", "_type": "product", "_id": 3}}
{"name": "构建高性能Web站点", "price": 75.00, "author": "郭欣"}
{"create": {"_index": "products", "_type": "product", "_id": 4}}
{"name": "大型网站技术架构:核心原理与案例分析", "price": 59.00, "author": "李智慧", "publisher": "电子工业出版社"}

尽管这里是一个文本文件,但是根据官方文档的说法,此处需要使用curl的二进制模式来发送数据,否则会报错。

个性化搜索

如果希望找到《失控》这本书的信息,那么可以根据书名进行查找,示例代码如下

1
curl 'http://localhost:9200/products/_search?q=name:失控'

Elastic Search提供了许多的搜索选项,如果全部通过URL中的query string来传递将会非常难以构造。为此,可以使用Elastic Search提供的基于HTTP body的参数传递方式,示例代码如下

1
curl -X GET 'http://localhost:9200/products/_search' --data '{"query": {"match": {"name": "失控"}}}'

Elastic Search支持相当丰富的搜索选项,这里不逐一介绍了,大家可以从官方文档的这里开始翻看。本来想在Chrome的POSTMAN插件中试验搜索功能的,结果当我选定了GET方法后,就不需要我提交HTTP body了,因此还是用curl进行演示。回到正题,如果我们搜索的是一个“站”字,那么Elastic Search会吐出两个结果,此处可以使用搜索接口的fromsize参数,分别控制返回的内容取自搜索结果中的哪一个片段。例如想要取出结果中的第二个,可以使用下列代码

1
curl -X GET 'http://localhost:9200/products/_search?pretty' --data '{"from": 1, "size": 1, "query": {"match": {"name": "站"}}}'

通过结合使用fromsize参数,可以实现许多应用中所要求的分页功能。在我厂的业务场景中,商品信息还是很多的,不可能全部放入到Elastic Search中作为文档数据存储,Elastic Search只是负责提供搜索出来的商品ID即可,之后再通过商品ID从原来的商品的数据库中按照顺序取出对应的完整的商品信息。因此,在搜索Elastic Search时实际上只需要商品的ID就足够了,可以通过Elastic Search提供的_source字段控制接口吐出的内容,示例代码如下

1
curl -X GET 'http://localhost:9200/products/_search?pretty' --data '{"query": {"match_all": {}}, "_source": ["_id"]}'

这样在吐出的内容中_source字段的值就会是一个空对象,应用程序只需要取每一个hits数组中的记录的”_id”字段即可。这样做的目的是减少Elastic Search通过网络传输了一部分毫无必要的数据,略微优化一下网络开销

全文完

如何用Common Lisp实现尾递归优化

什么是尾递归

如果一个函数在定义时引用了自身,那么这个函数就是一个递归函数。例如我们所熟知的阶乘就可以通过递归函数的形式予以定义

1
2
3
4
(defun fact (n)
(if (<= n 0)
1
(* n (fact (1- n)))))

在if语句的备选路径上,正在定义的函数fact被自身所调用,因此fact就是一个递归函数了。递归有一类较为特殊的形式,叫做尾递归,它们的特征是递归函数的调用位于被定义函数的最后一个步骤。也就是说,这个递归调用的返回值也就是整个函数调用的返回值,后面不再有其它的计算步骤了。例如实现了辗转相除法的下面这个函数就是尾递归的

1
2
3
4
(defun my-gcd (a b)
(cond ((zerop a) b)
((zerop b) a)
(t (my-gcd b (mod a b)))))

此处命名为my-gcd,是因为在Common Lisp中已经预置了一个叫做gcd的函数了

什么是尾递归优化

递归调用其实也就是函数调用,每一次调用都需要保存当前的执行上下文(寄存器的值、程序计数器的值等信息)并压入栈中。如果递归调用得非常深,那么很可能将栈空间消耗殆尽导致程序崩溃,因此很多时候都会选择使用循环来实现用递归实现的效果。尾递归形式的一个优势,就在于编译器可以对其进行优化,使得原本需要添加一个栈帧的函数调用操作,直接重用当前的调用中所使用的栈帧即可。这样一来,递归函数的调用就不会无节制地消耗栈空间了。

另一种对尾递归进行优化的方式,则是将其改写为【赋值】与【跳转】。例如对于上面的my-gcd函数,可以改写为如下形式

1
2
3
4
5
6
7
8
9
(defun my-gcd (a b)
(tagbody
rec
(cond ((zerop a) (return-from my-gcd b))
((zerop b) (return-from my-gcd a))
(t (progn
(psetf a b
b (mod a b))
(go rec))))))

如何在Common Lisp中实现

如果要使用递归的形式定义一个计算列表长度的函数,那么很可能会写出这样子的代码

1
2
3
4
(defun my-length (lst)
(if (null lst)
0
(1+ (my-length (rest lst)))))

采用累加器的思路,可以将上述函数改写为下面的尾递归形式

1
2
3
4
(defun my-length (lst acc)
(if (null lst)
acc
(my-length (rest lst) (1+ acc))))

对于第二个版本的my-length函数,同样可以手动改写为基于【赋值】和【跳转】的实现形式,结果如下

1
2
3
4
5
6
7
8
9
(defun my-length (lst acc)
(tagbody
rec
(if (null lst)
(return-from my-length acc)
(progn
(psetf lst (rest lst)
acc (1+ acc))
(go rec)))))

你可能已经注意到了,my-gcdmy-length函数的改写都是很有规律的,甚至可以通过一个宏来帮助我们自动完成这种变换。这个宏所需要做的事情其实只有三件:

  1. 将原本的定义中的函数体包裹在一个tagbody
  2. 将原本作为返回值的表达式包裹在一个return-from
  3. 将递归调用的表达式改为按顺序执行的psetfgo的组合

为了降低一下实现难度,第二点暂时就不处理了,函数的实现者必须手动编写return-from语句。因此,如果只考虑首尾两个条件,首先,可以考虑实现第三条,将函数体内的递归调用修改为prognpsetfgo的组合。要实现这个变换,可以使用macrolet,如下

1
2
3
4
5
6
7
8
9
10
(defun my-length (lst acc)
(tagbody
rec
(macrolet ((my-length (&rest args)
`(progn
(psetf ,@(mapcan #'list '(lst acc) args))
(go rec))))
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))))

为了自动生成上面的代码,我编写了这样的一个宏

1
2
3
4
5
6
7
8
9
10
(defmacro define-rec (name lambda-list &body body)
(let ((rec (gensym)))
`(defun ,name ,lambda-list
(tagbody
,rec
(macrolet ((,name (&rest exprs)
,``(progn
(psetf ,@(mapcan #'list ',lambda-list exprs))
(go ,',rec))))
,@body)))))

利用上面这个宏编写一个计算列表长度的尾递归形式的函数,代码如下

1
2
3
4
(define-rec my-length (lst acc)
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))

利用macroexpand-1或者是SLIME提供的展开一次宏的调试功能,在我的及其上得到的代码如下

1
2
3
4
5
6
7
8
9
10
(DEFUN MY-LENGTH (LST ACC)
(TAGBODY
#:G937
(MACROLET ((MY-LENGTH (&REST EXPRS)
`(PROGN
(PSETF ,@(MAPCAN #'LIST '(LST ACC) EXPRS))
(GO ,'#:G937))))
(IF (NULL LST)
(RETURN-FROM MY-LENGTH ACC)
(MY-LENGTH (REST LST) (1+ ACC))))))

跟上面手写的代码没有太大的差别,并且用于计算所得到的列表长度也是正确的。那么如何验证这个函数是采用了【赋值】和【跳转】的机制来完成运算的呢?可以借助Common Lisp提供的trace函数。如果使用的真实执行递归调用的my-length函数的定义,那么执行(trace my-length)后运行(my-length '(1 2 4 5) 0),在我的机器上会输出如下内容

1
2
3
4
5
6
7
8
9
10
11
12
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
1: (MY-LENGTH (2 4 5) 1)
2: (MY-LENGTH (4 5) 2)
3: (MY-LENGTH (5) 3)
4: (MY-LENGTH NIL 4)
4: MY-LENGTH returned 4
3: MY-LENGTH returned 4
2: MY-LENGTH returned 4
1: MY-LENGTH returned 4
0: MY-LENGTH returned 4
4

而如果是使用define-rec宏定义的my-length,求值同样的表达式的输出为

1
2
3
4
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
0: MY-LENGTH returned 4
4

显然,这当中没有递归的函数调用,my-length确实不需要调用自身。

全文完

如何自定义命令行补全

在UC就职时养成了一个习惯,就是将自己所参与的项目的源代码都存放在一个名为uc的目录下。换了工作之后这个习惯仍然保留下来了,只不过原本名为uc的目录现在改名了(假设这个目录叫做work)。在新公司参与的项目比较多,因此在这个work目录下有许多的子目录,大致上的结构如下

1
2
3
work/
|-- A/
|-- B/

其中A和B分别表示一个项目的源代码目录。在work目录下存放的直接是A和B两个项目的目录。work目录本身是放置在~/src/这个目录下的,因此项目A和B的完整根目录路径是~/src/work/A/~/src/work/B/。由于参与的项目比较多,经常需要在几个项目间交替着编码,因此经常会在终端键入下面的指令

1
2
cd ~/src/work/A/ # 或者
cd ~/src/work/B/

不得不说这样确实是非常的麻烦,因此我很快就定义了一个shell函数来简化这串命令,这个shell函数的定义如下

1
2
3
4
5
6
7
8
function she() {
dir=${1}
target="/home/liutos/src/work/${dir}"
if [ -d "${target}" ]; then
cd "${target}"
return
fi
}

有了这个辅助工具后,要切换到项目A和B中就简单多了,只需要输入

1
2
she A # 或者
she B

即可。但一使用起来就会发现,原本直接使用cd命令时所能享用的目录名补全功能没有了!绝大多数情况下补全功能是非常有用的,为此打算动手为she函数配备一个目录名的补全功能。显然自定义命令行补全的想法已经有前人实践过了,略加搜索就可以找到这么一篇指南。模仿文章中的方法,我先是写了下面的代码骨架

1
2
3
4
5
_she() {
local cur
_get_comp_words_by_ref cur
}
complete -F _she she

我的想法是只要当前的输入能够作为work下的一个目录名字的前缀,那么就认为这个子目录是本次补全的目标。为此,我需要先获取到work目录下的所有子目录的名称。利用ls命令可以做到这一点,同时为了便于处理,在这里将ls返回的文件名列表作为数组保存起来。修改后的_she函数的代码如下

1
2
3
4
5
6
_she() {
local cur
local dirs
_get_comp_words_by_ref cur
dirs=($(ls ~/src/work/))
}

现在,只要遍历${dirs}并找出第一个以用户输入的${cur}为名字前缀的目录即可。最终_she函数的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_she() {
local cur
local dirs
_get_comp_words_by_ref cur
dirs=($(ls ~/src/work/))
for dir in ${dirs[@]}
do
case ${dir} in
${cur}*)
COMPREPLY="${dir}"
return 0
;;
esac
done
}

Common Lisp的restart特性

主流的编程语言中,表示出现错误的手段不外乎两种:

  • 函数调用返回错误码
  • 函数调用抛出异常

C语言就属于前者,它的fopen(3)函数在成功打开文件时返回一个FILE指针,失败时返回NULL,并将错误代码写入全局变量errno;Ruby语言属于后者,它的File.open方法在找不到文件时抛出ENOENT的异常,在File.open之外包裹一层begin…rescue…end即可捕捉其抛出的异常。

Common Lisp的错误机制叫做状况系统(Condition System),与异常机制相似,可以实现抛出异常(使用函数error)和捕捉异常(使用宏handler-case)。但与其它语言的异常机制不同的地方在于,状况系统有一种名为RESTART的特性,能够由使用者、或者由代码决定是否要、以及如何从错误中恢复过来。听起来很别致也很诡异,不妨继续往下看。

假设我有一个Web框架,它提供了将日志记录到文件中的功能。这个功能需要先调用名为init-logger的函数进行初始化,该函数实现如下

1
2
3
4
5
(defun init-logger ()
(with-open-file (s "/tmp/log/web.log"
:direction :output
:if-exists :supersede)
(format s "Logger module starting...")))

这个函数被框架的初始化代码所调用,如下

1
2
3
4
5
6
7
(defun init-framework ()
(format t "Framework starting...~%")
(init-plugin))

(defun init-plugin ()
(format t "Plugins starting...~%")
(init-logger))

而框架的初始化代码则由应用的初始化代码所调用,如下

1
2
3
(defun init-app ()
(format t "Application starting...~%")
(init-framework))

如果在目录/tmp/log不存在时调用init-app函数,我将会收到一个错误,说明其无法找到/tmp/log/web.log这个文件。为了避免错误打断了应用的正常启动流程,可以让init-app函数负责创建这个用于存放日志文件的目录。将init-app函数改写为如下形式

1
2
3
4
(defun init-app ()
(format t "Application starting...~%")
(ensure-directories-exist "/tmp/log/")
(init-framework))

尽管这种做法确实可行,但它导致应用层的代码(init-app函数)必须了解位于底层的日志模块的实现细节。直觉告诉我这样子是不对的,框架的事情应该由框架本身提供方案来解决。借助Common Lisp的restart功能,框架确实可以对外提供一种解决方案。

首先需要主动检测用于存放日志文件的目录是否存在。借助UIOP这个包可以写出如下代码

1
2
3
4
5
6
7
8
(defun init-logger ()
(let ((dir "/tmp/log/"))
(unless (uiop:directory-exists-p dir)
(error 'file-error :pathname dir))
(with-open-file (s (format nil "~Aweb.log" dir)
:direction :output
:if-exists :supersede)
(format s "Logger module starting..."))))

接着,init-logger需要主动为调用者提供目录不存在的问题的解决方案,一种办法就是当这个目录不存在时,可以由调用者选择是否创建。使用Common Lisp的restart-case宏,我将init-logger改写为如下形式

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun init-logger ()
(let ((dir "/tmp/log/"))
(restart-case
(unless (uiop:directory-exists-p dir)
(error 'file-error :pathname dir))
(create-log-directory ()
:report (lambda (stream)
(format stream "Create the directory ~A" dir))
(ensure-directories-exist dir)))
(with-open-file (s (format nil "~Aweb.log" dir)
:direction :output
:if-exists :supersede)
(format s "Logger module starting..."))))

此时如果调用第一版的init-app函数,那么init-logger仍将抛出异常(类型为file-error与之前一样)并将我带入到SBCL(我用的是SBCL)的调试器中,但看到的内容会稍有不同

1
2
3
4
5
6
7
8
error on file "/tmp/log"
[Condition of type FILE-ERROR]

Restarts:
0: [CREATE-LOG-DIRECTORY] Create the directory /tmp/log ;; <- 新增了这一行
1: [RETRY] Retry SLIME REPL evaluation request.
2: [*ABORT] Return to SLIME's top level.
3: [ABORT] abort thread (#<THREAD "new-repl-thread" RUNNING {1001F958A3}>)

在Restarts中新增了名为create-log-directory的一项,这正是在init-logger中通过restart-case定义的新的”恢复措施“。我输入0触发这个restart,Common Lisp会回到它被定义的restart-case宏相应的子句中执行其中的表达式,也就是调用CL:ENSURE-DIRECTORY-EXIST函数创建/tmp/log。

如果总是希望执行CREATE-LOG-DIRECTORY这个选项来创建存放日志文件的目录,可以直接在代码中指定,只需要配合使用Common Lisp的handler-bindinvoke-restart函数即可,最终init-app函数的实现如下

1
2
3
4
5
6
7
(defun init-app ()
(format t "Application starting...~%")
(handler-bind
((file-error #'(lambda (c)
(declare (ignorable c))
(invoke-restart 'create-log-directory))))
(init-framework)))