模拟小于运算符的短路特性

发表于 2021-06-26 分类于实战CommonLisp Disqus：

~~忆往昔峥嵘岁月稠~~在Python的语言标准的Comparisions章节中提到

Also unlike C, expressions like a < b < c have the interpretation that is conventional in mathematics

也就是说，在C语言中要写成a < b && b < c的表达式，在Python中可以写成a < b < c。并且，标准中还提到

Comparisons can be chained arbitrarily, e.g., x < y <= z is equivalent to x < y and y <= z, except that y is evaluated only once (but in both cases z is not evaluated at all when x < y is found to be false).

一般将这种性质成为短路。因此，像2 < 1 < (1 / 0)这样的表达式在Python中不会引发异常，而是返回False。

Python的小于号能拥有短路特性，是因为它并非一个普通函数，而是有语言层面加持的操作符。而在Common Lisp（下称CL）中，小于号仅仅是一个普通函数，就像Haskell中的小于号也是一个函数一般。不同的是，CL的小于号能接受多于两个的参数

1	(< 1 2 3 -1) ; 结果为NIL

但它并没有短路特性

1	(< 1 2 3 -1 (/ 1 0)) ; 引发名为DIVISION-BY-ZERO的错误

要想模拟出具有短路特性的小于号，必须借助于宏的力量。

想生成什么样的代码

要想写出一个宏，必须先设想出它的语法，以及它会展开成什么样的代码。姑且为这个宏起名为less-than，它的语法应当为

1
2
3

(defmacro less-than (form &rest more-forms)
  ; TBC
  )

至于它的展开结果可以有多种选择。例如，可以(less-than 2 1 (/ 1 0))展开为自身具有短路特性的and形式

1	(and (< 2 1) (< 1 (/ 1 0)))

但就像在C语言中用宏朴素地实现计算二者最大值的MAX宏一样，上面的展开方式在一些情况下会招致重复求值

1	(less-than 1 (progn (print 'hello) 2) 3)

因此，起码要展开为and和let的搭配

(let ((g917 1)
      (g918 (progn (print 'hello) 2)))
  (and (< g917 g918)
       (let ((g919 3))
         (< g918 g919))))

要想展开为这种结构，可以如这般实现less-than

(defmacro less-than (form &rest more-forms)
  (labels ((aux (lhs forms)
             "LHS表示紧接着下一次要比较的、小于号的左操作数。"
             (unless forms
               (return-from aux))
             (let* ((rhs (gensym))
                    (rv (aux rhs (rest forms))))
               (if rv
                   `(let ((,rhs ,(first forms)))
                      (and (< ,lhs ,rhs)
                           ,rv))
                   `(< ,lhs ,(first forms))))))
    (cond ((null more-forms)
           `(< ,form))
          (t
           (let ((lhs (gensym)))
             `(let ((,lhs ,form))
                ,(aux lhs more-forms)))))))

用上面的输入验证一下是否会导致重复求值

CL-USER> (macroexpand-1 '(less-than 1 (progn (print 'hello) 2) 3))
(LET ((#:G942 1))
  (LET ((#:G943 (PROGN (PRINT 'HELLO) 2)))
    (AND (< #:G942 #:G943) (< #:G943 3))))
T

优化一下

显然less-than可以优化，只需要简单地运用递归的技巧即可

(defmacro less-than (form &rest more-forms)
  (cond ((<= (length more-forms) 1)
         `(< ,form ,@more-forms))
        (t
         (let ((lhs (gensym))
               (rhs (gensym)))
           `(let ((,lhs ,form)
                  (,rhs ,(first more-forms)))
              (and (< ,lhs ,rhs)
                   (less-than ,rhs ,@(rest more-forms))))))))

展开后的代码简短得多

CL-USER> (macroexpand-1 '(less-than 1 (progn (print 'hello) 2) 3))
(LET ((#:G955 1) (#:G956 (PROGN (PRINT 'HELLO) 2)))
  (AND (< #:G955 #:G956) (LESS-THAN #:G956 3)))
T

从AOP到method-combination

发表于 2021-06-14 分类于实战Elisp Disqus：

“实战Elisp”系列旨在讲述我使用Elisp定制Emacs的经验，抛砖引玉，还请广大Emacs同好不吝赐教——如果真的有广大Emacs用户的话，哈哈哈。

Emacs的org-mode用的是一门叫Org的标记语言，正如大部分的标记语言那样，它也支持无序列表和检查清单——前者以-（一个连字符、一个空格）为前缀，后者以- [ ]或- [x]为前缀（比无序列表多了一对方括号及中间的字母x）

此外，org-mode还为编辑这两种列表提供了快速插入新一行的快捷键M-RET（即按住alt键并按下回车键）。如果光标位于无序列表中，那么新的一行将会自动插入-前缀。遗憾的是，如果光标位于检查清单中，那么新一行并没有自动插入一对方括号

每次都要手动敲入[ ]还挺繁琐的。好在这是Emacs，它是可扩展的、可定制的。只需敲几行代码，就可以让Emacs代劳输入方括号了。

Emacs的AOP特性——`advice-add`

借助Emacs的describe-key功能，可以知道在一个org-mode的文件中按下M-RET时，Emacs会调用到函数org-insert-item上。要想让M-RET实现自动追加方括号的效果，马上可以想到简单粗暴的办法：

定义一个新的函数，并将M-RET绑定到它身上；
重新定义org-insert-item函数，使其追加方括号；

但不管是上述的哪一种，都需要连带着重新实现插入连字符、空格前缀的已有功能。有一种更温和的办法可以在现有的org-insert-item的基础上扩展它的行为，那就是Emacs的advice特性。

advice是面向切面编程范式的一种，使用Emacs的advice-add函数，可以在一个普通的函数被调用前或被调用后捎带做一些事情——比如追加一对方括号。对于这两个时机，分别可以直接用advice-add的:before和:after来实现，但用在这里都不合适，因为：

检测是否位于检查清单中，需要在调用org-insert-item前做；
追加一对方括号，则需要在org-insert-item之后做。

因此，正确的做法是使用:around来修饰原始的org-insert-item函数

(cl-defun lt-around-org-insert-item (oldfunction &rest args)
  "在调用了org-insert-item后识时务地追加 [ ]这样的内容。"
  (let ((is-checkbox nil)
        (line (buffer-substring-no-properties (line-beginning-position) (line-end-position))))
    ;; 检查当前行是否为checkbox
    (when (string-match-p "- \\[.\\]" line)
      (setf is-checkbox t))
    ;; 继续使用原来的org-insert-item插入文本
    (apply oldfunction args)
    ;; 决定要不要追加“ [ ]”字符串
    (when is-checkbox
      (insert "[ ] "))))

(advice-add 'org-insert-item :around #'lt-around-org-insert-item)

这下子，M-RET对检查清单也一视同仁了

Common Lisp的`method combination`

advice-add的:after、:around，以及:before在Common Lisp中有着完全同名的等价物，只不过不是用一个叫advice-add的函数，而是喂给一个叫defmethod的宏。举个例子，用defmethod可以定义出一个多态的len函数，对不同类型的入参执行不同的逻辑

(defgeneric len (x))

(defmethod len ((x string))
  (length x))

(defmethod len ((x hash-table))
  (hash-table-count x))

然后为其中参数类型为字符串的特化版本定义对应的:after、:around，以及:before修饰过的方法

(defmethod len :after ((x string))
  (format t "after len~%"))

(defmethod len :around ((x string))
  (format t "around中调用len前~%")
  (prog1
      (call-next-method)
    (format t "around中调用len后~%")))

(defmethod len :before ((x string))
  (format t "before len~%"))

这一系列方法的调用规则为：

先调用:around修饰的方法；
由于上述方法中调用了call-next-method，因此再调用:before修饰的方法；
调用不加修饰的方法（在CL中这称为primary方法）；
再调用:after修饰的方法；
最后，又回到了:around中调用call-next-method的位置。

咋看之下，Emacs的advice-add支持的修饰符要多得多，实则不然。在CL中，:after、:around，以及:before同属于一个名为standard的method combination，而CL还内置了其它的method combination。在《Other method combinations》一节中，作者演示了progn和list的例子。

如果想要模拟Emacs的advice-add所支持的其它修饰符，那么就必须定义新的method combination了。

可编程的编程语言——`define-method-combination`

曾经我以为，defmethod只能接受:after、:around，以及:before，认为这三个修饰符是必须在语言一级支持的特性。直到有一天我闯入了LispWorks的define-method-combination词条中，才发现它们也是三个平凡的修饰符而已。

(define-method-combination standard ()
  ((around (:around))
   (before (:before))
   (primary () :required t)
   (after (:after)))
  (flet ((call-methods (methods)
           (mapcar #'(lambda (method)
                       `(call-method ,method))
                   methods)))
    (let ((form (if (or before after (rest primary))
                    `(multiple-value-prog1
                         (progn ,@(call-methods before)
                                (call-method ,(first primary)
                                             ,(rest primary)))
                       ,@(call-methods (reverse after)))
                    `(call-method ,(first primary)))))
      (if around
          `(call-method ,(first around)
                        (,@(rest around)
                           (make-method ,form)))
          form))))

秉持“柿子要挑软的捏”的原则，让我来尝试模拟出advice-add的:after-while和:before-while的效果吧。

:after-while和:before-while的效果还是很容易理解的

Call function after the old function and only if the old function returned non-nil.

Call function before the old function and don’t call the old function if function returns nil.

因此，由define-method-combination生成的form中（犹记得伞哥在《PCL》中将它翻译为形式），势必要：

检查是否有被:before-while修饰的方法；
如果有，检查调用了被:before-while修饰的方法后的返回值是否为NIL；
如果没有，或者被:before-while修饰的方法的返回值为非NIL，便调用primary方法；
如果有被:after-while修饰的方法，并且primary方法的返回值不为NIL，就调用这些方法；
返回primary方法的返回值。

为了简单起见，尽管after-while和before-while变量指向的是多个“可调用”的方法，但这里只调用“最具体”的一个。

给这个新的method combination取名为emacs-advice，其具体实现已是水到渠成

(define-method-combination emacs-advice ()
  ((after-while (:after-while))
   (before-while (:before-while))
   (primary () :required t))
  (let ((after-while-fn (first after-while))
        (before-while-fn (first before-while))
        (result (gensym)))
    `(let ((,result (when ,before-while-fn
                      (call-method ,before-while-fn))))
       (when (or (null ,before-while-fn)
                 ,result)
         (let ((,result (call-method ,(first primary))))
           (when (and ,result ,after-while-fn)
             (call-method ,after-while-fn))
           ,result)))))

call-method（以及它的搭档make-method）是专门用于在define-method-combination中调用传入的方法的宏。

用一系列foobar方法来验证一番

(defgeneric foobar (x)
  (:method-combination emacs-advice))

(defmethod foobar (x)
  'hello)

(defmethod foobar :after-while (x)
  (declare (ignorable x))
  (format t "for side effect~%"))

(defmethod foobar :before-while (x)
  (evenp x))

(foobar 1) ;; 返回NIL
(foobar 2) ;; 打印“fo side effect”，并返回HELLO

后记

尽管我对CL赏识有加，但越是琢磨define-method-combination，就越会发现编程语言的能力是有极限的~~，除非超越编程语言~~。比如Emacs的advice-add所支持的:filter-args和:filter-return就无法用define-method-combination优雅地实现出来——并不是完全不行，只不过需要将它们合并在由:around修饰的方法之中。

非递归遍历二叉树到底有什么用

发表于 2021-05-03 Disqus：

准备过互联网公司的服务端岗位面试的人，对于二叉树的三种遍历方式想必是如数家珍。假设以类BinaryTree定义一棵二叉树

class BinaryTree:
    def __init__(self, left, right, value):
        self.left = left
        self.right = right
        self.value = value

实现一个前序遍历的算法便是信手拈来的事情

def preorder_traversal(tree, func):
    """前序遍历二叉树的每个节点。"""
    if tree is None:
        return
    func(tree.value)
    preorder_traversal(tree.left, func)
    preorder_traversal(tree.right, func)

随着行业曲率的增大，要求写出不使用递归的版本也没什么过分的

def iterative_preorder_traversal(tree, func):
    nodes = [tree]
    while len(nodes) > 0:
        node = nodes.pop()
        func(node)
        if node.left is not None:
            nodes.append(node.right)
        if node.left is not None:
            nodes.append(node.left)

一直以来，我觉得这种用一个显式的栈来代替递归过程中隐式的栈的做法就是镜花水月。但最近却找到了它的一个用武之地——用于实现iterator。

`iterator`是个啥？

这年头，iterator已经不是什么新鲜事物了，许多语言中都有支持，维基百科上有一份清单列出了比较知名的语言的iterator特性。按照Python官方的术语表中的定义，iterator表示一个数据流，反复调用其__next__方法可以一个接一个地返回流中的下一项数据。将内置函数iter作用于list、str、tuple类型的对象，可以获得相应的迭代器

$ cat get_iter.py
# -*- coding: utf8 -*-
if __name__ == '__main__':
    values = [
        [1, 2, 3],
        'Hello, world!',
        (True, None),
    ]
    for v in values:
        print('type of iter({}) is {}'.format(v, type(iter(v))))
$ python get_iter.py
type of iter([1, 2, 3]) is <class 'list_iterator'>
type of iter(Hello, world!) is <class 'str_iterator'>
type of iter((True, None)) is <class 'tuple_iterator'>

写一个前序遍历的`iterator`

一个iterator对象必须要实现__iter__和__next__方法：

__iter__只需要返回iterator对象自身即可；
顾名思义，__next__负责返回下一个元素。

仔细观察一下前文中的iterative_preorder_traversal函数可以看出：

nodes = [tree]属于初始化逻辑；
len(nodes) > 0用于判断是应当抛出StopIteration，还是应当继续返回下一个值（nodes.pop()）；
最后四行就是负责填充nodes，好让它可以在下一次调用__next__的时候有值可以返回的。

到这里，iterator的具体实现代码已经呼之欲出了

class BinaryTreePreorderIterator:
    def __init__(self, root):
        nodes = []
        if root is not None:
            nodes.append(root)
        self.nodes = nodes

    def __iter__(self):
        return self

    def __next__(self):
        if len(self.nodes) == 0:
            raise StopIteration
        node = self.nodes.pop()
        if node.right is not None:
            self.nodes.append(node.right)
        if node.left is not None:
            self.nodes.append(node.left)
        return node.value

构造一棵这样的满二叉树

用BinaryTreePreorderIterator可以正确地打印出每一个节点的值

if __name__ == '__main__':
    tree = BinaryTree(
        BinaryTree(
            BinaryTree(None, None, 1), 
            BinaryTree(None, None, 3), 
            2,
        ),
        BinaryTree(
            BinaryTree(None, None, 5), 
            BinaryTree(None, None, 7), 
            6,
        ),
        4,
    )
    for n in BinaryTreePreorderIterator(tree):
        print('{}\t'.format(n), end='')
# 打印内容为：4	2	1	3	6	5	7

`iterator`的优势

显然，iterator比起preorder_traversal更为灵活——很容易在for-in循环内添加各种各样的控制逻辑：用continue跳过一些值，或者用break提前结束遍历过程。这些在函数preorder_traversal中做起来会比较别扭。

聪明的你应该已经发现了，大可不必将preorder_traversal拆解到一个构造方法和一个__next__方法中。用generator写起来明明更加直观

def preorder_generator(tree):
    """返回一个能够以前序遍历的次序遍历二叉树节点的generator。"""
    nodes = [tree]
    while len(nodes) > 0:
        node = nodes.pop()
        yield node.value
        if node.left is not None:
            nodes.append(node.right)
        if node.left is not None:
            nodes.append(node.left)

但是，很多语言并不支持generator。与之相比，iterator要亲民得多，更容易移植。例如，即使是Common Lisp这种一穷二白的语言，也可以实现和Python的iterator以及for类似的效果

(in-package #:cl-user)

(defpackage #:com.liutos.binary-tree
  (:use #:cl))

(in-package #:com.liutos.binary-tree)

(defclass preorder-iterator ()
  ((nodes
    :initform nil)
   (tree
    :initarg :tree))
  (:documentation "前序遍历二叉树的迭代器"))

(defmethod initialize-instance :after ((instance preorder-iterator) &key)
  (with-slots (nodes tree)
      instance
    (when tree
      (push tree nodes))))

(defgeneric next (iterator)
  (:documentation "返回迭代器的下一个值。"))

(define-condition stop-iteration (error)
  ()
  (:documentation "Python中StopIteration异常的等价物。"))

(defmethod next ((iterator preorder-iterator))
  (with-slots (nodes) iterator
    (when (null nodes)
      (error 'stop-iteration))

    (let ((node (pop nodes)))
      ;; 一个节点的结构为：(值 左子树 右子树)
      (when (third node)
        (push (third node) nodes))
      (when (second node)
        (push (second node) nodes))
      (first node))))

(defmacro for-in (var iterator &body forms)
  "将iterator中的值逐个绑定到变量var上，并执行forms中的表达式。"
  (let ((iter (gensym)))
    `(let ((,iter ,iterator))
       (handler-case
           (loop
              (let ((,var (next ,iter)))
                ,@forms))
         (stop-iteration (c)
           (declare (ignorable c)))))))

(defparameter *tree*
  '(4 (2 (1 nil nil) (3 nil nil)) (6 (5 nil nil) (7 nil nil))))

(defun test-preorder-iterator ()
  "测试前序遍历迭代器。"
  (for-in n (make-instance 'preorder-iterator
                           :tree *tree*)
    (format t "~D~C" n #\Tab)))

后记

中序遍历和后序遍历也可以写成迭代器，证明略。

当你SET的时候，Redis到底在SET些什么

发表于 2021-04-17 Disqus：

准备过互联网公司的服务端岗位面试的人，对Redis中的5种数据类型想必是如数家珍。而网上很多面试题里也会出现这道题目

随着行业曲率的增大，光是知道有这些数据类型已经不够了，还得知道同一个类型也有不同的底层数据结构。例如同样是string类型，不同内容或不同长度会采用不同的编码方式：

127.0.0.1:6379> SET key1 "1"
OK
127.0.0.1:6379> SET key2 "value"
OK
127.0.0.1:6379> SET key3 "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
OK
127.0.0.1:6379> TYPE key1
string
127.0.0.1:6379> TYPE key2
string
127.0.0.1:6379> TYPE key3
string
127.0.0.1:6379> OBJECT ENCODING key1
"int"
127.0.0.1:6379> OBJECT ENCODING key2
"embstr"
127.0.0.1:6379> OBJECT ENCODING key3
"raw"

而hash类型也有两种底层实现

127.0.0.1:6379>  HSET myhash field1 "Hello"
(integer) 1
127.0.0.1:6379>  HSET myhash2 field1 "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
(integer) 1
127.0.0.1:6379> OBJECT ENCODING myhash
"ziplist"
127.0.0.1:6379> OBJECT ENCODING myhash2
"hashtable"

不知道你是否曾经好奇过，上文中的key1、key2、key3、myhash，以及myhash2这些键，与它们各自的值（前三个为string，后两个为hash）之间的关系又是存储在什么数据结构中的呢？

答案在意料之外，情理之中：键与值的关系，也是存储在一张哈希表中的，并且正是上文中的hashtable。

求证的办法当然是阅读Redis的源代码。

Redis命令的派发逻辑

阅读Redis的源码是比较轻松愉快的，一是因为其源码由简单易懂的C语言编写，二是因为源码仓库的README.md中对内部实现做了一番高屋建瓴的介绍。在README.md的server.c一节中，道出了有关命令派发的两个关键点

call() is used in order to call a given command in the context of a given client.

The global variable redisCommandTable defines all the Redis commands, specifying the name of the command, the function implementing the command, the number of arguments required, and other properties of each command.

位于文件src/server.c中的变量redisCommandTable定义了所有可以在Redis中使用的命令——为什么一个C语言项目里要用camelCase这种格格不入的命名风格呢——它的元素的类型为struct redisCommand，其中：

name存放命令的名字；
proc存放实现命令的C函数的指针；

比如高频使用的GET命令在redisCommandTable中就是这样定义的

1
2
3

{"get",getCommand,2,
 "read-only fast @string",
 0,NULL,1,1,1,0,0,0},

身为一名老解释器爱好者，对这种套路的代码当然是不会陌生的。我也曾在写过的、跑不起来的玩具解释器上用过类似的手法

Redis收到一道需要执行的命令后，根据命令的名字用lookupCommand找到一个命令（是个struct redisCommand类型的结构体），然后call函数做的事情就是调用它的proc成员所指向的函数而已

1	c->cmd->proc(c);

那么接下来，就要看看SET命令对应的C函数究竟做了些什么了。

`SET`命令的实现

redisCommonTable中下标为2的元素正是SET命令的定义

/* Note that we can't flag set as fast, since it may perform an
 * implicit DEL of a large key. */
{"set",setCommand,-3,
 "write use-memory @string",
 0,NULL,1,1,1,0,0,0},

其中函数setCommand定义在文件t_string.c中，它根据参数中是否有传入NX、XX、EX等选项计算出一个flags后，便调用setGenericCommand——顾名思义，这是一个通用的SET命令，它同时被SET、SETNX、SETEX，以及PSETEX四个Redis命令的实现函数所共用。

setGenericCommand调用了genericSetKey，后者定义在文件db.c中。尽管该函数上方的注释写着

All the new keys in the database should be created via this interface.

但~~人生不如意事十之八九~~事实并非如此。例如在命令RPUSH的实现函数rpushCommand中，调用了pushGenericCommand，后者直接调用了dbAdd往Redis中存入键和列表对象的关系。

言归正传。根据键存在与否，genericSetKey会调用dbAdd或dbOverwrite。而在dbAdd中，最终调用了dictAdd将键与值存入数据库中。

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

现在我们知道了，使用SET命令时传入的key和value，是存储在一个dict类型的数据结构中。

`HSET`命令的实现

依葫芦画瓢，Redis的HSET命令由位于文件t_hash.c中的函数hsetCommand实现，它会尝试转换要操作的hash值的编码方式。

1	hashTypeTryConversion(o,c->argv,2,c->argc-1);

如果hashTypeTryConversion发现要写入哈希表的任何一个键或者值的长度超过了server.hash_max_ziplist_value所规定的值，就会将hash类型的编码从ziplist转换为hashtable。server.hash_max_ziplist_value的值在文件config.c中通过宏设置，默认值为64——这正是上文中myhash2所对应的值的编码为hashtable的原因。

将思绪拉回到函数hsetCommand中。做完编码的转换后，它调用函数hashTypeSet，在编码为hashtable的世界线中，同样调用了dictAdd实现往哈希表中写入键值对。

殊途同归

结论

因此，在Redis中用以维持每一个键与其对应的值——这些值也许是string，也许是list，也许是hash——的关系的数据结构，与Redis中的一系列操作哈希表的命令——也许是HSET、也许HGET，也许是HDEL——所用的数据结构，不能说是毫不相关，起码是一模一样。

多重返回值的阵营九宫格

发表于 2021-03-14 Disqus：

通常在糊业务代码的时候，不管是函数、方法，还是宏，都只会有一个返回值。比如在C语言用于检查一个字符是否为阿拉伯数字的isdigit函数就只会返回是（1）或否（0）

#include <ctype.h>
#include <stdio.h>

int
main(int argc, char *argv[])
{
    char c = 'a';
    printf("isdigit('%c') is %d\n", c, isdigit(c));
    return 0;
}

但有时候如果一个函数、方法，或宏可以返回多个值的话会更加方便。例如，在Python中dict类型有一个实例方法get，它可以取得dict实例中与给定的键对应的值。但如果有一个键在字典中的值为None，那么光凭get的返回值无法准确判断这个键是否存在——除非你给它一个非None的默认值

# -*- coding: utf8 -*-
def test(d, key):
    print("d.get('{0}') is {1}\t'{0}' in d is {2}".format(key, d.get(key), key in d))

if __name__ == '__main__':
    d = {
        'foo': 'bar',
        'baz': None,
    }
    test(d, 'foo')
    test(d, 'baz')

发展了这么多年的编程语言，又怎么会连一次调用、多值返回这么简单的事情都做不到呢。事实上，有各种各样、各显神通的返回多个值的方法，我给其中的一些做了个分类

Lisp的`multiple-value-bind`

Common Lisp（简称为CL）的多重返回值当之无愧是其中最正统、最好用的实现方式。以它的内置函数truncate为例，它的第一个返回值为第一个参数除以第二个参数的商，第二个返回值为对应的余数

1
2
3

CL-USER> (truncate 10 3)
3
1

如果不加修饰地调用truncate，就像其它只返回一个值的函数一样，也只会拿到一个返回值

1
2
3

CL-USER> (let ((q (truncate 10 3)))
           (format t "q = ~D~%" q))
q = 3

除非用multiple-value-bind来捕获一个函数产生的所有返回值

CL-USER> (multiple-value-bind (q r)
             (truncate 10 3)
           (format t "q = ~D~8Tr = ~D~%" q r))
q = 3   r = 1

CL的方案的优点在于它十分灵活。即使将一个函数从返回单个值改为返回多个值，也不会导致原本调用该函数的位置要全部修改一遍——对修改封闭，对扩展开放（误）。

Go的多重返回值

踩在C语言肩膀上的Go也能够从函数中返回多个值。在io/ioutil包的官方文档中有大量的例子，比如用ReadAll方法从字符串衍生的流中读取全部内容，就会返回两个值

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"strings"
)

func main() {
	s := "Hello, world!"
	reader := strings.NewReader(s)
	bytes, err := ioutil.ReadAll(reader)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("bytes is %s", bytes)
}

Go以这种方式取代了C语言中用返回值表达成功与否、再通过指针传出读到的数据的风格。由于这个模式在有用的Go程序中到处出现，因此Gopher们用的都是定制的键盘（误）

不同于前文的multiple-value-bind，如果一个函数或方法返回多个值，那么调用者必须捕获每一个值，否则编译无法通过

➜  try cat try_read_all_ignore_err.go
package main

import (
	"fmt"
	"io/ioutil"
	"strings"
)

func main() {
	s := "Hello, world!"
	reader := strings.NewReader(s)
	bytes := ioutil.ReadAll(reader)
	fmt.Printf("bytes is %s", bytes)
}
➜  try go build try_read_all_ignore_err.go
# command-line-arguments
./try_read_all_ignore_err.go:12:8: assignment mismatch: 1 variable but ioutil.ReadAll returns 2 values

这一要求也是合理的，毕竟多重返回值机制主要用于向调用者传递出错原因——既然可能出错，那么就必须要检查一番。

Python和Rust的解构

就像CL的truncate函数一样，Python中的函数divmod也可以同时返回两个数相除的商和余数，并且咋看之下也是返回多个值的形式

# -*- coding: utf8 -*-
if __name__ == '__main__':
    q, r = divmod(10, 3)
    print('q = {}\tr = {}'.format(q, r))

但本质上，这是因为Python支持解构，同时divmod返回的是一个由商和余数组成的元组。这样的做法与CL的真·奥义·多重返回值的差异在于，如果只想要divmod的第一个值，那么等号左侧也要写成对应的结构

# -*- coding: utf8 -*-
if __name__ == '__main__':
    q, _ = divmod(10, 3)
    print('q = {}'.format(q))

在支持解构的语言中都可以模仿出多重返回值，例如Rust

fn divmod(a: u32, b: u32) -> (u32, u32) {
    (a / b, a % b)
}

fn main() {
    let (q, r) = divmod(10, 3);
    println!("q = {}\tr = {}", q, r);
}

Prolog的归一

到了Prolog这里，画风就有点不一样了。首先Prolog既没有函数，也没有方法，更没有宏。在Prolog中，像length/2和member/2这样的东西叫做functor，它们之于Prolog中的列表，就犹如CL的length和member之于列表、Python的len函数和in操作符之于列表，JavaScript的length属性和indexOf方法之于数组……

其次，Prolog并不“返回”一个functor的“调用结果”，它只是判断输入的查询是否成立，以及给出使查询成立的变量值。在第一个查询中，length/2的第二个参数为变量L，因此Prolog给出了使这个查询成立的L的值4；第二个查询中没有变量，Prolog只是简单地给出查询是否成立；第三个查询中，Prolog给出了四个能够使查询成立的变量X的值。

由于Prolog会给出查询中每一个变量的值，可以用这个特性来模拟多重返回值。例如，可以让Prolog一次性给出两个数字的和、差、积，和商

麻烦之处在于就算只想要得到两数之和，也必须用占位符填在后三个参数上：jjcc(10, 3, S, _, _, _)。

作弊的指针与全局变量

尽管在开篇的时候提到了C语言中的函数无法返回多个值，但如果像上文的Prolog那般允许修改参数的话，C语言也是可以做到的，谁让它有指针这个强力特性呢。例如，stat(2)函数就会将关于一个文件的信息填充到参数中所指向的结构体的内存中

#include <stdio.h>
#include <sys/stat.h>

int
main(int argc, char *argv[])
{
    char *path = "./try_stat.c";
    struct stat buf;
    stat(path, &buf);
    printf("inode's number of %s is %llu\n", path, buf.st_ino);
    return 0;
}

查看man 2 stat可以知道struct stat类型中有非常多的内容，这显然也是一种多重返回值。同样的手法，在Go中也可以运用，例如用于把从数据库中读取出来的行的数据写入目标数据结构的Scan方法。

最后，如果只要能让调用者感知就行，那么全局变量未尝不是一种通用的多重返回值机制。例如在C语言中的strtol函数，就会在无法转换出任何数字的时候返回0并设置errno，因此检查errno是必须的步骤

#include <stdio.h>
#include <stdlib.h>
#include <sys/errno.h>

void try_conversion(const char *str)
{
    long num = strtol(str, NULL, 10);
    if (errno == EINVAL || errno == ERANGE)
    {
        char message[64];
        snprintf(message, sizeof(message), "strtol(\"%s\")", str);
        perror(message);
        return;
    }
    printf("strtol(\"%s\") is %ld\n", str, num);
}

int
main(int argc, char *argv[])
{
    try_conversion("233");
    try_conversion("0");
    try_conversion("lisp");
    return 0;
}

鉴于errno是一个全局变量，strtol的使用者完全有可能忘记要检查。相比之下，Go的strconv包的函数都将转换过程中的错误以第二个参数的形式返回给调用者，用起来更安全。

后记

按照《代码写得不好，不要总觉得是自己抽象得不好》这篇文章的说法，代码写成什么样子完全是由产品经理决定的。但产品经理又怎么会在意你用的技术是怎么实现多重返回值的呢。综上所述，这个特性没用（误）。

全文完。

想生成什么样的代码

优化一下

Emacs的AOP特性——advice-add

Common Lisp的method combination

可编程的编程语言——define-method-combination

后记

iterator是个啥？

写一个前序遍历的iterator

iterator的优势

后记